sql_tests.md

Test data

CREATE TABLE nodes (
    id SERIAL PRIMARY KEY,
    parent VARCHAR(2) NOT NULL,
    child VARCHAR(2) NOT NULL
);

INSERT INTO nodes (parent, child) VALUES  ('B1', 'C1');
INSERT INTO nodes (parent, child) VALUES  ('B1', 'C2');
INSERT INTO nodes (parent, child) VALUES  ('B1', 'C3');
INSERT INTO nodes (parent, child) VALUES  ('B2', 'C2');
INSERT INTO nodes (parent, child) VALUES  ('B3', 'C2');
INSERT INTO nodes (parent, child) VALUES  ('B3', 'C4');
INSERT INTO nodes (parent, child) VALUES  ('B8', 'C4');

postgres=# SELECT * FROM nodes;
 id | parent | child 
----+--------+-------
  1 | B1     | C1
  2 | B1     | C2
  3 | B1     | C3
  4 | B2     | C2
  5 | B3     | C2
  6 | B3     | C4
  7 | B6     | C8
(7 rows)

Bidirected version of the graph

(2x the number of rows) Where the parent of the child is also the child of the parent

postgres=# SELECT parent, child from nodes UNION SELECT child, parent from nodes;
 parent | child 
--------+-------
 C4     | B3
 C2     | B3
 B3     | C4
 B1     | C2
 B1     | C3
 B1     | C1
 B3     | C2
 C2     | B1
 C3     | B1
 C8     | B6
 B2     | C2
 C1     | B1
 B6     | C8
 C2     | B2
(14 rows)

Our starting / base case

SELECT parent, child FROM nodes where parent = 'B1';

parent | child
--------+-------
 B1     | C1
 B1     | C2
 B1     | C3

Rows that include the nodes connected to 'B1'

(https://www.postgresqltutorial.com/postgresql-recursive-query/)

WITH RECURSIVE included_nodes (parent, child) AS (
    SELECT parent, child FROM bidirected WHERE parent='B1'
    UNION
    SELECT bidirected.parent, bidirected.child FROM bidirected INNER JOIN included_nodes ON bidirected.parent = included_nodes.child
),

bidirected AS (SELECT parent, child from nodes UNION SELECT child, parent FROM nodes)
SELECT * FROM included_nodes;

parent | child 
--------+-------
 B1     | C2
 B1     | C3
 B1     | C1
 C2     | B3
 C2     | B1
 C3     | B1
 C1     | B1
 C2     | B2
 B3     | C4
 B3     | C2
 B2     | C2
 C4     | B3
(12 rows)

The distinct nodes included in the graph

WITH RECURSIVE included_nodes (parent, child) AS (
    SELECT parent, child FROM bidirected WHERE parent='B1'
    UNION
    SELECT bidirected.parent, bidirected.child FROM bidirected INNER JOIN included_nodes ON bidirected.parent = included_nodes.child
),

bidirected AS (SELECT parent, child from nodes UNION SELECT child, parent FROM nodes)
SELECT DISTINCT parent FROM included_nodes;

 parent 
--------
 B3
 C1
 B1
 C2
 C3
 C4
 B2
(7 rows)

Number of distinct nodes

WITH RECURSIVE included_nodes (parent, child) AS (
    SELECT parent, child FROM bidirected WHERE parent='B1'
    UNION
    SELECT bidirected.parent, bidirected.child FROM bidirected INNER JOIN included_nodes ON bidirected.parent = included_nodes.child
),

bidirected AS (SELECT parent, child from nodes UNION SELECT child, parent FROM nodes)
SELECT COUNT(DISTINCT parent) FROM included_nodes;
 count 
-------
     7
(1 row)

MISC

SELECT parent, array_agg(child) as children
FROM nodes where parent = 'B1'
GROUP BY parent;

 parent |  children
--------+------------
 B1     | {C1,C2,C3}

SELECT parent, array_agg(child) as children
FROM nodes GROUP BY parent;

 parent |  children
--------+------------
 B3     | {C2,C4}
 B1     | {C1,C2,C3}
 B2     | {C2}
 

https://learnsql.com/blog/get-to-know-the-power-of-sql-recursive-queries/
https://www.fusionbox.com/blog/detail/graph-algorithms-in-a-database-recursive-ctes-and-topological-sort-with-postgres/620/
https://stackoverflow.com/questions/58081344/sql-recursive-cte-graph-traversal
https://www.postgresql.org/docs/9.1/queries-with.html
https://www.postgresqltutorial.com/postgresql-recursive-query/