US 5,485,607 A · Concurrency-control method and apparatus in a database management system utilizing key-valued locking

For managing a database of accessible records that contain resources of first and second types, each of a plurality of the resources of the second type being uniquely associated with a respective resource of the first type, and for providing accesses to the resources in response to implementing instructions of user-requested transactions, a method comprising the steps of:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of composite lock modes, which pairs of the composite lock modes are compatible with each other, the lock manager maintaining a lock table that identifies locked database resources and the composite lock modes in which they are locked, receiving lock requests that designate resources and composite lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the resources of the first and second types that each resource of the second type is mapped to a resource identifier the same as that to which the resource of the first type associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including a set of operations that includes a plurality of operations of which each requires locks both on at least one resource of the first type and on the resource of the second type with which it is associated, the lock requests applied to the lock manager by the instructions that implement such a transaction's operations requesting, in the absence of an already existing lock acquired by the given transaction, a composite lock whose mode is associated with constituent first-resource-type and second-resource-type lock modes whose compatibility sets within a set of constituent lock modes would be sufficient to maintain serializability if the constituent first-resource-type and second-resource-type lock modes individually locked the resources of the first and second resource types, respectively, on which that operation requires locks, a given composite lock mode being compatible with another composite lock mode if and only if the constituent first-resource-type and second-resource-type lock modes associated with the given composite lock mode are respectively compatible with the first-resource-type and second-resource-type lock modes associated with that other composite lock mode.

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next range, insert-next-range, scan, and updated modes and indicating that the delete-next-range mode is incompatible with the insert-next range mode and the scan mode but compatible with the update mode which the compatibility matrix indicates to be incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource-identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operation scans;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of an already existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the insert-next-range mode and including a resource identifier that, before insertion of the record to be inserted, represents the key-value range that encompasses the key value thereof;
and
iv) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the update mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby one transaction's scan of, or insertion of a record into, a key range from which a record has been deleted by another uncommitted transaction can be prevented without preventing the one transaction from updating the record whose key value is associated with that key range.

6 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix:including delete-next-range, singleton-read, and scan modes and indicating that the delete-next-range mode is incompatible with the scan mode but compatible with the singleton-read mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan-read operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of a previous existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby a scan by one transaction of a key range from which a record has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from reading the record whose key value is associated with that key range, and whereby deletion by one transaction of a record whose key value is immediately in front of that of an existing key value of a record read by another uncommitted transaction can be permitted without permitting deletion by the one transaction of a record whose key is in a range that has been scanned by another uncommitted transaction.

4 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including scan, singleton-read, and insert-next-range modes and indicating that the insert-next-range mode is compatible with the singleton-read mode but is incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby insertion by one transaction of a record into a key range that has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from inserting a record into a key range associated with a key value contained in a record accessed in a singleton-read operation by another uncommitted transaction.

5 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a method comprising the steps of:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including a singleton update mode, an update-scan mode, and an insert-next-range mode and indicating that the insert-next-range mode is incompatible with the update-scan mode but compatible with the singleton-update mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) an update-scan operation that scans through key value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement the update-scan operations requesting, in the absence of an already existing lock acquired by the same transaction, locks of update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the update-next-range mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby an insert by one transaction of a record into a range associated with the key value of a record updated by another uncommitted transaction can be permitted while insertion into a range in which another uncommitted transaction has performed an update scan is prevented.

5 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a resource manager method comprising:

A) providing a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next-range, insert-next-range, scan, and updated modes and indicating that the delete-next-range mode is incompatible with the insert-next range mode and the scan mode but compatible with the update mode which the compatibility matrix indicates to be incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) providing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operation scans;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of an already existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the insert-next-range mode and including a resource identifier that, before insertion of the record to be inserted, represents the key-value range that encompasses the key value thereof;
and
iv) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the update mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls, whereby one transaction's scan of, or insertion of a record into, a key range from which a record has been deleted by another uncommitted transaction can be prevented without preventing the one transaction from updating the record whose key value is associated with that key range.

5 more elements

A database-management system for managing a database of accessible records that contain resources of first and second resource types, each of a plurality of the resources of the second type being uniquely associated with a respective resource of the first type, and for providing accesses to the resources in response to implementing instructions of user-requested transactions, the database-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of composite lock modes, which pairs of the composite lock modes are compatible with each other, the lock manager maintaining a lock table that identifies locked database resources and the composite lock modes in which they are locked, receiving lock requests that designate resources and composite lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) a query compiler for receiving a transaction definition from a database definer and compiling the transaction definition into a transaction routine for performing a transaction, the transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the resources of the first and second resource types that each resource of the second type is mapped to a resource identifier the same as that to which the resource of the first type associated therewith is mapped, the query compiler selecting the database-access operations in accordance with the transaction definitions from among a set of operations that includes a plurality of operations of which each acquires locks both on the at least one resource of the first type and on the resource of the second type with which it is associated, the lock requests applied to the lock manager by the instructions that implement such a transaction's operations requesting, in the absence of an already existing lock acquired by the given transaction, a composite lock whose mode is associated with constituent first-resource-type and second-resource-type lock modes whose compatibility sets within a set of constituent lock modes would be sufficient to maintain serializability if the constituent first-resource-type and second-resource-type lock modes individually locked the resources of the first and second resource types, respectively, on which that operation requires locks, a given composite lock mode being compatible with another composite lock mode if and only if the constituent first-resource-type and second-resource-type lock associated with the given composite lock mode are respectively compatible with the first-resource-type and second-resource-type lock modes associated with that other composite lock mode.

A database-management system for managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to an existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, the database-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next-range, insert-next-range, scan, and update modes and indicating that the delete-next-range mode is incompatible with the insert-next range mode and the scan mode but compatible with the update mode, which the compatibility matrix indicates to be incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) a query compiler for receiving a transaction definition from a database definer and compiling the transaction definition into a transaction routine for performing a transaction, the transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the query compiler selecting the database-access operations in accordance with the transaction definitions from among at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operation scans;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of an already existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the insert-next-range mode and including a resource identifier that, before insertion of the record to be inserted, represents the key-value range that encompasses the key value thereof;
and
iv) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the update mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby one transaction's scan of, or insertion of a record into, a key range from which a record has been deleted by another uncommitted transaction can be prevented without preventing the one transaction from updating the record whose key value is associated with that key range.

6 more elements

A database-management system for managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, the database-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next-range, singleton-read, and scan modes and indicating that the delete-next-range mode is incompatible with the scan mode but compatible with the singleton-read mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) a query compiler for receiving a transaction definition from a database definer and compiling the transaction definition into a transaction routine for performing a transaction, the transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the query compiler selecting the database-access operations in accordance with the transaction definitions from among at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan-read operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of a previous existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby a scan by one transaction of a key range from which a record has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from reading the record whose key value is associated with that key range, and whereby deletion by one transaction of a record whose key value is immediately in front of that of an existing key value of a record read by another uncommitted transaction can be permitted without permitting deletion by the one transaction of a record whose key is in a range that has been scanned by another uncommitted transaction.

4 more elements

A database-management system for managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, the database-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including scan, singleton-read, and insert-next-range modes and indicating that the insert-next-range mode is compatible with the singleton-read mode but is incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) a query compiler for receiving a transaction definition from a database definer and compiling the transaction definition into a transaction routine for performing a transaction, the transaction routine comprising instructions that implement database-access operations, associated with respective dam base accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the query compiler selecting the database-access operations in accordance with the transaction definitions from among at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby insertion by one transaction of a record into a key range that has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from inserting a record into a key range associated with a key value contained in a record accessed in a singleton-read operation by another uncommitted transaction.

5 more elements

A database-management system for managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, the database-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including a singleton-update mode, an update-scan mode, and an insert-next-range mode and indicating that the insert-next-range mode is incompatible with the update-scan mode but compatible with the singleton-update mode, the lock manager maintaining a lock table that identifies locked-database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) a query compiler for receiving a transaction definition from a database definer and compiling the transaction definition into a transaction routine for performing a transaction, the transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the query compiler selecting the database-access operations in accordance with the transaction definitions from among at least:
i) an update-scan operation that scans through key-value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement the update-scan operations requesting, in the absence of an already existing lock acquired by the same transaction, locks of update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the update-next-range mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby an insert by one transaction of a record into a range associated with the key value of a record updated by another uncommitted transaction can be permitted while insertion into a range in which another uncommitted transaction has performed an update scan is prevented.

5 more elements

A resource-management system for managing a database of accessible records that contain resources of first and second types, each of a plurality of the resources of the second type being uniquely associated with a respective resource of the first type, and for providing accesses to the resources in response to implementing instructions of user-requested transactions, the resource-management system comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of composite lock modes, which pairs of the composite lock modes are compatible with each other, the lock manager maintaining a lock table that identifies locked database resources and the composite lock modes in which they are locked, receiving lock requests that designate resources and composite lock modes in which those resources are to be locked, and responding to .the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible in accordance with the compatibility matrix with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) means for executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the resources of the first and second types that each resource of the second type is mapped to a resource identifier the same as that to which the resource of the first type associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including a set of operations that includes a plurality of operations of which each requires locks both on at least one resource of the first type and on the resource of the second type with which it is associated, the lock requests applied to the lock manager by the instructions that implement such a transaction's operations requesting, in the absence of an already existing lock acquired by the given transaction, a composite lock whose mode is associated with constituent first-resource-type and second-resource-type lock modes whose compatibility sets within a set of constituent lock modes would be sufficient to maintain serializability if the constituent first-resource-type and second-resource-type lock modes individually locked the resources of the first and second resource types, respectively, on which that operation requires locks, a given composite lock mode being compatible with another composite lock mode if and only if the constituent first-resource-type and second-resource-type lock modes associated with the given composite lock mode are respectively compatible with the first-resource-type and second-resource-type lock modes associated with that other composite lock mode.

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a resource manager comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including delete-next-range, singleton-read, and scan modes and indicating that the delete-next-range mode is incompatible with the scan mode but compatible with the singleton-read mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) means for executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager land perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan-read operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) a delete operation that deletes a record, one said lock request applied to the lock manager by the instructions that implement the delete operation in a given transaction requesting, in the absence of a previous existing lock acquired by the given transaction, a lock of the delete-next-range mode and including a resource identifier that represents the key-value range immediately behind the range with which the key value of the record to be deleted is associated;
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the given transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby a scan by one transaction of a key range from which a record has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from reading the record whose key value is associated with that key range, and whereby deletion by one transaction of a record whose key value is immediately in front of that of an existing key value of a record read by another uncommitted transaction can be permitted without permitting deletion by the one transaction of a record whose key is in a range that has been scanned by another uncommitted transaction.

4 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a resource manager comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including scan, singleton-read, and insert-next-range modes and indicating that the insert-next-range mode is compatible with the singleton-read mode but is incompatible with the scan mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the, lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) a scan operation that scans through key-value ranges, lock requests applied to the lock manager by the instructions that implement a given transaction's scan operations requesting, in the absence of an already existing lock acquired by the given transaction, locks of the scan mode and including resource identifiers that represent the key-value ranges through which the scan operations scan;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the insert operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) a singleton-read operation that reads a single record, one said lock request applied to the lock manager by the instructions that implement the singleton-read operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the singleton-read mode and including a resource identifier that represents the key value of the record to be read,
whereby insertion by one transaction of a record into a key range that has been deleted by another, uncommitted transaction can be prevented without preventing the one transaction from inserting a record into a key range associated with a key value contained in a record accessed in a singleton-read operation by another uncommitted transaction.

5 more elements

For managing a database of accessible records that contain respective existing key values belonging to an ordered sequence of possible key values divided into key-value ranges, each of a plurality of which extends from an existing key value uniquely associated therewith to the existing key value immediately in front of the associated key value, and for providing accesses to the records in response to implementing instructions of user-requested transactions, a resource manager comprising:

A) a lock manager characterized by a predetermined compatibility matrix that indicates, for a plurality of lock modes, which pairs of the lock modes are compatible with each other, the compatibility matrix including a singleton-update mode, an update-scan mode, and an insert-next-range mode and indicating that the insert-next-range mode is incompatible with the update-scan mode but compatible with the singleton-update mode, the lock manager maintaining a lock table that identifies locked database resources and the modes in which they are locked, receiving lock requests that designate resources and lock modes in which those resources are to be locked, and responding to the lock requests by generating compatibility indications that indicate whether the lock modes designated by the lock requests are compatible, in accordance with the compatibility matrix, with the lock modes of locks acquired by other transactions on the database resources that the lock requests designate;
and
B) means for executing a plurality of transaction routines for performing respective transactions, each transaction routine comprising instructions that implement database-access operations, associated with respective database accesses, that apply lock requests to the lock manager and perform the associated database accesses only if the compatibility indications generated by the lock manager in response to the lock requests are positive, the resource identifiers in the lock requests being so mapped from the key values and ranges that the resource identifier to which each range is mapped is the same as that to which the key value associated therewith is mapped, the database-access operations implemented by the instructions of the plurality of transaction routines including at least:
i) an update-scan operation that scans through key-value ranges and updates records having key values in those ranges, lock requests applied to the lock manager by the instructions that implement the update-scan operations requesting, in the absence of an already existing lock acquired by the same transaction, locks of update-scan mode and including resource identifiers that represent the key-value ranges through which the update-scan operation scans;
ii) an insert operation that inserts a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the insert-next-range mode and including a resource identifier that represents the key-value range that, before insertion of the record to be inserted, encompasses the key value thereof;
and
iii) an update operation that updates a record, one said lock request applied to the lock manager by the instructions that implement the update operation in a given transaction requesting, in the absence of an already-existing lock acquired by the same transaction, a lock of the update-next-range mode and including a resource identifier that represents the key-value range into which the key value of the record to be updated falls,
whereby an insert by one transaction of a record into a range associated with the key value of a record updated by another uncommitted transaction can be permitted while insertion into a range in which another uncommitted transaction has performed an update scan is prevented.

5 more elements

Concurrency-control method and apparatus in a database management system utilizing key-valued locking

Life of this patent

Concurrency-control method and apparatus in a database management system utilizing key-valued locking

Life of this patent

Abstract

Claims30