Concurrency and Transaction Management

What is Concurrency?

interleaving the execution of operations

needed for performance reasons

What are Schedules?

list of actions formed from a set of transactions

What is a Well-Formed Schedule?

a schedule where the actions of a particular transaction T are in the same order they appear in T

What is a Complete Schedule?

a schedule that contains an abort of commit action for every transaction that occurs in the schedule

What is a Serial Schedule?

a schedule where the actions of different transactions aren’t interleaved

What are Equivalent Schedules?

schedules involving the same set of operations on the same data objects

What are the Conditions for Conflicting Operations?

they belong to different transactions

they operate on the same data item

at least one of them is a write operation

What is ACID?

• atomicity

• consistency

• isolation

• durability

What is Atomicity?

ensures that a transaction either fully completes or doesn’t affect the database at all, even in the event of a failure

What is Consistency?

guarantees that a transaction brings the database from one valid state to another, maintaining defined rules and constraints

What is Isolation?

ensures that transactions are executed independently of each other, so intermediate results aren’t visible to other transactions until the transaction is complete

What is Durability?

guarantees that once a transaction is committed, the changes it made to the database are permanent, even if the system crashes immediately afterward

What is Concurrency Control?

mechanisms to ensure that multiple transactions can execute simultaneously without violating the consistency of the database

What is Locking Protocol?

a mechanism where transactions acquire locks on data objects to control access and prevent conflicting operations from occurring at the same time

What is a Lock (L)?

a variable associated with a data item that restricts access to that item

typically 2 types

What is a Shared Lock (S-Lock)?

allows multiple transactions to read a data item concurrently but prohibits writes

What is an Exclusive Lock (X-Lock)?

allows only one transaction to read and write a data item, blocking others from  accessing it

What is Deadlock?

a situation in which a set of transactions is blocked because each transaction is holding a lock and waiting for a lock held by another transaction in the set

What is Starvation?

a situation where a transaction can’t acquire the necessary locks due to continuous denial, often because other transactions are repeatedly prioritised

What is a Wait-Die Scheme?

deadlock prevention

older transactions wait for younger ones, and younger ones are aborted if they request resources held by older transactions

What is a Wound-Wait Scheme?

deadlock prevention

older transactions ‘wound’ younger transactions by forcing them to release resources, allowing the older transaction to proceed

What is the Two-Phase Locking (2PL) Protocol?

a concurrency control method that ensures serialisability by dividing a transaction’s life into 2 phases

growing - a transaction may acquire locks but can’t release any locks

shrinking - a transaction may release locks but can’t acquire any new locks

What is Strict 2PL?

transactions hold all acquired locks until they complete (commit/abort)

this prevents cascading aborts, as changes made by a transaction are visible only after it commits

What is Timestamp Ordering?

a non-locking concurrency control protocol that assigns timestamps to each transaction and enforces an order based on these timestamps to prevent conflicts

What is Validation-Based/Optimistic Concurrency Control?

where transactions are allowed to execute without locking, but at the commit time, they are validated for potential conflict

What is Serialisability?

the highest isolation level, where transactions are executed in a sequence such that the outcome is equivalent to some serial execution of the transactions

What is a Cascading Abort?

the abort of one transaction causes several other transactions to be aborted, especially when they have read uncommitted data from the aborted transaction

What is a Read-Write Conflict?

one transaction reads a data item and another writes to the same item simultaneously

What is a Write-Write Conflict?

two transactions attempt to write to the same data item simultaneously

What is a Lost Update?

one transaction's update is overwritten by another's update, leading to data inconsistency

What is a Dirty Read?

a transaction reads uncommitted changes made by another transaction, potentially leading to inconsistencies if the latter transaction aborts