Re: Bags vs. Sets

From: <vadimtro_at_gmail.com>
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

Original text of this message