Enforcing temporal uniqueness of index keys utilizing key-valued locking in the presence of pseudo-deleted keys

A computer-readable storage medium containing computer program code that, when executed, performs an operation for identifying conflicts between an index of temporal keys and a prospective temporal key to be inserted into the index, wherein the temporal keys in the index are sorted based at least in part on a time value associated with each of the temporal keys, and wherein the prospective temporal key specifies a prospective range of time, the operation comprising:

• scanning the index of temporal keys in sorted order to identify a first temporal key that potentially conflicts with the prospective temporal key, wherein the first temporal key specifies a first range of time, and wherein the first temporal key is identified based on a comparison of at least one of (i) a starting time value associated with the first range of time with an ending time value associated with the prospective range of time and (ii) an ending time value associated with the first range of time with a starting time value associated with the prospective range of time;
• and
• determining whether the prospective temporal key conflicts with any temporal keys in the index of temporal keys, such that the prospective temporal key conflicts with the first temporal key if the first range of time overlaps with the prospective range of time and the first temporal key is not a pseudo-deleted key, and such that the prospective temporal key does not conflict with any temporal keys in the index of temporal keys if the temporal key does not conflict with the first temporal key.

A system, comprising:

• a processor;
• and
• a memory containing a program that, when executed, performs an operation for identifying conflicts between an index of temporal keys and a prospective temporal key to be inserted into the index, wherein the temporal keys in the index are sorted based at least in part on a time value associated with each of the temporal keys, and wherein the prospective temporal key specifies a prospective range of time, the operation comprising:
• scanning the index of temporal keys in sorted order to identify a first temporal key that potentially conflicts with the prospective temporal key, wherein the first temporal key specifies a first range of time, and wherein the first temporal key is identified based on a comparison of at least one of (i) a starting time value associated with the first range of time with an ending time value associated with the prospective range of time and (ii) an ending time value associated with the first range of time with a starting time value associated with the prospective range of time;
• and
• determining whether the prospective temporal key conflicts with any temporal keys in the index of temporal keys, such that the prospective temporal key conflicts with the first temporal key if the first range of time overlaps with the prospective range of time and the first temporal key is not a pseudo-deleted key, and such that the prospective temporal key does not conflict with any temporal keys in the index of temporal keys if the temporal key does not conflict with the first temporal key.