Path: dp-news.maxwell.syr.edu!spool.maxwell.syr.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!postnews.google.com!75g2000cwc.googlegroups.com!not-for-mail
From: vadimtro@gmail.com
Newsgroups: comp.databases.theory
Subject: Re: Bags vs. Sets
Date: 28 Jun 2006 11:08:00 -0700
Organization: http://groups.google.com
Lines: 186
Message-ID: <1151518080.092646.12990@75g2000cwc.googlegroups.com>
References: <1138133065.180926.200290@o13g2000cwo.googlegroups.com>
   <uzwBf.202606$bU4.6928482@phobos.telenet-ops.be>
   <1139077231.689141.257420@o13g2000cwo.googlegroups.com>
   <m3y80rkl73.fsf@mobile.int.cbbrowne.com>
   <1139108326.233924.42880@o13g2000cwo.googlegroups.com>
   <1139168228.005959.200970@z14g2000cwz.googlegroups.com>
   <6aa05$449aa847$50db0a0b$30267@news.hispeed.ch>
   <1151002223.848102.58220@p79g2000cwp.googlegroups.com>
   <1151514091.239068.316460@75g2000cwc.googlegroups.com>
NNTP-Posting-Host: 148.87.1.171
Mime-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
X-Trace: posting.google.com 1151518084 24807 127.0.0.1 (28 Jun 2006 18:08:04 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Wed, 28 Jun 2006 18:08:04 +0000 (UTC)
In-Reply-To: <1151514091.239068.316460@75g2000cwc.googlegroups.com>
User-Agent: G2/0.2
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.1; SV1; .NET CLR 2.0.50727),gzip(gfe),gzip(gfe)
X-HTTP-Via: 1.0 inet-nc02 (NetCache NetApp/5.6.2R1D19)
Complaints-To: groups-abuse@google.com
Injection-Info: 75g2000cwc.googlegroups.com; posting-host=148.87.1.171;
   posting-account=AAOD3A0AAAAyAIYH7_00xqXu9g714b8n
Xref: dp-news.maxwell.syr.edu comp.databases.theory:42525

vc wrote:
> vadimtro@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.