XML data query technology has become a hot research topic nowadays.

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 a relational data file, the field name of the data only needs to appear once, but in the XML data file, the element name will appear repeatedly, which will definitely 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 XPath 2.0 and XQuery 1.0 as recommended standards on January 23, 2007, ending the previous competition among 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 is mainly based on values ​​(rather than patterns with certain relationships) The function of locating data records does not pay much attention to the logical relationship 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, XML The main content of indexing is to design techniques suitable for pattern matching.

XML index classification

Path-based XML index

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

Dataguides 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.

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

Dataguides 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 at handling partial match query expressions with descendant-or-self axes defined in the XPath standard

#For this reason , APEX [14] introduces information that depends on the distribution of XML data queries: label nodes corresponding to frequently occurring XML query statements are saved in a hash structure in advance. 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 data units Record collection, and save 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 index

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

The basic idea of ​​prefix encoding is to directly use the encoding of a node's parent node as the prefix of the node encoding. For prefix encoding, To determine whether a node v is a descendant of another node u, just determine whether the code of u is the prefix of the code 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 given an interval code [begin, end], which satisfies: the interval code of a node includes the interval code of its descendant nodes. In other words, node u in tree T is the ancestor of node v if and only if start (u)

The first interval coding scheme is Dietz coding. Each node in the tree T is assigned a pre-order traversal sequence number and a post-order traversal sequence number. Tuple. Since an ancestor node u in the tree T must appear before (after) its descendant node v in the pre-order traversal (post-order traversal), therefore, the nodes u and v are ancestor/descendant relationships, If and only if PRe(u)

Another typical example of interval-encoded index is the XISS index, which assigns each node a number pair, where order is extended Preorder encoding, size is the range of descendants of the node. 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

The path-based index is mainly based on the node merging strategy, through nodes, etc. Using techniques such as valency and path equivalence, we can obtain an index structure that is much smaller than the original document. Its structure is still tree-shaped, so when processing queries, we still basically 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 data query technology that has become a hot research topic today. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!