Re: Relational lattice
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