Affiliations: Department of Computer Science, Memorial University of Newfoundland, St. John’s, Newfoundland, Canada A1C 5S7
Note: [1] This research is supported in part by the Natural Sciences and Engineering Research Council of Canada Individual Operating Grant A-3182.
Note: [2] Some results of this paper have appeared in two conference papers: (i) the results in sections 3–5 in [K. Vidyasankar, A Simple Characterization of Database Serializability, Proc. 5th Conj. on Foundations of Software Technology and Theoretical Computer Science, India, December 1985, Lecture Notes in Computer Science 206, Springer-Verlag, pp. 329–345] and (ii) those in sections 6–8 and part of section 9 (upto Theorem 9.1) in [K. Vidyasankar, Serializable Graphs, Proc. 14th International Workshop on Graph-Theoretic Concepts in Computer Science (WG’88), Amsterdam, June 1988, Lecture Notes in Computer Science 344, Springer-Verlag, pp. 107–121].
Abstract: A database system is a collection of data items, read or written by transactions in a possibly interleaved fashion. An interleaved execution is assumed to be correct if the sequence of the steps of the transactions, called history, is serializable, that is, the effect of the execution is equivalent to that of some serial execution of the same transactions. In this paper we give a new characterization of serializability that brings out the inherent problem of serialization explicitly. We then give a graph-theoretic analogue of serializable histories. We define a new class of graphs, called serializable graphs, whose properties are such that (i) a serializable graph can be associated with each serializable history, and this can be done for various notions of serializability of histories and for serializability under various sets of constraints, and (ii) a serializable history, in fact a serial one, can be associated with each serializable graph. We use serializable graphs to characterize, in an intuitive manner, serializable histories involving general multi-step transactions, where the same data item can be accessed by several read and write steps of a transaction in an arbitrary manner, and those involving nested transactions. We also define a new notion of serializability for nested transactions. This enables relating several acceptable concurrent executions of transactions, that are not serializable with the traditional transaction concept, to sequential behaviour. Serializability under this notion is also characterized. The main graph-theoretic properties used in these characterizations are a directed cutset matching property and graph contraction.
