Come mantenere una tabella di chiusura transitiva in modo efficiente?

Question

Ho un DAG nel mio database relazionale (Firebird) con due tabelle edge e node (modello di elenco di adiacenze). Voglio interrogarli in modo ricorsivo, ma ho trovato le query ricorsive molto inefficienti. Così ho cercato di implementare i trigger per mantenere la chiusura transitiva seguendo il Dong et.al. carta http://homepages.inf.ed.ac.uk/libkin/papers/tc-sql.pdf.

SELECT s ora sono molto veloci, ma DELETE s sono estremamente lenti, poiché quasi l'intero grafico viene copiato per una singola eliminazione. Ancora peggio, gli aggiornamenti concorrenti sembrano impossibili.

C'è un modo migliore per implementare questo?

Modifica

ho fatto alcuni esperimenti e ha introdotto un contatore riferimento alla tabella TC. Con ciò, le eliminazioni sono veloci. Ho scritto alcuni semplici casi di test, ma non sono sicuro se sto facendo bene. Questo è quello che ho finora:

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^

Questa è la mia idea, ma penso che altri abbiano già implementato un TC. Stanno facendo la stessa cosa?

Ho alcuni casi di test, ma non sono sicuro di ottenere un'incoerenza con grafici più grandi.

Per quanto riguarda la concorrenza, penso che questo approccio fallirà quando due transazioni simultanee vogliono aggiornare il grafico, giusto?

Modifica

ho trovato alcuni bug nel mio codice, e mi piacerebbe condividere la versione fissa con voi.

Ho trovato un grande articolo: http://www.codeproject.com/Articles/22824/A-Model-to-Represent-Directed-Acyclic-Graphs-DAG-o. Ci sono articoli più interessanti o articoli scientifici, con approcci diversi?

Answer 1

Ho appena corretto un'operazione di eliminazione lenta estendendola al modello di tabella di chiusura riflessiva transitivo qui descritta: http://www.dba-oracle.com/t_sql_patterns_incremental_eval.htm. Ci è voluto un po 'più di lavoro per mantenere pienamente il conteggio dei percorsi al suo interno, ma ha pagato grandi quando le eliminazioni sono passate da 6 secondi a ogni singola operazione di rimozione a trascurabile (ora posso eliminare tutte le relazioni nel grafico e quindi aggiungerle tutte indietro in 14 secondi totali per 4.000 relazioni).

Answer 2

SQL non è lo strumento giusto per gestire i grafici. Utilizzare uno di questi:

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

mi piacciono molto ArangoDB, wich avere uno syntaxe vicino al MongoDB.

Answer 3

provare a creare indici per il relativo dove clausole (ad es .: child, parent).

Non ho familiarità con Firebird, ma ho un'idea di come funziona "firebird describe" e controlla se sta usando un uso corretto degli indici per accelerare i selezioni che hai all'interno delle tue procedure.

Anche la creazione di indici persi nelle prestazioni per upddate/delete/insert, nel tuo caso può migliorare il risultato.