skip to main content
10.1145/1321440.1321534acmconferencesArticle/Chapter ViewAbstractPublication PagescikmConference Proceedingsconference-collections
research-article

Efficient evaluation of high-selective xml twig patterns with parent child edges in tree-unaware rdbms

Published: 06 November 2007 Publication History

Abstract

Recent study showed that native twig join algorithms and tree-aware relational framework significantly outperform tree-unaware approaches in evaluating structural relationships in XML twig queries. In this paper, we present an efficient strategy to evaluate high-selective twig queries containing only parent-child relationships in a tree-unaware relational environment. Our scheme is built on top of our S<scp>UCXENT</scp>++ system. We show that by exploiting the encoding scheme of S<scp>UCXENT</scp>++, we can devise efficient strategy for evaluating such twig queries. Extensive performance studies on various data sets and queries show that our approach performs better than a representative tree-unaware approach (G<scp>LOBAL</scp>-O<scp>RDER</scp>) and a state-of-the-art native twig join algorithm (TJF<scp>AST</scp>) on all benchmark queries with the highest observed gain factors being 243 and 95, respectively. Additionally, our approach reduces significantly the performance gap between tree-aware and tree-unaware approaches and even outperforms a tree-aware approach(M<scp>ONET</scp>DB/XQ<scp>UERY</scp>) for certain high-selective twig queries. We also report our insights to the plan choices a relational optimizer made during twig query evaluation by visually characterizing its behavior over the relational selectivity space.

References

[1]
S. AL-KHALIFA, H. V. JAGADISH, J. M. PATEL ET AL. Structural Joins: A Primitive for Efficient XML Query Pattern Matching. In ICDE, 2002.
[2]
P. BONCZ, T. GRUST, M. VAN KEULEN, S. MANEGOLD, J. RITTINGER, J. TEUBNER. MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine. In SIGMOD, 2006.
[3]
N. BRUNO, N. KOUDAS, D. SRIVASTAVA. Holistic Twig Joins: Optimal XML Pattern Matching. In SIGMOD, 2002.
[4]
S. CHIEN, H-G. LI ET AL. Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents. In VLDB, 2006.
[5]
D. DEHAAN, D. TOMAN ET AL. A Comprehensive XQuery to SQL Translation Using Dynamic Interval Coding. In SIGMOD, 2003.
[6]
D. FLORESCU, D. KOSSMAN. Storing and Querying XML Data using an RDBMS. IEEE Data Engg. Bulletin. 22(3), 1999.
[7]
T. GRUST, J. TEUBNER, M. V. KEULEN. Accelerating XPath Evaluation in Any RDBMS. In ACM TODS, 29(1), 2004.
[8]
Q. LI, B. MOON. Indexing and Querying XML Data for Regular Path Expressions. In VLDB, 2001.
[9]
W. LIAN, N. MAMOULIS, D. W. CHEUNG, S. M. LIU. Indexing Useful Structural Patterns for XML Query Processing. In TKDE, 17(7), July 2005.
[10]
J. LU, T. CHEN, T. W. LING. Efficient Processing of XML Twig Patterns with Parent Child Edges: A Look-ahead Approach. In CIKM, 2004.
[11]
J. LU, T. W. LING ET AL. From Region Encoding to Extended Dewey: On Efficient Processing of XML Twig Pattern Matching. In VLDB, 2005.
[12]
N. REDDY, J. HARITSA. Analyzing Plan Diagrams of Database Query Optimizers. In VLDB, 2005.
[13]
B.-S SEAH, K. G. WIDJANARKO, S. S. BHOWMICK, B. CHOI, E. LEONARDI. Efficient Support for Ordered XPath Processing in Tree-Unaware Commercial Relational Databases. In DASFAA, 2007.
[14]
J. SHANMUGASUNDARAM, K. TUFTE ET AL. Relational Databases for Querying XML Documents: Limitations and Opportunities. In VLDB, 1999.
[15]
I. TATARINOV, S. VIGLAS, K. BEYER, ET AL. Storing and Querying Ordered XML Using a Relational Database System. In SIGMOD, 2002.
[16]
H. WANG, S. PARK, W. FAN, P. S. YU. ViST: A Dynamic Index Method for Querying XML Data by Tree Structures. In SIGMOD, 2003.
[17]
S. S. BHOWMICK, E. LEONARDI, H. SUN. Efficient Evaluation of High-Selective XML Twig Patterns with Parent Child Edges in Tree-Unaware RDBMS. Technical Report, 2007. Available at http://www.cais.ntu.edu.sg/~assourav/TechReports/PCTwig-TR.pdf.
[18]
B. YAO, M. TAMER ÖZSU, N. KHANDELWAL. XBench: Benchmark and Performance Testing of XML DBMSs. In ICDE, 2004

Cited By

View all
  • (2020)QuickSel: Quick Selectivity Learning with Mixture ModelsProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389727(1017-1033)Online publication date: 11-Jun-2020
  • (2012)ANDESThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-012-0275-921:6(889-914)Online publication date: 1-Dec-2012
  • (2012)Analyzing Plan Diagrams of XQuery OptimizersDatabase and Expert Systems Applications10.1007/978-3-642-32600-4_11(131-146)Online publication date: 2012
  • Show More Cited By

Index Terms

  1. Efficient evaluation of high-selective xml twig patterns with parent child edges in tree-unaware rdbms

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management
      November 2007
      1048 pages
      ISBN:9781595938039
      DOI:10.1145/1321440
      Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 06 November 2007

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. parent child edges
      2. tree-unaware rdbms
      3. twig query evaluation
      4. xml

      Qualifiers

      • Research-article

      Conference

      CIKM07

      Acceptance Rates

      Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

      Upcoming Conference

      CIKM '25

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)1
      • Downloads (Last 6 weeks)0
      Reflects downloads up to 15 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2020)QuickSel: Quick Selectivity Learning with Mixture ModelsProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389727(1017-1033)Online publication date: 11-Jun-2020
      • (2012)ANDESThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-012-0275-921:6(889-914)Online publication date: 1-Dec-2012
      • (2012)Analyzing Plan Diagrams of XQuery OptimizersDatabase and Expert Systems Applications10.1007/978-3-642-32600-4_11(131-146)Online publication date: 2012
      • (2011)Efficient evaluation of NOT-twig queries in tree-unaware relational databasesProceedings of the 16th international conference on Database systems for advanced applications - Volume Part I10.5555/1997305.1997353(511-527)Online publication date: 22-Apr-2011
      • (2011)Efficient Evaluation of NOT-Twig Queries in Tree-Unaware Relational DatabasesDatabase Systems for Advanced Applications10.1007/978-3-642-20149-3_37(511-527)Online publication date: 2011
      • (2009)Towards non-directional Xpath evaluation in a RDBMSProceedings of the 18th ACM conference on Information and knowledge management10.1145/1645953.1646156(1501-1504)Online publication date: 2-Nov-2009

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media