Answering natural language table queries through semantic table representation

• US 10,191,946 B2
• Filed: 03/11/2015
• Issued: 01/29/2019
• Est. Priority Date: 03/11/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Guggilla, Chinnappa, Majjiga, Prabhakar R., Midde, Praveen K., Polisetty Venkata Sai, Avinesh
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Bartlett, William P
• Application Number:
  US14/644,302
• Publication Number:
  US 20160267117A1
• Time in Patent Office: 1,420 Days
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/24578 using ranking

Abstract

According to one exemplary embodiment, a method for finding an answer to a query from a table is provided. The method may include receiving the query and the table. The method may also include generating a hierarchical representation based on the received table, whereby the hierarchical representation comprises a primary tree and a secondary tree. The method may then include mapping the primary tree to the secondary tree. The method may further include generating a plurality of predicate triples in a semantic relationship form based on the primary tree and the secondary tree. The method may also include determining if a predicate triple within the plurality of predicate triples matches the query using query-side and table-side context and semantics. The method may then include adding the predicate triple within the plurality of predicate triples to a plurality of candidate answers based on determining that the predicate triple matches the query.

Claims

1. A computer system for finding an answer to a query from a table, comprising:

one or more processors, one or more computer-readable memories, one or more computer-readable tangible storage medium, and program instructions stored on at least one of the one or more tangible storage medium for execution by at least one of the one or more processors via at least one of the one or more computer-readable memories, wherein the computer system is capable of performing a method comprising;

receiving the query and the table, wherein the table is derived from a source document containing the table and a plurality of peripheral context data;

receiving a focus associated with the received query;

receiving the plurality of peripheral context data associated with the table, wherein the received plurality of peripheral context data includes data distinct from the table, and wherein the received plurality of peripheral context data is derived from the source document;

generating a primary tree and a secondary tree based on the received table, wherein the primary tree corresponds with a first column of the received table, and wherein the secondary tree corresponds with a second column of the received table, wherein a primary root node of the primary tree corresponds with a first header value of the first column, wherein a secondary root node of the secondary tree corresponds with a second header value of the second column, wherein a plurality of primary child nodes of the primary tree correspond with a plurality of first column cell values, and wherein a plurality of secondary child nodes of the secondary tree correspond with a plurality of second column cell values, and wherein missing header values are represented by a placeholder value;

generating a hierarchical representation based on the generated primary tree and the generated secondary tree;

mapping the primary tree to the secondary tree;

determining that the primary tree or the secondary tree contains a missing value based on identifying the placeholder value in the primary tree or secondary tree;

determining that the plurality of peripheral context data contains a substitute value based on determining that the primary tree or the secondary tree contains the missing value;

inserting the substitute value from the plurality of peripheral context data in place of the missing value;

determining the received focus is not in the primary tree and secondary tree;

mapping the received focus onto the secondary tree based on determining the received focus is not in the primary tree and secondary tree;

generating a plurality of predicate triples based on the primary tree and the secondary tree;

determining if a predicate triple within the plurality of predicate triples matches the query; and

adding the predicate triple within the plurality of predicate triples to a plurality of candidate answers based on determining that the predicate triple matches the query.

2. The computer system of claim 1, wherein generating the primary tree and the secondary tree comprises using a breadth first search (BFS) algorithm.

3. The computer system of claim 1, wherein determining if the predicate triple within the plurality of predicate triples matches the query comprises using a string similarity metric.

4. The computer system of claim 1, wherein the primary tree is a pivot tree and the secondary tree is an association tree.

5. The computer system of claim 1, wherein mapping the primary tree to the secondary tree comprises using a depth first search (DFS) algorithm in left-to-right order.

6. The computer system of claim 1, wherein the table comprises a first column and a second column and wherein the primary tree is based on the first column and the secondary tree is based on the second column.

7. A computer program product for finding an answer to a query from a table, comprising:

one or more computer-readable storage medium and program instructions stored on at least one of the one or more computer-readable storage medium, the program instructions executable by a processor, the program instructions comprising;

program instructions to receive the query and the table, wherein the table is derived from a source document containing the table and a plurality of peripheral context data;

program instructions to receive a focus associated with the received query;

program instructions to receive the plurality of peripheral context data associated with the table, wherein the received plurality of peripheral context data includes data distinct from the table, and wherein the received plurality of peripheral context data is derived from the source document;

program instructions to generate a primary tree and a secondary tree based on the received table, wherein the primary tree corresponds with a first column of the received table, and wherein the secondary tree corresponds with a second column of the received table, wherein a primary root node of the primary tree corresponds with a first header value of the first column, wherein a secondary root node of the secondary tree corresponds with a second header value of the second column, wherein a plurality of primary child nodes of the primary tree correspond with a plurality of first column cell values, and wherein a plurality of secondary child nodes of the secondary tree correspond with a plurality of second column cell values, and wherein missing header values are represented by a placeholder value;

program instructions to generate a hierarchical representation based on the generated primary tree and the generated secondary tree;

program instructions to map the primary tree to the secondary tree;

program instructions to determine that the primary tree or the secondary tree contains a missing value based on identifying the placeholder value in the primary tree or secondary tree;

program instructions to determine that the plurality of peripheral context data contains a substitute value based on determining that the primary tree or the secondary tree contains the missing value;

program instructions to insert the substitute value from the plurality of peripheral context data in place of the missing value;

program instructions to determine the received focus is not in the primary tree and secondary tree;

program instructions to map the received focus onto the secondary tree based on determining the received focus is not in the primary tree and secondary tree;

program instructions to generate a plurality of predicate triples based on the primary tree and the secondary tree;

program instructions to determine if a predicate triple within the plurality of predicate triples matches the query; and

program instructions to add the predicate triple within the plurality of predicate triples to a plurality of candidate answers based on determining that the predicate triple matches the query.

8. The computer program product of claim 7, wherein generating the primary tree and the secondary tree comprises using a breadth first search (BFS) algorithm.

9. The computer program product of claim 7, wherein determining if the predicate triple within the plurality of predicate triples matches the query comprises using a string similarity metric.

10. The computer program product of claim 7, wherein the primary tree is a pivot tree and the secondary tree is an association tree.