Re: Relational lattice

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 14 Mar 2005 11:16:41 -0800
Message-ID: <1110827801.062965.41920_at_l41g2000cwc.googlegroups.com>


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
home
> >> page:
> >
> > OK, where is the equation?
>
> It is constructed in the proof of Prop. 7.2. Each of the conditions
over
> the variable X in the list 1, .., 4 can be expressed with equations.
>
> > I have difficulty understanding which constructs they admit into
the
> > 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
flat
> 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

e_min

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