Disambiguating join paths for natural language queries

• US 10,282,444 B2
• Filed: 09/09/2016
• Issued: 05/07/2019
• Est. Priority Date: 09/11/2015
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google LLC (Alphabet Inc.)
• Inventors: Bozkaya, Tolga, Dijamco, Armand Joseph
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US15/261,556
• Publication Number:
  US 20170075891A1
• Time in Patent Office: 970 Days
• Field of Search: 707722
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems

Abstract

One of the methods includes, obtaining a natural language query from a user; while converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base: responsive to detecting a linguistic ambiguity associated with the converting, wherein the linguistic ambiguity identifies two or more interpretations of a word included in the natural langue query: resolving the linguistic ambiguity by selecting an interpretation of the word, from the two or more interpretations of the word, based on one or more join paths that have been generated based on a data schema of the knowledge base; modifying the converting in accordance with the selected interpretation of the word, to generate one or more structured operations; performing the one or more structured operations on the structured APIs of the knowledge base; and returning search results matching the natural language query results to the user.

Claims

1. A Method comprising:

obtaining a natural language query from a user;

converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base, including;

identifying one or more tokens in the natural language query;

generating a tree specifying dependency relationships among the identified tokens in the natural language query;

generating a graph based on the tree and a data schema of the knowledge base, the graph having multiple join paths that each specify a directional relationship among elements within the knowledge base that correspond to the identified tokens in the natural language query;

responsive to detecting a linguistic ambiguity due to the inclusion of a particular identified token in multiple join paths in the graph, wherein a token included in the natural language query has two or more interpretations;

resolving the linguistic ambiguity by selecting one of the multiple join paths specified by the graph, wherein the selected join path corresponds to an interpretation of the token from among the two or more interpretations of the token;

using the natural language query in accordance with the selected interpretation of the token, to generate one or more structured operations;

identifying search results by performing the one or more structured operations on the structured APIs of the knowledge base; and

returning the search results to the user in response to the natural language query;

wherein the knowledge base is implemented on one or more computers and one or more storage devices storing instructions to produce operation results based on structured operations; and

wherein the knowledge base stores information associated with entities according to the data schema and has the APIs for programs to query the knowledge base.

2. The method of claim 1, wherein the join path includes identifiers of at least two tables that share a common column.

3. The method of claim 2, wherein the join path further includes one or more identifiers of the common column.

4. The method of claim 3, wherein resolving the linguistic ambiguity by selecting an interpretation of the token, from the two or more interpretations of the token, based on the multiple join paths specified by the graph includes:

determining that the token matches a value specified in a first column of a first table in the at least two tables; and

based on the determining, identifying the token as referring to a value specified in a second column of a second table in the at least two tables.

5. The method of claim 1, wherein converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base includes:

obtaining parser output generated by a parser, the parser output representing the natural language query; and

generating a concept tree in accordance with the parser output, wherein subcontext concept nodes are located on a level of the concept tree that is no closer to the root of the concept tree than any attribute node is.

6. The method of claim 5, wherein obtaining parser output includes processing the natural language query into tokens.

7. The method of claim 5, wherein the structured operations are generated based on the concept tree and the selected interpretation of the token.

8. A computing system comprising:

one or more computers; and

one or more storage units storing instructions that when executed by the one or more computers cause the computing system to perform operations comprising;

obtaining a natural language query from a user;

converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base, including;

identifying one or more tokens in the natural language query;

generating a tree specifying dependency relationships among the identified tokens in the natural language query;

generating a graph based on the tree and a data schema of the knowledge base, the graph having multiple join paths that each specify a directional relationship among elements within the knowledge base that correspond to the identified tokens in the natural language query;

responsive to detecting a linguistic ambiguity due to the inclusion of a particular identified token in multiple join paths in the graph, wherein a token included in the natural language query has two or more interpretations;

resolving the linguistic ambiguity by selecting one of the multiple join paths specified by the graph, wherein the selected join path corresponds to an interpretation of the token, from among the two or more interpretations of the token;

using the natural language query in accordance with the selected interpretation of the token, to generate one or more structured operations;

identifying search results by performing the one or more structured operations on the structured APIs of the knowledge base; and

returning the search results to the user in response to the natural language query;

wherein the knowledge base is implemented on one or more computers and one or more storage devices storing instructions to produce operation results based on structured operations; and

wherein the knowledge base stores information associated with entities according to the data schema and has the APIs for programs to query the knowledge base.

9. The system of claim 8, wherein a join path includes identifiers of at least two tables that share a common column.

10. The system of claim 9, wherein the join path further includes one or more identifiers of the common column.

11. The system of claim 10, wherein resolving the linguistic ambiguity by selecting an interpretation of the token, from the two or more interpretations of the token, based on the multiple join paths specified by the graph includes:

determining that the token matches a value specified in a first column of a first table in the at least two tables; and

based on the determining, identifying the token as referring to a value specified in a second column of a second table in the at least two tables.

12. The system of claim 8, wherein converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base includes:

obtaining parser output generated by a parser based on the natural language query; and

generating a concept tree in accordance with the parser output, wherein subcontext concept nodes are located on a level of the concept tree that is no closer to the root of the concept tree than any attribute node is.

13. The system of claim 12, wherein obtaining parser output includes processing the natural language query into tokens.

14. The system of claim 12, wherein the structured operations are generated based on the concept tree and the selected interpretation of the token.

15. A non-transitory computer storage medium encoded with a computer program, the computer program comprising instructions that when executed by a system cause the system to perform operations comprising:

obtaining a natural language query from a user;

converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base, including;

identifying one or more tokens in the natural language query;

generating a tree specifying dependency relationships among the identified tokens in the natural language query;

generating a graph based on the tree and a data schema of the knowledge base, the graph having multiple join paths that each specify a directional relationship among elements within the knowledge base that correspond to the identified tokens in the natural language query;

responsive to detecting a linguistic ambiguity due to the inclusion of a particular identified token in multiple join paths in the graph, wherein a token included in the natural language query has two or more interpretations;

resolving the linguistic ambiguity by selecting one of the multiple join paths specified by the graph, wherein the selected join path corresponds to an interpretation of the token from among the two or more interpretations of the token;

using the natural language query in accordance with the selected interpretation of the token, to generate one or more structured operations;

identifying search results by performing the one or more structured operations on the structured APIs of the knowledge base; and

returning the search results to the user in response to the natural language query;

wherein the knowledge base is implemented on one or more computers and one or more storage devices storing instructions to produce operation results based on structured operations; and

wherein the knowledge base stores information associated with entities according to the data schema and has the APIs for programs to query the knowledge base.

16. The non-transitory computer storage medium of claim 15, wherein a join path includes identifiers of at least two tables that share a common column.

17. The non-transitory computer storage medium of claim 16, wherein the join path further includes one or more identifiers of the common column.

18. The non-transitory computer storage medium of claim 17, wherein resolving the linguistic ambiguity by selecting an interpretation of the token, from the two or more interpretations of the token, based on the multiple join paths specified by the graph includes:

determining that the token matches a value specified in a first column of a first table in the at least two tables; and

based on the determining, identifying the token as referring to a value specified in a second column of a second table in the at least two tables.

19. The non-transitory computer storage medium of claim 15, wherein converting the natural language query into structured operations to be performed on structured application programming interfaces (APIs) of a knowledge base includes:

obtaining parser output generated by a parser based on the natural language query; and

generating a concept tree in accordance with the parser output, wherein subcontext concept nodes are located on a level of the concept tree that is no closer to the root of the concept tree than any attribute node is.

20. The non-transitory computer storage medium of claim 19, wherein obtaining parser output includes processing the natural language query into tokens.