Thesis of Nicolas Crosetti

Enrichir et résoudre des programmes linéaires avec des requêtes conjonctives

L'optimisation mathématique et la gestion des données sont deux domaines majeurs de l'informatique qui sont largement étudiés par des communautés essentiellement distinctes. Cependant, les problèmes d'optimisation complexes dépendent souvent de grands jeux de données qui peuvent être difficiles à gérer, alors que la gestion de grandes quantités de données n'est utile que dans la mesure où l'on analyse ces données pour en extraire des connaissances afin de résoudre un problème pratique, de sorte que ces domaines sont souvent entremêlés en pratique. Cette thèse se place à la croisée de ces deux domaines en étudiant les programmes linéaires qui raisonnent sur les réponses de requêtes de bases de données. La première contribution de cette thèse est la définition de ce que nous appelons le langage des programmes linéaires avec requêtes conjonctives (que nous noterons LP(CQ)). Il s'agit d'un langage de modélisation de programmes linéaires avec des constructions permettant d'exprimer des contraintes et sommes linéaires qui raisonnent sur les ensembles de réponses de requêtes de bases de données sous forme conjonctive. Nous décrivons ensuite la sémantique naturelle du langage en montrant comment de tels modèles peuvent être interprétés, en conjonction avec une base de données, en de vrais programmes linéaires qui peuvent ensuite être résolus par tout solveur de programmes linéaires standard et nous discutons de la difficulté de résoudre les modèles LP(CQ). Motivés par la difficulté de résoudre les modèles LP(CQ) en général, nous introduisons ensuite un processus basé sur ce que nous appelons l'interprétation T-factorisée pour résoudre de tels modèles plus efficacement. Cette approche est basée sur des techniques classiques en théorie des bases de données pour exploiter la structure des requêtes en utilisant des décompositions arborescentes de petite largeur. L'interprétation T-factorisée produit un programme linéaire qui a la même valeur optimale que la sémantique naturelle du modèle mais moins de variables et qui peut donc être utilisé pour résoudre le modèle plus efficacement. La troisième contribution est une généralisation du résultat précédent au cadre des bases de données factorisées. Nous introduisons une structure de données spécifique pour coder succinctement les relations sous forme de circuit. Nous définissons ensuite l'interprétation dite C-factorisée qui exploite le caractère succinct de ces circuits pour produire un programme linéaire qui a la même valeur optimale que la sémantique naturelle du modèle mais avec moins de variables de manière similaire à l'interprétation T-factorisée. Enfin, nous montrons que nous pouvons explicitement compiler les ensembles de réponses de requêtes conjonctives admettant une décomposition de petite largeur en circuits succincts, ce qui nous permet de recapturer l'interprétation T-factorisée.

Jury

Mme Sophie TISON Université de Lille Directrice de thèse M. Pierre SENELLART Ecole Normale Supérieure Rapporteur M. Bruno ZANUTTNI Université de Caen Normandie, France Rapporteur M. Joachim NIEHREN Inria Lille Nord Europe Co-directeur de thèse M. Pierre MARQUIS Université d'Artois Examinateur Mme Luce BROTCORNE INRIA Lille Nord Europe Examinatrice M. Florent CAPELLI Université de Lille Invité M. Jan RAMON Inria Lille Nord Europe Invité

Thesis of the team LINKS defended on 28/02/2023