System and method of joining data obtained from horizontally and vertically partitioned heterogeneous data stores using string-based location transparent search expressions

• US 7,890,507 B2
• Filed: 02/25/2005
• Issued: 02/15/2011
• Est. Priority Date: 02/25/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kilroy, John F.
• Primary Examiner(s): Cottingham; John R.
• Assistant Examiner(s): Reyes; Mariela D
• Application Number:
  US11/065,967
• Publication Number:
  US 20060195420A1
• Time in Patent Office: 2,181 Days
• Field of Search: 707/736, 707/740, 707/760
• US Class Current: 707/736
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Described are a system and method for accepting a string-based search expression, parsing the search expression into an expression tree, distributing the tree (or portion thereof) across heterogeneous repositories, and merging the results. The system is data-location transparent, encapsulates a federation model within query nodes and query trees. A client application produces and issues the search expression to the system. One type of expression tree node is an attribute node corresponding to an attribute included in the search expression. Metadata is associated with the attribute node for identifying each repository that supports the attribute represented by that attribute node. A call passes to the expression tree to perform the search, which occurs in a recursive-descent traversal of the tree. The search completes in a single tree traversal. Sub-trees receive a relevant portion of the search expression to translate into a query expression specific for each type of searched repository.

Claims

1. A method for performing a search of a virtual repository formed from a plurality of repositories, each repository of the virtual repository being associated with a separate database system, the method comprising:

receiving a string-based search expression;

generating an expression tree of nodes based on the string-based search expression, one or more of the nodes of the expression tree being an attribute node, each attribute node corresponding to an attribute included in the string-based search expression;

adding repository-location information to the expression tree by associating metadata with each attribute node in the expression tree, the metadata associated with a given attribute node identifying one or more repositories of the virtual repository that support the attribute represented by that attribute node;

generating, for each repository identified by the metadata associated with the one or more attribute nodes, a query expression specifically for that repository; and

determining whether sub-trees of a particular node of the expression tree have attribute nodes associated with metadata identifying different types of repositories, and, if the metadata associated with the attribute nodes identify different types of repositories, constructing the particular node as a federation node for merging search results returned by the child sub-trees;

searching each repository identified by the metadata associated with the one or more attribute nodes using the query expression specifically generated for that repository.

2. The method of claim 1, further comprising initiating a search by calling a root node of the expression tree;

and performing the search in a single recursive descent traversal of the nodes in the expression tree.

3. The method of claim 1, wherein the virtual repository includes one or more horizontally partitioned repositories and one or more vertically partitioned repositories.

4. The method of claim 1, further comprising merging a search result obtained from a horizontally partitioned repository with a search result obtained from a vertically partitioned repository.

5. The method of claim 1, further comprising distributing a first portion of the string-based search expression to a first sub-tree in the expression tree based on metadata associated with each attribute node of the first sub-tree and a second portion of the string-based search expression to a second sub-tree in the expression tree based on metadata associated with each attribute node of the second sub-tree.

6. The method of claim 1, further comprising translating at least a portion of the string-based search expression into the query expression generated specifically for each type of repository to be searched.

7. The method of claim 1, wherein the step of associating metadata with the attribute node includes accessing at least one configuration file to determine which of the repositories support the attribute corresponding to the attribute node.

15. The method of claim 1, wherein the string-based search expression is repository neutral.

16. The method of claim 1, further comprising translating the string-based search expression into a repository-neutral format.

17. The method of claim 16, wherein the repository-neutral format is a generic query language (GQL) format.

8. A server system for performing a search of a virtual repository formed from a plurality of repositories, each repository of the virtual repository being associated with a separate database system, the server system comprising a server computer having:

a query processor apparatus receiving from a client computer having an initiator a string-based search expression, the query processor apparatus including a parser for generating an expression tree of nodes based on the string-based search expression, one or more of the nodes of the expression tree being an attribute node, each attribute node corresponding to an attribute included in the string-based search expression, the parser adding repository-location information to the expression tree by associating each attribute node with metadata to identify the repositories of the virtual repository that support the one or more attributes included in the search expression, each repository of a plurality of repositories being identified by the metadata associated with the one or more attribute nodes;

one or more repository adapters generating, for each repository identified by the metadata associated with the one or more attribute nodes, a query expression specifically for that repository based on the string-based search expression; and

wherein the parser determines whether sub-trees of a particular node of the expression tree have attribute nodes associated with metadata identifying different types of repositories, and, if the metadata associated with the attribute nodes identify different types of repositories, constructs the particular node as a federation node for merging search results obtained by the sub-trees, and searching each repository identified by the metadata associated with the one or more attribute nodes using the query expression specifically generated for that repository,

wherein the query processor apparatus returns a search result to the initiator of the string-based search expression.

9. The server system of claim 8, wherein the parser initiates a search based on the search expression by calling a root node of the expression tree.

10. The server system of claim 8, wherein a node of the expression tree distributes a first portion of the string-based search expression to a first sub-tree in the expression tree based on metadata associated with each attribute node of the first sub-tree and a second portion of the string-based search expression to a second sub-tree in the expression tree based on metadata associated with each attribute node of the second sub-tree.

11. The server system of claim 8, wherein each repository adapter translates at least a portion of the string-based search expression into the query expression specifically generated for one of the repositories to be searched.

12. A computer program product for use with a computer system to perform a search of a virtual repository formed from a plurality of repositories, each repository of the virtual repository being associated with a separate database system, the computer program product comprising a computer useable medium having embodied therein program code comprising:

program code for receiving a string-based search expression;

program code for generating an expression tree of nodes based on the string-based search expression, one or more of the nodes of the expression tree being an attribute node, each attribute node corresponding to an attribute included in the string-based search expression; and

program code for adding repository-location information to the expression tree by associating metadata with each attribute node in the expression tree, the metadata associated with a given attribute node identifying one or more repositories that support the attribute represented by that attribute node, each repository of the plurality of repositories being identified by the metadata associated with the one or more attribute nodes;

program code for generating for each repository identified by the metadata associated with the one or more attribute nodes a query expression specifically for that repository based on the string-based search expression;

program code for searching each repository identified by the metadata associated with the one or more attribute nodes using the query expression specifically generated for that repository and

program code for determining whether sub-trees of a particular node of the expression tree have attribute nodes associated with metadata identifying different sets of repositories, and, if the metadata associated with the attribute nodes identify different sets of repositories, program code for constructing the particular node as a federation node to merge search results returned by the sub-trees.

13. The computer program product of claim 12, further comprising program code for initiating a search based on the search expression by calling a root node of the expression tree.

14. The computer program product of claim 12, further comprising program code for translating at least a portion of the string-based search expression into a query expression specifically generated for each repository to be searched.