US6009425A
Expired / Lapsed
US
⏱️ 0.0 years remaining
System and method for performing record deletions using index scans
Assignee: International Business Machines Corp
•
Filing: 1996-08-21
•
Granted: 1999-12-28
•
Expires: 2016-08-21
Abstract
Abstract A data manager of a relational database management system (RDBMS) receives a command, such as a DELETE. As the RDBMS processes this command, an index manager looks at cursor control block information about the scan position (page number, logical key position within page and log sequence number (LSN) of the page) and immediately accesses the corresponding leaf page to do the key deletion. If the page's log sequence number has not changed since the scan was positioned on it, the index manager knows precisely where the key is and deletes it right away. Even if the page's log sequence number has changed, the index manager checks to see if the key is still on the same page. Only if the key is not on that page anymore will the index manager traverse the tree from the root to locate the key. Using this same information, together with a return -- current flag in the cursor control block, the method can easily determine the next key in the sequence. The return -- current flag is set when the current key is deleted. If the leaf page's log sequence number has not changed since the deletion and the return -- current flag is set, the method of the invention establishes that the key which now resides in the same logical position as the previously deleted key is the next key, and may be returned as such. If the LSN is the same and the return -- current flag is not set, then the next key is returned following locking. If the LSN has changed but the key is still bound on the page, the next key is searched and located, a lock is asserted (if necessary) and the key is returned. Only if the page logical sequence number has changed and the previous key is no longer bound on the page will the index manager traverse the index tree to locate the next key, lock the key (if necessary) and return it.
Inventors
- 👤 Chandrasekaran Mohan
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 22:22
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2455; G06F16/24553; G06F16/24554; G06F16/24557; G06F16/22; G06F16/2228; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99938; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
210 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a method for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising the steps of: selecting the plurality of records using a range scan; traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); storing cursor information representing the location of said current key in a cursor data structure; performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said current key; and if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key, using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure.
Claim 2
Dependent Claim
210 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a method for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising the steps of: selecting the plurality of records using a range scan; traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); storing cursor information representing the location of said current key in a cursor data structure; performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said current key; and if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key, using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure.
Claim 3
Dependent Claim
75 words
A method as recited in claim 1, further comprising the steps of: determining whether said current key's tree position has been affected by a concurrent operation following updating of said current key; and if said current key's tree position has not been affected by another concurrent operation following updating of said current key, using said cursor information to locate a next one (next key) of said sequence of record keys corresponding to a next record.
Claim 4
Dependent Claim
29 words
A method as recited in claim 2 wherein said cursor data structure includes fields for determining whether said current key's tree position has been affected by a concurrent operation.
Claim 5
Dependent Claim
69 words
A method as recited in claim 3 wherein said current key is located on a page representing a leaf node of said index tree structure and wherein said fields for determining whether said current key's tree position has been affected by a concurrent operation include a field representing a page number on which said current key is located and a field representing a log sequence number of said page.
Claim 6
Dependent Claim
45 words
A method as recited in claim 4 wherein said step of determining whether said current key's tree position has been affected by a concurrent operation following retrieval or update of said current key includes determining whether changes have occurred to said page's log sequence number.
Claim 7
Dependent Claim
30 words
A method as recited in claim 5 wherein said cursor information is used to update said current key if the page number corresponding to said current key has not changed.
Claim 8
Dependent Claim
50 words
A method as recited in claim 2 wherein said cursor data structure further includes a field for determining whether said current key was updated in order to help locate said next key when said current key has not been affected by a concurrent operation following updating of said current key.
Claim 9
Dependent Claim
99 words
A method as recited in claim 1, further comprising the step of, upon locating said current key, determining whether additional operational predicates exist and, if true, asserting a nonexclusive lock on said current record, if record locking is being performed by said database management system, or on said current key, if index-specific locking is being performed by said database management system, and, if false, asserting an exclusive lock on said current record, if record locking is being performed by said database management system, or on said current key, if index-specific locking is being performed by said database management system.
Claim 10
Dependent Claim
54 words
A method as recited in claim 8, wherein said record operation is a record delete or update operation and said current key is updated by deleting said key, and further wherein said step of locking said current record or said current key includes the step of locking said next record or next key, respectively.
Claim 11
Dependent Claim
33 words
A method as recited in claim 8 wherein said cursor data structure includes a field for determining the status of the lock on said current key or the lock on said current record.
Claim 12
Dependent Claim
218 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a system for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising: means for selecting the plurality of records using a range scan; means for traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); means for storing cursor information representing the location of said current key in a cursor data structure; means for performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; means for determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said key; and means for using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure, if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key.
Claim 13
Dependent Claim
218 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a system for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising: means for selecting the plurality of records using a range scan; means for traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); means for storing cursor information representing the location of said current key in a cursor data structure; means for performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; means for determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said key; and means for using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure, if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key.
Claim 14
Dependent Claim
75 words
A system as recited in claim 11, further comprising: means for determining whether said current key's tree position has been affected by concurrent operation following updating of said current key; and means for using said cursor information to locate a next one (next key) of said sequence of record keys corresponding to a next record, if said current key's tree position has not been affected by a concurrent operation following updating of said current key.
Claim 15
Dependent Claim
29 words
A system as recited in claim 12 wherein said cursor data structure includes fields for determining whether said current key's tree position has been affected by a concurrent operation.
Claim 16
Dependent Claim
69 words
A system as recited in claim 13 wherein said current key is located on a page representing a leaf node of said index tree structure and wherein said fields for determining whether said current key's tree position has been affected by a concurrent operation include a field representing a page number on which said current key is located and a field representing a log sequence number of said page.
Claim 17
Dependent Claim
47 words
A system as recited in claim 14 wherein said means for determining whether said current key's tree position has been affected by a concurrent operation following retrieval or update of said current key includes means for determining whether changes have occurred to said page's log sequence number.
Claim 18
Dependent Claim
30 words
A system as recited in claim 15 wherein said cursor information is used to update said current key if the page number corresponding to said current key has not changed.
Claim 19
Dependent Claim
50 words
A system as recited in claim 12 wherein said cursor data structure further includes a field for determining whether said current key was updated in order to help locate said next key when said current key has not been affected by a concurrent operation following updating of said current key.
Claim 20
Dependent Claim
98 words
A system as recited in claim 11, further comprising means for determining, upon locating said current key, whether additional operational predicates exist and, if true, asserting a nonexclusive lock on said current record, if record locking is being performed by said database management system or on said current key, if index-specific locking is being performed by said database management system, and, if false, asserting an exclusive lock on said current record, if record locking is being performed by said database management system, or on said current key, if index-specific locking is being performed by said database management system.
Claim 21
Dependent Claim
53 words
A system as recited in claim 18, wherein said record operation is a record delete or update operation and said current key is updated by deleting said key, and further wherein said means for locking said current record or said current key includes means for locking said next record or next key, respectively.
Claim 22
Dependent Claim
33 words
A system as recited in claim 18 wherein said cursor data structure includes a field for determining the status of the lock on said current key or the lock on said current record.
Claim 23
Dependent Claim
260 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a computer program product for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising: a data storage medium; means recorded on said data storage medium for selecting the plurality of records using a range scan; means recorded on said data storage medium for traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); means recorded on said data storage medium for storing cursor information representing the location of said current key in a cursor data structure; means recorded on said data storage medium for performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; means recorded on said data storage medium for determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said key; and means recorded on said data storage medium for using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure, if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key.
Claim 24
Dependent Claim
260 words
For use with a data base management system in which a cursor is used for specifying one of a plurality of records in a data structure within a data base, a computer program product for performing an operation on the plurality of records within the data structure, the records having related locations searchable in an index file configured as a tree structure and containing a sequence of record keys, comprising: a data storage medium; means recorded on said data storage medium for selecting the plurality of records using a range scan; means recorded on said data storage medium for traversing the tree structure to retrieve a first one of said sequence of record keys (hereinafter referred to as the "current key"); means recorded on said data storage medium for storing cursor information representing the location of said current key in a cursor data structure; means recorded on said data storage medium for performing an operation (hereinafter referred to as the "record operation") on a record (hereinafter referred to as the "current record") corresponding to said current key; means recorded on said data storage medium for determining whether said current key's tree position has been affected by a concurrent operation following retrieval of said key; and means recorded on said data storage medium for using said cursor information in said cursor data structure to locate and update said current key to reflect said record operation without retraversing the tree structure, if determined that said current key's tree position has not been affected by a concurrent operation following retrieval of said key.
Claim 25
Dependent Claim
90 words
A computer program product as recited in claim 21, further comprising: means recorded on said data storage medium for determining whether said current key's tree position has been affected by a concurrent operation following updating of said current key; and means recorded on said data storage medium for using said cursor information to locate a next one (next key) of said sequence of record keys corresponding to a next record, if said current key's tree position has not been affected by a concurrent operation following updating of said current key.
Claim 26
Dependent Claim
31 words
A computer program product as recited in claim 22 wherein said cursor storage structure includes fields for determining whether said current key's tree position has been affected by a concurrent operation.
Claim 27
Dependent Claim
71 words
A computer program product as recited in claim 23 wherein said current key is located on a page representing a leaf node of said index tree structure and wherein said fields for determining whether said current key's tree position has been affected by a concurrent operation include a field representing a page number on which said current key is located, and a field representing a log sequence number of said page.
Claim 28
Dependent Claim
55 words
A computer program product as recited in claim 24 wherein said means for determining whether said current key's page position has been affected by a concurrent operation following retrieval or update of said current key includes means recorded on said data storage medium for determining whether changes have occurred to said page's log sequence number.
Claim 29
Dependent Claim
32 words
A computer program product as recited in claim 25 wherein said cursor information is used to update said current key if the page number corresponding to said current key has not changed.
Claim 30
Dependent Claim
52 words
A computer program product as recited in claim 22 wherein said cursor data structure further includes a field for determining whether said current key was updated in order to help locate said next key when said current key has not been affected by a concurrent operation following updating of said current key.
Claim 31
Dependent Claim
106 words
A computer program product as recited in claim 21, further comprising means recorded on said data storage medium for determining, upon locating said current key, whether additional operational predicates exist and, if true, asserting a nonexclusive lock on said current record, if record locking is being performed by said database management system, or on said current key, if index-specific locking is being performed by said database management system, and, if false, asserting an exclusive lock on said current record, if record locking is being performed by said database management system, or on said current key, if index-specific locking is being performed by said database management system.
Claim 32
Dependent Claim
59 words
A computer program product as recited in claim 28, wherein said record operation is delete or update operation and said current key is updated by deleting said key, and further wherein said means for locking said current record or said current key includes means recorded on said data storage medium for locking said next record or next key, respectively.
Claim 33
Dependent Claim
35 words
A computer program product as recited in claim 28 wherein said cursor data structure includes a field for determining the status of the lock on said current key or the lock on said current record.
References Cited (Backward Citations)
US3916387A
Cited
US4677550A
Cited
US4754326A
Cited
US5010478A
Cited
US4821336A
Cited
US5237678A
Cited
US4823310A
Cited
US4914569A
Cited
US4945474A
Cited
US5123104A
Cited
US4965516A
Cited
US5218696A
Cited
US5230047A
Cited
US5537574A
Cited
US5430869A
Cited
US5475837A
Cited
US5551046A
Cited
US5490258A
Cited
US5495609A
Cited
US5551027A
Cited
US5485607A
Cited
US5440732A
Cited
US5560007A
Cited
US5812996A
Cited
US5694608A
Cited
US5717919A
Cited
US5832508A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-12-27 | 2003-06-28 | 2003-12-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-12-27 | 2007-06-28 | 2007-12-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-12-27 | 2011-06-28 | 2011-12-28 | $7700.00 | Window Closed / Lapsed |