 |
|
|
Query Containment for Conjunctive Queries with Regular Expressions |
Full Paper (PDF)
Slides (PDF)
|
The management of semistructured data has recently received significant attention because of the need of several applications to model and query large volumes of irregular data. This paper considers the problem of query containment for a query language over semistructured data, StruQL0, that contains the essential feature common to all such languages, namely the ability to specify regular path expressions over the data. We show here that containment of StruQL0 queries is decidable. First, we give a semantic criterion for StruQL0 query containment: we show that it suffices to check containment on only finitely many canonical databases. Second, we give a syntactic criteria for query containment, based on a notion of query mappings , which extends containment mappings for conjunctive queries. Third, we consider a certain fragment of StruQL0, obtained by imposing restrictions on the regular path expressions, and show that query containment for this fragment of StruQL0 is NP complete. |
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]Serge Abiteboul, Dallan Quass, Jason McHugh, Jennifer Widom, Janet L. Wiener:
The Lorel Query Language for Semistructured Data.
Int. J. on Digital Libraries 1(1): 68-88(1997)[4]Alfred V. Aho, Yehoshua Sagiv, Jeffrey D. Ullman:
Equivalences Among Relational Expressions.
SIAM J. Comput. 8(2): 218-246(1979)[5]Peter Buneman:
Semistructured Data.
PODS 1997: 117-121[6]Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu:
A Query Language and Optimization Techniques for Unstructured Data.
SIGMOD Conf. 1996: 505-516[7]Diego Calvanese, Giuseppe de Giacomo, Maurizio Lenzerini:
On the Decidability of Query Containment under Constraints.
PODS 1998: 149-158[8]Ashok K. Chandra, Philip M. Merlin:
Optimal Implementation of Conjunctive Queries in Relational Data Bases.
STOC 1977: 77-90[9]...
[10]Surajit Chaudhuri, Moshe Y. Vardi:
On the Equivalence of Recursive and Nonrecursive Datalog Programs.
PODS 1992: 55-66[11]Surajit Chaudhuri, Moshe Y. Vardi:
On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs.
PODS 1994: 107-116[12]Sudarshan S. Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, Jennifer Widom:
The TSIMMIS Project: Integration of Heterogeneous Information Sources.
IPSJ 1994: 7-18[13]Stavros S. Cosmadakis, Haim Gaifman, Paris C. Kanellakis, Moshe Y. Vardi:
Decidable Optimization Problems for Database Logic Programs (Preliminary Report).
STOC 1988: 477-490[14]Bruno Courcelle:
Recursive Queries and Context-free Graph Grammars.
TCS 78(1): 217-244(1991)[15]Mary F. Fernandez, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu:
Catching the Boat with Strudel: Experiences with a Web-Site Management System.
SIGMOD Conference 1998: 414-425[16]Mary F. Fernandez, Daniela Florescu, Alon Y. Levy, Dan Suciu:
A Query Language for a Web-Site Management System.
SIGMOD Record 26(3): 4-11(1997)[17]Mary F. Fernandez, Daniela Florescu, Alon Y. Levy, Dan Suciu:
A Query Language for a Web-Site Management System.
SIGMOD Record 26(3): 4-11(1997)[18]...
[19]...
[20]Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi:
Undecidable Optimization Problems for Database Logic Programs.
JACM 40(3): 683-713(1993)[21]Ashid Gupta, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom:
Constraint Checking with Partial Information.
PODS 1994: 45-55[22]Anthony C. Klug:
On Conjunctive Queries Containing Inequalities.
JACM 35(1): 146-160(1988)[23]Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava:
Answering Queries Using Views.
PODS 1995: 95-104[24]Alon Y. Levy, Anand Rajaraman, Joann J. Ordille:
Querying Heterogeneous Information Sources Using Source Descriptions.
VLDB 1996: 251-262[25]Alon Y. Levy, Yehoshua Sagiv:
Queries Independent of Updates.
VLDB 1993: 171-181[26]Alon Y. Levy, Dan Suciu:
Deciding Containment for Queries with Complex Objects.
PODS 1997: 20-31[27]...
[28]Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina:
Object Fusion in Mediator Systems.
VLDB 1996: 413-424[29]Yehoshua Sagiv, Mihalis Yannakakis:
Equivalences Among Relational Expressions with the Union and Difference Operators.
JACM 27(4): 633-655(1980)[30]...
[31]Oded Shmueli:
Equivalence of DATALOG Queries is Undecidable.
JLP 15(3): 231-241(1993)[32]Larry J. Stockmeyer, Albert R. Meyer:
Word Problems Requiring Exponential Time: Preliminary Report.
STOC 1973: 1-9[33]Jeffrey D. Ullman:
Information Integration Using Logical Views.
ICDT 1997: 19-40[34]Ron van der Meyden:
The Complexity of Querying Indefinite Data about Linearly Ordered Domains.
PODS 1992: 331-345[35]Moshe Y. Vardi:
Decidability and Undecidability Results for Boundedness of Linear Recursive Queries.
PODS 1988: 341-351[36]Ke Wang:
Some Positive Results for Boundedness of Multiple Recursive Rules.
ICDT 1995: 383-396[37]Xubo Zhang, Z. Meral Özsoyoglu:
On Efficient Reasoning with Implication Constraints.
DOOD 1993: 236-252
|
@inproceedings{DBLP:conf/pods/FlorescuLS98,
author = {Daniela Florescu and
Alon Y. Levy and
Dan Suciu},
title = {Query Containment for Conjunctive Queries with Regular Expressions},
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 = {139-148},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
