Deterministic database systems

• US 8,700,563 B1
• Filed: 07/13/2012
• Issued: 04/15/2014
• Est. Priority Date: 07/15/2011
• Status: Active Grant

• Current Assignee: Yale University
• Original Assignee: Yale University
• Inventors: Thomson, Alexander, Abadi, Daniel J.
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US13/548,915
• Time in Patent Office: 641 Days
• Field of Search: 707/607, 707/615, 707/705, 707/781, 707/782, 709/201, 709/203, 709/213, 709/217
• US Class Current: 707/607
• CPC Class Codes: G06F 16/1774 Locking methods, e.g. locking methods for file systems allowing shared and concurrent access to files
• CPC Class Codes: G06F 16/1865 Transactional file systems
• CPC Class Codes: G06F 16/2336 Pessimistic concurrency control approaches, e.g. locking or multiple versions without time stamps
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

In an embodiment, a plurality of transactions for accessing a database may be acquired. The database may be associated with a plurality of locks. The plurality of transactions may include a first transaction, a second transaction, and a third transaction. A logical serialization sequence for executing the transactions may be identified. The logical serialization sequence may indicate that (1) the first transaction is to be executed before the second transaction based on all locks that are required by the first transaction being available; (2) the second transaction is to be executed after the first transaction has completed execution based on the second transaction requiring a lock that is required by the first transaction; and (3) the third transaction is to be executed before or during execution of the first transaction based on all locks required by the third transaction being different than the locks required by the first transaction.

Claims

1. A method comprising:

acquiring a plurality of transactions for accessing a database, the plurality of transactions including a first transaction, a second transaction, and a third transaction, the first transaction being received before the second transaction and the third transaction being received after the second transaction, the database being associated with a plurality of locks;

identifying a logical serialization sequence for executing the first, second, and third transactions, the identifying including;

identifying that the first transaction is to be executed before the second transaction based on all locks, in the plurality of locks, that are required by the first transaction being available,

identifying that the second transaction is to be executed after the first transaction has completed execution based on the second transaction requiring a lock, in the plurality of locks, that is required by the first transaction, and

identifying that the third transaction is to be executed before or during execution of the first transaction based on all locks, in the plurality of locks, required by the third transaction being different than the locks required by the first transaction; and

executing the first, second, and third transactions, based on the identified logical serialization sequence.

2. The method of claim 1, further comprising:

decomposing the first transaction into a first access set that contains a write set or a read set associated with the first transaction;

decomposing the second transaction into a second access set that contains a write set or a read set associated with the second transaction; and

determining that a lock, in the plurality of locks, required by the first access set is also required by the second access set.

3. The method of claim 1, further comprising:

acquiring all of the locks required by the first transaction;

executing the first transaction to completion;

releasing all of the locks required by the first transaction;

acquiring all of the locks required by the second transaction; and

executing the second transaction.

4. The method of claim 1, wherein the lock required by the first transaction and the second transaction is associated with a record in the database.

5. A method comprising:

acquiring a plurality of transactions for accessing a database, the plurality of transactions including a first transaction and second transaction, the first transaction being received before the second transaction, the database being associated with a plurality of locks;

decompose the first transaction into a third transaction and a fourth transaction based on;

the first transaction including the third transaction and the fourth transaction, and

the fourth transaction being dependent on a result of the third transaction;

identifying a logical serialization sequence for executing the second and third transactions, the identifying including;

identifying that the third transaction is to be executed before the second transaction based on all locks, in the plurality of locks, that are required by the third transaction being available, and

identifying that the second transaction is to be executed after the third transaction has completed execution based on the second transaction requiring a lock, in the plurality of locks, that is required by the third transaction; and

executing the second, and third transactions, based on the identified logical serialization sequence.

6. A non-transitory tangible computer-readable medium storing computer-executable instructions for:

acquiring a plurality of transactions for accessing a database, the plurality of transactions including a first transaction, a second transaction, and a third transaction, the first transaction being received before the second transaction and the third transaction being received after the second transaction, the database being associated with a plurality of locks;

identifying a logical serialization sequence for executing the first, second, and third transactions, the identifying including;

identifying that the first transaction is to be executed before the second transaction based on all locks, in the plurality of locks, that are required by the first transaction being available,

identifying that the second transaction is to be executed after the first transaction has completed execution based on the second transaction requiring a lock, in the plurality of locks, that is required by the first transaction, and

identifying that the third transaction is to be executed before or during execution of the first transaction based on all locks, in the plurality of locks, required by the third transaction being different than the locks required by the first transaction; and

executing the first, second, and third transactions, based on the identified logical serialization sequence.

7. The computer-readable medium of claim 6, further comprising computer-executable instructions for:

decomposing the first transaction into a first access set that contains a write set or a read set associated with the first transaction;

decomposing the second transaction into a second access set that contains a write set or a read set associated with the second transaction; and

determining that a lock, in the plurality of locks, required by the first access set is also required by the second access set.

8. The computer-readable medium of claim 6, further comprising computer-executable instructions for:

acquiring all of the locks required by the first transaction;

executing the first transaction to completion;

releasing all of the locks required by the first transaction;

acquiring all of the locks required by the second transaction; and

executing the second transaction.

9. The computer-readable medium of claim 6, wherein the lock required by the first transaction and the second transaction is associated with a record in the database.

10. A system comprising:

processing logic for;

acquiring a plurality of transactions for accessing a database, the plurality of transactions including a first transaction, a second transaction, and a third transaction, the first transaction being received before the second transaction and the third transaction being received after the second transaction, the database being associated with a plurality of locks,

identifying a logical serialization sequence for executing the first, second, and third transactions, the identifying including;

identifying that the first transaction is to be executed before the second transaction based on all locks, in the plurality of locks, that are required by the first transaction being available,

identifying that the second transaction is to be executed after the first transaction has completed execution based on the second transaction requiring a lock, in the plurality of locks, that is required by the first transaction, and

identifying that the third transaction is to be executed before or during execution of the first transaction based on all locks, in the plurality of locks, required by the third transaction being different than the locks required by the first transaction, and

executing the first, second, and third transactions, based on the identified logical serialization sequence.

11. The system of claim 10, wherein the processing logic is further for:

executing the first, second, and third transactions based on the schedule.

12. The system of claim 10, wherein the processing logic is further for:

decomposing the first transaction into a first access set that contains a write set or a read set associated with the first transaction;

decomposing the second transaction into a second access set that contains a write set or a read set associated with the second transaction; and

determining that a lock, in the plurality of locks, required by the first access set is also required by the second access set.

13. The system of claim 10, wherein the processing logic is further for:

acquiring all of the locks required by the first transaction;

executing the first transaction to completion;

releasing all of the locks required by the first transaction;

acquiring all of the locks required by the second transaction; and

executing the second transaction.

14. The system of claim 10, wherein the lock required by the first transaction and the second transaction is associated with a record in the database.