DATABASE THEORY (236356)

Winter Semester 2010/11

Last given Winter Semester 2001/02

Course details

Course Home Page:
http://www.cs.technion.ac.il/~janos/COURSES/236356-10

Projects for final grade: Received Projects

Lecturer: Prof. J.A. Makowsky
Tirgul: NN
Language: Hebrew or English (if required) , Reading assignments in English
Time: Monday: 14:30-16:30 Lecture, 16:30-17:30 Tirgul
Place: Lecture and Tirgul in Taub 4 (CS Building)

FIRST MEETING: MONDAY, 18.10. 2010, 14:30

Previously Given: Winter 94/95, Spring 1997, Winter 2000/01, Winter 2001/02

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 and the ER-formalism. 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 concerns the theory of Query Languages and the foundation of Logic Programming (Datalog). 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:

These topics will be discussed depending on time and audience.

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 (under construction! List from 2002).

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)