Re: Bags vs. Sets

From: vc <boston103_at_hotmail.com>
Date: 28 Jun 2006 18:52:44 -0700
Message-ID: <1151545964.316629.63580_at_x69g2000cwx.googlegroups.com>


vadimtro_at_gmail.com wrote:
> vc wrote:
> > vadimtro_at_gmail.com wrote:
> > > vc wrote:
> > > > That does not look right. Take different values for 'y'.
> > >
> > > OK, let's add a tuple {(x=2,y=2)} so that the relation becomes
> >
> > No, let's just consider {(1,2), (3,4)}. You'd see that there would be
> > 4 defining equations instead if just two as was in the case of {(1,1),
> > (2,1)}.
>
> There are 4 equations indeed
>
> (x-1)(x-3)=0
> (x-1)(y-4)=0
> (y-2)(x-3)=0
> (y-2)(y-4)=0
>
> However, take your favorite computer algebra system, compute Groebner
> basis, and withness that the system reduces to just 2 equations:
>
> (y-2)(y-4)=0
> x-y+1=0
>
> It is easy to see that we need only 2 equations. One defines domain y
> in {2,4}. The other one is linear interpolation polynome y=x+1. There
> would be 2 equations for any binary relation which has functional
> dependency!

Rght, but imagine a real life relation with on average 10 attributes and say cardinality of 50,000. Naively, one would need to end up with 10^50,000-1 equations, or perform 50,000 Buchberger reductions to ten equations at each step.

>
> > My point is that you want to explain to those interested how
> > you recover polynoms from the variety and what computational complexity
> > it would entail, not just say "Can we write those equations explicitly?
> > Sure".
>
> It could be constructed by adding tuples one by one like in the example
> in my previous message. It might be beneficial to apply Buchberger
> algorithm at each step in order to collapse the system.
>
> I haven't research complexity issues. Buchberger algorithm is known to
> be theoretically non-efficient, while it has good behaviour on
> practice.

It woud be interesting to get some data on how realistic it might be (see above).

>
> > > > For example, what field did you have
> > > > in mind when you talked about polynomials ?
> > >
> > > C ? This matter doesn't seem important to me.
> >
> > Then, how do you intend to handle non-numeric domains like strings of
> > characters, or user defined finite domains ?
>
> I expected this question:-) Map them to numbers somehow?

What kind of mapping do you have in mind ?

More importanly, I am not convinced that ideals is a good tool tool to represent bags: killing a fly with a gun, unfamiliar to most mumbo-jumbo, etc. Could you please list some advantages as compared to the "old way" ? Received on Thu Jun 29 2006 - 03:52:44 CEST

Original text of this message