General purpose schedulers for database systems | Acta Informatica Skip to main content
Springer Nature Link
Log in

General purpose schedulers for database systems

  • Published:
Acta Informatica Aims and scope Submit manuscript

Summary

A family of simple models for database systems is defined, where a system is composed of a scheduler, a data manager and several user transactions. The basic correctness criterion for such systems is taken to be consistency preservation. The central notion of the paper is that of a general purpose scheduler, a database system scheduler that is blind to the semantics of transactions and integrity assertions. Consistency preservation of a database system is shown to be precisely equivalent to a restriction on the output of a general purpose scheduler GPS, called weak serializability. That is, any database system using GPS will preserve consistency iff the output of GPS is always weakly serializable. This establishes a tight connection between database system correctness and scheduler behavior. Also, aspects of restart facilities and predeclared data accesses are discussed. Finally, several examples of schedulers correct with respect to weak serializability are presented.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho AV, Hopcroft JE, Ullman JD (1975) The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass

    Google Scholar 

  2. Bernstein PA, Shipman DW, Rothnie JB (1980) Concurrency control in a system for distributed databases (SDD-1), ACM TODS 5: 18–51

    Google Scholar 

  3. Bernstein PA (1979) A formal model of concurrency control mechanisms for database systems. IEEE Transactions on Software Engineering p 203

  4. Casanova MA, Bernstein PA (1979) General Purpose Schedulers for database systems, Technical Report TR-08-79, Center for Research in Computing Technology, Harvard University

  5. Casanova MA, Bernstein PA (1980) On the construction of database schedulers based on conflictpreserving serializability. (In press)

  6. Cook SA (1975) Axiomatic and interpretative semantics for an ALGOL fragment, TR-79, Univ of Toronto

  7. Eswaran KP, Gray JN, Lorie R, Traiger I (1976) The notion of consistency and predicate locks in a data base system, CACM 19:624–633

    MathSciNet  Google Scholar 

  8. Flon L, Suzuki N (1977) Nondeterminism and the correctness of parallel programs, IFIP Working Conference on the Formal Description of Programming Concepts

  9. Gardarin G, Lebeaux P (1977) Scheduling algorithms for avoiding inconsistency in large databases, Proc of the Int Conf on Very Large Data Bases, 1977, p. 501

  10. Howard JH (1976) Proving monitors, CACM 19: 273–279

    MATH  MathSciNet  Google Scholar 

  11. Kung HT, Papadimitriou CH (1979) An optimality theory of concurrency control for databases, ACM-SIGMOD 1979 International Conference on Management of Data, ACM, NY, p 116–126

    Google Scholar 

  12. Lamport L (1976) Towards a theory of correctness for multi-user data base systems. Massachusetts Computer Associates Tech Rep CA-7610-0712

  13. Lorie RA (1977) Physical integrity in a large segmented database, ACM TODS 2:91–104

    Article  Google Scholar 

  14. Manna Z (1974) Mathematical theory of computation, McGraw-Hill, New York (Chap 4 pp 260)

    Google Scholar 

  15. Owicki SS (1975) Axiomatic proof techniques for parallel programs, Dept of Comp Science, Cornell Univ, Tech Rep 75–251

  16. Papadimitriou CH, Bernstein PA, Rothnie JB (1977) Some computational problems related to database concurrency control, Proc of Conf on Theoretical Computer Science, Waterloo, Aug 1977, pp 275–282

  17. Papadimitriou CH (1979) The serializability of concurrent updates, JACM 26: 631–653

    MATH  MathSciNet  Google Scholar 

  18. Rosenkrantz DJ, Lewis PM, Stearns RE (1978) System level concurrency for distributed database systems, ACM TODS 3: 178–198

    Article  Google Scholar 

  19. Schlageter G (1978) Process synchronization in database systems, ACM TODS 3: 248–271

    Article  Google Scholar 

  20. Stearns RE, Lewis PM, Rosenkrantz DJ (1976) Concurrency control for database systems, Proc of the 17th IEEE Symp on Found of Comp Sci, pp 19–32

  21. Stonebraker M, Neuhold E (1977) A distributed database version of INGRES, Proc 2nd Berkeley Workshop on Distributed Databases and Computer Networks, Berkeley, California

  22. Thomas RH (1979) A majority consensus approach to concurrency control for multiple copy databases, ACM TODS 4: 180–209

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Center for Research in Computing Technology, Aiken Computation Laboratory, Harvard University, 02138, Cambridge, MA, USA

    Marco A. Casanova & Philip A. Bernstein

Authors
  1. Marco A. Casanova
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Philip A. Bernstein
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Casanova, M.A., Bernstein, P.A. General purpose schedulers for database systems. Acta Informatica 14, 195–220 (1980). https://doi.org/10.1007/BF00264253

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation