 |
|
|
On the Decidability of Query Containment under Constraints |
Full Paper (PDF)
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'. |
References, where available, link to the DBLP on the World Wide Web.
[1]Serge Abiteboul:
Querying Semi-Structured Data.
ICDT 1997: 1-18[2]Serge Abiteboul, Richard Hull, Victor Vianu:
Foundations of Databases.
Addison-Wesley 1995, ISBN 0-201-53771-0
Contents[3]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Efficient Optimization of a Class of Relational Expressions.
TODS 4(4): 435-454(1979)[4]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979)[5]...
[6]Diego Calvanese, Giuseppe de Giacomo, Maurizio Lenzerini:
Structured Objects: Modeling and Reasoning.
DOOD 1995: 229-246[7]...
[8]...
[9]Edward P. F. Chan:
Containment and Minimization of Positive Conjunctive Queries in OODB's.
PODS 1992: 202-211[10]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[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)[12]Surajit Chaudhuri, Moshe Y. Vardi:
On the Equivalence of Recursive and Nonrecursive Datalog Programs.
PODS 1992: 55-66[13]Chandra Chekuri, Anand Rajaraman:
Conjunctive Query Containment Revisited.
ICDT 1997: 56-70[14]David S. Johnson, Anthony C. Klug:
Testing Containment of Conjunctive Queries under Functional and Inclusion Dependencies.
JCSS 28(1): 167-189(1984)[15]...
[16]Giuseppe de Giacomo, Maurizio Lenzerini:
TBox and ABox Reasoning in Expressive Description Logics.
KR 1996: 316-327[17]Guozhu Dong, Jianwen Su:
Conjunctive Query Containment with Respect to Views and Constraints.
IPL 57(2): 95-102(1996)[18]...
[19]...
[20]Michael J. Fischer, Richard E. Ladner:
Propositional Dynamic Logic of Regular Programs.
JCSS 18(2): 194-211(1979)[21]Ashish Gupta, Inderpal Singh Mumick:
Maintenance of Materialized Views: Problems, Techniques, and Applications.
Data Engineering Bulletin 18(2): 3-18(1995)[22]Ashid Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom:
Constraint Checking with Partial Information.
PODS 1994: 45-55[23]...
[24]Richard Hull:
Managing Semantic Heterogeneity in Databases: A Theoretical Perspective.
PODS 1997: 51-61[25]Yannis E. Ioannidis, Raghu Ramakrishnan:
Containment of Conjunctive Queries: Beyond Relations as Sets.
TODS 20(3): 288-324(1995)[26]Anthony C. Klug:
On Conjunctive Queries Containing Inequalities.
JACM 35(1): 146-160(1988)[27]...
[28]...
[29]Alon Y. Levy, Divesh Srivastava, Thomas Kirk:
Data Model and Query Evaluation in Global Information Systems.
JIIS 5(2): 121-143(1995)[30]Alon Y. Levy, Dan Suciu:
Deciding Containment for Queries with Complex Objects.
PODS 1997: 20-31[31]John C. Mitchell:
The Implication Problem for Functional and Inclusion Dependencies.
Information and Control 56(3): 154-173(1983)[32]Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
JACM 27(4): 633-655(1980)[33]Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40[34]...
[35]Moshe Y. Vardi, Pierre Wolper:
Automata-Theoretic Techniques for Modal Logics of Programs.
JCSS 32(2): 183-221(1986)[36]...
Referenced By:
- Daniela Florescu, Alon Y. Levy, Dan Suciu:
Query Containment for Conjunctive Queries with Regular Expressions.
PODS 1998: 139-148
|
@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-966-3},
pages = {149-158},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
