Herramientas Personales
Usted está aquí: Inicio / Eventos / ECI / ECI 2015 / Courses ECI 2015 / Introduction to Logical Foundations of Database

Introduction to Logical Foundations of Database

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


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


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



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.