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.

Advertisements

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: