DATABASE THEORY (236356)

Winter Semester 2001/02

Course Home Page:
http://www.cs.technion.ac.il/~janos/COURSES/DB/announce.html

Projects for final grade:

Strike News

Lecturer: Prof. J.A. Makowsky
Tirgul: Prof. J.A. Makowsky
Language: Hebrew , Reading assignments in English

Previously Given: Winter 94/95, Spring 1997, Winter 2000/01
Time: TUESDAY: 9:30-10:30 Tirgul 10:30-12:30 Lecture
Place: To be announced

FIRST MEETING: TUESDAY, 23.10, 9:30

Prerequisites and Requirements:

Logic 1 (2342920) necessary and Database Systems (236363).
The course will mainly follow [1,2,6] below. Take home exam or project.

Abstracts of each lecture will be available together with further references.

Course outline:

This course gives the logical foundations of the theory of relational data bases. Its main topics are the semantics of data base specifications and of query languages. Complexity issues will also be discussed. The first part of the course is dependency theory and its relationship to data modelling. The second part of the course is the theory of query languages. Both parts are based on the relational model of data bases. In a third part of the course alternative data models of theoretical significance will be discussed: The most recent developments are Constraint Databases. Depending on time and audience we shall also look at the entity relationship model, object oriented models and knowledge bases. We shall reach a level where topics for research can be formulated both for M.Sc. and Ph.D. candidates.

Textbooks

  1. * S. Abiteboul, R. Hull and V. Vianu, Foundations of Databases , Addison-Wesley 1995
  2. * H. Mannila and K.J. Raiha, The Design of Relational Databases , Addison-Wesley 1992
  3. * G. Kuper, Leonid Libkin and J. Paredaens (Eds.), Constraint Databases, Springer 2000.
  4. P.C. Kannelakis, Elements of Relational Database Theory, in: Handbook of Theoretical Computer Science, volume 2, chapter 17. J. van Leeuwen, ed., Elsevier Science Publishers, 1990.
  5. J. Paredaens, P. De Bra, M. Gyssens and D. van Gucht, The Structure of the relational database model, EATCS Monographs on Theoretical Computer Science, vol. 17, Springer Verlag 1989
Preprints of recent research relevant for the course.

Further Literature

  1. Review of the books Foundations of Databases, The Design of Relational databases and Kannelakis' handbook article by J.A. Makowsky, from the Journal of Symbolic Logic.
  2. H.D. Ebbinghaus and J. Flum, Finite Model Theory, Springer 1996 J. Ullmann, Principles of data base systems, Computer science press, 1980ff.
  3. D. Maier, The theory of relational databases, Computer science press, 1983.
  4. A. Chandra and D. Harel, Computable queries, JCSS 21.2 (1980).
  5. J.A.Makowsky, Review of [1, Ullman], [2, Maier] and [3, Chandra and Harel], in Journal of Symbolic Logic 51.4 (1987).
  6. M. Vardi, Fundamentals of dependency theory, in: Trends in theoretical computer science (E.Boerger ed.), Computer science press, 1988.
  7. J.A. Makowsky and E. Ravve , Translation Schemes and the Fundamental problem of Database Design (invited lecture) (Published in: Conceptual Modeling - ER'96, B. Thalheim (ed.), LNCS vol. 1157 (1996) pp. 5-26)