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

Question

J'ai trouvé en ligne quelques articles fournissant des exemples de modélisation de graphes de différents types (les DAG, en particulier) en SQL, mais ils semblaient tous extrêmement complexes, compte tenu de la simplicité relative de ce qu'ils modélisent.

Existe-t-il un moyen optimal / standard de procéder? Ma pensée actuelle ressemble à 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
) 

Quelque chose ne va pas avec ça? Quelqu'un connaît-il un meilleur moyen (plus robuste peut-être)?

Answer 1

Ce serait une approche tout à fait raisonnable. SQL ne fait pas vraiment bien les structures récursives, bien que certains systèmes tels que 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 ainsi limitées, une telle optimisation peut vous apporter des avantages.

Un réseau bayésien est un graphe acyclique dirigé (DAG), un parent purement récursif La relation -child n’est pas suffisante pour modéliser le réseau (c’est-à-dire qu'un nœud peut avoir plus d'un parent). Une relation M: M du type que vous avez décrit va donc être nécessaire.

Divers des livres "SQL for Smarties" de Joe Celko donne un bon aperçu des techniques permettant d'implémenter et d'interroger des structures hiérarchiques et graphiques en SQL. Ce sont de loin la meilleure ressource sur le sujet que je connaisse. Fortement recommandé.