dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

On the Decidability of Query Containment under Constraints.

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158
@inproceedings{DBLP:conf/pods/CalvaneseGL98,
  author    = {Diego Calvanese and
               Giuseppe De Giacomo and
               Maurizio Lenzerini},
  editor    = {Alberto O. Mendelzon and
               Jan Paredaens},
  title     = {On the Decidability of Query Containment under Constraints},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington,
               USA},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {149-158},
  ee        = {http://doi.acm.org/10.1145/275487.275504, db/conf/pods/CalvaneseGL98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Query containment under constraints is the problem of checking whether for every database satisfying a given set of constraints, the result of one query is a subset of the result of another query. Recent research points out that this is a central problem in several database applications, and we address it within a setting where constraints are specified in the form of special inclusion dependencies over complex expressions, built by using intersection and difference of relations, special forms of quantification, regular expressions over binary relations, and cardinality constraints. These types of constraints capture a great variety of data models, including the relational, the entity-relational, and the object-oriented model.

We study the problem of checking whether q is contained in q' with respect to the constraints specified in a schema S, where q and q' are nonrecursive Datalog programs whose atoms are complex expressions. We present the following results on query containment. For the case where q does not contain regular expressions, we provide a method for deciding query containment, and analyze its computational complexity. We do the same for the case where neither S nor q, q' contain number restrictions. To the best of our knowledge, this yields the first decidability result on containment of conjunctive queries with regular expressions. Finally, we prove that the problem is undecidable for the case where we admit inequalities in q'.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

Printed Edition

Alberto O. Mendelzon, Jan Paredaens (Eds.): Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington, USA. ACM Press 1998, ISBN 0-89791-996-3
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1216 KB]

References

[1]
Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Efficient Optimization of a Class of Relational Expressions. ACM Trans. Database Syst. 4(4): 435-454(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[4]
Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: Structured Objects: Modeling and Reasoning. DOOD 1995: 229-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
...
[8]
...
[9]
Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
Ashok K. Chandra, Moshe Y. Vardi: The Implication Problem for Functional and Inclusion Dependencies is Undecidable. SIAM J. Comput. 14(3): 671-677(1985) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[12]
Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
David S. Johnson, Anthony C. Klug: Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies. J. Comput. Syst. Sci. 28(1): 167-189(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
...
[16]
Giuseppe De Giacomo, Maurizio Lenzerini: TBox and ABox Reasoning in Expressive Description Logics. KR 1996: 316-327 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
Guozhu Dong, Jianwen Su: Conjunctive Query Containment with Respect to Views and Constraints. Inf. Process. Lett. 57(2): 95-102(1996) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
...
[19]
...
[20]
Michael J. Fischer, Richard E. Ladner: Propositional Dynamic Logic of Regular Programs. J. Comput. Syst. Sci. 18(2): 194-211(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[22]
Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[23]
...
[24]
Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[27]
...
[28]
...
[29]
Alon Y. Levy, Divesh Srivastava, Thomas Kirk: Data Model and Query Evaluation in Global Information Systems. J. Intell. Inf. Syst. 5(2): 121-143(1995) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[30]
Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[31]
John C. Mitchell: The Implication Problem for Functional and Inclusion Dependencies. Information and Control 56(3): 154-173(1983) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[33]
Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[34]
...
[35]
Moshe Y. Vardi, Pierre Wolper: Automata-Theoretic Techniques for Modal Logics of Programs. J. Comput. Syst. Sci. 32(2): 183-221(1986) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
...

Last update Fri Sep 14 17:28:36 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page