Lambda the Ultimate

The set of operations that can be performed by SQL is roughly the same as the set of operations that can be performed with relational algebra, which has a concise mathematical definition. That said, the set of operations supported by relational algebra is by no means beautiful -- to my knowledge it doesn't have a more beautiful characterization than "whatever operations can be performed by composing relational algebra operations". It is just as ad-hoc as the set of operations supported by SQL. And just like with SQL even the operations that it does support often require hoop jumping and are expressed in inefficient ways. Contrast this with Turing complete languages where the set of operations has a nice characterization as the set of computable functions.

It's a good language design challenge to design a better language for dealing with relations and aggregation of relations.

I wrote a long reply on my blog, since it was rather long and mostly based on my engineering wisdom.

I love this sort of discussion. I think part of getting the hang of SQL is having a good mental model for its quite limited semantic range. One comment, though. It seems to me you use the term "semantic" in a rather restricted sense. The semantics you refer to are the execution semantics of various constructs, but constructs you deemed semantically equivalent in terms of performance, are in fact different as regards their declarative semantics. This distinction, though somewhat old fashioned, is a useful one.

I think the reason is that aggregation operations are not logically monotonic. You can see this in the article you link to which says, "this topic is related to numbering rows". As the Bloom paper says, non-monotonic operations require counting, and counting involves waiting, because such operations have stricter ordering and synchronization requirements. Monotonic operations are much more flexible, can be executed out of order, in parallel, etc.

SQL as a query language was probably (accidentally) designed to encourage monotonic queries, and make it harder to express non-monotonic queries because those tend to be harder to execute efficiently.

Sorry — there was a mistake in my original post: I don't need the empty relation, but the unit relatin, that contains some unit value. Because my projection cannot create tuples.

I think that aggregation and grouping add further structure to relational algebra. To demonstrate this, I'll try to naively develope relational algebra starting from plain ralations over simple values (integers, booleans, and a unit value). Suddenly I'll need lists. (These are just rough ideas...)

Let's look at the signatures of the primitive relational operators, where ‘R’ denotes the type “Relation”, ignoring a schema (I'll use a lot of Haskell-like notation):

    × ∷ R → R → R
    ∪ ∷ R → R → R
    ∩ ∷ R → R → R
    ∖ ∷ R → R → R

All of them are well known. All of them take relations, and return relations, So we safely stay within the domain of ralations over simple values.

We could work with these if we had more relations, but we only have the unit relation

    I ∷ R

which contins a single tuple with a single value distinct from all other values.

So lets add something to create a new relation. Therefore we need to name attributes, and values. That's new, and I'd like to choose a somewhat strange approach to do so:

Let ‘L’ denote the type of expressions in a value-level language that has variables with assignment, numbers, booleans, and the usual operations on them (arithmetics, comparison, ...).

Now, we add projection that applies L-expressions on relations:

    π ∷ L → R → R

For this to make sense, the variables in the L-typed argument correspond to the attributes of the relations: Exactly the variabbles assigned to appear as attribute in the result. And the attributes of the input relation are available as variables in the L-expression. (Ugly: reusing the same name. Bear with me)

Examples:

                        x y
    π{x:=1, y:=2} I  = -----                — creating tuples
                        1 2
      
                                   x
    (π{x:=1} I) ∪ (π{x:=2} I)  =  ---       — creating columns
                                   1
                                   2
                                   
                                                            x z y
    π{ x:=1, z:=2, y:= 3 } I ∪ π{ x:=4, z:=5, y:= 6 } I  = -------
                                                            1 2 3
                                                            4 5 6
                         — construction of abigger table
                                            
                   x z y       x y
    π{x:=x, y:=z} -------  =  -----         — projection as usual
                   1 2 3       1 2
                   4 5 6       4 5

I'm pretty sure that this is enough to construct all relations over the given domain of values.

We can even use this projection to map an operation in the L-language (for example multiplication) over all tuples in a relation:

                       x       x y
    π{ x:=x, y:=2*x } ---  =  -----
                       1       1 2
                       2       2 4

                 x         y 
    π{ y:=x>1 } ---  =  -------
                 1       False 
                 2       True

What about selection?

    σ ∷ L → R → R

like in

                x y       x y
    σ{ x > 4 } -----  =  -----
                1 5       6 9
                6 9

There is something new here! The L-expression is abused to return a value, which decides whether a tuple survives the selection or not. IMHO this is quite different than the uses of L-expressions above: The value returned by the L-expression (formerly a tuple with named attributes) does not end up in the relation, but is rather used to steer its construction! Is this already new structure?

Joining, then (without outer joins) is easy, it can be rewritten as a cross product followed by a selection, as in the following example:

      ⋈{ «predicate» } r1 r2
    =
      σ{ «predicate» } (r1 × r2)

Back to work, selection might be spooky but aggregation and grouping are really scary!

Look at aggregation (I'll use ρ):

    ρ ∷ L → R → R

Again, we need to change the semantics of the L-expression, as we already did for σ: We add a list-structure and functions working on lists to the domain of L. The input relations make their attributes available as lists, and the output relation contains all variables assigned to in the L-expression, which must be singleton values (not lists).

Example:

                                 x y       a b
    ρ{ a := sum x, b := max y } -----  =  -----
                                 1 2       4 5
                                 3 5

So I was just urged to add lists to the value-level language of L-expressons. But that's not to bad, after all we wnated to use functions like ‘sum’ that only make sense on lists.

But that's not enough: Look at grouping (I'll use γ):

    γ ∷ L → R → ?

What should it return? The only thing I can imagine is a list of relations

    γ ∷ L → R → [R]        — Haskell syntax to denote list-type

which definitely adds more structure to our relational algebra language.

            x y         x y     x y
    γ{ x } -----  =  [ ----- , ----- ]
            1 4         1 4     3 5
            3 5         1 6
            1 6

We would even need tools in the proposed relational algebra that operate on lists, e.g., a function

    map ∷ (R → R) → [R] → [R]

that applies its first argument on all relations in a list, and a

    union ∷ [R] → R

that unions all its arguments.

Nested relations would also be an option, then we'd be able to use π again, but we would still need something like ‘union’ to do the unnesting.

By the way, it is not sufficient to identify tuples that form a group, and then to add an identifying attribute. Assume such a γ' as follows, wich identifies groups in a new attribute g:

    γ' ∷ L → R → R
    
             x y       x y g
    γ'{ x } -----  =  -------
             1 4       1 4 1
             3 5       3 5 2
             1 6       1 6 1

We did not win anything! This example is quite trenchant, but it points out one thing: This kind of grouping is not really useful.

So I was just urged to add lists to the relational algebra itself.

With γ, ρ, and functions ‘map’ and ‘union’ we can aggregate groups:

                                                a b
      ( union ∘ map ρ{ x := max a } ∘ γ{ b } ) -----
                                                1 4
                                                2 4
                                                1 5
    =
                                         a b     a b 
      ( union ∘ map ρ{ x := max a } ) [ ----- , ----- ]
                                         1 4     1 5
                                         2 4
    =
                               a b                     a b 
      union [ ρ{ x := max a } ----- , ρ{ x := max a } ----- ]
                               1 4                     1 5
                               2 4
    =
               x      x 
      union [ --- ,  --- ]
               2      1
    =
       x        — Yeah, well, I've lost the grouping attribute, but since it's
      ---         constant in each group, it could be saved by giving it as
       1          maximum in the aggregations: ρ{x:=max a, b:=max b}
       2

A workaround to having lists, map, union, etc. in the relational algebra is to extend all relational operators with a grouping facility, where appropriate.

I am not satisfied.

So, the problem IMO is the designers of SQL forgot to implement argmax() and argmin(). (Wikipedia) Such a command should have little significant overhead beyond max() and min().

Such a query as you desire could then be written as:

SELECT * FROM (SELECT key_a, argmax(the_value, key_b) AS key_b FROM the_table GROUP BY key_a) a NATURAL JOIN the_table;

And you need only a simple peephole optimization to recognize the pattern of the NATURAL JOIN with the entire table to transform this into an O(n) operation.