Optimizing Regular Path Expressions Using Graph Schemas.

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

@inproceedings{DBLP:conf/icde/FernandezS98,
  author    = {Mary F. Fernandez and
               Dan Suciu},
  title     = {Optimizing Regular Path Expressions Using Graph Schemas},
  booktitle = {Proceedings of the Fourteenth International Conference on Data
               Engineering, February 23-27, 1998, Orlando, Florida, USA},
  publisher = {IEEE Computer Society},
  year      = {1998},
  isbn      = {0-8186-8289-2},
  pages     = {14-23},
  ee        = {db/conf/icde/FernandezS98.html},
  crossref  = {DBLP:conf/icde/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Query languages for data with irregular structure use regular path expressions for navigation. This feature is useful for querying data where parts of the structure is either unknown, unavailable to the user, or changes frequently. Naive execution of regular path expressions is ineffcient, however, because it ignores any structure in the data. We describe two optimization techniques for queries with regular path expressions. Both rely on graph schemas for specifying partial knowledge about the data's structure. Query pruning uses this structure to restrict navigation to only a fragment of the data; we give an effcient algorithm for rewriting any regular path expression query into a pruned one. Query rewriting using state extents can eliminate or reduce navigation altogether; it is reminiscent of optimizing relational queries using indices. There may be several ways to optimize a query using state extents; we give a polynomial-space algorithm that finds all such optimizations. For restricted forms of regular path expressions, the algorithm is provably effcient. We also give an effcient approximation algorithm that works on all regular path expressions.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 7, ICDE 1996-1998, PDIS, Hypertext, ACL DL" 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/An2-7 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" 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 DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

Proceedings of the Fourteenth International Conference on Data Engineering, February 23-27, 1998, Orlando, Florida, USA. IEEE Computer Society 1998, ISBN 0-8186-8289-2
Contents

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, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275
[4]: Serge Abiteboul, Victor Vianu: Regular Path Queries with Constraints. PODS 1997: 122-133
[5]: François Bancilhon, Raghu Ramakrishnan: An Amateur's Introduction to Recursive Query Processing Strategies. SIGMOD Conference 1986: 16-52
[6]: Catriel Beeri, Raghu Ramakrishnan: On the Power of Magic. PODS 1987: 269-284
[7]: Peter Buneman, Susan B. Davidson, Mary F. Fernandez, Dan Suciu: Adding Structure to Unstructured Data. ICDT 1997: 336-350
[8]: Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516
[9]: Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl: From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994: 313-324
[10]: Vassilis Christophides, Sophie Cluet, Guido Moerkotte: Evaluating Queries with Generalized Path Expressions. SIGMOD Conference 1996: 413-422
[11]: Mary F. Fernández, Daniela Florescu, Jaewoo Kang, Alon Y. Levy, Dan Suciu: STRUDEL: A Web-site Management System. SIGMOD Conference 1997: 549-552
[12]: 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)
[13]: ...
[14]: Harold N. Gabow, Robert Endre Tarjan: Faster Scaling Algorithms for Network Problems. SIAM J. Comput. 18(5): 1013-1036(1989)
[15]: ...
[16]: Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987)
[17]: David Konopnicki, Oded Shmueli: W3QS: A Query System for the World-Wide Web. VLDB 1995: 54-65
[18]: ...
[19]: Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: A Declarative Language for Querying and Restructuring the WEB. RIDE-NDS 1996: 12-21
[20]: Alon Y. Levy, Alberto O. Mendelzon, Yehoshua Sagiv, Divesh Srivastava: Answering Queries Using Views. PODS 1995: 95-104
[21]: Alberto O. Mendelzon, George A. Mihaila, Tova Milo: Querying the World Wide Web. PDIS 1996: 80-91
[22]: Alberto O. Mendelzon, Peter T. Wood: Finding Regular Simple Paths in Graph Databases. SIAM J. Comput. 24(6): 1235-1258(1995)
[23]: Yannis Papakonstantinou, Serge Abiteboul, Hector Garcia-Molina: Object Fusion in Mediator Systems. VLDB 1996: 413-424
[24]: Yannis Papakonstantinou, Hector Garcia-Molina, Jeffrey D. Ullman: MedMaker: A Mediation System Based on Declarative Specifications. ICDE 1996: 132-141
[25]: Yannis Papakonstantinou, Hector Garcia-Molina, Jennifer Widom: Object Exchange Across Heterogeneous Information Sources. ICDE 1995: 251-260
[26]: Dominique Perrin: Finite Automata. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 1-57
[27]: Dallan Quass, Anand Rajaraman, Yehoshua Sagiv, Jeffrey D. Ullman, Jennifer Widom: Querying Semistructured Heterogeneous Information. DOOD 1995: 319-344
[28]: Larry J. Stockmeyer, Albert R. Meyer: Word Problems Requiring Exponential Time: Preliminary Report. STOC 1973: 1-9
[29]: ...