Recursive triggers..

Iterative programming is too dominant. Some how, most programmers have been trained in using for/while loops, iterators, coroutines and similar constructs so sucessfully to see that they are not needed, or indeed not very elegant.

One case in point is computing the transitive closure of a graph in SQL. We can easilly find iterative solutions (like this one or even this one) which could easilly have been written in an interative language. SQL is not an interative language, and I see no point of using control constructs like that. All we really need is triggers.
(I'm using SQLite for this, other RDMS may work too :-) ):

So, this is what I am playing with:

PRAGMA recursive_triggers = 1;
--- SQlite verison > 3.6.18 is needed for this to work.

-- Clears the TC store and insert simple connections
-- This is the start point in the call sequence and is triggered by the user inserting data

create trigger ll_tcll_insert after insert on level_level for each row begin
delete from tc_level_level where depth > 1;
insert into tc_level_level select NEW.parent_id ancestor_id,NEW.child_id descendant_id,1 depth,NEW.parent_id || ',' ||NEW.child_id path from level_level;
end;

-- This trigger does the recursive TC building by merging of subgraphs
create trigger tcll_tcll_insert after insert on tc_level_level for each row begin
insert into tc_level_level select tc1.ancestor_id, tc2.descendant_id, tc1.depth + tc2.depth,tc1.path || substr(tc2.path, length(tc2.ancestor_id)+1) from tc_level_level tc1, tc_level_level tc2 where tc1.descendant_id = tc2.ancestor_id;
end;

-- This trigger clears the TC store and deletes the simple connection when a simple connection is deleted

create trigger ll_tcll_delete after delete on level_level for each row begin
delete from tc_level_level where depth > 1 or (OLD.parent_id = ancestor_id and OLD.child_id = descendant_id) ;
end;

-- This trigger is executed when something in the TC store is deleted. It runs exactly one TC run, so that teh main TC builing trigger is executed.

create trigger tcll_tcll_delete after delete on tc_level_level for each row when (select max(depth) from tc_level_level) = 1 begin
insert into tc_level_level select tc1.ancestor_id, tc2.descendant_id, tc1.depth + tc2.depth,tc1.path || substr(tc2.path, length(tc2.ancestor_id)+1) from tc_level_level tc1, tc_level_level tc2 where tc1.descendant_id = tc2.ancestor_id;
end;

These triggers combined results in the following example run (level_level links adjecent nodes together and the transitice closure (TC) is then stored in tc_level_level):

sqlite> select * from level_level;
sqlite> select * from tc_level_level;
sqlite> INSERT INTO "level_level" VALUES(1,2);
sqlite> INSERT INTO "level_level" VALUES(1,3);
sqlite> INSERT INTO "level_level" VALUES(3,4);
sqlite> INSERT INTO "level_level" VALUES(4,5);
sqlite> INSERT INTO "level_level" VALUES(2,5);
sqlite> select * from level_level;
parent_id child_id
---------- ----------
1 2
1 3
3 4
4 5
2 5
sqlite> select * from tc_level_level;
ancestor_id descendant_id depth path
----------- ------------- ---------- ----------
1 2 1 1,2
1 3 1 1,3
3 4 1 3,4
4 5 1 4,5
1 4 2 1,3,4
3 5 2 3,4,5
1 5 3 1,3,4,5
2 5 1 2,5
1 5 2 1,2,5
sqlite> delete from level_level where parent_id = 1 and child_id = 2;sqlite> select * from tc_level_level;
ancestor_id descendant_id depth path
----------- ------------- ---------- ----------
1 3 1 1,3
3 4 1 3,4
4 5 1 4,5
2 5 1 2,5
1 4 2 1,3,4
3 5 2 3,4,5
1 5 3 1,3,4,5
sqlite> delete from level_level where parent_id = 3 and child_id = 4;
sqlite> select * from tc_level_level;
ancestor_id descendant_id depth path
----------- ------------- ---------- ----------
1 3 1 1,3
4 5 1 4,5
2 5 1 2,5
sqlite> INSERT INTO "level_level" VALUES(1,2);
sqlite> select * from tc_level_level;
ancestor_id descendant_id depth path
----------- ------------- ---------- ----------
1 3 1 1,3
4 5 1 4,5
2 5 1 2,5
1 2 1 1,2
1 5 2 1,2,5

So, by using just a couple of triggers (actually, really just one for the TC computation, the rest of them are just maintenance triggers) we are able to get a TV computed. We even get the full path (which is the main reason for the complicated code sections above).

No for/while loops, and just simple clean code, written in SQLite SQL.

Quite neat really. Yay for recursion.