Computerised information-retrieval database systems

• US 5,471,611 A
• Filed: 09/10/1993
• Issued: 11/28/1995
• Est. Priority Date: 03/13/1991
• Status: Expired due to Fees

• Current Assignee: University of Strathcylde
• Original Assignee: University of Strathclyde
• Inventors: McGregor, Douglas R.
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Tkacs, Stephen R.
• Application Number:
  US08/117,106
• Time in Patent Office: 809 Days
• Field of Search: 364/419.08, 364/419.19, 395/10, 395/12, 395/51, 395/52, 395/600
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An information-retrieval system comprises a workstation having an input device and an output device. The workstation is connected to an intelligent interface which in turn is connected to a date base memory system. The interface comprises a lexical analyzer, a semantic associator, a query code generator and an output formatter. The user inputs a query as an ordered stream of characters in natural language (e.g., English or German). The lexical analyzer partitions the character stream into sections which are then compared with and matched against the contents of a look-up table held in a local memory and if a match is located, converted to a single token record for transmission to the Semantic Associator. Associator stores all the node/link records and those corresponding to the received tokens are identified to form the initial starting point of the conceptual graph which is operated on by a Steiner Marcher within Associator in order to identify the Steiner Tree which is then interpreted link by link by the code generator. The query in coded form is then delivered to the DBMS which delivers its consequential output to the formatter which formats the answer to the query for presentation to the user on the display device.

Claims

1. A computer system for retrieving data stored in a database, the computer system comprising:

an input device arranged to input a natural language query from a user thereof; and

an intelligent interface device connected to said input device to responsively transform a natural language query received from said input device to a formal computer language of the computer system, said intelligent interface device having means for solving a Steiner Problem wherein a conceptual graph representing a database is unrestricted, said Steiner Problem solving means comprising;

means for identifying N nodes in a query set received from the database responsive to the natural language query received from said input device,

means in communication with said identifying means for storing a collection of N triple-part markers at each node of a conceptual graph of the database, each of said N triple-part markers including a first-part having an initial node identity, a second-part having an indication of cost to said triple-part marker in traversing between adjacent nodes, and a third-part having a pointer to a link between adjacent nodes immediately and previously traversed by said triple-part marker, and wherein said collection of N triple-part markers initially comprises N triple-part markers having said first-part identifying each of the N nodes, the respective said second-part and said third-part for N-1 of said N triple-part markers being an undefined value, and a remaining triple-part marker of said N triple-part markers having the respective said second-part and said third-part thereof set to zero, said remaining triple-part marker having an initial node identity identifying the node at which said collection is stored,

means in communication with each node for storing global values which are available to each node, said global values being a node identifier to identify a current root of that node with all said second-parts being defined wherein the accumulated value for said second

part of said triple-part marker is a current minimum,

means in communication with said global value storing means for initializing the current root of the identified node to null and for initializing the current minimum of said second-part of said triple-part marker to a maximum value,

means in communication with each of the nodes for transmitting data messages from each of the nodes to each immediately adjacent node via respective links therebetween and having a traverse cost of which is proportional to a length of the respective links,

means at each adjacent node in communication with said transmitting means for receiving said data messages, each received data message containing a duplicate of all said triple-part markers stored in a transmitting node with respective said second-parts of said triple-part markers equal to a previous cost of said second-part markers and with respective said third-parts of said triple-part markers identifying the link traversed by that marker,

means in communication with said receiving means and said marker storing means for iteratively comparing received and stored triple-part markers responsive to an initial node identity, the comparison being between the respective second-parts of said triple-part markers to identify and discard those received triple-part markers of greater cost than the stored triple-part markers, other than when said second-part of the stored triple-part marker is undefined, and with a predetermined number of received triple-part markers in each iterative comparison equally sharing an additional traverse cost of a particular link, and for storing a collection of N markers which are respectively of least defined cost responsive to termination of an iteration,

means in communication with said comparing means for updating the current minimum and the current root when any one node has N triple

part markers each having a defined second-part and having an aggregate cost value less than the previously stored value of the current minimum,

means in communication with said updating means for initiating data message transmission from a node on each occurrence of a change in a stored collection of triple-part markers at that node and when that node has an accumulated cost value less than the current minimum,

means in communication with said initiating means for identifying when message transmission has been completed for every node, and

means in communication with said completed message identifying means for tracing the traverse of each triple-part marker in a finally identified current root node back to an originating node in order to determine a Steiner Tree.

2. A computer system as defined in claim 1, wherein said third-part of said triple-part marker of said marker storing means initially is zero and said second-part of a triple-part marker of said marker storing means initially is a comparatively corresponding large value.