zbMATH — the first resource for mathematics

Relative serializability: An approach for relaxing the atomicity of transactions. (English) Zbl 0887.68026
Summary: Serializability is too strong a correctness criterion and unnecessarily restricts concurrency. We use the semantic information of a transaction to provide different atomicity views of the transaction to other transactions. The proposed approach improves concurrency and allows interleavings among transactions which are nonserializable, but which nonetheless preserve the consistency of the database and are acceptable to the users. We develop a graph-based tool whose acyclicity is both a necessary and sufficient condition for the correctness of an execution. Our theory encompasses earlier proposals that incorporate semantic information of transactions. Furthermore, it is the first approach that provides an efficient graph-based tool for recognizing correct schedules without imposing any restrictions on the application domain. Our approach is widely applicable to many advanced database applications such as systems with long-lived transactions and collaborative environments.
68P15 Database theory
Full Text: DOI
[1] D. Agrawal, J. L. Bruno, A. El Abbadi, V. Krishnaswamy, Managing concurrent activities in collaborative environments, Proceedings, Cooperative Information Systems (CoopIS’95), May 1995, 112, 124
[2] Barghouti, N. S.; Kaiser, G. E., Concurrency control in advanced database applications, ACM Comput. Surveys, 23, 269-318, (1991)
[3] Bernstein, A. J.; Lewis, P. M., Technical Report TRCS 93-05, (1993)
[4] Badrinath, B. R.; Ramamritham, K., Semantics-based concurrency control: beyond computativity, ACM Trans. Database Systems, 17, 163-199, (1992)
[5] Bernstein, P. A.; Shipman, D. W.; Wong, W. S., Formal aspects of serializability in database concurrency control, IEEE Transactions on Software Engineering, 5, 203-216, (1979) · Zbl 0396.68020
[6] Eswaran, K. P.; Gray, J. N.; Lorie, R. A.; Traiger, I. L., The notions of consistency and predicate locks in a database system, Comm. ACM, 19, 624-633, (1976) · Zbl 0341.68023
[7] Farrag, A. A.; Özsu, M. T., Using semantic knowledge of transactions to increase concurrency, ACM Transactions on Database Systems, 14, 503-525, (1989)
[8] Garcia-Molina, H., Using semantic knowledge for transaction processing in a distributed database, ACM Transactions on Database Systems, 8, 186-213, (1983) · Zbl 0509.68111
[9] Herlihy, M., A quorum-consensus replication method for abstract data types, ACM Transactions on Computer Systems, 4, 32-53, (1986)
[10] Krishnaswamy, V.; Bruno, J., Technical Report, TRCS 92-21, (1992)
[11] Korth, H. F., Locking primitives in a database system, J. Assoc. Comput. Mach., 30, 55-79, (1983) · Zbl 0498.68060
[12] V. Krishnaswamy, 1993, Semantics BAsed Synchronization in Database Systems, Department of Computer Science, University of California, Santa Barbara
[13] Lynch, N. A., Multilevel atomicity—A new correctness criterion for database concurrency control, ACM Transactions on Database Systems, 8, 485-502, (1983) · Zbl 0548.68094
[14] Papadimitriou, C. H., The serializability of concurrent database updates, Journal of the ACM, 26, 631-653, (1979) · Zbl 0419.68036
[15] C. H. Papadimitriou, 1986, The Theory of Database Concurrency Control, Computer Sci. Press, New York · Zbl 0609.68073
[16] Rosenkrantz, D. J.; Stearns, R. E.; lewis, P. M., System level concurrency control for distributed database systems, ACM Transactions on Database Systems, 3, 178-198, (1978)
[17] Salem, K. M.; Garcia-Molina, H.; Alonso, R., Altruistic locking: A strategy for coping with long-lived transactions, Lect. Notes in Comput. Sci., 352, 175-199, (1987)
[18] Schwarz, P. M.; Spector, A. Z., Synchronizing shared abstract types, ACM Transactions on Computer Systems, 2, 223-250, (1984)
[19] D. Shasha, E. Simon, P. Valduriez, Simple rational guidance for chopping up transactions, Proceedings of the 1992 ACM SIGMOD International Conference on management of Data, June 1992, 298, 307
[20] Weihl, W. E., Local atomicity properties: modular concurrency control for abstract data types, ACM Transactions on Programming languages and Systems, 11, 249-283, (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.