MySQL データベースで再帰的不変式を維持するにはどうすればよいですか?

StackOverflow https://stackoverflow.com/questions/20426

質問

MySQL データベースにエッジとしてエンコードされたツリーがあります。

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

木の葉一枚一枚に、 items.tot 誰かが設定したものです。内部ノードの場合、 items.tot 子の合計である必要があります。次のクエリを繰り返し実行すると、目的の結果が生成されます。

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)

(これは実際には機能しないことに注意してくださいが、それは重要ではありません)

データベースが存在し、不変条件がすでに満たされていると仮定します。

質問は：

この要件を維持しながら DB を更新する最も現実的な方法は何ですか?更新によりノードが移動したり、値が変更される場合があります。 tot リーフノード上。葉ノードは葉ノードとして残り、内部ノードは内部ノードとして残り、全体が適切なツリーとして残ると想定できます。

私が抱いたいくつかの考え:

  • 完全な無効化、更新後にすべてを再計算します (ええと...いいえ）
  • items テーブルにトリガーを設定して、更新される行の親を更新します。
    • これは再帰的になります (更新が更新をトリガーし、更新をトリガーする...)
    • 機能しません。MySQL はトリガーを開始したテーブルを更新できません
  • 更新される行の親の更新をスケジュールするトリガーを設定します。
    • これは反復的になります (スケジュールから項目を取得し、それを処理するとさらに多くの項目がスケジュールされます)。
    • 何がきっかけでこれが始まるのでしょうか？クライアントコードを信頼して正しく動作しますか?
    • 利点は、アップデートが正しく注文された場合、コンピュータに必要な金額が少なくて済むことです。しかし、その順序はそれ自体が複雑です。

理想的な解決策は、他の「集約不変条件」に一般化することです。

FWIW これは「少し行き過ぎ」であることは承知していますが、私はこれを楽しみのためにやっています (楽しい:動詞、実行することで不可能を発見する。:-)

役に立ちましたか？

解決

あなたが抱えている問題は明らかで、SQL の再帰です。親の親を取得する必要があります...リーフの合計を更新し、その合計を更新します (古いものを減算して新しいものを追加するか、再計算します)。ツリーの構造を確認し、すべてのノードの子と親のリスト/更新するリーフへのパスを取得するには、何らかの形式の識別子が必要です。

この方法では、定数スペースが追加されます (テーブルに 2 列ですが、必要なテーブルは 1 つだけです。そうでない場合は、後で結合できます)。私は少し前に、それぞれ事前順序トラバーサルと事後順序トラバーサルによって計算される「左」列と「右」列 (明らかにこれらの名前ではありません) を使用した階層形式を使用する構造を試してみました。心配しないでください。これらは毎回再計算する必要はありません。

ページを見てみましょう mysqlでこのメソッドを使用する この方法が答えとして気に入らない場合に備えて、この議論を続ける代わりに。しかし、気に入っていただけましたら、投稿/編集していただければ、少し時間をかけて説明させていただきます。

他のヒント

あなたの質問を正しく理解できているかどうかはわかりませんが、これはうまくいくかもしれません SQL におけるツリーについての私の見解.

リンクされた投稿では、ツリーをデータベースに保存する方法 (この場合は PostgreSQL) について説明しましたが、その方法は十分に明確なので、どのデータベースにも簡単に採用できます。

この方法を使用すると、変更されたノードに応じてすべてのノードを簡単に更新できます K 約で N 単純な SELECT クエリ N の距離です K ルートノードから。

あなたのツリーがそれほど深くないことを願っています:)。

幸運を！

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top