Re:Expressive Power of SQL (2003) [pdf]
by YeGoblynQueenne on Friday November 03, 2017 @08:27PM
(#15623154)
>> 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.
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_...