如何避免 logicblox/logiQL 中递归逻辑谓词的具体化？

Question

我正在尝试使用 LogicBlox 的功能作为数据记录求解器。我有性能问题，我认为我使用 LB 是错误的，因为它的行为就好像它正在具体化所有关系（使用例如魔术集的 Datalog 求解器不会这样做）。

正如我所说，我可能没有像预期的那样使用 LB，但这是我的测试。我想创建一些二元关系 e(x,y) 的传递闭包 c(x,y)。出于测试目的，我将 e 创建为一个简单的循环，即我将 e(i,(i+1)%1000) 添加到 LB 0 ≤ i < 1000。

当我只对 from0(x) <- c(0,x) 感兴趣时，则无需实际具体化 c 并且魔术设置方法将创建谓词 c_{bound,free}(x, y) 并从 0(0) 计算，然后从 0(1) 导出，等等。整个操作大约需要 1000 步。

如果我用程序做我的例子：

e(x,y) -> int(x), int(y).
// fill e with data
c(x,y) -> int(x), int(y).
c(x,y) <- e(x,y) ; c(x,z),e(z,y).
from0(x) <- c(0,x).

然后，显然，我正在生成 c 的具体化版本，c 将包含所有元素对；因此，整个操作大约需要 1000^2 的时间（当我运行查询时，我发现它实际上需要一些时间来计算）。

根据文档，LogicBlox 允许将谓词定义为 "Derived"，但对于 c 它似乎不可能，因为 c 递归自身。

现在，我还尝试在查询或 exec 块中使用 "local predicate" 定义此传递闭包，但没有成功。我尝试过的例子：

query '
   _c(x,y)->int(x),int(y). 
   _c(x,y) <- e(x,y) ; e(x,z),_c(z,y). 
   _(x) <- _c(0,x).'

显然在这个例子中我可以手动优化查询并定义一个块：

f0(x)->int(x). 
f0(y)<- e(0,y) ; f0(x),e(x,y).

但如果我对 LB 的理解正确，应该有一种方法可以将优化留给 LB。

Answer 1

我不确定你如何定义 "datalog solver"，但也许是更好地将 LogicBlox 理解为使用数据日志派生的数据库语言作为其查询语言。

如您所见，LogicBlox 不会自动应用任何类型的类似于魔术集的优化。此外，不幸的是 named "Derived" derivation-type 在您的情况下不起作用，因为它避免了通过内联实现。但是，不可能内联递归谓词。

如果您使用的平台版本早于 4.4.9，那么可以，不幸的是，您唯一的选择是手动执行某种方式魔法对您的逻辑进行转换。

如果您使用的是 LogicBlox 4.4.9 或更新版本，我们添加了一个新的推导类型 "OnDemand" 将执行您想要的操作。它会重写内部谓词的规则，因此只有 "demanded" 计算元组。这和古典魔术不太一样设置重写，类似于所谓的“需求转型”在最近的文献中（见 http://doi.acm.org/10.1145/1836089.1836094).

但是，这仍然需要对您的示例进行小的更改。有必要为谓词的所有键（而不是值）参数提供 "demand"。所以你需要将你的例子重写成

e(x,y) -> int(x), int(y).
e(x, int:mod[x + 1,1000]) <- int:range(0,1000,1,x).
nodes(x) <- e(x, _); e(_, x).

c(x,y) -> int(x), int(y).
c(x,y) <- e(x,y); c(x,z), e(z,y).
//lang:derivationType[`c]="OnDemand".

from0(x) <- c(0,x), nodes(x).

取消注释以上行将应用转换。这产生当运行在我的笔记本电脑上时，大约有 7 倍的加速。

再举个例子，这里是斐波那契函数

fib[i]=f -> int(i), int(f).
lang:derivationType[`fib]="OnDemand".

fib[0]=0.
fib[1]=1.
fib[i]=f1+f2 <- i >= 2, fib[i-1]=f1, fib[i-2]=f2.

我们还使用了"OnDemand"谓词来实现更精细的诸如 CYK 解析或计算 lambda 演算之类的关系和函数。

如何避免 logicblox/logiQL 中递归逻辑谓词的具体化？

How to avoid materialization of recursive logical predicates in logicblox/logiQL?

logicblox

logiql