Re: Relational lattice

From: Jan Hidders <>
Date: Mon, 14 Mar 2005 21:05:57 GMT
Message-ID: <V0nZd.37792$>

Vadim Tropashko wrote:
> Ignoring sparsity brings us back to the "obvious equation algebra
> expression for transitive closure" in the example 4.3. There I see that
> the problem of finding the minimum solution has been solved with
> introduction of an operator
> e_min
> which works over powerset.

It's not really a new operator, because we can express it with the classical operators, so it is actually just some convenient syntactic sugar. That's actually not that hard to see because you can express that in second order logic, so you can also express it in the nested relational algebra plus powerset.

> It seems like the concept of sparse
> equations is merely a way of bringing powerset algebra back to earth to
> operate with normal ("flat") relations.

Well observed. It's sort of a nice middle ground such that you can use the powerful powerset operator in your equations, but avoid the exponential explosion in the final and intermediate results. You can compare it with adding an explicit transitive closure operator, only less ad-hoc.

> Returning back to proposition 7.2, what are the equations for
> conditions 3 and 4? Those conditions have universal quantifiers, which
> is not that much different from universal quantifier that says: "find a
> minimal relation that satisfies the TC recurrence relation".

Oh, but it is very different. The quantifiers in conditions 3 and 4 quantify over *domain values* (or pairs of them, but that doesn't matter much here) so they are first-order quantifiers, and the quantifiers that give you the minimal relation quantify over *relations* which makes the second-order quantifiers. So since they are first-order statements we know that they can be expressed in the flat relational algebra.

I'm afraid I don't have the time to write the exact expressions, but I think you can figure that out for yourself.

  • Jan hidders
Received on Mon Mar 14 2005 - 22:05:57 CET

Original text of this message