Please use this identifier to cite or link to this item:
Title: Minimization of tree pattern queries with constraints
Authors: Chen, D. 
Chan, C.-Y. 
Keywords: Chase
Integrity constraints
Query minimization
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.
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
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 Nov 28, 2021

Page view(s)

checked on Nov 18, 2021

Google ScholarTM



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