More Web Proxy on the site http://driver.im/

Article

Benefits of path summaries in an XML query optimizer supporting multiple access methods

Authors:

Mariano P. Consens,

Alberto O. MendelzonAuthors Info & Claims

VLDB '05: Proceedings of the 31st international conference on Very large data bases

Pages 133 - 144

Published: 30 August 2005 Publication History

Abstract

We compare several optimization strategies implemented in an XML query evaluation system. The strategies incorporate the use of path summaries into the query optimizer, and rely on heuristics that exploit data statistics.We present experimental results that demonstrate a wide range of performance improvements for the different strategies supported. In addition, we compare the speedups obtained using path summaries with those reported for index-based methods. The comparison shows that low-cost path summaries combined with optimization strategies achieve essentially the same benefits as more expensive index structures.

References

[1]

A. Aboulnaga, A. Alameldeen, J. F. Naughton, "Estimating the Selectivity of XML Path Expressions for Internet Scale Applications", Proc. VLDB, 2001.]]

Digital Library

[2]

S. Al-Khalifa, H. V. Jagadish, "Combining Operators in XML Query Processing", Proc. VLDB, 2002.]]

[3]

S. Al-Khalifa, H. V. Jagadish, N. Koudas, J. M. Patel, Divesh Srivastava, Y. Wu, "Structural Joins: A Primitive for Efficient XML Query Pattern Matching", Proc. ICDE, 2002.]]

Digital Library

[4]

D. Barbosa, A. Barta, A. O. Mendelzon, G. A. Mihaila, F. Rizzolo, P. Rodriguez-Gianolli, "ToX - The Toronto XML Engine", Proc. Int. Workshop on Inf. Integration on the Web, 2001.]]

[5]

A. Barta, "Access Methods for XML Query Optimization", Ph.D. Thesis, U. of Toronto, 2005.]]

Digital Library

[6]

A. Barta, M. P. Consens, A. O. Mendelzon, "XML Query Optimization Using Path Indexes", Proc. XIME-P 2004.]]

[7]

N. Bruno, D. Srivastava, N. Koudas, "Holistic Twig Joins: Optimal XML Pattern Matching", Proc. SIGMOD, 2002.]]

Digital Library

[8]

V. Christophides, S. Cluet, G. Moerkotte, "Evaluating Queries with Generalized Path Expressions", Proc. SIGMOD, 1996.]]

Digital Library

[9]

M. P. Consens, T. Milo, "Algebras for Querying Text Regions", Proc. PODS, 1995.]]

Digital Library

[10]

A. Deutsch, L. Popa, V. Tannen, "Physical Data Independence, Constraints, and Optimization with Universal Plans", Proc. VLDB, 1999.]]

Digital Library

[11]

M. F. Fernandez, D. Suciu, "Optimizing Regular Path Expressions Using Graph Schemas", Proc. ICDE, 1998.]]

Digital Library

[12]

T. Fiebig, S. Helmer, C. Kanne, G. Moerkotte, J. Neumann, R. Schiele, T. Westmann, "Natix: A Technology Overview", Proc. Web, Web-Services, and Database Systems, 2002.]]

Digital Library

[13]

D. Florescu, C. Hillery, D. Kossmann, P. Lucas, F. Riccardi, T. Westmann, M. J. Carey, A. Sundararajan, G. Agrawal, "The BEA/XQRL Streaming XQuery Processor", Proc. VLDB, 2003.]]

[14]

R. Goldman, J. Widom, "DataGuides, "Enabling Query Formulation and Optimization in Semistructured Databases", Proc. VLDB, 1997.]]

Digital Library

[15]

A. Halverson, J. Burger, L. Galanis, A. Kini, R. Krishnamurthy, A. N. Rao, F. Tian, S. Viglas, Y. Wang, J. F. Naughton, D. J. DeWitt, "Mixed Mode XML Query Processing", Proc. VLDB, 2003.]]

[16]

H. V. Jagadish, S. Al-Khalifa, A. Chapman, L. V. S. Lakshmanan, A. Nierman, S. Paparizos, J. Patel, D. Srivastava, N. Wiwatwattana, Y. Wu, C. Yu, "TIMBER: A Native XML Database", VLDBJ, 2003.]]

Digital Library

[17]

H. V. Jagadish, Laks V. S. Lakshmanan, Divesh Srivastava, K. Thompson, "TAX: A Tree Algebra for XML", Proc. DBPL, 2001.]]

Digital Library

[18]

H. Jiang, W. Wang, H. Lu, J. X. Yu, "Holistic Twig Joins on Indexed XML Documents", Proc. VLDB, 2003.]]

[19]

R. Kaushik, P. Shenoy, P. Bohannon, E. Gudes, "Exploiting Local Similarity for Indexing Paths in Graph-Structured Data", Proc. ICDE, 2002.]]

Digital Library

[20]

Lucent's Galax, http://db.bell-labs.com/galax/]]

[21]

A. Marian, J. Siméon, "Projecting XML Documents", Proc. VLDB, 2003.]]

[22]

J. McHugh, J. Widom, "Compile-Time Path Expansion in Lore", Proc. Workshop on Q. Proc. for Semistr. Data and Non-Standard Data Formats, 1999.]]

[23]

J. McHugh, J. Widom, "Query Optimization for XML" Proc. VLDB, 1999.]]

Digital Library

[24]

T. Milo, D. Suciu, "Index Structures for Path Expressions", Proc. ICDT, 1999.]]

Digital Library

[25]

G. Miklau, "U. W. XML Repository", http://www.cs.washington.edu/research/xmldatasets.]]

[26]

N. Polyzotis, M. N. Garofalakis, Y. E. Ioannidis, "Selectivity Estimation for XML Twigs", Proc. ICDE, 2004.]]

Digital Library

[27]

C. Qun, A. Lim, K. W. Ong, "D(k)-Index: An Adaptive Structural Summary for Graph-Structured Data", Proc. VLDB, 2003.]]

[28]

P. R. Rao, B. Moon, "PRIX: Indexing and Querying XML Using Prufer Sequences", Proc. ICDE, 2004.]]

Digital Library

[29]

P. R. Rao, B. Moon, "PRIX: Indexing and Querying XML Using Prufer Sequences", Technical Report TR-03-06, U. of Arizona, Tucson, 2003.]]

[30]

F. Rizzolo, A. O. Mendelzon, "Indexing XML Data with ToXin", Proc. WebDB, 2001.]]

[31]

H. Wang, S. Park, W. Fan, P. S. Yu, "VIST: A Dynamic Index Method for Querying XML Data by Tree Structures", Proc. SIGMOD, 2003.]]

Digital Library

[32]

Y. Wu, J. Patel, H. V. Jagadish, "Using Histograms to Estimate Answer Size for XML Queries", Journal of Information Science 2002.]]

Digital Library

[33]

C. Zhang, J. F. Naughton, D. J. DeWitt, Q. Luo, G. M. Lohman, "On Supporting Containment Queries in Relational Database Management Systems", Proc. VLDB, 2001.]]

[34]

A. Arion, A. Bonifati, G. Costa, S. D'Aguanno, I. Manolescu, A. Pugliese, "Efficient Query Evaluation over Compressed XML Data", Proc. EDBT 2004.]]

[35]

P. Buneman, B. Choi, W. Fan, R. Hutchison, R. Mann, S. Viglas, "Vectorizing and Querying Large XML Repositories", Proc. ICDE 2005.]]

Digital Library

Cited By

Pettovello PFotouhi FNg JCouturier CMüller HRyman A(2010)XPath query processing improvementsProceedings of the 2010 Conference of the Center for Advanced Studies on Collaborative Research10.1145/1923947.1923957(86-99)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1145/1923947.1923957
Consens MMiller RRizzolo FVaisman A(2010)Exploring XML web collections with DescribeXACM Transactions on the Web10.1145/1806916.18069204:3(1-46)Online publication date: 20-Jul-2010
https://dl.acm.org/doi/10.1145/1806916.1806920
Choi RWong R(2009)Efficient XQuery join processing in publish/subscribe systemsProceedings of the Twentieth Australasian Conference on Australasian Database - Volume 9210.5555/1862681.1862695(95-104)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1862681.1862695
Show More Cited By

Index Terms

Benefits of path summaries in an XML query optimizer supporting multiple access methods

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

VLDB '05: Proceedings of the 31st international conference on Very large data bases

August 2005

1392 pages

ISBN:1595931546

General Chair:
Kjell Bratbergsengen
Norwegian University of Science & Technology, Trondheim, Norway

Publisher

VLDB Endowment

Publication History

Published: 30 August 2005

Qualifiers

Article

Conference

ICMI05

ICMI05: Seventh International Conference on Multimodal Interfaces 2005

August 30 - September 2, 2005

Trondheim, Norway

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
518
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Pettovello PFotouhi FNg JCouturier CMüller HRyman A(2010)XPath query processing improvementsProceedings of the 2010 Conference of the Center for Advanced Studies on Collaborative Research10.1145/1923947.1923957(86-99)Online publication date: 1-Nov-2010
https://dl.acm.org/doi/10.1145/1923947.1923957
Consens MMiller RRizzolo FVaisman A(2010)Exploring XML web collections with DescribeXACM Transactions on the Web10.1145/1806916.18069204:3(1-46)Online publication date: 20-Jul-2010
https://dl.acm.org/doi/10.1145/1806916.1806920
Choi RWong R(2009)Efficient XQuery join processing in publish/subscribe systemsProceedings of the Twentieth Australasian Conference on Australasian Database - Volume 9210.5555/1862681.1862695(95-104)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.5555/1862681.1862695
Theodoratos DPlacek PDalamagas TSouldatos SSellis T(2009)Containment of partially specified tree-pattern queries in the presence of dimension graphsThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-008-0097-y18:1(233-254)Online publication date: 1-Jan-2009
https://dl.acm.org/doi/10.1007/s00778-008-0097-y
Grimsmo NFekete ALin X(2008)Faster path indexes for search in XML dataProceedings of the nineteenth conference on Australasian database - Volume 7510.5555/1378307.1378330(127-135)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.5555/1378307.1378330
Moro MVagena ZTsotras V(2008)XML Structural SummariesProceedings of the VLDB Endowment10.14778/1454159.14542211:2(1524-1525)Online publication date: 1-Aug-2008
https://dl.acm.org/doi/10.14778/1454159.1454221
Xie GCheng QGryz JZuzarte CShanahan JAmer-Yahia SManolescu IZhang YEvans DKolcz AChoi KChowdury A(2008)Some rewrite optimizations of DB2 XQuery navigationProceedings of the 17th ACM conference on Information and knowledge management10.1145/1458082.1458153(531-540)Online publication date: 26-Oct-2008
https://dl.acm.org/doi/10.1145/1458082.1458153
Marks GRoantree MDesai B(2008)Pattern based processing of XPath queriesProceedings of the 2008 international symposium on Database engineering & applications10.1145/1451940.1451965(179-188)Online publication date: 10-Sep-2008
https://dl.acm.org/doi/10.1145/1451940.1451965
Theodoratos DWu X(2008)Assigning semantics to partial tree-pattern queriesData & Knowledge Engineering10.1016/j.datak.2007.07.00264:1(242-265)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1016/j.datak.2007.07.002
Theodoratos DWu X(2007)An original semantics to keyword queries for XML using structural patternsProceedings of the 12th international conference on Database systems for advanced applications10.5555/1783823.1783903(727-739)Online publication date: 9-Apr-2007
https://dl.acm.org/doi/10.5555/1783823.1783903
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents