Joe Celko's SQL for Smarties, 3rd Edition

30.5. Adjacency Matrix Model

An adjacency matrix is a square array whose rows are out-nodes and columns are in-nodes of a graph. A one in a cell means that there is edge between the two nodes. Using the graph in Figure 30.1, we would have a array like this:

   A B C D E F G H
  ================
A| 1 1 1 0 0 0 0 0
B| 0 1 0 1 0 0 0 0
C| 0 0 1 1 0 0 1 0
D| 0 0 0 1 1 1 0 0
E| 0 0 0 0 1 0 0 1
F| 0 0 0 0 0 1 0 0
G| 0 0 0 0 0 0 1 1
H| 0 0 0 0 0 0 0 1

Many graph algorithms are based on the adjacency matrix model and can be translated into SQL. Go back to Chapter 25 for details on modeling matrices in SQL; in particular, review Section 25.3.3, which deals with matrix multiplication in SQL. For example, Dijkstra’s algorithm for the shortest distances between ...