A fast algorithm for testing for safety and detecting deadlocks in locked transaction systems

Aho, 1974 Bentley, 1977 Eswaran, 1976, The notions of consistency and predicate locks in a database system, Comm. ACM, 19, 624, 10.1145/360363.360369 H. T. Kung and C. H. Papadimitriou, An optimality theory of database concurrency control, in “Proceeding, 1979 SIGMOD,”, pp. 116–126. Lipski, 1979 W. Masek, J. Comput. System Sci., in press. Papadimitriou, 1979, The serializability of concurrent database updates, J. Assoc. Comput. Mach., 26, 613, 10.1145/322154.322158 Preparata, 1979 Tarjan, 1975, Efficiency of a good but not linear set union algorithm, J. Assoc. Comput. Mach., 215, 10.1145/321879.321884 van Emde Boas, 1975, Preserving order in a forest in less than logarithmic time, 75 van Emde Boas, 1977, Preserving order in a forest in less than logarithmic time and linear space, Inform. Process. Lett., 6, 80, 10.1016/0020-0190(77)90031-X M. Yannakakis, C. H. Papadimitriou, and H. T. Kung, Locking policies: Safety and freedom from deadlock, in “Proceeding, 1979 FOCS Conferences pp. 286–297.