# Re: completeness of the relational lattice

From: Jan Hidders <hidders_at_gmail.com>
Date: Sat, 23 Jun 2007 13:53:28 -0000

>
>
> 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 /\ []

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]

For completeness we need to show that if two such queries subsume each other we can perform absorption. This is enough because for CQ's it holds that disjunctions of CQ's between which there is no subsumption that they are equivalent iff it describes the same set of CQ's. So what is needed for this? We need to be able to rename the variables, e.g., in the above example we should be able to replace x, y, z with u, v an w, for example. Of course this is only possible because these are projected out afterwards.

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:

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

These would allow us to generate from a disjunct versions with renamed variables and versions where more variables are required to be equal, which are exactly all queries that are subsumed. So if another disjunct is subsumed we can do the reverse, i.e., have absorption.

Until sofar. I hope this made some sense. If have to move to other work now, so I might be less present in the coming days.

• Jan Hidders
Received on Sat Jun 23 2007 - 15:53:28 CEST

Original text of this message