NATURAL LANGUAGE QUERYING WITH CASCADED CONDITIONAL RANDOM FIELDS

• US 20120254143A1
• Filed: 05/26/2011
• Published: 10/04/2012
• Est. Priority Date: 03/31/2011
• Status: Active Grant

• Current Assignee: Infosys Limited
• Original Assignee: Infosys Technologies Limited (Infosys Limited)
• Inventors: Krishnamoorthy, Srikumar, Pisipati, Radha Krishna, Varma, Kishore Indukuri
• Granted Patent: US 9,280,535 B2
• Time in Patent Office: Days
• US Class Current: 707/706
• 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 in a first conditional random field to obtain a first output from the first conditional random field, the processing in the first conditional random field comprising extracting at least a first entity and a second entity from the natural language input, labeling the first entity as a column value, and labeling the second entity as a column name, the first output comprising a column value label associated with the first entity and a column name label associated with the second entity;

processing the natural language input and the first output in a second conditional random field to obtain a second 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, the second output comprising information that represents the at least one relationship.

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:

forming a query based at least in part on the first output;

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 wherein forming the query comprises determining a query type, and wherein the query is based at least in part on the query type.

10. The method of claim 9 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.

11. The method of claim 10 wherein the query comprises a range query.

12. The method of claim 11 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.

13. The method of claim 10 wherein the query comprises a logical query.

14. The method of claim 13 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.

15. The method of claim 10 wherein the query comprises a join query.

16. The method of claim 15 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 9 wherein the query comprises an aggregate query.

18. The method of claim 9 wherein the query comprises a combination of plural query types.

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

20. The method of claim 19 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.

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

22. 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.

23. 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.

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

24. One or more 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; and

based on the output from the cascaded conditional random fields, forming a database query.

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

27. The computer-readable storage media of claim 24, 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.

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

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

30. 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 first output from the linear-chain conditional random field, the first output comprising a column value label and a column name label, each label associated with one of the plural terms in the natural language input;

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

forming a search string based at least in part on the first output;

sending the search string to a search engine;

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

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

presenting the ordered database search results in the user interface.