# US 2012/0254143 A1 · Natural language querying with cascaded conditional random fields

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254143 A1
- Document ID: US20120254143A1
- Status: Published application
- Kind: A1
- Application number: 13/117,077
- Filed: 2011-05-26
- Published: 2012-10-04
- Earliest claimed: 2011-03-31
- Assignees: Infosys Technologies Limited
- Inventors: Kishore Indukuri Varma; Srikumar Krishnamoorthy; Radha Krishna Pisipati
- Web page: https://patentgrep.com/patent/US20120254143A1

## CPC

- G06F 40/30: Semantic analysis
- G06F 16/243: {Natural language query formulation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

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

### Claim 4 (depends on 1)

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

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 4)

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.

### Claim 7 (depends on 4)

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.

### Claim 8 (depends on 1)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 10)

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

### Claim 12 (depends on 11)

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.

### Claim 13 (depends on 10)

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

### Claim 14 (depends on 13)

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.

### Claim 15 (depends on 10)

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

### Claim 16 (depends on 15)

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.

### Claim 17 (depends on 9)

The method of claim 9 wherein the query comprises an aggregate query.

### Claim 18 (depends on 9)

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

### Claim 19 (depends on 8)

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

### Claim 20 (depends on 19)

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.

### Claim 21 (depends on 19)

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

### Claim 22 (depends on 1)

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.

### Claim 23 (depends on 1)

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.

### Claim 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.

### Claim 25 (depends on 23)

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

### Claim 26 (depends on 24)

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

### Claim 27 (depends on 24)

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.

### Claim 28 (depends on 26)

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

### Claim 29 (depends on 24)

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

### Claim 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.
