Popis: |
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 LPCQ). 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 LPCQ. Motivés par la difficulté de résoudre les modèles LPCQ 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 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 knowledge in 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 LPCQ for short. It is a language to model linear programs with constructs that allow one to express linear constraints and linear sums that reason over the answer sets of database queries in the form of conjunctive queries. We then describe the natural semantics of the language by showing how such models can be interpreted, in conjunction with a database, into actual linear programs that can then be solved by any standard linear program solver and discuss the hardness of solving LPCQ models. Motivated by the hardness of solving $\LPCQ$ models in general, we then introduce a process based on the so-called T-factorized interpretation to solve such models more efficiently. This approach is based on classical techniques from database theory to exploit the structure of the queries using hypertree decompositions of small width. The T-factorized interpretation yields a linear program that has the same optimal value as the natural semantics of the model but fewer variables which 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 circuits to yield a linear program that has the same optimal value as the natural semantics of the model but fewer variables similarly to the T-factorized interpretation. Finally we show that we can explicitly compile the answer sets of conjunctive queries with small fractional hypertreewidth into succinct circuits, thus allowing us to recapture the T-factorized interpretation. |