US5551031A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Program storage device and computer program product for outer join operations using responsibility regions assigned to inner tables in a relational database
Assignee: International Business Machines Corp
•
Filing: 1995-06-07
•
Granted: 1996-08-27
•
Expires: 2015-06-07
Abstract
Abstract A computer database system utilizes a method for performing a right outer join of database tables without sorting the inner table (T2). The processing of each tuple in the outer table (T1) includes the preservation in the joint output of all tuples in T2 which are in its responsibility region. The initialization step of the process preserves in the join output all of the tuples in T2 which have column set values less than the lowest column set value in T1, i.e. the first tuple in T1, since T1 is sorted or accessed using a sorted index. The responsibility region for tuples in T1, other than the last tuple, is defined as those tuples which have column set values less than the column set value for the next tuple in T1 and greater than or equal to the column set value for the current T1 tuple. The last tuple in T1 must preserve all of the tuples in T2 which have not already been preserved in T2, i.e. all tuples greater than or equal to its column set value. If T1 has duplicate values for the column set value, only the last one preserves the associated T2 tuples. Additional methods for parallel execution of the outer join methods and methods for applying the outer join methods to subqueries (i.e., an All (or universal) Right Join (ARJOIN) and an Existential Right Join (ERJOIN)) are described.
Inventors
- 👤 Josephine M. Cheng
- 👤 Chandrasekaran Mohan
- 👤 Mir H. Pirahesh
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 07:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24558; G06F16/2456; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 26
Claim 1
Independent Claim
176 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing a right outer join with specified join predicates in a database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple.
Claim 2
Dependent Claim
176 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing a right outer join with specified join predicates in a database system having an inner table and an outer table, each of which tables is composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple.
Claim 3
Dependent Claim
56 words
The program storage device of claim 1, wherein the determining step further comprises the step of defining an initial responsibility region which contains all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.
Claim 4
Dependent Claim
59 words
The program storage device of claim 1, wherein the determining step further comprises the step of defining a final responsibility region which contains all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.
Claim 5
Dependent Claim
50 words
The program storage device of claim 1, wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.
Claim 6
Dependent Claim
53 words
The program storage device of claim 1, wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.
Claim 7
Dependent Claim
164 words
The program storage device of claim 1, wherein the determining step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and for the last tuple in the outer table, assigning a last responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions.
Claim 8
Dependent Claim
175 words
The program storage device of claim 1, wherein the processing step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and for the last tuple in the outer table, accessing a set of tuples of the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the last tuple of the outer table.
Claim 9
Dependent Claim
154 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing an existential right join with specified join predicates in a database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the inner tuple once.
Claim 10
Dependent Claim
154 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing an existential right join with specified join predicates in a database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the inner tuple once.
Claim 11
Dependent Claim
164 words
The program storage device of claim 8, wherein the determining step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and for the last tuple in the outer table, assigning a last responsibility region to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions.
Claim 12
Dependent Claim
84 words
The program storage device of claim 8, wherein the processing step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple which is associated with one of the non-null responsibility regions and accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns equal to the value of the selected set of columns for the current tuple of the outer table.
Claim 13
Dependent Claim
156 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing an all right join with specified join predicates in a database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple do not match by not satisfying all the specified join predicates, outputting the inner tuple.
Claim 14
Dependent Claim
156 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing an all right join with specified join predicates in a database system having an inner table and an outer table, each of which tables are composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said method steps comprising: determining a plurality of responsibility regions in the inner table using a selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and processing each non-null responsibility region by outputting all tuples of the inner table which belong to the non-null responsibility region, wherein if an inner tuple and an outer tuple do not match by not satisfying all the specified join predicates, outputting the inner tuple.
Claim 15
Dependent Claim
57 words
The program storage device of claim 11, wherein the determining step further comprises the step of defining an initial non-null responsibility region which contains all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.
Claim 16
Dependent Claim
60 words
The program storage device of claim 11, wherein the determining step further comprises the step of defining a final non-null responsibility region which contains all tuples of the inner table which have values of a selected set of columns equal to or greater than the value of the selected set of columns for a last tuple of the outer table.
Claim 17
Dependent Claim
50 words
The program storage device of claim 11, wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns less than the value of the selected set of columns for a first tuple of the outer table.
Claim 18
Dependent Claim
54 words
The program storage device of claim 11, wherein the processing step further comprises the step of outputting all tuples of the inner table which have values of a selected set of columns greater than and not equal to the value of the selected set of columns for a last tuple of the outer table.
Claim 19
Dependent Claim
159 words
The program storage device of claim 11, wherein the determining step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning the non-null responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of a selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and for the last tuple in the outer table, a last non-null responsibility region to include all tuples from the inner table which have not been assigned to any other of the non-null responsibility regions.
Claim 20
Dependent Claim
177 words
The program storage device of claim 11, wherein the processing step further comprises the steps of: sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, accessing a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than and not equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and for the last tuple in the outer table, accessing a set of tuples of the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than and not equal to the value of the selected set of columns for the last tuple of the outer table.
Claim 21
Dependent Claim
259 words
A computer program product for use with a database system having means for performing a right outer join, an existential right join, and an all right join, with specified join predicates, on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said computer program product comprising: a computer usable medium having a computer readable program code means embodied in said medium for performing the join operations, said computer readable program code means comprising: computer readable first program code means for causing a computer to determine a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and computer readable second program code means for causing said computer to process each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential right join, if the inner and outer tuples match, outputting the inner tuple once, and for the all right join, if the inner and outer tuples do not match, outputting the inner tuple.
Claim 22
Dependent Claim
259 words
A computer program product for use with a database system having means for performing a right outer join, an existential right join, and an all right join, with specified join predicates, on an inner table and an outer table, each table composed of a plurality of tuples having multiple columns, the outer table being ordered or indexed in a sorted sequence on a selected set of columns, said computer program product comprising: a computer usable medium having a computer readable program code means embodied in said medium for performing the join operations, said computer readable program code means comprising: computer readable first program code means for causing a computer to determine a plurality of responsibility regions in the inner table using the selected set of columns such that every tuple in the inner table belongs to one and only one responsibility region; and computer readable second program code means for causing said computer to process each responsibility region by outputting all tuples of the inner table which belong to the responsibility region, wherein for the right outer join, if an inner tuple and an outer tuple match by satisfying all the specified join predicates, outputting the outer tuple with the inner tuple, and if the inner and outer tuples do not match, outputting null values for the outer tuple with the inner tuple, for the existential right join, if the inner and outer tuples match, outputting the inner tuple once, and for the all right join, if the inner and outer tuples do not match, outputting the inner tuple.
Claim 23
Dependent Claim
169 words
The computer program product of claim 18, wherein said computer readable second program code means comprises: means for sequencing through the tuples in the outer table referencing a current tuple and a next tuple and for each unique set of column values in the outer table, other than that of a last tuple, assigning one of the plurality of responsibility regions to include a set of tuples from the inner table which corresponds to all tuples in the inner table which have values of the selected set of columns greater than or equal to the value of the selected set of columns for the current tuple of the outer table and less than the value of the specified set of columns for the next tuple of the outer table; and means for assigning a last responsibility region, associated with the last tuple in the outer table, to include all tuples from the inner table which have not been assigned to any other one of the plurality of responsibility regions.
Claim 24
Dependent Claim
26 words
The computer program product of claim 18, wherein said computer readable first program code means further comprises means for defining both null and non-null responsibility regions.
Claim 25
Dependent Claim
40 words
The computer program product of claim 20, wherein: the join operation to be performed is an existential right join; and said computer readable second program code means further comprises means for accessing the inner table only for non-null responsibility regions.
Claim 26
Dependent Claim
54 words
The computer program product of claim 20, wherein: the join operation to be performed is an all right join having an ON clause; and said computer readable second program code means further comprises means for accessing the inner table only for non-null responsibility regions and only for tuples not matched by the ON clause.
References Cited (Backward Citations)
US4497039A
Cited
JPS59125461A
Cited
US4506326A
Cited
US4967341A
Cited
US5043872A
Cited
EP0421408A2
Cited
US5210870A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-08-27 | 2000-02-26 | 2000-08-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-08-27 | 2004-02-26 | 2004-08-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-08-27 | 2008-02-26 | 2008-08-27 | $7700.00 | Window Closed / Lapsed |