Transactions

Wikipedia · Database transaction · CC BY-SA 4.0

A transaction is a sequence of operations that either all succeed (commit) or all fail (rollback). The ACID properties guarantee correctness: Atomicity (all or nothing), Consistency (valid state to valid state), Isolation (concurrent transactions do not interfere), Durability (committed data survives crashes).

ACID properties

Atomicity: a transaction is indivisible. If any operation fails, all are undone. Consistency: the database moves from one valid state to another. Isolation: concurrent transactions behave as if they ran serially. Durability: once committed, the data persists even through power failures.

Scheme

; Simulating atomicity: transfer money between accounts.
; If the debit succeeds but the credit fails, rollback both.

(define accounts (list (cons "Alice" 100) (cons "Bob" 50)))

(define (get-balance accts name)
  (cdr (assoc name accts)))

(define (update-balance accts name delta)
  (map (lambda (a)
    (if (string=? (car a) name)
      (cons name (+ (cdr a) delta))
      a))
    accts))

(define (transfer accts from to amount)
  (let ((from-bal (get-balance accts from)))
    (if (< from-bal amount)
      (begin (display "ROLLBACK: insufficient funds") (newline) accts)
      (let* ((step1 (update-balance accts from (- amount)))
             (step2 (update-balance step1 to amount)))
        (display "COMMIT: transfer complete") (newline)
        step2))))

(display "Before: ") (display accounts) (newline)
(define after (transfer accounts "Alice" "Bob" 30))
(display "After:  ") (display after) (newline)
(newline)
; Try overdraft
(transfer after "Bob" "Alice" 200)

Serializability and conflict graphs

A schedule is serializable if its result equals some serial execution of the same transactions. To test: build a conflict graph (precedence graph). Add an edge T1 -> T2 whenever T1 and T2 access the same item and at least one writes, and T1 goes first. If the graph has no cycle, the schedule is conflict-serializable.

Scheme

; Conflict serializability check.
; Schedule: T1:R(A), T2:R(A), T1:W(A), T2:W(A)
; Conflicts: T1:R(A) vs T2:W(A) => T1->T2
;            T2:R(A) vs T1:W(A) => T2->T1
; Cycle! Not serializable.

(define schedule
  (list
    (list "T1" "R" "A")
    (list "T2" "R" "A")
    (list "T1" "W" "A")
    (list "T2" "W" "A")))

(define (conflicts? op1 op2)
  (and (not (string=? (car op1) (car op2)))         ; different transactions
       (string=? (caddr op1) (caddr op2))           ; same data item
       (or (string=? (cadr op1) "W")
           (string=? (cadr op2) "W"))))              ; at least one write

; Build edges
(define (find-edges schedule)
  (let loop ((ops schedule) (edges (list)))
    (if (null? ops) edges
      (let inner ((rest (cdr ops)) (e edges))
        (if (null? rest) (loop (cdr ops) e)
          (if (conflicts? (car ops) (car rest))
            (let ((edge (cons (caar ops) (caar rest))))
              (if (member edge e)
                (inner (cdr rest) e)
                (inner (cdr rest) (cons edge e))))
            (inner (cdr rest) e)))))))

(define edges (find-edges schedule))
(display "Conflict edges: ") (display edges) (newline)

; Check for cycle: if T1->T2 and T2->T1, cycle exists
(define (has-cycle? edges)
  (let loop ((es edges))
    (if (null? es) #f
      (let ((rev (cons (cdar es) (caar es))))
        (if (member rev edges) #t
          (loop (cdr es)))))))

(display "Has cycle (not serializable)? ")
(display (has-cycle? edges))

; Conflict serializability check.
; Schedule: T1:R(A), T2:R(A), T1:W(A), T2:W(A)
; Conflicts: T1:R(A) vs T2:W(A) => T1->T2
;            T2:R(A) vs T1:W(A) => T2->T1
; Cycle! Not serializable.

(define schedule
  (list
    (list "T1" "R" "A")
    (list "T2" "R" "A")
    (list "T1" "W" "A")
    (list "T2" "W" "A")))

(define (conflicts? op1 op2)
  (and (not (string=? (car op1) (car op2)))         ; different transactions
       (string=? (caddr op1) (caddr op2))           ; same data item
       (or (string=? (cadr op1) "W")
           (string=? (cadr op2) "W"))))              ; at least one write

; Build edges
(define (find-edges schedule)
  (let loop ((ops schedule) (edges (list)))
    (if (null? ops) edges
      (let inner ((rest (cdr ops)) (e edges))
        (if (null? rest) (loop (cdr ops) e)
          (if (conflicts? (car ops) (car rest))
            (let ((edge (cons (caar ops) (caar rest))))
              (if (member edge e)
                (inner (cdr rest) e)
                (inner (cdr rest) (cons edge e))))
            (inner (cdr rest) e)))))))

(define edges (find-edges schedule))
(display "Conflict edges: ") (display edges) (newline)

; Check for cycle: if T1->T2 and T2->T1, cycle exists
(define (has-cycle? edges)
  (let loop ((es edges))
    (if (null? es) #f
      (let ((rev (cons (cdar es) (caar es))))
        (if (member rev edges) #t
          (loop (cdr es)))))))

(display "Has cycle (not serializable)? ")
(display (has-cycle? edges))

Python

# Transaction simulation with sqlite3
import sqlite3

conn = sqlite3.connect(":memory:")
c = conn.cursor()
c.execute("CREATE TABLE accounts (name TEXT PRIMARY KEY, balance REAL)")
c.execute("INSERT INTO accounts VALUES ('Alice', 100)")
c.execute("INSERT INTO accounts VALUES ('Bob', 50)")
conn.commit()

def transfer(conn, src, dst, amount):
    c = conn.cursor()
    try:
        c.execute("SELECT balance FROM accounts WHERE name=?", (src,))
        bal = c.fetchone()[0]
        if bal < amount:
            raise ValueError("Insufficient funds")
        c.execute("UPDATE accounts SET balance = balance - ? WHERE name=?", (amount, src))
        c.execute("UPDATE accounts SET balance = balance + ? WHERE name=?", (amount, dst))
        conn.commit()
        print("COMMIT: " + src + " -> " + dst + ": $" + str(amount))
    except Exception as e:
        conn.rollback()
        print("ROLLBACK: " + str(e))

transfer(conn, "Alice", "Bob", 30)
for row in conn.execute("SELECT * FROM accounts"):
    print("  " + str(row[0]) + ": $" + str(row[1]))

print()
transfer(conn, "Bob", "Alice", 200)  # should rollback

# Transaction simulation with sqlite3
import sqlite3

conn = sqlite3.connect(":memory:")
c = conn.cursor()
c.execute("CREATE TABLE accounts (name TEXT PRIMARY KEY, balance REAL)")
c.execute("INSERT INTO accounts VALUES ('Alice', 100)")
c.execute("INSERT INTO accounts VALUES ('Bob', 50)")
conn.commit()

def transfer(conn, src, dst, amount):
    c = conn.cursor()
    try:
        c.execute("SELECT balance FROM accounts WHERE name=?", (src,))
        bal = c.fetchone()[0]
        if bal < amount:
            raise ValueError("Insufficient funds")
        c.execute("UPDATE accounts SET balance = balance - ? WHERE name=?", (amount, src))
        c.execute("UPDATE accounts SET balance = balance + ? WHERE name=?", (amount, dst))
        conn.commit()
        print("COMMIT: " + src + " -> " + dst + ": $" + str(amount))
    except Exception as e:
        conn.rollback()
        print("ROLLBACK: " + str(e))

transfer(conn, "Alice", "Bob", 30)
for row in conn.execute("SELECT * FROM accounts"):
    print("  " + str(row[0]) + ": $" + str(row[1]))

print()
transfer(conn, "Bob", "Alice", 200)  # should rollback

Neighbors

Cross-references

🖥 OS Ch.4 — synchronization: transactions are the database equivalent of critical sections and mutual exclusion

Foundations (Wikipedia)

← Indexing by june.kim Concurrency Control →