Skip to main content
SpringerLink
Log in

Static and dynamic aspects of goal-oriented concurrency control

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

A new correctness criterion for schedules of update transactions is proposed, which captures users' intended changes to the database. This is motivated by the observation that traditional serializability may lead to anomalies by not taking into account semantics related to such intended changes. The alternate criterion —goal-correctness — is orthogonal to serializability, and is based on realizing goals associated with each transaction. The problems involved in goal-oriented concurrency control are first identified in a general framework. The analysis suggests that this approach is practical only for restricted transaction languages where goals can be inferred and manipulated efficiently. One such language is then considered, capturing a class of updates of practical interest. For this language, it is shown that goal-oriented concurrency control is tractable and compares favorably to serializability with respect to complexity: testing goal-correctness takes polynomial time, while testing serializability is NP-complete. The set of schedules which are correct with respect to the two criteria are incomparable. Thus, goal-correctness may allow increased concurrency. The results highlight the feasibility and advantages of goal-oriented concurrency control in restricted frameworks. The paper also discusses the dynamic aspects of goal-oriented concurrency control; in particular, an optimistic approach to the dynamic generation of goal-correct schedules is presented.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Abiteboul and V. Vianu, Transactions in relational databases, inProc. 10th Int. Conf. on Very Large Data Bases (1984) pp. 46–56.

  2. S. Abiteboul and V. Vianu, Transactions and integrity constraints, in:Proc. 4th ACM Symp. on Principles of Database Systems (1985) pp. 193–204.

  3. S. Abiteboul and V. Vianu, Equivalence and optimization of relational transactions, J. ACM 35(1988) 70–120.

    Google Scholar 

  4. S. Abiteboul and V. Vianu, A transaction-based approach to relational database specification, J. ACM 36(1989)758–789.

    Google Scholar 

  5. A.V. Aho and J.D. Ullman, Universality of data retrieval languages, in:Proc. 6th ACM Symp. on Principles of Programming Languages (1979) pp. 110–117.

  6. N.S. Barghouti and G.E. Kaiser, Concurrency control in advanced database applications, ACM Comp. Surveys 23(1991)269–317.

    Google Scholar 

  7. C. Beeri and M.Y. Vardi, Formal systems for tuple and equality generating dependencies, SLAM J. Comp. 13(1984)76–98.

    Google Scholar 

  8. P.A. Bernstein, V. Hadzilacos and N. Goodman,Concurrency Control and Recovery in Database Systems (Addison-Wesley, 1987).

  9. M.A. Casanova,The Concurrency Control Problem for Database Systems (Springer, LNCS 116, 1981).

  10. A.K. Chandra and D. Harel, Computable queries for relational databases, J. Comp. Syst. Sci. 21(1980) 156–178.

    Google Scholar 

  11. W. Du and A.K. Elmagarmid, Quasi serializability: A correctness criterion for global concurrency in InterBase, in:Proc. 15th Int. Conf. of Very Large Data Bases (1989) pp. 347–355.

  12. A. El Abbadi and S. Toueg, The group paradigm for concurrency control protocols, IEEE Trans. Knowledge Data Eng. KDE-1(1989)376–386.

    Google Scholar 

  13. H. Garcia-Molina, Using semantic knowledge for transaction processing in a distributed database, ACM Trans. Database Syst. 8(1983)186–213.

    Google Scholar 

  14. G. Gararin and P. Lebeux, Scheduling algorithms for avoiding inconsistency in large databases, in:Proc. 3rd Int. Conf. on Very Large Data Bases (1977) pp. 501–506.

  15. M. Genesereth and N. Nilsson,Logical Foundations of Artificial Intelligence (Morgan Kaufmann, 1987).

  16. J. Gray, Notes on data base operating systems, in:Operating Systems — An Advanced Course, ed. R. Bayer, M.R. Graham and G. Seegmuller (Springer, LNCS 60, 1978) pp. 393–481.

  17. J. Gray, The transaction concept: Virtues and limitations, in:Proc. 7th Int. Conf. on Very Large Data Bases (1981) pp. 144–154.

  18. V. Hadzilacos, A theory of reliability in database systems, J. ACM 35(1988)121–145.

    Google Scholar 

  19. D. Harel,First-Order Dynamic Logic (Springer, LNCS 68, 1979).

  20. R. Hull, Relative information capacity of simple relational database schemata, SLAM J. Comp. 15(1986)856–886.

    Google Scholar 

  21. A. Karabeg, D. Karabeg, K. Papakonstantinou and V. Vianu, Axiomatization and simplification rules for relational transactions, in:Proc. 6th ACM Symp. on Principles of Database Systems (1987) pp. 254–259.

  22. D. Karabeg and V. Vianu, Simplication rules and complete axiomatization for relational update transactions, ACM Trans. Database Syst. 16(1991)439–475.

    Google Scholar 

  23. H.F. Korth and G.D. Speegle, Formal model of correctness without serializability, in:Proc. ACM SIGMOD Int. Conf. on Management of Data (1988) pp. 379–386.

  24. N. Lynch, Multilevel atomicity — A new correctness criterion for database concurrency control, ACM Trans. Database Syst. 8(1983)484–502.

    Google Scholar 

  25. D. Maier,The Theory of Relatironal Databases (Computer Science Press, 1983).

  26. D. Maier, A.O. Medelzon and Y. Sagiv, Testing implications of data dependencies, ACM Trans. Database Syst. 4(1979)455–469.

    Google Scholar 

  27. C.H. Papadimitriou, The serializability of concurrent database updates, J. ACM 26(1979)631–653.

    Google Scholar 

  28. D. Shasha and N. Goodman, Concurrent search structure algorithms, ACM Trans. Database Syst. 13(1988)53–90.

    Google Scholar 

  29. A. Tuzhilin and P. Sprirakis, A semantic approach to correctness of concurrent transaction executions, in:Proc. 4th ACM Symp. on Principles of Database Systems (1985) pp. 85–95.

  30. V. Vianu and G. Vossen, Conceptual level concurrency control of relational update transactions (Extended Abstract), in:Proc. 2nd Int. Conf. on Database Theory (Springer, LNCS 326, 1988) pp. 353–367; full version in: Theor. Comp. Sci. 95(1992)1–42.

  31. G. Vossen,Data Models, Database Languages and Database Management Systems (Addison-Wesley, 1991).

  32. G. Vossen, Commit-serializability of schedules for relational update transactions, Found. Comp. Dec. Sci. 17(1992)153–163.

    Google Scholar 

  33. M. Winslett, Sometimes updates are circumscription, Manuacript, University of Illinois at Urbana-Champaign (1988).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, University of California, 92093, San Diego, La Jolla, CA, USA

    Victor Vianu

  2. Fachbereich Mathematik, Arbeitsgruppe Informatik, Justus-Liebig-Universität Giessen, Arndstrasse 2, D-6300, Giessen, Germany

    Gottfried Vossen

Authors
  1. Victor Vianu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gottfried Vossen
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

An extended abstract of this paper appeared in the Proceedings of the 2nd Symposium on Mathematical Fundamentals of Database Systems (MFDBS), LNCS 364 (Springer, 1989) pp. 398–414.

This author was supported in part by the National Science Foundation, under Grant Number IRI-8816078.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vianu, V., Vossen, G. Static and dynamic aspects of goal-oriented concurrency control. Ann Math Artif Intell 7, 257–287 (1993). https://doi.org/10.1007/BF01556355

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01556355

Keywords

Search

Navigation