This page makes a subset of the database theory slides that I have created
in the past available to the public, specifically to lecturers who might want
to use all or part of this material in their courses. For this reason,
I put these SLIDES AND THEIR LATEX SOURCES in the PUBLIC DOMAIN. I have
created these slides entirely myself, and think that the inspiration that I
may have derived from other works is covered by fair use.
I make NO WARRANTIES for the correctness of the content of these slides or
that they are fit for any particular purpose. If you find mistakes, I'd be
interested in hearing about it.
Since these slides are in the public domain, you may use or modify them in
any way you like. In particular, it is ok to call them your slides and not
to acknowledge me. However, if you find the slides useful, I ask you to
sign my blog article announcing the creation of this page (i.e., post a comment), and to say something nice.
Note that this is not a course page, and it is not representative of the
courses that I teach or have taught in the past. The slides made available
here focus on certain aspects of logic and finite model theory. By themselves,
I do not think they make an interesting or self-contained course. I have currently
no plans to release my other DB theory slides here, but this may change in the
future.
|
Lecture | English slides | German slides | Remarks |
 |
First-order Logic and Relational Calculus #1:
Syntax and Semantics of FO; examples; typical beginner's mistakes
|
.tex
.pdf
|
.tex
.pdf
|
 |
First-order Logic and Relational Calculus #2:
Relational domain calculus; methodology for getting from a prose specification
to a calculus query.
|
.tex
.pdf
|
.tex
.pdf
|
I found these slides quite useful, even for undergraduate database systems
teaching.
|
 |
First-order Logic and Relational Calculus #3:
Domain independence, range restriction, Codd's theorem and its proof, and many examples
of the mapping from FO to relational algebra.
|
.tex
.pdf
|
n/a
|
My proof makes heavy use of the active domain relation (which is easily definable in relational algebra). This makes the proof less intelligent than the one,
say, in Abiteboul-Hull-Vianu, but also much shorter and simpler.
|
 |
Failure of Compactness in the Finite:
Motivates EF games and 01 laws |
n/a
|
.tex
.pdf
|
Reachability argument is from Libkin, Elements of Finite Model Theory,
if I remember well.
|
 |
Ehrenfeucht-Fraïssé Games #1:
Definition of EF games; many examples with game trees; proof of the
methodology theorem using just games trees in both proof directions. |
.tex
.pdf
|
.tex
.pdf
|
The proof uses a near minimal amount of machinery and is as elementary as
I could make it. I think this helps computer science students, but mathematicians will have seen more elegant proofs.
|
 |
Ehrenfeucht-Fraïssé Games #2:
Composition lemmata and some example inexpressibility proofs.
|
.tex
.pdf
|
.tex
.pdf
|
Some inspiration was taken from Phokion Kolaitis' beautiful slides.
|
 |
Zero-one Laws:
Definitions and one long proof. |
.tex
.pdf
|
.tex
.pdf
|
I constructed some -- as I think minimal -- graphs that satisfy certain
extension axioms. Haven't seen these anywhere else before. Hopefully useful.
|
 |
Automata and Decidability of MSO on Strings and Trees:
I give a fully executed translation from an MSO formula (on finite strings)
to an automaton. Haven't seen this before in the literature -- this might
be a great help for not so confident students, because it really only requires
undergraduate-level automata theory.
|
.tex
.pdf
|
n/a
|
The part on infinite objects is sloppy in that I do not give a construction
for complementing automata on infinite objects.
|