Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Expressive Power of SQL (2003) [pdf]

homepages.inf.ed.ac.uk

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Expressive Power of SQL (2003) [pdf]

#11

Post by MarkusWinand »

corpMaverick wrote: post #5
domparise wrote: post #3

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

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.

The mentioned proof is confirming SQL:2003.

See also: https://wiki.postgresql.org/wiki/Cyclic_Tag_System

Re: Expressive Power of SQL (2003) [pdf]

#12

Post by nerdponx »

dspillett wrote: post #4
numbsafari wrote: post #2

Interesting to note that neither BigQuery, nor Apache Presto (and therefore AWS Athena), support recursive CTEs. However, most other DBs do (e.g. Postgres, MS SQL, MySQL 8.0, MariaDB 10.2, Oracle, etc.). Which is disappointing, given how powerful BQ and Presto/Athena are for startups.

Be careful with CTEs with regard to performance, some SQL DBs can optimise by pushing predicates through to the inner queries, where for some (postgres being the one example that I know but there are probably others) a CTE presents an optimisation fence.

I never understood this. Why can't CTEs be transparently compiled into subqueries?

Re: Expressive Power of SQL (2003) [pdf]

#13

Post by kafkaesq »

domparise wrote: post #3

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

Isn't SQL Turing complete?

Even if it is -- "turing complete" != "expressive".

They're rather different beasties, in fact.

Re: Expressive Power of SQL (2003) [pdf]

#14

Post by dspillett »

nerdponx wrote: post #12
dspillett wrote: post #4

Earlier quoted context omitted.

Be careful with CTEs with regard to performance, some SQL DBs can optimise by pushing predicates through to the inner queries, where for some (postgres being the one example that I know but there are probably others) a CTE presents an optimisation fence.

I never understood this. Why can't CTEs be transparently compiled into subqueries?

There is plenty of discussion about it out there (search for "postgres cte optimisation fence") including official word.

Note though that simply replacing CTE references with appropriate sub-queries simply won't work in the recursive case, and in some cases where a CTE is referred to multiple times the result may be an even less optimal query plan.

Re: Expressive Power of SQL (2003) [pdf]

#15

Post by __coaxialcabal »

numbsafari wrote: post #2

Interesting to note that neither BigQuery, nor Apache Presto (and therefore AWS Athena), support recursive CTEs. However, most other DBs do (e.g. Postgres, MS SQL, MySQL 8.0, MariaDB 10.2, Oracle, etc.). Which is disappointing, given how powerful BQ and Presto/Athena are for startups.

Recursive CTEs are significantly more difficult to implement in an MPP platform than SMP.

Re: Expressive Power of SQL (2003) [pdf]

#16

Post by Kenji »

mhd wrote: post #7
domparise wrote: post #3

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

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.

Re: Expressive Power of SQL (2003) [pdf]

#17

Post by kwillets »

numbsafari wrote: post #2

Interesting to note that neither BigQuery, nor Apache Presto (and therefore AWS Athena), support recursive CTEs. However, most other DBs do (e.g. Postgres, MS SQL, MySQL 8.0, MariaDB 10.2, Oracle, etc.). Which is disappointing, given how powerful BQ and Presto/Athena are for startups.

To be fair, neither does Vertica. The big data warehouses are expecting fairly flat predigested fact tables.

Re: Expressive Power of SQL (2003) [pdf]

#18

Post by __coaxialcabal »

kwillets wrote: post #17
numbsafari wrote: post #2

Interesting to note that neither BigQuery, nor Apache Presto (and therefore AWS Athena), support recursive CTEs. However, most other DBs do (e.g. Postgres, MS SQL, MySQL 8.0, MariaDB 10.2, Oracle, etc.). Which is disappointing, given how powerful BQ and Presto/Athena are for startups.

To be fair, neither does Vertica. The big data warehouses are expecting fairly flat predigested fact tables.

Recursive CTEs have been implemented as UDx in Vertica, although possibly not available publicly. This is where you need to look carefully at can vs. should and carefully consider what you are trying to accomplish.

Re: Expressive Power of SQL (2003) [pdf]

#19

Post by YeGoblynQueenne »

>> However, logicians proved it long time ago that first-order logic, and thus relational calculus, cannot compare cardinalities of relations, and yet we have a very simple SQL query doing precisely that.

I'm not sure what the bit about comparing cardinalities refers to. I think it relates to Trakhtenbrot's theorem, or the Löwenheim–Skolem theorem, but I'd appreciate it if someone clarified this.

As it is, my intuition is that the result mentioned is for either finite or infinite relations, or in any case for some broad case of unrestricted sentences (any formula in any language), whereas there are restricted cases where it doesn't hold (sort of like satisfiability).

Like I say, if anyone knows what this refers to, please speak up.

____________________

[1] https://en.wikipedia.org/wiki/Trakhtenbrot%27s_theorem

[2] https://en.wikipedia.org/wiki/L%C3%B6wenheim%E2%80%93Skolem_...

Re: Expressive Power of SQL (2003) [pdf]

#20

Post by [deleted] »

dspillett wrote: post #14
nerdponx wrote: post #12

Earlier quoted context omitted.

I never understood this. Why can't CTEs be transparently compiled into subqueries?

There is plenty of discussion about it out there (search for "postgres cte optimisation fence") including official word. Note though that simply replacing CTE references with appropriate sub-queries simply won't work in the recursive case, and in some cases where a CTE is referred to multiple times the result may be an even less optimal query plan.

[deleted]
Post reply on HN