Wie pflege ich eine rekursive Invariante in einer MySQL-Datenbank?

Question

Ich habe einen Baum, der in einer MySQL-Datenbank als Kanten kodiert ist:

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)
    )

Für jedes Blatt im Baum, items.tot wird von jemandem festgelegt.Für innere Knoten: items.tot muss die Summe seiner Kinder sein.Das wiederholte Ausführen der folgenden Abfrage würde zum gewünschten Ergebnis führen.

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)

(Beachten Sie, dass dies tatsächlich nicht funktioniert, aber das ist nebensächlich)

Gehen Sie davon aus, dass die Datenbank existiert und die Invariante bereits erfüllt ist.

Die Frage ist:

Was ist die praktischste Möglichkeit, die Datenbank zu aktualisieren und gleichzeitig diese Anforderung einzuhalten?Aktualisierungen können Knoten verschieben oder den Wert von ändern tot an Blattknoten.Es kann davon ausgegangen werden, dass Blattknoten als Blattknoten bleiben, innere Knoten als innere Knoten bleiben und das Ganze als richtiger Baum bleibt.

Einige Gedanken, die ich hatte:

• Vollständige Invalidierung, nach jedem Update alles neu berechnen (Ähm...)NEIN)
• Legen Sie einen Auslöser für die Artikeltabelle fest, um das übergeordnete Element jeder aktualisierten Zeile zu aktualisieren
  • Dies wäre rekursiv (Updates lösen Updates aus, lösen Updates aus, ...)
  • Funktioniert nicht, MySQL kann die Tabelle, die den Trigger ausgelöst hat, nicht aktualisieren
• Legen Sie einen Auslöser fest, um eine Aktualisierung des übergeordneten Elements jeder aktualisierten Zeile zu planen
  • Dies wäre iterativ (ein Element aus dem Zeitplan abrufen, bei der Verarbeitung werden weitere Elemente geplant)
  • Was löst das aus?Vertrauen Sie dem Client-Code, um es richtig zu machen?
  • Ein Vorteil besteht darin, dass bei korrekter Reihenfolge der Updates weniger Beträge berechnet werden müssen.Aber diese Reihenfolge ist an sich schon eine Komplikation.

Eine ideale Lösung wäre die Verallgemeinerung auf andere „aggregierende Invarianten“

FWIW Ich weiß, das ist „etwas übertrieben“, aber ich mache das zum Spaß (Spaß:Verb: Das Unmögliche finden, indem man es tut.:-)

Answer 1

Das Problem, das Sie haben, ist klar: Rekursion in SQL.Sie müssen den Elternteil des Elternteils erhalten ...des Blattes und aktualisiert dessen Gesamtsumme (entweder durch Subtrahieren des Alten und Addieren des Neuen oder durch Neuberechnung).Sie benötigen eine Art Identifikator, um die Struktur des Baums zu sehen und alle untergeordneten Knoten eines Knotens sowie eine Liste der Eltern/Pfade zu einem zu aktualisierenden Blatt abzurufen.

Diese Methode fügt konstanten Speicherplatz hinzu (2 Spalten zu Ihrer Tabelle – Sie benötigen jedoch nur eine Tabelle, andernfalls können Sie später einen Join durchführen).Ich habe vor einiger Zeit mit einer Struktur herumgespielt, die ein hierarchisches Format mit „linken“ und „rechten“ Spalten (offensichtlich nicht diese Namen) verwendete, berechnet durch einen Durchlauf vor der Bestellung bzw. einen Durchlauf nach der Bestellung – keine Sorge Diese müssen nicht jedes Mal neu berechnet werden.

Ich lasse Sie einen Blick auf eine Seite werfen Verwenden dieser Methode in MySQL Anstatt diese Diskussion fortzusetzen, falls Ihnen diese Methode als Antwort nicht gefällt.Aber wenn es Ihnen gefällt, posten/bearbeiten Sie es und ich werde mir etwas Zeit nehmen und es klären.

Answer 2

Ich bin mir nicht sicher, ob ich Ihre Frage richtig verstehe, aber das könnte funktionieren Meine Sicht auf Bäume in SQL.

Der verlinkte Beitrag beschreibt die Methode zum Speichern des Baums in einer Datenbank – in diesem Fall PostgreSQL –, aber die Methode ist klar genug, sodass sie problemlos für jede Datenbank übernommen werden kann.

Mit dieser Methode können Sie alle Knoten, die von geänderten Knoten abhängen, einfach aktualisieren K mit ungefähr N einfache SELECTs-Abfragen wo N ist Abstand von K vom Wurzelknoten.

Ich hoffe, dein Baum ist nicht wirklich tief :).

Viel Glück!