Comment maintenir un invariant récursif dans une base de données MySQL ?

Question

J'ai un arbre codé dans une base de données MySQL sous forme d'arêtes :

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

Pour chaque feuille de l'arbre, items.tot est défini par quelqu'un.Pour les nœuds intérieurs, items.tot doit être la somme de ses enfants.L’exécution répétée de la requête suivante générerait le résultat souhaité.

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)

(notez que cela ne fonctionne pas mais ce n'est pas la question)

Supposons que la base de données existe et que les invariants sont déjà satisfaits.

La question est:

Quelle est la manière la plus pratique de mettre à jour la base de données tout en conservant cette exigence ?Les mises à jour peuvent déplacer des nœuds ou modifier la valeur de tot sur les nœuds feuilles.On peut supposer que les nœuds feuilles resteront en tant que nœuds feuilles, les nœuds intérieurs resteront en tant que nœuds intérieurs et le tout restera comme un arbre approprié.

Quelques réflexions que j'ai eues :

• Invalidation complète, après toute mise à jour, recalculez tout (Euh...Non)
• Définir un déclencheur sur la table des éléments pour mettre à jour le parent de toute ligne mise à jour
  • Cela serait récursif (les mises à jour déclenchent des mises à jour, déclenchent des mises à jour, ...)
  • Ne fonctionne pas, MySQL ne peut pas mettre à jour la table qui a déclenché le déclencheur
• Définir un déclencheur pour planifier une mise à jour du parent de toute ligne mise à jour
  • Ce serait itératif (obtenir un élément de la planification, le traiter planifie plus d'éléments)
  • Qu’est-ce qui déclenche cela ?Faire confiance au code client pour bien faire les choses ?
  • Un avantage est que si les mises à jour sont commandées correctement, moins de sommes doivent être informatiques.Mais cet ordre est une complication en soi.

Une solution idéale se généraliserait à d'autres « invariants agrégés »

FWIW, je sais que c'est "un peu exagéré", mais je fais ça pour m'amuser (Fun :verbe, Trouver l'impossible en le faisant.:-)

Answer 1

Le problème que vous rencontrez est clair, la récursivité en SQL.Vous devez obtenir le parent du parent...de la feuille et met à jour son total (soit en soustrayant l'ancien et en ajoutant le nouveau, soit en recalculant).Vous avez besoin d'une forme d'identifiant pour voir la structure de l'arborescence, et récupérer tous les nœuds enfants et une liste des parents/chemin d'accès à une feuille à mettre à jour.

Cette méthode ajoute un espace constant (2 colonnes à votre table - mais vous n'avez besoin que d'une seule table, sinon vous pourrez effectuer une jointure plus tard).Il y a quelque temps, j'ai joué avec une structure qui utilisait un format hiérarchique utilisant des colonnes « gauche » et « droite » (évidemment pas ces noms), calculées respectivement par un parcours pré-commande et un parcours post-commande - ne vous inquiétez pas ceux-ci n'ont pas besoin d'être recalculés à chaque fois.

Je vous laisse jeter un oeil à une page en utilisant cette méthode dans MySQL au lieu de continuer cette discussion au cas où vous n'aimeriez pas cette méthode comme réponse.Mais si vous l'aimez, postez/modifiez et je prendrai un peu de temps pour clarifier.

Answer 2

Je ne suis pas sûr de bien comprendre votre question, mais cela pourrait fonctionner Mon point de vue sur les arbres en SQL.

L'article lié décrit la méthode de stockage de l'arbre dans la base de données - PostgreSQL dans ce cas - mais la méthode est suffisamment claire pour qu'elle puisse être facilement adoptée pour n'importe quelle base de données.

Avec cette méthode, vous pouvez facilement mettre à jour tous les nœuds en fonction du nœud modifié. K avec environ N requêtes SELECT simples où N est la distance de K à partir du nœud racine.

J'espère que ton arbre n'est pas vraiment profond :).

Bonne chance!