Re: Bags vs. Sets

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

Relations should always be reduced, as 10^50,000 is ridiculously large. I'm not able to get any estimate on the polynomial system size however. Here is a radical ideal for the relation with 10 tuples in 3 variables:

  {x = 5, y = 5, z = 5}, {x = 1, y = 1, z = 1}, {y = 2, x = 3, z = 1},

        {y = 4, x = 3, z = 1}, {z = 2, x = 1, y = 1},
        {z = 2, x = 1, y = 2}, {y = 1, z = 4, x = 3},
        {x = 5, y = 2, z = 4}, {y = 4, z = 4, x = 3},
        {y = 2, z = 3, x = 3}

<pre>
  S := [z - 15 z + 85 z - 225 z + 274 z - 120, 2 z y - 14 z y

                              4       3       2               2  2
         + 28 y z - 16 y - 3 z  + 26 z  - 77 z  + 94 z - 40, z  y

                2      2      2                        4       3
         - 5 z y  + 4 y  - 3 z  y + 15 y z - 12 y - 2 z  + 20 z

               2
         - 68 z  + 90 z - 40,

           3       2           4       3       2
        2 y  - 14 y  + 28 y - z  + 10 z  - 35 z  + 50 z - 40, 9 x

              2      2      2                      4      3    2
         + z y  + 5 y  - 9 z  y + 42 y z - 69 y + z  - 4 z  - z  + 25
        ]

• 4 equations only, so that polynomial representation appears not to grow significantly.

Here is couple of amusing manipulations:

1. select all the tuples with x=1:

> gbasis(convert(S ,set) union {x-1},plex(x,y,z)); # polynomial representation

   solve(convert(S ,set) union {x-1},{x,y,z}); # relational representation

          2                                2
        [z  - 3 z + 2, y z - z - 2 y + 2, y  - 3 y + 2, x - 1]

 {x = 1, y = 1, z = 1}, {z = 2, x = 1, y = 1}, {z = 2, x = 1, y = 2}

2. Project the previous result to {x,y}:

i) Eliminate variable x by computing Grobner basis in proper monomial ordering. In our case we can just take a shortcut and notice that we can just trow away "x-1" from the

          2                                2
        [z  - 3 z + 2, y z - z - 2 y + 2, y  - 3 y + 2, x - 1]

ii) > solve({z^2-3*z+2, y*z-z-2*y+2, y^2-3*y+2},{y,z});

            {z = 2, y = 2}, {y = 1, z = 1}, {z = 2, y = 1}

Life is not as simple for bags. If we fing grobner basis -- that would be a radical ideal and duplicate information would be lost.

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

I don't have satisfactory answer yet. Received on Sat Jul 01 2006 - 02:07:02 CEST