Please use this identifier to cite or link to this item:
|dc.title||Minimization of tree pattern queries with constraints|
|dc.identifier.citation||Chen, D.,Chan, C.-Y. (2008). Minimization of tree pattern queries with constraints. Proceedings of the ACM SIGMOD International Conference on Management of Data : 609-622. ScholarBank@NUS Repository. <a href="https://doi.org/10.1145/1376616.1376678" target="_blank">https://doi.org/10.1145/1376616.1376678</a>|
|dc.description.abstract||Tree pattern queries (TPQs) provide a natural and easy formalism to query tree-structured XML data, and the efficient processing of such queries has attracted a lot of attention. Since the size of a TPQ is a key determinant of its evaluation cost, recent research has focused on the problem of query minimization using integrity constraints to eliminate redundant query nodes; specifically, TPQ minimization has been studied for the class of forward and subtype constraints (FT-constraints). In this paper, we explore the TPQ minimization problem further for a richer class of FBST-constraints that includes not only FT-constraints but also backward and sibling constraints. By exploiting the properties of minimal queries under FBST-constraints, we propose efficient algorithms to both compute a single minimal query as well as enumerate all minimal queries. In addition, we also develop more efficient minimization algorithms for the previously studied class of FT-constraints. Our experimental study demonstrates the effectiveness and efficiency of query minimization using FBST-constraints. Copyright 2008 ACM.|
|dc.subject||Tree pattern queries|
|dc.description.sourcetitle||Proceedings of the ACM SIGMOD International Conference on Management of Data|
|Appears in Collections:||Staff Publications|
Show simple item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.