Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Transaction Management

Field: Databases

The process of managing database transactions.

Sequence of Expressions

Definition

Serialization

Let T=⟨T1,…,Tn⟩\mathcal{T} = \langle \mathcal{T}_1, \dots, \mathcal{T}_n \rangle be a set of transactions. The execution Conf(T)\text{Conf}(\mathcal{T}) is said to be serializable if there exists a permutation π\pi of T\mathcal{T} such that the outcome state Sfinal\mathbf{S}_{final} resulting from Conf(T)\text{Conf}(\mathcal{T}) is identical to the outcome state resulting from the serial execution Ser(π)\text{Ser}(\pi): \n\nSfinal(Conf(T))=Sfinal(Ser(π))\mathbf{S}_{final}(\text{Conf}(\mathcal{T})) = \mathbf{S}_{final}(\text{Ser}(\pi)) \n\nThis condition is equivalent to the existence of a conflict graph GcG_c where all edges are directed and acyclic (i.e., the graph is a Directed Acyclic Graph, DAG).
Let T1\mathcal{T}_1 and T2\mathcal{T}_2 be concurrent transactions. Isolation levels define the permissible visibility of intermediate states. \n\n1. **Read Uncommitted:** T1\mathcal{T}_1 may read uncommitted writes from T2\mathcal{T}_2 (Dirty Reads allowed).\n2. **Read Committed:** T1\mathcal{T}_1 only reads values committed by T2\mathcal{T}_2. Read(T1,X)  ⟹  X committed before Read(T1,X)\text{Read}(\mathcal{T}_1, X) \implies X \text{ committed before } \text{Read}(\mathcal{T}_1, X).\n3. **Repeatable Read:** T1\mathcal{T}_1 reads the same committed value of XX throughout its execution, preventing Non-Repeatable Reads. Read(T1,X) at time t1=Read(T1,X) at time t2\text{Read}(\mathcal{T}_1, X) \text{ at time } t_1 = \text{Read}(\mathcal{T}_1, X) \text{ at time } t_2.\n4. **Serializable:** T1\mathcal{T}_1 must behave as if it executed entirely before or entirely after T2\mathcal{T}_2, preventing Phantom Reads and all other anomalies.
Let DD be the database state and TstartT_{start} be the timestamp defining the snapshot. Define the read operation Read(d,Tstart)\text{Read}(d, T_{start}) such that it retrieves the version of data item dd whose commit timestamp TScommit(d)\text{TS}_{\text{commit}}(d) satisfies TScommit(d)≤Tstart\text{TS}_{\text{commit}}(d) \le T_{start} and TScommit(d)\text{TS}_{\text{commit}}(d) is maximized. This ensures that all reads within the transaction view are consistent with the state at TstartT_{start}, effectively isolating the transaction from concurrent writes that commit after TstartT_{start}.
Let SS be the persistent storage medium and C\mathcal{C} be the commit operation for a transaction TT. Durability requires that if C\mathcal{C} returns success, the resulting state DcommitD_{commit} must be permanently recorded in SS, even if a subsequent failure F\mathcal{F} occurs. Formally, let WriteLog(Lcommit)\text{WriteLog}(L_{commit}) be the operation of flushing the commit log records LcommitL_{commit} to SS. Durability mandates that the state DcommitD_{commit} must be recoverable from SS after F\mathcal{F}, such that Dcommit=Restore(S,Lcommit)D_{commit} = \text{Restore}(S, L_{commit}). This is typically achieved by forcing the log records to stable storage before acknowledging the commit.
Let C={Coordinator,Participant1,…,Participantk}\mathcal{C} = \{\text{Coordinator}, \text{Participant}_1, \dots, \text{Participant}_k\} be the set of nodes. The Two-Phase Commit protocol proceeds through two phases:\n\n**Phase 1: Prepare (Voting)**\n1. Coordinator→PREPAREParticipanti\text{Coordinator} \xrightarrow{\text{PREPARE}} \text{Participant}_i. \n2. Participanti\text{Participant}_i writes all necessary changes to stable storage (undo/redo logs) and replies VOTEYES\text{VOTE}_{YES} if successful, or VOTENO\text{VOTE}_{NO} otherwise.\n\n**Phase 2: Commit/Abort (Decision)**\n1. If Coordinator\text{Coordinator} receives VOTEYES\text{VOTE}_{YES} from all Participanti\text{Participant}_i: Coordinator→COMMITParticipanti\text{Coordinator} \xrightarrow{\text{COMMIT}} \text{Participant}_i. Participanti\text{Participant}_i makes changes permanent.\n2. Otherwise: Coordinator→ABORTParticipanti\text{Coordinator} \xrightarrow{\text{ABORT}} \text{Participant}_i. Participanti\text{Participant}_i rolls back changes.
Let G=(V,E)G = (V, E) be a Resource Allocation Graph, where VV is the set of transactions T={t1,t2,…,tn}T = \{t_1, t_2, \dots, t_n\} and EE represents resource dependencies. Define EE such that an edge (ti,tj)(t_i, t_j) exists if transaction tit_i is waiting for a resource currently held by tjt_j. A deadlock D\mathcal{D} occurs if and only if the graph GG contains a cycle: ∃ cycle C=(ti1→ti2→⋯→tik→ti1) in G.\exists \text{ cycle } C = (t_{i_1} \to t_{i_2} \to \dots \to t_{i_k} \to t_{i_1}) \text{ in } G. The detection algorithm must identify such cycles by traversing the dependency graph.
Define the Transaction Log LL as a sequence of log records ⟨L1,L2,…,Lm⟩\langle L_1, L_2, \dots, L_m \rangle. Each record LkL_k is a tuple ⟨TID,Type,Data,OldValue,NewValue⟩\langle \text{TID}, \text{Type}, \text{Data}, \text{OldValue}, \text{NewValue} \rangle, where TID\text{TID} is the transaction ID, Type∈{<BEGIN>,<COMMIT>,<ABORT>,<UPDATE>}\text{Type} \in \{\text{<BEGIN>}, \text{<COMMIT>}, \text{<ABORT>}, \text{<UPDATE>}\}, Data\text{Data} is the identifier of the modified data item, and OldValue\text{OldValue} and NewValue\text{NewValue} are the values before and after the modification, respectively. The log must maintain the strict temporal ordering of all state changes.
Let T\mathcal{T} be a transaction, Sk\mathbf{S}_{k} be the database state before T\mathcal{T}, and Sk+1\mathbf{S}_{k+1} be the state after T\mathcal{T}. The ACID properties require the following conditions:\n\n1. **Atomicity:** Commit(T)  ⟹  Sk+1=Sk after T executes fully\text{Commit}(\mathcal{T}) \implies \mathbf{S}_{k+1} = \mathbf{S}_{k} \text{ after } \mathcal{T} \text{ executes fully}. Abort(T)  ⟹  Sk+1=Sk\text{Abort}(\mathcal{T}) \implies \mathbf{S}_{k+1} = \mathbf{S}_{k}.\n2. **Consistency:** Sk+1⊨I\mathbf{S}_{k+1} \models I, where II is the set of all database invariants (constraints) that must hold true for any valid state.\n3. **Isolation:** For any set of concurrent transactions T={T1,…,Tn}\mathcal{T} = \{\mathcal{T}_1, \dots, \mathcal{T}_n\}, the resulting state Sk+1\mathbf{S}_{k+1} must be indistinguishable from the state resulting from some serial execution Sk+1=Sk after Ser(T)\mathbf{S}_{k+1} = \mathbf{S}_{k} \text{ after } \text{Ser}(\mathcal{T}).\n4. **Durability:** If Commit(T)\text{Commit}(\mathcal{T}) occurs, the changes ΔS\Delta \mathbf{S} are permanently recorded in stable storage, such that subsequent system failures do not revert Sk+1\mathbf{S}_{k+1} to Sk\mathbf{S}_{k}.
Let T1,T2\mathcal{T}_1, \mathcal{T}_2 be two concurrent transactions operating on a data item XX. Define the conflict set C(X)={(Read(X),Write(X)),(Write(X),Read(X)),(Write(X),Write(X))}C(X) = \{(\text{Read}(X), \text{Write}(X)), (\text{Write}(X), \text{Read}(X)), (\text{Write}(X), \text{Write}(X))\}. A concurrency control mechanism M\mathcal{M} must ensure that for every pair of conflicting operations o1∈Op(T1)o_1 \in \text{Op}(\mathcal{T}_1) and o2∈Op(T2)o_2 \in \text{Op}(\mathcal{T}_2), the mechanism enforces a total ordering ≺\prec such that the execution sequence respects the defined conflict resolution rules (e.g., two-phase locking: Lock(X)\text{Lock}(X) must be acquired before Read(X)\text{Read}(X) or Write(X)\text{Write}(X)).
Let DD be the initial database state and LL be the transaction log. The Recovery Manager R\mathcal{R} defines a state transition function R:(D,L)→D′\mathcal{R}: (D, L) \to D' such that D′D' is the consistent state. The recovery process involves two phases: Redo and Undo. For any operation ⟨TID,<UPDATE>,d,Old,New⟩∈L\langle \text{TID}, \text{<UPDATE>}, d, \text{Old}, \text{New} \rangle \in L, the Redo operation Redo(d,New)\text{Redo}(d, \text{New}) applies New\text{New} to dd if the transaction TID\text{TID} committed, and the Undo operation Undo(d,Old)\text{Undo}(d, \text{Old}) reverts dd to Old\text{Old} if the transaction TID\text{TID} aborted or failed before committing. The final state D′D' must satisfy the ACID properties based on the surviving committed transactions.