Ionona Ranaivoson (GREYC, Caen)

Les requêtes conjonctives permettent d’exprimer la plupart des requêtes en pratique des base de données relationnelles et des problèmes CSP. Mais l’évaluation d’une requête conjonctive rq (le calcul du résultat rq ( DB ) de l’application de rq à une base de données DB ) est en général NP- difficile.

Quand rq est acyclique, i.e. son hypergraphe associé H ( rq ) est acyclique (les hyperarêtes de H ( rq ) sont les atomes de rq ), l’évaluation de rq ( DB ) est polynomiale [Yannakakis]. En particulier, le test de la satisfaisabilité de rq (tester si rq ( DB ) est non vide) se fait en tems linéaire O (| DB |), où | DB |, la taille de DB , “mesure” le nombre de lignes dans DB. L’évaluation de rq ( DB ) utilise un arbre de jointure T de H , dont chaque nœud correspond à une hyperarête de H et qui est calculable en temps O (| H |) quand H est acyclique.

Quand rq n’est pas acyclique, on essaie de ramener l’évaluation de rq au cas acyclique en utilisant comme “arbre de jointure” le résultat d’une décomposition arborescente T de H.

Dans une DA “standard” T de H (c’est une DA du graphe primal de H ), les nœuds de T peuvent regrouper plusieurs hyperarêtes de H. Si tw ( T )= k , i.e., chaque nœud de T contient au plus ( k +1) sommets de H , alors T permet de tester la satisfaisabilité de rq en O (|dom( DB )| k +1), où |dom( DB )| est la taille (cardinalité) du domaine de DB. En particulier, chaque hyperarête de H est incluse dans au moins un nœud de T.

Dans une DA croisée, chaque hyperarête de H est incluse dans un seul nœud ou dans la réunion de deux nœuds adjacents de T au moins. Si les nœuds de T contiennent au plus k sommets de H alors on définit la largeur arborescente croisée de T à ctw ( T )= k.

Le problème de l’évaluation de rq quand ctw ( H ( rq ))= k est alors posée, ainsi que le problème de test si ctw ( H ) = k pour un hypergraphe ou graphe quelconque H.

Si ctw ( H ( rq ))=2, alors tester la satisfaisabilité de rq se fait en O (| DB |2).

Nous exhiberons une requête rq tq tw ( H ( rq ))=3 et ctw ( H ( rq ))=2. Et donc dont une DA non croisée donne un test de satisfaisabilité en O (|Dom( DB )|4) et une DA croisée un test en O (|DB|2).

Pour terminer, nous donnons un algorithme qui teste si ctw ( G )=2 pour un graphe quelconque et qui construit une DA croisée de G à partir d’une décomposition en trous de G.

Décomposition en trous d’un graphe: Appelons “trou” (hole) un cycle sans corde de G. Nous construisons, pour tout graphe biconnexe G , un ensemble de trous de G tel que:

  1. toute arête de G appartient à un trou
  2. l’intersection de deux trous quelconques est connexe (un chemin, qui peut être vide ou réduit à un sommet)
  3. le graphe d’adjacence des trous est connexe (deux trous sont adjacents si leur intersection contient au moins une arête).