A domain-independent natural language database interface

Claim 2

A natural language system (10) for interfacing to an entity-relationship database management system (21 said natural language system characterized by: a) a syntactic, domain-independent grammar (16); b) an abstract database navigation language(23); and c) an algorithm (13) that parses natural language input against said grammar (16) to generate said navigation language (23).

Claim 3

The system of claim 1 further including a lexical analyzer means (11) for performing synonym substitution from a synonym lexicon (12) prior to parsing said natural language via said algorithm.

Claim 4

The system of claim 2 wherein said algorithm (13) is implemented in a topdown, backtrack fashion, which draws upon a syntactic grammar (16) and a domain-dependent lexicon (14) and produces database navigation operations (23) as an output.

Claim 5

The system of claim 3 further including a simplifier means (17) responsive to said first database navigation operations (23) for applying meaning preserving topdown rules to produce more concise expressions in the form of said second database navigation operations (24).

Claim 6

The system of claim 4 further including a translator means (18) responsive to said second database navigation operations (24) for outputting database queries (26) in the target database language.

Claim 7

A natural language system (10) for interfacing to an entity-relationship database management system (21 said natural language system characterized by: a lexical analyzer means (11) for performing synonym substitution prior to parsing a natural language input, said analyzer means being interactive with a synonym lexicon means (12); a parser means (13) for parsing the output of said lexical-analyzer means (11) to generate first database navigation operations (23), said parser means being interactive with both a main lexicon means (14) and a grammar means (16); a simplifier means (17) responsive to said first database navigation operations (23) for applying meaning preserving topdown rules to produce expressions in the form of second database navigation operations (24); and a translator means (18) responsive to said second database navigation operations (24) for producing as an output, database queries (26) in the target database language, said translator means being interactive with an augmented database schema means (19).

Claim 8

A natural language system (10) for interfacing to an entity-relationship database management system (21 said natural language system characterized by: a lexical analyzer means (11) for performing synonym substitution prior to parsing a natural language input, said analyzer means being interactive with a synonym lexicon means (12); a parser means (13) for parsing the output of said lexical-analyzer means (11) to generate first database navigation operations (23), said parser means being interactive with both a main lexicon means (14) and a grammar means (16); a simplifier means (17) responsive to said first database navigation operations (23) for applying meaning preserving topdown rules to produce expressions in the form of second database navigation operations (24); and a translator means (18) responsive to said second database navigation operations (24) for producing as an output, database queries (26) in the target database language, said translator means being interactive with an augmented database schema means (19).

Claim 11

The method of claim 7 further including the step of performing synonym substitution (12) prior to the step of parsing.

Claim 12

The method of claim 8 wherein said parsing step is implemented in a topdown, backtrack fashion, drawing upon a syntactic grammar (16) and a domain-dependent lexicon (14).

Claim 13

The method of claim 9 further including the step of simplifying (17) said first database navigation operations to produce second database navigation operations (24).

Claim 14

The method of claim 10 further including the step of translating (18) said second database navigation operations (24) to produce said database queries-(26).

Claim 17

The method of claim 12 wherein said parsing includes the steps of: a) selecting (61) a new transition tree for searching; b) exploring (62) a path in said transition tree; . c) selecting (65) a new path through a subtree of said transition tree; d) backtracking (68) along a path within said transition tree; e) resetting the context (70) after searching said transititon tree; and f) performing semantic tests (72) after finding all applicable paths through said transition tree.

Claim 18

The method of claim 12 wherein said parsing is performed according to the following algorithm, wherein the input is either a Name identifying the grammar goal to be satisfied or Words to be parsed: a) ParseRule: Fetch the transition tree for Name. Enter state TryBranch; b) TryBranch: If no more branches remain in the current tree, then -enter state TryParse. Get the next branch off the tree. If at the end of the Branch, then -perform semantic testing, -build a representation for the parse, if valid, -enter state TryBranch. If the branch can be followed by comsuming a terminal, then -save the context on Substack, -perform the next transition on the branch, consuming input from Words, -set the current tree to the remainder of the branch, -enter state TryBranch. If a subgoal must be satisfied to continue along the branch, then -save the context on Stack, -set Name to the new goal, -enter state ParseRule. Enter state TryBranch; c) TryParse: If a new parse satisfying a previous subgoal can be found, then -select the new parse, -reset the context, including the tree, to the situation obtaining after satisfaction of the subgoal, -enter state TryBranch. Enter state SubPop; d) SubPop: If a saved context exists on SubStack. then -reset the context to the saved one, -enter state TryBranch. Enter state RulePop; e) RulePop: If a saved context exists on Stack, then -reset the context to the saved one, -enter state Semtest. Terminate execution, returning all valid parses found; and f) SemTest: If no parses were found satisfying the most recently postulated subgoal, then -enter state TryBranch. Save the context on SubStack. Perform semantic filtering on the above-mentioned parses. Enter state TryParse.