ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Query Containment for Conjunctive Queries with Regular Expressions.

Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148
@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-996-3},
  pages     = {139-148},
  ee        = {http://doi.acm.org/10.1145/275487.275503, db/conf/pods/FlorescuLS98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

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.

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

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. 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, 1267 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]
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) 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]
Peter Buneman: Semistructured Data. PODS 1997: 117-121 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
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
[9]
...
[10]
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
[11]
Surajit Chaudhuri, Moshe Y. Vardi: On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs. PODS 1994: 107-116 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
Bruno Courcelle: Recursive Queries and Context-free Graph Grammars. Theor. Comput. Sci. 78(1): 217-244(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Mary F. Fernández, 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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[18]
...
[19]
...
[20]
Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. J. ACM 40(3): 683-713(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[21]
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
[22]
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
[23]
Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[24]
Alon Y. Levy, Anand Rajaraman, Joann J. Ordille: Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996: 251-262 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[25]
Alon Y. Levy, Yehoshua Sagiv: Queries Independent of Updates. VLDB 1993: 171-181 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[26]
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
[27]
...
[28]
Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Object Fusion in Mediator Systems. VLDB 1996: 413-424 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[29]
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
[30]
...
[31]
Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 15(3): 231-241(1993) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[32]
Larry J. Stockmeyer, Albert R. Meyer: Word Problems Requiring Exponential Time: Preliminary Report. STOC 1973: 1-9 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]
Ron van der Meyden: The Complexity of Querying Indefinite Data about Linearly Ordered Domains. PODS 1992: 331-345 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[35]
Moshe Y. Vardi: Decidability and Undecidability Results for Boundedness of Linear Recursive Queries. PODS 1988: 341-351 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[36]
Ke Wang: Some Positive Results for Boundedness of Multiple Recursive Rules. ICDT 1995: 383-396 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[37]
Xubo Zhang, Z. Meral Özsoyoglu: On Efficient Reasoning with Implication Constraints. DOOD 1993: 236-252 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:19:59 2010 by Michael Ley (ley@uni-trier.de)