Boots – shoes – and leggings
Patent
1993-09-10
1995-11-28
Huntley, David M.
Boots, shoes, and leggings
36441908, 395 51, G06F 1730
Patent
active
054716110
DESCRIPTION:
BRIEF SUMMARY
MICROFICHE APPENDIX
A Microfiche Appendix is included as part of this patent application. The Microfiche Appendix has two microfiche having a total of 174 frames of computer program listings.
1. Field of the Invention
This invention relates to the retrieval of information from database systems.
2. Background of the Invention
Query languages for database systems are already known, falling into two broad classes. In one class the user is required to input a query requesting retrieval of information stored in a computer memory database system in a specialized formal computer language (such as SQL or QUEL) in which case the user is restricted to that group of persons conversant with the relevant formal computer language. In the second class the user may use his own natural language to input his query and in this case the database system incorporates an "intelligent interface" to transform the natural language query to the relevant formal computer language.
Unfortunately, when a user is free to present a particular query in his own natural language he can do so in a variety of different ways each of which the user perceives as being correct. Due to volume, it is not a practical matter for the "intelligent interface" simply to store in memory each possible query and each possible manner of presentation of each query to provide a corresponding codified output to the remainder of the computer memory system. For a wide range of problems however, and in semantic terms for a particular query, each manner of presentation contains in common a list of items of interest to the user and which are also contained in the computer memory system, and if these items are mapped onto the schema (the nodes of a conceptual graph representing the database) the shortest possible connection, having the minimum total length, effectively represents the query. The problem of finding the shortest connection is known as the Steiner Problem in Graphs and the answer (being the shortest connection) is known as the Steiner Tree. Identification of the Steiner Tree is known to be a problem of great computational complexity because it is exponential with the number of nodes in the query set, and with the square of the number of nodes in the database. A known form of "intelligent interface" as described in the article entitled "Resolving the Query Inference Problem using Steiner Trees" by J. A. Wald and P. G. Sorenson, published in ACM Transactions on Database Systems, Vol.9, No. 3, September 1984, incorporates a means of solving the Steiner Problem only where the conceptual graph is restricted in extent.
OBJECT AND SUMMARY OF THE INVENTION
It is an object of the present invention to provide a computer system for retrieving information from a database and having a new and improved means of solving the Steiner Problem.
According to the present invention there is provided a computer system for retrieving data stored in a database. The computer system has an input device arranged to input a natural language query from a user thereof, an intelligent interface device connected to the input device to responsively transform a natural language query received from the input device to a formal computer language of the computer system, the intelligent interface device being arranged to connect to a database and having means for solving a Steiner Problem wherein a conceptual graph representing a database is unrestricted, and means for transmitting data representative of a Steiner Tree to a database. The Steiner Problem solving means of the intelligent interface device includes means for identifying N nodes in a query set, means in communication with the identifying means for storing a collection of N triple-part markers at each node of a conceptual graph of a database, each of the N triple-part markers including a first-part having an initial node identity, a second-part having an indication of cost to the triple-part marker in traversing between adjacent nodes, and a third-part having a pointer to a link between adjacent nodes immediately and previously
REFERENCES:
patent: 4606002 (1986-08-01), Waisman et al.
patent: 5201046 (1993-04-01), Goldberg et al.
patent: 5295261 (1994-03-01), Simonetti
"Automatic Logical Navigation Among Relations Using Steiner Trees", Dept. of Computing Science, pp. 582-588, 1989.
"Resolving the Query Inference Problem Using Steiner Trees", by Joseph A. Wald & Paul G. Sorenson, pp. 348-368, Sep. 1984.
Huntley David M.
Tkacs Stephen R.
University of Strathclyde
LandOfFree
Computerised information-retrieval database systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computerised information-retrieval database systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computerised information-retrieval database systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2020677