CODEWITHSUNDEEP
turing-completetuple-relational-calculus
Sailaja
Sailaja

Reputation: 141

Tuple relational calculus

Is safe tuple relational calculus a turing complete language?

Upvotes: 7

Views: 2202

Answers (2)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 86023

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

Upvotes: 1

sdcvvc
sdcvvc

Reputation: 25654

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.

Upvotes: 6

Related Questions