DATABASE THEORY (236356)

Summaries and slides, Winter Semester 2019/20

Under construction. Last updated January 21, 2020

Lecture 1 (24.10.2019)

Present: 4 students (there are at least 13 students enrolled).
Organization and motivation of the course, checking the background of the students (Logic, Database systems, computability).
Logic and the relational model: The first steps. Aiming for Codd's Theorem.
Edgar F. Codd on Wikipedia.
Slides of the lecture.

Lecture 2 (31.10.2019)

Present: 7 students, 5 new, 2 previous students absent (there are at least 13 students enrolled).
Slides on Domain independence (domain invariance).
Slides for Lecture 2.
Slides my logic course of 2014. Especially Lectures 10-12.

Lecture 3 (07.11.2019)

We complete the proof of Codd's Theorem.

Depending on time, we may start with (non)-expressibilty in RA and DRC.
See Summary of Computability and Definability 236331-18.
and Slides of Computability and Definability 236331-18, Lectures 3 and 4.

Lecture 4 (14.11.2019)

We continue with (non)-expressibilty in RA and DRC.
We introduced substructure invariance and showed that universal FOL-formuas are substructure invariant.
We introduced order invariance and showed that order invariant formulas using the order are more expressive than without using the order.

We introduced quantifier rank of FOL formulas.
We introduced the equivalence relation on $\tau$-structures which states that two structures cannot be distinguished by sentences of quantifier rank k.

Lecture 5 (21.11.2019)

We introduced Pebble Games.
We studied the use of Pebble games to show non-expressibility of transitove closure and connectedness

More material on pebble games and non-definability can be found in the books
L. Libkin, "Elements of Finite Model Theory" and
H.-D. Ebbinghaus and J. Flum, "Finite Model Theory".

Lecture 6 (28.11.2019)

We discussed the Craig Interpolation Theorem for FOL.
We showed that on infinite structures every order invariant formula with order is logically equivalent to a formula without order.
We showed that this is not true when resricted to finite structures.

We introduced database dependencies: Functional Dependencies (FD), Join Dependencies, Full and Embedded Implicational Dependencies.

Ctaig's Theorem can be found in the book by J. Malitz, "Introduction to MathematicalLogic"

Lecture 7 (05.12.2019)

We studied Functional Dependencies FD's.

Tirgul: FD's from B. Kimelfeld's lectures 236363 (2013/14) see also 2015/16. and 2017/18.
Slides.

Otherwise we covered much of Chapter 8 and 9 in the book [AHV].

Lecture 8 (12.12.2019)

We study Normal Forms NF's.
Tirgul: NF's from B. Kimelfeld's lectures 236363 (2013/14) see also 2015/16. and 2017/18. Slides.
We explain Boyce-Codd-Normal-Form (slides from my lecture 236356-10).
Part I, Part II,
Chanukah/Christmas break
No lectures on December 19 and 26, 2019

Lecture 9 (02.01.2020)

We start studying Computable Queries after Chapter 6 of the book :
A Guided Tour of Relational Databases and Beyond
by M. Levene and G. Loisou.
I first give a summary of Computability: Turing Machines vs. Register Machines.
Computing with strings.
Computing with Natural numbers.
Computing with Integers.

Computing with Relations.

Lecture 10 (09.01.2020)

We continue studying Computable Queries after Chapter 6 of the book :
A Guided Tour of Relational Databases and Beyond
by M. Levene and G. Loisou.
We defined computable queries using independence (invariance) conditions:
  1. Order independence
  2. Isomorphisms (domain) independence
  3. Coding independence
We ntrocuded the query language QL and showed that it satisfies these independence properties.

We showed that RA and DRC can be expressed using QL.

Lecture 11 (16.01.2020)

We continued with our exploration of QL. We had to show some lemmas missing in the prove that RA and DRC can be expressed in QL.

We filled these gaps using Section 4 of the paper : by A. Chandra and D. Harel.
"Computable queries for relational data bases". Journal of Computer and System Sciences, 1980.

Next we introduced Datalog and its loop-free version and showed that it can be expressed in QL augmented by a symbol for the actual domain.

We are left with the question of what is safe Datalog.

This material is from Chapter 3.2 of the book by Levene and Loisou.
Chapter 3.2

Lecture 12 (23.01.2020)

We discuss safe Datalog.

We also give out projects for the final grade.

Lecture 13 (30.01.2020)

We will give a formal definition of the Entity Relationship model (ER-model) using FD's and ID's (Functional and inclusion dependencies) and discuss whether this translation into the relational model gives always relations in BCNF.

See slides from my introductory course from 2010.

Proposal for projects (30.01.2020)

Here are templates for slides in latex.

I propose projects as follows;

A: Non-definability in DRC.

Using Hankel matrices (aka connection matrices) as described in Lecture 3 . of my Pague Lectures 2014 . See also my paper with T. Kotek here .

Student: Yonatan Toybenshlak and Antoine Vinciguerra

B: Computable queries

Work out some details from Chapter 6 of A Guided Tour of Relational Databases and Beyond
by M. Levene and G. Loisou.

Student: Ohad Goudsmid

C: ER-design and Normal Forms

Students:
Noa Wengrowicz (Paper 1 below),
Tatiana Zahavchenko and Yael Grunzweig (both ER and IDNF),
Samuel Panzieri (tbd) , XXXX (tbd)

Here are a few relevant papers:

    Are ER-designed databases in Normal Form?
  1. Discovering Functional and Inclusion Dependencies in Relational Databases
    M. Kantola, H. Mannila, K.-J. Raiha, and H. Sirtola, 1992 DB-Manilla-etal.pdf
  2. The Implication Problem for Functional and Inclusion Dependencies
    J. Mitchell, 1983 DB-Mitchell.pdf
  3. The Implication Problem For Functional and Inclusion Dependencies is Undecidable
    A. Chandra and M. Vardi, 1985 DB-ChandraVardi
  4. Independent Database Schemes Under Functional and Inclusion Dependencies
    P. Atzeni and E. Chan, 1987 DB-Atzeni
  5. Inclusion Dependencies and Their Interaction with Functional Dependencies
    M. Casanova, R. Fagin and C. Papadimitriou, 1984 DB-Casanova-etal
  6. How to prevent interaction of functional and inclusion dependencies
    M. Levene and G. Loizou, 1999 DB-LeveneLouzou.pdf
  7. Justification for Inclusion Dependency Normal Form
    M. Levene and M. Vincent, 2000 DB-LeveneVincent.pdf
    Critical evaluations of Normal Forms
  8. Schema Optimisation Instead Of (Local) Normalisation
    B. Thalheim, 2019 DB-Schema_Optimisation_Instead_Of_Local_Nor
  9. Why Normalization Failed to Become the Ultimate Guide for Database Designers?
    M. Fotache, 2006 DB-Why_normalization_failed_to_become_the_u.pdf
    Undecidability of FD's and MVD's
  10. On the undecidability of implications between embedded multivalued database dependencies,
    C. Herrmann, 1983 DB-Herrmann.pdf