元组关系演算
安全元组关系演算是图灵完备语言吗？
Is safe tuple relational calculus a turing complete language?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
安全元组关系演算是图灵完备语言吗？
Is safe tuple relational calculus a turing complete language?
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
发布评论
评论（2）
让我们忘记安全吧。根据Codd定理，关系微积分等价于一阶逻辑。 FOL的局限性很大，它不能表达某些图中从A点到B点有一条路线的事实（它可以表达在有限长度内从A点到B点有一条路线的事实，例如∃ x ∃y ∃z ∃t 路线（a，x）和路线（x，y）和路线（y，z）和路线（z，t）和路线（t，b）意味着有一条长度为4）的路线。
请参阅描述性复杂性，了解不同逻辑的强度的描述。
Let's forget about safety. By Codd's theorem, relational calculus is equivalent to first order logic. FOL is very limited, it can't express the fact that there's a route from a point A to point B in some graph (it can express the fact that there's a route from a point A to point B in limited length, for example ∃x ∃y ∃z ∃t route(a,x) and route(x,y) and route(y,z) and route(z,t) and route(t,b) means there's a route of length 4).
See descriptive complexity for a description of what is the strength of different logics.
根据科德定理，关系代数和关系微积分是等价的。众所周知，关系代数不是图灵完备的，关系微积分也不是图灵完备的。
[编辑] 例如，您无法在关系代数/微积分中执行聚合运算（例如求和、最大值）或进行递归查询。请参阅此处（接近尾声） 。
According to Codd's Theorem, relational algebra and relational calculus are equivalent. It is well-known that relational algebra is not Turing Complete, so neither is relational calculus.
[Edit] You cannot, for instance, do aggregate operations (such as sum, max) or make recursive queries in relational algebra/calculus. See here (near the end).