Re: completeness of the relational lattice

On Jun 22, 9:42 am, Jan Hidders <hidd..._at_gmail.com> wrote:

> Marshall schreef:
> > Any expression of the form
>
> > E \/ [x]
>
> > can be rewritten as
>
> > E \/ (X /\ 00)
>
> > where X is any relation with the same header as [x].
>
> ?? Either you can express it or you cannot. Either you can give me an
> expression equivalent to [x] or you cannot. An expression that is only
> equivalent under certain circumstances is not good enough. It means
> your expressive power in terms of queries that you can express drops
> below that of the unions of conjunctive queries (UCQ). If the database
> consists of just R(a,b) then how can I project on {a}, or on {c,d}?

You cannot. If the database consists of just a single nonempty relation R(x,y), then the whole lattice consists just of 4 elements:

00, R(x,y),
00 /\ R(x,y) = 10, and
00 \/ R(x,y) = 01

.
.
.
.
.
.
.
.
.
.

(drumroll)
.
.
.
.
.
.
.
.
.

For all practical purposes here R(x,y) is indistinguisheble from 11. Received on Fri Jun 22 2007 - 12:14:56 CDT