Oracle FAQ | Your Portal to the Oracle Knowledge Grid |
Home -> Community -> Usenet -> comp.databases.theory -> Re: How is this collection called?
Mikito Harakiri wrote:
> Let '*' be binary aggregation operator.
>
> Then, sets obey the following laws:
>
> a*a=a
> a*b=b*a
> a*(b*c)=(a*b)*c
>
> Bags:
>
> a*a!=a
> a*b=b*a
> a*(b*c)=(a*b)*c
>
> Lists:
>
> a*a!=a
> a*b!=b*a
> a*(b*c)=(a*b)*c
>
> What collection type meets
>
> a*a!=a
> a*b!=b*a
> a*(b*c)!=(a*b)*c
>
You've already seen some examples. The problem is a
bit under-specified, since one has to pick a structure and an aggregation operator, but I'd suggest the merge of two (binary? ordered?) trees, i.e., a * b is the tree formed by making a new node with a as the left child and b as the right child. Obviously none of the laws will be satisfied in general.
We could even invent more laws, like the existence of an identity:
There exists a (unique?) object 1 such that a * 1 = a and/or 1 * a = a
(True for sets under union, true for bags under their "union",
true for lists, true (in one direction) for Michael's stacks, and false for my tree example.)
Inverses are a bit trickier:
For (all|all "nonzero") objects a, there is an object b such that a * b = 1 and/or b * a = 1 (for suitable "1").
(No "natural" collection type + aggregation jumps to mind.)
Of course one could include another operator and ask for distributivity....
Just noodling around when I should be working,
Rick
p.s. One could modify Michael's example and have the collection type be binary search trees and let a * b be delete (somehow) the elements of a and insert them into b.
p.p.s. Is it obvious that I'm teaching data structures this term?
p^3.s. Binomial heaps?
p^4.s. I gotta stop this and start grading. Received on Tue Mar 30 2004 - 19:59:46 CST