236356 Database Theory, Winter 2001/02

Under Construction

We shall roughly cover the book by Abiteboul, Hull and Vianu. Additionally, the emphasis will change from previous courses. We shall include (new):

The expressive power of SQL (after Libkin)
Constraint databases

Previous abstracts (1997)

236356 Database Theory, Spring 1997

Last update: March 16, 97

Prerequisite: Logic for CS 1 (234292)

[Ma1] J.A. Makowsky, Lecture Notes of Logic for Computer Science 1, part I.
[Ma2] J.A. Makowsky, Lecture Notes of Logic for Computer Science 1, part II.

Index of lectures

Lecture 1 (6.3.97)
Lecture 2 (13.3.97)
Lecture 3 (20.3.97)
Lecture 4 (27.3.97)

Lecture 1 (6.3.97)

Administrative organization of this course (Tirgul, Exams, Grades).

Overview of the Database Management Systems Course

In the introductory course Database Management Systems (236363) we introduced

The ER-Model and its system of tables;
the Relational Model;
Query languages SQL, extSQL, Relational Algebra (RA, procedural), Relational Calculus (RC, descriptive), Datalog (Prolog-like);
Functional Dependencies (and their manipulation);
Normal Forms (BCNF, 3-NF);
obtaining normal forms via decomposition (projections);
obtaining dependency preserving normal forms via synthesis.
We also mentioned that certain queries (e.g. transitive closure) are not expressible in RA or RC, but expressible in Datalog.

What is Database Theory ?

Database Theory has three aspects:

It gives a theory of query languages (initiated by A. Chandra and D. Harel in 1979). This is by now very well developed. The second part of this course will deal with the theory of query lanuages.
It gives a specification mechanism for relational database schemes using dependencies. In particular it studies the consequence problem between first order dependencies. The Consequence Problem for these dependencies has been almost completely solved (mostly negatively).
Databases are designed using this specification mechanism and the question arises which of the possible (equivalent) design solutions are preferable. ER-diagrams traditionally are viewed only as useful visualizations. In this course we take them more seriously. Database Theory tries to solve the design problem using the table format and the dependencies as the only available information. The design problem has a rich but not so convincing literature. We think that the design problem has not yet been understood satisfactorally.

Lecture 2 (13.3.97)

The ER-Model and its Dependencies

We review the main ingredients of the ER-model. You may want to consult my lectures notes of the introductory course. With each construct (Entity, Relationship, Weak Entity, Aggregation, etc) we associate a set of tables, Functional Dependencies (FD's) and Inclusion Dependencies (IND's). Some more general dependencies arise from case distinction and partitioning.

In short, we assoicate with each ER-diagram a set of tables and a set of dependencies. The design problem is now formulated as the search for criteria for good design.

Decomposition of Relation Schemes

Tables can be decomposed by projections. The decomposition into BCNF and 3-NF are given as examples. Decomposition is lossless (without loss of information) if the original table can be reconstructed from the projections by joins. The decomposition theorem asserts that this is possible, if a certain FD's hold.

Theorem: proj_XY(R) |><| proj_XY(R) = R iff either Y->X or Y->Z.

Why should one restrict decomposition to projections and reconstruction to joins ? We shall introduce a general form of restructuring (translation) of database schemes and database states. Back to Index

Lecture 3 (20.3.97)

Reference for the next few lectures:

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)

First Order Queries and Dependencies

First Order queries (Tuple Calculus) vs. Relational Algebra. Dependencies are queries with boolean answers (boolean queries).

Classification of First Order Dependencies

Functional Dependencies
Inclusion Dependencies
Join Dependencies
Tuple Generating Dependencies
Equality Generating Dependencies
Full Implicational Dependencies
Embedded Implicational Dependencies
Typing of dependencies

Let D be a (finite) set of dependences and d be one additional dependency. We say the d is a consequence of D, denoted by D |= d , if d is true in all finite database states in which D is true.

The Consequence Problem asks whether the relation D |= d is algorithmically solvable. We know from the introductory course that the answer is yes when D and d are restricted to FD's.

Translation Schemes

Background literature:

[Ma3] J.A. Makowsky, Draft chapter of Interpretations, Translations and Reductions (for the Handbook of Logic in CS)

Restructuring via Translation Schemes

Remark on updates Back to Index

Lecture 4 (27.3.97)

Information Preserving Translations

Dependency Preserving Translation

Lecture 4 (3.4.97)

Horizontal and vertical decompositions

Lecture 4 (10.4.97)

The consequence problem for dependencies. FD's FID's IND not equivalent to FID's

Later lectures

Closure under Interpretations

The Consequence Problem for Dependencies: Decidable cases

A class of dependencies is decidable if the consequence problem can be solved by an algorithm.

Functional Dependencies (FD's) are decidable.
Inclusion Dependencies (IND's) are decidable.

The Consequence Problem for Dependencies: Undecidable cases

First Order Dependencies are undecidable (for finite relations and in general). [Church-Turing, Trakhtenbrot]
Embedded Implicational Dependencies are undecidable (for finite relations and in general).
FD's and IND's together are undecidable.

Normal Forms for Relation Schemes

Redundancy and update anomalies
Boyce-Codd Normal Form
3-NF and 4-NF
Obtaining Normal Forms using projections only
Obtaining Normal Forms using Translation schemes: BCNF via splitting attributes.
ER-Normal Form
Are Normal Forms useful ?

Lecture 5 (17.4.97)

Undecidability (i)

Lecture 6 (1.5.97)

Undecidability (ii)

Lecture 7 (8.5.97)

Ehrenfeucht Fraisse Games (i)

Lecture 8 (15.5.97)

Ehrenfeucht Fraisse Games (ii)

Lecture 9 (22.5.97)

Ehrenfeucht Fraisse Games (iii)
Second order Logic and RC +WHILE

Lecture 10 (29.5.97)

Complexity of query languages

Lecture 11 (5.6.97)

Complexity of query languages

Lecture 12 (19.6.97)

Conclusions