27.1.1 All Nodes in the Graph

CREATE VIEW Graph_Nodes (node_id)
AS
SELECT DISTINCT node_id FROM Nested_Sets_Graph;

27.1.2 Path Endpoints

A path through a graph is a traversal of consecutive nodes along a sequence of edges. Clearly, the node at the end of one edge in the sequence must also be the node at the beginning of the next edge in the sequence. The length of the path is the number of edges that are traversed along the path.

Path endpoints are the first and last nodes of each path in the graph. For a path of length zero, the path endpoints are the same node. If there is more than one path between two nodes, then each path will be distinguished by its own distinct set of number pairs for the nested-set representation.

If there is only one path p between two nodes but this path is a sub-path of more than one distinct path, then the endpoints of p will have number pairs for each of these greater paths. As a canonical form, the least numbered pairs are returned for these endpoints.

CREATE VIEW Path_End_Points
(begin_node_id, end_node_id,
 begin_lft, begin_rgt,
 end_lft, end_rgt)
AS
SELECT G1.node_id, G2.node_id,
G1.lft, G1.rgt, G2.lft, G2.rgt
 FROM (SELECT node_id, MIN(lft), MIN(rgt)
FROM Nested_Sets_Graph
 GROUP BY node_id) AS G1 (node_id, lft, rgt)
INNER JOIN
Nested_Sets_Graph AS G2
ON G2.lft >= G1.lft
AND G2.lft < G1.rgt;

27.1.3 Reachable Nodes

If a node is reachable from another node, then a path exists from one node to the other. It is assumed that every node is reachable from itself.

CREATE VIEW Reachable_Nodes (begin_node_id, end_node_id)
AS
SELECT DISTINCT begin_node_id, end_node_id
 FROM Path_End_Points;

27.1.4 Edges

Edges are pairs of adjacent connected nodes in the graph. If edge E is represented by the pair of nodes (n0, n1), then (n1) is reachable from (n0) in a single traversal.

CREATE VIEW Edges (begin_node_id, end_node_id)
AS
SELECT begin_node_id, end_node_id
 FROM Path_Endpoints AS PE
 WHERE begin_node_id <> end_node_id
AND NOT EXISTS
(SELECT *
FROM Nested_Sets_Graph AS G
 WHERE G.lft > PE.begin_lft
AND G.lft < PE.end_lft
AND G.rgt > PE.end_rgt);

27.1.5 Indegree and Outdegree

The indegree of a node n is the number of distinct edges ending at n. Nodes that have 0 indegree are not returned. Indegree of all nodes in the graph:

CREATE VIEW Indegree (node_id, node_indegree)
AS
SELECT N.node_id, COUNT(E.begin_node_id)
 FROM Graph_Nodes AS N
LEFT OUTER JOIN
Edges AS E
ON N.node_id = E.end_node_id
 GROUP BY N.node_id;

Outdegree of a node (n) is the number of distinct edges beginning at (n). Nodes that have zero outdegree are not returned. Outdegree of all nodes in the graph:

CREATE VIEW Outdegree (node_id, node_outdegree)
AS
SELECT N.node_id, COUNT(E.end_node_id)
 FROM Graph_Nodes AS N
LEFT OUTER JOIN
Edges AS E
ON N.node_id = E.begin_node_id
 GROUP BY N.node_id;

27.1.6 Source, Sink, Isolated, and Internal Nodes

A source node of a graph has a positive outdegree but 0 indegree, that is, it has edges leading from, but not to, the node. This assumes there are no isolated nodes (nodes belonging to no edges).

CREATE VIEW Source_Nodes (node_id, lft, rgt)
AS
SELECT node_id, lft, rgt
 FROM Nested_Sets_Graph AS G1
 WHERE NOT EXISTS
(SELECT *
FROM Nested_Sets_Graph AS G
 WHERE G1.lft > G2.lft
AND G1.lft < G2.rgt);

Likewise, a sink node of a graph has positive indegree but 0 outdegree. It has edges leading to, but not from, the node. This assumes there are no isolated nodes.

CREATE VIEW Sink_Nodes (node_id)
AS
SELECT node_id
 FROM Nested_Sets_Graph AS G1
 WHERE lft = rgt - 1
AND NOT EXISTS
 (SELECT *
 FROM Nested_Sets_Graph AS G2
WHERE G1.node_id = G2.node_id
AND G2.lft < G1.lft);

An isolated node belongs to no edges, i.e., it has zero indegree and zero outdegree.

CREATE VIEW Isolated_Nodes (node_id, lft, rgt)
AS
SELECT node_id, lft, rgt
 FROM Nested_Sets_Graph AS G1
 WHERE lft = rgt - 1
AND NOT EXISTS
(SELECT *
FROM Nested_Sets_Graph AS G2
 WHERE G1.lft > G2.lft
 AND G1.lft < G2.rgt);

An internal node of a graph has an (indegree > 0) and an (outdegree > fPa0), that is, it acts as both a source and a sink.

CREATE VIEW Internal_Nodes (node_id)
AS
SELECT node_id
 FROM (SELECT node_id, MIN(lft) AS lft, MIN(rgt) AS rgt
FROM Nested_Sets_Graph
 WHERE lft < rgt - 1
GROUP BY node_id) AS G1
 WHERE EXISTS
(SELECT *
 FROM Nested_Sets_Graph AS G2
WHERE G1.lft > G2.lft
AND G1.lft < G2.rgt)

27.2.1 Length of Paths

The length of a path is the number of edges that are traversed along the path. A path of N nodes has a length of (N − 1).

CREATE VIEW Path_Lengths
(begin_node_id, end_node_id,
path_length,
begin_lft, begin_rgt,
end_lft, end_rgt)
AS
SELECT begin_node_id, end_node_id, MAX(seq_nbr),
 begin_lft, begin_rgt, end_lft, end_rgt
FROM Paths
GROUP BY begin_lft, end_lft, begin_rgt, end_rgt,
 begin_node_id, end_node_id;

27.2.2 Shortest Path

This gives the shortest path length between all nodes, but it does not tell you what the actual path is. There are other queries that use the new CTE feature and recursion which we will discuss in Section 27.3.

CREATE VIEW Shortest_Path_Lengths
(begin_node_id, end_node_id, path_length,
begin_lft, begin_rgt, end_lft, end_rgt)
AS
SELECT PL.begin_node_id, PL.end_node_id,
 PL.path_length,
 PL.begin_lft, PL.begin_rgt,
 PL.end_lft, PL.end_rgt
FROM (SELECT begin_node_id, end_node_id,
 MIN(path_length) AS path_length
FROM PathLengths
 GROUP BY begin_node_id, end_node_id) AS MPL
 INNER JOIN
 PathLengths AS PL
 ON MPL.begin_node_id = PL.begin_node_id
AND MPL.end_node_id = PL.end_node_id
AND MPL.path_length = PL.path_length;

27.2.3 Paths by Iteration

First let’s build a graph with a cost associated with each edge and put it into an adjacency list model.

INSERT INTO Edges (out_node, in_node, cost)
VALUES ('A', 'B', 50),
('A', 'C', 30),
('A', 'D', 100),
('A', 'E', 10),
('C', 'B', 5),
('D', 'B', 20),
('D', 'C', 50),
('E', 'D', 10);

To find the shortest paths from one node to those that it can reach, we can write this recursive VIEW.

CREATE VIEW Shortest_Paths (out_node, in_node, path_length)
AS
WITH RECURSIVE Paths (out_node, in_node, path_length)
AS
(SELECT out_node, in_node, 1
 FROM Edges
UNION ALL
SELECT E1.out_node, P1.in_node, P1.path_length + 1
 FROM Edges AS E1, Paths AS P1
WHERE E1.in_node = P1.out_node)
SELECT out_node, in_node, MIN(path_length)
FROM Paths
GROUP BY out_node, in_node;

To find the shortest paths without recursion, stay in a loop and add one edge at a time to the set of paths defined so far.

CREATE PROCEDURE Iterate_Paths()
LANGUAGE SQL
MODIFIES SQL DATA
BEGIN
DECLARE old_path_tally INTEGER;
SET old_path_tally = 0;
DELETE FROM Paths; -- clean out working table
INSERT INTO Paths
SELECT out_node, in_node, 1
FROM Edges; -- load the edges
-- add one edge to each path
WHILE old_path_tally < (SELECT COUNT(*) FROM Paths)
DO SET old_path_tally = (SELECT COUNT(*) FROM Paths);
 INSERT INTO Paths (out_node, in_node, lgth)
 SELECT E1.out_node, P1.in_node, (1 + P1.lgth)
 FROM Edges AS E1, Paths AS P1
WHERE E1.in_node = P1.out_node
AND NOT EXISTS -- path is not here already
(SELECT *
 FROM Paths AS P2
WHERE E1.out_node = P2.out_node
AND P1.in_node = P2.in_node);
END WHILE;
END;

The Least Cost Path is basically the same algorithm, but instead of a constant of one for the path length, we use the actual costs of the edges.

CREATE PROCEDURE Iterate_Cheap_Paths ()
LANGUAGE SQL
MODIFIES SQL DATA
BEGIN
DECLARE old_path_cost INTEGER;
SET old_path_cost = 0;
DELETE FROM Paths; -- clean out working table
INSERT INTO Paths
SELECT out_node, in_node, cost
FROM Edges; -- load the edges
-- add one edge to each path
WHILE old_path_cost < (SELECT COUNT(*) FROM Paths)
DO SET old_path_cost = (SELECT COUNT(*) FROM Paths);
 INSERT INTO Paths (out_node, in_node, cost)
 SELECT E1.out_node, P1.in_node, (E1.cost + P1.cost)
 FROM Edges AS E1
INNER JOIN
(SELECT out_node, in_node, MIN(cost)
FROM Paths
 GROUP BY out_node, in_node)
AS P1 (out_node, in_node, cost)
ON E1.in_node = P1.out_node
 AND NOT EXISTS
 (SELECT *
FROM Paths AS P2
 WHERE E1.out_node = P2.out_node
 AND P1.in_node = P2.in_node
 AND P2.cost <= E1.cost + P1.cost);
END WHILE;
END;

27.2.4 Listing the Paths

I got data for this table from the book Introduction to Algorithms by Cormen, Leiserson, and Rivest (ISBN 0-262-03141-8), page 518. This book was very popular in college courses in the United States. I made one decision that will be important later; I added self-traversal edges (i.e., the node is both the out_node and the in_node of an edge) with weights of zero.

INSERT INTO Edges
VALUES ('s', 's', 0);
INSERT INTO Edges
VALUES ('s', 'u', 3),
('s', 'x', 5),
('u', 'u', 0),
('u', 'v', 6),
('u', 'x', 2),
('v', 'v', 0),
('v', 'y', 2),
('x', 'u', 1),
('x', 'v', 4),
('x', 'x', 0),
('x', 'y', 6),
('y', 's', 3),
('y', 'v', 7),
('y', 'y', 0);

I am not happy about this approach, because I have to decide the maximum number of edges in path before I start looking for an answer. But this will work and I know that a path will have no more than the total number of nodes in the graph. Let’s create a table to hold the paths:

CREATE TABLE Paths
(step1 CHAR(2) NOT NULL,
step2 CHAR(2) NOT NULL,
step3 CHAR(2) NOT NULL,
step4 CHAR(2) NOT NULL,
step5 CHAR(2) NOT NULL,
total_cost INTEGER NOT NULL,
path_length INTEGER NOT NULL,
PRIMARY KEY (step1, step2, step3, step4, step5));

The “step1” node is where I begin the path. The other columns are the second step, third step, fourth step, and so forth. The last step column is the end of the journey. The “total_cost” column is the total cost, based on the sum of the weights of the edges, on this path. The path length column is harder to explain, but for now, let’s just say that it is a count of the nodes visited in the path.

To keep things easier, let’s look at all the paths from ‘s’ to ‘y’ in the graph. The INSERT INTO statement for constructing that set looks likes this:

INSERT INTO Paths
SELECT G1.out_node, -- it is 's' in this example
 G2.out_node,
 G3.out_node, G4.out_node,
 G4.in_node, -- it is 'y' in this example
 (G1.cost + G2.cost + G3.cost + G4.cost),
 (CASE WHEN G1.out_node NOT IN (G2.out_node,  G3.out_node, G4.out_node) THEN 1 ELSE 0 END
+ CASE WHEN G2.out_node NOT IN (G1.out_node,  G3.out_node, G4.out_node) THEN 1 ELSE 0 END
+ CASE WHEN G3.out_node NOT IN (G1.out_node,  G2.out_node, G4.out_node) THEN 1 ELSE 0 END 
+ CASE WHEN G4.out_node NOT IN (G1.out_node,  G2.out_node, G3.out_node) THEN 1 ELSE 0 END)
FROM Edges AS G1,
 Edges AS G2, 
 Edges AS G3, 
 Edges AS G4 
WHERE G1.out_node = 's'
 AND G1.in_node = G2.out_node
 AND G2.in_node = G3.out_node
 AND G3.in_node = G4.out_node
 AND G4.in_node = 'y';

I put in ‘s’ and ‘y’ as the out_node and in_node of the path and made sure that the in_node of each step in the path was the out_node of the next step in the path. This is a combinatorial explosion, but it is easy to read and understand.

The sum of the weights is the cost of the path, which is easy to understand. The path_length calculation is a bit harder. This sum of CASE expressions looks at each node in the path. If it is unique within the row, it is assigned a value of one, if it is not unique within the row, it is assigned a value of zero.

All paths will have five steps in them because the way to table is declared. But what if a path exists between the two nodes which is shorter than five steps? That is where the self-traversal rows are used. Consecutive pairs of steps in the same row can be repetitions of the same node.

Here is what the rows of the Paths table look like after this INSERT INTO statement, ordered by descending path_length, and then by ascending cost.

Clearly, all pairs of nodes could be picked from the original Edges table and the same INSERT INTO run on them with a minor change in the WHERE clause. However, this example is big enough for a short magazine article. And it is too big for most applications. It is safe to assume that people really want the cheapest path. In this example, the total_cost column defines the cost of a path, so we can eliminate some of the paths from the Paths table with this statement.

DELETE FROM Paths
WHERE total_cost
 > (SELECT MIN(total_cost)
FROM Paths);

Again, if you had all the paths for all possible pairs of nodes, the subquery expression would have a WHERE clause to correlate it to the subset of paths for each possible pair.

In this example, it got rid of 3 out of 22 possible paths. It is helpful and in some situations we might like having all the options. But these are not distinct options.

As one of many examples, the paths

(s, x, v, v, y, 11, 2)

and

(s, x, x, v, y, 11, 2)

are both really the same path, (s, x, v, y). Before we decide to write a statement to handle these equivalent rows, let’s consider another cost factor. People do not like to change airplanes or trains. If they can go from Amsterdam to New York City on one plane without changing planes for the same cost, they are happy. This is where that path_length column comes in. It is a quick way to remove the paths that have more edges than they need to get the job done.

DELETE FROM Paths
WHERE path_length
 > (SELECT MIN(path_length)
FROM Paths);

In this case, that last DELETE FROM statement will reduce the table to one row: (s, s, x, x, y, 11, 0) which reduces to (s, x, y). This single remaining row is very convenient for my article, but if you look at the table, you will see that there was also a subset of equivalent rows that had higher path_length numbers.

(s, s, s, x, y, 11, 1)

(s, x, x, x, y, 11, 1)

(s, x, x, y, y, 11, 2)

(s, x, y, y, y, 11, 2)

Your task is to write code to handle equivalent rows. Hint: the duplicate nodes will always be contiguous across the row.

27.6.1 Taxi Versus Euclidean Distance

Let’s invent some notations that we can turn into programs. Use uppercase letters for point (hotel) names:

A = (x1, y1), B = (x2, y2)

De (A, B) = Euclidean Distance = d = √((x1 − x2)² + (y1 − y2)²)

Dt (A, B) = Taxicab Distance = (|x1 − x2| + |y1 − y2|).

You might want to convince yourself that

Dt (A, A) = 0

Dt (A, B) = Dt (B, A)

Unlike Euclidean geometry, there is more than one shortest path between two points. It is a combinatorial problem, with the formula N = r!/(n!(r − n)!). The idea is that if you need to travel (i) blocks North and (j) blocks East, then any permutation of (i) blocks North and (j) blocks East will get you to your destination.

27.6.2 Taxi Shapes

The definition of a circle in Taxicab geometry is that all points (hotels) in the set are the same distance from the center. Just like a Euclidean circle, but with a finite number of points.

Circle = {X: Dt (X, P) = k}, k is the radius and P is the center

When you look at diagram, you will see a diamond shape. Remember the definition of π? The ratio of the circumference to the radius of a circle. This gives us a value of 4 for taxi-π.

Triangles and other polygons are defined by replacing Euclidean Distance with Taxicab Distance. But the results are not as pretty as the circle. Congruent triangles are hard to find; you cannot use the simple side and angle rules. Rectangles and other polygons are not visually obvious.

But one of the interesting tools is Pick’s Theorem. Given a general polygon, you can find the area by Pick’s formula,

A = i + b/2 − 1, where A = area, i = the number of interior points, b = number of boundary points (Figure 27.3).

The math is much simpler than a Euclidean model, which would involve trigonometry.

27.7.1 Graph for Equivalence Relations

As we have seen, the idiom for graphs in SQL is to use a table with the nodes involved and a second table with pairs of nodes (a, b) to model the edges, which model our ~ relation. The bad news is that when you use it for equivalence relations, it can get big. A class with one member is has one row to show the edge back to itself. A class with two members {a, b} has {(a, a), (b, b), (a, b), (b, a)} to show the ~ properties as edges. Three members give us six rows: {(a, a), (b, b), (c, c), (a, b), (a, c), (b, a), (b, c), (c, a), (c, b)}. The general formula is (n * (n − 1)) + n, which is pretty close to (n!).

First, load the table a few facts we might already know:

CREATE TABLE Friends
(lft_member VARCHAR(20) NOT NULL,
rgt_member VARCHAR(20) NOT NULL,
PRIMARY KEY (lft_member, rgt_member))
INSERT INTO Friends (lft_member, rgt_member)
VALUES
('John', 'Mary'),
('Mary', 'Jessica'),
('Peter', 'Albert'),
('Peter', 'Nancy'),
('Abby', 'Abby'),
('Jessica', 'Fred'),
('Joe', 'Frank'),

27.7.2 Reflexive Rows

The first thing we noticed is that only Abby has a reflexive property row. We need to add those rows and can do this with basic set operators. Bu it is not that easy, as you can see with this insertion statement:

INSERT INTO Friends
SELECT X.lft_member, X.rgt_member
FROM
((SELECT lft_member, lft_member FROM Friends AS F1
UNION
SELECT rgt_member, rgt_member FROM Friends AS F2)
EXCEPT
SELECT lft_member, rgt_member FROM Friends AS F3)
AS X (lft_member, rgt_member);

The use of table aliases is tricky. You have to be sure that the SQL engine will construct a table in such a way that you do not get scoping problems. The UNION and EXCEPT operators are used to assure that we do not have primary key violations.

27.7.3 Symmetric Rows

Look at the update table and there are no {(a, b), (b, a)} pairs. We need to add this second property to the relation table. This follows the pattern of set operators we just used:

INSERT INTO Friends
SELECT X.lft_member, X.rgt_member
FROM
(
(SELECT F1.rgt_member, F1.lft_member
FROM Friends AS F1
WHERE F1.lft_member <> F1.rgt_member)
EXCEPT
(SELECT F2.lft_member, F2.rgt_member FROM Friends AS F2)
) AS X (lft_member, rgt_member);

This will give us:

If you do quick GROUP BY query, you see that Abby is seriously antisocial with a count of 1, but Mary and Jessica look very social with a count of 3. This is not quite true because the property could be the dreaded “Rock-paper-scissors-lizard-Spock” relationship. But this is what we are using.

27.7.4 Transitive Rows

Transitivity goes on forever. Well, until we have what mathematicians call a closure. This means we have gotten a set of elements that have all of the valid relationships. In some cases, these sets are infinite. But in database, we can only have insanely large tables. Let’s pull a subset that is part of a clique of four friends.

Now apply the transitive relation to get some of the missing edges of a graph:

INSERT INTO Friends
SELECT X.lft_member, X.rgt_member
FROM
((SELECT F1.lft_member, F2.rgt_member
FROM Friends AS F1, Friends AS F2
WHERE F1.rgt_member = F2.lft_member)
EXCEPT
(SELECT F3.lft_member, F3.rgt_member FROM Friends AS F3)
) AS X (lft_member, rgt_member);

This is a simple statement using the definition of transitivity, without a universal quantifier or loop on it. It will add these rows to this subset:

When you look at Mary and Jessica have all of their friends. However, Fred and John do not know that they are friends. So we invoke the statement again and get those two rows. If you try it for a third time, there are zero rows added.

The first thought is this sounds like a job for a recursive statement. But it is not that easy. If the original graph has a cycle in it, you can hang in an infinite loop if you try to use a recursive CTE. The assumption is that each clique has a spanning graph in the pairs in. Oops! New term: a spanning graph is a subgraph that includes the nodes and some or all of the edges of the graph. A complete graph is the spanning graph has all the possible edges, so each node is directly connected to any other node.

27.7.5 Cliques

Now change your mindset from graphs to sets. Let’s look at the size of the cliques:

WITH X (member, clique_size)
AS
(SELECT lft_member, COUNT(*) FROM Friends GROUP BY lft_member)
SELECT * FROM X ORDER BY clique_size;

What we want to do it is assign a number to each clique. This sample data is biased by the fact that the cliques are all of different sizes. You cannot simply use the size to assign a clique_nbr.

Create this table and load it with the names.

CREATE TABLE Cliques
(clique_member VARCHAR(20) NOT NULL PRIMARY KEY,
clique_nbr INTEGER);

We can start by assigning everyone their own clique, using whatever your favorite method is:

INSERT INTO Cliques
VALUES
('Abby', 1),
('Frank', 2),
('Joe', 3),
('Nancy', 4),
('Peter', 5),
('Albert', 6),
('Fred', 7),
('Jessica', 8),
('John', 9),
('Mary', 10);

Everyone is equally a member of their clique in this model. That means we could start with anyone to get the rest of their clique. The update is very straight forward. Take any clique number, find the member to whom it belongs and use that name to build that clique. But which number to we use? We could use the MIN, MAX, or a random number in the clique; I will use the MAX for no particular reason.

I keep thinking that there is a recursive update statement that will do this in one statement. But I know it will not port (Standard SQL has no recursive update statement right now. We would do it with SQL/PSM or a host language) and I think it would be expensive. Recursion will happen for each member of the whole set, but if we consolidate a clique for one person, we have removed his friends from consideration.

The worst situation would be a bunch of hermits, so the number of clique would be the cardinality of set. That is not likely or useful in the real world. Let’s put the update in the body of a loop.

BEGIN
DECLARE clique_loop INTEGER;
DECLARE node CHAR(10);
SET clique_loop = (SELECT MAX(clique_nbr) FROM Cliques);
WHILE clique_loop > 0
DO
SET node
= (SELECT clique_member
FROM Cliques
 WHERE clique_nbr = clique_loop);
UPDATE Cliques
 SET clique_nbr
 = (SELECT clique_nbr
FROM Cliques
 WHERE clique_member = node)
WHERE clique_member
IN (SELECT rgt_member
FROM Friends
 WHERE lft_member = mode);
SET clique_loop = clique_loop - 1;
END WHILE;
END;

As a programming assignment, replace the simple counting loop with one that does not do updates with clique_loop values that were removed in the prior iteration. This can save a lot of work in a larger social network than the sample data used here.

27.7.6 Adding Members

Now that we have a Cliques table, we can do a simple insertion if the new guy belongs to one clique. However, we can have someone who knows a people in different cliques. This will merge the two cliques into one.

CREATE PROCEDURE Clique_Merge
(IN clique_member_1 CHAR(10),
IN clique_member_2 CHAR(10))
UPDATE Cliques
SET clique_nbr
 =(SELECT MAX(clique_nbr)
 FROM Cliques
WHERE clique_member
IN (clique_member_1, clique_member_2))
WHERE clique_nbr
 =(SELECT MIN (clique_nbr)
 FROM Cliques
WHERE clique_member
IN (clique_member_1, clique_member_2));

Deleting a member or moving him to another clique is trivial.