1

我有一个小而复杂的数据库（几百万条记录分成非常少的数千张表）。这些记录可以被认为是业务规则。用户可以根据现有规则（包括其他用户定义的规则）定义自己的规则。这些规则依赖于其他规则，有时通过复杂的路径。依赖关系形成一个扩展的网络，而不是一个层次结构。

我正在寻找一种算法来确定，在新定义的规则（或规则集）中，新规则本身是否是循环的，或者它是否与现有规则一起创建循环。

我需要一种在以下情况下有效的算法：

  1. 算法的结果只需要是一个布尔值 - 如果有一个循环，则为 true，否则为 false。
  2. 可以假设现有数据库是无循环的。
  3. 一旦发现循环，处理就可以停止。通常的情况（95% ??）是没有循环。不幸的是，这正是（我认为）处理必须完成提议的新规则的所有可能路径的情况，以确定没有循环。
  4. 该算法用于验证新的用户定义规则，因为它们被输入到数据库中。对于通常的情况，它需要尽可能快——我不希望这种验证成为创建过程中的瓶颈。
  5. 获取数据的成本相对较高——通常涉及一个或多个查询，其中一些非常复杂。新定义的规则集可以被约束以便在内存中完全可用。如果可以对新规则的输入施加任何其他限制，这将有助于提高检查的效率，我不知道它们可能是什么。

编辑

我接受了尼克的回答，但做了一处修改。存储依赖项是对数据库的一个非常简单的修改。我将只存储直接​​依赖项而不是所有依赖项，无论是直接的还是间接的。我可以将两组依赖项 C、D、F、G 和 X、Y、Z（在尼克的回答中）视为树结构，并使用各种技术中的一种从单级依赖表派生层次结构。我认为在这种情况下，这样做的成本是可以接受的。

编辑

4

1 回答 1

1

我希望我正确理解了您的问题：

假设您将规则 A 添加到数据库中，然后您还添加了依赖信息，例如A depends on C,D,F,G和X,Y,Z depend on A。

我认为如果不真正查看整个结构，就无法在插入时检测循环，你说这是不允许的。

所以我的想法是预先计算和存储所有内容，即对于每个规则 R 存储它依赖的所有其他规则（不仅直接，而且间接）。现在，当您插入规则 A 时，只需从其中获取所有依赖C, D, F, G项并查看它们是否包含任何一个，X,Y,Z or A如果它们不存在则没有循环，您可以安全地将 A 添加到您的规则集中并将所有依赖项从C, D, F, G加上C, D, F, G它们自己存储为 A 的依赖项。

这当然需要对数据库进行一些重组（和重建）。

于 2012-08-19T10:54:13.677 回答