On the Decidability of Query Containment under Constraints.

@inproceedings{DBLP:conf/pods/CalvaneseGL98,
  author    = {Diego Calvanese and
               Giuseppe De Giacomo and
               Maurizio Lenzerini},
  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},
  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.

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 BibTeX

[2]

Serge Abiteboul, Richard Hull, Victor Vianu: Foundations of Databases. Addison-Wesley 1995, ISBN 0-201-53771-0
Contents BibTeX

[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) BibTeX

[4]

Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman: Equivalences Among Relational Expressions. SIAM J. Comput. 8(2): 218-246(1979) BibTeX

[5]

...

[6]

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: Structured Objects: Modeling and Reasoning. DOOD 1995: 229-246 BibTeX

[7]

...

[8]

...

[9]

Edward P. F. Chan: Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992: 202-211 BibTeX

[10]

Ashok K. Chandra, Philip M. Merlin: Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977: 77-90 BibTeX

[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) BibTeX

[12]

Surajit Chaudhuri, Moshe Y. Vardi: On the Equivalence of Recursive and Nonrecursive Datalog Programs. PODS 1992: 55-66 BibTeX

[13]

Chandra Chekuri, Anand Rajaraman: Conjunctive Query Containment Revisited. ICDT 1997: 56-70 BibTeX

[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) BibTeX

[15]

...

[16]

Giuseppe De Giacomo, Maurizio Lenzerini: TBox and ABox Reasoning in Expressive Description Logics. KR 1996: 316-327 BibTeX

[17]

Guozhu Dong, Jianwen Su: Conjunctive Query Containment with Respect to Views and Constraints. Inf. Process. Lett. 57(2): 95-102(1996) BibTeX

[18]

...

[19]

...

[20]

Michael J. Fischer, Richard E. Ladner: Propositional Dynamic Logic of Regular Programs. J. Comput. Syst. Sci. 18(2): 194-211(1979) BibTeX

[21]

Ashish Gupta, Inderpal Singh Mumick: Maintenance of Materialized Views: Problems, Techniques, and Applications. IEEE Data Eng. Bull. 18(2): 3-18(1995) BibTeX

[22]

Ashish Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Constraint Checking with Partial Information. PODS 1994: 45-55 BibTeX

[23]

...

[24]

Richard Hull: Managing Semantic Heterogeneity in Databases: A Theoretical Perspective. PODS 1997: 51-61 BibTeX

[25]

Yannis E. Ioannidis, Raghu Ramakrishnan: Containment of Conjunctive Queries: Beyond Relations as Sets. ACM Trans. Database Syst. 20(3): 288-324(1995) BibTeX

[26]

Anthony C. Klug: On conjunctive queries containing inequalities. J. ACM 35(1): 146-160(1988) BibTeX

[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) BibTeX

[30]

Alon Y. Levy, Dan Suciu: Deciding Containment for Queries with Complex Objects. PODS 1997: 20-31 BibTeX

[31]

John C. Mitchell: The Implication Problem for Functional and Inclusion Dependencies. Information and Control 56(3): 154-173(1983) BibTeX

[32]

Yehoshua Sagiv, Mihalis Yannakakis: Equivalences Among Relational Expressions with the Union and Difference Operators. J. ACM 27(4): 633-655(1980) BibTeX

[33]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX

[34]

...

[35]

Moshe Y. Vardi, Pierre Wolper: Automata-Theoretic Techniques for Modal Logics of Programs. J. Comput. Syst. Sci. 32(2): 183-221(1986) BibTeX

[36]

...

Referenced by

1. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
2. Lucian Popa, Val Tannen: An Equational Chase for Path-Conjunctive Queries, Constraints, and Views. ICDT 1999: 39-57
3. Maurizio Lenzerini: Description Logics and Their Relationships with Databases. ICDT 1999: 32-38
4. James Bailey, Guozhu Dong: Decidability of First-Order Logic Queries over Views. ICDT 1999: 83-99
5. Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148