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)

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

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

问题是：

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

我曾经有过的一些想法：

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

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

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

4

2 回答 2

1

我不确定我是否正确理解了您的问题，但这可能适用于我对 SQL 中的树的看法。

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

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

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

祝你好运！

于 2008-08-21T21:36:29.450 回答
1

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

此方法增加了固定空间（表中有 2 列——但您只需要一个表，否则您可以稍后进行连接）。不久前，我使用了一种结构，它使用了使用“左”和“右”列（显然不是那些名称）的分层格式，分别由前序遍历和后序遍历计算——别担心这些不需要每次都重新计算。

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

于 2008-08-22T02:14:04.820 回答