turing-complete - 元组关系演算

Question

安全元组关系演算是图灵完备的语言吗？

Answer 1

让我们忘记安全。根据Codd 定理，关系演算等价于一阶逻辑。FOL 是非常有限的，它不能表示在某个图中存在从 A 点到 B 点的路线（它可以表示从 A 点到 B 点的路线长度有限，例如∃ x ∃y ∃z ∃t route(a,x) and route(x,y) and route(y,z) and route(z,t) and route(t,b) 表示有一条长度为 4 的路线。

有关不同逻辑强度的描述，请参见描述性复杂性。

Answer 2

根据Codd 定理，关系代数和关系演算是等价的。众所周知，关系代数不是图灵完备的，所以关系演算也不是。

[编辑]例如，您不能在关系代数/微积分中进行聚合运算（例如 sum、max）或进行递归查询。见这里（接近尾声）。