2

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リーフ ノードの値が変更されたりする場合があります。葉ノードは葉ノードのままであり、内部ノードは内部ノードのままであり、全体は適切なツリーのままであると想定できます。

私が持っていたいくつかの考え：

  • 完全な無効化、更新後、すべてを再計算します (ええと...いいえ)
  • アイテム テーブルにトリガーを設定して、更新された行の親を更新します。
    • これは再帰的です（更新は更新をトリガーし、更新をトリガーします...）
    • 動作しません。MySQL はトリガーを開始したテーブルを更新できません
  • 更新される任意の行の親の更新をスケジュールするようにトリガーを設定します
    • これは反復的です（スケジュールからアイテムを取得し、それを処理してさらにアイテムをスケジュールします）
    • 何がこれを開始しますか？クライアントコードを信頼して正しく取得しますか?
    • 利点は、更新が正しく順序付けられている場合、計算する必要がある合計が少なくなることです。しかし、その順序はそれ自体が複雑です。

理想的な解決策は、他の「集約不変条件」に一般化されます

FWIW私はこれが「少しやり過ぎ」であることを知っていますが、私は楽しみのためにこれをやっています（楽しい：動詞、それを行うことによって不可能を見つける. :-)

4

2 に答える 2

1

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

このメソッドは一定のスペースを追加します（テーブルに2つの列が必要ですが、必要なテーブルは1つだけです。それ以外の場合は、後で結合できます）。少し前に、「左」列と「右」列（明らかにこれらの名前ではない）を使用して階層形式を使用し、それぞれプレオーダートラバーサルとポストオーダートラバーサルによって計算された構造を試してみました-心配しないでくださいこれらは毎回再計算する必要はありません。

この方法が答えとして気に入らない場合に備えて、この議論を続ける代わりに、mysqlでこの方法を使用しているページを見てみましょう。しかし、あなたがそれを好きなら、投稿/編集してください、そして私は少し時間をかけて明確にします。

于 2008-08-22T02:14:04.820 に答える
1

あなたの質問を正しく理解しているかどうかはわかりませんが、これでうまくいくかもしれません。

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

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

あなたの木が本当に深くないことを願っています:)。

幸運を！

于 2008-08-21T21:36:29.450 に答える