Several serializable classes in database concurrency control
Jin Kiniwa, Shojiro Nishio, Toshiharu Hasegawa · Systems and Computers in Japan · 1988
Abstract This paper considers several serializable classes in database concurrencey control, namely: Δ‐, τ‐, and σ‐serializable classes. It is shown that: the DITS in a labeled directed graph (proposed by Ibaraki et al. for testing membership of σ‐serializable class) can be extended to both ϵ‐ and Δ‐serializable classes; several proofs are given that the ϵ‐serializable class is a significant definition of concurrency control, especially in a cautious scheduler model; the computational complexity of testing membership of ϵ‐ and Δ‐serializable classes is analyzed; and the inclusion relationship of the preceding three serializable classes under restricted numbers of versions for several types of transaction models is investigated.