I recently ran into the problem of having to store a directed graph in MySQL. Actually, I was trying to efficiently store a thesaurus in SQL so that it both used little space and had high performing lookups. A thesaurus, as you probably know, could best be represented as a graph of some type; perhaps as a tree (in a naive implementation), or a directed acyclic graph, or even a directed multigraph.

SQL, unfortunately, does not readily lend itself to these type of data structures at first glance. With some thought, however, one can readily store a tree or any other graph in SQL. Consider the following example:

This quickly becomes much more complex as we want to attach definitions to words, and some words in the thesaurus may be the same ‘word’, but a differing class of speech, such as a noun, verb, etc.

How to store this in SQL? One possible solution is to build a node list and an adjacency list:

The node list:

The adjacency list:

Extremely fast and efficient lookups can now be done using SQL JOIN, and it is doubtful if the table could be stored in a much more efficient manner. This is not the only possible solution, but a fairly good one for the problem.

I’ve set up a live demonstration of the thesaurus right here:

It contains 83,318 words and phrases, and 1,112,705 cross references for synonyms. Most uncached lookups take place on the order of less than a 1/10th of a second on this busy shared hosting server. Cached queries are virtually instantaneous. And honestly, I’m not a MySQL genius; I would imagine that this could be made even faster.

One Comment on “Storing a Directed Graph in SQL” - Leave your comment below: