Algorithms and complexity of enumeration problems for the evaluation of logical queries
| Autor: | Bagan, Guillaume |
|---|---|
| Přispěvatelé: | Bagan, Guillaume |
| Jazyk: | francouzština |
| Rok vydání: | 2009 |
| Předmět: |
base de données
hypergraphe computational complexity algorithm conjunctive query hypergraph model-checking largeur arborescente logical query complexité algorithmique largeur de clique unit interval graph [INFO.INFO-OH] Computer Science [cs]/Other [cs.OH] linear time énumération cliquewidth treewidth délai constant requête logique requête conjonctive graphe d'intervalles unitaires constant delay database algorithme temps linéaire |
| Popis: | This thesis is dedicated to the evaluation of logical queries from the enumeration point of view. First, we deal with acyclic conjunctive formulas with inequalities; we show that such a query can be evaluated with linear delay in the size of the structure: this improves a result by Papadimitriou and Yannakakis. Then, we exhibit a subclass of acyclic formulas, so-called connex-acyclic formulas. Such queries can be evaluated with constant delay after some linear time preprocessing. We show that this result is maximal in the following sense: if the product of boolean matrices cannot be computed in linear time then any acyclic query is computable with constant delay after some linear time preprocessing if and only if it is connex-acyclic. Second, we prove that any MSO query over a class of bounded treewidth structures can be evaluated with a linear delay in the size of each solution after some linear preprocessing in the size of the structure. Third, we show that for each first-order query over bounded degree structures, one can compute the j-th solution of the query in constant time after some linear time preprocessing. Finally, we prove that unit interval graphs are of bounded local cliquewidth. Hence we deduce that any first-order statement over these graphs is decidable in linear time; Also, we show that this result is somehow maximal. Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|