Index de BDD sur la base d'une relation quelconque

Titi le curieux

Bonjour,

  Je ne sais pas si la question est vraiment à sa place en combinatoire et graphes, mais je n'ai rien trouvé de plus pertinent.

   Supposons une base de données. On doit souvent faire des recherches sur la base d'une jointure concernant un champ qu'on va retrouver dans une ou plusieurs tables.

  Les jointures en questions ne sont pas basées sur une stricte égalité entre champ mais sur une relation $\mathcal{R}$ qui a été définie préalablement et est reconnue par le gestionnaire de base de données (on y fait textuellement appel dans les requêtes).

  On nommera $V$ l'ensemble des valeurs prises par ce champ, $E$ l'ensemble des "edges" (l'ensemble des couples $(x,y)\in V^2$ tels que $x\mathcal{R}y$).

  Ma question est donc: dans ce genre de cas, à quoi pourraient ressembler l'équivalent d'un index fait pour optimiser les requêtes faisant appel à des jointures par $\mathcal{R}$ ?

  Je suppose que des cas concret se sont régulièrement posés et qu'il existe des travaux et des cours traitant de la question, mais je ne sais pas où chercher.

  Cela dit, j'ai un peu d'imagination, et si je ne pense pas qu'il existe un truc qui est efficace tout le temps: voilà deux approches  trois-quart que j'adopterais dans certains cas:

 -Facile à coder: l'équivalent d'une table de jointure représentant $E$ (avec ses propres index, on fera l'hypothèse qu'il existe aussi une structure d'ordre totale sur $V$). Le problème cette approche apparaît si $E$ est démentiellement grand.

 -Le treillis: Si la relation reste une relation d'ordre et qu'elle n'est pas trop moche on pourra ajouter des éléments à $V$ (et à $E$) de manière à en faire un beau treillis. Intuitivement, créer un index efficicace sur la base d'un treillis doit rester sympa.

- Le treillis bis: Pour les relations qui ne sont pas des relationsnt d'ordre mais qui reste transitives et réflexives:  on recommence le coup du treillis mais sur les classes d'équivalence $V'$ (un élément de $V'$ est une partie de $V$ dont tout les paires d'élémnts $(x,y)$ vérifient $x\mathcal{R}y \wedge y\mathcal{R}x$ ). Ça demande quand même d'avoir de quoi comparer les éléments de $V$ et $V'$, parfois il y a une fonction simple, mais parfois il faudra faire une table fonctionnelle de $V$ vers $V'$.

- Le treillis "si ç'est utile, c'est vraiment un coup de bol!": Pour un cas un peu plus général, on prend la clôture transitive et réflexive de la relation puis on relance le treillis bis (j'étais très fier de cette idée de treillis et j'ai voulu l'user jusqu'à la corde).

Merci d'avance pour toute réponse

Edit: J'ai publié trop vite par accident, du coup au tout début le message était incomplet, ce qui en donnait une lecture désagréable. J'espère qu'il n'y a pas eu de victime.

Médiat_Suprème

Votre problème est-il d'améliorer les moteurs de BDD ou de faire une requête ?
Dans le deuxième cas, créer une vue (éventuellement matérialisée) et un index sur cette vue.

Titi le curieux

Bonjour,

  Merci pour la réponse, je n'ai pas de problème concret là dessus à ce jour. La question est purement théorique (donc disons que l'idée est d'améliorer le moteur), comment devrait fonctionner un index optimisé pour faire des recherches avec une relation autre qu'une relation d'ordre totale.

  Je crois que la solution que vous proposez pour le cas concret est équivalente à celle que j'avais nommé la "facile à coder", la table de jointure étant une vue (matérialisée en effet) sur la relation.