Stack-based Pattern Matching Algorithm for XML Query Processing

Su-Cheng Haw; Chien-Sing Lee
June 2007
Journal of Digital Information Management;Jun2007, Vol. 5 Issue 3, p167
Academic Journal
With the popularity of XML as data exchange over the Web, querying XML data has become an important issue to be addressed. Since the logical structure of XML is a tree, establishing a parent-child (P-C), ancestor-descendant (A-D) or sibling relationship between nodes is essential for structural query processing. Thus, we propose using a labeling scheme to encode each element in the XML database by its positional information. Based on this labeling scheme, we further propose our TwigINLAB algorithm to optimize the query processing. Experimental results indicate that TwigINLAB can process both path queries and twig queries better than the TwigStack algorithm on an average of 27% and 14% respectively in terms of execution time using the XMARK benchmark dataset.


Related Articles

  • Lenguajes de consulta para xml: un análisis comparativo. Dominguez, Adelaida Delgado; Baeza-Yates, Ricardo // El Profesional de la Información;mar/abr2002, Vol. 11 Issue 2, p84 

    A query language for xml should be flexible enough to cover the whole range of information sources that can be labelled by xml, including databases and web documents. In this article we present a comparative analysis of several query languages that have been created for xml. We study sets of...

  • Using a relational database for scalable XML search. Cathey, Rebecca; Beitzel, Steven; Jensen, Eric; Grossman, David; Frieder, Ophir // Journal of Supercomputing;May2008, Vol. 44 Issue 2, p146 

    XML is a flexible and powerful tool that enables information and security sharing in heterogeneous environments. Scalable technologies are needed to effectively manage the growing volumes of XML data. A wide variety of methods exist for storing and searching XML data; the two most common...

  • VIREX and VRXQuery: interactive approach for visual querying of relational databases to produce XML. Lo, Anthony; Özyer, Tansel; Kianmehr, Keivan; Alhajj, Reda // Journal of Intelligent Information Systems;Aug2010, Vol. 35 Issue 1, p21 

    VIREX provides an interactive approach for querying and integrating relational databases to produce XML documents and the corresponding schemas. VIREX connects to each database specified by the user; analyzes the catalogue to derive an interactive diagram equivalent to the extended...

  • Efficient query processing for XML keyword queries based on the IDList index. Zhou, Junfeng; Bao, Zhifeng; Wang, Wei; Zhao, Jinjia; Meng, Xiaofeng // VLDB Journal International Journal on Very Large Data Bases;Feb2014, Vol. 23 Issue 1, p25 

    Keyword search over XML data has attracted a lot of research efforts in the last decade, where one of the fundamental research problems is how to efficiently answer a given keyword query w.r.t. a certain query semantics. We found that the key factor resulting in the inefficiency for existing...

  • XML Veritabani için Tavlama Benzetimi ile Sorgu Optimizasyonu. GÖZÜDEL, Yasar; AKCAYOL, M. Ali // International Journal of InformaticsTechnologies;2008, Vol. 1 Issue 1, p21 

    In this study, XML query optimization has been realized using simulated annealing. The nodes in query tree need to be joined for XML querying. The joining order of nodes is most important for the cost of query. In this study, the joining order has been done using simulated annealing. An...

  • Subtree Reconstruction, Query Node Intervals and Tree Pattern Query Evaluation. Yangjun Chen; Yibin Chen // Journal of Information Science & Engineering;Mar2012, Vol. 28 Issue 2, p263 

    Since the extensible markup language XML emerged as a new standard for information representation and exchange on the Internet, the problem of storing, indexing, and querying XML documents has been among the major issues of database research. In this paper, we study the tree pattern matching and...

  • XML Data Storage and Query Optimization in Relational Database by XPath Processing Model. Xiaojie Yuan; Xiangyu Hu; Dongxing Wu; Haiwei Zhang; Xin Lian // Journal of Software (1796217X);Apr2013, Vol. 8 Issue 4, p809 

    XML is de facto new standard for data representation and exchanging on the web. Along with the growth of XML data, traditional relational databases support XML data processing across-the-board. Consistent storage and efficient query for XML data is the chief problem in XML supported relational...

  • Retrieval quality vs. effectiveness of specificity-oriented search in XML collections. Fuhr, Norbert; Gövert, Norbert // Information Retrieval;Jan2006, Vol. 9 Issue 1, p55 

    Content-only queries in hierarchically structured documents should retrieve the most specific document nodes which are exhaustive to the information need. For this problem, we investigate two methods of augmentation, which both yield high retrieval quality. As retrieval effectiveness, we...

  • PERSISTENT STORAGE AND QUERYING OF COMPRESSED XML DOCUMENTS ON THE WEB. Demmings, Brian; Müldner, Tomasz; Gregory Leighton; Islam, Obidul; Young, Andrew // Proceedings of the IADIS International Conference on WWW/Interne;Jan2006, p178 

    We describe the design and implementation of a Web-based distributed system called TREESTORE, intended for storing compressed XML documents in a relational database. The use of a database is fully portable, requiring minimal changes to application code to substitute one database management...

  • SCHEMA BASED STORAGE OF XML DOCUMENTS IN RELATIONAL DATABASES. Suri, Pushpa; Sharma, Divyesh // International Journal on Web Service Computing;Jun2013, Vol. 4 Issue 2, p23 

    XML (Extensible Mark up language) is emerging as a tool for representing and exchanging data over the internet. When we want to store and query XML data, we can use two approaches either by using native databases or XML enabled databases. In this paper we deal with XML enabled databases. We use...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics