Logic, descriptive complexity and database theory (24H, 3 ECTS)
In french: Logique, complexité descriptive et théorie des bases de données.
Coordinator : Luc Segoufin
Importants messages
First lecture: Monday September 20, 8:45am
Objectives
This course could be seen with three different angles.
The first one is to see it as an introduction to the theory of databases, and
more specifically to the study of query languages for database systems. We will
give the basis of what the complexity of a query language is. We will also give
elementary tools for studying the expressive power of query languages.
The second point of view is an introduction to descriptive complexity. We will
see that the difficulty of expressing a problem is closely related to the
resources necessary for computing it. We will see that most of the open
problems concerning the separation of complexity classes can be reformulated in
term of equality of logics, without any reference to a computing model such as
Turing machines.
The third point of view is an introduction to finite model theory. We will present concepts like locality, 0-1 laws and Ehrenfeucht-Fraïsse games.
Of course the real objective of this course is to show that all this form a unique story linking nicely logic, complexity and query languages.
In french:
Ce cours peut-être vu sous trois angles différents.
Le premier est de le voir comme une introduction à la théorie des bases de
données, et plus particulièrement à l'étude des langages de requêtes pour les
bases de données. On donne les bases de ce qu'est l'étude de la complexité d'un
langage de requêtes. On donne aussi les outils élémentaires permettant l'étude
du pouvoir d'expression d'un langage de requêtes.
Le deuxième est de le voir comme une introduction à la théorie de la complexité
descriptive. On montre que la difficulté nécessaire à énoncer une propriété est
intimement liée aux ressources nécessaires pour la calculer. On montre que les
problèmes ouverts de séparation des classes de complexité peuvent se formuler
sans aucune référence à un modèle de calcul (comme les machines de Turing par
exemple).
Le troisième est de le voir comme une introduction à la théorie des modèles
finis. On présente des concepts comme la localité, les lois 0-1 ou les Jeux de
Ehrenfeucth-Fraïssé.
Bien sur l'objectif du cours est de montrer que tout cela correspond en fait à
une seule et même histoire liant la logique, la complexité et les langages de
requêtes de façon élégante.
Outline for 2010-2011
- Introduction. Conjunctive queries (CQ), First-Order (FO) logic, relational calculus and relational algebra.
Links between logic and complexity: combined and data complexity. Illustration with FO and CQ.
- Expressive power: 0-1 laws, Ehrenfeucth-Fraïssé games. Application to FO. (2 lectures)
- Logics with bounded number of variables. MSO and links with automata.
- Fix-point logics: IFP and PFP. Links 0-1 laws and Ehrenfeuch-Fraissé games. Links with PTime and PSpace. Theorem of Immerman-Vardi. Theorem of Abiteboul-Vianu.
- Links with string automata: MSO=REG, FO=*-free=Aperiodic
