[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/1083592.1083635dlproceedingsArticle/Chapter ViewAbstractPublication PagesvldbConference Proceedingsconference-collections
Article

Pattern tree algebras: sets or sequences?

Published: 30 August 2005 Publication History

Abstract

XML and XQuery semantics are very sensitive to the order of the produced output. Although pattern-tree based algebraic approaches are becoming more and more popular for evaluating XML, there is no universally accepted technique which can guarantee both a correct output order and a choice of efficient alternative plans.We address the problem using hybrid collections of trees that can be either sets or sequences or something in between. Each such collection is coupled with an Ordering Specification that describes how the trees are sorted (full, partial or no order). This provides us with a formal basis for developing a query plan having parts that maintain no order and parts with partial or full order.It turns out that duplicate elimination introduces some of the same issues as order maintenance: it is expensive and a single collection type does not always provide all the flexibility required to optimize this properly. To solve this problem we associate with each hybrid collection a Duplicate Specification that describes the presence or absence of duplicate elements in it. We show how to extend an existing bulk tree algebra, TLC [12], to use Ordering and Duplicate specifications and produce correctly ordered results. We also suggest some optimizations enabled by the flexibility of our approach, and experimentally demonstrate the performance increase due to them.

References

[1]
N. Bruno, D. Srivastava, and N. Koudas. Holistic twig joins: Optimal XML pattern matching. In Proc. SIGMOD Conf., 2002.]]
[2]
Z. Chen, H. V. Jagadish, F. Korn, N. Koudas, S. Muthukrishnan, R. T. Ng, and D. Srivastava. Counting twig matches in a tree. In Proc. ICDE Conf., Mar. 2001.]]
[3]
Z. Chen, H. V. Jagadish, L. V. S. Lakshmanan, and S. Paparizos. From tree patterns to generalized tree patterns: On efficient evaluation of XQuery. In Proc. VLDB Conf., Sep. 2003.]]
[4]
D. DeHaan, D. Toman, M. P. Consens, and M. T. Ozsu. A comprehensive XQuery to SQL translation using dynamic interval encoding. In Proc. SIGMOD Conf., Jun. 2003.]]
[5]
G. Graefe. Query evaluation techniques for large databases. ACM Comput. Surv., 25(2):73--170, 1993.]]
[6]
J. Hidders and P. Michiels. Avoiding unnecessary ordering operations in XPath. In Proc. DBPL Conf., 2003.]]
[7]
H. V. Jagadish, S. Al-Khalifa, A. Chapman, L. V. S. Lakshmanan, A. Nierman, S. Paparizos, J. M. Patel, D. Srivastava, N. Wiwatwattana, Y. Wu, and C. Yu. TIMBER: A native XML database. VLDB Journal, 11(4), 2002.]]
[8]
H. V. Jagadish, L. V. S. Lakshmanan, D. Srivastava, and K. Thompson. TAX: A tree algebra for XML. In Proc. DBPL Conf., Sep. 2001.]]
[9]
B. Ludascher, Y. Papakonstantinou, and P. Velikhov. Navigation-driven evaluation of virtual mediated views. In Proc. EDBT Conf., Mar. 2000.]]
[10]
U. of Michigan. The TIMBER project. http://www.eecs.umich.edu/db/timber]]
[11]
U. of Wisconsin. The Niagara internet query system. http://www.cs.wisc.edu/niagara/.]]
[12]
S. Paparizos, Y. Wu, L. V. S. Lakshmanan, and H. V. Jagadish. Tree logical classes for efficient evaluation of XQuery. In Proc. SIGMOD Conf., Jun. 2004.]]
[13]
A. R. Schmidt, F. Waas, M. L. Kersten, M. J. Carey, I. Manolescu, and R. Busse. XMark: A benchmark for XML data management. In Proc. VLDB Conf., 2002.]]
[14]
H. Schoning. Tamino - A DBMS designed for XML. In Proc. ICDE Conf., 2001.]]
[15]
P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proc. SIGMOD Conf., 1979.]]
[16]
J. Shanmugasundaram, K. Tufte, C. Zhang, G. He, D. J. DeWitt, and J. F. Naughton. Relational databases for querying XML documents: Limitations and opportunities. In Proc. VLDB Conf., 1999.]]
[17]
J. Simeon and M. F. Fernandez. Galax, an open implementation of XQuery. http://db.bell-labs.com/galax/.]]
[18]
D. Simmen, E. Shekita, and T. Malkemus. Fundamental techniques for order optimization. In Proc. SIGMOD Conf., 1996.]]
[19]
I. Tatarinov, S. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. Storing and querying ordered XML using a relational database system. In Proc. SIGMOD Conf., 2002.]]
[20]
S. D. Viglas, L. Galanis, D. J. DeWitt, D. Maier, and J. F. Naughtonn. Putting XML query algebras into context. http://www.cs.wisc.edu/niagara/]]
[21]
Y. Wu, J. M. Patel, and H. V. Jagadish. Structural join order selection for XML query optimization. In Proc ICDE Conf., Mar. 2003.]]
[22]
C. Zhang, J. Naughton, D. Dewitt, Q. Luo, and G. Lohman. On supporting containment queries in relational database management systems. In Proc. SIGMOD Conf., 2001.]]

Cited By

View all
  • (2010)Let SQL drive the XQuery workhorse (XQuery join graph isolation)Proceedings of the 13th International Conference on Extending Database Technology10.1145/1739041.1739062(147-158)Online publication date: 22-Mar-2010
  • (2008)IFOXProceedings of the 2008 ACM symposium on Applied computing10.1145/1363686.1363974(1252-1257)Online publication date: 16-Mar-2008
  • (2007)Foundations of rule-based query answeringProceedings of the Third international summer school conference on Reasoning Web10.5555/2391482.2391484(1-153)Online publication date: 3-Sep-2007
  • Show More Cited By

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

Publisher

VLDB Endowment

Publication History

Published: 30 August 2005

Qualifiers

  • Article

Conference

ICMI05

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2010)Let SQL drive the XQuery workhorse (XQuery join graph isolation)Proceedings of the 13th International Conference on Extending Database Technology10.1145/1739041.1739062(147-158)Online publication date: 22-Mar-2010
  • (2008)IFOXProceedings of the 2008 ACM symposium on Applied computing10.1145/1363686.1363974(1252-1257)Online publication date: 16-Mar-2008
  • (2007)Foundations of rule-based query answeringProceedings of the Third international summer school conference on Reasoning Web10.5555/2391482.2391484(1-153)Online publication date: 3-Sep-2007
  • (2007)Isolating order semantics in order-sensitive xquery-to-SQL translationProceedings of the 24th British national conference on Databases10.5555/1770274.1770293(147-159)Online publication date: 3-Jul-2007
  • (2007)DUMAXProceedings of the 2nd international conference on Scalable information systems10.5555/1366804.1366871(1-4)Online publication date: 6-Jun-2007
  • (2006)Type-based XML projectionProceedings of the 32nd international conference on Very large data bases10.5555/1182635.1164152(271-282)Online publication date: 1-Sep-2006
  • (2006)MonetDB/XQueryProceedings of the 2006 ACM SIGMOD international conference on Management of data10.1145/1142473.1142527(479-490)Online publication date: 27-Jun-2006
  • (2006)The importance of algebra for XML query processingProceedings of the 2006 international conference on Current Trends in Database Technology10.1007/11896548_13(126-135)Online publication date: 26-Mar-2006

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media