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

• US 20060195420A1
• Filed: 02/25/2005
• Published: 08/31/2006
• Est. Priority Date: 02/25/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kilroy, John F.
• Granted Patent: US 7,890,507 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 one or more repositories, the method comprising:

receiving a string-based search expression;

generating an expression tree of nodes based on the string-based search expression, one of the nodes of the expression tree being an attribute node that corresponds to an attribute included in the string-based search expression; and

associating metadata with the attribute node in the expression tree, the metadata identifying one or more repositories of the virtual repository that support the attribute represented by that attribute node.

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, further comprising determining whether sub-trees of a particular node of the expression tree have attributes 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.

4. The method of claim 3, further comprising merging search results returned by the child sub-trees of the federation node.

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

6. 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.

7. 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.

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

9. 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.

10. A server system, comprising a query processor receiving a string-based search expression, the query processor including a parser for generating an expression tree of nodes based on the string-based search expression, one of the nodes of the expression tree being an attribute node that corresponds to an attribute included in the string-based search expression, the parser identifying one or more repositories that support the attribute and associating the attribute node with metadata that links the attribute node with the identified one or more repositories.

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

12. The server system of claim 10 wherein the parser determines whether sub-trees of a particular node of the expression tree have attributes 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.

13. The server system of claim 10, 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.

14. The server system of claim 10, further comprising a repository adapter translating at least a portion of the string-based search expression into a query expression specific for a repository to be searched.

15. A computer program product for use with a computer 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 of the nodes of the expression tree being an attribute node that corresponds to an attribute included in the string-based search expression; and

program code for associating metadata with the attribute node in the expression tree, the metadata identifying one or more repositories that support the attribute represented by that attribute node.

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

17. The computer program product of claim 15, further comprising program code for determining whether sub-trees of a particular node of the expression tree have attributes 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.

18. The computer program product of claim 15, further comprising program code for translating at least a portion of the string-based search expression into a query expression specific for a repository to be searched.

19. A computer data signal embodied in a carrier wave for use with a computer system having a display and capable of generating a user interface through which a user may interact with the computer system, the computer data signal 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 of the nodes of the expression tree being an attribute node that corresponds to an attribute included in the string-based search expression; and

program code for associating metadata with the attribute node in the expression tree, the metadata identifying one or more repositories that support the attribute represented by that attribute node.

20. The computer data signal of claim 19, further comprising program code for initiating a search based on the search expression by calling a root node of the expression tree.

21. The computer data signal of claim 19, further comprising program code for determining whether sub-trees of a particular node of the expression tree have attributes nodes associated with metadata identifying different types of repositories, and, if the metadata associated with the attribute nodes identify different types of repositories, program code for constructing the particular node as a federation node to merge search results returned by the sub-trees.

22. The computer data signal of claim 19, further comprising program code for 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.