More Web Proxy on the site http://driver.im/

Article

Efficient algorithms for minimizing tree pattern queries

Author:

Prakash RamananAuthors Info & Claims

SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data

Pages 299 - 309

https://doi.org/10.1145/564691.564726

Published: 03 June 2002 Publication History

Abstract

We consider the problem of minimizing tree pattern queries (TPQ) that arise in XML and in LDAP-style network directories. In [Minimization of Tree Pattern Queries, Proc. ACM SIGMOD Intl. Conf. Management of Data, 2001, pp. 497-508], Amer-Yahia, Cho, Lakshmanan and Srivastava presented an O(n⁴) algorithm for minimizing TPQs in the absence of integrity constraints (Case 1); n is the number of nodes in the query. Then they considered the problem of minimizing TPQs in the presence of three kinds of integrity constraints: required-child, required-descendant and subtype (Case 2). They presented an O(n⁶) algorithm for minimizing TPQs in the presence of only required-child and required-descendant constraints (i.e., no subtypes allowed; Case 3). We present O(n²), O(n⁴) and O(n²) algorithms for minimizing TPQs in these three cases, respectively, based on the concept of graph simulation. We believe that our O(n²) algorithms for Cases 1 and 3 are runtime optimal.

References

[1]

S. Abiteboul, P. Buneman and D. Suciu. Data on the Web. Morgan Kaufman, San Francisco, CA, 2000.]]

[2]

S. Amer-Yahia, SR. Cho, L. V. S. Lakshmanan and D. Srivastava. Minimization of Tree Pattern Queries, Proc. ACM SIGMOD Intl. Conf. Management of Data, 2001, pp. 497-508.]]

Digital Library

[3]

B. Bloom and R. Paige. Transformational Design and Implementation of a New Efficient Solution to the Ready Simulation Problem, Science of Computer Programming24(1995), pp. 189-220.]]

Digital Library

[4]

P. Buneman, S. Davidson, M. Fernandez and D. Suciu. Adding Structure to Unstructured Data, Proc. Internat. Conf. Database Theory, 1997, pp. 336-350.]]

Digital Library

[5]

D. Calvanese, G. De Giacomo and M. Lenzerini. On the Decidability of Query Containment under Constraints, Proc. 17th ACM Symp. Principles of Database Systems, 1998, pp. 149-158.]]

Digital Library

[6]

D. D. Chamberlin, J. Robie and D. Florescu. Quilt: An XML Query Language for Heterogeneous Data Sources, WebDB 2000.]]

Digital Library

[7]

A. K. Chandra and P. M. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases, Proc. 9th ACM Symp. Theory of Computing, 1977, pp. 77-90.]]

Digital Library

[8]

A. Deutch, M. Fernandez, D. Florescu, A. Levy and D. Suciu. A Query Language for XML, Intl. WWW Conf., 1999.]]

Digital Library

[9]

W. Fan and J. Simeon. Integrity Constraints for XML, Proc. 19th ACM Symp. Principles of Database Systems, 2000, pp. 23-34.]]

Digital Library

[10]

D. Florescu, A. Levy and D. Suciu. Query Containment for Conjunctive Queries with Regular Expressions, Proc. 17th ACM Symp. Principles of Database Systems, 1998, pp. 139-148.]]

Digital Library

[11]

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., NY, 1979.]]

Digital Library

[12]

M. R. Henzinger, T. A. Henzinger and P. W. Kopke. Computing Simulations on Finite and Infinite Graphs, Proc. IEEE Symp. Foundations of Computer Science, 1995, pp. 453-462.]]

Digital Library

[13]

T. Howes, M. Smith and G. S. Wood. Understanding and Deploying LDAP Directory Services. MacMillan Technical Publishing, Indianapolis, 1999.]]

Digital Library

[14]

H. V. Jagadish, L. V. S. Lakshmanan, T. Milo, D. Srivastava and D. Vista. Querying Network Directories, Proc. ACM SIGMOD Intl. Conf. Management of Data, 1999.]]

Digital Library

[15]

D. Maier, A. O. Mendelzon and Y. Sagiv. Testing Implications of Data Dependencies, ACM Trans. Database Systems4(1979), pp. 455-469.]]

Digital Library

[16]

G. Miklau and D. Suciu. Containment and Equivalence for an XPath Fragment, Proc. 21st ACM Symp. Principles of Database Systems, 2002.]]

Digital Library

[17]

Y. Papakonstantinou and V. Vianu. DTD Inference for Views of XML Data, Proc. 19th ACM Symp. Principles of Database Systems, 2000, pp. 35-46.]]

Digital Library

[18]

P. Ramanan. Inferring DTDs for Views of XML Data, Tech. Rep. WSUCS-01-1, Comp. Sci. Dept, Wichita State Univ, August 2001.]]

[19]

J. D. Ullman. Principles of Database and Knowledge Base Systems, Vol. I & II. Computer Science Press, Maryland, 1989.]]

Digital Library

[20]

P. T. Wood. Optimizing Web Queries Using Document Type Definitions, Proc. 2nd ACM CIKM Intl. Workshop on Web Information and Data Management, 1999, pp. 28-32.]]

Digital Library

[21]

P. T. Wood. On the Equivalence of XML Patterns, Proc. 1st Intl. Conf. Computational Logic, Lecture Notes in Artificial Intelligence 1861, pp. 1152-1166, Springer Verlag, New York, 2000.]]

[22]

P. T. Wood. Rewriting XQL Queries on XML Repositories, Proc. 17th British National Conf. on Databases, Lecture Notes in Computer Science 1832, pp. 209-226, Springer Verlag, New York, 2000.]]

Digital Library

[23]

P. T. Wood. Minimising Simple XPath Expressions, WebDB 2001.]]

[24]

World Wide Web Consortium. XML Path Language (XPath), W3C Recommendation, Version 1.0, November 1999. See http://www.w3.org/TR/xpath.]]

[25]

World Wide Web Consortium. XQuery 1.0: An XML Query Language, W3C Recommendation, Version 1.0, December 2001. See http://www.w3.org/TR/xquery.]]

Cited By

Hao LYu XZhang TSchulzrinne H(2022)Distributed MQTT Brokers at Network Edges: A Study on Message Dissemination2022 IEEE International Conferences on Internet of Things (iThings) and IEEE Green Computing & Communications (GreenCom) and IEEE Cyber, Physical & Social Computing (CPSCom) and IEEE Smart Data (SmartData) and IEEE Congress on Cybermatics (Cybermatics)10.1109/iThings-GreenCom-CPSCom-SmartData-Cybermatics55523.2022.00044(17-24)Online publication date: Aug-2022
https://doi.org/10.1109/iThings-GreenCom-CPSCom-SmartData-Cybermatics55523.2022.00044
CzerwiŃski WMartens WNiewerth MParys P(2018)Minimization of Tree PatternsJournal of the ACM10.1145/318028165:4(1-46)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1145/3180281
Du RYang JCao YWang H(2018)Personalized graph pattern matching via limited simulationKnowledge-Based Systems10.1016/j.knosys.2017.11.008141:C(31-43)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.knosys.2017.11.008
Show More Cited By

Index Terms

Efficient algorithms for minimizing tree pattern queries

Recommendations

Minimization of tree pattern queries with constraints
SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

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, ...
Efficient algorithms for descendant-only tree pattern queries

Tree pattern matching is a fundamental problem that has a wide range of applications in Web data management, XML processing, and selective data dissemination. In this paper we develop efficient algorithms for the tree homeomorphism problem, i.e., the ...
Faster bit-parallel algorithms for unordered pseudo-tree matching and tree homeomorphism

In this paper, we consider the unordered pseudo-tree matching problem, which is a problem of, given two unordered labeled trees P and T, finding all occurrences of P in T via such many-to-one matchings that preserve node labels and parent-child ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '02: Proceedings of the 2002 ACM SIGMOD international conference on Management of data

June 2002

654 pages

ISBN:1581134975

DOI:10.1145/564691

Conference Chair:
Bongki Moon
University of Wisconsin - Madison
,
General Chair:
David DeWitt
University of Wisconsin - Madison
,
Program Chair:
Michael Franklin
University of California, Berkeley

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS02

Sponsor:

SIGMOD/PODS02: International Conference on Management of Data and Symposium on Principles Database and Systems

June 3 - 6, 2002

Wisconsin, Madison

Acceptance Rates

SIGMOD '02 Paper Acceptance Rate 42 of 240 submissions, 18%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

56
Total Citations
View Citations
863
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Hao LYu XZhang TSchulzrinne H(2022)Distributed MQTT Brokers at Network Edges: A Study on Message Dissemination2022 IEEE International Conferences on Internet of Things (iThings) and IEEE Green Computing & Communications (GreenCom) and IEEE Cyber, Physical & Social Computing (CPSCom) and IEEE Smart Data (SmartData) and IEEE Congress on Cybermatics (Cybermatics)10.1109/iThings-GreenCom-CPSCom-SmartData-Cybermatics55523.2022.00044(17-24)Online publication date: Aug-2022
https://doi.org/10.1109/iThings-GreenCom-CPSCom-SmartData-Cybermatics55523.2022.00044
CzerwiŃski WMartens WNiewerth MParys P(2018)Minimization of Tree PatternsJournal of the ACM10.1145/318028165:4(1-46)Online publication date: 25-Jul-2018
https://dl.acm.org/doi/10.1145/3180281
Du RYang JCao YWang H(2018)Personalized graph pattern matching via limited simulationKnowledge-Based Systems10.1016/j.knosys.2017.11.008141:C(31-43)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.knosys.2017.11.008
Czerwinski WMartens WNiewerth MParys P(2017)Optimizing Tree Patterns for Querying Graph- and Tree-Structured DataACM SIGMOD Record10.1145/3093754.309375946:1(15-22)Online publication date: 12-May-2017
https://dl.acm.org/doi/10.1145/3093754.3093759
Czerwinski WMartens WNiewerth MParys PMilo TTan W(2016)Minimization of Tree Pattern QueriesProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902295(43-54)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902295
Venetis TStoilos GVassalos V(2016)Rewriting Minimisations for Efficient Ontology-Based Query Answering2016 IEEE 28th International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI.2016.0168(1095-1102)Online publication date: Nov-2016
https://doi.org/10.1109/ICTAI.2016.0168
Chakraborty SCortesi AChaki N(2016)A uniform representation of multi-variant data in intensive-query databasesInnovations in Systems and Software Engineering10.1007/s11334-016-0275-912:3(163-176)Online publication date: 1-Sep-2016
https://dl.acm.org/doi/10.1007/s11334-016-0275-9
Hachicha MDarmont J(2013)A Survey of XML Tree PatternsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2011.20925:1(29-46)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1109/TKDE.2011.209
Zeng QJiang XZhuge H(2012)Adding logical operators to tree pattern queries on graph-structured dataProceedings of the VLDB Endowment10.14778/2212351.22123555:8(728-739)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.14778/2212351.2212355
Cong GFan WKementsietsidis ALi JLiu X(2012)Partial Evaluation for Distributed XPath Query Processing and BeyondACM Transactions on Database Systems10.1145/2389241.238925137:4(1-43)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1145/2389241.2389251
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents