推移閉包表を効率的に維持する方法は？

Question

私はリレーショナルデータベース（Firebird）に2つのテーブルedgeとnode（隣接リストモデル）を持つDAGを持っています。私はそれらを再帰的にクエリしたいが、再帰的なクエリは非常に非効率的であることがわかった。そこで私は、Dong et.alに続いて推移的閉鎖を維持するためのトリガーを実装しようとしました。ペーパーhttp://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf。

SELECTは非常に高速ですが、ほとんどのグラフが1回の削除でコピーされるため、DELETEは非常に遅いです。さらに悪いことに、同時更新は不可能に思えます。

これを実装するより良い方法はありますか？

編集

私はいくつかの実験を行なったし、TCテーブルに参照カウンタを導入しました。これで、削除は高速です。私はいくつかの簡単なテストケースを書いたが、私が正しいことをしているかどうかは分からない。これは私がこれまで持っているものです：

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 <= 1; 
    update graph_tc set refcount = refcount - 1 where parent = :p_parent and child = :p_parent and refcount > 1; 
    delete from graph_tc where parent = :c_child and child = :c_child and refcount <= 1; 
    update graph_tc set refcount = refcount - 1 where parent = :c_child and child = :c_child and refcount > 1; 
    delete from graph_tc where parent = :p_parent and child = :c_child and refcount <= 1; 
    update graph_tc set refcount = refcount - 1 where parent = :p_parent and child = :c_child and refcount > 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 <= :refs; 
     update graph_tc set refcount = refcount - :refs where parent = :tp_parent and child = :tc_child and refcount > :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 <= :refs; 
     update graph_tc set refcount = refcount - :refs where child = :tc_child and parent = :tp_parent and refcount > :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 <= :refs; 
     update graph_tc set refcount = refcount - :refs where parent = :tp_parent and child = :tc_child and refcount > :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 <> old.parent) or (new.child <> 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^

これは私の考えですが、他の人がすでにTCを実装していると思います。彼らは同じことをしていますか？

私はいくつかのテストケースを持っていますが、大きなグラフでは矛盾するかどうかはわかりません。

並行性については、2つの同時トランザクションがグラフを更新したい場合、このアプローチは失敗すると思いますか？

編集

私は自分のコード内のいくつかのバグを発見した、と私はあなたと固定されたバージョンを共有したいと思います。

私は素晴らしい記事を見つけました：http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o。異なるアプローチを使って、より興味深い論文や科学論文がありますか？

Answer 1

http://www.dba-oracle.com/t_sql_patterns_incremental_eval.htmここに記載されている過渡的な反射的クロージャテーブルモデルに拡張することで、遅い削除操作を修正しました。その中のパス数を完全に維持するためにもう少し作業が必要でしたが、削除が6秒ごとに削除操作から無視できる状態になったときに大きな効果を得ました（グラフ内のすべての関係を削除できるようになりました。 4秒で合計4,000の関係）。

Answer 2

SQLは、グラフを扱うための適切なツールではありません。これらのいずれかを使用します。

http://en.wikipedia.org/wiki/Graph_database

は、私は非常にArangoDBが好きで、ウィッヒのMongoDBに近いsyntaxeを持っています。

Answer 3

のインデックスを作成すると、句（たとえば、、parent）が作成されます。

私はFirebirdに慣れていませんが、 "firebird describe"がどのように機能しているかを見て、手順内の選択をスピードアップするためにインデックスを適切に使用しているかどうかを確認します。

upddate/delete/insertのパフォーマンスが低下したインデックスを作成しても、結果が改善される場合があります。