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

Serialization

The ordering of operations in a database to ensure that concurrent transactions appear to execute serially.
📜

The statement of the theorem

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