Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

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

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

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

Plan

  • Lecture 1: 7 décembre ✔
  • Lecture 2: 14 décembre ✔
  • Lecture 3: 4 janvier ✔
  • Lecture 4: 11 janvier ✔
  • Lecture 5: 18 janvier ✔
  • Lecture 6: 25 janvier ✔
  • Lecture 7: 1 février ✔
  • Lecture 8: 8 février ✔
  • Exam: 8 mars

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 2016-2017

- 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 notes from 2009-2010

Prerequisites

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

Related courses:

Bibliography

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

Pedagogic team

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA