Under Constructions

About teaching and learning

Lecture 1 (18. October, 2010)

• Entity-Relationship model
• Relational model
• Relational algebra (RA) and logic (DRC)
• First Order Logic (FOL) = DRC
• Datalog and Stratified Datalog
• Functional dependencies
• Outlook

Lecture 2 (25. October, 2010)

• What we can say in First Order Logic (FOL)
• The Completeness Theorem
• The Compactness Theorem
• Connectivity is not definable over finite and infinite structures

Lecture 3 (01. November, 2010)

Pebble Games and definability in First order Logic (or DRC).
Lecture on Pebble Games, I, Lecture on Pebble Games, II, from Computability and Definability 236331-01.

Lecture 4 (08. November, 2010)

• Games in structures WITHOUT relations (sets).
• Even/Odd are not FOL-definable
• Games in ordered structures.
• Using (implementation) order in queries.
• Order invariant queries in DRC.
• Even/Odd are order invariant definable using Transitive closure.
• OUTLOOK: Order invariant queries with Transitive closure are complete for Nondeterministic Logspace.

Lecture 5 (15. November, 2010)

• Views in Databases
• Translation schemes
• Examples from Mathematics
• Examples from Databases
• The Fundamental Theorem of Translation schemes
• Using the Fundamental Theorem for computing queries over views.
• Decomposition of Database schemes and preserving functional dependencies.
  (to be expanded in the lectures on "Dependency Theory" and Normal Forms).

Lecture 6 (22. November, 2010)

• Using the Fundamental Theorem for non-definability
  Equicardinality is not FOL definable
  Hamiltonicity is not FOL definable
  Eulerian graphs are not FOL definable.
  Deterministic reachability, Reachability and Path Systems are not FOL definable.
• Completeness via Translation schemes.
  The universality of Transitive Closures: Deterministic reachability, Reachability and Path Systems.
• Complexity of query languages.
  1. Stratified Datalog on ordered structures corresponds to P-time computable queries
  2. Linear Datalog on ordered structures corresponds to NL-space computable queries.

Student notes: Notes by Orit Abutbul

Distributing projects.

November 29 and December 6 2010

No lecture (Conference and Chanukkah).

Lecture 7 (13. December, 2010)

The Decision Problem in Logic, I

Solvable cases of the Decision problem, I

1. The logic of pure equality (using the Finite Model Property)
2. The logic of pure equality (using Elimination of quantiers)
3. The logic of equality with unary predicates only
4. Universal formulas
5. The Bernays-Schoenfinkel Theorem (Satisfiability of E*A*-formulas)

Lecture 8 (20. December, 2010)

Solvable cases of the Decision problem, II

1. Functional dependencies (FD's) and Multivalued dependencies (MD's)
2. Inclusion dependencies
3. Dependencies in ER-diagrams
4. (Full) Tuple generating dependencies in databases (FTGD's)
5. Embedded tuple generating dependencies in databases (ETGD's)

Lecture 9 (27. December, 2010)

Proof systems for dependencies

1. Functional dependencies (FD's) and Multivalued dependencies (MD's)
2. Inclusion dependencies
3. Armstrong relations and generic models
4. Propositional Horn formulas and resolution
5. Universal Horn formulas
6. The CHASE algorithm (if time permits)

Lecture 10 (3. January, 2011)

Dependencies and design, I

slides of lecture
You can see the latex-files of the slides of this lecture (for those who want to do their project in LaTeX).

See also Blog on design problems

Lecture 11 (10. January, 2010)

Dependencies and design, II

New Paper: BCNF for SQL
Recent Papers on Normal Forms in XML:

1. download An Information-Theoretic Approach to Normal Forms for Relational and XML Data, by Marcelo Arenas and Leonid Libkin
2. download Title and authors
3. download Title and authors
4. download Title and authors
5. download Title and authors
6. download Title and authors
7. download Title and authors

Lecture 12 (17. January, 2010)

Computable queries, I

Lecture 13 (24. January, 2010)

Computable queries, II

Tool 4: The unsolvability of the Halting Problem of Turing machines
Tool 5: Translation schemes and Turing reductions.

Unsolvable cases of the Decision problem

1. The Church-Turing Theorem
2. Trakhtenbrot's Theorem
3. Embedded Tuple generating dependencies (ETGD's)