no way to compare when less than two revisions

Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

@@ Řádek 1: / Řádek 1: @@
+====== PostgreSQL (advanced) ======
+  * http://bytes.com/topic/postgresql/answers/66221-recursing-tree-data-pl-pgsql
+  * http://stackoverflow.com/questions/3440840/postgresql-sql-or-pl-pgsql-query-for-traversing-a-directed-graph-and-returning-al
+  * http://techportal.ibuildings.com/2009/09/07/graphs-in-the-database-sql-meets-social-networks/
+  * http://www.storytotell.org/blog/2009/08/11/postgresql84-recursive-queries.html
+  * http://www.postgresql.org/docs/8.4/static/queries-with.html
+  * http://stackoverflow.com/questions/53108/is-it-possible-to-make-a-recursive-sql-query
+  * http://www.depesz.com/index.php/2008/04/11/my-take-on-trees-in-sql/
+  * http://wiki.postgresql.org/wiki/Getting_list_of_all_children_from_adjacency_tree
+  * http://www.scribd.com/doc/14683319/Trees-and-More-with-PostgreSQL
+===== Graphs =====
+<code sql>
+-- 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)
+</code>
+When working with recursive queries it is important to be sure that the recursive part of the query will eventually return no tuples, or else the query will loop indefinitely. Sometimes, using UNION instead of UNION ALL can accomplish this by discarding rows that duplicate previous output rows. However, often a cycle does not involve output rows that are completely duplicate: it may be necessary to check just one or a few fields to see if the same point has been reached before. The standard method for handling such situations is to compute an array of the already-visited values. For example, consider the following query that searches a table graph using a link field:
+<code sql>
+WITH RECURSIVE search_graph(id, link, data, depth) AS (
+        SELECT g.id, g.link, g.data, 1
+        FROM graph g
+      UNION ALL
+        SELECT g.id, g.link, g.data, sg.depth + 1
+        FROM graph g, search_graph sg
+        WHERE g.id = sg.link
+)
+SELECT * FROM search_graph;
+</code>
+This query will loop if the link relationships contain cycles. Because we require a "depth" output, just changing UNION ALL to UNION would not eliminate the looping. Instead we need to recognize whether we have reached the same row again while following a particular path of links. We add two columns path and cycle to the loop-prone query:
+<code sql>
+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
+	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;
+</code>
+<code sql>
+-- Tady je rekurzivni query lehce upravena pro potreby kyberky:
+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
+</code>
+==== Tree ====
+<code sql>
+CREATE TABLE tree (node INTEGER, parent INTEGER);
+INSERT INTO tree(node,parent) VALUES(1,0);
+INSERT INTO tree(node,parent) VALUES(2,0);
+INSERT INTO tree(node,parent) VALUES(3,1);
+INSERT INTO tree(node,parent) VALUES(4,3);
+INSERT INTO tree(node,parent) VALUES(5,4);
+INSERT INTO tree(node,parent) VALUES(6,2);
+INSERT INTO tree(node,parent) VALUES(7,6);
+INSERT INTO tree(node,parent) VALUES(8,6);
+INSERT INTO tree(node,parent) VALUES(9,2);
+CREATE OR REPLACE FUNCTION getTree(INTEGER, INTEGER) RETURNS SETOF tree AS '
+	DECLARE
+		root ALIAS FOR $1;
+		depth ALIAS FOR $2;
+		tempRow1 tree%ROWTYPE;
+		tempRow2 tree%ROWTYPE;
+	BEGIN
+		-- Using PostgreSQL 7.3.4.
+		-- Docs: http://www.postgresql.org/docs/7.3/static/plpgsql.html
+		-- See chapter 19, especially 19.6
+	FOR tempRow1 IN SELECT node, parent FROM tree WHERE parent = root LOOP
+		RETURN NEXT tempRow1;
+		FOR tempRow2 IN SELECT node, parent FROM
+			getTree(tempRow1.node, depth+1) LOOP
+			RETURN NEXT tempRow2;
+		END LOOP;
+	END LOOP;
+	RETURN;
+	END;
+' LANGUAGE 'plpgsql';
+CREATE OR REPLACE FUNCTION getTree(INTEGER) RETURNS SETOF tree AS '
+DECLARE
+root ALIAS FOR $1;
+tempRow tree%ROWTYPE;
+BEGIN
+FOR tempRow IN SELECT node, parent FROM getTree(root, 0) LOOP
+RETURN NEXT tempRow;
+END LOOP;
+RETURN;
+END;
+' LANGUAGE 'plpgsql';
+SELECT * FROM getTree(0);
+node | parent
+------+--------
+| 0
+| 1
+| 3
+| 4
+| 0
+| 2
+| 6
+| 6
+| 2
+(9 rows)
+SELECT * FROM getTree(1);
+node | parent
+------+--------
+| 1
+| 3
+| 4
+(3 rows)
+SELECT * FROM getTree(2);
+node | parent
+------+--------
+| 2
+| 6
+| 6
+| 2
+(4 rows)
+</code>

SPOJE.NET

Uživatelské nástroje

Nástroje pro tento web

Rozdíly

Nástroje pro stránku