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

  1. By age (newest or oldest timestamp).
  2. By progress (least/most queries executed).
  3. By the # of items already locked.
  4. By the # of transactions needed to rollback with it.
  5. 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.


  • 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).