私はエッジとしてMySQLデータベースにエンコードされたツリーを持っています:どのように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
の値を変更することがあります。リーフノードはリーフノードのままであり、内部ノードは内部ノードとして残り、すべてが適切なツリーとして残ると仮定できます。
私はいくつかの考えを持っていました:
- すべての更新の後、完全失効はすべてを再計算します(Um ...いいえ)
- 任意の行が更新されます
- これは再帰的です(トリガの更新、トリガの更新などを更新します)。
- 動作しません.MySQLはトリガを起動したテーブルを更新できません
更新される行の親の更新をスケジュールするトリガーを設定する
- これは反復的です(スケジュールから項目を取得し、それ以上の項目をスケジュールする)
- それを正しくするためにクライアントコードを信頼していますか?
- 利点は、更新プログラムが正しく注文された場合、合計がコンピュータである必要があることです。しかし、その順序はそれ自身の複雑さです。
理想的な解は、他の「凝集不変量」に一般化されます。
FWIWこれは「少し外れている」ことを知っていますが、私はこれを楽しんでいます。それをすることで不可能です:-)
興味深いアプローチです。私が気に入らないのは、 'N * Log(N)'のようなものを使用していることです。また、私は主要な改造を必要とするいくつかのバージョン管理の制約があります。 - 残念ながら、著者は集計値を更新する方法に決して慣れていません。私はいくつかのアプローチについて考えることができますが、その実装に依存します。私はこれ以上考えなければならないでしょう。 ([非常に古い]回答から移動しました) – BCS
形式を記述するmysqlドキュメントへのリンクを更新しました。 – nlucaroni