Enhancing and solving linear programs with conjunctive queries

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 connaissancesafin 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éairesqui 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éairesqui 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 ensuiteun 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éespour 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 variableset 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 circuitspour produire un programme linéaire qui a la même valeur optimale que la sémantique naturelle du modèle mais avec moins de variablesde 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 largeuren circuits succincts, ce qui nous permet de récapturer l'interprétation T-factorisée.Mathematical optimization and data management are two major fields of computer science that are widely studied by mostly separate communities.However complex optimization problems often depend on large datasets that may be cumbersome to manage,while managing large amounts of data is only useful insofar as one analyzes this data to extract some knowledgein order to solve some practical problem, so these fields are often actually intertwined in practice.This thesis places itself at the crossroads between these two fields by studying linear programs that reason about the answers of database queries.The first contribution of this thesis is the definition of the so-called language of linear programs with conjunctive queries, or LP(CQ) for short.It is a language to model linear programs with constructs that allow one to express linear constraints and linear sumsthat reason over the answer sets of database queries in the form of conjunctive queries.We then describe the natural semantics of the languageby showing how such models can be interpreted, in conjunction with a database, into actual linear programsthat can then be solved by any standard linear program solver and discuss the hardness of solving LP(CQ) models.Motivated by the hardness of solving LP(CQ) models in general, we then introducea process based on the so-called T-factorized interpretation to solve such models more efficiently.This approach is based on classical techniques from database theoryto exploit the structure of the queries using hypertree decompositions of small width.The T-factorized interpretation yields a linear programthat has the same optimal value as the natural semantics of the model but fewer variableswhich can thus be used to solve the model more efficiently.The third contribution is a generalization of the previous result to the framework of factorized databases.We introduce a specific circuit data-structure to succintly encode relations.We the define the so-called C-factorized interpretation that leverages the succintness of these circuitsto yield a linear program that has the same optimal value as the natural semantics of the model but fewer variablessimilarly to the T-factorized interpretation.Finally we show that we can explicitly compile the answer sets of conjunctive queries with small fractional hypertreewidthinto succinct circuits, thus allowing us to recapture the T-factorized interpretation