System and methods for performing multi-source searches over heterogeneous databases
First Claim
1. A method for performing a multiple-segment search over a first database segment with a search predicate requiring values from a second database segment, where the first and the second databases are managed by a first and a second database management system, respectively, where the search predicate is a top-level AND conjunction of independent factors, and where the search predicate contains an INCURSOR operator, the method comprising the computer-implemented steps of:
- (a) Dividing the top-level factors into incursor factors, being those that contain INCURSOR operators, and local factors, being those that do not contain INCURSOR operators, whereby the local factors contain no references to the second database segment; and
(b) Iterating the following steps over those tuples produced by a search of the first database where all the local factors are satisfied;
i. evaluating the INCURSOR predicates in the incursor factors;
ii. then evaluating the incursor factors using the results of the foregoing step;
iii. then, while the multiple-segment search is ongoing, if the result of the preceding step is TRUE, making the record from the first database segment available at that time as an incremental part of the result of the multiple-segment search.
2 Assignments
0 Petitions
Accused Products
Abstract
System and methods for performing search and retrieval operations over multiple databases, the system and methods being suitable for use in combination with databases of different kinds managed by different database management systems, the system and methods also being suitable for use in combination with databases resident on different computers in a computer network environment. The system and methods in their simplest application search each of a pair of database segments incrementally, using the incremental results of one search to direct the processing of the other search. The methods may be nested, and the system may be used in multiple instances, to effect searches on combinations of any number of database segments.
148 Citations
19 Claims
-
1. A method for performing a multiple-segment search over a first database segment with a search predicate requiring values from a second database segment, where the first and the second databases are managed by a first and a second database management system, respectively, where the search predicate is a top-level AND conjunction of independent factors, and where the search predicate contains an INCURSOR operator, the method comprising the computer-implemented steps of:
-
(a) Dividing the top-level factors into incursor factors, being those that contain INCURSOR operators, and local factors, being those that do not contain INCURSOR operators, whereby the local factors contain no references to the second database segment; and (b) Iterating the following steps over those tuples produced by a search of the first database where all the local factors are satisfied; i. evaluating the INCURSOR predicates in the incursor factors; ii. then evaluating the incursor factors using the results of the foregoing step; iii. then, while the multiple-segment search is ongoing, if the result of the preceding step is TRUE, making the record from the first database segment available at that time as an incremental part of the result of the multiple-segment search. - View Dependent Claims (2, 3, 4, 5)
-
-
6. A method for performing a multiple-segment search over a first database segment with a search predicate requiring values from a second database segment, where the first and the second databases are managed by a first and a second database management system, respectively, where the search predicate is a top-level AND conjunction of independent factors, and where at least one of the top-level factors is an INCURSOR predicate, the method comprising the computer-implemented steps of:
-
(a) Selecting a driving clause from among the top-level INCURSOR predicates; (b) Then dividing the remaining top-level factors into incursor factors, being those that contain INCURSOR operators, and local factors, being those that do not contain INCURSOR operators, whereby the local factors contain no references to the second database segment; (c) Then iterating the following steps over those tuples produced by a search of the second database segment using the driving clause; i. Passing on to the next iteration if the tuple from the driving clause contains any NULL values; ii. Otherwise, iterating the following steps over each record produced by a search of the first database segment using a filter predicate that conjoins the local factors with a predicate that is TRUE only if all the values in the tuple from the driving clause are equal to the values from the corresponding fields in the first database segment; A. evaluating the INCURSOR base predicates in the incursor factors; B. then evaluating the incursor factors using the results of the foregoing step; and C. then, while the multiple-segment search is ongoing, if the result of the preceding step is TRUE, making the record from the first database segment available at that time as an incremental part of the result of the multiple-segment search. - View Dependent Claims (7, 8, 9, 10)
-
-
11. A method for performing a theta-join over a first and a second table managed by a first and a distinct second database management system to produce a select list of field expressions, with a filter predicate and with a set of linking fields between the first and the second table, the method comprising the computer-implemented steps of:
-
(a) Reducing the filter predicate into a conjunctive form having a top-level conjunction of factors; (b) Dividing the top-level factors into first-table factors, being those that refer only to fields in the first table, second-table factors, being those that refer only to fields in the second table, and mixed factors, being those that refer to fields in the both the first and the second tables; (c) Invoking a query on the first table by the first database management system to retrieve incrementally records that satisfy the first-table factors, and for each record retrieved that has no NULL linking field, performing the following steps; i. If no linking field in the record is NULL, invoking a query on the second table by the second database management system to retrieve records that satisfy the second-table factors and that have linking field values related by the theta operator to the linking field values of the record retrieved from the first table; ii. For each record retrieved from the second table in the preceding step (i), evaluating the mixed factors against the current first table record and the second table record; iii. If the result of the evaluation of the preceding step (ii) is TRUE, calculating the values of the field expressions in the select list and producing the select list as a result of the present iteration. - View Dependent Claims (12, 13, 14, 15)
-
-
16. A method for performing a theta-join over a first and a second table managed by a first and a distinct second database management system to produce a select list of field expressions, with a filter predicate, and with a set of linking fields between the first and the second table, the method comprising the computer-implemented steps of:
-
(a) Reducing the filter predicate to conjunctive normal form, whereby a top-level conjunction of factors is created; (b) Dividing the top-level factors into first-table factors, being those that refer only to fields in the first table, second-table factors, being those that refer only to fields in the second table, and mixed factors, being those that refer to fields in the both the first and the second tables; (c) Invoking a query on the first table by the first database management system to retrieve incrementally records that satisfy the first-table factors, and for each record retrieved that has no NULL linking field, performing the following steps; i. Transforming the mixed factors into NULL-reduced mixed factors based on the values in the record retrieved from the first table, whereby all the consequences of any NULL values in the retrieved record are propagated through the mixed factors; ii. Invoking a query on the second table by the second database management system to retrieve records that satisfy the second-table factors, that satisfy the NULL-reduced mixed factors, and that have linking field values related by the theta operator to the linking field values of the record retrieved from the first table; iii. Then calculating the values of the field expressions in the select list and producing the select list as a result of the present iteration.
-
-
17. A gateway system for performing a multiple-operand search over a database for those records that satisfy a first search predicate that includes an INCURSOR predicate having a field list operand and a foreign cursor operand, where the database is managed by a database management system, the gateway system comprising:
-
(a) means for receiving the first search predicate; (b) means for dividing the first search predicate into a conjunction of top-level factors; (c) means for opening the database through the database management system; (d) means for incrementally retrieving those records that satisfy the local factors (being those top-level factors that do not contain an INCURSOR operand at any level) from the database through the database management system; (e) means for invoking the foreign cursor operand to validate a local tuple of values taken from a record retrieved from the database; and (f) means for incrementally producing records retrieved from the database while the multiple-operand search is ongoing as incremental parts of the result of the multiple-operand search. - View Dependent Claims (18, 19)
-
Specification