Detection
DBMS creates a wait for Graph, where transactions are a node, and there exists a directed edge from i to j, if transaction i is waiting for transaction j.
What to do when deadlock happens, we kill
- By age (newest or oldest timestamp).
- By progress (least/most queries executed).
- By the # of items already locked.
- By the # of transactions needed to rollback with it.
-
of times a transaction has been restarted in the past (to avoid starvation)
Rollback Strategy
- Approach #1: Completely
- Rollback entire txn and tell the application it was aborted.
- Approach #2: Partial (Savepoints)
- DBMS rolls back a portion of a txn (to break deadlock) and then attempts to re-execute the undone queries.
Prevention
- does not require a waits-for graph or detection algorithm.
- 2PL
- Assign priorities based on timestamps: Older timestamp = higher priority
- To guarantee no deadlocks, only one type of direction is allowed when waiting for a lock. When a transaction restarts, the DBMS reuses the same timestamp (to prevent starvation).