zbMATH — the first resource for mathematics

On the complexity of concurrency control using semantic information. (English) Zbl 0826.68039
Summary: In the presence of semantic information, serializability is too strong a correctness criterion and unnecessarily restricts concurrency. Many researchers have investigated the use of semantic information to allow interleaving among transactions which are non-serializable, but which nonetheless preserves the consistency of the database and is acceptable to the users. In this paper we consider a class of schedules, called conflict-correct schedules, first proposed by Farrag and Özsu, which enlarges upon the class of serializable schedules by taking semantic information of transaction into account. In this paper we show that the problem of recognizing schedules in this class is NP-complete. Thus it is unlikely that there exists an efficient scheduler which accepts the entire class of conflict-correct schedules.
68P15 Database theory
68Q55 Semantics in the theory of computing
Full Text: DOI
[1] Badrinath, B.R., Ramamritham, K.: Semantics-based concurrency control: beyond commutativity. ACM Trans. Database Syst.17 (1) 163-199 (1992) · doi:10.1145/128765.128771
[2] Berstein, P.A., Shipman, D.W. and Wong, W.S.: Formal aspects of serializability in database concurrency control. IEEE Trans. Software Eng.5 (5) 203-216 (1979) · Zbl 05341419 · doi:10.1109/TSE.1979.234182
[3] Casanova, M.A., Bernstein, P.A.: General purpose schedulers for database systems. Acta Inf.4 185-221 (1980) · Zbl 0419.68080
[4] Eswaran, K.P., Gray, J.N., Lorie, R.A., Traiger, I.L.: The notions of consistency and predicate locks in database systems. Commun. ACM19 (11) 624-633 (1976) · Zbl 0341.68023 · doi:10.1145/360363.360369
[5] Farrag, A.A., Özsu, M.T.: Using semantic knowledge of transactions to increase concurrency. ACM Trans. Database Syst.14 (4) 503-525 (1989) · doi:10.1145/76902.76905
[6] Fischer, J.M., Griffeth, N.D., Lynch, N.A.: Global states of a distributed system. IEEE Trans. Software Eng. SE-8 (3) 198-202 (1982) · Zbl 05341448 · doi:10.1109/TSE.1982.235418
[7] Garcia Molina, H.: Using semantic knowledge for transaction processing in a distributed database. ACM Trans. Database Syst.8 (2) 186-213 (1983) · Zbl 0509.68111 · doi:10.1145/319983.319985
[8] Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completeness. New York: S.H. Freeman 1979 · Zbl 0411.68039
[9] Gray, J.N.: The transaction concept: Virtues and limitations. In: Proceedings of the 7th International Conference on Very Large Data Bases, pp. 144-154, September 1981
[10] Kung, H.T., Papadimitriou, C.H.: An optimality theory of concurrency control for databases. In: Proceedings ACM-SIGMOD International Conference on Management of Data, Boston, MA, May 30?June 1, ACM, New York, pp. 116-126, 1979
[11] Lynch, N.A.: Multilevel atomicity?a new correctness criterion for database concurrency control. ACM Trans. Database Syst.8 (4) 484-502 (1983) · Zbl 0548.68094 · doi:10.1145/319996.319999
[12] Papadimitriou, C.H.: The theory of database concurrency control. New York: Computer Science Press 1986 · Zbl 0609.68073
[13] Papadimitriou, C.H.: The serializability of concurrent database updates. J. ACM26 (4) 631-653 (1979) · Zbl 0419.68036 · doi:10.1145/322154.322158
[14] Rosenkrantz, D.J., Stearns, R.E., Lewis, P.M.: System level concurrency control for distributed database systems. ACM Trans. Database Syst.3 (2) 178-198 (1978) · doi:10.1145/320251.320260
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.