research-article

Query containment in entity SQL

Authors:

Guillem Rull,

Philip A. Bernstein,

Ivo Garcia dos Santos,

Yannis Katsis,

Sergey Melnik,

Ernest TenienteAuthors Info & Claims

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

Pages 1169 - 1172

https://doi.org/10.1145/2463676.2463711

Published: 22 June 2013 Publication History

Get Access

Abstract

We describe a software architecture we have developed for a constructive containment checker of Entity SQL queries defined over extended ER schemas expressed in Microsoft's Entity Data Model. Our application of interest is compilation of object-to-relational mappings for Microsoft's ADO.NET Entity Framework, which has been shipping since 2007. The supported language includes several features which have been individually addressed in the past but, to the best of our knowledge, they have not been addressed all at once before. Moreover, when embarking on an implementation, we found no guidance in the literature on how to modularize the software or apply published algorithms to a commercially-supported language. This paper reports on our experience in addressing these real-world challenges.

References

[1]

A. Adya, J. A. Blakeley, S. Melnik, and S. Muralidhar. Anatomy of the ADO.NET Entity Framework. SIGMOD 2007, pp. 877--888.

Digital Library

Google Scholar

[2]

A. Calì. Containment of Conjunctive Queries over Conceptual Schemata. DASFAA 2006, pp. 628--643.

Digital Library

Google Scholar

[3]

E. P. F. Chan. Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992, pp. 202--211.

Digital Library

Google Scholar

[4]

A.K. Chandra, and P.M. Merlin. Optimal implementation of conjunctive queries in relational data bases. 9th ACM Symposium on Theory of Computing, 1977, pp. 77--90.

Digital Library

Google Scholar

[5]

C. Farré, W. Nutt, E. Teniente, and T. Urpí. Containment of Conjunctive Queries over Databases with Null Values. ICDT 2007, pp. 389--403.

Digital Library

Google Scholar

[6]

D. S. Johnson, and A. C. Klug. Testing Containment of Conjunctive Queries under Functional and Inclusion Depend-encies. J. Comput. Syst. Sci. 28(1) (1984), pp. 167--189.

Crossref

Google Scholar

[7]

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

Digital Library

Google Scholar

[8]

C. Farré, E. Teniente, and T. Urpí. Checking query containment with the CQC method. Data Knowl. Eng. 53(2) (2005), pp. 163--223.

Digital Library

Google Scholar

[9]

M. Meier, M. Schmidt, F. Wei, G. Lausen. Semantic query optimization in the presence of types. PODS 2010: 111--122.

Digital Library

Google Scholar

[10]

S. Melnik, A. Adya, and P. A. Bernstein. Compiling mappings to bridge applications and databases. ACM Trans. Database Syst. 33(4) (2008).

Digital Library

Google Scholar

[11]

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

Digital Library

Google Scholar

[12]

F. Wei, and G. Lausen. Containment of Conjunctive Queries with Safe Negation. ICDT 2003, pp. 343--357.

Digital Library

Google Scholar

[13]

X. Zhang, and Z. M. Özsoyoglu. Implication and Referential Constraints: A New Formal Reasoning. IEEE Trans. Knowl. Data Eng. 9(6) (1997), pp. 894--910.

Digital Library

Google Scholar

Cited By

View all

Spasić MVujošević Janičić M(2023)Solving the SPARQL query containment problem with SpeCSWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10077076:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.websem.2022.100770
Zhou QArulraj JNavathe SHarris WXu D(2019)Automated verification of query equivalence using satisfiability modulo theoriesProceedings of the VLDB Endowment10.14778/3342263.334226712:11(1276-1288)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.14778/3342263.3342267
Fan QZeitouni KXiong NWu QCamtepe STian Y(2016)Nash Equilibrium-Based Semantic Cache in Mobile Sensor Grid Database SystemsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2016.2523949(1-12)Online publication date: 2016
https://doi.org/10.1109/TSMC.2016.2523949

Index Terms

Query containment in entity SQL

Recommendations

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 ...
Decidable containment of recursive queries
Database theory

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Conjunctive query containment and answering under description logic constraints

Query containment and query answering are two important computational tasks in databases. While query answering amounts to computing the result of a query over a database, query containment is the problem of checking whether, for every database, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGMOD '13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data

June 2013

1322 pages

ISBN:9781450320375

DOI:10.1145/2463676

General Chairs:
Kenneth Ross
Columbia University
,
Divesh Srivastava
AT&T Research
,
Program Chair:
Dimitris Papadias
HKUST

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: 22 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS'13

Sponsor:

SIGMOD

SIGMOD/PODS'13: International Conference on Management of Data

June 22 - 27, 2013

New York, New York, USA

Acceptance Rates

SIGMOD '13 Paper Acceptance Rate 76 of 372 submissions, 20%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
239
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Spasić MVujošević Janičić M(2023)Solving the SPARQL query containment problem with SpeCSWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2022.10077076:COnline publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1016/j.websem.2022.100770
Zhou QArulraj JNavathe SHarris WXu D(2019)Automated verification of query equivalence using satisfiability modulo theoriesProceedings of the VLDB Endowment10.14778/3342263.334226712:11(1276-1288)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.14778/3342263.3342267
Fan QZeitouni KXiong NWu QCamtepe STian Y(2016)Nash Equilibrium-Based Semantic Cache in Mobile Sensor Grid Database SystemsIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2016.2523949(1-12)Online publication date: 2016
https://doi.org/10.1109/TSMC.2016.2523949

View Options

Login options

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

Cited By

Index Terms

Recommendations

Query containment under bag and bag-set semantics

Decidable containment of recursive queries

Conjunctive query containment and answering under description logic constraints