Re: Relational lattice

Jan Hidders wrote:
> The answer to your question is actually in that
> reference. See Remark 7.3 on page 16. If you want to know more, the
> paper by Kolaitis they refer to is actually also on-line: See
Phokion's
> home page:

OK, where is the equation? I have difficulty understanding which constructs they admit into the algebra and which don't. In particular, is "Run" a legitimate expression that is allowed as left side of equality? The concept of sparce equation also eludes me:-(

Here is my attempt. Given a set of edges A(x,y) the equation

(TCA(x,y) join A(y,z)) union A(x,z) = TCA(x,y) [1]

constrains the possible solutions for the transitive closure relation TCA. It strikingly resembles the Absorption law:

(B join A) union A = A

except that variables interchange in the relation heading makes the relation [1] play differently.

Next, the solution of [1] is not unique. We can try making it unique by introducing another relation variable TCA_1 that meets the same equation

(TCA_1(x,y) join A(y,z)) union A(x,z) = TCA_1(x,y) [2]

and demanding that

TCA_1 <= TCA

or, equivalently,

TCA_1 join TCA = TCA [3]

In other words, we are after the "maximal" solution. TCA should be greater or equal than any solution TCA_1 of the equation [2]. (It is unfortunate, and perhaps even confusing, that by trying to reconcile the relational join term with the lattice join I've got A(x,y) <= B(x,y) whenever B is subset of A!)

This solution is not satisfactory, orf course, because of universal quantification over auxiliary variable TCA_1.

There is a vague similarity to some classic undrgraduate level math topics. The equation

TCA = A union A^2 union A^3 union ...

is too similar to

e^x = 1 + x + x^2/2 + x^3/6 + ...

to ignore it. Take x to be an adjacency matrix, and the similarity is even more pronounced. Change arithmetics to tropical to get the analogy literal.

Is there an equation that defines exponentiation? Well, either differential one

d e^x / dx = e^x

or the integral one

integral( e^t, t=-infinity..x ) = e^x

The integral case with its quantification over an auxiliary variable t is a vague indication that, perhaps, quantification in the transitive closure definition is unavoidable.

Regarding the Tarski paper, I searched if he ever mentioned lattice operations, and he seems not. Any relation can be considered as a cylindric set in the space of the "all containing" relation. Join is an intersection of the relation defining cylindric sets, but the union of the 2 cylindric sets is not cylindric! The union can be redefined to become a closed operation, at least 2 ways (D&D or lattice).

One statement of the Van den Bussche paper is intriguing, though. Tarski viewed logic as an extreme form of geometry. What is the geometry of the relational algebra is like? Received on Fri Mar 11 2005 - 23:38:53 CET