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 and
[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;
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;
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 . However, we must switch to polynomial ring which contains both and :
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”:
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
[[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:
[[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.