Evaluating Queries with Generalized Path Expressions.

@inproceedings{DBLP:conf/sigmod/ChristophidesCM96,
  author    = {Vassilis Christophides and
               Sophie Cluet and
               Guido Moerkotte},
  editor    = {H. V. Jagadish and
               Inderpal Singh Mumick},
  title     = {Evaluating Queries with Generalized Path Expressions},
  booktitle = {Proceedings of the 1996 ACM SIGMOD International Conference on
               Management of Data, Montreal, Quebec, Canada, June 4-6, 1996},
  publisher = {ACM Press},
  year      = {1996},
  pages     = {413-422},
  ee        = {http://doi.acm.org/10.1145/233269.233358, db/conf/sigmod/ChristophidesCM96.html},
  crossref  = {DBLP:conf/sigmod/96},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

In the past few years, query languages featuring generalized path expressions have been proposed. These languages allow the interrogation of both data and structure. They are powerful and essential for a number of applicationss. However, until now, their evaluation has relied on a rather naive and inefficient algorithm.

In this paper, we extend an object algebra with two new operators and present some interesting rewriting techniques for queries featuring generalized path expressions. We also show how a query optimizer can integrate the new techniques.

Copyright © 1996 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 Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" 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
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/smod9397 or /cdrom

• 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

[Bat87]

Don S. Batory: Extensible Cost Models and Query Optimization in GENESIS. IEEE Database Eng. Bull. 9(4): 30-36(1986) BibTeX

[Ber89]

...

[BF92]

Elisa Bertino, Paola Foscoli: An Analytical Model of Object-Oriented Query Costs. POS 1992: 241-261 BibTeX

[BMG93]

José A. Blakeley, William J. McKenna, Goetz Graefe: Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993: 287-296 BibTeX

[BRG88]

Elisa Bertino, Fausto Rabitti, Simon J. Gibbs: Query Processing in a Multimedia Document System. ACM Trans. Inf. Syst. 6(1): 1-41(1988) BibTeX

[CACS94]

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

[CM95a]

...

[CM95b]

...

[GD87]

Goetz Graefe, David J. DeWitt: The EXODUS Optimizer Generator. SIGMOD Conference 1987: 160-172 BibTeX

[GM91]

...

[GW89]

Goetz Graefe, Karen Ward: Dynamic Query Evaluation Plans. SIGMOD Conference 1989: 358-366 BibTeX

[HFLP89]

Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388 BibTeX

[JWKL90]

B. Paul Jenq, Darrell Woelk, Won Kim, Wan-Lik Lee: Query Processing in Distributed ORION. EDBT 1990: 169-187 BibTeX

[KKS92]

Michael Kifer, Won Kim, Yehoshua Sagiv: Querying Object-Oriented Databases. SIGMOD Conference 1992: 393-402 BibTeX

[KM90]

Alfons Kemper, Guido Moerkotte: Access Support in Object Bases. SIGMOD Conference 1990: 364-374 BibTeX

[KM93]

...

[KMP93]

Alfons Kemper, Guido Moerkotte, Klaus Peithner: A Blackboard Architecture for Query Optimization in Object Bases. VLDB 1993: 543-554 BibTeX

[Loh88]

Guy M. Lohman: Grammar-like Functional Rules for Representing Query Optimization Alternatives. SIGMOD Conference 1988: 18-27 BibTeX

[MZD92]

...

[QRS+95]

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

[Sim95]

...

Referenced by

1. Vassilis Christophides, Sophie Cluet, Jérôme Siméon: On Wrapping Query Languages and Efficient XML Integration. SIGMOD Conference 2000: 141-152
2. Qiu Yue Wang, Jeffrey Xu Yu, Kam-Fai Wong: Approximate Graph Schema Extraction for Semi-Structured Data. EDBT 2000: 302-316
3. Bertram Ludäscher, Yannis Papakonstantinou, Pavel Velikhov: Navigation-Driven Evaluation of Virtual Mediated Views. EDBT 2000: 150-165
4. Sergio Flesca, Sergio Greco: Querying Graph Databases. EDBT 2000: 510-524
5. Jason McHugh, Jennifer Widom: Query Optimization for XML. VLDB 1999: 315-326
6. Jacek Plodzien, Anna Kraken: Object Query Optimization in the Stack-Based Approach. ADBIS 1999: 303-316
7. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49
8. Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23
9. Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: STRUDEL: A Web-site Management System. SIGMOD Conference 1997: 549-552
10. Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350
11. Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18
12. Talel Abdessalem, Geneviève Jomier: VQL: A Query Language for Multiversion Databases. DBPL 1997: 160-179