Winter Semester 2019/20

Last given Winter Semester 2010/11
Under construction. Last updated July 3, 2019

Course details

Course Home Page:

Lecturer: Prof. J.A. Makowsky
Tirgul: J.A. Makowsky
Language: Hebrew or English (if required) , Reading assignments in English
Time: Thursday: 09:30-11:30 Lecture, 11:30-12:30 Tirgul
Place: TBA

FIRST MEETING: THURSDAY, 24.10.2019, 09:30

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

Prerequisites and Requirements:

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

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

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.


  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. * B. Thalheim, Entity-Relationship Modeling: Foundations of Database Technology , Springer 2000
  4. * M. Levene and G. Loizou, Guided Tour of Relational Databases and Beyond , Springer-Verlag, London, 1999
  5. * G. Kuper, Leonid Libkin and J. Paredaens (Eds.), Constraint Databases, Springer 2000.
  6. 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.
  7. 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

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
  3. 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)