Abstract
Finding all occurrences of a twig pattern in a database is a core operation in xml query processing. Recent study showed that 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 a specific class of structural relationship called nca -twiglet in a tree-unaware relational environment. Informally, nca-twiglet is a subtree in a twig pattern where all nodes have the same nearest common ancestor (the root of nca-twiglet). We focus on nca-twiglets having parent-child relationships. Our scheme is build on top of our Sucxent++ system. We show that by exploiting the encoding scheme of Sucxent++ we can reduce useless structural comparisons in order to evaluate nca-twiglets. Through a comprehensive experiment, we show that our approach is not only more scalable but also performs better than a representative tree-unaware approach on all benchmark queries with the highest observed gain factors being 352.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Al-Khalifa, S., Jagadish, H.V., Patel, J.M., et al.: Structural Joins: A Primitive for Efficient XML Query Pattern Matching. In: ICDE (2002)
Alstrup, S., Gavoille, C., Kaplan, H., Rauhe, T.: Nearest Common Ancestors: A Survey and a new Distributed Algorithm. In: SPAA (2002)
Boncz, P., Grust, T., van Keulen, M., Manegold, S., Rittinger, J., Teubner, J.: MonetDB/XQuery: A Fast XQuery Processor Powered by a Relational Engine. In: SIGMOD (2006)
Bruno, N., Koudas, N., Srivastava, D.: Holistic Twig Joins: Optimal XML Pattern Matching. In: SIGMOD (2002)
Chien, S., Li, H-G., Tatemura, J., et al.: Twig2Stack: Bottom-up Processing of Generalized-Tree-Pattern Queries over XML Documents. In: VLDB (2006)
DeHaan, D., Toman, D., Consens, M.P., Ozsu, M.T.: A Comprehensive XQuery to SQL Translation Using Dynamic Interval Coding. In: SIGMOD (2003)
Florescu, D., Kossman, D.: Storing and Querying XML Data using an RDBMS. IEEE Data Engg. Bulletin 22(3) (1999)
Grust, T., Teubner, J., Keulen, M.V.: Accelerating XPath Evaluation in Any RDBMS. In: ACM TODS, vol. 29(1) (2004)
Li, Q., Moon, B.: Indexing and Querying XML Data for Regular Path Expressions. In: VLDB (2001)
Lu, J., Ling, T.W., Chen, T.Y., Chen, T.: From Region Encoding to Extended Dewey: On Efficient Processing of XML Twig Pattern Matching. In: VLDB (2005)
Rao, P., Moon, B.: PRIX: Indexing and Querying XML Using Prufer Sequences. In: ICDE (2004)
Seah, B.-S, Widjanarko, K.G., Bhowmick, S.S., Choi, B., Leonardi, E.: Efficient Support for Ordered XPath Processing in Tree-Unaware Commercial Relational Databases. In: DASFAA (2007)
Shanmugasundaram, J., Tufte, K., et al.: Relational Databases for Querying XML Documents: Limitations and Opportunities. In: VLDB (1999)
Tatarinov, I., Viglas, S., Beyer, K., et al.: Storing and Querying Ordered XML Using a Relational Database System. In: SIGMOD (2002)
Wang, H., Park, S., Fan, W., Yu, P.S.: ViST: A Dynamic Index Method for Querying XML Data by Tree Structures. In: SIGMOD (2003)
Widjanarko, K.J., Leonardi, E., Bhowmick, S.S.: Efficient Evaluation of Nearest Common Ancestor in XML Twig Queries Using Tree-Unaware RDBMS. Technical Report (2007), Available at http://www.cais.ntu.edu.sg/~assourav/TechReports/nca-TR.pdf
Wu, X., Lee, M., Hsu, W.: A Prime Number Labeling Scheme for Dynamic Ordered XML Trees. In: ICDE (2004)
Yao, B., Tamer Özsu, M., Khandelwal, N.: XBench: Benchmark and Performance Testing of XML DBMSs. In: ICDE (2004)
Yoshikawa, M., Amagasa, T., Shimura, T., Uemura, S.: XRel: a path-based approach to storage and retrieval of xml documents using relational databases. ACM TOIT 1(1), 110–141 (2001)
Zhang, C., Naughton, J., Dewitt, D., Luo, Q., Lohmann, G.: On Supporting Containment Queries in Relational Database Systems. In: SIGMOD (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Widjanarko, K.G., Leonardi, E., Bhowmick, S.S. (2007). Efficient Evaluation of Nearest Common Ancestor in XML Twig Queries Using Tree-Unaware RDBMS. In: Wagner, R., Revell, N., Pernul, G. (eds) Database and Expert Systems Applications. DEXA 2007. Lecture Notes in Computer Science, vol 4653. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74469-6_60
Download citation
DOI: https://doi.org/10.1007/978-3-540-74469-6_60
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74467-2
Online ISBN: 978-3-540-74469-6
eBook Packages: Computer ScienceComputer Science (R0)