Apparatus and methods for retrieving information by modifying query plan based on description of information sources

• US 5,600,831 A
• Filed: 11/30/1994
• Issued: 02/04/1997
• Est. Priority Date: 02/28/1994
• Status: Expired due to Term

• Current Assignee: Nokia of America Corporation (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Srivastava, Divesh, Levy, Alon Y.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/347,016
• Time in Patent Office: 797 Days
• Field of Search: 395/600, 395/575, 395/425
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/954 Navigation, e.g. using categorised browsing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

Claims

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

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

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

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

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

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

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

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

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

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

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

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