recursive_test.sql

DROP TABLE IF EXISTS test_edges;
DROP TABLE IF EXISTS test_nodes;
CREATE TABLE test_nodes(id SERIAL PRIMARY KEY);
CREATE TABLE test_edges(
    a INTEGER REFERENCES test_nodes(id), b INTEGER REFERENCES test_nodes(id));

INSERT INTO test_nodes(id) VALUES (0);


-- Create a graph with 100,000 nodes
DO
$do$
BEGIN
    FOR i IN 1..100000 LOOP
        INSERT INTO test_nodes(id) VALUES (i);
        INSERT INTO test_edges(a, b) VALUES (floor((1 - power(random(),4)) * i), i);
        FOR j IN 1..floor(i / 10000) LOOP
            INSERT INTO test_edges(a, b) VALUES (
                floor(random() * 0.9 * i),
                floor((random() * 0.1 + 0.9) * i));
        END LOOP;
    END LOOP;
END
$do$;

-- Avoid cycles
DELETE FROM test_edges where a >= b;

-- http://www.postgresonline.com/journal/archives/131-Using-Recursive-Common-table-expressions-to-represent-Tree-structures.html
-- DO NOT ATTEMPT THIS WITH 100000 NODES.... YOU'VE BEEN WARNED!
WITH RECURSIVE tree AS (
    SELECT distinct a, b, CAST('(' || a || ',' || b || ')'  AS VARCHAR(1000)) AS fullname
    FROM test_edges
    UNION ALL
    SELECT distinct e.a, e.b,
        CAST('(' || e.a || ',' || e.b || ')' || '<' || t.fullname AS VARCHAR(1000)) AS fullname
    FROM test_edges AS e
        INNER JOIN tree AS t
        ON (e.b = t.a)
    )
    SELECT distinct a, fullname
    FROM tree
    ORDER BY a, fullname
;



-- Limit query to a leaf node e.g. find all trees with a leaf of id=50000
WITH RECURSIVE tree AS (
    SELECT distinct a, b, CAST('(' || a || ',' || b || ')'  AS VARCHAR(1000)) AS fullname
    FROM test_edges WHERE b = 50000
    UNION ALL
    SELECT distinct e.a, e.b,
        CAST('(' || e.a || ',' || e.b || ')' || '<' || t.fullname AS VARCHAR(1000)) AS fullname
    FROM test_edges AS e
        INNER JOIN tree AS t
        ON (e.b = t.a)
    )
    SELECT distinct a, fullname
    FROM tree
    ORDER BY a, fullname
;


-- Similar, with a hack to print out the number of edges in the tree
WITH RECURSIVE tree AS (
    SELECT a, b, CAST('(' || a || ',' || b || ')'  AS VARCHAR(1000)) AS fullname
    FROM test_edges WHERE b = 50000
    UNION
    SELECT e.a, e.b,
        CAST('(' || e.a || ',' || e.b || ')' || '<' || t.fullname AS VARCHAR(1000)) AS fullname
    FROM test_edges AS e
        INNER JOIN tree AS t
        ON (e.b = t.a)
    )
    SELECT length(fullname) - length(replace(fullname, '<', '')) + 1 len,
        fullname
    FROM tree
    ORDER BY len DESC, fullname
;