CONSTRUCTING STRUCTURED DATABASE QUERY LANGUAGE STATEMENTS FROM NATURAL LANGUAGE QUESTIONS

• US 20200134032A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Lin, Yishu, Gao, Wenxuan, Zhang, Weidong, Hong, Jimmy, Surlaker, Kapil
• Granted Patent: US 10,872,083 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• 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/2456 Join operations
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

Computer-implemented techniques for constructing structured database query language statements from natural language questions are disclosed. In some embodiments, a knowledge graph-based approach is employed to construct a structured database query language statement such as, for example, a Structure Query Language (SQL) statement, from a natural language question. The approach encompasses a domain knowledge graph model and a database schema wiring model. The domain knowledge graph model represents domain-specific knowledge about the underlying database data in the form of a graph having nodes and directed edges between the nodes. The database schema wiring model maps routes in the domain knowledge graph to database schema elements. The techniques allow a natural language interface system to accurately translate domain-specific natural language questions posed by users to structured database query language statements that can be executed against a structured database to answer the natural language question.

Claims

1. A method, comprising:

obtaining a parse tree of a natural language question;

based on the parse tree, identifying a plurality of routes in a domain knowledge graph, each route of the plurality of routes encompassing one or more respective nodes of the domain knowledge graph;

accessing a predefined set of a plurality of wirings to determine a plurality of coverage wirings for the plurality of routes, each coverage wiring of the plurality of coverage wirings being in the predefined set of the plurality of wirings, each coverage wiring of the plurality of coverage wirings mapping a route in the plurality of routes to a column pair, the column pair pairing a primary key of a respective structured database table with a non-primary key column of the respective structured database table;

constructing a structured database query language statement based on the plurality of coverage wirings; and

causing the structured database query language statement to be executed against a structured database.

2. The method of claim 1, wherein the structured database query language statement is a Structured Query Language (SQL) statement and the structured database is a relational database.

3. The method of claim 1, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph; and

identifying nodes in the domain knowledge graph matched to nodes of the parse tree that are connected in the domain knowledge graph.

4. The method of claim 1, wherein the constructing the structured database query language statement based on the plurality of coverage wirings is based on:

identifying a first route in the domain knowledge graph associated with a first coverage wiring of the plurality of coverage wirings;

identifying a second route in the domain knowledge graph associated with a second coverage wiring of the plurality of coverage wirings;

determining that the first route ends at a same node in the domain knowledge graph that the second route starts from; and

constructing a join relation for inclusion in the structured database query language statement based on;

(a) the non-primary key column of the column pair of the first coverage wiring and (b) the primary key of the column pair of the second coverage wiring.

5. The method of claim 1, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph;

automatically inferring a particular node of the domain knowledge graph based on nodes of the domain knowledge graph to which nodes of the parse tree are matched;

based on the automatically inferring the particular node, adding the particular node to a particular route of the plurality of routes based on the automatically inferring;

wherein, after the adding the particular node to the particular route, the particular route comprises a first node of the domain knowledge graph, a second node of the domain knowledge graph, and the particular node;

wherein the first node of the domain knowledge graph is matched to a node of the parse tree;

wherein the second node of the domain knowledge graph is matched to a node of the parse tree; and

wherein the particular node of the domain knowledge graph is not matched to a node of the parse tree but is automatically inferred to be part of the particular route based on connecting the first node and the second node in the domain knowledge graph via the particular node.

6. The method of claim 1, wherein the plurality of routes is a first plurality of routes;

wherein the natural language question is a first natural language question;

and the identifying the plurality of routes in the domain knowledge graph for the first natural language question based on the parse tree is based on;

obtaining a second plurality of routes in the domain knowledge graph determined for a second natural language question that occurred prior to the first natural language question in a conversation;

identifying one or more preliminary routes in the domain knowledge graph for the first natural language question; and

adding a node from a route of the one or more preliminary routes for the first natural language question to a route of the second plurality of routes for the second natural language question to form a route of the first plurality of routes for the first natural language question.

7. The method of claim 1, wherein each node of the domain knowledge graph represents an entity, an action, or a property;

and wherein a node of the domain knowledge graph is associated with a lexicon, the lexicon for the node specifying a name or alias for the node.

8. One or more non-transitory computer-readable media storing one or more programs for execution by a computing system having one or more processors and storage media, the one or more programs comprising instructions configured for:

obtaining a parse tree of a natural language question;

based on the parse tree, identifying a plurality of routes in a domain knowledge graph, each route of the plurality of routes encompassing one or more respective nodes of the domain knowledge graph;

accessing a predefined set of a plurality of wirings to determine a plurality of coverage wirings for the plurality of routes, each coverage wiring of the plurality of coverage wirings being in the predefined set of the plurality of wirings, each coverage wiring of the plurality of coverage wirings mapping a route in the plurality of routes to a column pair, the column pair pairing a primary key of a respective structured database table with a non-primary key column of the respective structured database table;

constructing a structured database query language statement based on the plurality of coverage wirings; and

causing the structured database query language statement to be executed against a structured database.

9. The one or more non-transitory computer-readable media of claim 8, wherein the structured database query language statement is a Structured Query Language (SQL) statement and the structured database is a relational database.

10. The one or more non-transitory computer-readable media of claim 8, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph; and

identifying nodes in the domain knowledge graph matched to nodes of the parse tree that are connected in the domain knowledge graph.

11. The one or more non-transitory computer-readable media of claim 8, wherein the constructing the structured database query language statement based on the plurality of coverage wirings is based on:

identifying a first route in the domain knowledge graph associated with a first coverage wiring of the plurality of coverage wirings;

identifying a second route in the domain knowledge graph associated with a second coverage wiring of the plurality of coverage wirings;

determining that the first route ends at a same node in the domain knowledge graph that the second route starts from; and

constructing a join relation for inclusion in the structured database query language statement based on;

(a) the non-primary key column of the column pair of the first coverage wiring and (b) the primary key of the column pair of the second coverage wiring.

12. The one or more non-transitory computer-readable media of claim 8, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph;

automatically inferring a particular node of the domain knowledge graph based on nodes of the domain knowledge graph to which nodes of the parse tree are matched;

based on the automatically inferring the particular node, adding the particular node to a particular route of the plurality of routes based on the automatically inferring;

wherein, after the adding the particular node to the particular route, the particular route comprises a first node of the domain knowledge graph, a second node of the domain knowledge graph, and the particular node;

wherein the first node of the domain knowledge graph is matched to a node of the parse tree;

wherein the second node of the domain knowledge graph is matched to a node of the parse tree; and

wherein the particular node of the domain knowledge graph is not matched to a node of the parse tree but is automatically inferred to be part of the particular route based on connecting the first node and the second node in the domain knowledge graph via the particular node.

13. The one or more non-transitory computer-readable media of claim 8, wherein the plurality of routes is a first plurality of routes;

wherein the natural language question is a first natural language question; and

the identifying the plurality of routes in the domain knowledge graph for the first natural language question based on the parse tree is based on;

obtaining a second plurality of routes in the domain knowledge graph determined for a second natural language question that occurred prior to the first natural language question in a conversation;

identifying one or more preliminary routes in the domain knowledge graph for the first natural language question; and

adding a node from a route of the one or more preliminary routes for the first natural language question to a route of the second plurality of routes for the second natural language question to form a route of the first plurality of routes for the first natural language question.

14. The one or more non-transitory computer-readable media of claim 8, wherein each node of the domain knowledge graph represents an entity, an action, or a property;

and wherein a node of the domain knowledge graph is associated with a lexicon, the lexicon for the node specifying a name or alias for the node.

15. A computing system, comprising:

one or more processors;

storage media; and

one or more programs stored in the storage media and configured for execution by the one or more processors, the one or more programs comprising instructions configured for;

obtaining a parse tree of a natural language question;

based on the parse tree, identifying a plurality of routes in a domain knowledge graph, each route of the plurality of routes encompassing one or more respective nodes of the domain knowledge graph;

accessing a predefined set of a plurality of wirings to determine a plurality of coverage wirings for the plurality of routes, each coverage wiring of the plurality of coverage wirings being in the predefined set of the plurality of wirings, each coverage wiring of the plurality of coverage wirings mapping a route in the plurality of routes to a column pair, the column pair pairing a primary key of a respective structured database table with a non-primary key column of the respective structured database table;

constructing a structured database query language statement based on the plurality of coverage wirings; and

causing the structured database query language statement to be executed against a structured database.

16. The computing system of claim 15, wherein the structured database query language statement is a Structured Query Language (SQL) statement and the structured database is a relational database.

17. The computing system of claim 15, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph; and

identifying nodes in the domain knowledge graph matched to nodes of the parse tree that are connected in the domain knowledge graph.

18. The computing system of claim 15, wherein the constructing the structured database query language statement based on the plurality of coverage wirings is based on:

identifying a first route in the domain knowledge graph associated with a first coverage wiring of the plurality of coverage wirings;

identifying a second route in the domain knowledge graph associated with a second coverage wiring of the plurality of coverage wirings;

determining that the first route ends at a same node in the domain knowledge graph that the second route starts from; and

constructing a join relation for inclusion in the structured database query language statement based on;

(a) the non-primary key column of the column pair of the first coverage wiring and (b) the primary key of the column pair of the second coverage wiring.

19. The computing system of claim 15, wherein the identifying the plurality of routes in the domain knowledge graph based on the parse tree is based on:

traversing nodes of the parse tree;

matching nodes of the parse tree to nodes of the domain knowledge graph;

automatically inferring a particular node of the domain knowledge graph based on nodes of the domain knowledge graph to which nodes of the parse tree are matched;

based on the automatically inferring the particular node, adding the particular node to a particular route of the plurality of routes based on the automatically inferring;

wherein, after the adding the particular node to the particular route, the particular route comprises a first node of the domain knowledge graph, a second node of the domain knowledge graph, and the particular node;

wherein the first node of the domain knowledge graph is matched to a node of the parse tree;

wherein the second node of the domain knowledge graph is matched to a node of the parse tree; and

wherein the particular node of the domain knowledge graph is not matched to a node of the parse tree but is automatically inferred to be part of the particular route based on connecting the first node and the second node in the domain knowledge graph via the particular node.

20. The computing system of claim 15, wherein the plurality of routes is a first plurality of routes;

wherein the natural language question is a first natural language question; and

the identifying the plurality of routes in the domain knowledge graph for the first natural language question based on the parse tree is based on;

obtaining a second plurality of routes in the domain knowledge graph determined for a second natural language question that occurred prior to the first natural language question in a conversation;

identifying one or more preliminary routes in the domain knowledge graph for the first natural language question; and

adding a node from a route of the one or more preliminary routes for the first natural language question to a route of the second plurality of routes for the second natural language question to form a route of the first plurality of routes for the first natural language question.

21. The computing system of claim 15, wherein each node of the domain knowledge graph represents an entity, an action, or a property;

and wherein a node of the domain knowledge graph is associated with a lexicon, the lexicon for the node specifying a name or alias for the node.