Digital Symposium Collection 2000  

 
 
 
 
 
 

 





















Query Rewriting for Semistructured Data

Yannis Papakonstantinou and Vasilis Vassalos

  View Paper (PDF)  

Return to Semistructured Data and Mediators

Abstract
We address the problem of query rewriting for TSL, a language for querying semistructured data. We develop and present an algorithm that, given a semistructured query q and a set of semistructured views V, finds rewriting queries, i.e., queries that access the views and produce the same result as q. Our algorithm is based on appropriately generalizing containment mappings, the chase, and query composition - techniques that were developed for structured, relational data. We also develop an algorithm for equivalence checking of TSL queries. We show that the algorithm is sound and complete for TLS. i.e., it always finds every non-trivial TLS rewriting query of q, and we discuss its complexity. We extend the rewriting algorithm to use some forms of structural constraints (such as DTDs) and find more opportunities for query rewriting.


References

Note: References link to DBLP on the Web.

[1]
Serge Abiteboul , Victor Vianu : Queries and Computation on the Web. ICDT 1997 : 262-275
[2]
...
[3]
Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350
[4]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[5]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi : Rewriting of Regular Expressions and Regular Path Queries. PODS 1999 : 194-204
[6]
Edward P. F. Chan : Containment and Minimization of Positive Conjunctive Queries in OODB's. PODS 1992 : 202-211
[7]
Ashok K. Chandra , Philip M. Merlin : Optimal Implementation of Conjunctive Queries in Relational Data Bases. STOC 1977 : 77-90
[8]
...
[9]
Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116
[10]
Olivier M. Duschka , Alon Y. Levy : Recursive Plans for Information Gathering. IJCAI (1) 1997 : 778-784
[11]
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)
[12]
Mary F. Fernandez , Dan Suciu : Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998 : 14-23
[13]
Daniela Florescu , Alon Y. Levy , Alberto O. Mendelzon : Database Techniques for the World-Wide Web: A Survey. SIGMOD Record 27(3) : 59-74(1998)
[14]
Daniela Florescu , Alon Y. Levy , Dan Suciu : Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998 : 139-148
[15]
Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Vasilis Vassalos , Jennifer Widom : The TSIMMIS Approach to Mediation: Data Models and Languages. JIIS 8(2) : 117-132(1997)
[16]
Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445
[17]
Laura M. Haas , Donald Kossmann , Edward L. Wimmers , Jun Yang : Optimizing Queries Across Diverse Data Sources. VLDB 1997 : 276-285
[18]
Richard Hull , Masatoshi Yoshikawa : On the Equivalence of Database Restructurings Involving Object Identifiers. PODS 1991 : 328-340
[19]
Arthur M. Keller , Julie Basu : A Predicate-based Caching Scheme for Client-Server Database Architectures. VLDB Journal 5(1) : 35-47(1996)
[20]
Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104
[21]
Alon Y. Levy , Anand Rajaraman , Joann J. Ordille : Querying Heterogeneous Information Sources Using Source Descriptions. VLDB 1996 : 251-262
[22]
Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman : Answering Queries Using Limited External Processors. PODS 1996 : 227-237
[23]
...
[24]
Alon Y. Levy , Dan Suciu : Deciding Containment for Queries with Complex Objects. PODS 1997 : 20-31
[25]
Chen Li , Ramana Yerneni , Vasilis Vassalos , Hector Garcia-Molina , Yannis Papakonstantinou , Jeffrey D. Ullman , Murty Valiveti : Capability Based Mediation in TSIMMIS. SIGMOD Conference 1998 : 564-566
[26]
Jason McHugh , Serge Abiteboul , Roy Goldman , Dallan Quass , Jennifer Widom : Lore: A Database Management System for Semistructured Data. SIGMOD Record 26(3) : 54-66(1997)
[27]
Alberto O. Mendelzon , Tova Milo : Formal Models of Web Queries. PODS 1997 : 134-143
[28]
...
[29]
Yannis Papakonstantinou , Hector Garcia-Molina , Jeffrey D. Ullman : MedMaker: A Mediation System Based on Declarative Specifications. ICDE 1996 : 132-141
[30]
Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom : Object Exchange Across Heterogeneous Information Sources. ICDE 1995 : 251-260
[31]
...
[32]
Yannis Papakonstantinou , Pavel Velikhov : Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999 : 136-145
[33]
Yehoshua Sagiv , Mihalis Yannakakis : Equivalences Among Relational Expressions with the Union and Difference Operators. JACM 27(4) : 633-655(1980)
[34]
...
[35]
...
[36-1]
Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
[36-2]
Jeffrey D. Ullman : Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
[37]
...
[38]
H. Z. Yang , Per-Åke Larson : Query Transformation for PSJ-Queries. VLDB 1987 : 245-254
[39]
Yue Zhuge , Hector Garcia-Molina , Joachim Hammer , Jennifer Widom : View Maintenance in a Warehousing Environment. SIGMOD Conference 1995 : 316-327

Referenced by

  1. Serge Abiteboul : On Views and XML. PODS 1999 : 1-9

BIBTEX

@inproceedings{DBLP:conf/sigmod/PapakonstantinouV99,
  author    = {Yannis Papakonstantinou and
                Vasilis Vassalos},
   editor    = {Alex Delis and
                Christos Faloutsos and
                Shahram Ghandeharizadeh},
   title     = {Query Rewriting for Semistructured Data},
   booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference
                on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,
                USA},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-084-8},
   pages     = {455-466},
   crossref  = {DBLP:conf/sigmod/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM