我有一个小而复杂的数据库(几百万条记录分布在非常少的几千个表中)。可以将记录视为业务规则。根据现有规则(包括其他用户定义的规则)，用户可以定义自己的规则。这些规则依赖于其他规则，有时通过复杂的路径。依赖关系形成一个扩展网络，而不是层次结构。
我正在寻找一种算法来确定在新定义的规则(或一组规则)中新规则本身是否是循环的，或者它是否在与现有规则一起使用时创建循环。
我需要一种在以下情况下高效的算法:
- 算法的结果只需是一个 bool 值 - 如果存在循环则为 true，否则为 false。
- 可以假定现有数据库是无循环的。
- 一旦找到循环，处理就可以停止。通常的情况(95% ??)是没有循环。不幸的是，这恰恰是(我认为)处理必须完成提议的新规则的所有可能路径，以确定没有循环的情况。
- 此算法将用于验证新的用户定义规则，因为它们被输入到数据库中。对于通常情况，它需要尽可能快 - 我不希望此验证成为创建过程中的瓶颈。
- 获取数据的成本相对较高 - 通常涉及一个或多个查询，其中一些查询非常复杂。可以约束新定义的规则集以便在内存中完全可用。如果可以对新规则的输入施加任何其他约束，这将有助于提高此检查的效率，我不知道它们可能是什么。
编辑
我接受 Nick 的回答，但有一点修改。存储依赖关系是对数据库的一种非常容易的修改。我只打算存储直接依赖项而不是所有直接或间接的依赖项。我可以将两组依赖项 C、D、F、G 和 X、Y、Z(在 Nick 的回答中)视为树结构，并使用各种技术中的一种从单级依赖项表中派生层次结构。我认为在这种情况下，这样做的成本是可以接受的。
编辑
最佳答案
希望我正确理解了您的问题:
假设您将规则 A 添加到数据库中，然后您还添加了依赖信息，例如 A depends C,D,F,G 和 X,Y,Z depend on A.
我假设没有真正查看整个结构的情况下无法在插入时检测循环，您说这是不允许的。
所以我的想法是预先计算和存储所有内容，即对于每个规则 R 存储它依赖的所有其他规则(不仅直接地，而且间接地)。现在，当您插入规则 A 时，只需从 C、D、F、G 获取所有依赖项，然后查看它们是否包含任何 X、Y、Z 或 A(如果不包含) t 没有循环，您可以安全地将 A 添加到您的规则集中，并存储来自 C、D、F、G 的所有依赖项以及 C、D、F、G 本身作为 A 的依赖项。
这当然需要对数据库进行一些重组(和重建)。
关于algorithm - 是否有一种有效的算法来检测复杂数据结构中的依赖循环？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12025839/