# Re: Bags vs. Sets

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