Moje prvni pokusy s ulozenim a traverzovanim grafu v PgSQL:

Volne inspirovano http://www.postgresql.org/docs/8.4/static/queries-with.html


-- tabulka
CREATE TABLE "graph" (
  "id" serial NOT NULL,
  "link" bigint NOT NULL,
  "data" text NULL
)

-- index
-- CREATE INDEX "graph_4d043073083b7" ON "graph" ("id") -- jeste prozkoumat

-- insert (jednoduchy cyklicky graf)
INSERT INTO "graph" ("id", "link", "data") VALUES
('1', '2', 'test a'),
('2', '4', 'test b'),
('3', '1', 'test c'),
('4', '3', 'test d'),
('7', '1', 'oh hai'),
('1', '7', NULL)

-- ------------------------------------------------------------------

-- Tady je rekurzivni query lehce upravena pro potreby kyberky:
-- (pokud se zaindexuje i "link", muzeme snadnou upravou traverzovat i v protismeru: od childa k rodicovi)

WITH RECURSIVE search_graph(id, link, data, depth, path, cycle) AS (
		SELECT g.id, g.link, g.data, 1, ARRAY[g.id], false
		FROM graph g
		WHERE id = 1  	-- tohle je ID nody ze ktery zaciname
	UNION ALL
		SELECT g.id, g.link, g.data, sg.depth + 1, path || g.id, g.id = ANY(path)
		FROM graph g, search_graph sg
		WHERE g.id = sg.link AND NOT cycle
)

SELECT * FROM search_graph
	WHERE cycle != TRUE 	-- vynechame nodu, ktera zjistila ze cyklime (zbytecne by tam byla znovu)
	AND depth <= 3 		-- hloubku omezime na 3 hrany od startu
	LIMIT 100 		-- celkovy pocet vybranych nod omezime na 100