Natural language querying with cascaded conditional random fields

• US 9,280,535 B2
• Filed: 05/26/2011
• Issued: 03/08/2016
• Est. Priority Date: 03/31/2011
• Status: Active Grant

• Current Assignee: Infosys Limited
• Original Assignee: Infosys Limited
• Inventors: Varma, Kishore Indukuri, Krishnamoorthy, Srikumar, Pisipati, Radha Krishna
• Primary Examiner(s): Somers, Marc
• Application Number:
  US13/117,077
• Publication Number:
  US 20120254143A1
• Time in Patent Office: 1,748 Days
• Field of Search: 707/760, 707/776
• US Class Current: 1/1
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A natural language query tool comprising cascaded conditional random fields (CRFs) (e.g., a linear-chain CRF and a skip-chain CRF applied sequentially) processes natural language input to produce output that can be used in database searches. For example, cascaded CRFs extract entities from natural language input that correspond to column names or column values in a database, and identify relationships between the extracted entities. A search engine can execute queries based on output from the cascaded CRFs over an inverted index of a database, which can be based on one or more materialized views of the database. Results can be sorted (e.g., according to relevance scores) and presented in a user interface.

Claims

1. A computer-implemented method, comprising:

receiving natural language input at a computing device;

processing the natural language input to generate an output, by;

processing the natural language input in a first conditional random field to obtain a first stage output from the first conditional random field, the processing in the first conditional random field comprises;

extracting at least a first entity and a second entity from the natural language input, wherein the first entity and the second entity appear separately in a natural language query expressed with the received natural language input, and at least one of the first entity and the second entity identifies a column name of a database table; and

labeling the first entity as a database column value for the database table, and labeling the second entity as a database column name for the database table, the first stage output comprising a database column value label associated with the first entity and a database column name label associated with the second entity; and

after processing the natural language input in the first conditional random field, processing the natural language input and the first stage output in a second conditional random field to obtain a second stage output from the second conditional random field, the processing in the second conditional random field comprising identifying at least one relationship between the first entity and the second entity in the first stage output, the second stage output comprising information that represents the at least one relationship,

wherein the output comprises the first stage output and the second stage output; and

forming a search query based at least in part on the output, wherein forming the query comprises determining a query type, wherein the query type is at least one of a range query, a logical query, a join query, or an aggregate query, and wherein the query is based at least in part on the query type.

2. The method of claim 1, wherein the second entity corresponds to a column in a database table.

3. The method of claim 2, wherein the first entity corresponds to a value in the column in the database table.

4. The method of claim 1, further comprising representing the at least one relationship as an edge between two nodes in a graph.

5. The method of claim 4, wherein the information that represents the at least one relationship comprises a start tag associated with one of the two nodes and an end tag associated the other of the two nodes.

6. The method of claim 4, wherein the second conditional random field is a skip-chain conditional random field, and wherein the edge is a skip-edge.

7. The method of claim 4, wherein a first node of the two nodes is associated with the column name label, and wherein a second node of the two nodes is associated with the column value label.

8. The method of claim 1, further comprising:

sending the query to a search engine; and

receiving database search results from the search engine in response to the query.

9. The method of claim 8, further comprising assigning relevance scores to the database search results.

10. The method of claim 9, further comprising:

determining a match type for each of the database search results; and

assigning a weight based at least in part on the respective match types, wherein the assigned relevance score for the respective database search results is based at least in part on the assigned weight.

11. The method of claim 9, further comprising determining an ordered set of search results based at least in part on the respective relevance scores.

12. The method of claim 1, wherein forming the search query is based at least in part on database metadata associated with at least one materialized view.

13. The method of claim 1, wherein determining the query type comprises applying one or more heuristic rules to the natural language input to identify one or more patterns in the natural language input that indicate the query type.

14. The method of claim 1, wherein the one or more heuristic rules comprise a heuristic rule that identifies one or more patterns in the natural language input that indicates quantitative comparisons.

15. The method of claim 1, wherein the one or more heuristic rules comprise a heuristic rule that identifies one or more patterns in the natural language input comprising one or more logical operators.

16. The method of claim 1, wherein the one or more heuristic rules comprise a heuristic rule that identifies one or more patterns in the natural language input comprising terms that indicate plural database tables, the method further comprising creating a materialized view for each of the plural database tables, wherein the join query is performed on the materialized views.

17. The method of claim 1, wherein the query comprises a combination of plural query types.

18. The method of claim 1, further comprising assigning part-of-speech tags to terms in the natural language input, wherein the extracting is based at least in part on the part-of-speech tags.

19. The method of claim 1, further comprising assigning relevance scores to database search results based at least in part on the first output and the second output.

20. One or more non-transitory computer-readable storage media having stored thereon computer-executable instructions which when executed by a computer cause the computer to perform a method, the method comprising:

receiving natural language input at a computing device;

processing the natural language input in cascaded conditional random fields comprising a linear-chain conditional random field and a skip-chain conditional random field to obtain an output from the cascaded conditional random fields, wherein;

the linear-chain conditional random field is used to extract entity information;

the skip-chain conditional random field is used to extract relationship information; and

the skip-chain conditional random field is sequential to the linear-chain conditional random field so that an output of the linear-chain conditional random field is an input to the skip-chain conditional random field, wherein the linear-chain conditional random field and the skip-chain conditional random field are trained using a training dataset comprising entity labels and relationship labels; and

based on the output from the cascaded conditional random fields, forming a database query, wherein forming the query comprises determining a query type, wherein the query type is at least one of a range query, a logical query, a join query, or an aggregate query, and wherein the query is based at least in part on the query type.

21. The computer-readable storage media of claim 20, the method further comprising executing the database query on an inverted index of a database.

22. The computer-readable storage media of claim 21, wherein the inverted index is based on one or more materialized views of the database.

23. The computer-readable storage media of claim 22, the method further comprising presenting query suggestions in the user interface.

24. The computer-readable storage media of claim 20, the method further comprising:

receiving results in response to the database query;

sorting the received results according to relevance scores; and

presenting sorted results in a user interface.

25. The computer-readable storage media of claim 20, wherein the output comprises entity information and relationship information.

26. A computing device comprising one or more processors, one or more output devices, and one or more computer-readable storage media having stored therein computer-executable instructions for performing a method, the method comprising:

receiving natural language input at the computing device via a user interface, the natural language input comprising plural terms;

assigning a part-of-speech tag to each of the plural terms in the natural language input;

processing the natural language input and the part-of-speech tags in a linear-chain conditional random field to obtain a first output from the linear-chain conditional random field, the first output comprising a database column value label and a database column name label, the database column value label indicating that a first term in the natural language input corresponds to a column value in a database, and the database column name label indicating that a second term in the natural language input corresponds to a column name in the database, wherein the first term and the second term appear separately within the natural language input;

processing the natural language input and the first output in a skip-chain conditional random field to obtain a second output from the skip-chain conditional random field, the second output comprising relationship information that associates the first term corresponding to the column value in the database with the second term corresponding to the column name in the database;

forming a search string based at least in part on the first output, wherein forming the search string comprises determining a query type, wherein the query type is at least one of a range query, a logical query, a join query, or an aggregate query, and wherein the search string is based at least in part on the query type;

sending the search string to a search engine;

receiving search results identified in the database by the search engine based at least in part on the search string;

ordering the search results based on relevance scores for the respective search results, the relevance scores based at least in part on the first output and the second output; and

presenting the ordered search results in the user interface.