Re: TRUE and FALSE values in the relational lattice

On 21 jun, 19:26, Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote:
> On Jun 21, 3:14 am, Jan Hidders <hidd..._at_gmail.com> wrote:
>
> > I would assume the following operations: (in yet another notation)
> > - E * E : natural join
> > - E + E : generalized union
>
> Eh, 3 different people, 3 different notations:-)

Yes, I know, sorry about that, but this is just easier for me to think and type.

> > - [A,B,..D] : the empty relation with header {A, B, ..., D} (possibly
> > the empty set)
>
> This is nice proposal. How abotut small letters for attributes and
> capital letters for relations?

Hadn't thought of that. Yes, I'll try to stick to that.

> One of my (yet not realized) goals is to get rid of the attributes
> completely.

I understand where you are coming from but could we for the moment also have attributes? I'm not sure what will happen to the axiomatization of the (a=b) relations if you change that. And I think changing will only move difficulties and not make them disappear. So can I request to leave them for the moment. Once we have a proof of completeness we might see if we can simplify things. By then the repercussions should be clearer.

> Defining equality relation is an intersting venture by itself. I can
> suggest few identities. Assuming R(x,y)
>
> (((R /\ (y=y') ) \/ [x,y'] ) /\ (y=y') ) \/ [x,y] = R

Indeed, I had bumped into that one too. Very important for completeness.

> > Actually, a (sound and complete) axiomatization would be a small but
> > publishable result. It doesn't seem that impossible either. You could
> > start with showing that you have enough rules to bring the thing into
> > some union normal form, and then show that you also have enough rules
> > to show a homomorfisme over the conjuncts. Quite interesting indeed.
> > Anyone interested in thinking about a paper on that?
>
> This is nice research program. If the other exchange taught any
> lessons, then spelling out every minute detail would be one of them:-)

Great!! :-)

> Could you please clarify (with an example!) what "homomorfism over the
> conjuncts" you have in mind?

A conjunctive query can be thought of as a positive datalog clause of the form

  result(x, y) :- p(x,y,z) & ... & q(x,x) & r(,s,x,z)

If you want to determine subsumption of such queries you can check this by verifying if there is a mapping h from the variables in one clause to the variables of the other that defines a homomorfism in the sense that if one clause contains p(x, y) then the other contains p(h(x), h(y)). An example:

(1) result(x, y) :- p(x, y) & p(x, x) & p(y, y) & p(y, x) (2) result(x, y) :- p(x, y) & p(x, x) & p(y, y) & p(y, x) & p(x, z) & p(z, z)

There is such a homomorfism from (1) to (2) : { x->x, y->y } and also from (2) to (1) : { x->x, y->y, z-> y } so (1) subsumes (2) and vice versa, and they are therefore equivalent.

What I meant is that we need to design the equivalencies such that if there is such an homomorfism of a clause onto itself (e.g. the mapping from (2) to (1) is also a homomorfism from (2) to a proper subset of itself) there should be rules that allow to absorp the redundant part in an algebra expression that corresponds with this. Of course this is very vague, but my intuition is that this is one of the tricky parts.

By the way, the rule that you gave above for equalities is very important for that because it allows you to rename the variables, which is basically what the homomorfism does. So you need it already for just showing that

(3) result(x, y) :- p(x, y) & p(x, x) & p(y, y) & p(y, x) (4) result(u, v) :- p(u, v) & p(u, u) & p(v, v) & p(v, u)

are equivalent.

• Jan Hidders