×

Methods, apparatus, and data structures for facilitating a natural language interface to stored information

  • US 6,993,475 B1
  • Filed: 05/03/2000
  • Issued: 01/31/2006
  • Est. Priority Date: 05/03/2000
  • Status: Expired due to Term
First Claim
Patent Images

1. 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.

View all claims
  • 3 Assignments
Timeline View
Assignment View
    ×
    ×