> > Every aggregation function is at least second order: a function that
> > applies a function to the set. So for MIN the function is 'less than',
> > for SUM() the function is 'plus' and so on. In Andl aggregation
> > functions are provided by fold(), which takes a function as an
> > argument.
>
> I want you to know that you hijacked my Saturday. I was bothered about
what
> "first order" and "second order" mean, suspecting that we meant different
> things. After an afternoon with the Oracle of All Knowledge, I think we
were
> talking about different things, and you had a better handle on your end
than
> I did on mine.
>
> I was concerned that we were treading in territory outside first-order
> predicate logic. On review, as Wikipedia explains, HOL deals in another
> beast, namely the quantification of sets of sets.
>
> You were talking about something much simpler, second-order *functions*.
> The input is still a value -- an individual member of a set -- plus
another
> function. As you say, there are many such in SQL. In keeping with the
> language's purpose, the primitive components are not exposed, so it's not
> possible to reconstruct min as FOLD(MIN,X). We can do similar things with
> subqueries, e.g.
Yes, agreed. I was indeed talking about second order functions (a function
that takes a function as an argument). This is well down the scale form the
full 'set of sets' and lambda calculus, but extremely useful. Andl has it,
in this one limited form.
>
> select sum(N) from (select count(*) as N from T group by a) as A
>
> One can imagine that restated as
>
> select F(sum, count, t) from T
>
> where F is defined as taking two functions and a value. I guess that
would
> make F a third-order function.
>
> APL is instructive in this regard. What we usually call operators -- + -
x
> ? -- are termed *functions* in APL, in keeping with their mathematical
> definition. A function that takes a function is called an operator. One
> such is "/", the reduction operator; SUM(t) could be expressed as
Yes, both mentally and in writing I naturally think in terms of functions. I
use 'operator' only to comply with TTM, but I think it adds a layer of
confusion.
>
> +/t
Just so. APL is a good source of ideas for second order functions.
>
> > > 2. Limit, as currently implemented, lies outside the theory because
> > > it doesn't operate on sets.
> >
> > I'll put that one on hold pending a suitable reference or detailed
> > mathematical treatment.
>
> I think I can accept "first(N)" could be a set function, and if SQL dealt
in
> sets, LIMIT would be a deterministic function. But SQL deals in bags, and
> with a couple of odd exceptions -- random(), now() -- all its functions
are
> determistic. LIMIT is not a deterministic function. I'm not sure what
> happens to first order predicate logic in the face of nondeterminism, but
I'm
> sure it's not good.
I was never arguing about the status of LIMIT wrt SQL as a non-relational
'bag' language. I was only ever defending LIMIT as a well-defined relational
operator, which implies SQL with DISTINCT in force.
>
> > Sorry. Your nth() is a second order function
>
> OK.
>
> > The (single-pass) implementation would maintain a temporary table of
> > rows that are 'minimum so far seen', to a maximum of N. It would be an
> > implementers decision what to do with a row equal to one in that table
> > once N has been reached: add it or ignore it?
>
> nth() acts on a single column; it keeps the set of N smallest values, as
you
> say. The answer to your question is "ignore it" because a value equal to
one
> in the set is already a member. Given the input
>
>
> C {1, 1, 2, 2, 2, 3}
>
> min(C) = 1
> nth(C, 1) = {1}
> nth(C, 2) = {1, 2}
>
> I'm not claiming any deep insight, only that nth() would be handy and can
be
> defined mathematically (even if I can't do it).
I don't like NTH() as a name, it's misleading. What is being discussed is a
LOWEST(attribute, N) function with a second argument that is how many. There
is also HIGHEST(attribute, N). It is easily implemented in Andl using FOLD()
and TAKE() [Andl name for LIMIT], but I don't see it as a primitive.
Regards
David M Bennett FACS
Andl - A New Database Language - andl.org
