US5600831A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and methods for retrieving information by modifying query plan based on description of information sources
Assignee: Alcatel Lucent SAS
•
Filing: 1994-11-30
•
Granted: 1997-02-04
•
Expires: 2014-11-30
Abstract
Abstract Techniques for optimizing queries in a system in which executing the query requires retrieval of information from a number of different data bases which are accessible via a network. In the techniques, a query results in a query plan which includes subplans for querying the data bases which contain the required information. When a subplan is executed in one of the data bases, the data base returns not only the information which results from the execution of the subplan, but also source and constraint information about the data in the data base. The source and constraint information is then used to optimize the query plan by pruning redundant subplans. An embodiment is disclosed in which queries are made to a domain model implemented using a knowledge base system. The domain model includes a world view of the data, a set of descriptions of the data bases, and a set of descriptions of how to access the data. The information in the domain model is used to formulate the query plan.
Inventors
- 👤 Alon Y. Levy
- 👤 Divesh Srivastava
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 17:23
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/954; G06F16/20; G06F16/24; G06F16/245; G06F16/2452; G06F16/24524; G06F16/2458; G06F16/2471; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
219 words
An improved information system for retrieving query result information from one or more information sources in response to a query, the information system including descriptions of the information sources and the improvement comprising query execution means including: query plan generating means for receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and query plan execution means for receiving and responding to the query plan by retrieving the query result information from the information sources, the query plan execution means retrieving additional information from the information sources in addition to the query result information and providing the additional information to the query plan generation means in the course of executing the query plan, the additional information being type information indicating a type of the retrieved query result information; and the query plan generating means responding to the additional information and to the descriptions of the information sources by making a modification of the query plan and providing the modification to the query plan execution means for execution while the query plan execution means is executing the query plan, the query plan generating means further responds to the type information and the type description in making the modification of the query plan.
Claim 2
Dependent Claim
219 words
An improved information system for retrieving query result information from one or more information sources in response to a query, the information system including descriptions of the information sources and the improvement comprising query execution means including: query plan generating means for receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and query plan execution means for receiving and responding to the query plan by retrieving the query result information from the information sources, the query plan execution means retrieving additional information from the information sources in addition to the query result information and providing the additional information to the query plan generation means in the course of executing the query plan, the additional information being type information indicating a type of the retrieved query result information; and the query plan generating means responding to the additional information and to the descriptions of the information sources by making a modification of the query plan and providing the modification to the query plan execution means for execution while the query plan execution means is executing the query plan, the query plan generating means further responds to the type information and the type description in making the modification of the query plan.
Claim 3
Dependent Claim
30 words
The improved information system set forth in claim 1, wherein a description of an information source includes a type description indicating a type of the information in the information source.
Claim 4
Dependent Claim
25 words
The improved information system set forth in any of claims 1, 2, or 3 wherein: the information sources are located remotely from the information system.
Claim 5
Dependent Claim
38 words
The improved information system set forth in any of claims 1, 2, or 3 further comprising: a knowledge base including concepts and wherein the descriptions of the information sources describe the information sources in terms of the concepts.
Claim 6
Dependent Claim
56 words
The improved information system set forth in claim 4 wherein: the concepts include concepts relating to the information in the information sources and the additional information is an instance of a concept and the query plan generation means is further responsive to the instance as required by the query and the concepts relating to the information.
Claim 7
Dependent Claim
45 words
The improved information system set forth in claim 5 wherein: the concepts in the knowledge base are ordered in a hierarchy; and the knowledge base responds to a new concept or a new instance by ordering the new concept or new instance in the hierarchy.
Claim 8
Dependent Claim
50 words
The improved information system set forth in claim 6 wherein: the information sources are accessible by means of a plurality of protocols; the concepts in the knowledge base include concepts which describe the protocols; and the query plan generation means is further responsive to the concepts which describe the protocols.
Claim 9
Dependent Claim
51 words
A memory medium readable by a computer system, the memory medium being characterized in that: the memory medium contains code which, when executed by the computer system, implements the improved information system of claim 1 for retrieving query result information from one or more information sources in response to a query.
Claim 10
Dependent Claim
218 words
An information system for retrieving query result information from one or more information sources in response to a query, the information system comprising: a knowledge base including concepts related to information in the information sources, the knowledge base receiving the query and responding thereto by producing an information access description which describes what information is to be accessed in terms of the concepts; query plan generating means for receiving the information access description and responding to the information access description and the concepts by generating a query plan describing how the query result information is to be obtained from the information sources; and query plan execution means for receiving the query plan and executing the query plan to retrieve the query result information and additional information from the information sources and provide the additional information to the query plan generating means in the course of executing the query plan, the query plan generating means responding thereto and to the concepts by making a modification of the query plan and providing the modification to the query plan execution means for execution, the additional information being type information indicating a type of the retrieved query result information, the query plan generating means further responds to the type information and the type description in making the modification of the query plan.
Claim 11
Dependent Claim
218 words
An information system for retrieving query result information from one or more information sources in response to a query, the information system comprising: a knowledge base including concepts related to information in the information sources, the knowledge base receiving the query and responding thereto by producing an information access description which describes what information is to be accessed in terms of the concepts; query plan generating means for receiving the information access description and responding to the information access description and the concepts by generating a query plan describing how the query result information is to be obtained from the information sources; and query plan execution means for receiving the query plan and executing the query plan to retrieve the query result information and additional information from the information sources and provide the additional information to the query plan generating means in the course of executing the query plan, the query plan generating means responding thereto and to the concepts by making a modification of the query plan and providing the modification to the query plan execution means for execution, the additional information being type information indicating a type of the retrieved query result information, the query plan generating means further responds to the type information and the type description in making the modification of the query plan.
Claim 12
Dependent Claim
41 words
The information system set forth in claim 9 wherein: The information sources are accessed by a plurality of protocols; and the concepts in the knowledge base include concepts related to the protocols by means of which the information sources are accessed.
Claim 13
Independent Claim
163 words
A method practiced in an information system which retrieves query result information from one or more information sources in response to a query, the method comprising the steps of: receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and receiving and responding to the query plan by retrieving the query result information from the information sources; retrieving additional information from the information sources in addition to the query result information and providing the additional information in the course of executing the query plan, the additional information being type information indicating a type of the retrieved query result informations; and responding to the additional information and to the descriptions of the information sources by making a modification of the query plan while executing the query plan, and further responding to the type information and the type description in making the modification of the query plan.
Claim 14
Independent Claim
163 words
A method practiced in an information system which retrieves query result information from one or more information sources in response to a query, the method comprising the steps of: receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and receiving and responding to the query plan by retrieving the query result information from the information sources; retrieving additional information from the information sources in addition to the query result information and providing the additional information in the course of executing the query plan, the additional information being type information indicating a type of the retrieved query result informations; and responding to the additional information and to the descriptions of the information sources by making a modification of the query plan while executing the query plan, and further responding to the type information and the type description in making the modification of the query plan.
Claim 15
Dependent Claim
234 words
An improved information system for retrieving query result information from one or more information sources in response to a query, the information system including descriptions of the information sources that include a source description indicating a source of the information in the information source, and the improvement comprising query execution means including: query plan generating means for receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and query plan execution means for receiving and responding to the query plan by retrieving the query result information from the information sources, the query plan execution means retrieving additional information from the information sources in addition to the query result information and providing the additional information to the query plan generation means in the course of executing the query plan, the additional information being source information indicating a source of the retrieved query result information; and the query plan generating means responding to the additional information and to the descriptions of the information sources by making a modification of the query plan and providing the modification to the query plan execution means for execution while the query plan execution means is executing the query plan, the query plan generating means further responds to the source information and the source description in making the modification of the query plan.
Claim 16
Dependent Claim
234 words
An improved information system for retrieving query result information from one or more information sources in response to a query, the information system including descriptions of the information sources that include a source description indicating a source of the information in the information source, and the improvement comprising query execution means including: query plan generating means for receiving the query and the descriptions of the information sources and responding thereto by generating a query plan for retrieving the query result information from the information sources; and query plan execution means for receiving and responding to the query plan by retrieving the query result information from the information sources, the query plan execution means retrieving additional information from the information sources in addition to the query result information and providing the additional information to the query plan generation means in the course of executing the query plan, the additional information being source information indicating a source of the retrieved query result information; and the query plan generating means responding to the additional information and to the descriptions of the information sources by making a modification of the query plan and providing the modification to the query plan execution means for execution while the query plan execution means is executing the query plan, the query plan generating means further responds to the source information and the source description in making the modification of the query plan.
References Cited (Backward Citations)
US4408302A
Cited
US4769772A
Cited
US5021989A
Cited
US5091852A
Cited
US4933800A
Cited
US5408655A
Cited
US5386556A
Cited
US5197005A
Cited
US5117349A
Cited
US5335345A
Cited
US5388196A
Cited
US5379419A
Cited
US5355474A
Cited
US5355320A
Cited
US5301317A
Cited
US5315703A
Cited
US5379366A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-04 | 2000-08-05 | 2001-02-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-04 | 2004-08-05 | 2005-02-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-04 | 2008-08-05 | 2009-02-04 | $7700.00 | Window Closed / Lapsed |