Indexing and querying of structured documents
AssigneeCanon Kabushiki Kaisha
InventorErnest Yiu Cheong Wan
Life of this patent
Estimating the term…
Abstract
A method is disclosed that can be used to reduce the size of the indexes 130 of structured-documents 150. The method uses the schema 110 of structured documents 180, in particular XML documents, to determine the existence of certain deterministic relationships 140 among the indexing components 170. Using such knowledge when indexing the data and formulating query execution plans can greatly reduce the size of the indices 170 and allow querying of such documents more efficiently.
Claims18
A method of indexing structured documents, the method comprising the steps of:
- parsing at least one schema of the structured documents to determine predefined deteministic relationships between components of the structured documents to be indexed;
- removing from one or more sets of indices those components whose occurrences can be deduced by virtue of said determined predefined deterministic relationships from occurrences of another indexing component to provide corresponding one or more smaller sets of indices;
- and
- indexing said structured documents in accordance with said one or more smaller sets of indices.
A method of querying structured documents, wherein said structured documents comprise a plurality of components and have one or more associated sets of indices of indexing components, the method comprising the steps of:
- reformulating an original query substituting references to one or more non-indexed components in the query with references to said indexing components using predefined deterministic relationships predetermined from schemas of the structured documents wherever possible;
- querying said structured documents using said reformulated query and said one or more sets of indices of indexing components to provide one or more sets of intermediate results;
- and
- performing post-retrieval processing on the one or more sets of intermediate results to form the final result of said original query, said post-retrieval processing comprises the sub-steps of:
- locating the location of the one or more non-indexed components existing in the one or more intermediate results that were substituted in the original query;
- and
- generating a final result set to satisfy the original query using the located non-indexed components.
Apparatus for indexing structured documents, the apparatus comprising:
- means for parsing one or more schemas of the structured documents to determine predefined deterministic relationships between components of the structured documents to be indexed;
- means for removing from one or more sets of indices those components whose occurrences can be deduced by virtue of said determined predefined deterministic relationships from occurrences of another indexing component to provide corresponding one or more smaller sets of indices;
- and
- means for indexing said structured documents in accordance with said one or more smaller sets of indices.
Apparatus for querying structured documents, wherein said structured documents comprise a plurality of components and have one or more associated sets of indices of indexing components, the apparatus comprising.
- means for reformulating an original query substituting references to one or more non-indexed components in the query with references to said indexing components using predefined deterministic relationships predetermined from schemas of the structured documents wherever possible;
- means for querying said structured documents using said reformulated query and said one or more sets of indices of indexing components to provide one or more sets of intermediate results;
- and
- means for performing post-retrieval processing on the one or more sets of intermediate results to form the final result of said original query, said post-retrieval processing means comprises:
- means for locating the location of the one or more non-indexed components existing in the one or more intermediate results that were substituted in the original query;
- and
- means for generating a final result set to satisfy the original query using the located non-indexed components.
A computer program for indexing structured documents, the computer program comprising:
- code for parsing one or more schemas of the structured documents to determine predefined deterministic relationships between components of the structured documents to be indexed;
- code for removing from one or more sets of indices those components whose occurrences can be deduced by virtue of said determined predefined deterministic relationships from occurrences of another indexing component to provide corresponding one or more smaller sets of indices;
- and
- code for indexing said structured documents in accordance with said one or more smaller sets of indices.
A computer program for querying structured documents, wherein said structured documents comprise a plurality of components and have one or more associated sets of indices of indexing components, the computer program comprising,
- code for reformulating an original query substituting references to one or more non-indexed components in the query with references to said indexing components using predefined deterministic relationships predetermined from schemas of the structured documents wherever possible;
- code for querying said structured documents using said reformulated query and said one or more sets of indices of indexing components to provide one or more sets of intermediate results;
- and
- code for performing post-retrieval processing on the one or more sets of intermediate results to form the final result of said original query, said post-retrieval processing code comprises;
- code for locating the location of the one or more non-indexed components existing in the one or more intermediate results that were substituted in the original query;
- and
- code for generating a final result set to satisfy the original query using the located non-indexed components.
Dependencies are inferred from the claim text.