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.