CN1965316A - Index for accessing XML data - Google Patents

Abstract

Provides techniques for indexing XML documents. According to one embodiment, a PATH table is created to store one row for each index node of the XML document. A row of a node's PATH table includes (1) information for locating the XML document containing the node, (2) information identifying the node's path, and (3) information identifying the node's location within the hierarchy of the XML document containing the node . A row of a node's PATH table may also include a value if the node is associated with a value. The PATH table is made easy to answer XPath queries through secondary indexes.

Description

Index for accessing XML data

priority statement

This application claims priority to U.S. Provisional Patent Application No. 60/560,927, filed April 9, 2004, entitled "XML INDEXFOR XML DATA STORED IN VARIOUS STORAGE FORMATS," and claims Priority to U.S. Provisional Patent Application No. 60/580,445, entitled "XML INDEX FOR XML DATA STORED INVARIOUS STORAGE FORMATS," the entire contents of which are hereby incorporated by reference.

technical field

This invention relates to managing information, and more particularly to accessing information contained in XML documents.

Background technique

In recent years, there have been many database systems that allow the storage and query of Extensible Markup Language data ("XML data"). Although there are many evolving standards for XML queries, all include some XPath variant. However, database systems are usually not the optimal system for processing XPath queries, and there are still many requirements for the query performance of database systems. In the specific case where an XML schema definition is available, the structure and data types used in the XML instance document are known. However, there are no efficient techniques for querying using XPath where XML schema definitions are not available and the document to be found does not conform to any schema.

Some database systems may employ an ad-hoc mechanism to satisfy XPath queries against documents (where the document schema is unknown). For example, a database system may satisfy an XPath query by performing a full scan of all documents. While a full scan of all documents could be used to satisfy all XPath queries, the implementation would be very slow due to the lack of indexes.

Another way to satisfy XPath queries involves the use of literal keywords. In particular, many database systems support text indexing, and these database systems can be used to satisfy certain XPaths. However, this technique can only satisfy a small subset of XPath queries. Therefore, there is no effective indexing technique available for processing various XPath queries in existing database systems.

The approaches described in this section are approaches that could be pursued and not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, the approaches described in this section should not be admitted to be prior art merely by virtue of their inclusion in this section.

Description of drawings

The present invention is described by way of example and not limitation in the accompanying drawings, in which like reference numerals refer to similar elements, in which:

Figure 1 is a flowchart showing the steps for updating an XML index based on a new XML document; and

Figure 2 is a block diagram of a system in which the techniques described herein may be implemented.

Detailed ways

In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It may be evident, however, that the invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to avoid unnecessarily obscuring the present invention.

Function overview

Provides a mechanism for indexing path, value, and order (order) information in an XML document. This mechanism can be used regardless of the data structure ("base structure") and format used to store the actual XML data. For example, the actual XML data can exist in the database in any form such as CLOB (a character LOB that stores actual XML text), O-R (an object-relational structure form in XML schema), or a BLOB (a binary LOB that stores some binary form of XML) inside or outside the structure.

The technique described here involves using a set of structures that collectively comprise an index for accessing XML data. According to one embodiment, the index (referred to herein as "XML data") includes three logical structures: a path index, an order index, and a value index. In one embodiment, all three of these logical structures exist in a single table, referred to here as PATH_TABLE.

The most commonly used parts of the XPath query language include value-based determination and navigation (parent-child derivation) access. As will be described in more detail below, XML indexes can be used to efficiently satisfy these access methods by tracking path, value, and order information. In addition, based on the embodiment of how the XML index is implemented, the use of the XML index can produce one or more of the following benefits: (1) improve search performance for XPath-based queries, including path matching and value predicates; (2) ) handles fragment extraction where the fragment is identified by an XPath expression; (3) datatype awareness with respect to value determination, where appropriate XML Schema definitions exist; (4) supports evolution of XML Schema and The ability to index XML; (5) handle multiple types of XPath expressions (including sub-axis and descendant axes), as well as equality and range determination; (6) users control the index by including or excluding path groups or namespaces specified in the index The ability to group paths, which is especially useful in document-oriented situations where formatting-related flags are omitted from the index; (7) allows customization of the actual text values stored in the index, e.g., removing spaces ( whitespace), case-insensitive (case-insensitive); (8) a large number of loaded indexes and good performance that supports parallel index creation.

XML document instance

For explanatory purposes, examples are given below with reference to the following two XML documents:

po1.xml

<PurchaseOrder>

<Reference>SBELL-2002100912333601PDT</Reference>

<Actions>

<Action>

<User>SVOLLMAN</User>

</Action>

</Actions>

....

</PurchaseOrder>

po2.xml

<PurchaseOrder>

<Reference>ABEL-20021127121040897PST</Reference>

<Actions>

<Action>

<User>ZLOTKEY</User>

</Action>

<Action>

<User>KING</User>

</Action>

</Actions>

....

</PurchaseOrder>

As noted above, po1.xml and po2.xml are just two instances of XML documents. The techniques described herein are not limited to XML documents having any particular type, structure, or content. Examples of how such documents are indexed and accessed according to various embodiments of the invention are given below.

XML index

According to one embodiment, the XML index is a domain index that improves query performance including XPath-based determination and/or XPath-based fragment extraction. For example, XML indexes can be built on schemaless XMLType columns (column, column) stored as CLOB or structured storage, as well as schema-based XML. In one embodiment, the XML index is a logical index generated through the cooperative use of path indexes, value indexes, and order indexes.

Path indexes provide a mechanism for finding fragments based on simple (navigation) path expressions. Value indexes provide lookups based on value equality or ranges. There may be multiple secondary value indexes - one for each data type. An order index associates hierarchical order information with the nodes of the index. Sequence indexes are used to determine parent-child, grandparent, and sibling relationships between XML nodes.

When a user submits a query containing XPath (as a predicate or fragment identifier), the XPath statement is decomposed into a SQL query to access the XML index table. The generated queries typically perform a set of lookups subject to path, value, and order constraints, and combine their results appropriately.

path table

According to one embodiment, a logical XML index includes a PATH table and a set of secondary indexes. As mentioned above, each index XML document can include many index nodes. The PATH table contains one row for each inode. For each index node, a row of that node's PATH table contains various information related to that node.

According to one embodiment, the information contained in the PATH table includes: (1) the PATHID indicating the path to the node; (2) "location data" used to locate the fragment data of the node within the base structure; and (3) "Hierarchy data" indicating the position of the node in the structural hierarchy of the XML document containing the node. Optionally, for those nodes associated with values, the PATH table may also contain value information. Each type of information is described in more detail below.

path

The XML document structure establishes parent-child relationships between nodes within the XML document. The "path" of a node in an XML document reflects a series of parent-child links starting from a "root" node to a particular node. For example, the path to the "User" node in po2.xml is /PurchaseOrder/Actions/Action/User, this is because the "User" node is a child node of the "Action" node, and the "Action" node is a child node of the "Actions" node child nodes, and the "Actions" node is a child node of the "PurchaseOrder" node.

A set of XML documents indexed by an XML index is referred to herein as an "indexed XML document." According to one embodiment, XML indexes can be built on all paths in all indexed XML documents or a subset of paths in indexed XML documents. Techniques for specifying which path to index are described below. The set of paths indexed by a particular XML index is referred to herein as an "indexed XML path".

The path ID above is only a preferred embodiment of the present invention, and is not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention. The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

According to one embodiment, each index XML path is assigned a unique path identifier (ID). For example, paths in po1.xml and po2.xml may be assigned the path IDs shown in the table below:

route ID path 1 /PurchaseOrder 2 /PurchaseOrder/Reference 3 /PurchaseOrder/Actions 4 /PurchaseOrder/Actions/Action 5 /PurchaseOrder/Actions/Action/User

Various techniques may be used to identify paths and assign path IDs to paths. For example, a user may explicitly enumerate paths, and assign corresponding path IDs to paths so identified. Optionally, the database server can parse each XML document into a document that is added to the set of indexed XML documents. During the resolution operation, the database server identifies any paths that have not been assigned a path ID, and automatically assigns new path IDs to these paths. The mapping of route IDs to routes can be stored in the database in various ways. According to one embodiment, the mapping of route IDs to routes is stored as metadata independently of the XML index itself.

According to one embodiment, the same access structure is used for XML documents conforming to different schemas. Since indexed XML documents may conform to different schemas, each XML document will generally only contain a subset of paths to which a path ID is assigned.

location data

The position data associated with a node indicates where in the basic structure the XML document containing the node exists. Therefore, the nature of location data varies from implementation to implementation, based on the nature of the underlying structure. Depending on how the actual XML document is stored, the location data may also include logical pointers or locators into the XML document. Logical pointers can be used to extract fragments related to nodes identified by XPath.

For purposes of explanation, it will be assumed that: (1) the base structure is a table in a relational database; and (2) each indexed XML document is stored in a corresponding row of the base table. In such a context, the node's location data may include, for example, (1) the ID (rowid) of the row in the base table in which the XML document containing the node is stored, and (2) a locator, in Quick access to fragment data corresponding to nodes is provided within the XML document.

Hierarchical data

A row of the PATH table for a node also includes information indicating where the node exists in the hierarchical structure of the XML document containing the node. Here, such hierarchical information is called "OrderKey" of a node.

According to one embodiment, Dewey type values are used to represent hierarchical order information. Specifically, in one embodiment, the sequence key of a node is created by adding a value to the sequence key of the node's direct parent node, wherein the added value represents the position of the specific child node among the child nodes of the parent node.

For example, assume that a particular node D is a child of node C, where node C is a child of node B, which is in turn a child of node A. Assume further that node D has the order key 1.2.4.3. The "3" at the end in the sequence key indicates that node D is the third child of its parent node C. Similarly, "4" indicates that node C is the fourth child of node B. "2" indicates that node B is the second child of node A. The leading "1" indicates that node A is the root node (ie, has no parent).

As described above, the ordinal key of the child node can be easily created by adding a value corresponding to the number of child nodes to the ordinal key of the parent node. Similarly, the ordinal key of the parent node can be easily derived from the ordinal key of the child node by removing the trailing digits in the ordinal key of the child node.

According to one embodiment, the composite number represented by each ordinal key is converted into a byte comparable value, such that a mathematical comparison between two ordinal keys represents the corresponding value of the ordinal key in the structural hierarchy of the XML document. The relative position of the node.

For example, in the hierarchical structure of an XML document, the node associated with the sequence key 1.2.7.7 precedes the node associated with the sequence key 1.3.1. Thus, the database server uses a conversion mechanism that converts the sequence key 1.2.7.7 to a first value and converts the sequence key 1.3.1 to a second value, where the first value is less than the second value. By comparing the first value with the second value, the database server can easily determine that the node associated with the first value precedes the node associated with the second value. A variety of transformation techniques can be used to achieve this result, and the invention is not limited to any particular transformation technique.

value information

Some nodes in the index document may be attribute nodes or nodes corresponding to simple elements. According to one embodiment, for attribute nodes and simple elements, the rows of the PATH table also store the actual values of the attributes and elements. For example, such a value could be stored in a "value column" in the PATH table. The secondary "value index" built on the value column will be described in detail below.

Example of PATH table

According to one embodiment, the PATH table includes columns defined as described in the following table:

column name type of data describe PATHID (path ID) RAW(8) The ID of the path token. Each distinct path (eg, /a/b/c) is assigned a unique ID by the system. RID (row ID) UROWD/ROWID The row ID of the row in the base table. ORDER KEY (order key) RAW(100) The Dewey instruction of the node, for example, 3.21.5 means the 5th child node of the 3rd child node of the root node and the 21st child node of the root node. LOCATOR (locator) RAW(100) Information corresponding to the start position of the fragment. This information is used during fragment extraction. VALUE (value) RAW(2000)/BLOB The value of the node in the case of attributes and simple elements. It is up to the user to specify the type (and the size of the RAW column)

As mentioned above, PATHID is a number assigned to a node and uniquely represents the fully expanded path to the node. The ORDER KEY is a systematic representation of the DEWEY sequence number associated with the node. According to one embodiment, the internal representation of the order key also preserves the document order.

The VALUE column stores valid text values for simple element (ie, no child elements) nodes and attribute nodes. According to one embodiment, adjacent text nodes are joined by links. As will be described in more detail below, mechanisms are provided that allow the user to customize the valid text values stored in the VALUE column by specifying options during index creation, for example, the behavior of mixed text, whitespace, case sensitivity, etc. can be customized. Users can store VALUE columns in a variety of formats including bounded RAW columns or BLOBs. If the user has selected bounded storage, any overflow during index creation will be flagged as an error.

The following table is an example of a PATH table (1) having the above-mentioned columns, and (2) consisting of entries for po1.xml and po2.xml. Specifically, each row of the PATH table corresponds to an index node of po1.xml or po2.xml. In this example, assume that po1.xml and po2.xml are stored in rows R1 and R2 of the base table, respectively.

Formed PATH table

line ID route ID Resource ID (Rid) sequence key locator value 1 1 R1 1 2 2 R1 1.1 SBELL-2002100912333601PDT 3 3 R1 1.2 4 4 R1 1.2.1 5 5 R1 1.2.1.1 SVOLLMAN 6 1 R2 1 7 2 R2 1.1 ABEL-20021127121040897PST 8 3 R2 1.2 9 4 R2 1.2.1 10 5 R2 1.2.1.1 ZLOTKEY 11 4 R2 1.2.2 12 5 R2 1.2.2.1 KING

In this example, the row ID column stores a unique identifier for each row of the PATH table. Depending on the database system in which the PATH table is created, the row ID column may be an implied column. For example, a row's disk location can be used as a unique identifier for the row. As will be described in detail below, secondary order indexes and value indexes use PATH table row ID values to locate rows in the PATH table.

In the above embodiment, the PATHID, ORDERKEY, and VALUE of a node are all included in a single table. In an alternative embodiment, separate tables may be used to map PATHID, ORDERKEY, and VALUE information to corresponding location data (eg, base table resource identifier (Rid) and locator).

secondary index

The PATH table includes information needed to locate XML documents or XML fragments, which can satisfy a wide range of queries. However, without secondary access structures, using the PATH table to satisfy such queries would often require a full scan of the PATH table. Thus, according to one embodiment, multiple secondary indexes are created by the database server to speed up queries that either (1) perform path finding and/or (2) identify order-based relationships. According to one embodiment, the following secondary index is created on the PATH table.

● PATHID_NDEX on (pathid, rid)

● ORDERKEY_INDEX on (rid, order_key)

●VALUE INDEXES

● PARENT_ORDERKEY_INDEX on (rid,

SYS_DEWEY_PARENT(order_key))

PATHID_INDEX (path ID index)

PATHID_NDEX is established on the path ID and resource identifier columns of the PATH table.

Thus, entries in PATHID_INDEX are of the form (key value, row ID), where key value is a compound value representing a particular path ID/resource identifier combination, and row ID identifies a specific row of the PATH table.

When (1) the base table row and (2) the node's path ID are known, PATHID_INDEX can be used to quickly locate the node's row in the PATH table. For example, based on the key value "3.R1", the PATHID_INDEX may be traversed to find entries related to the key value "3.R1". Assuming the PATH table is structured as described above, the index entry has a row ID with a value of 3. The row ID whose value is 3 points to the third row of the PATH table, which is the row of the node related to the path ID3 and the resource identifier R1.

ORDERKEY_INDEX (order key_index)

ORDERKEY_INDEX is established on the resource identification and order key columns of the PATH table. Thus, an entry in ORDERKEY_INDEX is of the form (key value, row ID), where key value is a composite value representing a particular resource ID/order key combination, and row ID identifies a specific row of the PATH table.

When (1) the base table row and (2) the order key of the node are known, ORDERKEY_INDEX can be used to quickly locate the node's row in the PATH table. For example, based on the key value "R1.'1.2, the ORDERKEY_INDEX may be traversed to find entries related to the key value "R1.'1.2. Assuming the PATH table is structured as described above, the index entry will have a row ID with a value of 3. A row ID with a value of 3 points to the third row of the PATH table, which is the row of the node associated with the sequence key 1.2 and the resource identifier R1.

value index

Just as you can use PATHID_INDEX to speed up queries based on path lookups, you can speed up queries based on value lookups by building an index on the value column of the PATH table. However, the value column of the PATH table can hold values of multiple data types. Therefore, according to one embodiment, a separate value index is established for each data type stored in the value column. So, in an implementation where value columns hold strings, numbers, and timestamps, the following value (secondary) indexes are also created:

●STRING_INDEX on

SYS_XMLVALUE_TO_STRING(value)

●NUMBER_INDEX on

SYS_XMLVALUE_TO_NUMBER(value)

●TIMESTAMP_INDEX on

SYS_XMLVALUE_TO_TIMESTAMP(value)

These value indexes are used to perform data type based comparisons (equalities and ranges). For example, NUMBER value indexes are used to handle number-based comparisons in user XPath. For example, an entry in NUMBER_INDEX may be in the form of (number, row ID), where the row ID points to the row of the node in the PATH table associated with the value of "number". Similarly, entries in STRING_INDEX may have the form (string, row ID) and entries in TIMESTAMP_INDEX may have the form (timestamp, row ID).

The format of the value in the PATH table may not correspond to the form of the data type itself. Therefore, when using a value index, the database server can call a conversion function to convert the value bytes from the storage format to the specified data type. Additionally, the database server applies any necessary transformations, as will be described below. According to one embodiment, the conversion function is performed on RAW values and BLOB values, and returns NULL when conversion is not possible.

The default is to create a value index when creating an XML index. However, users can cancel the creation of one or more numeric indexes based on knowledge of the query workload. For example, NUMBER and TIMESTAMP value indexes can be avoided if all XPath decisions involve only string comparisons.

PARENT_ORDERKEY_INDEX

According to one embodiment, the secondary index group established on the PATH table includes PARENT_ORDERKEY_INDEX. Similar to the ORDER_KEY index, the PARENT_ORDERKEY_INDEX is built on the resource identifier and order key columns of the PATH table. Thus, an index entry for PARENT_ORDERKEY_INDEX has the form (key value, row ID), where key value is a compound value corresponding to a particular resource ID/order key combination. However, unlike an ORDER_KEY index, the row ID in a PARENT_ORDERKEY_INDEX entry does not point to a row of the PATH table with a particular resource ID/order key combination. Instead, the row ID of each PARENT_ORDERKEY_INDEX entry points to a row in the PATH table of the node that is the immediate parent of the node associated with the resource ID/order key combination.

For example, in the PATH table constructed above, the resource ID/sequence key combination "R1.'1.2" corresponds to the node in row 3 of the PATH table. The immediate parent node of the node in row 3 of the PATH table is defined by the The node represented by row 1. Thus, the PARENT_ORDERKEY_INDEX entry associated with "R1.'1.2 has a row ID pointing to row 1 of the PATH table.

Create an XML index

According to one embodiment, an XML index is created within the database in response to an index creation command received by the database server. For explanation purposes, the creation of an XML index is described in the context of the XML document to be indexed will be stored in the XML Type column of a relational table.

For example, assume that the basic structure is a table stylesheet_tab that stores stylesheets as XML Type identified by the ID column. For example, the following command can be used to create the table:

CREATE TABLE stylesheet_tab(id number, stylesheet XMLType);

An XML index can be created on the stylesheet column of stylesheet_tab to speed up queries involving XPath-based fragment retrieval and XPath determination. According to one embodiment, the following command can be used to create such an XML index:

CREATE INDEX ss_tab_xmli ON stylesheet_tab(stylesheet)

INDEXTYPE IS XML INDEX;

The following command is an example of how to create an XML index on a schema-based XML type:

CREATE TABLE purchaseorder OF XMLType

XMLSchema

http://xmlns.oracle.com/xdb/documentation/purchaseOrder.xsd″

ELEMENT "PurchaseOrder";

CREATE INDEX purchaseorder_xmli ON purchaseorder(object_value)

INDEXTYPE IS XML INDEX;

The above commands are merely examples of commands that can be submitted to the database server to cause the database server to create an XML index. The techniques described here are not limited to any form or syntax for specifying index creation.

According to one embodiment, the index creation command includes parameters that allow the user to specify various properties of the XML index, such as:

○ Paths included in or excluded from an indexed path group

○ The name of the PATH table and secondary index

○ Storage options for the PATH table and secondary indexes (for example, whether to store the PATH table as a partitioned table, Index Organized Table, etc.)

○ Rules for processing values

○ the column type of the value column (for example, RAW or BLOB)

For example, rules for handling values may specify: whether to treat values as case-sensitive, whether to normalize values (and if so, how to perform normalization), and how to handle values for mixed content nodes (nodes that have a value and child nodes). With respect to mixed content nodes, for example, the rule may specify values associated with mixed content nodes that should be ignored, concatenated, or treated specially. This is just an example of value handling rules that can be specified by the user. The set of available rules can vary from implementation to implementation and can further vary based on the value types involved.

When a user creates an XML index, the following PATH table and secondary indexes are automatically created. The default is based on the name of the XML index, and the name of the secondary index and PATH table is generated by the system. However, users can explicitly specify the names of these objects.

The default is to get the storage options for PATH tables and secondary indexes from the storage properties of the base table on which the XML index is created. However, the user can also explicitly specify storage properties for these objects.

The following example shows how to create a number index in a separate table space of the PATH table.

CREATE INDEX POIndex ON purchaseOrder

NDEXTYPE IS XML INDEX

PARAMETERS'PATHS(/PurchaseOrder/LineItems//*, /PurchaseOrder/LineItems/LineItem/@ItemNumber)

PATH TABLE POIndex_path_table tablespace

tab_tbs

VALUE STORE AS RAW(50)

NUMBER INDEX POIndex_num_idx tablespace

idx_tbs'

The user selects the path for the index

According to one embodiment, a mechanism is provided by which a user can specify rules for determining which XML paths an XML index will index. Specifically, a user may register rules that explicitly include certain XML paths and/or rules that explicitly exclude certain XML paths.

According to one embodiment, when a user creates an XML index, the default is to index all nodes in the base document (ie, there are rows in the PATH table corresponding to all nodes in the document). However, users can explicitly specify groups of nodes (subtrees) to be indexed, thereby omitting the remaining nodes in the PATH table. This is typically used to exclude fragments that are known to be useless from a query point of view. By reducing the number of index nodes, the space utilization and management efficiency of XML indexes can be improved.

According to one embodiment, the initial registration of rules may occur when the XML index is created. For example, suppose the documents to be indexed are stored in the purchaseOrder (order order) table. If the user wants to index all Lineitem elements and their child nodes, as well as the Order Reference and Requester, the following Create Index DDL can be issued:

CREATE INDEX POIndex1 ON purchaseOrder

INDEXTYPE IS XML INDEX

    PARAMETERS'PATHS(/PurchaseOrder/LineItems//*,

/PurchaseOrder/Reference,

/PurchaseOrder/Requestor)

PATH TABLE POIndex_path_table’

In this example, POIndex_path_table represents the name of the table used by the domain index to store index data. In the preceding examples, the rules explicitly include specific paths. All paths not explicitly included by the rule will be excluded from the index. The rule /PurchaseOrder/LineItems//* includes the wildcard "*". Thus, the rule explicitly includes the path /PurchaseOrder/LineItems and paths to all nodes originating from the path /PurchaseOrder/LineItems. This is just one example of how wildcards can be used in rules. According to one embodiment, the routing rules mechanism supports wildcards in many cases. For example, the rule /nodex/*/nodey/nodez selects all paths that (1) originate in /nodex/ and (2) end in /nodey/nodez, regardless of paths between nodex and nodey/nodez.

Users can also specify rules that explicitly exclude paths. For example, to index all paths of documents except the Lineitem description and the purchaseOrder action, use the following Create Index DDL to create the index:

CREATE INDEX POIndex2 ON purchaseOrder

INDEXTYPE IS XML INDEX PARAMETERS‘PATHS EXCLUDE

/PurchaseOrder/LineItems/LineItem/Description,

/PurchaseOrder/Actions)

PATH TABLE POIndex_path_table2'

Add a document to an indexed document group

When a new XML document needs to be indexed, path, order, and value information is collected and stored in the XML index. According to one embodiment, when an XML document is added to a repository of indexed XML documents, the new XML document is parsed to identify paths to nodes contained therein. Once the paths of the nodes in the new XML document are identified, the database server determines which nodes to include in the new XML document for indexing. The database server then updates the XML index based on each of these nodes.

Referring to FIG. 1 , it shows a flowchart of how to process a new XML document according to an embodiment of the present invention. In FIG. 1, steps 102 and 108 define a loop for processing each node in the new XML document. Specifically, in step 102, a node that has not been processed before is selected. During the first iteration, the first node selected for processing will be the root node of the new XML document.

At step 104, the database server determines the path of the currently selected node. At step 106, based on the path, the database server determines whether to index the currently selected node. In particular, when the user has specified a subset of paths to be indexed, index entries are only added for those nodes corresponding to the specified subset of paths. According to one embodiment, step 106 comprises matching the paths related to the current node with routing rules to check whether the current node should be indexed. If (1) the user has registered rules indicating which paths should be included, and (2) the paths associated with the current node do not match any paths specified by the user, then a subtree (fragment) rooted at that node will be Omitted from the index. On the other hand, if (1) the rule specifies which paths are to be excluded from the index, and (2) nodes that match any path specified by the user are excluded, then the segment rooted at that node is removed from the index omitted. For example, a finite sequential machine can be used to perform matching operations.

If at step 106 it is determined that the selected node is not relevant to the path to be indexed, then control passes to step 108 . At step 108, the database server determines whether the new XML document still has nodes to be processed. If the new XML document has no nodes to be processed, then the process of updating the XML index is done. Otherwise, if the new XML document still has nodes to be processed, control returns to step 102 and other nodes are processed.

If it is determined in step 106 that the current node is to be indexed, the segment with this node as the root node is added to the index. Additionally, all its ancestors (element nodes up to the root node) are added to the index. Finally, any namespace attributes within the ancestor element nodes are also added to the index.

In FIG. 1 , more specifically illustrating the operation of interrupt processing a node to be indexed, in step 110 it is determined whether the path associated with the current node is assigned a PATHID. In the event that a suitable path does not exist in a previously indexed XML document, the path may not have been assigned to PATHID. In this case, control passes to step 112 to assign a PATHID to the path. Afterwards, store the new PATHID-to-path mapping in the database.

At step 114, a row including information about the current node is added to the PATH table. At step 116, the PATHID, ORDERKEY, and PARENT_ORDERKEY indexes are updated with the current node's entries. As mentioned above, the PATHID and ORDERKEY entries will point to the new row for the current node, while the PARENT_ORDERKEY entry will point to the row of the PATH table for the current node's parent node.

At step 118, it is determined whether the current node is associated with a value. If the current node is not associated with a value, then control returns to step 108 . If the current node is associated with a value, and a value index has been created for the data type of the value, then in step 120, an index entry is added to the value index associated with that particular data type. Thereafter, control returns to step 108 .

According to one embodiment, even if a node is related to a path that is not indexed, the node is still indexed if it is an ancestor node of any node being indexed. Thus, even if the user specifies that only paths matching /a/b/c/* should be included, nodes related to the paths /a, /a/b, and /a/b/c will still be indexed as long as they are associated with the pattern /a/b/c/* Ancestors of any node associated with the matched path.

Change XML index

According to one embodiment, a mechanism is provided for altering XML index properties after the index has been created. For example, a post-creation alter of an XML index may be performed in response to a statement that alters the index.

An important use of the ALTER INDEX statement for XML indexes is to add or remove index paths. According to one embodiment, new paths can be added to the index via the following Alter Index DDL:

ALTER INDEX POIndex

PARAMETERS'PATHS(/PurchaseOrder/Reference,

/PurchaseOrder/Actions/Action//*)’

This DDL command indexes all Order Order References and all child nodes of the Action element, in case the index does not already index all child nodes of the Order Order Reference and Action element. Similarly, the following DDL removes paths from the index if they are already indexed:

ALTER INDEX POIndex

PARAMETERS 'PATHS EXCLUDE (/PurchaseOrder/Reference, /PurchaseOrder/Actions/Action//*)'

As shown in the following example, the Alter Index Rename DDL (Alter Index Rename DDL) allows the user to change the index name without explicitly deleting and creating the index name:

ALTER INDEX POIndex RENAME PONewIndex

Determine if XML indexes can be used

At query time, an XML index can be used to answer a query if the query XPath can be statically determined to be a subset of the user-specified XPath (and thus guaranteed to be in that index). If the subset relationship cannot be determined when the query is edited, the XML index cannot be used to satisfy the query.

For example, create an XML index POIndex1 with the following statement:

CREATE INDEX POIndex1 ON purchaseOrder

INDEXTYPE IS XML INDEX

PARAMETERS'PATHS(/PurchaseOrder/LineItems//*,

/PurchaseOrder/Reference,

/PurchaseOrder/Requestor)

PATH TABLE POIndex_path_table’

XML indexes can be used to answer queries XPath/PurchaseOrder/LineItem/Description. However, the XML index cannot be used to answer the query XPATH//Description due to the presence of the <Description> element at a different path than /PurchaseOrder/LineItems.

Use XML indexes to answer XPath queries

XML indexes can be used to satisfy XPath queries by decomposing XPath indexes into simple value-based paths and predicates. Turn the final decomposed part into a SQL query on the index PATH_TABLE. According to one embodiment, the input to the index access method is a compound expression comprising one or more of the following expressions:

● Simple (navigation) path expressions, eg, /a/b

● Simple value expressions, for example, /a/b/c > 50

● Structural combination (ie, hierarchical relationship) between expressions, for example, express the XPath expression /a/b[c>50] as (/a/b)PARENT-OF(/a/b/c>50 )

Assuming a query with a simple predicate, e.g., /a/b/c=foo, such a query can be performed against the following PATH table:

SELECT DISTINCT rid FROM path_table

WHERE pathid=:1 AND xmlvalue_to_string(value)='foo';

Qualify the ID of the path /a/b/c as variable 1. There are several execution schemes for this query. According to one embodiment, the query optimizer adopts the best execution plan based on cost. The database server can (1) use a secondary index on path ID, (2) use a secondary index on xmlvalue_to_string(value), or (3) use both, and the bitmap and result.

Assume a query that specifies a fragment lookup, for example, XPath /a/b/c. Such a query can be performed against the PATH table using the following statement:

SELECT rid FROM path_table WHERE pathid=:1 ORDER BY order_key;

The ID of the path /a/b/c is limited to variable 1. A query in document order returns matching results. Concatenates all fragments corresponding to a single document, if desired.

Assume a query that specifies segment lookup based on a simple predicate, eg, /a/b[c=foo]. The normalized representation of the input XPath is (/a/b)PARENT-OF(/a/b/c=foo). The following query can be used to find matches for the path /a/b as well as matches for the simple predicate (/a/b/c=foo).

SELECT p1.rid, p1.offset FROM path_table p1, path_table p2

WHERE p1.pathid＝:1 AND p2.pathid＝:2

AND xmlvalue_to_string(p2.value)='foo'

AND SYS_DEWEY_PARENT(p1.order_key)＝p2.order_key

ORDER BY p1.rid, p1.offset;

The results are then combined using a structural join operator (which is represented using Dewey order keys). Qualify the IDs of paths /a/b and /a/b/c as variables 1 and 2. According to one embodiment, the cost-based optimizer employs the best execution plan among several possible execution plans.

XML indexes can also be used to perform data type aware operations. There are various mechanisms for attaching data type information to XPath decisions. For example:

● Use XML Schema. If the base table column has an associated XML schema, the user XPath is type-checked against the XML schema so that the appropriate data type is associated with the expression.

● Explicit type coercion. XPath provides operators for explicit type coercion.

● Implicit type coercion. XPath defines some implicitly typed evaluation rules. For example, if the RHS of a comparison operator is NUMBER, the LHS is implicitly coerced to NUMBER.

According to one embodiment, in all these cases, the input to the XML index access method is an XPath expression associated with data type information. The data type information is used in the generated SQL query to ensure that the appropriate value index is selected. For example, the XPath for type checking is as follows:

SYS_XMLVALUE_TO_NUMBER(/a/b/c)＞10.567

The results in the following query are compared against the PATH table indexed with NUMBER values:

SELECT DISTINCT rid FROM path_table

WHERE pathid＝:1 AND sys_xmlvalue_to_number(value)＞10.567;

Using XML indexes, as described here, yields several advantages, including: multiple sets of XPaths can be efficiently estimated; XPaths involving datatype-aware comparisons can be satisfied; fragments can be efficiently extracted from raw XML documents; users can choose to only Indexing a subset of paths avoids index inflation (bloating); the index value can be customized based on application needs; the ability to index even non-schema XML documents can meet the query requirements of various types of users; it enables them to use All its XML documents are stored in Oracle regardless of query performance.

grammar

Embodiments have been described in the context where the database server creates and maintains XML indexes in response to commands received by the database server. The command must conform to a language understood by the database server. According to one embodiment of the present invention, the syntax for various DDL commands involving XML indexes is as follows:

create index

grammar

CREATE INDEX<index_name>ON[<schema>.]

<table_name>(<column_name>)

INDEXTYPE IS[<schema>.]XMLINDEX

[LOCAL]

[PARALLEL]

[PARAMETERS'<parameter_clause>'];

example

Create index xmldoc_idx on xmldoc_tab(xmldoc)indextype is

XMLINDEX

Parameters'PATHS(/a/b/c, //e),

PATH TABLE xmldoc_idx_pathtab';

According to one embodiment, the domain index is a split of the parent XML table. If the XML table is not partitioned, neither are the domain indexes. PATH TABLE and its sub-indexes are also equally divided into XML tables.

Syntax of the PARAMETERS clause:

<parameters_clause>::=<parameter_clause>[, <parameters_clause>]

<parameter_clause>::=[<paths_clause>|

<path_table_clause>|

<pathid_index_clause>|

<orderkey_index_clause>|

<value_index_clause>]

<paths_clause>::=PATHS([<path_list_clause>|

<namespaces_clause>]*)

<path_list_clause>::＝{<include_list_clause>|

<exclude_list_clause>}

<include_list_clause>::=<xpath_list_clause>

<exclude_list_clause>::＝EXCLUDE(<xpath_list_clause>)

<xpath_list_clause>::=<xpath>[,<xpath_list_clause>]

<namespaces_clause>::＝NAMESPACES(<namespace_list_clause>)

<namespace_list_clause>::=<namespace>[,

<namespace_list_clause>]

<path_table_clause>::=PATH TABLE[ <identifier> ]

[(< segment attributes clause >

<table_properties> )]

<pathid_index_clause>::=PATH<index_parameters>

<orderkey_index_clause>::=ORDER KEY<index_parameters>

[PARENT<index_parameters>]

<value_index_clause>::=VALUE STORE AS<value_type>

[<value_idx_clause>]

<value_type>::＝{RAW[(< integral number >)]

BLOB}

<value_idx_clause>::=<value_idx1_clause>[,

<value_idx_clause>]

<value_idx_1_clause>::＝[<string_parameters>|NUMBER|

TIMESTAMP]

<index_parameters>

<string_parameters>::=STRING[<string_parametersl>[,

<string_parameters>]]

<string_parametersl>::＝NORMALIZED|

IGNORE_MIXED_TEXT|CASE_INSENSITIVE

<index_parameters>::=[INDEX[ <identifier> ][(<index_attributes>)]]

According to one embodiment, the PARAMENTERS clause is used to specify:

• Names and physical parameters (tablespaces, etc.) for path tables and secondary indexes. All six indexes on PATH TABLE are created even if not explicitly specified.

o If the type of column VALUE is explicitly specified as BLOB, store the value out-of-line in the BLOB fragment. Otherwise, store the value inline as RAW data. RAW's <size> is exactly an integer.

○The properties of the STRING value are:

■ NORMALIZED when all leading and trailing spaces of the string are to be stripped

■ IGNORE_MIXED_TEX stores value as NULL in case of mixed text

■ When converting all character strings to lowercase, for

CASE_INSENSITIVE

Note that the above is applied before storing the value into the VALUE column (and before creating the secondary index on PATHTABLE ).

• Groups of paths to indexes. Users can control index path groups by specifying:

o An explicit list of paths to the index. This can include wildcards and // axes. For example, /a/b/c, /d/*, /x//y

○ an explicit list of paths not to be indexed

delete index

grammar

DROP INDEX <index_name>;

example

Drop index xmldoc_idx;

use

Drops the XML index along with its components, the lower PATH TABLE, and its subordinate indexes.

change index

grammar

ALTER INDEX <index_name>

PARAMETERS'<parameter_clause>'|

RENAME<new_index_name>|

REBUILD[ONLINE][PARALLEL[DEGREE<degree>]]

|

MODIFY PARTITION<partition_name>

PARAMETERS'<parameter_clause>'|

RENAME PARTITION<partition_name>TO<new_partition_name>|

REBUILD PARTITION<partition_name>[ONLINE]

[PARALLEL[DEGREE

<degree>]]|

example

Alter index xmldoc_idx

      Parameters 'PATHS(/a/b/c, //e), PATH TABLE

xmldoc_idx_pathtab';

Alter index xmldoc_idx RENAME TO new_xmldoc_idx;

Alter index xmldoc_idx REBUILD;

Alter index xmldoc_idx MODIFY PARTITION p1

Parameters 'PATHS(/a/b/c, //e)';

Alter index xmldoc_idx RENAME PARTITION xmldoc_idxpart TOnew_xmldoc_idxpart;

Alter index xmldoc_idx REBUILD PARTITION xmldoc_idxpart;

hardware overview

FIG. 2 is a block diagram illustrating a computer system 200 on which an embodiment of the present invention may be implemented. Computer system 200 includes a bus 202 or other communication means for communicating information and a processor 204 coupled with bus 202 for processing information. Computer system 200 also includes a main memory 206 , such as a random access memory (RAM) or other dynamic storage device, coupled to bus 202 for storing information and instructions to be executed by processor 204 . Main memory 206 may also be used for storing temporary variables or other intermediate information during execution of instructions to be executed by processor 204 . Computer system 200 further includes a read only memory (ROM) 208 or other static storage device coupled to bus 202 for storing static information and instructions for processor 204 . A storage device 210, such as a magnetic or optical disk, is provided and connected to bus 202 for storing information and instructions.

Computer system 200 may be connected via bus 202 to a display 212, such as a cathode ray tube (CRT), for displaying information to a computer user. An input device 214 including alphanumeric and other keys is connected to bus 202 for communicating information and command selections to processor 204 . Another type of user input device is cursor control 216 , such as a mouse, trackball, or cursor direction keys, for communicating direction information and command selections to processor 204 and for controlling cursor movement on display 212 . The input device typically has two degrees of freedom in two axes, a first axis (eg, X-axis) and a second axis (eg, Y-axis), enabling the device to specify a position on a plane.

The present invention is directed to the use of computer system 200 for performing the techniques described herein. These techniques are implemented by computer system 200 in response to processor 204 executing one or more sequences of one or more instructions contained in main memory 206 , according to one embodiment of the invention. Such instructions may be read into main memory 206 from other computer-readable media, such as storage device 210 . Execution of the sequences of instructions contained in main memory 206 causes processor 204 to perform the process steps described herein. In alternative embodiments, hard-wired circuitry may be used in place of or in combination with software instructions to implement the invention. Thus, embodiments of the invention should not be limited to any specific combination of hardware circuitry and software.

The term "machine-readable medium" as used herein refers to any medium that participates in providing data to cause a machine to function in a specific manner. In an embodiment implemented using computer system 200, various machine-readable media are involved, for example, in providing instructions to processor 204 for execution. Such a medium may take many forms, including but not limited to, non-volatile media, volatile media, and transmission media. Non-volatile media include, for example, optical or magnetic disks, such as storage device 210 . Volatile media includes dynamic memory, such as main memory 206 . Transmission media include coaxial cables, copper wire, and fiber optics, including the wires that make up bus 202 . Transmission media can also take the form of acoustic or light waves, such as those generated during radio-wave and infrared data communications.

Common forms of computer readable media include, for example, floppy disks, floppy disks, hard disks, magnetic tape, or any other magnetic media, CD-ROMs, any other optical media, punched paper, paper tape, or any physical media with a pattern of holes, RAM, PROM, EPROM, FLASH-EPROM, or any other memory chips or cartridges, or carrier waves mentioned below, or any other medium readable by a computer.

Various forms of computer readable media may be involved in carrying one or more sequences of one or more instructions to processor 204 for execution. For example, the instructions may initially be carried on a disk in a remote computer. The remote computer can load the instructions into its dynamic memory and then send the instructions over a telephone line using a modem. A modem local to computer system 200 can receive the data on the telephone line and use an infrared transmitter to convert the data to an infrared signal. An infrared detector can receive the data carried in the infrared signal and appropriate circuitry can place the data on bus 202 . Bus 202 carries the data to main memory 206 , from which processor 204 retrieves and executes the instructions. The instructions received by main memory 206 can optionally be stored on storage device 210 either before or after execution of the instructions by processor 204 .

Computer system 200 also includes a communication interface 218 connected to bus 202 . A communication interface 218 , which provides bi-directional data communication, is connected to a network link 220 connected to a local area network 222 . For example, communication interface 218 may be an Integrated Services Digital Network (ISDN) card or a modem for providing a data communication connection to a corresponding type of telephone line. As another example, communication interface 218 may be a local area network (LAN) card for providing a data communication connection to a compatible local area network (LAN). Wireless links may also be used. In any such implementation, communication interface 218 sends and receives electrical, electromagnetic, and optical signals that carry digital data streams representing various types of information.

Network link 220 may generally provide data communication to other data devices through one or more networks. For example, network link 220 may connect to host computer 224 through local area network 222 or to data equipment operated by Internet Service Provider (ISP) 226 . ISP 226 in turn provides data communication services through a global packet data communication network currently known as the "Internet" 228 . Local area network 222 and Internet 228 both use electrical, electromagnetic or optical signals that carry digital data streams. The signals through the various networks and the signals on network link 220 and the signals through communication interface 218, both carrying digital data to and from computer system 200, are exemplary forms of carrier waves carrying the information.

Computer system 200 is capable of sending messages and receiving data (including program code) over a network, network link 220 , and communication interface 218 . In the example of the Internet, server 230 may transmit the requested program code for the application through Internet 228 , ISP 226 , local area network 222 , and communication interface 218 .

The received code may be executed by processor 204 as it is received, and/or stored in storage device 210 or other non-volatile medium for subsequent execution. In this manner, computer system 200 can obtain the application code in the form of a carrier wave.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. For those skilled in the art, the present invention may have various modifications and changes. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included within the protection scope of the present invention.

Claims (24)

1. method that is used for access from the information of XML document, described method comprises:

Identification is with indexed groups of nodes in XML document;

For with each node in the indexed described groups of nodes, the clauses and subclauses of described node are stored in the index, wherein, the described clauses and subclauses of given node comprise the locator data that is used to locate the XML content relevant with described given node, and in following at least one:

(a) ranked data is represented the classification position of described given node in comprising the described XML document of described given node; And

(b) path data is corresponding to the structure of the XML document by the comprising described specific node path to described given node; And

In response to request, use described index to locate information in the described XML document from the information of described XML document.

2. method according to claim 1, wherein, described index is implemented as relation table, and the step of carrying out each node clauses and subclauses of storage by the row of each node in the described groups of nodes of described relation table stored.

3. method according to claim 1, wherein, the relevant value of one or more nodes in described index stores and the described groups of nodes.

4. method according to claim 3, wherein, be stored in described value in the described index and comprise the value of numerous types of data, and described method also is included as every kind of step of setting up secondary index in two or more data types in the described numerous types of data.

5. method according to claim 1, wherein, the described locator data of described given node comprises first data that are used for the localization of XML document and second data that are used for the information that the location is relevant with described given node in described XML document.

6. method according to claim 1, wherein,

The clauses and subclauses of described given node comprise ranked data, and described ranked data is represented the classification position of described given node in comprising the described XML document of described given node; And

Described method also comprises based on described ranked data, sets up the secondary index that is used for storing entry in described index.

7. method according to claim 1, wherein,

The clauses and subclauses of described given node comprise path data, and described path data is corresponding to the structure of the XML document by the comprising described specific node path to described given node; And

Described method also comprises based on described path data, sets up the secondary index that is used for storing entry in described index.

8. method according to claim 1 also comprises based on the rating information relevant with the child node of described father node, sets up the secondary index that is used for storing entry for described father node in described index.

9. according to the described method of claim 1, wherein, identification may further comprise the steps the step of indexed groups of nodes:

Reception be used for determining should which path of index rule;

Determine and the path that the node in the indexed XML document is relevant; And

Be used for determining the described rule in which path of index based on (a), and (b) with the described path that the node in the indexed described XML document is relevant, discern which node of index.

10. method according to claim 9, wherein, described regular explicit identification will be included in the path in the described index.

11. method according to claim 9, wherein, described regular explicit identification will be by the path of getting rid of from described index.

12. method according to claim 4 comprises that also receiving indication will set up the user data of secondary value indexed data type to it.

13. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 1.

14. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 2.

15. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 3.

16. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 4.

17. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 5.

18. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 6.

19. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 7.

20. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 8.

21. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 9.

22. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 10.

23. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 11.

24. a computer-readable medium that carries one or more instruction sequences when described one or more instruction sequences are carried out by one or more processors, makes described one or more processor enforcement of rights require the method described in 12.