Mapping natural language to queries using a query grammar

1. A system for providing a search interface for databases, comprising:

a network interface,

a processor, and

a memory, wherein the memory stores instructions executable by the processor to:

generate, based on a string, a set of tokens of a database syntax, wherein the tokens are each matched to a respective fragment of the string;

generate a query graph for the set of tokens using a finite state machine representing a query grammar, wherein nodes of the finite state machine represent token types, directed edges of the finite state machine represent valid transitions between token types in the query grammar, vertices of the query graph correspond to respective tokens of the set of tokens, and directed edges of the query graph represent a transition between two tokens in a sequencing of the tokens, wherein, to generate the query graph, the processor executes the instructions to determine a weight for a directed edge from a source vertex of the query graph corresponding to a first token of the set of tokens to a destination vertex of the query graph corresponding to a second token of the set of tokens, wherein the weight is determined based on a grammar weight of a directed edge from a node of the finite state machine representing a token type of the first token to a node of the finite state machine representing a token type of the second token;

determine, based on the query graph, a sequence of the tokens in the set of tokens to form a database query; and

invoke a search of the database using a query based on the database query to obtain search results.

2. The system of claim 1 , wherein

the weight is determined based on grammar weights of directed edges along the path from the node of the finite state machine representing the token type of the first token to the node of the finite state machine representing the token type of the second token.

3. The system of claim 1 , wherein the memory stores instructions executable by the processor to:

remove one or more directed edges from the query graph to form an acyclic query graph; and

determine, based on the acyclic query graph, the sequence of the tokens in the set of tokens.

4. The system of claim 3 , wherein the memory stores instructions executable by the processor to:

apply an Eades algorithm to the query graph.

5. The system of claim 1 , wherein the memory stores instructions executable by the processor to:

identify a valid start token and a valid end token from the set of tokens based on the query grammar; and

determine a tour of the vertices in the query graph that starts at a vertex corresponding to the valid start token and ends at a vertex corresponding to the valid end token.

6. The system of claim 1 , wherein the memory stores instructions executable by the processor to:

determine tours of the vertices in the query graph; and

select one of the tours that has a largest sum of weights for directed edges of the tour.

7. The system of claim 1 , wherein the memory stores instructions executable by the processor to:

determine that the string and the set of tokens matches a pattern; and

responsive to the match, set a weight of a directed edge of the query graph based on a pattern score associated with the pattern.

8. A method comprising:

receiving a string entered via a user interface;

generating, based on the string, a set of tokens of a database syntax, wherein the tokens are each matched to a respective fragment of the string;

generating a query graph for the set of tokens using a finite state machine representing a query grammar, wherein nodes of the finite state machine represent token types, directed edges of the finite state machine represent valid transitions between token types in the query grammar, vertices of the query graph correspond to respective tokens of the set of tokens, and directed edges of the query graph represent a transition between two tokens in a sequencing of the tokens, wherein generating the query graph includes determining a weight for a directed edge from a source vertex of the query graph corresponding to a first token of the set of tokens to a destination vertex of the query graph corresponding to a second token of the set of tokens, wherein the weight is determined based on a grammar weight of a directed edge from a node of the finite state machine representing a token type of the first token to a node of the finite state machine representing a token type of the second token;

determining, based on the query graph, a sequence of the tokens in the set of tokens to form a database query;

invoking a search of a database using a query based on the database query to obtain search results; and

presenting data based on the search results in the user interface.

9. The method of claim 8 , wherein

the weight is determined based on grammar weights of directed edges along the path from the node of the finite state machine representing the token type of the first token to the node of the finite state machine representing the token type of the second token.

10. The method of claim 8 , wherein determining, based on the query graph, the sequence of the tokens in the set of tokens comprises:

removing one or more directed edges from the query graph to form an acyclic query graph; and

determining, based on the acyclic query graph, the sequence of the tokens in the set of tokens.

11. The method of claim 10 , wherein removing one or more directed edges from the query graph to form the acyclic query graph comprises:

applying an Eades algorithm to the query graph.

12. The method of claim 8 , wherein determining, based on the query graph, the sequence of the tokens in the set of tokens comprises:

identifying a valid start token and a valid end token from the set of tokens based on the query grammar; and

determining a tour of the vertices in the query graph that starts at a vertex corresponding to the valid start token and ends at a vertex corresponding to the valid end token.

13. The method of claim 8 , wherein determining, based on the query graph, the sequence of the tokens in the set of tokens comprises:

determining tours of the vertices in the query graph; and

selecting one of the tours that has a largest sum of weights for directed edges of the tour.

14. The method of claim 8 , comprising:

determining that the string and the set of tokens matches a pattern; and

responsive to the match, setting a weight of a directed edge of the query graph based on a pattern score associated with the pattern.

15. A non-transitory computer-readable storage medium that includes instructions that, when executed by a processor, facilitate performance of operations comprising:

generating, based on a string, a set of tokens of a database syntax, wherein the tokens are each matched to a respective fragment of the string;

generating a query graph for the set of tokens using a finite state machine representing a query grammar, wherein nodes of the finite state machine represent token types, directed edges of the finite state machine represent valid transitions between token types in the query grammar, vertices of the query graph correspond to respective tokens of the set of tokens, and directed edges of the query graph represent a transition between two tokens in a sequencing of the tokens, wherein generating the query graph includes determining a weight for a directed edge from a source vertex of the query graph corresponding to a first token of the set of tokens to a destination vertex of the query graph corresponding to a second token of the set of tokens, wherein the weight is determined based on a grammar weight of a directed edge from a node of the finite state machine representing a token type of the first token to a node of the finite state machine representing a token type of the second token;

determining, based on the query graph, a sequence of the tokens in the set of tokens to form a database query; and

invoking a search of a database using a query based on the database query to obtain search results.

16. The non-transitory computer-readable storage medium of claim 15 , wherein determining, based on the query graph, the sequence of the tokens in the set of tokens comprises:

removing one or more directed edges from the query graph to form an acyclic query graph; and

determining, based on the acyclic query graph, the sequence of the tokens in the set of tokens.

17. The non-transitory computer-readable storage medium of claim 15 , wherein determining, based on the query graph, the sequence of the tokens in the set of tokens comprises:

identifying a valid start token and a valid end token from the set of tokens based on the query grammar; and

determining a tour of the vertices in the query graph that starts at a vertex corresponding to the valid start token and ends at a vertex corresponding to the valid end token.