Computerised information-retrieval database systems

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.