System and method for avoiding deadlock situations due to pseudo-deleted entries

• US 20030004945A1
• Filed: 06/28/2001
• Published: 01/02/2003
• Est. Priority Date: 06/28/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Teng, James Zu-Chia, Hrle, Namik
• Granted Patent: US 6,944,615 B2
• Time in Patent Office: Days
• US Class Current: 707/8
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users

Abstract

In a database management system (DBMS) (60) for a database application (10) including a database (12) having a table (14, 16, 18) and a unique key index (42) having indexes (44, 46, 48) therefor, the DBMS (60) includes a data manager (64), an index manager (66), a transaction manager (62), and a lock manager (68) which restricts access to the table by assigning locks to elements thereof. In order to avoid deadlock in the database application due to the pseudo-deleted entries, the lock categories include an X-lock and a Conditional S-lock, and have lock attributes including at least a Delete attribute for the X-lock. The Conditional S-lock is compatible (granted by the lock manager) with an X-lock whose Delete attribute is NOT SET, but is not compatible (granted) with an X-lock whose Delete attribute is SET. Each index entry includes a pseudo-delete flag which is SET by the index manager (66) to indicate deletion of the indexed row. Conditional upon locating a pseudo-deleted index key corresponding to a key to be added to the index, the index manager (66) requests a Conditional S-lock on the row indexed thereby, whereby the index manager (66) verifies the Delete transaction which set the pseudo-delete flag has committed.

Claims

1. A database management system (DBMS) for managing a database application, the database application including a database having at least one table, and an index having at least one unique key index table corresponding to the at least one table, the DBMS comprising:

a data manager for managing updates of the database;

an index manager for managing updates of the unique key table index;

a transaction manager for executing database transactions in cooperation with the data manager and the index manager; and

,

a lock manager cooperative with the index manager and the data manager for restricting access to a first table element of said at least one table by assigning one or more locks thereto, said locks being selected from a plurality of lock types including at least,

an exclusive X-lock that enables exclusive access to the first table element, the exclusive X-lock including a Delete attribute associated therewith, a SET state of the Delete attribute being indicative of a transaction holding the X-lock being a delete transaction; and

,

an unconditional S-lock that enables shared access to the first table element and is selectively assigned by the lock manager to the first table element only when the first table element is without an exclusive X-lock previously assigned thereto.

2. The DBMS as set forth in claim 1, wherein:

the plurality of lock types further includes a Conditional S-lock that enables shared access to the first table element; and

,

the lock manager selectively assigns the Conditional S-lock to the first table element only when the first table element is without an exclusive X-lock previously assigned thereto with the Delete attribute in a SET state.

3. The DBMS as set forth in claim 2, wherein:

the unique key index table further includes a pseudo-delete flag corresponding to each key entry of the unique key index table; and

,

the index manager selectively SETs the pseudo-delete flag to indicate deletion of a table row corresponding to the index key entry.

4. The DBMS as set forth in claim 3, wherein in response to receiving a request from the index manager to enter an index key entry and a corresponding new row identification RID in which the index key entry corresponds to an existing index key entry whose pseudo-delete flag SET, the index manager is operative to:

request a Conditional S-lock on the table row corresponding to the existing index key en try; and

,

conditional upon the Conditional S-lock on the table row corresponding to the existing index key entry being granted by the lock manager, update the table index key entry with the new row identification RID, release the Conditional S-lock on the table row corresponding to the existing index key entry, and reset the pseudo-delete flag to and OFF state.

5. The DBMS as set forth claim 4, wherein in response to receiving a request from the index manager to enter an index key entry and a corresponding new row identification RID in which the index key entry corresponds to an existing index key entry whose pseudo-delete flag is SET, the index manager is adapted to:

conditional upon the Conditional S-lock on the table row corresponding to the existing index key entry being denied by the lock manager, request an unconditional S-lock on the table row corresponding to the existing index key entry; and

,

upon granting of the unconditional S-lock by the lock manager, update the table index key entry with the new row identification RID, release the unconditional S-lock, and reset the pseudo-delete flag.

6. The DBMS as set forth in claim 3, wherein in response to receiving a request from the index manager to enter an index key entry and a corresponding new row identification RID in which the index key entry corresponds to an existing index key entry whose pseudo-delete flag is NOT SET, RESET, or OFF, the index manager is operative to:

request an unconditional S-lock on the table row corresponding to the existing index key entry; and

,

upon granting of the unconditional S-lock on the table row corresponding to the existing index key entry by the lock manager and conditional upon the index key entry having its pseudo-delete flag SET, update the table index key entry with the new row identification RID, release the unconditional S-lock, and reset the pseudo-delete flag.

7. A database management method for entering a key and a new row identification RID into a unique key table index of a database application that uses pseudo-deletion of table index entries, comprising:

searching the unique key table index for the key;

when a pseudo-deleted table index entry corresponding to the key is located during the searching step;

requesting a Conditional S-lock on a table row indexed by the pseudo-deleted table index entry; and

,

conditional upon receiving an indication that the Conditional S-lock is granted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag; and

,

conditional upon not locating a table index entry corresponding to the key during the searching step, updating the table index by adding the key and the new row identification RID.

8. The method according to claim 7, wherein the step of receiving an indication that the Conditional S-lock is granted includes the steps of:

granting the Conditional S-lock conditional upon the table row indexed by the pseudo-deleted table index entry not having an X-lock assigned thereto;

granting the Conditional S-lock conditional upon the table row indexed by the pseudo-deleted table index entry having an X-lock assigned thereto wherein said X-lock has a Delete attribute that is not set, reset, or off; and

receiving an indication that the Conditional S-lock is granted conditional upon the granting of the Conditional S-lock.

9. The method according to claim 8, further including the steps:

conditional upon receiving an indication that the Conditional S-lock is denied;

requesting an unconditional S-lock on the table row indexed by the pseudo-deleted table index entry; and

conditional upon receiving an indication that the unconditional S-lock is granted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag.

10. The method according to claim 7, further including the steps:

conditional upon locating a table index entry that is not pseudo-deleted during the searching step;

requesting an unconditional S-lock on the table row indexed by the located table index entry; and

upon granting of the unconditional S-lock and conditional upon the located table index entry being pseudo-deleted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag.

11. An article of manufacture comprising a program storage medium readable by a computer and embodying one or more instructions executable by the computer to perform method steps for entering a key and a new row RID into a unique key table index of a database stored on a data store connected to the computer, the unique key table index using pseudo-deletion of table index entries, the method comprising the steps of:

searching the unique key table index for the key;

conditional upon locating a pseudo-deleted table index entry corresponding to the key during the searching step;

requesting a Conditional S-lock on a table row indexed by the pseudo-deleted table index entry, and

conditional upon receiving an indication that the Conditional S-lock is granted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag; and

,

conditional upon not locating a table index entry corresponding to the key during the searching step, updating the table index by adding the key and the new row identification RID.

12. The article of manufacture according to claim 11, wherein the step of receiving an indication that the Conditional S-lock is granted includes the steps of:

granting the Conditional S-lock conditional upon the table row indexed by the pseudo-deleted table index entry not having an X-lock assigned thereto;

granting the Conditional S-lock conditional upon the table row indexed by the pseudo-deleted table index entry having an X-lock assigned thereto wherein said X-lock has a Delete attribute that is not set, reset, or off; and

receiving an indication that the Conditional S-lock is granted conditional upon the granting of the Conditional S-lock.

13. The article of manufacture according to claim 12, wherein the method further includes the steps, to be executed conditional upon receiving an indication that the Conditional S-lock is denied, of:

requesting an unconditional S-lock on the table row indexed by the pseudo-deleted table index entry; and

conditional upon receiving an indication that the unconditional S-lock is granted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag.

14. The article of manufacture according to claim 11, wherein the method further includes the steps, to be executed conditional upon locating a table index entry that is not pseudo-deleted during the searching step, of:

requesting an unconditional S-lock on the table row indexed by the located table index entry; and

upon granting of the unconditional S-lock and conditional upon the located table index entry being pseudo-deleted, updating the table index entry with the new row identification RID and resetting the pseudo-delete flag.

16. The lock manager according to claim 15, wherein:

the lock manager is adapted to restrict access to said first table element by assigning a Conditional S-lock that enables shared access to the first table element and is selectively assigned by the lock manager to the first table element only when the first table element is without an exclusive X-lock previously assigned thereto with the Delete attribute in a SET state.

17. The lock manager as set forth in claim 16, wherein:

the unique key index table further includes a pseudo-delete flag corresponding to each key entry of the unique key index table; and

,

the index manager is operative to selectively SET the pseudo-delete flag to indicate deletion of a table row corresponding to the index key entry.

18. The lock manager as set forth in claim 17, wherein:

in response to receiving a request from the transaction manager to enter an index key entry and a corresponding new row identification RID in which the index key entry corresponds to an existing index key entry whose pseudo-delete flag SET, the index manager is operative to request a Conditional S-lock on the table row corresponding to the existing index key entry; and

,

the lock manager is operative to grant the Conditional S-lock on the table row corresponding to the existing index key entry being only when;

the table row is without an exclusive X-lock assigned thereto, and the table row has an exclusive X-lock assigned thereto with the Delete attribute not in said SET state, to enable the index manager to update the table index key entry with the new row identification RID, release the Conditional S-lock on the table row corresponding to the existing index key entry, and reset the pseudo-delete flag to and OFF state.

15. A lock manager for use in a database management system (DBMS) managing a database application including a database having at least one table and cooperative with an index manager and a data manager for restricting access to a first table element of said at least one table by assigning one or more locks thereto including at least an exclusive X-lock that enables exclusive access to the first table element, the exclusive X-lock including a Delete attribute associated therewith, a SET state of the Delete attribute being indicative of a transaction holding the X-lock being a delete transaction.