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

Date: 30 Jun 2006 17:07:02 -0700

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
]
```

</pre>
• 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