Article

Equivalence of queries combining set and bag-set semantics

Author:

Sara CohenAuthors Info & Claims

PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 70 - 79

https://doi.org/10.1145/1142351.1142362

Published: 26 June 2006 Publication History

Abstract

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 a subquery or view that returns a set of elements. As another example, in SQL one can compute a multiset-union of queries, each of which returns a set of answers. This paper presents combined semantics, which formally models query evaluation combining set and bag-set semantics. The equivalence problem for queries evaluated under combined semantics is studied. A sufficient condition for equivalence is presented. For several important common classes of queries necessary and sufficient conditions for equivalence are presented.

References

[1]

A. Aho, Y. Sagiv, and J. Ullman. Efficient optimization of a class of relational expressions. ACM Transactions on Database Systems, 4(4):435--454, 1979.

Digital Library

[2]

D. Calvanese, G. De Giacomo, and M. Y. Vardi. Decidable containment of recursive queries. In Proc 9th International Conference on Database Theory, Lecture Notes in Computer Science, pages 330--345, Siena (Italy), Jan. 2003. Springer-Verlag.

Digital Library

[3]

A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. 9th Annual ACM Symposium on Theory of Computing, 1977.

Digital Library

[4]

S. Chaudhuri and M. Vardi. Optimization of real conjunctive queries. In Proc. 12th Symposium on Principles of Database Systems, Washington (D.C., USA), May 1993. ACM Press.

Digital Library

[5]

C. Chekuri and A. Rajaraman. Conjunctive query containment revisited. Theoretical Computer Science, 239(2):211--229, 2000.

Digital Library

[6]

S. Cohen, W. Nutt, and Y. Sagiv. Containment of aggregate queries. In Proc 9th International Conference on Database Theory, Lecture Notes in Computer Science, Siena (Italy), Jan. 2003. Springer-Verlag.

Digital Library

[7]

S. Cohen, W. Nutt, and Y. Sagiv. Equivalences among aggregate queries with negation. ACM Transactions on Computational Logic, 6(2), 2005.

Digital Library

[8]

S. Cohen, W. Nutt, and A. Serebrenik. Rewriting aggregate queries using views. In C. Papadimitriou, editor, Proc. 18th Symposium on Principles of Database Systems, Philadelphia (Pennsylvania, USA), May 1999. ACM Press.

Digital Library

[9]

S. Cosmadakis and P. Kanellakis. Functional and inclusion dependencies: A graph theoretic approach. In Proc. 3rd Symposium on Principles of Database Systems, Waterloo (Ontario, Canada), Apr. 1984. ACM Press.

Digital Library

[10]

Y. Ioannidis and R. Ramakrishnan. Beyond relations as sets. ACM Transactions on Database Systems, 20(3):288--324, 1995.

Digital Library

[11]

T. S. Jayram, P. Kolaitis, and E. Vee. The containment problem for "real" conjunctive queries with inequalities. In Proc. 25th Symposium on Principles of Database Systems, Chicago (Illinois, USA), June 2006. ACM Press.

Digital Library

[12]

D. Johnson and A. Klug. Testing containment of conjunctive queries under functional and inclusion dependencies. In Proc. 1st Symposium on Principles of Database Systems, pages 164--169, Los Angeles (California, USA), Mar. 1982. ACM Press.

Digital Library

[13]

D. Johnson and A. Klug. Optimizing conjunctive queries that contain untyped variables. SIAM Journal on Computing, 12(4):616--640, 1983.

Digital Library

[14]

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

Digital Library

[15]

A. Levy, I. S. Mumick, Y. Sagiv, and O. Shmueli. Equivalence, query-reachability, and satisfiability in datalog extensions. In Proc. 12th Symposium on Principles of Database Systems, pages 109--122, Washington (D.C., USA), May 1993. ACM Press.

Digital Library

[16]

A. Levy, I. S. Mumick, Y. Sagiv, and O. Shmueli. Static analysis in datalog extensions. J. ACM, 48(5):971--1012, 2001.

Digital Library

[17]

A. Levy and Y. Sagiv. Semantic query optimization in datalog programs. In Proc. 14th Symposium on Principles of Database Systems, pages 163--173, San Jose (California, USA), Proc. 14th Symposium on Principles of Database Systems 1995. ACM Press.

Digital Library

[18]

W. Nutt, Y. Sagiv, and S. Shurin. Deciding equivalences among aggregate queries. In J. Paredaens, editor, Proc. 17th Symposium on Principles of Database Systems, pages 214--223, Seattle (Washington, USA), June 1998. ACM Press. Long version as Report of Esprit LTR DWQ.

Digital Library

[19]

Y. Sagiv and Y. Saraiya. Minimizing restricted-fanout queries. Discrete Applied Mathematics, 40:245--264, 1992.

Digital Library

[20]

Y. Sagiv and M. Yannakakis. Equivalence among relational expressions with the union and difference operators. J. ACM, 27(4):633--655, 1981.

Digital Library

[21]

E. Sciore. Inclusion dependencies and the universal instance. In Proc. 2nd Symposium on Principles of Database Systems, Atlanta (Georgia, USA), Mar. 1983. ACM Press.

Digital Library

[22]

J. D. Ullman. Principles of Database and Knowledge-Base Systems, volume II. Computer Science Press, 1988.

Digital Library

[23]

R. van der Meyden. The complexity of querying indefinite data about linearly ordered domains. In Proc. 11th Symposium on Principles of Database Systems, pages 331--345, San Diego (California, USA), May 1992. ACM Press.

Digital Library

[24]

F. Wei and G. Lausen. Conjunctive query containment in the presence of disjunctive integrity constraints. In Proceedings of the 9th International Workshop on Knowledge Representation meets Databases, Toulouse (France), Apr. 2002.

[25]

X. Zhang and Z. Özsoyoglu. Implication and referential constraints: A new formal reasoning. IEEE Transactions on Knowledge and Data Engineering, 9(6):894--910, 1997.

Digital Library

Cited By

Haynes BAlotaibi RPavlenko ALeeka JJindal ATian Y(2023)GEqO: ML-Accelerated Semantic Equivalence DetectionProceedings of the ACM on Management of Data10.1145/36267101:4(1-25)Online publication date: 12-Dec-2023
Afrati FChirkova R(2022)Answering Queries Using Views, Second EditionundefinedOnline publication date: 26-Feb-2022
Spasić MJaničić M(2021)Verification supported refactoring of embedded sqlSoftware Quality Journal10.1007/s11219-020-09517-y29:3(629-665)Online publication date: 1-Sep-2021
Show More Cited By

Index Terms

Equivalence of queries combining set and bag-set semantics
1. Information systems
  1. Data management systems
    1. Query languages
  2. Information retrieval
    1. Information retrieval query processing

Recommendations

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 ...
Query containment under bag and bag-set semantics

Conjunctive queries (CQs) are at the core of query languages encountered in many logic-based research fields such as AI, or database systems. The majority of existing work assumes set semantics but often in real applications the manipulation of ...
Pulling Conjunctive Query Equivalence out of the Bag
CIKM '14: Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management

We present LECQTER, a tool for generating a 'perfect example' database, called exemplar, for a given conjunctive query. Indeed, exemplars separate the given query from any non-equivalent query. Therefore, LECQTER reduces the query equivalence problem to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2006

382 pages

ISBN:1595933182

DOI:10.1145/1142351

General Chair:
Georg Gottlob
Vienna University of Technology
,
Program Chair:
Jan Van den Bussche
Hasselt University

Copyright © 2006 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: 26 June 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SIGMOD/PODS06

Sponsor:

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

June 26 - 28, 2006

IL, Chicago, USA

Acceptance Rates

PODS '06 Paper Acceptance Rate 35 of 185 submissions, 19%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
773
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Haynes BAlotaibi RPavlenko ALeeka JJindal ATian Y(2023)GEqO: ML-Accelerated Semantic Equivalence DetectionProceedings of the ACM on Management of Data10.1145/36267101:4(1-25)Online publication date: 12-Dec-2023
Afrati FChirkova R(2022)Answering Queries Using Views, Second EditionundefinedOnline publication date: 26-Feb-2022
Spasić MJaničić M(2021)Verification supported refactoring of embedded sqlSoftware Quality Journal10.1007/s11219-020-09517-y29:3(629-665)Online publication date: 1-Sep-2021
Konstantinidis GMogavero FSuciu DSkritek SKoch C(2019)Attacking DiophantusProceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/3294052.3319689(399-413)Online publication date: 25-Jun-2019
Green T(2018)Bag SemanticsEncyclopedia of Database Systems10.1007/978-1-4614-8265-9_979(252-258)Online publication date: 7-Dec-2018
Kaminski MKostylev EGrau B(2017)Query Nesting, Assignment, and Aggregation in SPARQL 1.1ACM Transactions on Database Systems10.1145/308389842:3(1-46)Online publication date: 12-Aug-2017
Green T(2017)Bag SemanticsEncyclopedia of Database Systems10.1007/978-1-4899-7993-3_979-2(1-7)Online publication date: 1-Apr-2017
Kaminski MKostylev ECuenca Grau BBourdeau JHendler JNkambou RHorrocks IZhao B(2016)Semantics and Expressive Power of Subqueries and Aggregates in SPARQL 1.1Proceedings of the 25th International Conference on World Wide Web10.1145/2872427.2883022(227-238)Online publication date: 11-Apr-2016
Amsterdamer YDeutch DMilo TTannen V(2012)On Provenance MinimizationACM Transactions on Database Systems10.1145/2389241.238924937:4(1-36)Online publication date: 1-Dec-2012
Chirkova RDeutsch A(2012)Equivalence and minimization of conjunctive queries under combined semanticsProceedings of the 15th International Conference on Database Theory10.1145/2274576.2274604(262-273)Online publication date: 26-Mar-2012
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