Foundations of Databases

Bolzano, Spring '08

  Instructor:           David Toman (david@cs.uwaterloo.ca)   
  Office:               Post Office 228 (office hours by appointment)    
  Lectures/Exercises    Thu 14:00-16:00   E221
                        Thu 17:00-18:00   E221 

  Class Info:           http://db.uwaterloo.ca/~david/fdb

Syllabus:

  • Objectives and Outcome:
    The goal of the course is to familiarize students with the concepts underlying database systems. We study predicate logic as a basis for database query languages and make use it to express complex logical queries in SQL. We then present techniques underlying query optimization (containment and equivalence checking). Then, we discuss options to extend non-recursive languages with means to express various forms of recursion and study the difficulties for query semantics and query evaluation that arise. The course puts strong emphasis on how to formulate questions that can approached with logical methods, that is, by proving or disproving formal statements.
  • Basic Info:
    Credits: 4 (24 lectures, 12 exercises, all in English)
    Assessment: written final exam (July 10 at 3p.m. in A101), exercises
  • Lectures/Exercises:

    1. Introduction: Relational Structures, Databases, and Queries (sample queries)
    2. Relational Calculus: Properties (Domain Independence, etc.)
    3. Relational Algebra and SQL (including duplicates)
    4. Basic Query Optimization: Algebraic Equivalences, etc.
    5. Conjunctive Queries (rule syntax, examples), Containment for Conjunctive Queries
    6. Schema Constraints
    7. Schema Constraints and their impact on containment
    8. Query Optimization revisited
    9. What cannot be done in Relational Calculus
    10. Datalog and Fixpoints (and Second-order logic)
    11. Datalog and Negation
    12. Incompleteness with quick notes on NULLs; Overview of additional topics. Summary of the class

  • Assignments:

    1. Relational Calculus etc.: 5.2 (1) and (3), queries (a-c,f); 5.4(b,d), 5.23, and 5.26 (all from the text available below).
    2. Conjunctive Queries, Constraints, etc.: 4.3(a), 4.4(a), 6.10(a,b), 6.22, 8.5, 9.10(a), 10.14
    3. Expressiveness, Datalog, etc.: 12.7, 12.10, 12.12(a,b), 12.23, 13.3, 15,1(a), 15.2, 17.7(i,ii)