GRAPH QUERIES OF INFORMATION IN RELATIONAL DATABASE

• US 20100241644A1
• Filed: 03/19/2009
• Published: 09/23/2010
• Est. Priority Date: 03/19/2009
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Karkanias, Chris Demetrios, Bowers, Stuart M., Campbell, David G., Jackson, Thomas E.
• Application Number:
  US12/407,767
• Publication Number:
  US 20100241644A1
• Time in Patent Office: Days
• US Class Current: 707/760
• CPC Class Codes: G06F 16/2423 Interactive query statement specification based on a database schema
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/288 Entity relationship models

Abstract

In one example, information may be stored in a relational database. The information in the database may define a graph, in the sense that the information may define a set of entities and relations between the entities. A user may want to query the information using a graph-based query language. A graph query engine may receive the query, and may convert the query into a relational query language, for execution by the relational database. The relational database may calculate views of the underlying tables. Each view corresponds to a particular relation, and the rows in each view are pairs of entities to which the relation applies. Since the views correspond very closely to the specification of a graph, the graph-based query may be translated into a relational query that performs relational algebraic operations on the views in order to answer the graph-based query.

Claims

1. A method of answering a query, comprising:

using a computer processor to perform acts comprising;

creating a plurality of views based on information stored in a relational database, the information being stored in tables in the relational database, the information defining a plurality of entities and a plurality of relationships between pairs of entities, each of the views corresponding to one of the plurality of relationships;

receiving a graph query that requests an answer based on said entities and said relationships;

converting said graph query into a relational query that is defined in terms of operations on the views;

using a relational query processor to answer said relational query; and

providing a result based on answering of said relational query.

2. The method of claim 1, wherein said graph query is specified in SPARQL.

3. The method of claim 1, wherein said graph query is received by a graph query processor, and wherein said converting is performed by said graph query processor.

4. The method of claim 3, wherein the result is provided to the graph query processor, and wherein the method further comprises:

using the graph query processor to present the result to a user who supplied the graph query.

5. The method of claim 1, further comprising:

using the computer processor to perform a tangible action that is based on the graph query.

6. The method of claim 1, wherein each of said relationships has a name, and wherein each of the views comprises the name of a relationship to which the view corresponds.

7. The method of claim 1, wherein each of the views comprises two columns, wherein a first one of the columns stores a subject of the relationship to which the view corresponds, and wherein a second one of the columns stores an object of a relationship to which the view corresponds.

8. The method of claim 1, wherein said relational database comprises a table in which an instance of a relationship is in a single column of said table, without a subject and an object of said relationship being in separate columns in said table, and wherein said creating creates said views based on said table.

9. A system comprising:

a relational database that comprises;

a plurality of tables that store information about entities and about relationships between said entities;

a table monitor that creates views of information stored in said tables, each of said views corresponding to a particular relationship identified by said tables, each of said views comprising a first column that stores a subject of the relationship to which the view corresponds and a second column that stores an object of the relationship to which the view corresponds; and

a relational query processor that processes relational queries on said views; and

a graph query engine that receives a graph query, that converts said graph query into a relational query that specifies operations to be performed on said views to answer said graph query, that provides said relational query to said relational query processor, and that receives a result from said relational query processor.

10. The system of claim 9, wherein said table monitor is triggered to update said views when a relationship is added to said tables, said table monitor updating said views by adding a new view corresponding to the added relationship.

11. The system of claim 9, wherein said table monitor is triggered to update said views when a relationship is deleted from said tables, said table monitor updating said views by deleting an existing view that corresponds to the relationship that is deleted from the tables.

12. The system of claim 9, wherein said table monitor is triggered to update said views when a new instance of a relationship is added to said tables, said table monitor updating said views by identifying a view to which said relationship corresponds and by adding a new row to the identified view that contains a subject and an object of the new instance.

13. The system of claim 9, wherein said table monitor is triggered to update said views when an instance of a relationship is deleted from said tables, said table monitor updating said views by identifying a view to which said relationship corresponds, by identifying a row containing a subject and an object of the deleted instance, and by removing the identified row from the view.

14. The system of claim 9, wherein said tables do not include a table that has a first column that stores a subject of a given relationship and a second column that stores an object of said given relationship.

15. The system of claim 9, wherein said query comprises a SPARQL query, and wherein said graph query engine converts said SPARQL query into said relational query.

16. The system of claim 9, wherein said table monitor includes, in each of the views, a name of a relationship to which a given view corresponds.

17. One or more computer-readable storage media that store executable instructions that, when executed by a computer, cause the computer to perform acts comprising:

monitoring a relational database to identify changes in the relational database, said relational database storing a table that specifies instances of relations, each instance of a relation identifying a subject and an object to which the relation applies, said table storing said subject and said object in a single column, said table not having separate columns to store said subject and said object;

determining that said table has been modified in a way that changes which relations, or instances of relations, exist; and

based on modifications to said table, updating a set of views, each of the views representing subjects and objects that are related by a given relation.

18. The one or more computer-readable storage media of claim 17, wherein said determining finds that said table has been modified by addition of a new relation to said table, and wherein the acts further comprising:

creating a new view that corresponds to said new relation.

19. The one or more computer-readable storage media of claim 17, wherein said determining finds that said table has been modified by addition of a new instance of a first relation to said table, and wherein the acts further comprise:

identifying a first one of the views that corresponds to said first relation; and

adding to said first one of the views a row that comprises a subject of said new instance in a first column of said first one of the views, and an object of said new instance in a second column of said first one of the views.

20. The one or more computer-readable storage media of claim 17, wherein each given one of said views comprises:

a name of the relation to which the given view corresponds;

a first column that stores subjects of the relation; and

a second column that stores objects of the relation.