Come mantenere un invariante ricorsivo in un database MySQL?

Question

Ho un albero codificato in un database MySQL come bordi:

CREATE TABLE items (
    num INT,
    tot INT,
    PRIMARY KEY (num)
    );
CREATE TABLE tree (
    orig INT,
    term INT
    FOREIGN KEY (orig,term) REFERENCES items (num,num)
    )

Per ogni foglia dell'albero, items.tot è impostato da qualcuno.Per i nodi interni, items.tot deve essere la somma dei suoi figli.L'esecuzione ripetuta della query seguente genererebbe il risultato desiderato.

UPDATE items SET tot = (
    SELECT SUM(b.tot) FROM
        tree JOIN items AS b
        ON tree.term = b.num 
        WHERE tree.orig=items.num)
    WHERE EXISTS 
        (SELECT * FROM tree WHERE orig=items.num)

(nota che in realtà non funziona ma non è questo il punto)

Supponiamo che il database esista e che gli invarianti siano già soddisfatti.

La domanda è:

Qual è il modo più pratico per aggiornare il DB mantenendo questo requisito?Gli aggiornamenti possono spostare i nodi o alterare il valore di tot sui nodi fogliari.Si può presumere che i nodi foglia rimarranno come nodi foglia, i nodi interni rimarranno come nodi interni e il tutto rimarrà come un vero e proprio albero.

Alcuni pensieri che ho avuto:

• Invalidamento completo, dopo ogni aggiornamento, ricalcola tutto (Um...NO)
• Imposta un trigger sulla tabella degli elementi per aggiornare l'elemento padre di qualsiasi riga aggiornata
  • Questo sarebbe ricorsivo (gli aggiornamenti attivano aggiornamenti, attivano aggiornamenti, ...)
  • Non funziona, MySQL non può aggiornare la tabella che ha avviato il trigger
• Imposta un trigger per pianificare un aggiornamento dell'elemento padre di qualsiasi riga aggiornata
  • Questo sarebbe iterativo (ottieni un articolo dalla pianificazione, elaborandolo pianifica più articoli)
  • Cosa dà il via a tutto questo?Ti fidi del codice cliente per farlo bene?
  • Un vantaggio è che se gli aggiornamenti sono ordinati correttamente, sono necessarie meno somme da parte del computer.Ma quell'ordinamento è di per sé una complicazione.

Una soluzione ideale si generalizzerebbe ad altri "invarianti aggreganti"

FWIW So che è "un po' esagerato", ma lo faccio per divertimento (Divertimento:verbo, Trovare l'impossibile facendolo.:-)

Answer 1

Il problema che stai riscontrando è chiaro, ricorsione in SQL.Devi trovare il genitore del genitore...della foglia e ne aggiorna il totale (sottraendo il vecchio e aggiungendo il nuovo, oppure ricalcolandolo).Hai bisogno di una qualche forma di identificatore per vedere la struttura dell'albero e prendere tutti i nodi figli e un elenco dei genitori/percorso di una foglia da aggiornare.

Questo metodo aggiunge spazio costante (2 colonne alla tabella, ma ti serve solo una tabella, altrimenti puoi eseguire un'unione in seguito).Qualche tempo fa ho giocato con una struttura che utilizzava un formato gerarchico utilizzando colonne "sinistra" e "destra" (ovviamente non quei nomi), calcolati rispettivamente da un attraversamento pre-ordine e da un attraversamento post-ordine --non preoccuparti questi non devono essere ricalcolati ogni volta.

Ti lascio dare un'occhiata a una pagina usando questo metodo in mysql invece di continuare questa discussione nel caso in cui non ti piaccia questo metodo come risposta.Ma se ti piace, pubblica/modifica e mi prenderò un po' di tempo per chiarire.

Answer 2

Non sono sicuro di aver compreso correttamente la tua domanda, ma potrebbe funzionare La mia opinione sugli alberi in SQL.

Il post collegato descrive il metodo di memorizzazione dell'albero nel database - PostgreSQL in quel caso - ma il metodo è abbastanza chiaro, quindi può essere adottato facilmente per qualsiasi database.

Con questo metodo puoi aggiornare facilmente tutti i nodi che dipendono dal nodo modificato K con circa N semplici query SELECT dove N è la distanza di K dal nodo radice.

Spero che il tuo albero non sia molto profondo :).

Buona fortuna!