On the serializability theorem for nested transactions. (English) Zbl 0807.68026

Resende, R. F.; El Abbadi, A.

Inf. Process. Lett. 50, No. 4, 177-183 (1994).

Summary: The fundamental theorem of the classical serializability theory states the necessary and sufficient conditions for the conflict serializability of an execution. In this paper, we extend the correctness criteria of the classical theory by presenting a definition of conflict serializability for concurrency control of nested transactions. We define a serialization graph for nested transactions and we prove that its acyclicity is a sufficient and necessary condition for conflict serializability.

MSC:

68P15	Database theory
68Q10	Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)

Keywords:

serializability theory; serialization graph; nested transactions

References:

[1]	Beeri, C.; Bernstein, P.A.; Goodman, N., A model for concurrency in nested transactions systems, J. ACM, 36, 2, 230-269, (1989) · Zbl 0678.68105
[2]	Bernstein, P.A.; Hadzilacos, V.; Goodman, N., Concurrency control and recovery in database systems, (1987), Addison-Wesley Reading, MA
[3]	Hadzilacos, T.; Hadzilacos, V., Transaction synchronization in object bases, J. comput. system sci., 43, 1, 2-24, (1991) · Zbl 0766.68029
[4]	Fekete, A.; Lynch, N.; Weihl, W., A serialization graph construction for nested transactions, (), 94-108
[5]	Moss, J.E.B., Nested transactions: an approach to reliable distributed computing, Ph.D. thesis, (1981), Tech. Rept. MIT/LCS/TR-260
[6]	Papadimitriou, C.H., The theory of database concurrency control, (1986), Computer Science Press Rockville, MD · Zbl 0609.68073
[7]	Resende, R.F.; El Abbadi, A., A graph testing concurrency control protocol for object bases, (), 316-317