Methods, apparatus and data structures for facilitating a natural language interface to stored information

• US 7,310,642 B2
• Filed: 01/14/2005
• Issued: 12/18/2007
• Est. Priority Date: 05/03/2000
• Status: Expired due to Term

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: McConnell, Christopher Clayton, Barklund, Par Jonas
• Primary Examiner(s): Gaffin, Jeffrey
• Assistant Examiner(s): Hicks, Michael J
• Application Number:
  US11/036,872
• Publication Number:
  US 20050197828A1
• Time in Patent Office: 1,068 Days
• Field of Search: 707 1- 6, 704 4- 10
• US Class Current: 707/748
• CPC Class Codes: G06F 40/169 Annotation, e.g. comment data or footnotes
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

An authoring tool (or process) to facilitate the performance of an annotation function and an indexing function. The annotation function may generate informational annotations and word annotations to a database design schema (e.g., an entity-relationship diagram or “ERD”). The indexing function may analyze the words of the annotations by classifying the words in accordance with a concordance and dictionary, and assign a normalized weight to each word of each of the annotations based on the classification(s) of the word(s) of the annotation.

A query translator (or query translation process) to (i) accept a natural language query from a user interface process, (ii) convert the natural language query to a formal command query (e.g., an SQL query) using the indexed annotations generated by the authoring tool and the database design schema, and (iii) present the formal command query to a database management process for interrogating the relational database.

Claims

1. A method for preprocessing a natural language database query, the method comprising:

a) accepting an alphanumeric string related to the query;

b) parsing the alphanumeric string to generate query words;

c) determining whether any of the query words, or any phases formed by at least two adjacent query words, match any of a plurality of indexed annotations;

d) if a query word or phrase matches one or more of the plurality of indexed annotations, for each of the plurality of indexed annotations, adding a pattern associated with the indexed annotation to a group associated with the query word or phrase;

e) selecting a pattern from each group of patterns to generate a selection of patterns; and

f) combining the patterns of the selection of patterns to generate a single, connected, lowest cost pattern.

2. The method of claim 1 wherein the act of parsing the alphanumeric string to generate query words includes:

i) removing at least some types of punctuation;

ii) normalizing case; and

iii) stemming words to generate root words.

3. The method of claim 1 wherein the act of determining whether any of the query words, or any phases formed by at least two adjacent query words, match any of a plurality of indexed annotations, includes, for each query word and each phase:

i) for each of the plurality of indexed annotations, determining whether the query word or phase is exactly or partially the same as the indexed annotation; and

ii) for each of the plurality of indexed annotations,

A) if the query word or phase is exactly the same as the indexed annotation, determining a match, and

B) if the query word or phase is partially, but not exactly, the same as the indexed annotation, determining a match only if certain criteria are met.

4. The method of claim 3 wherein if the query word or phrase does not match any of a plurality of indexed annotations, then performing further acts of:

determining whether the query word is one of a noun or adjective; and

if it is determined that the query word is one of noun or adjective, generating an error message conveying a fact that the query word or phrase is unknown.

5. The method of claim 1 wherein, in the act of combining the patterns of the selection of patterns to generate a single, connected, lowest cost pattern, includes

i) determining start states by determining all possible selections,

ii) applying a cost heuristic, based on a database schema, to each of the states,

iii) selecting a lowest cost state, and

iv) until a single, connected, pattern is found,

A) generating successor states of the selected lowest cost state,

B) applying a cost heuristic, based on the database schema, to each of the successor states,

C) estimating a cost for each of the successor states,

D) adding the successor states to a queue of all states, and

E) selecting a new lowest cost state from the queue of all states.

6. The method of claim 5 wherein the act of generating successor states of the selected lowest cost state, includesfor each pair of patterns in the selected state,

determining possible actions and their costs, and

pruning actions based on their costs.

7. The method of claim 6 wherein the possible actions include a unify entity action, a unify relationship action, and a link patterns via a path action, and wherein the cost of a link patterns via a path action is based on at least one of (i) a number of entities in the path and (ii) a number of relationships in the path.

8. The method of claim 7 wherein the path may include at least one of:

A) a link from a more specific entity table to a more general entity table;

B) a link from a property table to a related entity table; and

C) a link from an entity table to a related property table.

9. The method of claim 7 wherein at least one of the relationships of the entity-relationship schema has an associated weight, and

wherein the path is chosen from a group of candidate paths such that a sum of weights associated with the relationships, associated with the links, is minimized.

10. The method of claim 9 wherein, if there is more than one candidate path with the same sum of weights, then choosing one of the more than one candidate paths such that a distance between words in the query that created the object pair is minimized.

11. The method of claim 5 wherein the act of generating successor states of the selected lowest cost state, includesdetermining whether any patterns of the lowest cost state include a nexus and if so, selecting a minimum cost pattern with a nexus, otherwise, selecting a minimum cost pattern, andfor each pair of patterns in the selected state including the selected pattern, determining possible actions and their costs.

12. The method of claim 11 wherein the possible actions include a unify entity action, a unify relationship action, and a link patterns via a path action, and wherein the cost of a link patterns via a path action is based on at least one of (i) a number of entities in the path and (ii) a number of relationships in the path.

13. The method of claim 12 wherein the path may include at least one of:

A) a link from a more specific entity table to a more general entity table;

B) a link from a property table to a related entity table; and

C) a link from an entity table to a related property table.

14. The method of claim 12 wherein at least one of the relationships of the entity-relationship schema has an associated weight, and

wherein the path is chosen from a group of candidate paths such that a sum of weights associated with the relationships, associated with the links, is minimized.

15. The method of claim 5 wherein the act of estimating a cost of each successor state includes

determining a known cost,

determining an unknown cost, and

determining an estimated cost based on the known cost and the unknown cost.

16. The method of claim 15 wherein the known cost is the cost of the parent state plus the cost of the action of generating the successor state less the cost of any entities in a path that are type compatible with any entities in any patterns of the start states.

17. The method of claim 15 wherein the unknown cost is discounted based on applicable hints in a hint set.

18. A storage medium having machine readable instructions embodied thereon, which when executed by a processor cause a machine to perform the method of claim 1.

19. An apparatus for preprocessing natural language database queries, the apparatus comprising:

a) an input for accepting an alphanumeric string related to the query;

b) a parser for parsing the alphanumeric string to generate query words;

c) a matcher for determining whether any of the query words, or any phrases formed by at least two adjacent query words, match any of a plurality of indexed annotations;

d) a facility for adding, if a query word or phrase matches one or more of the plurality of indexed annotations, for each of the plurality of indexed annotations, adding a pattern associated with the indexed annotation to a group associated with the query word or phrase;

e) a facility for selecting a pattern from each group of patterns to generate a selection of patterns; and

f) a facility for combining the patterns of the selection of patterns to generate a single, connected, lowest cost pattern.

20. The apparatus of claim 19 further comprising:

f) an object marker for marking at least one object of combined pattern objects, for presentation.