Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Rewriting of Regular Expressions and Regular Path Queries

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, and Moshe Y. Vardi

  View Paper (PDF)  

Return to Semistructured Data

Abstract
Recent work on semi-structured data has revitalized the interest in path queries, i.e., queries that ask for all pairs of objects in the database that are connected by a, path conforming to a certain specification, in particular to a regular expression. Also, in semi-structured data, as well as in data integration, data warehousing, and query optimization, the problem of query rewriting using views is receiving much attention: Given a query and a collection of views, generate a new query which uses the views and provides the answer to the original one. In this paper we address the problem of query rewriting using views in the context of semi-structured data. We present a method for computing the rewriting of a regular expression in in terms of other regular expressions. The method computes the exact rewriting (the one that defines the same regular language as E) if it exists, or the rewriting that defines the maximal language contained in the one defined by E, otherwise. We present a complexity analysis of both the problem and the method, showing that the latter is essentially optimal. Finally, we illustrate how to exploit the method to rewrite regular path queries using views in semistructured data. The complexity results established for the rewriting of regular expressions apply also to the case of regular path queries.


References

Note: References link to DBLP on the Web.

[Abi97]
Serge Abiteboul : Querying Semi-Structured Data. ICDT 1997 : 1-18
[ACPS96]
Sibel Adali , K. Selçuk Candan , Yannis Papakonstantinou , V. S. Subrahmanian : Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conf. 1996 : 137-148
[AD98]
Serge Abiteboul , Oliver M. Duschka : Complexity of Answering Queries Using Materialized Views. PODS 1998 : 254-263
[AQM+97]
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)
[AV97]
Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133
[BDFS97]
Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350
[BDHS96]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[BFW98]
Peter Buneman , Wenfei Fan , Scott Weinstein : Path Constraints in Semistructured and Structured Databases. PODS 1998 : 129-138
[BLR97]
Catriel Beeri , Alon Y. Levy , Marie-Christine Rousset : Rewriting Queries Using Views in Description Logics. PODS 1997 : 99-108
[Bun97]
Peter Buneman : Semistructured Data. PODS 1997 : 117-121
[CACS94]
Vassilis Christophides , Serge Abiteboul , Sophie Cluet , Michel Scholl : From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994 : 313-324
[CDGL98]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : On the Decidability of Query Containment under Constraints. PODS 1998 : 149-158
[CDGLV99]
...
[CKPS95]
Surajit Chaudhuri , Ravi Krishnamurthy , Spyros Potamianos , Kyuseok Shim : Optimizing Queries with Materialized Views. ICDE 1995 : 190-200
[CM90]
Mariano P. Consens , Alberto O. Mendelzon : GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990 : 404-416
[CMW87]
Isabel F. Cruz , Alberto O. Mendelzon , Peter T. Wood : A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987 : 323-330
[CNS99]
Sara Cohen , Werner Nutt , A. Serebrenik : Rewriting Aggregate Queries Using Views. PODS 1999 : 155-166
[DG97]
Oliver M. Duschka , Michael R. Genesereth : Answering Recursive Queries Using Views. PODS 1997 : 109-116
[FFK+98]
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
[FFLS97]
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)
[FLS98]
Daniela Florescu , Alon Y. Levy , Dan Suciu : Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998 : 139-148
[FS98]
Mary F. Fernandez , Dan Suciu : Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998 : 14-23
[Jon75]
Neil D. Jones : Space-Bounded Reducibility among Combinatorial Problems. JCSS 11(1) : 68-85(1975)
[LMSS95]
Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv , Divesh Srivastava : Answering Queries Using Views. PODS 1995 : 95-104
[MMM97]
Alberto O. Mendelzon , George A. Mihaila , Tova Milo : Querying the World Wide Web. Int. J. on Digital Libraries 1(1) : 54-67(1997)
[MS99]
Tova Milo , Dan Suciu : Index Structures for Path Expressions. ICDT 1999 : 277-295
[QRS+95]
Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom : Querying Semistructured Heterogeneous Information. DOOD 1995 : 319-344
[RS59]
...
[RSU95]
Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman : Answering Queries Using Templates with Binding Patterns. PODS 1995 : 105-112
[Sav70]
Walter J. Savitch : Relationships Between Nondeterministic and Deterministic Tape Complexities. JCSS 4(2) : 177-192(1970)
[SDJL96]
Divesh Srivastava , Shaul Dar , H. V. Jagadish , Alon Y. Levy : Answering Queries with Aggregation Using Views. VLDB 1996 : 318-329
[TSI96]
Odysseas G. Tsatalos , Marvin H. Solomon , Yannis E. Ioannidis : The GMAP: A Versatile Tool for Physical Data Independence. VLDB Journal 5(2) : 101-118(1996)
[Ull97]
Jeffrey D. Ullman : Information Integration Using Logical Views. ICDT 1997 : 19-40

Referenced by

  1. Alberto O. Mendelzon : Review - Rewriting of Regular Expressions and Regular Path Queries. ACM SIGMOD Digital Review 1 : (1999)
  2. Yannis Papakonstantinou , Vasilis Vassalos : Query Rewriting for Semistructured Data. SIGMOD Conference 1999 : 455-466

BIBTEX

@inproceedings{DBLP:conf/pods/CalvaneseGLV99,
  author    = {Diego Calvanese and
                Giuseppe De Giacomo and
                Maurizio Lenzerini and
                Moshe Y. Vardi},
   title     = {Rewriting of Regular Expressions and Regular Path Queries},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {194-204},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM