Transactions, Locking, and Concurrency

Question 1

Transactions

Answer 1

• A sequence of operations that is treated as a single logical operation
• All-or-nothing

Question 2

ACID Properties

Answer 2

• Atomicity: all-or-nothing
• Consistency: operations take the database from one consistent state to another
• Isolation: not affected by and does not affect concurrent transactions
• Durability: commits survive failures

Question 3

Serializability

Answer 3

• A serializable schedule is one whose effects are equivalent to the effects of some serial schedule

Question 4

Schedule Conflict

Answer 4

• A pair of actions that can’t be swapped without potentially changing the behavior of one or more transactions
• Actions in different transactions conflict if they involve the same data item and at least one of them is a write

Question 5

Conflict Serializability

Answer 5

• A schedule is conflict serializable if we can turn it into a serial schedule by swapping pairs of consecutive actions that don’t conflict

Question 6

Precedence Graph

Answer 6

• Nodes are the transactions
• Edges are the precedence constraints
• If the graph is acyclic, the schedule is conflict serializable

Question 7

Conflict Serializability vs Serializability

Answer 7

• All conflict serializable schedules are serializable
• Not all serializable schedules are conflict serializable

Question 8

Recoverability

Answer 8

• In a recoverable schedule, if T1 reads a value written by T2, T1 must commit after T2 commits

Question 9

Dirty Read

Answer 9

• A read of uncommitted data

Question 10

Cascading Rollback

Answer 10

• The rollback of a single transaction leads to other rollbacks
• Can be caused by dirty reads

Question 11

Two-Phase Locking (2PL)

Answer 11

• All of a transaction’s lock actions must come before all of its unlock actions
• Guarantees serializability, but not recoverability or cascadelessness

Question 12

Exclusive Lock

Answer 12

• Allows a transaction to read or write an item
• Only one transaction can hold it at a given time

Question 13

Shared Lock

Answer 13

• Only allows a transaction to read an item
• Multiple transactions can hold it at a given time

Question 14

Lock Compatibility Matrix

Answer 14

• A lock request for a currently locked item can only be granted when both the existing and requested locks are shared locks

Question 15

Strict Locking

Answer 15

• Makes transactions hold all exclusive locks until they commit or abort
• Prevents dirty reads, ensuring recoverability and cascadelessness
• Can lead to deadlock

Question 16

Lock Upgrade

Answer 16

• Acquire a shared lock to read an item, but upgrade to an exclusive lock when you need to write
• May need to wait if others hold shared locks
• Can lead to deadlock

Question 17

Update Locks

Answer 17

• Allows a transaction to read an item and can be upgraded to an exclusive lock
• Only one transaction can hold an update lock for a given item

Question 18

Handling Deadlock

Answer 18

• Can use a waits-for graph to identify deadlock
• Rolls back one of the deadlocked transactions

Question 19

Timestamp-Based Concurrency

Answer 19

• If TS(T1) < TS(T2), only allow actions consistent with the serial schedule T1; T2

Question 20

RTS(A)

Answer 20

• The largest timestamp of any transaction that has read A

Question 21

WTS(A)

Answer 21

• The largest timestamp of any transaction that has written A

Question 22

Timestamp Rules for Reads

Answer 22

• If TS(T) < WTS(A), don’t allow the read
• Else allow the write

Question 23

Timestamp Rules for Writes

Answer 23

• If TS(T) < RTS(A), roll back T and restart it
• Else if TS(T) < WTS(A), ignore the write and continue (Thomas Write Rule)
• Else allow the write

Question 24

Multiversion Timestamp Protocol

Answer 24

• Keep old versions of data elements to reduce rollbacks
• Never roll back a read-only transaction

Question 25

Combining Locking and Multiversion Timestamps

Answer 25

• Transactions with writes use 2PL
• Transactions with only reads use timestamps