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 XPath 2.0 and XQuery 1.0 as recommended standards on January 23, 2007, ending the previous situation in which various query languages competed for dominance. 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 index technology
At present, 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 the 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 XML index is to design technology suitable for pattern matching.
XML index classification
Path-based XML index
Path-based index is based on the path information of nodes in the XML tree structure, and adopts a certain reduction method so that the reduced tree structure only maintains different path information and does not exist 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 structural summary of the refined path starting from the root node. . The string path formed by concatenating edge labels is described only once in the 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. , BLOB is to process 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 index is from the root node A structural summary of the starting refinement path. The string path formed by concatenating edge labels is described only once in the 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, thus Convert 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 partially matched query expressions with descendant-or-self axes defined in the XPath standard.
To this end, APEX [14] introduced information that relies on the distribution of XML data queries. : 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 whether 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 the 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 indexes generated based on Dewey [12] encoding, and the ORDPATH encoding of literature [13] A similar method is adopted, and a method of compressing ORDPATH is given, which 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's coding. For prefix coding, to determine whether a node v is a descendant of another node u, you only need to determine whether the coding of u is the prefix of the coding 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 code [begin, end], which satisfies: the interval code of a node includes the interval code of its descendant nodes. Also That is to say, node u in tree T is the ancestor of node v, if and only if
the first interval encoding scheme of start(u) is Dietz encoding, each node in tree T is assigned a pre-order traversal sequence number and 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 relationship, if and only if pre(u)
Another typical example of interval encoding index is the XISS index, which assigns a number pair to each node, where order is the extended preorder encoding and size is the descendants of the node. scope. 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 tree-shaped, so in When processing a query, you still essentially have to traverse the entire index tree to get the result. 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 query generation When there are many intermediate results, the join operation of 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.