Rewriting of Regular Expressions and Regular Path Queries.

@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},
  ee        = {http://doi.acm.org/10.1145/303976.303996, db/conf/pods/CalvaneseGLV99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 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.

ACM SIGMOD DiSC

• 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• 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
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[Abi97]

Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 BibTeX

[ACPS96]

Sibel Adali, K. Selçuk Candan, Yannis Papakonstantinou, V. S. Subrahmanian: Query Caching and Optimization in Distributed Mediator Systems. SIGMOD Conference 1996: 137-148 BibTeX

[AD98]

Serge Abiteboul, Oliver M. Duschka: Complexity of Answering Queries Using Materialized Views. PODS 1998: 254-263 BibTeX

[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) BibTeX

[AV97]

Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133 BibTeX

[BDFS97]

Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350 BibTeX

[BDHS96]

Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516 BibTeX

[BFW98]

Peter Buneman, Wenfei Fan, Scott Weinstein: Path Constraints in Semistructured and Structured Databases. PODS 1998: 129-138 BibTeX

[BLR97]

Catriel Beeri, Alon Y. Levy, Marie-Christine Rousset: Rewriting Queries Using Views in Description Logics. PODS 1997: 99-108 BibTeX

[Bun97]

Peter Buneman: Semistructured Data. PODS 1997: 117-121 BibTeX

[CACS94]

Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl: From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994: 313-324 BibTeX

[CDGL98]

Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini: On the Decidability of Query Containment under Constraints. PODS 1998: 149-158 BibTeX

[CDGLV99]

...

[CKPS95]

Surajit Chaudhuri, Ravi Krishnamurthy, Spyros Potamianos, Kyuseok Shim: Optimizing Queries with Materialized Views. ICDE 1995: 190-200 BibTeX

[CM90]

Mariano P. Consens, Alberto O. Mendelzon: GraphLog: a Visual Formalism for Real Life Recursion. PODS 1990: 404-416 BibTeX

[CMW87]

Isabel F. Cruz, Alberto O. Mendelzon, Peter T. Wood: A Graphical Query Language Supporting Recursion. SIGMOD Conference 1987: 323-330 BibTeX

[CNS99]

Sara Cohen, Werner Nutt, Alexander Serebrenik: Rewriting Aggregate Queries Using Views. PODS 1999: 155-166 BibTeX

[DG97]

Oliver M. Duschka, Michael R. Genesereth: Answering Recursive Queries Using Views. PODS 1997: 109-116 BibTeX

[FFK+98]

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 BibTeX

[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) BibTeX

[FLS98]

Daniela Florescu, Alon Y. Levy, Dan Suciu: Query Containment for Conjunctive Queries with Regular Expressions. PODS 1998: 139-148 BibTeX

[FS98]

Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23 BibTeX

[Jon75]

Neil D. Jones: Space-Bounded Reducibility among Combinatorial Problems. J. Comput. Syst. Sci. 11(1): 68-85(1975) BibTeX

[LMSS95]

Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104 BibTeX

[MMM97]

Alberto O. Mendelzon, George A. Mihaila, Tova Milo: Querying the World Wide Web. Int. J. on Digital Libraries 1(1): 54-67(1997) BibTeX

[MS99]

Tova Milo, Dan Suciu: Index Structures for Path Expressions. ICDT 1999: 277-295 BibTeX

[QRS+95]

Dallan Quass, Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Querying Semistructured Heterogeneous Information. DOOD 1995: 319-344 BibTeX

[RS59]

...

[RSU95]

Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman: Answering Queries Using Templates with Binding Patterns. PODS 1995: 105-112 BibTeX

[Sav70]

Walter J. Savitch: Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. 4(2): 177-192(1970) BibTeX

[SDJL96]

Divesh Srivastava, Shaul Dar, H. V. Jagadish, Alon Y. Levy: Answering Queries with Aggregation Using Views. VLDB 1996: 318-329 BibTeX

[TSI96]

Odysseas G. Tsatalos, Marvin H. Solomon, Yannis E. Ioannidis: The GMAP: A Versatile Tool for Physical Data Independence. VLDB J. 5(2): 101-118(1996) BibTeX

[Ull97]

Jeffrey D. Ullman: Information Integration Using Logical Views. ICDT 1997: 19-40 BibTeX

Referenced by

1. Gösta Grahne, Alex Thomo: Algebraic Rewritings for Optimizing Regular Path Queries. ICDT 2001: 301-315
2. Moshe Y. Vardi: Constraint Satisfaction and Database Theory: a Tutorial. PODS 2000: 76-85
3. Frank Neven, Thomas Schwentick: Expressive and Efficient Pattern Languages for Tree-Structured Data. PODS 2000: 145-156
4. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
5. Alberto O. Mendelzon: Review - Rewriting of Regular Expressions and Regular Path Queries. ACM SIGMOD Digital Review 1: (1999)
6. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466