DATABASE THEORY (236356)
Winter Semester 2019/20
Last given Winter Semester 2010/11
Under construction. Last updated July 3, 2019
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
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
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.
Abstract State Machines (ASM) for Databases
XML Data Models.
We shall reach a level where topics for research can be
formulated both for M.Sc. and Ph.D. candidates.
- * S. Abiteboul, R. Hull and V. Vianu,
Foundations of Databases , Addison-Wesley 1995
- * H. Mannila and K.J. Raiha, The Design of Relational
Databases , Addison-Wesley 1992
Entity-Relationship Modeling: Foundations of Database Technology ,
M. Levene and G. Loizou,
Guided Tour of Relational Databases and Beyond ,
Springer-Verlag, London, 1999
- * G. Kuper, Leonid Libkin and J. Paredaens (Eds.),
Constraint Databases, Springer 2000.
- 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.
- 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
Review of the books Foundations of
The Design of Relational databases
and Kannelakis' handbook article
by J.A. Makowsky, from the Journal of
- H.D. Ebbinghaus and J. Flum, Finite Model Theory,
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)