How to model a Bayesian network or, more generally, a directed weighted graph, in SQL?

Question

Hi,

I found a few articles online providing examples of how to model graphs of various kinds (DAGs, in particular) in SQL, but they all seemed enormously complex, given the relative simplicity of what they're modeling.

Is there a best / standard way of doing this? My current thinking is something like this:

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
)

Is there anything wrong with that? Anyone know of a better (more robust, perhaps) way?

Thanks,

Ben

Answer 1

This would be quite a reasonable approach. SQL does not really do recursive structures well, although some systems such as Oracle or SQL Server have a recursive query function.

Although you may find a structure that works better for specific search types I don't think you will find an appreciably better structure in the general case. If your application's requirements are limited in this way, such an optimisation may bring you benefit.

As a bayesian network is a Directed Acyclic Graph (DAG), a purely recursive parent-child relationship is not sufficient to model the network (i.e. a node can have more than one parent), so a M:M relationship of the type you've described is going to be necessary.

Various of the 'SQL for Smarties' books by Joe Celko give a good overview of techniques for implementing and querying hierarchical and graph structures in SQL. These are by far the best resource on the subject that I know of. Highly recommended.

Answer 2

Joe Celko's books are excellent.