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 ...

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/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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

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

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
[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 Conference 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. Theor. Comput. Sci. 78(1): 217-244(1991)
[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
[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. J. ACM 40(3): 683-713(1993)
[21]: Ashish 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. J. ACM 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. J. ACM 27(4): 633-655(1980)
[30]: ...
[31]: Oded Shmueli: Equivalence of DATALOG Queries is Undecidable. J. Log. Program. 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