×

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.

MSC:

68P15 Database theory

Keywords:

serializability
PDFBibTeX XMLCite
Full Text: DOI

References:

[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
[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
[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)
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.