Re:Expressive Power of SQL (2003) [pdf]
by domparise on Friday November 03, 2017 @10:27AM
(#15619414)
Isn't SQL Turing complete? So imo the question of "how expressive is SQL" is really just "how expressive can SQL be with reasonably useful performance".
[ Parent
| on HN ]
Re:Expressive Power of SQL (2003) [pdf]
by corpMaverick on Friday November 03, 2017 @10:43AM
(#15619521)
From what I can understand (barely) The paper tries to determine if some of the new(2003) SQL3 extensions were really needed.
From the answers here https://stackoverflow.com/questions/900055/is-sql-or-even-ts...
It seems that SQL92 was not Turing complete but it became turing complete later on. Possibly by the same extensions added in SQL3.
Re:Expressive Power of SQL (2003) [pdf]
by MarkusWinand on Friday November 03, 2017 @12:43PM
(#15620483)
The mentioned proof is confirming SQL:2003.
See also: https://wiki.postgresql.org/wiki/Cyclic_Tag_System
I don't think that vanilla SQL defined in older versions of the standard is actually Turing-complete. Most commercial releases included features that made it Turing complete, and my understanding is that the most recent standard includes enough from these features that it's now Turing-complete.
That reminds me of some horrible datbase designs I've seen, where people too enamored with FSMs/petri nets etc. tried to put the "code" into tables…
Sounds like the stuff my code refactoring nightmares are made of. The opposite case is funny too though: I've seen people who fetched and deserialized the entire SQL table and then manually SELECTed by looping over it with a foreach loop and picking the right record =)
They even had their own custom logic to do table JOINs. It involved fetching and deserializing both entire tables with SELECT *, of course.
Relational calculus at its finest, me gusta.