mysql - 如何在 MySQL 数据库中维护递归不变量？

Question

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

(注意这实际上不起作用，但那不是重点)

假设数据库存在并且不变量已经满足。

问题是:

What is the most practical way to update the DB while maintaining this requirement? Updates may move nodes around or alter the value of tot on leaf nodes. It can be assumed that leaf nodes will stay as leaf nodes, interior nodes will stay as interior nodes and the whole thing will remain as a proper tree.

我的一些想法:

• 完全失效，在任何更新后，重新计算所有内容(嗯...不)
• 在 items 表上设置触发器以更新任何已更新行的父级
  • 这将是递归的(更新触发更新，触发更新，...)
  • 不起作用，MySQL 无法更新启动触发器的表
• 设置触发器以安排更新任何已更新行的父级
  • 这将是迭代的(从时间表中获取一个项目，处理它以安排更多项目)
  • 是什么开始了？信任客户端代码才能正确执行？
  • 一个优点是，如果更新的顺序正确，则需要计算的总和就会减少。但这种排序本身就很复杂。

一个理想的解决方案是推广到其他“聚合不变量”

FWIW 我知道这“有点过火”，但我这样做是为了好玩(乐趣:动词，通过做来发现不可能。:-)

Answer 1

您遇到的问题很明显，SQL 中的递归。您需要获取父级的父级...并更新它的总数(减去旧的并添加新的，或重新计算)。您需要某种形式的标识符来查看树的结构，并获取所有子节点和要更新的叶子的父节点/路径列表。

此方法会添加常量空间(2 列到您的表中——但您只需要一个表，否则您可以稍后进行连接)。我刚才玩过一个结构，它使用分层格式使用“左”和“右”列(显然不是那些名称)，分别通过前序遍历和后序遍历计算——别担心这些不需要每次都重新计算。

我让你看一个页面using this method in mysql如果您不喜欢这种方法作为答案，请不要继续讨论。但是，如果您喜欢它，请发布/编辑，我会花一些时间进行澄清。