US5933820A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System, method, and program for using direct and indirect pointers to logically related data and targets of indexes
Assignee: International Business Machines Corp
•
Filing: 1996-05-20
•
Granted: 1999-08-03
•
Expires: 2016-05-20
Abstract
Abstract The system, method, and program product of this invention allows a database management system to internally use direct and indirect pointing to locate targeted data elements that are logically related to another data element or are a target of a secondary index. By using direct and indirect pointing, the number of steps involved in a reorganization of the database can be reduced. After a reorganization, the database management system does not go back, in a separate process, to update all of the direct pointers that have pointed to segments that have moved as a result of the reorganization. Instead, the direct pointer is updated, by using the indirect pointer, only upon a first reference to the targeted data element that has moved. As such, each data element, that points to a targeted data element, has a direct pointer associated with it having a unique identifier of the targeted data element, assigned by the DBMS at the time a data element is created, a partition id of the targeted segment, a reorganization number, and a pointer to a location of the targeted data element. Each targeted data element has an entry in an indirect index where the unique identifier is the key into the index. Each entry is updated, with a new location, whenever the targeted data element is moved. The DBMS also maintains, in memory, a current reorganization number for each partition. Upon reference to a targeted element, the reorganization number in memory is compared with the reorganization number in the direct pointer. If they match, the direct pointer is used to locate the targeted element. If they do not match, the indirect index is used by indexing into it by using the unique id in the direct pointer. The current location and current reorg number from the indirect index are used to update the direct pointer. The direct pointer can then be used, directly, to locate the targeted data element on subsequent references until a next reorganization involves the targeted data segment.
Inventors
- 👤 Harley Al Beier
- 👤 Sidney Kornelis
- 👤 Vern L. Watts
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 03:39
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2282; Y; Y10; Y10S; Y10S707/00; Y10S707/99931
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
110 words
A database system for reorganizing a database having at least one related data element related to a targeted data element, the database system comprising: means for relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element; means for updating an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; and means for updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.
Claim 2
Dependent Claim
110 words
A database system for reorganizing a database having at least one related data element related to a targeted data element, the database system comprising: means for relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element; means for updating an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; and means for updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.
Claim 3
Dependent Claim
114 words
A database system comprising: direct pointing means associated with a first data element for locating a specific targeted data element related to the first data element; an indirect index for each targeted data element, the indirect index containing a unique identifier and a current location of each targeted data element; means for determining whether the direct pointing means are valid; means for locating the targeted data element using the direct pointing means if the means for determining determines the direct pointing means to be valid; means for using the current location in the indirect index to locate the targeted data element if the means for determining determines the direct pointing means to be invalid.
Claim 4
Dependent Claim
114 words
A database system comprising: direct pointing means associated with a first data element for locating a specific targeted data element related to the first data element; an indirect index for each targeted data element, the indirect index containing a unique identifier and a current location of each targeted data element; means for determining whether the direct pointing means are valid; means for locating the targeted data element using the direct pointing means if the means for determining determines the direct pointing means to be valid; means for using the current location in the indirect index to locate the targeted data element if the means for determining determines the direct pointing means to be invalid.
Claim 5
Dependent Claim
24 words
The database system of claim 2 further comprising means for assigning the unique identifier to each data element when the data element is created.
Claim 6
Dependent Claim
56 words
The system of claim 2 wherein the direct pointing means comprises a pointer to a location of the targeted data element, a description of a partition of a database where the targeted data element exists, and a reorganization number to indicate a reorganization level of the targeted data element at a time the pointer is assigned.
Claim 7
Dependent Claim
30 words
The system of claim 4 wherein the direct pointing means further comprises a relative byte address of the targeted data element, and the unique identifier of the targeted data element.
Claim 8
Dependent Claim
46 words
The system of claim 5 further comprising means for using the unique identifier in the direct pointing means as a key into the indirect index to find the current location of the targeted data element if the determining means determines the pointing means to be invalid.
Claim 9
Dependent Claim
35 words
The system of claim 2 wherein the unique identifier for each data element comprises a relative byte address of a data element segment, a current partition of the segment, and a current partition reorganization number.
Claim 10
Dependent Claim
45 words
The system of claim 2 wherein the means for using further comprises means for updating the direct pointing means on a first reference to the direct pointing means by using the indirect index, and using the updated pointer to locate the specific targeted data element.
Claim 11
Dependent Claim
168 words
The database system of claim 2 wherein the means for determining further comprises means for storing in memory a current reorganization number associated with each one of at least one partitions of a database; means for incrementing the reorganization number in memory for each reorganization whenever the at least one partition is reorganized; means for keeping, in the direct pointing means, a direct pointer reorganization number indicative of a reorganization level associated with a targeted location pointer in the direct pointing means which points to a location of the targeted data element as a result of the reorganization designated by the direct pointer reorganization number; means for comparing the direct pointer reorganization number with the reorganization number in memory for a specified partition; means for determining the pointing means are valid if the direct pointer reorganization number and the reorganization number in memory match; and means for determining the pointing means are invalid if the direct pointer reorganization number and the reorganization number in memory do not match.
Claim 12
Independent Claim
102 words
A method of reorganizing a database having at least one related data element related to a targeted data element, the method comprising: relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element; updating an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; and updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.
Claim 13
Independent Claim
102 words
A method of reorganizing a database having at least one related data element related to a targeted data element, the method comprising: relocating to a new physical storage location the targeted data element independently of updating a direct pointer associated with the related data element to indicate a location of the targeted data element; updating an indirect index with the new physical storage location of the targeted data element when the targeted data element is relocated; and updating, using the updated indirect index, the direct pointer at a first reference of the targeted data element after the targeted data element is relocated.
Claim 14
Independent Claim
106 words
A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising: updating an indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element, is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid.
Claim 15
Independent Claim
106 words
A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising: updating an indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element, is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid.
Claim 16
Independent Claim
125 words
A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising: assigning an unique identifier to each data element; updating an indirect index having the unique identifier as the key into the indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid.
Claim 17
Independent Claim
125 words
A method, for use in a database system, for locating a targeted data element from a related data element, the method comprising: assigning an unique identifier to each data element; updating an indirect index having the unique identifier as the key into the indirect index with a current location of the targeted data element when the targeted data element is moved; determining whether a direct pointer, associated with the related data element, that directly points to the targeted data element is valid; using the direct pointer to locate the targeted data element if the direct pointer is determined to be valid; and using the current location in the indirect index to locate the targeted data element if the direct pointer is determined to be invalid.
Claim 18
Dependent Claim
47 words
The method of claim 11 further comprising: determining whether each data element is involved in a logical relationship or is a target of a secondary index; and maintaining the indirect index for each data element involved in the logical relationship or the target of the secondary index.
Claim 19
Dependent Claim
31 words
The method of claim 12 further comprising the step of determining whether a data element is dependent and maintaining an indirect index entry for each data element determined to be dependent.
Claim 20
Dependent Claim
155 words
The method of claim 11 wherein the step of determining further comprises the steps of storing in memory a current reorganization number associated with each one of at least one partitions of a database; incrementing the reorganization number in memory for each reorganization whenever the at least one partition is reorganized; maintaining, in the direct pointer, a direct pointer reorganization number indicative of the reorganization associated with a targeted location pointer in the direct pointer which points to a location of the targeted data element as a result of the reorganization designated by the direct pointer reorganization number; comparing the direct pointer reorganization number with the reorganization number in memory for a specified partition; determining the direct pointer is valid if the direct pointer reorganization number and the reorganization number in memory match; and determining the direct pointer is invalid if the direct pointer reorganization number and the reorganization number in memory do not match.
Claim 21
Dependent Claim
134 words
A memory, for use with a database management system, for accessing a targeted data element from a related data segment, the memory comprising: a direct pointer data structure comprising: a first reorganization number indicating a reorganization level of a partition containing the targeted data element; a relative byte address of a first location of the targeted data element associated with the first reorganization number; a unique segment identifier of the targeted data element; an indirect index data structure having the unique segment identifier as a key into the indirect index data structure comprising: a second reorganization number indicating the reorganization level of the partition containing the targeted data element; and a relative byte address of a second location of the targeted data element associated with the reorganization level indicated by the second reorganization number.
Claim 22
Dependent Claim
134 words
A memory, for use with a database management system, for accessing a targeted data element from a related data segment, the memory comprising: a direct pointer data structure comprising: a first reorganization number indicating a reorganization level of a partition containing the targeted data element; a relative byte address of a first location of the targeted data element associated with the first reorganization number; a unique segment identifier of the targeted data element; an indirect index data structure having the unique segment identifier as a key into the indirect index data structure comprising: a second reorganization number indicating the reorganization level of the partition containing the targeted data element; and a relative byte address of a second location of the targeted data element associated with the reorganization level indicated by the second reorganization number.
Claim 23
Dependent Claim
44 words
The memory of claim 16 having the direct pointer data structure for each related data segment having the ability to point outside a database record containing the related data segment, and the indirect list entry data structure having an entry for each targeted segment.
Claim 24
Dependent Claim
134 words
A program product, for use with a database system, having program code, on a computer usable medium, comprising: means for causing an assignment of a unique identifier for each data segment in a database; means for determining, for each data segment that is moved, whether the data segment is logically related to a related data segment or is a target of an index, whereby if the data segment is logically related or a target of an index it is a targeted data segment; and means for using the unique identifier of the targeted data segment as a key into a indirect index data structure to update the indirect index data structure with a reorganization number indicative of a latest move of the targeted data segment and a new location of the targeted data segment.
Claim 25
Dependent Claim
134 words
A program product, for use with a database system, having program code, on a computer usable medium, comprising: means for causing an assignment of a unique identifier for each data segment in a database; means for determining, for each data segment that is moved, whether the data segment is logically related to a related data segment or is a target of an index, whereby if the data segment is logically related or a target of an index it is a targeted data segment; and means for using the unique identifier of the targeted data segment as a key into a indirect index data structure to update the indirect index data structure with a reorganization number indicative of a latest move of the targeted data segment and a new location of the targeted data segment.
Claim 26
Dependent Claim
200 words
A program product, for use with a database system having at least one related data element related to a targeted data element, the program product having program code, on a computer usable medium, comprising: means for causing a determination that the targeted data element needs to be accessed from the related data element; means for causing a use of a direct pointer data structure, associated with the related data element, having a first location of the targeted data element, a partition identifier of the targeted data element, and a first reorganization number associated with the location of the targeted data element for comparing the first reorganization number to a second reorganization number in memory for the targeted data element; means for causing a use of the first location to locate the targeted data element if the first reorganization number and the second reorganization number are the same; and means for causing a use of an indirect index data structure, that is updated with a newer location of the targeted data element when the targeted data element is moved, to locate the targeted data element using the newer location if the first reorganization number and the second reorganization number are different.
Claim 27
Dependent Claim
200 words
A program product, for use with a database system having at least one related data element related to a targeted data element, the program product having program code, on a computer usable medium, comprising: means for causing a determination that the targeted data element needs to be accessed from the related data element; means for causing a use of a direct pointer data structure, associated with the related data element, having a first location of the targeted data element, a partition identifier of the targeted data element, and a first reorganization number associated with the location of the targeted data element for comparing the first reorganization number to a second reorganization number in memory for the targeted data element; means for causing a use of the first location to locate the targeted data element if the first reorganization number and the second reorganization number are the same; and means for causing a use of an indirect index data structure, that is updated with a newer location of the targeted data element when the targeted data element is moved, to locate the targeted data element using the newer location if the first reorganization number and the second reorganization number are different.
References Cited (Backward Citations)
US5222235A
Cited
US5555409A
Cited
US5481701A
Cited
US5596747A
Cited
US5408654A
Cited
US5517641A
Cited
US5412805A
Cited
US5555371A
Cited
JPH07152615A
Cited
US5434994A
Cited
US5581765A
Cited
US5721915A
Cited
US5625817A
Cited
US5787476A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-02 | 2003-02-01 | 2003-08-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-02 | 2007-02-01 | 2007-08-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-02 | 2011-02-01 | 2011-08-03 | $7700.00 | Window Closed / Lapsed |