patternMinor
Smallest set of features that would make relational algebra Turing complete
Viewed 0 times
smallestmakerelationalwouldcompletethatturingfeaturesalgebraset
Problem
I'm thinking this should be just one or two things, since lambda calculus is so tiny and still Turing complete.
Probably just recursion (something like "MY_QUERY(param) = select * from param UNION MY_QUERY(DO_SOMETHING_WITH(param))"). But I don't see how I could define aggregate functions with this.
Any idea?
Probably just recursion (something like "MY_QUERY(param) = select * from param UNION MY_QUERY(DO_SOMETHING_WITH(param))"). But I don't see how I could define aggregate functions with this.
Any idea?
Solution
You need just two things: new values and recursion/while.
New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.
Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.
SQL with CTE RECURSIVE is Turing Complete (without stored procedures).
See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.
New values means the ability to execute some external function that returns values that were not already to be found in the database. Obviously most implementations (including SQL) have that.
Recursion/while means the ability to execute a loop or iterative computation that may not terminate. The CTE RECURSIVE feature of SQL is one such.
SQL with CTE RECURSIVE is Turing Complete (without stored procedures).
See the Alice book http://webdam.inria.fr/Alice/ for a detailed treatment.
Context
StackExchange Computer Science Q#14694, answer score: 5
Revisions (0)
No revisions yet.