Please use this identifier to cite or link to this item: https://doi.org/10.1145/1376616.1376678
Title: Minimization of tree pattern queries with constraints
Authors: Chen, D. 
Chan, C.-Y. 
Keywords: Chase
Integrity constraints
Query minimization
Simulation
Tree pattern queries
XML
Xpath
Issue Date: 2008
Source: 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.

SCOPUSTM   
Citations

15
checked on Dec 5, 2017

Page view(s)

42
checked on Dec 9, 2017

Google ScholarTM

Check

Altmetric


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