EXPRESSING AND EXECUTING SEMANTIC QUERIES WITHIN A RELATIONAL DATABASE

• US 20110202560A1
• Filed: 02/16/2010
• Published: 08/18/2011
• Est. Priority Date: 02/16/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bowers, Stuart M., Campbell, David G., Aust, Brian S., Jackson, Thomas E., Karkanias, Chris Demetrios, Brown, Allen L.
• Granted Patent: US 8,204,903 B2
• Time in Patent Office: Days
• US Class Current: 707/773
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Semantic queries are expressed and executed within a relational database. This can be done by defining semantic rules applied to execute the semantic queries using table valued functions and common table expressions, and then simply calling the defined table valued functions to execute the queries.

Claims

1. A computer-implemented method of retrieving data from a relational database having a processing component and a relational data store, comprising:

receiving a semantic query that depends, for its execution, on application of at least one semantic rule;

expressing the semantic query within the relational database, using the processing component;

executing the semantic query against the relational data store, using the processing component within the relational database; and

returning database results, using the processing component, generated from execution of the semantic query.

2. The computer-implemented method of claim 1 wherein expressing the semantic query comprises:

generating a table valued function that defines a semantic rule to be called in executing the semantic query, and wherein executing the semantic query comprises calling the table valued function.

3. The computer-implemented method of claim 2 wherein the semantic query comprises a recursive semantic query requiring application of a recursive semantic rule and wherein generating a table valued function comprises:

generating the table valued function using a common table expression to express the recursive semantic rule.

4. The computer-implemented method of claim 3 wherein the semantic query comprises a bifurcating recursive semantic query requiring application of a bifurcating recursive semantic rule and wherein expressing comprises:

generating a table valued function that defines the bifurcating recursive semantic rule.

5. The computer-implemented method of claim 1 wherein expressing the semantic query within the relational database comprises:

expressing only non-recursive and linearly recursive semantic queries within the relational database.

6. The computer-implemented method of claim 1 wherein expressing the semantic query is performed after receiving the semantic query and in response to receiving the semantic query.

7. The computer-implemented method of claim 1 wherein expressing the semantic query results in a direct expression of the semantic query and is performed prior to receiving the semantic query, and further comprising:

storing the direct expression of the semantic query for execution against the relational data store in response to receiving the semantic query.

8. The computer-implemented method of claim 1 and further comprising:

after receiving the semantic query, determining whether the semantic query has an expression stored within the relational database; and

if not, expressing the semantic query within the relational database.

9. The computer-implemented method of claim 1 wherein expressing the semantic query comprises:

defining a scalar valued function that expresses a semantic rule to be applied in executing the semantic query, and wherein executing the semantic query comprises calling the scalar valued function.

10. A relational database, comprising:

a relational data store storing data in a form represented by a graph structure comprising a set of triples, each triple including a subject node, an object node and a predicate connecting the subject and object nodes; and

a processing component that defines and stores at least one semantic rule to be applied in executing a semantic query, the processing component receiving a call to the at least one semantic rule and directly executing the at least one semantic rule against the graph structure in the relational data store within the relational database to return results responsive to the semantic query.

11. The relational database of claim 10 wherein the semantic query comprises a recursive semantic query requiring application of a recursive semantic rule having at least one unbound subject or object such that when directly executing the recursive semantic rule against the graph structure, the processing component recursively climbs the graph structure to obtain results that bind the at least one unbound subject or object.

12. The relational database of claim 11 wherein the processing component defines a group of four functions to express all bindings for the semantic rule.

13. The relational database of claim 10 wherein the processing component defines and stores the at least one semantic rule prior to receiving a call to the at least one semantic rule.

14. The relational database of claim 10 wherein the processing component defines the at least one semantic rule in response to receiving the at least one semantic query.

15. The relational database of claim 10 wherein the processing component defines and stores all classes of semantic rules, including non-recursive, linearly recursive and bifurcating recursive semantic rules.

16. The relational database of claim 10 wherein the processing component defines and stores only non-recursive and linearly recursive semantic rules.

17. The relational database of claim 16 wherein the processing component determines whether the semantic query is a bifurcating recursive semantic query and, if so, provides the semantic query to a semantic reasoning engine, external to the relational database, for processing.

18. A relational database, comprising:

a relational data store storing items and indicating relations between the items;

a computer readable medium storing semantic rules applied to execute semantic queries, the semantic rules falling into one of only a subset of classes of semantic rules, within the relational database; and

a processing component, receiving an input semantic query, and calling at least one of the stored semantic rules that express the input semantic rules and executing the one of the semantic queries against the relational data store to obtain search results responsive to the input semantic query, the processing component executing a query plan that accounts for semantic dependencies in the input semantic query.

19. The relational database of claim 18 wherein the subset of classes of semantic rules stored in the computer readable medium comprises:

non-recursive semantic rules; and

linearly recursive semantic rules.

20. The relational database of claim 18 wherein the stored semantic rules are defined as table valued functions using common table expressions.