我有一棵树在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.

我有一些想法：

• 完全无效，进行任何更新后，重新计算所有内容(嗯...否)
• 不起作用，MySQL无法更新启动触发器的表
• 是什么开始的呢？信任客户端代码以使其正确吗？
• 优点是，如果正确订购了更新，则需要的计算机数量更少。但是，排序本身就是一种复杂情况。

理想的解决方案将推广到其他"聚合不变量"

FWIW我知道这有点"过分"，但是我这样做很有趣(有趣：动词，通过这样做发现不可能。:-)

解决方案

回答

我不确定我是否正确理解了问题，但这可以解决我在SQL中对树的看法。

链接后描述了在数据库中存储树的方法(在这种情况下为PostgreSQL)，但是该方法很明确，因此可以轻松地用于任何数据库。

使用这种方法，我们可以使用大约N个简单的SELECTs查询轻松地更新所有依赖于修改后的节点K的节点，其中N是K到根节点的距离。

我希望你的树不是真的很深:)。

祝你好运！

回答

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

此方法增加了恒定的空间(表中有2列-但我们只需要一个表，否则可以稍后进行联接)。我之前玩过一种结构，该结构使用了使用"左"和"右"列(显然不是那些名称)的分层格式，分别由前遍历和后遍历计算得出-不用担心这些不需要每次都重新计算。

如果我们不喜欢使用此方法作为答案，我将让我们看一下在mysql中使用此方法的页面，而不是继续进行此讨论。但是，如果我们喜欢，请发表/编辑，我将花一些时间进行澄清。