# Re: completeness of the relational lattice

Date: Sat, 23 Jun 2007 13:53:28 -0000

Message-ID: <1182606808.002178.145700_at_n2g2000hse.googlegroups.com>

On 23 jun, 02:53, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:

*>
**>
*

> I cleared my confusion. What would be the result of join betwwen empty

*> relation R and empty relation S with disjoint attributes? 00, of
**> course.
*

Sure? I would describe that as [H1] /\ [H2] wich is equivalent to [H3] where H3 is the union of H1 and H2, wich would not be empty.

E ::= R | E /\ E | E \/ E | 11 | [H] | 'x=y'

I allow H to be empty, so I omitted 00 = [], 01 = 11 \/ [] and 10 = 11 /\ []

Conjecture: we have enough rewrite rules to achieve this normal form.

Some of the disjuncts will be conjunctive queries (CQ) and some will not. There are three reasons why some are not in CQ: (1) the result may be always empty, (2) the result is (infinitely) wide and (3) the result is (infinitely) long.

Conjecture: if a disjunct always returns an empty result it can be rewritten to []

That would take care disjuntionts with problem (1). For the other two problems I conjecture the following:

Conjecture: if a disjunct returns a wide or long result it can be rewritten to r /\ W or r /\ W /\ 11 where r is a query in CQ and W a conjunction of 'x=y's such that x and y are not in A(r).

If this holds then we can probably split the problem in showing completeness for queries in CQ and for special queries such as W.

Conjecture: the rewrite rules are complete for boolean combinations of 'x=y's

So we can the concentrate on expressions that represent normal CQ's. We can think of those queries as expressed by Horn clauses or:

{ (c=x d=y) | R(a=x, b=x) /\ S(a=x, b=y) /\ T(a=y, b=z) }

In fact you might read that as a shorthand for our algebra where for
example

- S(a=x, b=y) denotes (S /\ 'a=x' /\ 'b=y') \/ [x,y]
- { (c=x d=y) | r } denotes (r /\ 'c=x' /\ 'd=y') \/ [c,d]

Conjecture: all disjuncts in CQ can be written in this form

Conjecture: the variables can be renamed with the rewriting rules.

Probably this requires that we have or can derive a rule like:

r /\ [H] = (r /\ 'x=y') \/ [H] where x and y not in H, and x in A(r) and y not in A(r)

We should also be able to make two variables the same:

r /\ [H] = ((r /\ 'x=y') \/ r) \/ [H]

Also needed is a rule to merge two queries:

{ (c=x d=y) | r1 } \/ { (c=x d=y) | r2 } = { (c=x d=y) | r1 \/ r2 }

- Jan Hidders