0

我正在尝试使用 LogicBlox 作为 Datalog 求解器的功能。我有性能问题，我认为我使用 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) 并计算 from0 (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 允许将谓词定义为“派生”，但对于 c 来说，它似乎不可能作为 c 自身递归。

现在，我还尝试在查询或 exec 块中使用“本地谓词”定义此传递闭包，但没有成功。我试过的例子：

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。

4

1 回答 1

2

我不确定您如何定义“数据记录求解器”，但最好将 LogicBlox 理解为使用数据记录派生语言作为其查询语言的数据库。

正如您所注意到的，LogicBlox 不会自动应用任何类似于魔术集的优化。此外，不幸的是，命名为“Derived”的派生类型在您的情况下不起作用，因为它通过内联避免了物化。但是，不可能内联递归谓词。

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

如果您使用的是 LogicBlox 4.4.9 或更高版本，我们添加了一个新的派生类型“OnDemand”，可以满足您的需求。它将在内部重写谓词的规则，以便计算唯一的“要求”元组。这与经典的魔法集合重写不太一样，并且类似于最近文献中所谓的“需求转换”（参见 http://doi.acm.org/10.1145/1836089.1836094）。

但是，这仍然需要在您的示例中进行一些小的更改。有必要为谓词的所有关键（而不是值）参数提供“需求”。因此，您需要将示例重写为

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 演算。

于 2019-01-17T15:29:40.923 回答