Comment modéliser un réseau bayésien ou, plus généralement, un graphe orienté, en SQL?

Question

J'ai trouvé quelques articles en ligne fournissant des exemples de modélisation de graphes de différents types (DAG, en particulier) en SQL, mais ils semblaient tous énormément complexes, étant donné la relative simplicité de ce qu'ils modélisent.

Existe-t-il une meilleure façon de procéder? Ma pensée actuelle est quelque chose comme ceci:

create table node (
    id int not null auto_increment, 
    name TEXT 
) 

create table edge (
    from_node int not null, 
    to_node int not null, 
    weight float 
) 

Y at-il quelque chose de mal à cela? Quelqu'un sait-il d'une meilleure façon (plus robuste, peut-être)?

Answer 1

Ce serait une approche assez raisonnable. SQL ne fait pas bien les structures récursives, bien que certains systèmes tels qu'Oracle ou SQL Server aient une fonction de requête récursive.

Bien que vous puissiez trouver une structure qui fonctionne mieux pour des types de recherche spécifiques, je ne pense pas que vous trouverez une structure sensiblement meilleure dans le cas général. Si les exigences de votre application sont limitées de cette manière, une telle optimisation peut vous apporter des avantages. Comme un réseau bayésien est un Directed Acyclic Graph (DAG), une relation parent-enfant purement récursive n'est pas suffisante pour modéliser le réseau (un nœud peut avoir plusieurs parents), donc une relation M: M du type vous avez décrit va être nécessaire.

Divers des livres 'SQL for Smarties' de Joe Celko donnent un bon aperçu des techniques d'implémentation et d'interrogation des structures hiérarchiques et de graphe en SQL. Ce sont de loin la meilleure ressource sur le sujet que je connaisse. Vivement recommandé.