System and method for query processing and optimization for XML repositories

Claim 2

A query processing method for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising: extracting structural relationship sets from the schemes; comparing a query against the structural relationship sets to determine if the query is to be executed on the hierarchical documents; and optimizing the query processing by filtering documents from the plurality of hierarchical documents that will produce an empty result; wherein optimizing the query processing comprises maintaining an indexing structure for tree pattern matching; wherein, for each non-filtered document, the indexing structure comprises three indices: a value index that corresponds to a document content; a structure index that corresponds to a tree structure pattern of the non-filtered document; and a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein optimizing the query processing further comprises, for each non-filtered document: organizing the three indices as a trie; and querying the trie using tree pattern matching.

Claim 3

The query processing method of claim 1 , wherein optimizing the query processing further further comprises eliminating the documents that will produce an empty result.

Claim 4

The query processing method of claim 1 , wherein optimizing the query processing comprises removing redundant query constraints, and simplifying complex constraints, if any.

Claim 5

The query processing method of claim 3 , wherein optimizing the query processing comprises determining if a query constraint will always be true, and removing such constraint.

Claim 6

The query processing method of claim 3 , wherein optimizing the query processing further comprises simplifying complex query constraints into simpler query constraints.

Claim 7

The query processing method of claim 5 , further comprising: precomputing results for tree structure patterns of the non-filtered documents; converting the tree structure patterns into strings; storing the strings as part of the trie; storing the precomputed results corresponding to each string as part of the indexing structure; and optimizing the query processing by querying the indexing structure.

Claim 8

The query processing method of claim 6 , further comprising precomputing results for common tree structure patterns.

Claim 9

The query processing method of claim 7 , wherein precomputing results comprising converting the tree structure patterns into strings, and maintaining a result for each tree structure pattern.

Claim 10

The query processing method of claim 7 , wherein optimizing the query processing the documents comprise XML documents.

Claim 11

A query system for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising: a preprocessor comprising a relation set generator that computes structural relationship sets between elements and attributes of a schema, and an indexer that computes values and structure indices; and a query processor for performing a query and returning a result set, comprising: a query optimizer that builds an execution plan for a document; and a query executor that executes the execution plan; wherein the query processor compares the query against the structural relationship sets to determine if the query is to be executed on the documents; and wherein the query processor optimizes a query processing by filtering documents that will produce an empty result; wherein the query processor optimizes by using the indices instead of executing the query on the actual documents; wherein the query processor maintains an indexing structure for tree pattern matching; wherein, for each non-filtered document, the indexing structure comprises three indices: a value index that corresponds to a document content; a structure index that corresponds to a tree structure pattern of the non-filtered document; and a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further organizes the three indices as a trie; and queries the trie using tree pattern matching.

Claim 12

A query system for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising: a preprocessor comprising a relation set generator that computes structural relationship sets between elements and attributes of a schema, and an indexer that computes values and structure indices; and a query processor for performing a query and returning a result set, comprising: a query optimizer that builds an execution plan for a document; and a query executor that executes the execution plan; wherein the query processor compares the query against the structural relationship sets to determine if the query is to be executed on the documents; and wherein the query processor optimizes a query processing by filtering documents that will produce an empty result; wherein the query processor optimizes by using the indices instead of executing the query on the actual documents; wherein the query processor maintains an indexing structure for tree pattern matching; wherein, for each non-filtered document, the indexing structure comprises three indices: a value index that corresponds to a document content; a structure index that corresponds to a tree structure pattern of the non-filtered document; and a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further organizes the three indices as a trie; and queries the trie using tree pattern matching.

Claim 13

The query system of claim 10 , wherein the query processor further comprises a result consolidator.

Claim 14

The query system of claim 11 , wherein the query processor further comprises: a schema extractor for extracting structural relationship sets from the schemas; and an indexing system.

Claim 15

The query system of claim 10 , wherein the query processor optimizes the query processing by determining if the query to be executed on the hierarchical documents will produce an empty result, and eliminating all the documents conforming to the common schema that will produce an empty result.

Claim 16

The query system of claim 10 , wherein the query processor further optimizes the query processing by removing redundant query constraints, and by simplifying complex constraints, if any.

Claim 17

The query system of claim 12 , wherein the preprocessor further optimizes the query processing by: precomputing results for tree structure patterns; converting the tree structure patterns into strings; storing the strings as a trie; storing the precomputed results corresponding to each string as an index; and optimizing the query processing by querying the index.

Claim 18

The query system of claim 15 , wherein the hierarchical documents comprise XML documents.

Claim 19

A query system having instruction codes for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising: a preprocessor comprising a first set of instruction codes for computing structural relationship sets between elements and attributes of a schema, and a second set of instruction codes for computing values and structure indices; a query processor for performing a query and returning a result set, comprising: a third set of instruction codes for building an execution plan for a document; and a fourth set of instruction codes for executing the execution plan; a fifth set of instruction codes for comparing the query against the structural relationship sets to determine if the query is to be executed on the documents; and a sixth set of instruction codes for optimizing a query processing by filtering documents that will produce an empty result; a seventh set of instruction codes for optimizing by using the indices instead of executing the query on the actual documents; an eight set of instruction codes for maintaining an indexing structure for tree pattern matching; wherein, for each non-filtered document, the indexing structure comprises three indices: a value index that corresponds to a document content; a structure index that corresponds to a tree structure pattern of the non-filtered document; and a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further organizes the three indices as a trie; and queries the trie using tree pattern matching.

Claim 20

A query system having instruction codes for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising: a preprocessor comprising a first set of instruction codes for computing structural relationship sets between elements and attributes of a schema, and a second set of instruction codes for computing values and structure indices; a query processor for performing a query and returning a result set, comprising: a third set of instruction codes for building an execution plan for a document; and a fourth set of instruction codes for executing the execution plan; a fifth set of instruction codes for comparing the query against the structural relationship sets to determine if the query is to be executed on the documents; and a sixth set of instruction codes for optimizing a query processing by filtering documents that will produce an empty result; a seventh set of instruction codes for optimizing by using the indices instead of executing the query on the actual documents; an eight set of instruction codes for maintaining an indexing structure for tree pattern matching; wherein, for each non-filtered document, the indexing structure comprises three indices: a value index that corresponds to a document content; a structure index that corresponds to a tree structure pattern of the non-filtered document; and a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further organizes the three indices as a trie; and queries the trie using tree pattern matching.

Claim 21

The query system of claim 17 , wherein the query processor further comprises a result consolidator.

Claim 22

The query system of claim 18 , wherein the query processor further comprises: a schema extractor for extracting structural relationship sets from the schemas; and an indexing system.

Claim 23

The query system of claim 17 , wherein the query processor optimizes the query processing by determining if the query to be executed on the hierarchical documents will produce an empty result, and eliminating all the documents conforming to the common schema that will produce an empty result.

Claim 24

The query system of claim 17 , wherein the query processor further optimizes the query processing by removing redundant query constraints, and by simplifying complex constraints, if any.

Claim 25

The query system of claim 19 , wherein the preprocessor further optimizes the query processing by: precomputing results for tree structure patterns; converting the tree structure patterns into strings; storing the strings as a trie; storing the precomputed results corresponding to each string as an index; and optimizing the query processing by querying the index.