Graph structure, parent search using stored procedure, postgres

Question

I am new to stored procedures. As part of our application, we have a database with one of the tables having child and parent relationships. Given id, we should be able to figure out the final parent id by going through the child parent links in the table.

Input1: 10943, Output 1: 8656

Input2: 5005, Output2: 9151, 9160

Various possibilities

An identifier may have several final parents; an identifier may not have a parent

Any inputs would be appreciated. Thanks in advance.

Answer 1

ANSWER TO THE STRUCTURE OF WOOD:

It all depends on how your data flow , I mean how your children and parents behave on time (inserts, updates) and how big the table can be (hundreds, thousands).

We can summarize the cases of two: a large table (thousands + rows) and a small table (hundreds of rows). In either case, you can use the "result" table to hold the first parent of all children.

LITTLE TABLE

If your table is not large, then its good to put everything in PL. and call PL when you want to materialize the result table.

LARGE TABLE

If your table is large (very large), you will have to use triggers to update the table. " And this " result " should be an Eager Materialized View . For it to work freely and not have to wait minutes for each transaction.

Here is an example of how you could do this in the case of Small Table, if it was large, it would look like it, but you will have to work hard on triggers to make it work fine. This example shows PL in DO format for explanatory purposes only, you can easily change this for PL:

-- YOUR EXAMPLE TABLE, without child with two parents CREATE TEMP TABLE demo (child integer,parent integer); INSERT INTO demo VALUES (10943,6766), (6766,9003), (9003,8656), (5005,6995), (6995,9151), (6996,9160); -- DO, for inline PL DO $$ DECLARE -- Variables, note that for variable asignation its better if you use ':=' fathers integer[] := NULL; father integer := 0; firstfather integer := 0; no_father boolean := 'f'; sons integer[] := NULL; son integer := 0; row integer := 1; rows_length integer := 0; BEGIN -- Create "result" table for the example, the drop is in case you test many times the code DROP TABLE IF EXISTS result; CREATE TEMP TABLE result (sons integer,fathers integer); SELECT array(SELECT child FROM demo) INTO sons; rows_length := array_length(sons,1); -- Code that gets the first father of a child LOOP RAISE NOTICE 'son: %',sons[row]; son = sons[row]; LOOP father := (SELECT parent FROM demo WHERE child=son); IF father IS NULL THEN no_father='f'; ELSE no_father='t'; fathers[row] := father; son = father; END IF; EXIT WHEN no_father='f'; END LOOP; RAISE NOTICE 'father: %',fathers[row]; -- INSERT in "result" son with its first father INSERT into result(sons,fathers) values(sons[row],fathers[row]); row := row+1; EXIT WHEN rows_length < row; END LOOP; END $$; -- Display "result" SELECT * FROM result; 

This code generates the following table:

 Sons Fathers --------------- 10943 8656 6766 8656 9003 8656 5005 9151 6995 9151 6996 9160 

NOTE. Your table shows a child with two fathers (6995), which is not possible in a tree structure, this example works in a tree structure, where each child has one parent.

Answer 2

Using common table expressions (CTEs) makes writing as a query easier than a procedure.

Let's say we have this al_test table:

 +-----------+----------+ | parent_id | child_id | +-----------+----------+ | 10943 | 6766 | +-----------+----------+ | 6766 | 9003 | +-----------+----------+ | 9003 | 8656 | +-----------+----------+ | 5005 | 6995 | +-----------+----------+ | 6995 | 9151 | +-----------+----------+ | 6995 | 9160 | +-----------+----------+ 

For example (PostgreSQL 8.4+) to get all parents for node 5005:

 WITH RECURSIVE al_tree AS ( SELECT parent_id, child_id, 1 as depth FROM al_test WHERE child_id = 5005 UNION ALL SELECT al_test.parent_id, al_test.child_id, al_tree.depth + 1 FROM al_test, al_tree WHERE al_test.child_id = al_tree.parent_id ) SELECT parent_id FROM al_tree WHERE depth = (SELECT MAX(depth) FROM al_tree); 

Result:

 +-----------+ | parent_id | +-----------+ | 9151 | +-----------+ | 9160 | +-----------+