Question answering framework for structured query languages

• US 8,996,555 B2
• Filed: 11/26/2012
• Issued: 03/31/2015
• Est. Priority Date: 11/26/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Kuchmann-Beauger, Nicolas, Brauer, Falk
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US13/685,290
• Publication Number:
  US 20140149446A1
• Time in Patent Office: 855 Days
• Field of Search: 704/9, 704/4, 704/1, 704/10, 704/7, 704/270.1, 704/3, 704/8, 704/E15.047, 704/E17.002, 704/200, 704/201, 704/248, 704/253, 704/256, 700/17, 700/83, 700/19, 700/20, 700/65, 700/86, 700/87, 700/1, 700/18, 700/33, 700/66, 700/79, 700/80, 700/94, 707/999.003, 707/999.005, 707/E17.058, 707/E17.078, 707/999.102, 707/999.2, 707/E17.006, 707/E17.084, 707/999.001, 707/E17.014, 707/E17.108, 707/756, 707/758, 707/771, 707/999.006, 707/999.01, 707/E17.005, 707/E17.074, 707/706, 707/713, 707/723, 707/739, 707/748, 707/755, 707/769, 707/999.002, 707/999.004, 707/999.009, 707/999.101, 707/999.104, 707/E17.002, 707/E17.015, 707/E17.017, 707/E17.045, 707/E17.046, 707/E17.054, 707/E17.066, 707/E17.067, 707/E17.068, 707/E17.069, 707/E17.089, 707/E17.109, 707/E17.111, 707/E17.116, 707/E17.119, 707/715, 707/722, 707/728, 707/731, 707/732, 707/736, 707/737, 707/740, 707/741, 707/759, 707/760, 707/770, 707/776, 707/784, 707/811, 707/812, 705/2, 705/14.66, 705/14.14, 705/14.23, 705/14.27, 705/14.41, 705/14.46, 705/14.53, 705/14.71, 705/14.73, 705/1.1, 705/26.1, 705/28, 705/30, 705/305, 705/31, 705/32, 705/34, 705/35, 705/36.R, 705/37, 705/39, 705/400
• US Class Current: 707/763
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

A framework for a question and answering (Q&A) system defines a mapping of recognized semantics of user questions, to a well structured query model that can be executed on arbitrary data warehouses. Embodiments may utilize a plugin-based architecture, with various elements responsible for: extracting information from a user'"'"'s question, formulating and executing a structured query, and post-processing a result by rendering a chart. Plugins within a certain processing step may be executed independently of one another, imparting a significant degree of parallelism. The framework may build on top of natural language processing technologies, and in particular embodiments may be based upon established standards (e.g. RDF and SparQL) thereby allowing adaptation to a variety of domains and use cases.

Claims

1. A computer-implemented method comprising:

causing an answering system to receive a user query posed in a natural language to a database;

causing the answering system to derive semantics from the user query and create a parse graph, wherein the semantics comprise a first dimension and a second dimension;

perform normalization and transformation of the semantics;

imposing constraints on the semantics to create artifacts by proposing a related measure connecting the first dimension and the second dimension in a database table;

mapping the artifacts into a plurality of structured queries;

ranking the plurality of structured queries according to a first scoring function considering a selectivity of the related measure, and a second scoring function considering a complexity of the structured query such that a more complex query structure indicates a higher relevance, a third scoring function comprising a confidence measure based on text retrieval metrics, and a fourth scoring function comprising a popularity of the first dimension, the second dimension, and the related measure; and

executing the plurality of structured queries on the database according to the ranking.

2. A method as in claim 1 wherein the answering system comprises an information extraction plugin configured to derive the semantics from the user query.

3. A method as in claim 1 wherein the answering system comprises a search plugin configured to:

recognize certain semantics from the parse graph; and

create the plurality of structured queries from the certain semantics.

4. A method as in claim 3 wherein the parse graph is captured in Resource Description Framework (RDF) form by the search plugin, and the plurality of structured queries are created in the SparQL query language.

5. A method as in claim 4 wherein the search plugin is written in Java.

6. A method as in claim 1 wherein the answering system further comprises a post processing plugin configured to render a chart for an executed query result.

7. A method as in claim 1 wherein each of the plurality of structured queries comprises a data source, a set of dimensions and measures, and a set of filters.

8. A non-transitory computer readable storage medium embodying a computer program for performing a method, said method comprising:

causing an answering system to receive a user query posed in a natural language to a database;

causing the answering system to derive semantics from the user query and create a parse graph, wherein the semantics comprise a first dimension and a second dimension;

perform normalization and transformation of the semantics;

imposing constraints on the semantics to create artifacts by proposing a related measure connecting the first dimension and the second dimension in a database table;

mapping the artifacts into a plurality of structured queries;

ranking the plurality of structured queries according to a first scoring function considering a selectivity of the related measure, a second scoring function considering a complexity of the structured query such that a more complex query structure indicates a higher relevance, a third scoring function comprising a confidence measure based on text retrieval metrics, and a fourth scoring function comprising a popularity of the first dimension, the second dimension, and the related measure; and

executing the plurality of structured queries on the database according to the ranking.

9. A non-transitory computer readable storage medium as in claim 8 wherein the answering system comprises an information extraction plugin configured to derive the semantics from the user query.

10. A non-transitory computer readable storage medium as in claim 8 wherein the answering system comprises a search plugin configured to:

recognize certain semantics from the parse graph; and

create the plurality of structured queries from the certain semantics.

11. A non-transitory computer readable storage medium as in claim 10 wherein the parse graph is captured in Resource Description Framework (RDF) form by the search plugin, and the plurality of structured queries are created in the SparQL query language.

12. A non-transitory computer readable storage medium as in claim 11 wherein the search plugin is written in Java.

13. A non-transitory computer readable storage medium as in claim 8 wherein the answering system further comprises a post-processing plugin configured to render a chart for an executed query result.

14. A non-transitory computer readable storage medium as in claim 8 wherein each of the plurality of structured queries comprises a data source, a set of dimensions and measures, and a set of filters.

15. A computer system comprising:

one or more processors;

a software program, executable on said computer system, the software program configured to;

cause an answering system to receive a user query posed in a natural language to a database;

cause the answering system to derive semantics from the user query and create a parse graph, wherein the semantics comprise a first dimension and a second dimension;

perform normalization and transformation of the semantics;

impose constraints on the semantics to create artifacts by proposing a related measure connecting the first dimension and the second dimension in a database table;

map the artifacts into a plurality of structured queries;

rank the plurality of structured queries according to a first scoring function considering a selectivity of the related measure, a second scoring function considering a complexity of the structured query such that a more complex query structure indicates a higher relevance, a third scoring function comprising a confidence measure based on text retrieval metrics, and a fourth scoring function comprising a popularity of the first dimension, the second dimension, and the related measure; and

execute the plurality of structured queries on the database according to the ranking.

16. A computer system as in claim 15 wherein the answering system comprises an information extraction plugin configured to derive the semantics from the user query.

17. A computer system as in claim 15 wherein the answering system comprises a search plugin configured to:

recognize certain semantics from the parse graph; and

create the plurality of structured queries from the certain semantics.

18. A computer system as in claim 17 wherein the parse graph is captured in Resource Description Framework (RDF) form by the search plugin, and the plurality of structured queries are created in the SparQL query language.

19. A computer system as in claim 18 wherein the search plugin is written in Java.

20. A computer system as in claim 15 wherein the answering system further comprises a post-processing plugin configured to render a chart for an executed query result.