Re: Relational lattice

Vadim Tropashko wrote:
>
> I'm confused what does it mean for a set of operators to be
> relationally complete. Is it
>
> 1. All the classic operators should be expressed in terms of the new
> ones. More precisely, given an expression in terms of projection,
> selection, CP, union, and minus, then one have to be able to exhibit an
> equivalent expression in terms of generalized union and join.
>
> or
>
> 2. Given a set of equations in terms of classic operators, one have to
> exhibit an equivalent set of equations in new terms.

The first, but the second one is also Ok provided that you give a syntactic characterization of which sets of equations express queries, i.e., which ones have always a unique solution.

> Clearly 1 is stronger than 2. Set difference equation X=A\B could be
> written as
>
> (A join B) union X = A
> A join B join X = {}

Yep, the last equation can even be replaced with: B join X = {}

>>>sigma_R(x,y) pi(x,y,z) A(w,x,y,z) = pi(x,y,z) sigma_R(x,y)
>>>A(w,x,y,z)
>>
>>Of course. The proof is trivial. You can simply prove it from the
>>set-theoretic definitions. You have a problem with that just because it 
>>is not an algebraic proof?

Absolutely. But if a problem is NP hard or undecidable it will probably stay that way, even if you reformulate it in an algebraic system.

• Jan Hidders