1

查询类似于

返回所有顶点，使得（可从（A 和（B 或 C）））和（不可从（D 和 E））。

可以使用任何类型的可达性布尔约束来形成查询。

有没有快速执行此查询的有效方法？除了实际找到所有项目可达关注点的集合之外，那么这些集合上的并集、交集和集减法呢？

4

1 回答 1

0

我认为使搜索速度比您建议的默认值更快的唯一方法（计算从谓词中的每个顶点可到达的集合，然后进行集合算术），就是在搜索期间进行布尔数学运算，并使用它来中止分支机构。

例如，假设我们试图计算从 ((A or B) 但不是 C) 可达的集合。在搜索节点时，如果我们在标记为 (B) 的节点上，并且“下一个”节点中的两个已经分别标记为 (A) 和 (C)。在这三个节点上，谓词简化为：

(B): P = NOT(C)
(A): P = NOT(C)
(C): P = FALSE

所以没有理由继续搜索这些节点中的任何一个。

（当然，如果我们要在同一个 DAG 上计算多个集合，我们应该保留这些标记。）

于 2010-05-10T16:47:26.267 回答