Semantic query language

Patent metadata

Field	Value
Publication number	US-9659082-B2
Application number	US-201213594883-A
Country	US
Kind code	B2
Filing date	Aug 27, 2012
Priority date	Aug 27, 2012
Publication date	May 23, 2017
Grant date	May 23, 2017

Abstract

Various technologies described herein pertain to executing a mixed query to search a database retained in a data repository. The mixed query includes a regular expression, which is a pattern of elements, and a semantic constraint. The elements in the regular expression include a first wildcard, where the semantic constraint restricts a meaning of the first wildcard. Moreover, the elements in the regular expression include explicit lexical constraint(s) and/or disparate wildcard(s). For instance, semantic constraint(s) can restrict meaning(s) of the disparate wildcard(s). The mixed query is executed to retrieve results that match the pattern of the elements in the regular expression and satisfy the semantic constraint(s).

First claim

What is claimed is:

1. A method of searching a database retained in a data repository, comprising:
iteratively generating a mixed query, the mixed query comprises:
a regular expression, the regular expression is a pattern of elements, and the elements in the regular expression comprise:
a first wildcard; and
at least one of an explicit lexical constraint or a second wildcard; and

a semantic constraint, the semantic constraint includes a restriction to a meaning of a match returned responsive to the first wildcard; and
wherein iteratively generating the mixed query further comprises:
executing a previous version of the mixed query to retrieve previous results from the database retained in the data repository;
receiving feedback concerning the previous results retrieved in response to executing the previous version of the mixed query, the feedback specifies at least one of a subset of the previous results undesirably retrieved in response to executing the previous version of the mixed query or a set of missing results undesirably omitted from the previous results retrieved in response to executing the previous version of the mixed query;
performing programming by example based on the feedback that specifies at least one of the subset of the previous results undesirably retrieved or the set of missing results undesirably omitted to automatically refine the previous version of the mixed query, wherein performing the programming by example based on the feedback generates the mixed query; and
executing the mixed query to retrieve results that match the pattern of the elements in the regular expression and satisfy the semantic constraint, wherein the results are retrieved from the database retained in the data repository; and

causing the results retrieved in response to executing the mixed query to be outputted.

2. The method of claim 1 , wherein the first wildcard and the second wildcard are each one of a word wildcard or a phrase wildcard.

3. The method of claim 1 , wherein the semantic constraint restricts the meaning of the match returned responsive to the first wildcard to one of a synonym of a given word, an antonym of the given word, a sense of the given word, or based on a negated semantic constraint.

4. The method of claim 1 , wherein the first wildcard is a phrase wildcard, and wherein the semantic constraint restricts the phrase wildcard to return a name of a geographic location.

5. The method of claim 1 , wherein the mixed query further comprises a syntactic constraint that restricts a grammatical construction of at least one of the first wildcard or the second wildcard.

6. The method of claim 1 , wherein the elements in the regular expression comprise the explicit lexical constraint and the second wildcard, wherein the mixed query further comprises a second semantic constraint that includes a second restriction to a meaning of a match returned responsive to the second wildcard in the regular expression, and wherein the semantic constraint is a context-independent semantic constraint and the second semantic constraint is a context-dependent semantic constraint.

7. The method of claim 6 , wherein executing the mixed query to retrieve the results that match the pattern of the elements in the regular expression and satisfy the context-independent semantic constraint and the context-dependent semantic constraint further comprises:
parsing the mixed query into the regular expression and semantic constraints, wherein the semantic constraints comprise the context-independent semantic constraint and the context-dependent semantic constraint;
expanding the context-independent semantic constraint into an expanded lexical constraint;
identifying candidate sentences from the database that include words specified by the expanded lexical constraint and the explicit lexical constraint;
filtering the candidate sentences from the database based on whether the candidate sentences match the pattern of the elements in the regular expression to output filtered candidate sentences from the database;
evaluating whether the filtered candidate sentences from the database satisfy the context-dependent semantic constraint; and
retrieving the filtered candidate sentences from the database that satisfy the context-dependent semantic constraint as the results.

8. The method of claim 7 , further comprising applying the expanded lexical constraint and the explicit lexical constraint in an order from most restrictive lexical constraint to least restrictive lexical constraint to identify the candidate sentences from the database that include the words specified by the expanded lexical constraint and the explicit lexical constraint.

9. The method of claim 6 , wherein the context-independent semantic constraint restricts the meaning of the match returned responsive to the first wildcard to one of a synonym of a first given word or an antonym of the first given word, and wherein the context-dependent semantic constraint restricts the meaning of the match returned responsive to the second wildcard to one of a sense of a second given word or based on a negated semantic constraint.

10. The method of claim 1 , wherein the mixed query is a parameterized query.

11. The method of claim 1 , wherein the results are utilized for at least one of interactive language tutoring or question answering.

12. A system that searches a database retained in a data repository, comprising:
a processor;
a memory that comprises computer-executable instructions that, when executed by the processor, cause the processor to perform acts including:
controlling a set of mixed queries outputted for an application, a particular mixed query in the set comprises a common regular expression and a variable constraint which is a function of the particular mixed query, the variable constraint is separate from the common regular expression in the particular mixed query, disparate mixed queries in the set comprise the common regular expression and differing variable constraints, the common regular expression is a pattern of elements, and the elements in the common regular expression comprise:
a first wildcard, wherein the variable constraint of the particular mixed query identifies the first wildcard in the common regular expression and includes a restriction to a meaning of a match returned responsive to the first wildcard; and
at least one of an explicit lexical constraint or a second wildcard;

executing the set of the mixed queries to retrieve, from the database in the data repository, respective results that match the pattern of the elements in the common regular expression and satisfy the variable constraint for each of the mixed queries in the set; and
utilizing the respective results for each of the mixed queries in the set for the application.

13. The system of claim 12 , wherein the application is an interactive language tutoring application, wherein the memory further comprises computer-executable instructions that, when executed by the processor, cause the processor to perform acts including:
controlling the variable constraint to restrict the meaning of the match returned responsive to the first wildcard to be a particular word in a first mixed query in the set; and
generating a sentence from the respective results corresponding to the first mixed query given the pattern of the elements and the particular word.

14. The system of claim 13 , wherein the memory further comprises computer-executable instructions that, when executed by the processor, cause the processor to perform acts including:
controlling the variable constraint to restrict the meaning of the match retu

Assignees

• Gulwani Sumit
• Zweig Geoffrey Gerson
• Microsoft Technology Licensing Llc

Inventors

• Gulwani Sumit
• Zweig Geoffrey Gerson

Classifications

• G06F16/3338 Primary

  Query expansion · CPC title

• G06F16/3331

  Query processing · CPC title

• G06F16/3344

  using natural language analysis · CPC title

• G06F16/338

  Presentation of query results · CPC title

• G06F17/30657 Primary

  Physics · mapped topic