Abstract
Unlike a twig query, an Xtwig query contains some selection predicates with reverse axes which are either ancestor or parent. To evaluate such queries in the stream-based context, some rewriting rules have been proposed to transform the paths with reverse axes into equivalent reverse-axis-free ones. However, the transformation method is expensive due to multiple scanning input streams and the generation of unnecessary intermediate results. To solve these problems, a holistic stream-based algorithm XtwigStack is proposed for Xtwig queries. Experiments show that XtwigStack is much more efficient than the transformation method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
AL-Khalifa, S., Jagadish, H.V., Kouda, N., Patel, J.M., Srivastava, D., Wu, Y.: Structural joins: a primitive for efficient XML query pattern matching. In: Proc. 18th Int. Conf. Data Engineering (ICDE’02), pp. 141–152. IEEE Computer Society, San Jose (2002)
Al-Khalifa, S., Jagadish, H.V., Koudas, N., Patel, J.M., Zhang, C., Naughton, J.F., DeWitt, D.J., Luo, Q., Lohman, G.M.: On supporting containment queries in relational database management systems. In: Proc. 27th ACM SIGMOD Int. Conf. Management of Data (SIGMOD’01), pp. 425–436. ACM, Santa Barbara (2001)
Arion, A., Bonifati, A., Manolescu, I., Pugliese, A.: Path summaries and path partitioning in modern XML databases. World Wide Web 11(1), 117–151 (2008)
Barton, C., Charles, P., Goyal, D., Raghavachari, M., Fontoura, M., Josifovski, V.: Streaming XPath processing with forward and backward axes. In: Proc. 19th Int. Conf. on Data Engineering (ICDE’03), Bangalore, pp. 455–466. IEEE Computer Society, Bangalore (2003)
Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: optimal XML pattern matching. In: Proc. 28th ACM SIGMOD Int. Conf. Management of Data (SIGMOD’02), pp. 310–321. ACM, Madison (2002)
Bruno, N., Srivastava, D., Koudas, N.: Holistic twig joins: optimal XML pattern matching. In: Proc. 28th ACM SIGMOD Int. Conf. Management of Data (SIGMOD’02), pp. 310–321. ACM, Madison (2002)
Chan, C.Y., Ni, Y.: Piggyback optimization of XML data dissemination. In: Proc. 23rd Int. Conf. Data Engineering (ICDE’07), pp. 1454–1455. IEEE Computer Society, Istanbul (2007)
Chen, S., Li, H., Tatemura, J., Hsiung, W., Agrawal, D., Candan, K.S.: Twig2Stack: bottom-up processing of generalized treepattern queries over XML documents. In: Proc. 32nd Int. Conf. Very Large Data Bases (VLDB’06), pp. 283–294. ACM, Seoul (2006)
Chen, T., Ling, T.W., Chan, C.: Prefix path streaming: a new clustering method for optimal XML twig pattern matching. In: Proc. 15th Int. Conf. Database and Expert Systems Applications (DEXA’04), pp. 801–811. Springer, Zaragoza (2004)
Fiebig, T., Helmer, S., Kanne, C.C., Moerkotte, G., Neumann, J., Schiele, R., Westmann, T.: Anatomy of a native XML base management system. VLDB J. 11(4), 292–314 (2003)
Florescu, D., Kossmann, D.: Storing and querying xml data using an rdmbs. IEEE Data Eng. Bull. 22(3), 27–34 (1999)
Jagadish, H.V., AL-Khalifa, S., Chapman, A., Lakshmanan, L.V., Nierman, A., Paparizos, S., Patel, J.M., Srivastava, D., Wu, Y., Yu, C.: TIMBER: a native XML database. VLDB J. 11(4), 274–291 (2002)
Jiao, E., Ling, T.W., Chan, C.Y.: PathStack : a holistic path join algorithm for path query with not-predicates on XML data. In: Proc. 10th Int. Conf. Database Systems for Advanced Applications (DASFAA’05), pp. 113–124. Springer, Beijing (2005)
Lu, J., Chen, T., Ling, T.W.: TJFast: effcient processing of XML twig pattern matching. In: Proc. 14th Int. Conf. World Wide Web (WWW’05), pp. 1118–1119. ACM, Chiba (2005)
Lu, J., Ling, T.W., Chan, C.-Y., Chen, T.: From region encoding to extended dewey: on efficient processing of XML twig pattern matching. In: Proc. 31st Int. Conf. Very Large Data Bases (VLDB’05), pp. 193–204. ACM, Trondheim (2005)
Lv, J., Wang, G., Yu, J.X., Yu, G., Lu, H., Sun, B.: Performance evaluation of a DOM-based XML database: storage, indexing and query optimization. In: Proc. 3rd Int. Conf. Web-Age Information Management (WAIM’02), pp. 13–24. Springer, Beijing (2002)
McHugh, J., Abiteboul, S., Goldman, R., Quass, D., Widom, J.: Lore: a database management system for semistructured data. SIGMOD Rec. 26(3), 54–66 (1997)
Olteanu, D., Meuss, H., Furche, T., Bry, F.: XPath: looking foward. In: Proc. the EDBT Workshop on XML Data Management, pp. 109–127. Matfyzpress, Prague (2002)
Qin, L., Yu, J.X., Ding, B.: TwigList: make twig pattern matching fast. In: Proc. 12th Int. Conf. Database Systems for Advanced Applications (DASFAA’07), pp. 850–862. Springer, Bangkok (2007)
Tatarinov, I., Viglas, S., Beyer, K., Shekita, E., Shanmugasundaram, J., Zhang, C.: Storing and querying ordered XML using a relational database system. In: Proc. 28th ACM SIGMOD Int. Conf. Management of Data (SIGMOD’02), pp. 204–215. ACM, Madison (2002)
University of Washington (2002) University of Washington XML Repository. http://www.cs.washington.edu/research/xmldatasets/
Wang, H., Li, J., Wang, H.: Clustered chain path index for XML document: efficiently processing branch queries. World Wide Web 11(1), 153–168 (2008)
Wang, G., Sun, B., Lv, J., Yu, G.: RPE query processing and optimization techniques for XML databases. J. Comput. Sci. Technol. 19(2), 224–237 (2004)
Wang, Y., Xing, C., Zhou, L.: Managing and querying of videos by semantics in digital library—a semantic model SemTTE and its XML-based implementation. In: Proc. 9th Int. Conf. Asian Digital Libraries (ICADL’06), pp. 519–522. Springer, Kyoto (2006)
Wong, K.-F., Yu, J.F., Tang, N.: Answering XML queries using path-based indexes: a survey. World Wide Web 9(3), 277–299 (2006)
W3C (1999) XPath. http://www.w3.org/TR/xpath
XMARK (2003) XMARK. http://monetdb.cwi.nl/xml
Yoshikawa, M., Amagasa, T.: XRel: a path-based approach to storage and retrieval of XML documents using relational databases. ACM Trans. Internet Technol. 1(1), 110–141 (2001)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, G., Ning, B. & Yu, G. Holistically Stream-based Processing Xtwig Queries. World Wide Web 11, 407–425 (2008). https://doi.org/10.1007/s11280-008-0047-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11280-008-0047-z