ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

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.

Copyright © 1998 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 2 Issue 7, ICDE 1996-1998, PDIS, Hypertext, ACL DL" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

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

Referenced by

  1. Gabriel M. Kuper, Jérôme Siméon: Subsumption for XML types. ICDT 2001: 331-345
  2. Gösta Grahne, Alex Thomo: Algebraic Rewritings for Optimizing Regular Path Queries. ICDT 2001: 301-315
  3. Vassilis Christophides, Sophie Cluet, Jérôme Siméon: On Wrapping Query Languages and Efficient XML Integration. SIGMOD Conference 2000: 141-152
  4. Yannis Papakonstantinou, Victor Vianu: DTD Inference for Views of XML Data. PODS 2000: 35-46
  5. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: View-Based Query Processing for Regular Path Queries with Inverse. PODS 2000: 58-66
  6. Qiu Yue Wang, Jeffrey Xu Yu, Kam-Fai Wong: Approximate Graph Schema Extraction for Semi-Structured Data. EDBT 2000: 302-316
  7. Peter T. Wood: Optimising Web Queries Using Document Type Definitions. Workshop on Web Information and Data Management 1999: 28-32
  8. Jayavel Shanmugasundaram, Kristin Tufte, Chun Zhang, Gang He, David J. DeWitt, Jeffrey F. Naughton: Relational Databases for Querying XML Documents: Limitations and Opportunities. VLDB 1999: 302-314
  9. Jason McHugh, Jennifer Widom: Query Optimization for XML. VLDB 1999: 315-326
  10. Yannis Papakonstantinou, Vasilis Vassalos: Query Rewriting for Semistructured Data. SIGMOD Conference 1999: 455-466
  11. Tova Milo, Dan Suciu: Type Inference for Queries on Semistructured Data. PODS 1999: 215-226
  12. Diego Calvanese, Giuseppe De Giacomo, Maurizio Lenzerini, Moshe Y. Vardi: Rewriting of Regular Expressions and Regular Path Queries. PODS 1999: 194-204
  13. Yannis Papakonstantinou, Pavel Velikhov: Enhancing Semistructured Data Mediators with Document Type Definitions. ICDE 1999: 136-145
  14. Georges Gardarin, Fei Sha, Tuyet-Tram Dang-Ngoc: XML-based Components for Federating Multiple Heterogeneous Data Sources. ER 1999: 506-519
  15. Jyh-Herng Chow, Josephine M. Cheng, Daniel T. Chang, Jane Xu: Index Design for Structured Documents Based on Abstraction. DASFAA 1999: 89-96
  16. Serge Abiteboul, Jason McHugh, Michael Rys, Vasilis Vassalos, Janet L. Wiener: Incremental Maintenance for Materialized Views over Semistructured Data. VLDB 1998: 38-49

Copyright © Mon Nov 2 20:43:55 2009 by Michael Ley (ley@uni-trier.de)