Patent ID: 6993475

Claim:
A method for preprocessing a natural language database query, the method comprising: a) accepting an alphanumeric string related to the query; b) parsing the alphanumeric string to generate query words; c) determining whether any of the query words, or any phrases formed by at least two adjacent query words, match any of a plurality of indexed annotations; d) if a query word or phrase matches one or more of the plurality of indexed annotations, for each of the plurality of indexed annotations, adding a pattern associated with the indexed annotation to a group associated with the query word or phrase; e) selecting a pattern from each group of patterns to generate a selection of patterns, wherein the pattern may include an object which may be bound to a set of rows or unbound, and wherein two patterns may be unified if they have objects having the same defined type; and f) combining the patterns of the selection of patterns to generate a single, connected, lowest cost pattern, wherein, in the act of combining the patterns of the selection of patterns to generate a single, connected, lowest cost pattern, includes: i) determining start states by determining all possible selections, ii) applying a cost heuristic, based on a database schema, to each of the states, iii) selecting a lowest cost state, and iv) until a single, connected, pattern is found, A) generating successor states of the selected lowest cost state, wherein the act of generating successor states of the selected lowest cost state, includes: for each pair of patterns in the selected state, determining possible actions and their costs, wherein the possible actions include a unify entity action, a unify relationship action, and a link patterns via a path action; and pruning actions based on their costs B) applying a cost heuristic, based on the database schema, to each of the successor states, C) estimating a cost for each of the successor states, D) adding the successor states to a queue of all states, and E) selecting a new lowest cost state from the queue of all states.