research-article

Bag equivalence of tree patterns

Authors:

Yaacov Y. WeissAuthors Info & Claims

ACM Transactions on Database Systems (TODS), Volume 36, Issue 4

Article No.: 24, Pages 1 - 35

https://doi.org/10.1145/2043652.2043657

Published: 19 December 2011 Publication History

Abstract

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This article is the first to focus on bag semantics for tree pattern queries. In particular, the problem of bag equivalence of a large class of tree pattern queries (which can be used to model XPath) is explored. The queries can contain unions, branching, label wildcards, the vertical child and descendant axes, the horizontal following and following-sibling axes, as well as positional (i.e., first and last) axes. Equivalence characterizations are provided, and their complexity is analyzed. As the descendant axis involves a recursive relationship, this article is also the first to address bag equivalence over recursive queries, in any setting.

References

[1]

Berglund, A. 2006. Extensible stylesheet language (XSL) version 1.1. http://www.w3.org/TR/xsl.

[2]

Boag, S., Chamberlin, D., Fernández, M. F., Florescu, D., Robie, J., and Siméon, J. 2007. XQuery 1.0: An XML query language. http://www.w3.org/TR/xquery.

[3]

Chaudhuri, S. and Vardi, M. Y. 1993. Optimization of real conjunctive queries. In Proceedings of the 12th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. ACM Press, 59--70.

Digital Library

[4]

Clark, J. and DeRose, S. 1999. XML path language (XPath) version 1.0. http://www.w3.org/TR/xpath.

[5]

Cohen, S. 2009. Equivalence of queries that are sensitive to multiplicities. VLDB J. 18, 3, 765--785.

Digital Library

[6]

Cohen, S., Nutt, W., and Sagiv, Y. 2007. Deciding equivalences among conjunctive aggregate queries. J. ACM 54, 2.

Digital Library

[7]

Cohen, S., Sagiv, Y., and Nutt, W. 2005. Equivalences among aggregate queries with negation. ACM Trans. Comput. Log. 6, 2, 328--360.

Digital Library

[8]

Cohen, S. and Weiss, Y. Y. 2010. Bag equivalence of xpath queries. In Proceedings of the International Conference on Database Theory (ICDT). ACM, 116--128.

Digital Library

[9]

Davis, M. 1982. Computability and Unsolvability. Dover Publications.

[10]

DeRose, S., Maler, E., and Daniel, Jr., R. 2001a. XML pointer language (XPointer) version 1.0. http://www.w3. org/TR/WD-xptr.

[11]

DeRose, S., Maler, E., and Orchard, D. 2001b. XML linking language (XLink) version 1.0. http://www.w3. org/TR/xlink.

[12]

Deutsch, A. and Tannen, V. 2001. Containment and integrity constraints for xpath. In Proceedings of the International Workshop on Knowledge Representation Meets Databases (KRDB).

[13]

Ioannidis, Y. E. and Ramakrishnan, R. 1995. Containment of conjunctive queries: Beyond relations as sets. ACM Trans. Datab. Syst. 20, 3, 288--324.

Digital Library

[14]

Klug, A. C. 1988. On conjunctive queries containing inequalities. J. ACM 35, 1, 146--160.

Digital Library

[15]

Miklau, G. and Suciu, D. 2004. Containment and equivalence for a fragment of xpath. J. ACM 51, 1, 2--45.

Digital Library

[16]

Neven, F. and Schwentick, T. 2006. On the complexity of xpath containment in the presence of disjunction, dtds, and variables. Logical Methods Comput. Sci. 2, 3.

[17]

Papadimitriou, C. M. 1994. Computational Complexity. Addison-Wesley, Reading, MA.

[18]

ten Cate, B. and Lutz, C. 2007. The complexity of query containment in expressive fragments of xpath 2.0. In Proceedings of the ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS). 73--82.

Digital Library

[19]

Thompson, H. S., Beech, D., Maloney, M., and Mendelsohn, N. 2004. XML schema part 1: Structures. http://www.w3.org/TR/xmlschema-1.

[20]

Wen-Guey, T. 1996. On path equivalence of nondeterministic finite automata. Inf. Process. Lett. 58, 1, 43--46.

Digital Library

[21]

Wood, P. T. 2003. Containment for xpath fragments under dtd constraints. In Proceedings of the International Conference on Database Theory (ICDT). 297--311.

Digital Library

Cited By

Afrati FChirkova R(2019)Answering Queries Using Views, Second EditionSynthesis Lectures on Data Management10.2200/S00884ED2V01Y201811DTM05414:3(1-275)Online publication date: 15-Apr-2019
https://doi.org/10.2200/S00884ED2V01Y201811DTM054
Afrati FChirkova R(2017)Answering Queries Using ViewsSynthesis Lectures on Data Management10.2200/S00805ED1V01Y201709DTM0469:2(1-235)Online publication date: Dec-2017
https://doi.org/10.2200/S00805ED1V01Y201709DTM046

Index Terms

Bag equivalence of tree patterns
1. Information systems
  1. Data management systems
    1. Query languages
2. Theory of computation
  1. Design and analysis of algorithms
  2. Theory and algorithms for application domains
    1. Database theory
      1. Database query languages (principles)

Recommendations

Bag equivalence of XPath queries
ICDT '10: Proceedings of the 13th International Conference on Database Theory

When a query is evaluated under bag semantics, each answer is returned as many times as it has derivations. Bag semantics has long been recognized as important, especially when aggregation functions will be applied to query results. This paper is the ...
Equivalence of queries combining set and bag-set semantics
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

The query equivalence problem has been studied extensively for set-semantics and, more recently, for bag-set semantics. However, SQL queries often combine set and bag-set semantics. For example, an SQL query that returns a multiset of elements may call ...
Equivalence of queries that are sensitive to multiplicities

The query equivalence problem has been studied extensively for set-semantics and, more recently, for bag and bag-set semantics. However, SQL queries often combine set, bag and bag-set semantics. For example, an SQL query that returns a multiset of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Database Systems

ACM Transactions on Database Systems Volume 36, Issue 4

December 2011

271 pages

ISSN:0362-5915

EISSN:1557-4644

DOI:10.1145/2043652

Issue’s Table of Contents

Copyright © 2011 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 December 2011

Accepted: 01 February 2011

Revised: 01 February 2011

Received: 01 September 2010

Published in TODS Volume 36, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Israel Science Foundation

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
275
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Afrati FChirkova R(2019)Answering Queries Using Views, Second EditionSynthesis Lectures on Data Management10.2200/S00884ED2V01Y201811DTM05414:3(1-275)Online publication date: 15-Apr-2019
https://doi.org/10.2200/S00884ED2V01Y201811DTM054
Afrati FChirkova R(2017)Answering Queries Using ViewsSynthesis Lectures on Data Management10.2200/S00805ED1V01Y201709DTM0469:2(1-235)Online publication date: Dec-2017
https://doi.org/10.2200/S00805ED1V01Y201709DTM046

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents