Logical Foundations of Databases

Diego Figueira and Gabriele Puppis

  • Area: LoCo
  • Level: F
  • Week: 2
  • Time: 14:00 – 15:30
  • Room: D1.01

Abstract

The proposed course will present several fundamental results linking logics with database query languages. The course can thus serve as an introduction to finite model theory and database theory. More specifically, it will cover basic knowledge about first-order logic, Relational Algebra and Conjunctive Queries; complexity of fundamental decision problems, such as evaluation and satisfiability; as well as results about expressiveness of specification languages. Regarding the logical formalisms, we will focus mainly on two important query languages for relational databases, namely, Relational Algebra and Conjunctive Queries. We will not assume any prior knowledge on either logic or databases, but some familiarity with basic results in complexity theory will be required. The goal of the course is to give the fundamental tools that enable a deeper understanding of database query languages.

Structure of the course and tentative schedule

The course will be given in English; however, if needed, questions can be posed and answered in French, Spanish, or Italian. The course will be structured into five lessons of about 90 minutes each.

Below is a tentative schedule of the covered subjects.

  • Day 1. First Order logic (FO) basics
    1. First-order logic
    2. Relational Algebra
  • Day 2. Evaluation and satisfiability
    1. Data complexity, combined complexity
    2. Complexity of model checking
    3. Undecidability of satisfiability problem
  • Day 3. Conjunctive Queries (CQ)
    1. CQ = Select-Project-Join fragment of Relational Algebra
    2. CQ = Existential-Positive FO (EPFO)
    3. Duality of CQ’s and structures
    4. Chandra-Merlin Lemma
  • Day 4. Complexity of problems on CQ
    1. Evaluation problem
    2. Containment and equivalence problems
    3. Evaluation problem for bounded-width CQ
  • Day 5. Expressiveness of FO
    1. Ehrenfeucht-Fraïssé games
    2. Hanf and Gaiffman locality
    3. 0-1 Law

Slides

Day 1

Day 2

Day 3

Day 4

Day 5

Additional References

[1] Serge Abiteboul, Richard Hull, Victor Vianu, Foundations of Databases. Addison Wesley.
Available online at http://webdam.inria.fr/Alice/

[2] Leonid Libkin. Finite Model Theory. Springer, 2004.