'XML' index technology based on relational database engine

XML (Extensible Markup Language) has become the standard for data representation and data exchange in Web applications. With the rapid development of the Internet, especially the widespread use of e-commerce, Web services and other applications, XML type data has become the current mainstream. data form. Therefore, XML data management technology, especially XML data query technology, has become a current research hotspot.

Compared with relational data, XML has various advantages, but its biggest drawback is its efficiency. Because in relational data files, data field names only need to appear once, while in XML data files, element names will appear repeatedly, which will certainly affect the efficiency of the query. In order to improve the query efficiency of XML as much as possible, it is necessary to provide indexing function for XML type.

The World Wide Web Consortium identified XPath2.0 and XQuery1.0 as recommended standards on January 23, 2007, ending the previous competition between various query languages. Based on this standard, in addition to traditional manufacturers, various scientific research institutions have proposed implementations of XPath and XQuery (there are more than a dozen mentioned in the literature), with different storage models, different query algorithms, and optimization methods. , in this context, Dameng Database Company also proposed its own XML query engine model based on its own development strategy. Currently, Dameng's XML query engine is under intense development, and establishing effective indexes for XML data is an important factor affecting XML. An important factor in data query performance. Based on an in-depth analysis of the indexing technology of existing database products, a more reasonable index structure is designed for the Dameng XML query engine so that the engine can achieve optimal performance.

Introduction to XML indexing technology

Currently, people’s research on XML is mainly divided into two aspects. One is a native database for the storage, query and management of semi-structured data such as XML. The data and metadata are completely expressed in XML structures and have nothing to do with its underlying data storage format (such as object model, relational model, etc.). The other is the mutual conversion between it and the relational database, using the mature technology of the relational database to process XML data. Since the latter direction has more practical significance, it has become the focus of XML research.

In addition to storage solutions, index technology is also one of the most important factors in determining a database system. If no index structure is built for XML documents, then any query for XML data is likely to result in traversing the entire document tree. As the XML data set increases, this overhead is intolerable. Therefore, the research on XML index technology has high theoretical and practical value.

Although traditional indexing technology has been relatively mature after long-term accumulation, this type of indexing technology mainly focuses on the function of locating data records based on values ​​(rather than patterns with certain relationships), and does not pay much attention to it. Logical relationships between data records; the basic feature of XML data query is to extract data that conforms to the pattern based on the input of pattern features (structural relationships described in the form of regular path expressions). Therefore, the main content of the XML index is to design the pattern suitable for Matching technology.

XML index classification

Path-based XML index

Path-based index is based on the path information of nodes in the XML tree structure, adopting some kind of reduction method, The reduced tree structure only maintains different path information, and there will not be two nodes with the same path. Such indexes that have been proposed include: DataGuides index, Index Fabric index, Adaptive Path Index for XML Data (APEX)

Dataguides index is a refinement starting from the root node. A structural summary of the path. The string paths formed by concatenating edge labels are described only once in Dataguides. Dataguides reduce the number of nodes required when traversing path queries, and are efficient at traversing XML documents from the root. However, path queries containing wildcard characters or path queries with the descendant-or-self axis defined in the XPath standard require multiple connection operations, resulting in low query efficiency and data redundancy.

Then write the java object file TestLob.java about these two large fields, and define the types as CLOB and BLOB attribute fields as String and byte[] types respectively. Since CLOB is a large text type, it corresponds to The String type in Java is used. BLOB handles some large files that are not strictly defined and are stored in the form of binary streams, so let it use the byte[] type, and then define the Getter and Setter methods of these two properties respectively. The relevant code is as follows:

Dataguides The index is a structural summary of the refined path starting from the root node. The string paths formed by concatenating edge labels are described only once in Dataguides. Dataguides reduce the number of nodes required when traversing path queries, and are efficient at traversing XML documents from the root. However, path queries containing wildcard characters or path queries with the descendant-or-self axis defined in the XPath standard require multiple connection operations, resulting in low query efficiency and data redundancy.

Index Fabric is an index structure developed on the Patricia Trie tree. It encodes each marked path to each element node with a string, and then inserts these encoded values ​​into the Patricia Trie tree. Go, thus converting the query of XML data according to the path into the query of string. When querying, first encode the query path into a string form, and then search it in the index tree. The advantage of Index Fabric index is that it stores the hierarchical structure information of XML data, uniformly handles the retrieval of XML data with schema and schema-less information, and makes the time required for querying and updating XML data related to the hierarchy rather than to the The length of the index key is related. The disadvantage of Index Fabric index is that it loses the structural relationship between element nodes, because it only retains the information of element nodes with text values. Therefore, similar to DataGuides indexes, Index Fabric indexes are not efficient in handling partial matching query expressions with descendant-or-self axes defined in the XPath standard. For this reason, APEX [14] introduced the dependency XML data query distribution information: Pre-save label nodes corresponding to frequently occurring XML query statements in a hash structure. Its function is similar to the function of Cache: when a new query requires processing, it first searches the hash table to see if there is a satisfying node set. But it is less efficient for query expressions with element values ​​or attribute values.

Node-based index

Node-based index essentially decomposes XML data into a record set of data units, and at the same time saves the location information of the unit in the XML data in the record. Unlike path-based indexes, node-based indexes break the restriction that nodes must be found through label paths and decompose XML data into node records in a canonical form. Because it saves the location information of nodes and can be well integrated into mature relational database management systems, it is currently the most widely used index.

According to different encoding methods of location information, node-based indexes can generally be divided into the following categories:

1. Prefix-based indexes

Prefix-based indexes are mainly It is an index generated based on Dewey [12] encoding. The ORDPATH encoding in [13] uses a similar method, and gives a method of compressing ORDPATH. This method has been applied to the index organization of SQL Server 2005.

The basic idea of ​​prefix coding is to directly use the coding of a node's parent node as the prefix of the node coding. For prefix coding, to determine whether a node v is a descendant of another node u, just determine The encoding of u is the prefix of the encoding of v. An important property of prefix coding indexes is their dictionary ordering: for any node u in the subtree rooted at node r, its prefix coding c(u) is greater (less than) its left sibling subtree (right sibling subtree) ) The prefix encoding of all nodes in . Therefore, prefix-based indexes can not only effectively support the calculation of inclusion relationships, but also effectively support the calculation of document position relationships.

2. Index based on interval coding

For interval coding index, each node in the tree T is assigned an interval coding [begin, end], which satisfies: the interval of a node The encoding contains the interval encoding of its descendant nodes. That is, node u in tree T is the ancestor of node v if and only if start(u)

The first interval encoding scheme is Dietz encoding , each node in the tree T is assigned a tuple with a pre-order traversal number and a post-order traversal number. Since an ancestor node u in the tree T must appear in the pre-order traversal (post-order traversal) Its descendant node v is before (after), therefore, nodes u and v are ancestor/descendant relationships if and only if PRe(u)

Another typical example of interval encoding index is the XISS index, which Assign a number pair to each node, where order is the extended preorder code and size is the range of the node's descendants. For any node X and Y in a document tree, if and only if order(x)

XISS index decomposes the original query statement into subexpressions. Then implement the query for these sub-expressions respectively, and finally join these intermediate results to obtain the query result set. This can better support query statements containing wildcard characters. However, it obtains the final query result after concatenating each intermediate result. Although such a method can indeed solve all wildcard problems, the concatenation of such intermediate results is likely to be very time-consuming, especially for simple expressions with long paths.

Comparison of two indexing mechanisms

Path-based indexing is mainly based on the node merging strategy. Through techniques such as node equivalence and path equivalence, an index structure that is much smaller than the original document is obtained. , its structure is still a tree, so when processing a query, you basically still have to traverse the entire index tree to get the results. Path-based indexes can support simple path expression queries very well, but for regular path expressions, it does not work very well.

Node-based index indexes each node through encoding technology. The structural relationship between nodes can be determined in constant time through encoding. It can support regular path expressions well, but for long path expressions , especially when the query generates many intermediate results, the join operation of the node index is expensive.

Path-based indexing and node-based indexing each have their own advantages and disadvantages, but they can complement each other. At present, in practical applications, node-based indexing is more widely used and the research is relatively mature. Therefore, Dameng Company's research on XML index structure mainly focuses on node-based indexing, and makes appropriate improvements with reference to path-based indexing.

The above is the content of "XML" indexing technology based on relational database engine. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!