Abstract
Query processing performance in XML databases can be greatly enhanced by the usage of materialized views whose content has been stored in the database. This requires a method for identifying query subexpressions matching the views, a process known as view-based query rewriting. This process is quite complex for relational databases, and all the more daunting on XML databases.
Current XML materialized view proposals are based on tree patterns, since query navigation is conceptually close to such patterns. However, the existing algorithms for extracting tree patterns from XQuery do not detect patterns across nested query blocks. Thus, complex, useful tree pattern views may be missed by the rewriting algorithm. We present a novel tree pattern extraction algorithm from XQuery queries, able to identify larger patterns than previous methods. Our algorithm has been implemented in an XML database prototype [5].
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
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Al-Khalifa, S., Jagadish, H.V., Patel, J.M., Wu, Y., Koudas, N., Srivastava, D.: Structural joins: A primitive for efficient XML query pattern matching. In: ICDE (2002)
Amer-Yahia, S., Kotidis, Y.: Web-services architectures for efficient XML data exchange. In: ICDE (2004)
Arion, A., Benzaken, V., Manolescu, I.: XML Access Modules: Towards Physical Data Independence in XML Databases. In: XIME-P Workshop (2005)
Arion, A., Benzaken, V., Manolescu, I., Vijay, R.: ULoad: Choosing the Right Store for your XML Application (demo). In: VLDB (2005)
Beyer, K., Ozcan, F., Saiprasad, S., Van der Linden, B.: DB2/XML: designing for evolution. In: SIGMOD (2005)
Brantner, M., Helmer, S., Kanne, C.-C., Moerkotte, G.: Full-Fledged Algebraic XPath Processing in Natix. In: ICDE (2005)
Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: Optimal XML pattern matching. In: SIGMOD (2002)
Chen, Z., Jagadish, H.V., Lakshmanan, L., Paparizos, S.: From tree patterns to generalized tree patterns: On efficient evaluation of XQuery. In: VLDB (2003)
Cooper, B., Sample, N., Franklin, M., Hjaltason, G., Shadmon, M.: A fast index for semistructured data. In: VLDB (2001)
Deutsch, A., Tannen, V.: MARS: A system for publishing XML from mixed and redundant storage. In: VLDB (2003)
Jagadish, H.V., Al-Khalifa, S., Chapman, A., Lakshmanan, L., Nierman, A., Paparizos, S., Patel, J., Srivastava, D., Wiwatwattana, N., Wu, Y., Yu, C.: Timber: A native XML database. VLDB J. 11(4) (2002)
Jiang, H., Lu, H., Wang, W., Xu, J.: XParent: An efficient RDBMS-based XML database system. In: ICDE (2002)
Kaushik, R., Bohannon, P., Naughton, J., Korth, H.: Covering indexes for branching path queries. In: SIGMOD (2002)
Manolescu, I.: XML query processing: storage and query model interplay. Tutorial at the EDBT summer school (2004), Available at: http://www-rocq.inria.fr/~manolesc
Manolescu, I., Florescu, D., Kossmann, D.: Answering XML queries over heterogeneous data sources. In: VLDB (2001)
Manolescu, I., Papakonstantinou, Y.: An unified tuple-based algebra for XQuery (2005), Available at: http://www-rocq.inria.fr/~manolesc/PAPERS/algebra.pdf
Miklau, G., Suciu, D.: Containment and equivalence for an XPath fragment. In: PODS (2002)
Neven, F., Schwentick, T.: XPath containment in the presence of disjunction, DTDs, and variables. In: Calvanese, D., Lenzerini, M., Motwani, R. (eds.) ICDT 2003. LNCS, vol. 2572, pp. 312–326. Springer, Heidelberg (2002)
O’Neil, P., O’Neil, E., Pal, S., Cseri, I., Schaller, G., Westbury, N.: ORDPATHs: Insert-friendly XML node labels. In: SIGMOD (2004)
Paparizos, S., Wu, Y., Lakshmanan, L., Jagadish, H.: Tree logical classes for efficient evaluation of XQuery. In: SIGMOD (2004)
Ré, C., Siméon, J., Fernandez, M.: A complete and efficient algebraic compiler for XQuery. In: ICDE (2006)
XQuery 1.0, www.w3.org/TR/xquery
Xu, W., Ozsoyoglu, M.: Rewriting XPath queries using materialized views. In: VLDB (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arion, A., Benzaken, V., Manolescu, I., Papakonstantinou, Y., Vijay, R. (2006). Algebra-Based Identification of Tree Patterns in XQuery. In: Larsen, H.L., Pasi, G., Ortiz-Arroyo, D., Andreasen, T., Christiansen, H. (eds) Flexible Query Answering Systems. FQAS 2006. Lecture Notes in Computer Science(), vol 4027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11766254_2
Download citation
DOI: https://doi.org/10.1007/11766254_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34638-8
Online ISBN: 978-3-540-34639-5
eBook Packages: Computer ScienceComputer Science (R0)