Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: Bags vs. Sets

# Re: Bags vs. Sets

From: vc <boston103_at_hotmail.com>
Date: 28 Jun 2006 10:01:31 -0700

> Peter Liedermann wrote:
> > bags can be represented by means of set theory, can't they?
>
> Peter Liedermann wrote:
> > but bags can be represented by means of set theory, can't they?
>
> There is an interesting mathematics behind both concepts. Let's shift
> pespective from set-theoretic into algebraic and focus upon
> multivariate polynomials. 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'.

> 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.

>(Finite) relations essentially are 0-dimensional affine
> varieties. (BTW, this is the ultimate
> answer to ignorants who claim that relations are 2-dimensional:-)
>
> Let's give some example of 1-dimensional affine variety:
>
> x-y=0
>
> This is a familiar x=y predicate. (It is 1-dimensional because we can
> parameterize the set of roots of the equation x-y=0 with a single
> parameter).
>
> Next, consider a set which is not a variety:
>
> (x-1)*(x-2)<=0
>
> This is ax interval {x in [1,2]}, and I speculate that the challenge of
> modelling temporal and spatial domains is anchored to the fact that we
> have to give up some nice properties of algebraic varieties.
>
> Next, there are set theoretic operations upon varieties. Intersection
> of varieties is just combining their defining equations:
>
> (x-1)*(x-2)=0
> (y-1)=0
>
> intersect
>
> x-y=0
>
> is
>
> (x-1)*(x-2)=0
> (y-1)=0
> x-y=0
>
> which reduces to
>
> (x-1)=0
> (y-1)=0

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' ?

>
> Intersection of varieties corresponds in relational language to join.
> In our example we joined finite relation {(x=1,y=1),(x=2,y=1)} with
> predicate {x=y} which in RA terms is the selection.
>
> Next, a set of equations for a union of varieties A and B is build by
> coupling each equation from A with that of B. For example, a union of
>
> (x-1)*(x-2)=0
> (y-1)=0
>
> and
>
> (y-2)=0
>
> is
>
> (x-1)*(x-2)*(y-2)=0
> (y-1)*(y-2)=0

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

>
> Even though union operands are 0-dimensional varieties, the result is
> not a 0-dimensional variety, which translates into the corresponding
> relation being no longer finite. The result is finite when both
> varieties are defined in the same space (that is the same set of
> variables). This is a familiar D&D union operator.
>
> 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.

> 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}.
>
>
> <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.
>
> <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. For example, what field did you have in mind when you talked about polynomials ? Received on Wed Jun 28 2006 - 12:01:31 CDT

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US