如何在 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)

（请注意，这实际上不起作用，但这不是重点）

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

问题是：

在保持此要求的同时更新数据库的最实用方法是什么？更新可能会移动节点或改变 tot 在叶节点上。可以假设叶节点将保留为叶节点，内部节点将保留为内部节点，并且整个事物将保留为适当的树。

我有过一些想法：

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

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

FWIW我知道这“有点过分”，但我这样做是为了好玩（有趣：动词，通过做来发现不可能的事情。:-)

Answer 1

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

此方法会添加恒定空间（表中包含 2 列——但您只需要一张表，否则您可以稍后进行联接）。我不久前玩过一个结构，该结构使用分层格式，使用“左”和“右”列（显然不是那些名称），分别通过前序遍历和后序遍历计算——不用担心这些不需要每次都重新计算。

我让你看一个页面 在mysql中使用这个方法 如果您不喜欢此方法作为答案，则不要继续此讨论。但如果您喜欢，请发布/编辑，我会花一些时间进行澄清。

Answer 2

我不确定我是否正确理解你的问题，但这可行 我对 SQL 中树的看法.

链接的帖子描述了在数据库中存储树的方法 - 在这种情况下是 PostgreSQL - 但该方法足够清晰，因此可以轻松地用于任何数据库。

通过这种方法，您可以轻松更新所有依赖于修改节点的节点 K 与约 氮 简单的 SELECT 查询 where 氮 是距离 K 从根节点开始。

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

祝你好运！