txn-serializability-validator

Answer

The implementation is a complete conflict-serializability checker for concurrent database transaction schedules. It uses the standard serialization graph (precedence graph) approach:

Algorithm: 1. Graph construction — Process the operation stream left-to-right. For each operation, track lastRead and lastWrite per data item. When a transaction T₂ reads an item last written by T₁, add edge T₁ → T₂ (WR conflict). When T₂ writes an item last read or written by T₁, add edges T₁ → T₂ (RW and WW conflicts). Self-loops (same transaction) are ignored.

1. Cycle detection — Run DFS with three-colour marking (WHITE/GRAY/BLACK) on the graph. When a GRAY→GRAY back edge is found, reconstruct the cycle by walking parent pointers from the descendant back to the ancestor, then reverse the path for a natural ordering.

Key implementation:

// serializability.go — core logic
func CheckSchedule(ops []Operation) (bool, []int) {
    // Build precedence graph from RW, WR, WW conflicts
    for _, op := range ops {
        switch op.Type {
        case "R":
            if w, ok := lastWrite[op.Item]; ok { addEdge(w, op.TxnID) }
            lastRead[op.Item] = op.TxnID
        case "W":
            if r, ok := lastRead[op.Item]; ok  { addEdge(r, op.TxnID) }
            if w, ok := lastWrite[op.Item]; ok { addEdge(w, op.TxnID) }
            lastWrite[op.Item] = op.TxnID
        }
    }
    // Detect cycle via DFS
    cycle := findCycle(graph, vertices)
    return cycle == nil, cycle
}