Query enumeration and nowhere dense graphs / Alexandre Vigny ; sous la direction de Arnaud Durand et de Luc Segoufin

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Catalogue Worldcat

Graphes, Théorie des

Bases de données -- Interrogation

Analyse des données

Durand, Arnaud (1981-...) (Directeur de thèse / thesis advisor)

Segoufin, Luc (Directeur de thèse / thesis advisor)

Sirangelo, Cristina (19..-....) (Président du jury de soutenance / praeses)

Ossona de Mendez, Patrice (1966-....) (Rapporteur de la thèse / thesis reporter)

Martens, Wim (Rapporteur de la thèse / thesis reporter)

David, Claire (1980-....) (Membre du jury / opponent)

Grandjean, Étienne (19..-....) (Membre du jury / opponent)

Université Sorbonne Paris Cité (Organisme de soutenance / degree-grantor)

École doctorale Sciences mathématiques de Paris centre (Paris ; 2000-....) (Ecole doctorale associée à la thèse / doctoral school)

Institut de mathématiques de Jussieu-Paris Rive Gauche (1997-....) (Equipe de recherche associée à la thèse / thesis associated research team)

Université Paris Diderot - Paris 7 (1970-2019) (Autre partenaire associé à la thèse / thesis associated third party)

Résumé / Abstract : Les travaux présentés dans ma thèse se situent à l’interface entre complexité, algorithmique et logique. Plus particulièrement, on s’intéresse à la complexité d'évaluation de requêtes.Plus précisément, étant donné G un graphe fini. Une requête q définit un sous ensemble de k-uplets de sommets de G que l'on note q(G). On appelle k l'arité de q et on se essaye alors d'effectuer efficacement les taches suivantes :1) décider si l'ensemble q(G) est vide ou non.2) décider si un k-uplet donné appartient à l'ensemble des solutions q(G).3) calculer le nombre de solutions.4) énumérer les éléments de q(G).En ce qui concerne la 4ème tache, un algorithme qui va énumérer les solutions sera décomposé en deux parties. La première est appelé le pré-calcul et sert à préparer l’énumération. Idéalement cette étape de requière qu’un temps linéaire en la taille du graphe. La deuxième étape est ensuite l’énumération des solutions. Le temps nécessaire pour obtenir une nouvelle solution est appelé le délai. Idéalement on souhaite que le délai de dépende pas de la taille du graphes mais uniquement de la taille de la requête. On parle alors d’énumération à délai constant après pré-calcul linéaire.Au début de cette thèse, une grand part des interrogations au sujet des classes de graphes pour lesquelles une énumération à délai constant serait possible semblait se trouver au niveau des classes de graphes nulle-part dense. Le résultat principal de cette thèse est de montrer qu’il est possible d’énumérer les solutions des requêtes du premier ordre sur les graphes nulle-part dense avec un délai constant après un pré-calcul pseudo linéaire.

Résumé / Abstract : The topic of my thesis lies between complexity, algorithmic and logic. In particular, we are interested in the complexity of evaluating query.More precisely, given G a finite graph. A query q defines a subset of k-tuples of vertices of G that we note q(G). We call k the arity of q and we then try to efficiently perform the following tasks:1) decide whether the set q G) is empty.2) decide whether a given k-tuplet belongs to the set of solutions q(G).3) calculate the number of solutions.4) enumerate the elements of q(G).Regarding the 4th task, an algorithm that will enumerate the solutions can be decomposed into two steps. The first is called preprocessing and is used to prepare the enumeration. Ideally this step only requires a time linear in the size of the graph. The second step is the enumeration properly speaking. The time needed to get a new solution is called the delay. Ideally we want the delay to not depend on the size of the graph but only on the size of the query. We then talk about constant delay enumeration after linear preprocessing.At the beginning of this thesis, a large part of the interrogations about classes of graphs for which a constant delay enumeration is possible seemed to be located around the classes of nowhere dense graphs