Fundamentos lógicos de la teoría de bases de datos

Prof. Diego Figueira y Prof. Gabrielle Puppis. CNRS, LaBRI, Bordeaux, Francia.

Abstract

This course shows some fundamental results linking logics with database query languages. It may serve as an introduction to _nite model theory and database theory. It will cover basic de_nitions and results such as First-order logic, Relational Algebra and Conjunctive queries; data and query complexities; complexity of evaluation /satis_ability problems; and expressivity problems. It will focus on the basic problems for two of the most basis query languages for Relational Databases, namely Relational Algebra and Conjunctive Queries, from the perspective of complexity and expressiveness. We don't assume any prior knowledge in neither logic nor databases, but a familiarity with basic complexity classes, such as NP, PTIME, PSPACE is needed. The goal of the course is to give the basic tools that enable a deeper understanding of database query languages.

Subjects covered

1. First Order logic (FO) basics (day 1)

(a) First-order structures

(b) FO = Relational Algebra

(c) Data complexity, combined complexity

(d) Model checking for FO

(e) Satis_ability for FO

 

2. Expressiveness of FO (days 2,3)

(a) Ehrenfeucht-Fra_ss_e game

(b) 0-1 law

(c) Hanf and Gai_man locality

 

3. Conjunctive Queries (CQ) (days 3,4)

(a) De_nition, duality of CQ's and structures

(b) CQ = select-project-join-union fragment of Relational Algebra

(c) CQ = Existential-positive FO (EPFO)

(d) Homomorphisms, cores, substructures

(e) Chandra-Merlin Lemma

(f) Evaluation problem, complexity

(g) Inclusion and equivalence problems

 

4. Well behaved classes of CQ (day 5)

(a) Acyclic CQ, Gaifman graph, evaluation problem

(b) Bounded-width EPFO, evaluation problem

(c) tree decompositions

(d) functional dependencies

Requirements

Elementary notions of complexity (PTime, NP, PSpace, LogSpace), reductions, decidability.

Attendance Examination
The Exam will be take place on Saturday 25th of July.

Bibliography

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.