Abstract
XML has emerged as a popular formatting and exchanging language for nearly all kinds of data, including scientific data. Efficient query processing in XML databases is of great importance for numerous applications. Trees or twigs are the core structural elements in XML data and queries. Recently, a holistic computing approach has been proposed for extended XML twig patterns, i.e., B-Twigs (Boolean Twigs), which allows presence of AND, OR, and NOT logical predicates. This holistic approach, however, resorts to pre-normalization on input B-Twig queries, and therefore causes extra processing time and possible expansion on input queries. In this paper, we propose a direct, holistic approach to B-Twig query evaluation without using any preprocessing or normalization, and present our algorithm and experimental results.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
University of Washington XML repository, http://www.cs.washington.edu/research/xmldatasets/
NASA Goddard Astronomical Data Center (ADC) ’Scientific Dataset’ in XML, http://xml.coverpages.org/nasa-adc.html
Simple API for XML(SAX), http://www.saxproject.org/about.html
Al-Khalifa, S., Jagadish, H.V., Patel, J.M., et al.: Structural joins: A primitive for efficient XML query pattern matching. In: ICDE 2002 Conf. Proc., pp. 141–152 (2002)
Bruno, N., Koudas, N., Srivastava, D.: Holistic twig joins: Optimal XML pattern matching. In: SIGMOD 2002 Conf. Proc., pp. 310–321. ACM (June 2002)
Jiang, H., Lu, H., Wang, W.: Efficient processing of twig queries with OR-predicates. In: SIGMOD 2004 Conf. Proc., pp. 59–70 (2004)
Che, D., Ling, T.W., Hou, W.-C.: Holistic boolean twig pattern matching for efficient XML query processing. IEEE Transactions on Knowledge and Data Engineering, preprint available: http://www.computer.org/portal/web/csdl/doi/10.1109/TKDE.2011.128
Chen, T., Lu, J., Ling, T.W.: On boosting holism in XML twig pattern matching using structural indexing techniques. In: SIGMOD 2005 Conf. Proc., pp. 455–466 (June 2005)
Jagadish, H.V., Al-Khalifa, S., Chapman, A., et al.: Timber: A native XML database. The VLDB Journal 11(4), 274–291 (2002)
Jiang, H., Wang, W., Lu, H., Yu, J.X.: Holistic twig joins on indexed XML documents. In: VLDB 2003 Conf. Proc., pp. 273–84 (September 2003)
Lu, J., Chen, T., Ling, T.W.: Efficient processing of XML twig patterns with parent child edges: A look-ahead approach. In: CIKM 2004 Conf. Proc., pp. 533–542 (November 2004)
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: VLDB 2005 Conf. Proc., pp. 193–204 (August 2005)
Lu, J., Ling, T.-W., Yu, T., Li, C., Ni, W.: Efficient Processing of Ordered XML Twig Pattern. In: Andersen, K.V., Debenham, J., Wagner, R. (eds.) DEXA 2005. LNCS, vol. 3588, pp. 300–309. Springer, Heidelberg (2005)
Xu, X., Feng, Y., Wang, F.: Efficient processing of XML twig queries with all predicates. In: ICIS 2009 Proc., pp. 457–462. IEEE/ACIS (June 2009)
Yu, T., Ling, T.-W., Lu, J.: TwigStackList¬: A Holistic Twig Join Algorithm for Twig Query with Not-Predicates on XML Data. In: Li Lee, M., Tan, K.-L., Wuwongse, V. (eds.) DASFAA 2006. LNCS, vol. 3882, pp. 249–263. Springer, Heidelberg (2006)
Zhang, C., Naughton, J., DeWitt, D., et al.: On supporting containment queries in relational database management systems. In: SIGMOD 2001 Conf. Proc, pp. 425–436 (May 2001)
Izadi, S.K., Harder, T., Haghjoo, M.S.: S3: Evaluation of tree pattern XML queries supported by structural summaries. Data and Knowledge Engineering 68(1), 126–145 (2009)
Izadi, S.K., Haghjoo, M.S.: Theo Harder, S3: Processing tree-pattern XML queries with all logical operators. Data Knowledge Engineering 72, 31–62 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ding, D., Che, D., Hou, WC. (2012). A Direct Approach to Holistic Boolean-Twig Pattern Evaluation. In: Liddle, S.W., Schewe, KD., Tjoa, A.M., Zhou, X. (eds) Database and Expert Systems Applications. DEXA 2012. Lecture Notes in Computer Science, vol 7446. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32600-4_25
Download citation
DOI: https://doi.org/10.1007/978-3-642-32600-4_25
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32599-1
Online ISBN: 978-3-642-32600-4
eBook Packages: Computer ScienceComputer Science (R0)