Existing XML twig pattern query processing algorithms fall into two classes: the relational approach and the native approach. Both kinds of approaches have their advantages and limitations. Particularly, the relational approach can search for data values (content search) efficiently using tables, but it is not efficient to match query structure to documents (structural search). The native approach processes structural search efficiently, but it has problem dealing with values. In this chapter, a hybrid approach for XML query processing is introduced. In this approach, the content search and the structural search in a twig pattern query are performed separately using the data structures in the relational approach and the native approach, i.e. relational tables and inverted lists. The authors show that this hybrid style technique can process both structural search and content search efficiently, and then improve the query processing performance comparing to the existing approaches. Furthermore, when more semantic information on object class and relationship between objects in the XML document is known, the relational tables used can be optimized according to such semantic information to achieve a better performance. Finally after performing twig pattern matching, value results can be extracted easily using relational tables, rather than navigating the document again in many other approaches.
TopIntroduction
XML is emerging as a standard format for data representation and exchange over the Internet. As a result, there is a compelling need of developing efficient algorithms to query XML data. An XML document is normally modeled as a tree, without considering ID references. In an XML tree, the nodes represent the elements, attributes and values in the document and the edges reflect the nested relationships between elements, attributes and values. Figure 1 shows a small XML document with its tree model representation. In most standard XML query languages, e.g. XPath and XQuery recommended by W3C, the core pattern of a query is also a tree structure (or a set of tree structures). We call such a tree-structured query pattern a twig pattern. Finding all occurrences of a twig pattern query in an XML document is considered as an essential operation for XML query processing. Consider a query to find the titles of all books written by Paredaens in the bookstore document shown in Figure 1, the corresponding XPath expression is //book[author=“Paredaens”]/title, and the twig pattern representation of this XPath query is shown in Figure 2.
Figure 1. An XML document with tree model representation.
Figure 2. Example twig pattern query.
Normally, an XML query consists of structural search and content search. The structural search in a query aims to find all matches that satisfy the structural constraints between query nodes in the document. Whereas the content search filters the query result based on the value comparison in query predicates. For the above XPath query, //book[author]/title is a structural search and author=“Paredaens” is a content search. How to efficiently process structural search and content search are equivalently important to achieve a good query processing performance.
The XML query processing algorithms are categorized into two classes: the relational approach and the native approach. In the early stage, many research works focus on using relational databases to store and query semi-structured XML data. The main idea of the relational approach is to shred XML documents into relational tables, and transform XML queries into SQL queries to query the database. During query transformation, an XML query structure is normally expressed by multiple selections and joins in the corresponding SQL statement, thus the overhead on these table operations, especially join, may seriously affect the efficiency of the structural search. Later how to process XML queries natively becomes a hot research topic, because the native approach does not use relational database and avoids the overhead on relational operations. The structural join based approach is an important native approach widely accepted by researchers. In this approach, inverted lists are used to store the occurrences of each type of document node, in terms of their positional labels, and the queries are processed by performing structural joins between query nodes using corresponding inverted lists. The structural join based approach is proven very efficient to process structural search, in contrast with the relational approach. However, the inverted list could not perform value comparison in content search efficiently. Furthermore, after finding the occurrences of a query pattern in a given document, inverted list is not feasible to extract child values to answer the query based on positional labels. Value extraction has to be done by navigating the original document, which is obviously not efficient.
In this chapter, we integrate the ideas of the relational approach and the native approach to process XML twig pattern queries. In more details, both relational tables and inverted lists are used to perform content search and structural search separately in a query. With this hybrid approach, problems in the relational approach and the native approach are avoided and the advantages are inherited. Furthermore, the relational tables used in this approach can be optimized when more semantics on object is known in XML documents. These semantic optimizations will further enhance the query processing efficiency. Before we move to the details, some background knowledge and related work are introduced in advance.