Re: Relational lattice

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:

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.

> In particular, is "Run" a legitimate expression that is allowed as
> left side of equality?

No, "Run" is just the relation that is supposed to be the solution of the construction.

> 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.

> 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.

Yes, and that is why it is a little surprising that it actually is avoidable.

• Jan Hidders