# Re: completeness of the relational lattice

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>

Date: Fri, 22 Jun 2007 10:14:56 -0700

Message-ID: <1182532496.024386.251390_at_i13g2000prf.googlegroups.com>

Date: Fri, 22 Jun 2007 10:14:56 -0700

Message-ID: <1182532496.024386.251390_at_i13g2000prf.googlegroups.com>

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 - 19:14:56 CEST