EXECUTION OF SEMANTIC QUERIES USING RULE EXPANSION

• US 20100250576A1
• Filed: 03/31/2009
• Published: 09/30/2010
• Est. Priority Date: 03/31/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Karkanias, Chris Demetrios, Bowers, Stuart M., Wecker, David B.
• Granted Patent: US 8,032,525 B2
• Time in Patent Office: Days
• US Class Current: 707/760
• CPC Class Codes: G06F 16/2435 Active constructs
• CPC Class Codes: G06F 16/2452 Query translation

Abstract

A semantic query may refer to a logical rule, where the rule is defined in terms of constituent expressions. In order to execute the semantic query efficiently, occurrences of the rule may be expanded by replacing the rule with its constituent expressions. Expansion may be performed repeatedly, until only grounded expressions remain. Expressions are grounded when they refer to tables or views that are represented in an underlying database. Once the rule has been reduced to grounded expressions, the semantic query processor may formulate a relational query in terms of the grounded expressions. If the relational query takes into account the various grounded expressions to which the rule reduces, then the portion of the semantic query that refers to the rule may be processed without an excessive number of round trips to the relational database.

Claims

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

receiving a semantic query;

determining that said semantic query comprises a first rule that comprises one or more constituent terms, each of said constituent terms comprising, or being reducible to, one or more grounded terms in a relational database, each of said grounded terms corresponding to a table or a view in said relational database;

creating an expanded semantic query by performing second acts comprising replacing said first rule with said first rule'"'"'s constituent terms;

forming a relational query based on said expanded semantic query;

sending said relational query to a relational query processor of said relational database; and

receiving a result from said relational query processor.

2. The one or more computer-readable storage media of claim 1, wherein a first one of said constituent terms is a rule, and wherein said first acts further comprise:

repeatedly expanding said first one of said constituent terms until a term is reached that is grounded in said relational database.

3. The one or more computer-readable storage media of claim 1, wherein each of the grounded terms in said relational database is a table or view that corresponds to a given predicate, wherein each table or view comprises a subject and an object of a predicate to which the table corresponds, and wherein said relational query comprises a join of a plurality of the tables or views.

4. The one or more computer-readable storage media of claim 1, wherein said first acts further comprise:

determining that said first rule is not recursive.

5. The one or more computer-readable storage media of claim 1, wherein said semantic query comprises a SPARQL query.

6. The one or more computer-readable storage media of claim 1, wherein said first acts further comprise:

taking a tangible action based on said result.

7. The one or more computer-readable storage media of claim 6, wherein said tangible action comprises:

presenting, to a person, a description of a condition of a human body or of a treatment of said human body.

8. The one or more computer-readable storage media of claim 6, wherein said tangible action comprises:

affecting a course of treatment of a human body.

9. A system for answering a semantic query, the system comprising:

a semantic query engine that receives the semantic query, the semantic query comprising a first rule that comprises one or more constituent terms that comprise, or are reducible to, one or more grounded terms in a relational database;

a relational query generator that expands the semantic query into an expanded semantic query by replacing said first rule with its constituent terms, said relational query generator generating a relational query based on said expanded semantic query and submitting said relational query to said relational database; and

said relational database, which stores tables corresponding to said grounded terms, each of said tables corresponding to a predicate and defining subject and object pairs that are related by said predicate, said relational database providing a result in response to said relational query by performing relational operations on said tables.

10. The system of claim 9, wherein one of said constituent terms is a second rule, and wherein said relational query generator generates said expanded semantic query by repeatedly replacing rules with their constituent terms until said grounded terms are reached.

11. The system of claim 9, wherein said relational query generator determines that said first rule is not recursive.

12. The system of claim 9, wherein, in absence of expansion of said first rule, said relational query generator generates a first relational query for a first one of said constituent terms, and then generates one or more additional relational queries based on a response to said first relational query, and then obtains, from said relational database, information that responds to said first rule by issuing only a single relational query.

13. The system of claim 9, wherein said semantic query comprises a SPARQL query.

14. The system of claim 9, wherein said first rule comprises, or is reducible to, grounded terms that comprise a first grounded term and a second grounded term, wherein said first grounded term and said second grounded term are related in said first rule by a common variable, wherein said relational query calls for performing a join on a first column of a first table that corresponds to said first grounded term, and a second column of a second table that corresponds to said second grounded term.

15. The system of claim 9, wherein said relational query generator presents information, based on said result, that describes a human body or a treatment of said human body.

16. The system of claim 9, wherein said system affects a course of treatment of a human body based on said result.

17. A method of processing a first query that includes a first rule, the method comprising:

using a processor to perform acts comprising;

receiving said first query;

determining that said first query comprises said first rule, wherein said first rule comprises, or is reducible to, a set of grounded terms comprising a first grounded term and a second grounded term;

expanding said first query into a second query that comprises said first grounded term and said second grounded term;

generating a third query based on said second query, said first query being a semantic query, said third query being a relational query that calls for relational operation on tables or views, in a relational database, that correspond to said first grounded term and said second grounded term;

receiving a first result of said third query from said relational database; and

providing said first result, or a second result based on said first result, to a person.

18. The method of claim 17, further comprising:

using a processor to perform acts comprising;

presenting, based on said first result or said second result, a description of a human body or of a treatment of said human body;

or

affecting a course of treatment of said human body based on said first result or said second result.

19. The method of claim 17, further comprising:

using a processor to perform acts comprising;

determining that said first rule is not recursive.

20. The method of claim 17, wherein said first rule comprises a second rule, and wherein the method further comprises:

using a processor to perform acts comprising;

repeatedly expanding said first rule until said second rule, and any rules that said first rule comprises or is reducible to, have been reduced to said set of grounded terms.