Transactions, Locking, and Concurrency Flashcards
1
Q
Transactions
A
- A sequence of operations that is treated as a single logical operation
- All-or-nothing
2
Q
ACID Properties
A
- 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
3
Q
Serializability
A
- A serializable schedule is one whose effects are equivalent to the effects of some serial schedule
4
Q
Schedule Conflict
A
- 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
5
Q
Conflict Serializability
A
- A schedule is conflict serializable if we can turn it into a serial schedule by swapping pairs of consecutive actions that don’t conflict
6
Q
Precedence Graph
A
- Nodes are the transactions
- Edges are the precedence constraints
- If the graph is acyclic, the schedule is conflict serializable
7
Q
Conflict Serializability vs Serializability
A
- All conflict serializable schedules are serializable
- Not all serializable schedules are conflict serializable
8
Q
Recoverability
A
- In a recoverable schedule, if T1 reads a value written by T2, T1 must commit after T2 commits
9
Q
Dirty Read
A
- A read of uncommitted data
10
Q
Cascading Rollback
A
- The rollback of a single transaction leads to other rollbacks
- Can be caused by dirty reads
11
Q
Two-Phase Locking (2PL)
A
- All of a transaction’s lock actions must come before all of its unlock actions
- Guarantees serializability, but not recoverability or cascadelessness
12
Q
Exclusive Lock
A
- Allows a transaction to read or write an item
- Only one transaction can hold it at a given time
13
Q
Shared Lock
A
- Only allows a transaction to read an item
- Multiple transactions can hold it at a given time
14
Q
Lock Compatibility Matrix
A
- A lock request for a currently locked item can only be granted when both the existing and requested locks are shared locks
15
Q
Strict Locking
A
- Makes transactions hold all exclusive locks until they commit or abort
- Prevents dirty reads, ensuring recoverability and cascadelessness
- Can lead to deadlock
16
Q
Lock Upgrade
A
- 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
17
Q
Update Locks
A
- 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
18
Q
Handling Deadlock
A
- Can use a waits-for graph to identify deadlock
- Rolls back one of the deadlocked transactions
19
Q
Timestamp-Based Concurrency
A
- If TS(T1) < TS(T2), only allow actions consistent with the serial schedule T1; T2
20
Q
RTS(A)
A
- The largest timestamp of any transaction that has read A
21
Q
WTS(A)
A
- The largest timestamp of any transaction that has written A
22
Q
Timestamp Rules for Reads
A
- If TS(T) < WTS(A), don’t allow the read
- Else allow the write
23
Q
Timestamp Rules for Writes
A
- 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
24
Q
Multiversion Timestamp Protocol
A
- Keep old versions of data elements to reduce rollbacks
- Never roll back a read-only transaction
25
Q
Combining Locking and Multiversion Timestamps
A
- Transactions with writes use 2PL
- Transactions with only reads use timestamps
