Please use this identifier to cite or link to this item:
DC FieldValue
dc.titleMinimization of tree pattern queries with constraints
dc.contributor.authorChen, D.
dc.contributor.authorChan, C.-Y.
dc.identifier.citationChen, 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="" target="_blank"></a>
dc.description.abstractTree 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.subjectIntegrity constraints
dc.subjectQuery minimization
dc.subjectTree pattern queries
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.sourcetitleProceedings 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.

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.