# Re: Bags vs. Sets

Date: 28 Jun 2006 11:08:00 -0700

Message-ID: <1151518080.092646.12990_at_75g2000cwc.googlegroups.com>

vc wrote:

*> vadimtro_at_gmail.com wrote:
**> Consider a relation
**> >
**> > {(x=1,y=1),(x=2,y=1)}
**> >
**> > This set can be considered as a set of roots of some system of
**> > polynomial equations. Can we write those equations explicitly? Sure:
**> >
**> > (x-1)*(x-2)=0
**> > (y-1)=0
**> >
**>
*

> 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

{(x=1,y=1),(x=2,y=1),(x=2,y=2)}

The equations for the tuple are

x-2 = 0

y-2 = 0

We have to multiply RHS of every equation for the original relation with the above set:

(x-1)*(x-2)*(x-2)=0 (x-1)*(x-2)*(y-2)=0 (y-1)*(x-2)=0 (y-1)*(y-2)=0

which reduces to

(x-1)*(x-2)=0 (x-2)*(y-1)=0 (y-1)*(y-2)=0

*> > The term for such an object in algebraic geometry is an "affine
*

> > variety".

*>
**> Well, a variety is a set of points, not a set of equations.
**> '{(x=1,y=1),(x=2,y=1)}'
**> is a variety allright.
*

Variety is a set of zeros of a system of polynomial equations.

<snipped>

> See above. Perhaps you are confusing ideals that are generated by a

*> set of polynomials with varieties that are just a set points where
**> such ideals 'vanish' ?
*

...

> Let's fix the terminology first before discussing the above.

Well, if you want to skip this naive introduction of operations upon varieties anf jump to ideals I don't object.

*> > Since we are talking about roots of equations, it is naturally to ask
**> > what about roots of multiplicity greater than one? For instance,
**> >
**> > x^2 = 0
**> >
**> > has root 0 of multiplicity 2. This would be a naive attempt to
**> > introduce bags.
**> >
**> > Unfortunately, the equation
**> >
**> > x^2 = 0
**> >
**> > defines the same variety as
**> >
**> > x = 0
**> >
**> > therefore, varieties are genuine relations.
**> >
**> > The mathematical object that corresponds to a bag is a polynomial
**> > ideal. Ideal is a set of polymomials closed over addition and
*

> > multiplication.

*>
**> Well, no. The structure you have in mind is called a ring. The ideal
**> is a special kind of subring closed with respect to 'external'
**> multiplication.
*

I don't understand this snippet. Can you be please more specific?

*> > The most celebrated mathematical result of 19th century
**> > is Hilbert's basis theorem which says that every ideal has a finite
**> > basis.
**> >
**> > By finding the right mathematical counterpart of a bag we can hope
**> > being able to give consistent definition of bag operations.
**> >
**> > Ideals can be added, multiplied and intersected. The union of ideals
**> > usually is not an ideal since it may not be closed under addition. From
**> > the perspective of algebraic geometry, ideals and varieties are
**> > intimately related: the addition of ideals corresponds to the
**> > intersection of varieties, and the intersection of ideals corresponds
**> > to the union of varieties. Also, the multiplication of ideals
**> > corresponds to the union of varieties. Lets go throug the examples.
**> >
**> > Multiplication of
**> >
**> > <x^2>
**> >
**> > by
**> >
**> > <x^3>
**> >
**> > produces
**> >
**> > <x^5>. In bag language this corresponds to union of {0,0} with {0,0,0}
**> > producing
**> >
**> > {0,0,0,0,0}.
**> >
**> > Intersection of
**> >
**> > <x^2>
**> >
**> > with
**> >
**> > <x^3>
**> >
**> > produces
**> >
**> > <x^3>. In bag language this corresponds to set union of {0,0} with
**> > {0,0,0} producing
**> >
**> > {0,0,0}.
**> >
**> > Addition of
**> >
**> > <x^2>
**> >
**> > with
**> >
**> > <x^3>
**> >
**> > produces
**> >
**> > <x^2>. In bag language this corresponds to set intersection of {0,0}
**> > with {0,0,0} producing {0,0}.
**> >
**> > The analoyy shines in case of one variable. It breaks in case of many.
**> > Consider the addition of
**> >
**> > <x^2>
**> >
**> > with
**> >
**> > <y^3>
**> >
**> > which is
**> >
**> > <x^2,y^3>. In language of bags the corresponding operation is cartesian
**> > product of {x=0,x=0} with {y=0,y=0,y=0}. The bag
**> > {(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0), (x=0,y=0),(x=0,y=0)} is the
**> > expected result, but does it really correspond to the ideal <x^2,y^3>?
**> > There are many reasons why not.
**> >
**> > In classic bag theory if we project
**> > {(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0),(x=0,y=0)} into x we
**> > won't get the original relation {x=0,x=0} back (yet another snag that
**> > challenges usefulness of classic bag theory). In ideal theory the
**> > calculating elimination ideal is analogous to projection operation on
**> > bags. Elimination ideal for <x^2,y^3> is <x^2> -- the original ideal.
**> >
**> > This is as much info as internet posting can hold. A more detailed
**> > paper is due.
**>
*

> While there are some similarities, not surprizingly, between ideal

*> operations and RA, it's unclear what advantage if any the
**> variety/ideal lingo may have.
*

I hope to extend relational algebra with introduction of clean bags semantics and aggregation.

> For example, what field did you have

*> in mind when you talked about polynomials ?
*

C ? This matter doesn't seem important to me. In the relational applications ideals are manufactured from 0-dimensional varieties, not the other way around. Therefore, we don't need fancy algebraic properties, like demanding the field to be algebraically closed. Received on Wed Jun 28 2006 - 20:08:00 CEST