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

Question

我正在尝试使用LogicBlox作为数据日志解算器的功能。我有性能问题，我认为我错误地使用了LB，因为它的行为就好像它正在实现所有的关系(这是具有魔术集的Datalog解算器所不能做到的)。

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

当我只对from0(x) <- c(0，x)感兴趣时，就不需要实体化c，魔术集方法将创建一个谓词c_{bound，free}(x，y)并计算from0(0)，然后派生from0(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。

Answer 1

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

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

如果您使用的是早于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倍的加速。

作为另一个例子，下面是Fibonacci函数

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解析或计算λ演算。