In french: Logique, complexité descriptive et théorie des bases de données.

Coordinator : Luc Segoufin

Début du cours le mercredi 7 décembre 2016.

Le cours à lieu le mercredi, de 8h45 à 11h45, en salle 2036

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.

- Introduction. Conjunctive queries (CQ) and First-Order (FO) logic. Links between logic and complexity: combined and data complexity. Illustration with FO and CQ.

- Expressive power: 0-1 laws, Ehrenfeucth-Fraïssé games, locality. Application to FO. (2 lectures)

- 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.

- Logics with bounded number of variables. MSO and links with automata.

- Links with string automata: MSO=REG, FO=star-free=Aperiodic

Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5 Lecture 6 Lecture 7 Lecture 8

Exam 2010

Elementary notions of complexity: PTime, NP, PSpace, LogSpace. Basic knowledge on finite state automata.

2.20.2: Fondations mathématiques de la théorie des automates Mathematical foundations of automata theory

• S. Abiteboul, R. Hull et V. Vianu. Foundations of Databases. Addison-Wesley. 1995. Il existe une traduction en français chez Vuibert.

• N. Immermann. Descriptive Complexity. Springer Graduate Texts in Computer Science. 1999.

• L. Libkin. Elements of Finite Model Theory. Springer. 2004.

Luc Segoufin.