7

Is safe tuple relational calculus a turing complete language?

SQB
  • 3,926
  • 2
  • 28
  • 49
Sailaja
  • 141
  • 5

2 Answers2

6

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.

sdcvvc
  • 25,343
  • 4
  • 66
  • 102
  • 1
    You seem to know more about this than I do, however, why can't the following express that there is a route? edge(x, y) -> route(x, y) edge(x, y) & edge(y, z) -> route(x, z) if the graph is represented as a set of facts about edges, i.e. edge(a, b) & edge(b, c) & edge(c, d) then the query edge(a, d) will be provable by a FOL theorem prover (e.g. a prolog interpreter). – Larry Watanabe Jan 10 '10 at 17:49
  • 1
    You're saying that route is _smallest_ transitive relation satisfying edge(x,y) -> route(x,y). This definition requires least-fixed-point. To define a new relation in tuple calculus, you may use intersection, union, projection... but it is not possible to say "route it is a relation satisfying the following conditions...". You might also quantify over relations, but that's higher-order logic, and quantification is allowed only over individuals in FOL. – sdcvvc Jan 10 '10 at 18:00
  • Thanks for your reply..Its really a useful. – Sailaja Jan 15 '10 at 13:41
1

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).

BlueRaja - Danny Pflughoeft
  • 84,206
  • 33
  • 197
  • 283
  • 2
    Either you are wrong or Larry Watanabe is. I have no idea of the topic, but this is getting interesting to watch! (goes to fetch popcorn) – Carl Smotricz Jan 10 '10 at 17:36
  • Now relational algebra not being Turing Complete is more well-known :) – Larry Watanabe Jan 10 '10 at 17:38
  • However, from reading another poster's link to Codd's theorem, relational algebra is not equivalent to relational calculus - relational algebra is essentially equivalent to propositional logic whereas relational algebra is equivalent to FOL. – Larry Watanabe Jan 10 '10 at 17:44
  • 1
    @Larry: http://en.wikipedia.org/wiki/Relational_calculus - "The relational algebra and the relational calculus are essentially logically equivalent ... This result is known as Codd's theorem." – BlueRaja - Danny Pflughoeft Jan 10 '10 at 18:22