GRAPH SEARCH SYSTEM AND METHOD FOR QUERYING LOOSELY INTEGRATED DATA

• US 20090240682A1
• Filed: 03/22/2008
• Published: 09/24/2009
• Est. Priority Date: 03/22/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Reinwald, Berthold, Balmin, Andrey, Pirahesh, Mir Hamid, Hwang, Heasoo
• Granted Patent: US 8,326,847 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2425 Iterative querying; Query formulation based on the results of a preceding query
• CPC Class Codes: G06F 16/248 Presentation of query results

Abstract

A system, method and computer program product for executing a query on linked data sources. Embodiments of the invention generate an instance graph expressing relationships between objects in the linked data sources and receive a query including at least first and second search terms. The first search term is then executed on the instance graph and a summary graph is generated using the results of the executing step. A second search term is then executed on the summary graph.

Claims

1. A method of executing a query on linked data sources comprising:

generating an instance graph expressing relationships between objects in said linked data sources;

receiving a query including at least first and second search terms;

executing said first search term on said instance graph;

generating a summary graph using the results of said executing; and

executing said second search term on said summary graph.

2. The method of claim 1 wherein said executing said first search term further comprises using said first term as a filter to derive a subset of said linked data sources.

3. The method of claim 2 wherein said executing said first search term further comprises performing a relationship search that ranks each object in said instance graph with respect to said subset.

4. The method of claim 3 wherein said relationship search uses a fuzzy search operator to derive said summary graph and wherein said summary graph indicates how closely related an object in said linked databases is to said first and second search terms.

5. The method of claim 3 wherein said relationship search uses a random walk to derive said summary graph and wherein said summary graph indicates how closely related an object in said linked databases is to said first and second search terms.

6. The method of claim 3 wherein said relationship search uses an ObjectRank method to derive said summary graph and wherein said summary graph indicates how closely related an object in said linked databases is to said first and second search terms.

7. The method of claim 3 further comprising filtering out results of said relationship search whose scores fall below a predetermined threshold.

8. The method of claim 7 further comprising generating an aggregated summary graph by adding to said summary graph an aggregated group of objects that fall below said threshold during said relationship search, which are related to one of said objects.

9. The method of claim 1 further comprising generating a presentation graph from said summary graph that visually displays clusters of closely connected objects in said linked databases.

10. A method of finding relationships between objects in a database comprising:

generating an instance graph expressing relationships between objects in said linked data sources;

receiving a query including at least first and second search terms;

executing a first search term in a query by using said first term as a filter to derive a subset of said database;

performing a relationship search that ranks each object in said instance graph with respect to said subset;

generating a summary graph using the results of said executing; and

executing said second search term on said summary graph.

11. The method of claim 10 wherein said query includes a third search term and further comprising executing said third search term on the results of said executing of said second search term.

12. The method of claim 10 wherein said performing a relationship search comprises performing a random walk.

13. The method of claim 10 wherein said performing a relationship search comprises using an ObjectRank method.

14. The method of claim 10 further comprising generating a presentation graph from said summary graph that visually displays clusters of closely connected objects in said linked databases.

15. A system comprising:

a plurality of databases;

a query processor coupled to a databases, said query processor having a filter module which receives a query including a relationship search term; and

a relationship search engine coupled to said query processor and receiving an instance graph from one of said databases, said relationship search engine processes said relationship search term on said instance graph to determine a ranking of objects in said instance graph that indicates how related said objects are to said relationship search term.

16. The system of claim 15 wherein said query processor uses said ranking to generate a summary graph including those objects having a score above a predetermined threshold.

17. The system of claim 16 wherein said query incluses a second relationship search term and said relationship search engine processes said second relationship search term on said summary graph to determine a ranking of objects in said summary graph that indicates how related objects in said summary graph are to said second relationship search term.

18. The system of claim 17 further comprising a presentation graph generator for receiving said summary graph and creating a visual display of said summary graph that displays clusters of closely connected objects in said databases.

19. A computer program product comprising a computer usable medium having a computer readable program, wherein said computer readable program when executed on a computer causes said computer to:

generate an instance graph expressing relationships between objects in said linked data sources;

receive a query including at least first and second search terms;

execute said first search term on said instance graph;

generate a summary graph using the results of said executing; and

execute said second search term on said summary graph.

20. The computer program product of claim 19 wherein said computer readable program further causes said computer to perform a relationship search that ranks each object in said instance graph with respect to at least one of said search terms.