Enforcing temporal uniqueness of index keys utilizing key-valued locking in the presence of pseudo-deleted keys
AssigneeInternational Business Machines Corporation
InventorsRobert W. Lyle, Ping Wang
Life of this patent
Estimating the term…
Abstract
Techniques are described for identifying conflicts between a prospective temporal key and an index of temporal keys, the index sorted based on a time value associated with each of the temporal keys. Embodiments determine whether a first temporal key within the index of temporal keys conflicts with the prospective temporal key. Here, the keys within the index may be sorted based upon a respective time value associated with each of the keys. Upon determining that the first temporal key conflicts with the prospective temporal key, the prospective temporal key is designated as conflicting with at least one existing temporal key in the index of temporal keys.
Claims8
A method 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, comprising:
- determining whether a first range of time specified by a first temporal key within the index of temporal keys overlaps with a prospective range of time specified by the prospective temporal key;
- and
- determining whether the prospective temporal key conflicts with any temporal keys in the index of temporal keys, wherein 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 further comprising:
- scanning the index of temporal keys to identify a next temporal key that potentially conflicts with the prospective temporal key;
- and
- determining whether the prospective temporal key conflicts with the next key, based on whether the prospective range of time conflicts with a next range of time specified by the next temporal key and whether the next temporal key is a pseudo-deleted key,
- wherein the scanning and determining are repeated until (i) a first temporal key with a different principal key value from the prospective temporal key is found, (ii) a non-overlapping temporal key that is not pseudo-deleted is found, or (iii) no potentially conflicting keys remain in the index.
A method 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, comprising:
- determining whether a first range of time specified by a first temporal key within the index of temporal keys overlaps with a prospective range of time specified by the prospective temporal key;
- determining whether the prospective temporal key conflicts with any temporal keys in the index of temporal keys, wherein 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
- upon determining that the prospective temporal key does not conflict with the first temporal key:
- scanning the index of temporal keys to identify the next temporal key that potentially conflicts with the prospective temporal key, wherein the next temporal key specifies a next range of time;
- and
- determining whether the prospective temporal key conflicts with the next key, wherein the prospective temporal key conflicts with the next temporal key if the next range of time overlaps with the prospective range of time and the next temporal key is not a pseudo-deleted key,
- wherein the scanning and determining are repeated until (i) a first temporal key with a different principal key value from the prospective temporal key is found, (ii) a non-overlapping temporal key that is not pseudo-deleted is found, the non-overlapping temporal key having a starting time after an ending time of the prospective temporal key, or (iii) no potentially conflicting keys remain in the index.
Dependencies are inferred from the claim text.