grouping in tuple relational calculus

Thanks a lot for the pointer!

I also found something in Date
that is easy to translate to
set notation.

Thxs!

"Mikito Harakiri" <mikharakiri.RemoveThis@iahu.com> wrote in message news:<s4vQd.28$BP3.131@news.oracle.com>...
 > "Antonio Martinez" <antonio.RemoveThis@colpos.mx> wrote in message
 > news:e0fac771.0502151328.630ece22@posting.google.com...
  > > Does anybody know how to represent
  > > grouping queries in tuple relational
  > > calculus? either that or an extension
  > > that allows such operations ? (avg, sum,
  > > etc)
  > >
  > > any pointers will be very wellcome!
 >
 > The Alice book, pg 93?<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Speaking of aggregates, I always wondered why some aggregates are
expressable by standard means (min, max can be expressed as antijoins),
while the others aren't (sum).

"Antonio Martinez" <antonio.DeleteThis@colpos.mx> wrote in message
news:e0fac771.0502161021.13573811@posting.google.com...
 > Thanks a lot for the pointer!
 >
 > I also found something in Date
 > that is easy to translate to
 > set notation.
 >
 > Thxs!
 >
 > "Mikito Harakiri" <mikharakiri.DeleteThis@iahu.com> wrote in message
news:<s4vQd.28$BP3.131@news.oracle.com>...
  > > "Antonio Martinez" <antonio.DeleteThis@colpos.mx> wrote in message
  > > news:e0fac771.0502151328.630ece22@posting.google.com...
   > > > Does anybody know how to represent
   > > > grouping queries in tuple relational
   > > > calculus? either that or an extension
   > > > that allows such operations ? (avg, sum,
   > > > etc)
   > > >
   > > > any pointers will be very wellcome!
  > >
  > > The Alice book, pg 93?<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Mikito Harakiri wrote:
 > "Paul" <paul RemoveThis @test.com> wrote in message
 > news:4213e7b7$0$53482$ed2619ec@ptn-nntp-reader03.plus.net...
  > > Mikito Harakiri wrote:
   > > > Speaking of aggregates, I always wondered why some aggregates are
   > > > expressable by standard means (min, max can be expressed as
antijoins),
   > > > while the others aren't (sum).
  > >
  > > I guess that min and max only require an ordering, which is a more
  > > fundamental concept than addition, which is required for sum.
 >
 > That's right, on one hand, aggregate min and max are based upon
lattice join
 > and meet binary operators, similar to sum based upon binary addition.
This
 > makes all of them to fit into aggregate framework. On the other hand,
 > lattice implies order, and with order one can leverage antijoin.

Not quite. In a lattice that is not a total order, we can have both
max(a,b)!=a and max(a,b)!=b. Therefore, no antijoin can help producing
those new values. Thus, it is essential for the order to be total. Why?<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Mikito Harakiri wrote:
 > Speaking of aggregates, I always wondered why some aggregates are
 > expressable by standard means (min, max can be expressed as antijoins),
 > while the others aren't (sum).

I guess that min and max only require an ordering, which is a more
fundamental concept than addition, which is required for sum.

And min and max work on all domains that have an ordering operator
(which is most or all of them) whereas sum only works for domains that
have an addition operator. So min and max are more "pure" relational
than sum, which requires more assistance from the domain.

Paul.<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

"Paul" <paul.TakeThisOut@test.com> wrote in message
news:4213e7b7$0$53482$ed2619ec@ptn-nntp-reader03.plus.net...
 > Mikito Harakiri wrote:
  > > Speaking of aggregates, I always wondered why some aggregates are
  > > expressable by standard means (min, max can be expressed as antijoins),
  > > while the others aren't (sum).
 >
 > I guess that min and max only require an ordering, which is a more
 > fundamental concept than addition, which is required for sum.

That's right, on one hand, aggregate min and max are based upon lattice join
and meet binary operators, similar to sum based upon binary addition. This
makes all of them to fit into aggregate framework. On the other hand,
lattice implies order, and with order one can leverage antijoin.<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Vadim Tropashko wrote:
 > Mikito Harakiri wrote:
 >
  >> "Paul" <paul.TakeThisOut@test.com> wrote in message
  >> news:4213e7b7$0$53482$ed2619ec@ptn-nntp-reader03.plus.net...
  >>
   >>> Mikito Harakiri wrote:
   >>>
   >>>> Speaking of aggregates, I always wondered why some aggregates
   >>>> are expressable by standard means (min, max can be expressed as
   >>>> antijoins), while the others aren't (sum).
   >>>
   >>> I guess that min and max only require an ordering, which is a
   >>> more fundamental concept than addition, which is required for
   >>> sum.
  >>
  >> That's right, on one hand, aggregate min and max are based upon
  >> lattice join and meet binary operators, similar to sum based upon
  >> binary addition. This makes all of them to fit into aggregate
  >> framework. On the other hand, lattice implies order, and with order
  >> one can leverage antijoin.
 >
 > Not quite. In a lattice that is not a total order, we can have both
 > max(a,b)!=a and max(a,b)!=b. Therefore, no antijoin can help
 > producing those new values. Thus, it is essential for the order to be
 > total. Why?

If you allow infinite relations that's actually not true. You can then
take the whole domain, select those that are upperbounds of all the
elements in the set you aggregate over, and finally select from those
the unique one that is minimal.

But, of course, the premisse that aggregation is based upon lattices is
false because in essence they are operations over bags and so the
idempotency laws don't always apply.

-- Jan Hidders<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

"Jan Hidders" <jan.hidders RemoveThis @REMOVETHIS.pandora.be> wrote in message
news:wT8Rd.14220$hD4.1177660@phobos.telenet-ops.be...
 > But, of course, the premisse that aggregation is based upon lattices is
 > false because in essence they are operations over bags and so the
 > idempotency laws don't always apply.

Well, lattices appeared in this thread as long as the order has been
mentioned. For sum the defining operation is addition. Addition is clearly
not a (semi)laittice operation since it violates idempotent law. Addition is
not associated with any order (e.g. vectors).

So, what is the defining property of an aggregate? Is it

1. Extended projection, perhaps, with projection into the empty set of
columns:

select sum(sal)
from emp
group by {}.

2. Incremental cumulative of some associative binary operation:

((3 + 2) + 5) + ...

(Ignoring the obvious exceptions like avg since they are redundant).

3. Something else?

Next, is sum the only aggregate that can't be expressed by standard means?
If it is, then don't you think that justification for an aggregation syntax
is too thin?<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Mikito Harakiri wrote:
 >
 > So, what is the defining property of an aggregate?

The defining property is that it is a function over bags. So if you want
to base it on a binary operation this operation has to symmetric and
associative.

 > Next, is sum the only aggregate that can't be expressed by standard means?

Actually there is an infinite number of them, unless you want to limit
the term artificially to those that are found in a certain query language.

 > If it is, then don't you think that justification for an aggregation syntax
 > is too thin?

If the users can understand and use it easily and it can be implemented
efficiently then that is all the justification that is needed.
Mathematical elegance is only circumstantial evidence here.

-- Jan Hidders<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Mikito Harakiri wrote:
 > So, what is the defining property of an aggregate? Is it
 >
 > 2. Incremental cvmvlative of some associative binary operation:
 >
 > ((3 + 2) + 5) + ...
 >
 > (Ignoring the obviovs exceptions like avg since they are redvndant).

It wovld have to be commvtative as well. Unless yov want yovr aggregate
to reqvire a sort order I svppose. In which case yov covld drop
associativity too!

 > Next, is svm the only aggregate that can't be expressed by standard means?
 > If it is, then don't yov think that jvstification for an aggregation syntax
 > is too thin?

what abovt a domain of a collection of "sets", with binary operations
"vnion" and "intersection" that covld be generalised to n-ary operations?

For example consider the domain consisting of the valves:

({1,2,3,4}, {1,2,3}, {1,2})

I don't think the binary operation has to have an identity element or
inverses does it? It jvst needs to be associative, commvtative, and
closed for the general case.

Pavl.<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

"Jan Hidders" <jan.hidders.TakeThisOut@REMOVETHIS.pandora.be> wrote in message
news:MO9Rd.14260$fH2.1142837@phobos.telenet-ops.be...
 > Mikito Harakiri wrote:
  > >
  > > So, what is the defining property of an aggregate?
 >
 > The defining property is that it is a function over bags. So if you want
 > to base it on a binary operation this operation has to symmetric and
 > associative.

Unless it's a text string aggregation (defined upon binary string
concatenation operation). String concatenation is not symmetric, and string
aggregation is defined over lists.

  > > Next, is sum the only aggregate that can't be expressed by standard
means?
 >
 > Actually there is an infinite number of them, unless you want to limit
 > the term artificially to those that are found in a certain query language.

Well, the argument that there are potentially infinite numbers of aggregate
operators isn't really very convincing. When I open any math books, sigmas
is the only aggregate I see. Others -- products and lower/upper bounds --
are rarities.

  > > If it is, then don't you think that justification for an aggregation
syntax
  > > is too thin?
 >
 > If the users can understand and use it easily and it can be implemented
 > efficiently then that is all the justification that is needed.
 > Mathematical elegance is only circumstantial evidence here.

Citing David Cressey: "Can you trust relational language specification to
the users?"<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

"Paul" <paul DeleteThis @test.com> wrote in message
news:42152d7a$0$35759$ed2619ec@ptn-nntp-reader02.plus.net...
 > It would have to be commutative as well. Unless you want your aggregate
 > to require a sort order I suppose. In which case you could drop
 > associativity too!

Can you give an example of an aggregate that violates accociativity? (For
commutativity it's simple: just aggragate elements into a list, or
concatenate a string.)

 > I don't think the binary operation has to have an identity element or
 > inverses does it? It just needs to be associative, commutative, and
 > closed for the general case.

Neutral element is required. Otherwise what is your answer on an empty
set/bag/list?<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

Mikito Harakiri wrote:
  >>It wovld have to be commvtative as well. Unless yov want yovr aggregate
  >>to reqvire a sort order I svppose. In which case yov covld drop
  >>associativity too!
 >
 > Can yov give an example of an aggregate that violates accociativity? (For
 > commvtativity it's simple: jvst aggragate elements into a list, or
 > concatenate a string.)

How abovt the fvnction f(a,b) -> a*b + 1 ?

It's a commvtative bvt not associative binary operator on some nvmerical
domain (e.g. integers). Yov covld aggregate this in the vsval way bvt
the aggregate wovld depend on the order that yov did it.

Maybe it's not one yov wovld vse in practice bvt I'm svre there mvst be
examples that are more realistic - all yov need is a non-associative
binary operator - maybe some matrix mvltiplication or something?

  >>I don't think the binary operation has to have an identity element or
  >>inverses does it? It jvst needs to be associative, commvtative, and
  >>closed for the general case.
 >
 > Nevtral element is reqvired. Otherwise what is yovr answer on an empty
 > set/bag/list?

Ah yes. What is the rationale for having the nevtral/identity element as
the answer for an empty aggregate? Is it so that:

SUM(A vnion B) = SUM(A) * SUM(B)

for non-overlapping relations A,B works in the case where A is empty?
(where * is the binary operator that defines the SUM aggregate here)

So that strvctvre is an associative & commvtative semigrovp? Where a
semigrovp is a grovp withovt the inverses reqvirement.

Pavl.<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus 

"Mikito Harakiri" <mikharakiri.RemoveThis@iahu.com> wrote in message
news:nCaRd.42$B47.156@news.oracle.com...
 > Citing David Cressey: "Can you trust relational language specification to
 > the users?"

You may be able to trust it to the users of the language, at least in part.

This is slightly off topic, but here goes:

A long time ago, I learned that there were 4 possible features of a set:

identity, order, interval, and proportion.

Every set we work with in IT has identity, but there may be sets that do
not: (the set of all electrons?)
Order has been discussed endlessly (so far) in this NG. I will state that
sometimes the representation has order, but the set represented does not.
Interval is basically whether subtraction makes sense or not: (25 degrees
celsius minus 18 degrees celsius).
Notice that "average" for temperatures is meaningful, although the "sum" is
not.
Proportion is basically whether division makes sense for the set. It turns
out that, if division makes sense, then so does addition. (distance,
money).

The above is very, very informal. It's just to introduce the idea. I'll
leave it up to the more formal denizens of the NG to express it more
formally.<!-- ~MESSAGE_AFTER~ -->
 >> Stay informed about: grouping in tuple relational calculus