# US 10,872,083 B2 · Constructing structured database query language statements from natural language questions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,872,083 B2 - Document ID: US10872083B2 - Status: Granted - Kind: B2 - Application number: 16/177,026 - Filed: 2018-10-31 - Published: 2020-04-30 - Granted: 2020-12-22 - Earliest claimed: 2018-10-31 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Yishu Lin; Wenxuan Gao; Weidong Zhang; Jimmy Hong; Kapil Surlaker - Web page: https://patentgrep.com/patent/US10872083B2 ## CPC - G06F 16/24522: {Translation of natural language queries to structured queries} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 16/243: {Natural language query formulation} - G06F 16/2456: {Join operations} - G06F 16/284: {Relational databases} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 8) 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. ### Claim 12 (depends on 8) 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. ### Claim 13 (depends on 8) 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. ### Claim 14 (depends on 8) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 15) 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. ### Claim 20 (depends on 15) 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. ### Claim 21 (depends on 15) 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.