Please use this identifier to cite or link to this item:
|Title:||Minimization of tree pattern queries with constraints||Authors:||Chen, D.
Tree pattern queries
|Issue Date:||2008||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. https://doi.org/10.1145/1376616.1376678||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.||Source Title:||Proceedings of the ACM SIGMOD International Conference on Management of Data||URI:||http://scholarbank.nus.edu.sg/handle/10635/41198||ISBN:||9781605581026||ISSN:||07308078||DOI:||10.1145/1376616.1376678|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jun 16, 2019
checked on Jun 14, 2019
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.