US6092061A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Data partitioning by co-locating referenced and referencing records
Assignee: International Business Machines Corp
•
Filing: 1997-08-15
•
Granted: 2000-07-18
•
Expires: 2017-08-15
Abstract
Abstract A partitioning scheme for co-locating records of a table with records they reference. In a distributed database system, records of one table or relation may be stored at different locations. In order to optimize database query processing the present invention partitions records of a table by reference. A record in a table may reference another record in the table or in another table. The present invention stores (or co-locates) the referencing record with the referenced record.
Inventors
- 👤 David Mun-Hien Choy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 11:25
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2282; G06F16/27; G06F16/278; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933
Claims Analysis
Total Claims: 31
Claim 1
Independent Claim
142 words
In a computer system having a plurality of storage locations for storing data records, a method of partitioning a group of data records in which at least one data record includes a reference to at least one other data record which in turn includes a reference to at least a third data record stored in one of the plurality of storage locations, comprising: identifying the at least one data record of the group of data records referencing the at least one other data record, the at least one other data record in turn referencing and being co-located with the at least a third data record; identifying the one of the plurality of storage locations where the at least one other data record is stored; and storing the at least one data record in the identified one of the plurality of storage locations.
Claim 2
Dependent Claim
142 words
In a computer system having a plurality of storage locations for storing data records, a method of partitioning a group of data records in which at least one data record includes a reference to at least one other data record which in turn includes a reference to at least a third data record stored in one of the plurality of storage locations, comprising: identifying the at least one data record of the group of data records referencing the at least one other data record, the at least one other data record in turn referencing and being co-located with the at least a third data record; identifying the one of the plurality of storage locations where the at least one other data record is stored; and storing the at least one data record in the identified one of the plurality of storage locations.
Claim 3
Dependent Claim
18 words
The method according to claim 1, wherein the group of data records comprises tuples of a database relation.
Claim 4
Dependent Claim
33 words
The method according to claim 2, the computer system having a plurality of database systems networked together, each database system being located at a storage location and including a database management system (DBMS).
Claim 5
Dependent Claim
33 words
The method according to claim 3, wherein the group of data records comprises tuples of a first table and the at least one other data record is a tuple of a second table.
Claim 6
Dependent Claim
33 words
The method according to claim 3, wherein the group of data records comprises tuples of a first table and the at least one other data record is a tuple of the first table.
Claim 7
Dependent Claim
77 words
The method according to claim 1, wherein identifying includes: maintaining an index of references to referenced data records, in which each reference is associated with a storage location of a referenced data record; and identifying the one of the plurality of storage locations where the at least one other data record referenced by the at least one data record is stored by locating the at least one other data record in the index of referenced data records.
Claim 8
Dependent Claim
14 words
The method of claim 1, wherein identifying comprises computing a function on the reference.
Claim 9
Dependent Claim
125 words
In a database system having a plurality of storage locations, a method of partitioning a relation having at least one tuple that includes a reference to at least one other tuple which in turn includes a reference to at least a third tuple stored in one of the plurality of storage locations, comprising: identifying the at least one tuple referencing the at least one other tuple. the at least one other tuple referencing and being co-located with the at least a third tuple; identifying the one of the plurality of storage locations where the at least one other tuple referenced by the at least one tuple is stored; and storing the at least one tuple in the identified one of the plurality of storage locations.
Claim 10
Dependent Claim
125 words
In a database system having a plurality of storage locations, a method of partitioning a relation having at least one tuple that includes a reference to at least one other tuple which in turn includes a reference to at least a third tuple stored in one of the plurality of storage locations, comprising: identifying the at least one tuple referencing the at least one other tuple. the at least one other tuple referencing and being co-located with the at least a third tuple; identifying the one of the plurality of storage locations where the at least one other tuple referenced by the at least one tuple is stored; and storing the at least one tuple in the identified one of the plurality of storage locations.
Claim 11
Dependent Claim
18 words
The method according to claim 8, wherein the at least one other tuple is part of another relation.
Claim 12
Dependent Claim
18 words
The method according to claim 8, wherein the at least one other tuple is part of the relation.
Claim 13
Dependent Claim
71 words
The method according to claim 8, wherein identifying includes: maintaining an index of references to referenced tuples, in which each reference is associated with a storage location of a referenced tuple; and identifying the one of the plurality of storage locations where the at least one other tuple referenced by the at least one tuple is stored by locating the at least one other tuple in the index of referenced tuples.
Claim 14
Dependent Claim
14 words
The method of claim 8, wherein identifying includes computing a function on the reference.
Claim 15
Independent Claim
165 words
A method of inserting a record into a group of records in one of a plurality of storage locations where a field of the record includes a reference to a record of a first group of records and a field of the record of the first group in turn includes a reference to a record of a second group of records and where the record of the second group of records may be stored in one of the plurality of storage locations, the method comprising: identifying the record referencing the record of a first group of records, the record of the first group of records in turn referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record of the second group of records is stored; and inserting the record into the first group of records by storing the record in the identified one of the plurality of storage locations.
Claim 16
Independent Claim
165 words
A method of inserting a record into a group of records in one of a plurality of storage locations where a field of the record includes a reference to a record of a first group of records and a field of the record of the first group in turn includes a reference to a record of a second group of records and where the record of the second group of records may be stored in one of the plurality of storage locations, the method comprising: identifying the record referencing the record of a first group of records, the record of the first group of records in turn referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record of the second group of records is stored; and inserting the record into the first group of records by storing the record in the identified one of the plurality of storage locations.
Claim 17
Dependent Claim
16 words
The method according to claim 13, wherein the first and second group of records are databases.
Claim 18
Dependent Claim
30 words
The method according to claim 13, wherein the first and second group of records are relations, the records are tuples, and the field is an attribute of the first relation.
Claim 19
Dependent Claim
26 words
The method according to claim 15, wherein the attribute of the first relation is a foreign key that references a primary key of the second relation.
Claim 20
Dependent Claim
71 words
The method according to claim 13, wherein identifying includes: maintaining an index of references to referenced records of the second group of records, in which each reference is associated with a storage location of a referenced record; and identifying the one of the plurality of storage locations where the record of the second group of records is stored by locating the record of the second group of records in the index.
Claim 21
Dependent Claim
15 words
The method according to claim 13, wherein identifying includes computing a function on the reference.
Claim 22
Independent Claim
192 words
A method of inserting a plurality of records into a group of records in one of a plurality of storage locations where a field of at least one of the plurality of records includes a reference to a record of a first group of records and a field of the record of the first group of records includes a reference to a record of a second group of records and where the record of the second group of records may be stored in one of the plurality of storage locations, the method comprising: identifying the at least one of the plurality of records referencing the record of the first group of records, the record of the first group of records referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record of the second group of records is stored; and inserting the at least one of the plurality of records into the first group of records by storing the at least one of the plurality of records in the identified one of the plurality of storage locations.
Claim 23
Independent Claim
192 words
A method of inserting a plurality of records into a group of records in one of a plurality of storage locations where a field of at least one of the plurality of records includes a reference to a record of a first group of records and a field of the record of the first group of records includes a reference to a record of a second group of records and where the record of the second group of records may be stored in one of the plurality of storage locations, the method comprising: identifying the at least one of the plurality of records referencing the record of the first group of records, the record of the first group of records referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record of the second group of records is stored; and inserting the at least one of the plurality of records into the first group of records by storing the at least one of the plurality of records in the identified one of the plurality of storage locations.
Claim 24
Dependent Claim
56 words
A method according to claim 19 further comprising inserting any of the plurality of records which do not include a field which references a record of a second group of records into the first group of records by storing into one of the plurality of storage locations as a function of an attribute of the record.
Claim 25
Independent Claim
164 words
A method of inserting a record into a group of records in one of a plurality of storage locations where a field of the record includes a reference to a record in a first group of records and a field of the record in the first group of records in turn includes a reference to a record in a second group of records, and where the record in the second group of records may be stored in one of a plurality of storage locations, the method comprising: identifying the record referencing the record in the first group of records, the record of the first group of records referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record in the second group of records is stored; and inserting the record into the group of records by storing the record in the identified one of the plurality of storage locations.
Claim 26
Independent Claim
164 words
A method of inserting a record into a group of records in one of a plurality of storage locations where a field of the record includes a reference to a record in a first group of records and a field of the record in the first group of records in turn includes a reference to a record in a second group of records, and where the record in the second group of records may be stored in one of a plurality of storage locations, the method comprising: identifying the record referencing the record in the first group of records, the record of the first group of records referencing and being co-located with the referenced record of the second group of records; identifying the one of the plurality of storage locations where the record in the second group of records is stored; and inserting the record into the group of records by storing the record in the identified one of the plurality of storage locations.
Claim 27
Dependent Claim
19 words
The method according to claim 21, wherein the group of records is comprised of at least one database relation.
Claim 28
Dependent Claim
21 words
The method according to claim 22, wherein the field of the record is an attribute of at least one database relation.
Claim 29
Dependent Claim
36 words
The method according to claim 23, wherein the attribute of the at least one database relation is a foreign key that references a primary key of at least one database relation in the group of records.
Claim 30
Dependent Claim
66 words
The method according to claim 21, wherein identifying includes: maintaining an index of referenced records in the group of records in which each reference is associated with a storage location of the referenced record; and identifying the one of the plurality of storage locations where the record in the group of records is stored by locating the record in the group of records in the index.
Claim 31
Dependent Claim
15 words
The method according to claim 21, wherein identifying includes computing a function on the reference.
References Cited (Backward Citations)
US5058002A
Cited
US4853843A
Cited
US5089954A
Cited
US5121494A
Cited
US5448727A
Cited
US5842207A
Cited
US5499367A
Cited
US5555404A
Cited
US5515531A
Cited
US5551027A
Cited
US5625815A
Cited
US5850522A
Cited
US5727197A
Cited
US5991758A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-18 | 2004-01-17 | 2004-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-18 | 2008-01-17 | 2008-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-18 | 2012-01-17 | 2012-07-18 | $7700.00 | Window Closed / Lapsed |