Re: Relational lattice

From: Vadim Tropashko <>
Date: 14 Mar 2005 11:16:41 -0800
Message-ID: <>

Jan Hidders wrote:
> Vadim Tropashko wrote:
> > 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
> >> page:
> >
> > OK, where is the equation?
> It is constructed in the proof of Prop. 7.2. Each of the conditions
> the variable X in the list 1, .., 4 can be expressed with equations.
> > I have difficulty understanding which constructs they admit into
> > algebra and which don't.
> They use in the proof the standard 5 operation of the flat relational
> algbra and furthermore you can use an arbitrary set of extra relation
> variables (which are of course existentially quantified) next to the
> ones in the database and the one that defines the result.
> > The concept of sparce equation also eludes me:-(
> You can ignore that for now. We only look at sets of equations over
> relations that always define a unique result, and those are always
> sparse anyway.

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


which works over 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.

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". Received on Mon Mar 14 2005 - 20:16:41 CET

Original text of this message