Method and system for network information access

• US 5,995,959 A
• Filed: 01/23/1998
• Issued: 11/30/1999
• Est. Priority Date: 01/24/1997
• Status: Expired due to Term

• Current Assignee: Board of Regents of The University of Washington (University of Washington)
• Original Assignee: Board of Regents of The University of Washington (University of Washington)
• Inventors: Kwok, Chung T., Friedman, Marc T., Weld, Daniel S.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US09/012,441
• Time in Patent Office: 676 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5, 709/217-219, 709/200, 709/201
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

This invention provides methods to locate and plan the retrieval of data from networked information sources in response to a user query. The methods utilize descriptions of the information sources, the information domain of the sources, and of the query. The methods of this invention integrate both legacy systems and full relational databases with an efficient, domain-independent, query-planning algorithm, reason about the capabilities of different information sources, handle partial goal satisfaction i.e., gather as much data as possible when all that the user requested cannot be gathered, are both sound and complete, and are efficient.

Claims

1. A method to retrieve information from one or more information sources in order to satisfy a user information query, said method comprising the steps of:

a. generating an ordered sequence of one or more operators, (i) wherein each said operator represents a type of query for retrieving information from one of said information sources, (ii) wherein each said operator has a representation comprising a head with zero or more bound arguments and with one or more free arguments, said bound and free arguments representing, respectively, input information required by, and output information returned from, said represented query type, (iii) and further wherein said user information query has a representation comprising a head with zero or more bound arguments and with one of more free arguments;

b. Instantiating each said ordered sequence of operators to form one or more ordered sequences of operator instances by replacing said bound and free arguments in each said operator and in said user information query with variables such that the binding pattern of said ordered sequence of operators is satisfied;

c. testing whether each said ordered sequence of operator instances satisfies said user information query, wherein said ordered sequence of operator instances satisfies said user information query if it returns information in its variables satisfying the free arguments of said head of said user information query; and

d. repeating steps (a), (b), and (c) either until no additional said ordered sequences of operators can be generated or until a resource bound is exceeded.

2. The method of claim 1 further comprising after step (d) the additional steps of:

e. submitting each operator instance of one of said ordered sequence of said operator instances that satisfies said user information query to said represented information source, wherein said variables replacing said bound arguments of said operator have values either according to said user query or according to information already retrieved from said information sources;

f. assigning values to said variables replacing said free arguments of said operator instance according to information returned from said represented information source;

g. repeating steps (e) and (f) in order for all said operator instances of said ordered sequence of operator instances; and

h. assigning values to the free variables in said user information query according to the information returned from said information sources in step (f), whereby said user information query is satisfied.

3. The method of claim 1 wherein said generating is according to a forward chaining method wherein a new one of said ordered sequences of operators is generated by appending an instance of one of said operators to a previous one of said ordered sequences of operators such that said binding pattern can be satisfied in said instantiating step.

4. The method of claim 3 wherein said appending and instantiating do not generate a new one of said ordered sequence of operators wherein the resulting ordered sequence of operator instances has two independent operators in a different order than said two independent operator instances have in an already generated ordered sequence of operator instances.

5. The method of claim 4 wherein two operator instances are independent if they are neither directly dependent nor transitively dependent, wherein two operator instances are directly dependent if there is a variable replacing a bound argument in one of said two operator instances and a replacing a free argument in the other of said two operator instances, and wherein two operator instances are transitively dependent if they are part of an ordered sequence of operator instances, each pair of adjacent operator instances being directly dependent.

6. The method of claim 1 wherein said arguments and said variables have one or more types, and wherein a variable can only replace an argument if they both have the same type.

7. The method of claim 1 wherein said binding pattern is satisfied if, for each operator instance in said ordered sequence of operator instances, all of its said bound arguments are replaced either by variables which replaced free arguments in previous operator instances in said ordered sequence of operator instances or are replaced by variables which replaced bound arguments in said head of said user information query.

8. The method of claim 1 (i) wherein said information sources are part of an information domain whose information content is represented by one or more relational schema, each said relational schema comprising a named predicate symbol and one or more arguments, (ii) wherein said operators and said user information query further comprise bodies comprising conjunctions of one or more of said relational schema, said conjunction comprising arguments including those of said heads of said operators and said user information query, respectively, (iii) and further wherein a said ordered sequence of operator instances satisfies said user information query if the variables replacing said arguments in the body of said user information query can be mapped to the variables in the conjunction of all the bodies of said ordered sequence of operator instances such that the body of user information query is contained in said conjunction of the bodies of ordered sequence of operator instances.

9. The method of claim 1 wherein said step of instantiating does not form an ordered sequence of operator instances in which two or more operator instances have bound arguments replaced by the same variables.

10. A computer system programmed according to the method of claim 1.

11. A computer system programmed according to the method of claim 2.