Information manifold for query processing

• US 5,995,961 A
• Filed: 11/07/1996
• Issued: 11/30/1999
• Est. Priority Date: 11/07/1995
• Status: Expired due to Term

• Current Assignee: Tamiras Per Pte Ltd LLC (Intellectual Ventures LLC)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Ordille, Joann J., Rajaraman, Anand, Levy, Alon Y.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/745,071
• Time in Patent Office: 1,118 Days
• Field of Search: 707/1, 707/2, 707/5, 707/10, 707/63, 707/3, 707/4
• 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/252 between a Database Management System and a front-end application
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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/99934 Query formulation, input preparation, or translation

Abstract

A system and method for accepting and responding to queries based on information stored on multiple heterogenous information sources. A uniform query interface to large collections of structured information sources is provided to a user to pose queries using a uniform schema of the available information. A query plan for answering the query is formulated from descriptions of the contents and capabilities of the available information sources. Based on these descriptions logical solutions which are subsets of the complete solution to the query are derived. An order for executing these solutions is determined based on the input requirements and other capabilities of the relevant information sources.

Claims

1. An information manifold system for processing a query with information from at least two of a plurality of available information sources, each information source having certain capabilities, at least two of said information sources having non-identical capabilities, the information manifold system comprising:

a query interface for formulating said query in terms of a schema of a world-view of said plurality of available information sources;

a query plan generator for formulating a query plan that exploits the capabilities of said information sources with non-identical capabilities, the query plan generator including storage for descriptions of the capabilities of said information sources, said query plan generator including means for generating at least one logical solution to said query, said query plan generator further including means for generating an executable order of said at least one logical solution;

a query plan execution engine for executing said query plan after said query plan is formulated; and

means for returning information which is responsive to said query, from at least two of said available information sources.

2. A system according to claim 1 wherein said query interface is a uniform query interface such that a single query can access multiple heterogenous information sources.

3. A system according to claim 1 wherein said world-view is a data model including at least one relation identifiable with at least one class and arranged in accordance with a class hierarchy, where a class is a unary relation in said data model, wherein each of said information sources are identifiable by content description and capability descriptions, and wherein said query plan generator includes means for identifying those of said plurality of available information sources that can be combined in a manner satisfying said capabilities.

4. A system according to claim 1 wherein said query plan generator further comprises means for determining those of said plurality of available information sources that contain information responsive to said query at least in part.

5. A system according to claim 1 wherein said query plan execution engine includes means for combining information from a plurality of said available information sources.

6. A system according to claim 5 wherein at least part of said information from said plurality of available information sources is grouped into at least one object, wherein each object is an instance of a class, said system further comprising means for determining whether any of said objects is referred to in more than one of said plurality of available information sources.

7. A system according to claim 6 wherein said means for determining includes at least one key associated with a unique one of said classes in said data model such that each of said objects has a unique key.

8. A system according to claim 5 wherein said information from said plurality of available information sources includes at least one value, said system further comprising means for determining whether a given one of said values appears in more than one of said available information sources.

9. A system according to claim 8 wherein said means for determining includes at least one host value for modeling said values in each of said relevant information sources.

10. A system according to claim 9 wherein said means for determining includes means for approximating comparisons between a plurality of host values.

11. A method for processing a query with information from at least two of a plurality of available information sources, each information source having certain capabilities, at least two of the information sources having non-identical capabilities, said method comprising the steps of:

formulating said query in terms of a schema of a world-view of said plurality of available information sources;

storing descriptions of the capabilities of the information sources;

determining those of said plurality of available information sources that are responsive to said query at least in part;

formulating a query plan that exploits the capabilities of said information sources that are responsive to said query at least in part and have non-identical capabilities, said formulating a query plan step including step for generating at least one logical solution to said query, said formulating a query plan step further including step for generating an executable order of said at least one logical solution;

after said formulating step, executing said query plan; and

returning information to said user, from at least one of said information sources that are responsive to said query at least in part.

12. A method according to claim 11 wherein said world-view is a data model including at least one relation identifiable with a class and arranged in accordance with a class hierarchy, where a class is a unary relation in said data model, wherein each of said information sources are identifiable by content description and capability descriptions, and wherein said formulating a query plan step includes identifying those of said information sources that are responsive to said query at least in part that can be combined in a manner satisfying said capabilities.

13. A method according to claim 11 wherein said executing step includes combining information from a plurality of said information sources that are responsive at least in part.

14. A method according to claim 13 wherein said information from said plurality of information sources that are responsive includes at least one object, said method further comprising the step of determining whether more than one of said plurality of information sources that are responsive to said query at least in part refers to the same object.

15. A method according to claim 14 wherein said determining whether more than one of said plurality of information sources that are responsive to said query at least in part refers to the same object step includes associating a key with a unique one of said classes in said data model such that each of said objects have a unique key.

16. A method according to claim 13 wherein said information from said plurality of information sources that are responsive includes at least one value, said method further comprising the step of determining whether more than one of said information sources that are responsive refers to the same value.

17. A method according to claim 16 wherein said determining whether more than one of said information sources that are responsive refers to the same value step, includes modeling each of said values to a host value.

18. A method according to claim 17 wherein said determining whether more than one of said information sources that are responsive refers to the same value includes approximating comparisons between a plurality of host values.