title: How to maintain a transitive closure table efficiently?
body: <p>I have a DAG in my relational database (Firebird) with two tables <code>edge</code> and <code>node</code> (adjacency list model). I want to query them recursively, but found recursive queries very inefficient. So I tried to implement triggers to maintain the transitive closure following the Dong et.al. paper <a href="http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf" rel="noreferrer">http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf</a>.</p>
  
  <p><code>SELECT</code>s are now very fast, but <code>DELETE</code>s are extremely slow, because almost the whole graph is copied for a single delete. Even worse, concurrent updates seem impossible.</p>
  
  <p>Is there a better way to implement this?</p>
  
  <p><strong>Edit</strong></p>
  
  <p>I did some experiments and introduced a reference counter to the TC table. With that, deletes are fast. I wrote some simple test cases, but I'm not sure if I'm doing right. This is what i have so far:</p>
  
  <pre><code>CREATE GENERATOR graph_tc_seq;
  
  CREATE TABLE EDGE (
      parent DECIMAL(10, 0) NOT NULL,
      child DECIMAL(10, 0) NOT NULL,
      PRIMARY KEY (parent, child)
  );
  
  CREATE TABLE GRAPH_TC (
      parent DECIMAL(10, 0) NOT NULL,
      child DECIMAL(10, 0) NOT NULL,
      refcount DECIMAL(9, 0),
      PRIMARY KEY (parent, child)
  );
  
  CREATE TABLE GRAPH_TC_TEMP (
      session_id DECIMAL(9, 0),
      parent DECIMAL(10, 0),
      child DECIMAL(10, 0)
  );
  
  CREATE PROCEDURE GRAPH_TC_CREATE (p_parent DECIMAL(10, 0), c_child DECIMAL(10, 0))
  AS 
      declare variable tp_parent DECIMAL(10,0);
      declare variable tc_child DECIMAL(10,0);
      declare variable session_id DECIMAL(9,0);
      declare variable refs DECIMAL(9,0);
  begin
      session_id = gen_id(graph_tc_seq,1);
      insert into graph_tc_temp (parent, child, session_id, refcount) values (:p_parent, :p_parent, :session_id, 1);
      insert into graph_tc_temp (parent, child, session_id, refcount) values (:c_child, :c_child, :session_id, 1);
      insert into graph_tc_temp (parent, child, session_id, refcount) values (:p_parent, :c_child, :session_id, 1);
      insert into graph_tc_temp (parent, child, session_id, refcount) select distinct :p_parent, child, :session_id, refcount from graph_tc where parent = :c_child and not parent = child;
      insert into graph_tc_temp (child, parent, session_id, refcount) select distinct :c_child, parent, :session_id, refcount from graph_tc where child = :p_parent and not parent = child;
      insert into graph_tc_temp (parent, child, session_id, refcount) select distinct a.parent, b.child, :session_id, a.refcount*b.refcount from graph_tc a, graph_tc b where a.child = :p_parent and b.parent = :c_child and not a.parent = a.child and not b.parent = b.child;
      for select parent, child, refcount from graph_tc_temp e where session_id= :session_id and exists (select * from graph_tc t where t.parent = e.parent and t.child = e.child ) into :tp_parent, :tc_child, :refs do begin
          update graph_tc set refcount=refcount+ :refs where parent = :tp_parent and child = :tc_child;
      end
      insert into graph_tc (parent, child, refcount) select parent, child, refcount from graph_tc_temp e where session_id = :session_id and not exists (select * from graph_tc t where t.parent = e.parent and t.child = e.child);
      delete from graph_tc_temp where session_id = :session_id;
  end ^
  
  CREATE PROCEDURE GRAPH_TC_DELETE (p_parent DECIMAL(10, 0), c_child DECIMAL(10, 0))
  AS 
      declare variable tp_parent DECIMAL(10,0);
      declare variable tc_child DECIMAL(10,0);
      declare variable refs DECIMAL(9,0);
  begin
      delete from graph_tc where parent = :p_parent and child = :p_parent and refcount &lt;= 1;
      update graph_tc set refcount = refcount - 1 where parent = :p_parent and child = :p_parent and refcount &gt; 1;
      delete from graph_tc where parent = :c_child and child = :c_child and refcount &lt;= 1;
      update graph_tc set refcount = refcount - 1 where parent = :c_child and child = :c_child and refcount &gt; 1;
      delete from graph_tc where parent = :p_parent and child = :c_child and refcount &lt;= 1;
      update graph_tc set refcount = refcount - 1 where parent = :p_parent and child = :c_child and refcount &gt; 1;
      for select distinct :p_parent,  b.child, refcount from graph_tc b where b.parent = :c_child and not b.parent = b.child into :tp_parent, :tc_child, :refs do begin
          delete from graph_tc where parent = :tp_parent and child = :tc_child and refcount &lt;= :refs;
          update graph_tc set refcount = refcount - :refs where parent = :tp_parent and child = :tc_child and refcount &gt; :refs;
      end
      for select distinct :c_child,  b.parent, refcount from graph_tc b where b.child = :p_parent and not b.parent = b.child into :tc_child, :tp_parent, :refs do begin
          delete from graph_tc where child = :tc_child and parent = :tp_parent and refcount &lt;= :refs;
          update graph_tc set refcount = refcount - :refs where child = :tc_child and parent = :tp_parent and refcount &gt; :refs;
      end
      for select distinct a.parent, b.child, a.refcount*b.refcount from graph_tc a, graph_tc b where not a.parent = a.child and not b.parent = b.child and a.child = :p_parent and b.parent = :c_child into :tp_parent, :tc_child, :refs do begin
          delete from graph_tc where parent = :tp_parent and child = :tc_child and refcount &lt;= :refs;
          update graph_tc set refcount = refcount - :refs where parent = :tp_parent and child = :tc_child and refcount &gt; :refs;
      end
  end ^
  
  CREATE TRIGGER GRAPH_TC_AFTER_INSERT FOR EDGE AFTER INSERT as
  begin
      execute procedure graph_tc_create(new.parent,new.child);
  end ^
  
  CREATE TRIGGER GRAPH_TC_AFTER_UPDATE FOR EDGE AFTER UPDATE as
  begin
      if ((new.parent &lt;&gt; old.parent) or (new.child &lt;&gt; old.child)) then begin
      execute procedure graph_tc_delete(old.parent,old.child);
      execute procedure graph_tc_create(new.parent,new.child);
      end
  end ^
  
  CREATE TRIGGER GRAPH_TC_AFTER_DELETE FOR EDGE AFTER DELETE as
  begin
      execute procedure graph_tc_delete(old.parent,old.child);
  end ^
  </code></pre>
  
  <p>This is my own idea, but I think others have implemented an TC already. Are they doing the same thing?</p>
  
  <p>I have some test cases, but I'm not sure if I might get an inconsistency with bigger graphs.</p>
  
  <p>How about concurrency, I think this approach will fail when two simultaneous transactions want to update the graph, right?</p>
  
  <p><strong>Edit</strong></p>
  
  <p>I found some bugs in my code, and I'd like to share the fixed version with you.</p>
  
  <p>I found a great article: <a href="http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o" rel="noreferrer">http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o</a>. Are there more interesting articles or scientific papers, with different approaches?</p>