edgeリレーショナル データベース (Firebird) に 2 つのテーブルとnode(隣接リスト モデル)を持つ DAG があります。それらを再帰的にクエリしたいのですが、再帰クエリは非常に非効率的であることがわかりました。そこで、Dong et.al に続いて推移閉包を維持するためのトリガーを実装しようとしました。論文http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf。
SELECTは非常に高速になりましたがDELETE、グラフ全体が 1 回の削除でコピーされるため、非常に低速です。さらに悪いことに、同時更新は不可能に思えます。
これを実装するより良い方法はありますか？
編集
いくつかの実験を行い、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。アプローチの異なる興味深い記事や科学論文はありますか?