## Relational Algebra with CAS

### January 4, 2016

Two years ago we have ventured into mathematical foundation of relational theory. From algebraic geometry perspective relations were viewed as Finite Varieties. In the followup  we were able to describe functional dependencies via explicit analytic formulas and provide intuitive interpretation of the classic result from database dependency theory — Heath’s theorem. Recent arXiv preprint provides a little more  coherent exposition of those ideas together with some excursion into Quantum Theory.

Here we complement the aforementioned arXiv article with demonstration that your average off-the-shelf Computer Algebra System is actually a [rudimentary] RDBMS. The CAS system of choice is CoCoA.

The starting point is being able to exhibit a system of polynomial equations constraining a relation defined as a set of set of tuples.

Given a binary relation with attributes $x$ and $y$

```[x y]
1 1
2 1
3 2
```

we execute the following series of CoCoA commands. First, we need to specify the polynomial ring:

```Use XY ::= QQ[x,y];
```

Then, list the tuples:

```Points := mat([[1, 1], [2, 1], [3, 2]]);
```

Finally, specify the ideal, and print it out:

```I := IdealOfPoints(XY, Points);
I;
```

The output:

`ideal(y^2 -3*y +2, x*y -x -3*y +3, x^2 -3*x -2*y +4)`

Next, for the second relation:

```[x z]
1 1
2 1
3 1
3 2
```

we execute the series of commands

```Use XZ ::= QQ[x,z];
Points := mat([[1, 1], [2, 1], [3, 1],[3, 2]]);
J := IdealOfPoints(XZ, Points);
J;
```

which outputs

```ideal(z^2 -3*z +2, x*z -x -3*z +3, x^3 -6*x^2 +11*x -6)
```

What is the natural join of the two relations? It is the sum $I+J$. However, we must switch to polynomial ring which contains both $XY$and $XZ$:

```Use XYZ ::= QQ[x,y,z];
I:=ideal(y^2 -3*y +2, x*y -x -3*y +3, x^2 -3*x -2*y +4);
J:=ideal(z^2 -3*z +2, x*z -x -3*z +3, x^3 -6*x^2 +11*x -6);
```

After redefining verbatim both ideals in the larger ring (can it be accomplished easier?), we calculate their “join”:

```I+J;
```

which outputs

```ideal(y^2 -3*y +2, x*y -x -3*y +3, x^2 -3*x -2*y +4,
z^2 -3*z +2, x*z -x -3*z +3, x^3 -6*x^2 +11*x -6)
```

This is, again an ideal of points, which is evident with the command

```RationalSolve(GBasis(I+J));
```
`[[1, 1, 1], [2, 1, 1], [3, 2, 1], [3, 2, 2]]`

Here we leveraged `GBasis` function as a way to convert an ideal into list (because `RationalSolve` accepts a list, not an ideal).

Next, projection is an elimination ideal. Once again, it is zero-dimensional ideal of points, so that a typical database user would like to list the tuples:

```RationalSolve(GBasis(elim(z, I+J)));
```
`[[1, 1], [2, 1], [3, 2]]`

Finally, let’s hint what are counterparts of the rest of RA operations. The set union is the intersection of an ideals. The set difference is colon ideal. The only operation which doesn’t have an obvious analog in polynomial algebra is the least challenging one — renaming.

### 2 Responses to “Relational Algebra with CAS”

1. AntC Says:

Hi Vadim, I’m worried whether this Finite Varieties approach really does correspond to Relational Algebra:
– How to represent DEE or DUM?
– How to represent an empty relation?
(I suppose equations with no solution.)
– How to JOIN DEE to a relation (identity operation)?
– How to JOIN DUM to a relation to get an empty heading?

I’m also worried where in the arXiv paper you “expand [a relation] into larger space spanning the common set of attributes.” The RA doesn’t have an expand operation like that(?)
I suppose you could build it from Cartesian product with of an empty relation with the needed attributes. But that’s a domain-dependent/unsafe query.

What are the semantics for that expand operation, in terms of FOPL? Is it a forall quantification? For example, to expand Q(x, y, z) with attribute w:
forall w. Q(x, y, z)
But what if the domain of w is empty? (Hence my q above about empty relations.)

2. > – How to represent DEE or DUM?
<0> and <1> but since those ideals are living in a
polynomial ring with no variables, they are constants 1 and 0 from the base field

> – How to represent an empty relation?
<1>

> – How to JOIN DEE to a relation (identity operation)?

in CoCoA

ideal(0)+ideal(…)

> – How to JOIN DUM to a relation to get an empty heading?

in CoCoA

ideal(1)+ideal(…)

> I’m also worried where in the arXiv paper you “expand [a relation] into larger
> space spanning the common set of attributes.” The RA doesn’t have an expand
> operation like that(?) I suppose you could build it from Cartesian product with
> of an empty relation with the needed attributes. But that’s a domain-dependent/unsafe query.

This is “implementation detail”, not an operation that is exposed as a part of [relational] algebra

> What are the semantics for that expand operation, in terms of FOPL?
> Is it a forall quantification? For example, to expand Q(x, y, z) with attribute w:
> forall w. Q(x, y, z)
> But what if the domain of w is empty? (Hence my q above about empty relations.)

The operation might be unsafe, but we have to be more concerned where it is used.
Ideal intersection can be defined in pure set-theoretic terms, so there is no danger there.
Ideal sum is also defined without it. Therefore, relational lattice (and hence) relational
algebra of ideals is well defined.