如何避免 logicblox/logiQL 中递归逻辑谓词的具体化?
How to avoid materialization of recursive logical predicates in logicblox/logiQL?
我正在尝试使用 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。
我不确定你如何定义 "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 的功能作为数据记录求解器。我有性能问题,我认为我使用 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。
我不确定你如何定义 "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 演算之类的关系和函数。