Re: RL notation

From: Tegiri Nenashi <>
Date: Thu, 7 Feb 2008 17:12:16 -0800 (PST)
Message-ID: <>

On Feb 7, 2:29 pm, Marshall <> wrote:
> > Can we
> > have just one more constant: Universal Equality Relation (denoted as
> > E)? Then `x=y` is defined as E projected to attributes x and y.
> What are the advantages and disadvantages? It doesn't seem
> much different from having = as a logical operator. But maybe
> it is, and equality (and hence substitutibility) exists only in the
> metalanguage. I guess one advantage would be that E would
> then be subject to the regular axioms as any other relation is.

... plus some extra.

> > What abouy
> > incompatible domains, though? If x and z are incompatible, we can't
> > define E projected to x,z as empty. We have to (somewhat counter
> > intuitively) to define x=z as a cartesian product of the domains!
> Can you be specific with what you mean by incompatible domains?

Like {a,b} incompatible with {1,2,3}...

> I would think the domain of the attributes of E would be the
> universal set of whatever is allowed to be in a tuple.

...although as you wrote here this "incompatibility" is mostly a perceived problem.

> (If the
> theory allows nested relations, then it would contain all
> relations; if the theory admits things that aren't relations,
> then it would contain all such things.)

Hmm, I never enlarged the scope of domain values to nested relations! Now I understand what you mean by being able to look at the relational equality as a relation.

> > So we have 5 constants: 00, 01, 10, 11 and E -- sounds too many.
> > Although, 10 and 01 are the least intersting elements of RL, so it is
> > really only 00, 11 and E that matter.
> You at least need 10 and 01 as the lattice top and bottom
> elements, which makes each one the fixpoint and identity
> for meet and join. If we are going to axiomatize the RL
> then we need axioms to say at least this much.

No, the top and bottom are not redundant, they are the least interesting. I can't think of any relational expression (a query, or a constraint) where you need them. Indeed, as soon as we have

R \/ 10

then we just rewrite it as


Likewise the

R /\ 10

is reduced to


Eventually you either get rid of 10, or collapse the expression to a single 10. Ditto for 01. So you can't really express any non vacuous fact about the database with them.

> > I'd suggest operating
> > RL expressions in completely attribute free fascion. Whenever there is
> > an expression and there is a relation with some specific constraints
> > (e.g. having attribute x, or being empty), then it could be rewritten
> > in more general way without these constraints. In principle generality
> > should lead to simplicity....

It actually seems to be easy. Consider the "equality" axiom

R(x,y) /\ `y=z` = R(x,z) /\ `y=z`

Informally, we requre the renaming of the attribute y into z to be consistent with the equality relation `y=z`. So we have three attributes x,y, and z. First of all the fact that attributes are atomic is not significant, we can easily think of "composite" attributes as disjoint sets of attributes! Next if we just agree to call empty relations as "attributes" then we half way to our goal of excluding the concept of attributes altogether. So what constraint to the relations x,y,z do we have? Easy:

x \/ y = 00
x \/ z = 00
y \/ z = 00

They say both that x,y,z are empty, and their set of attributes are disjoint! If you really insist on atomic attributes, then we can define them as atoms in the boolean algebra of the header relations, but again, this is unnecessary constraint.

Next, the next two constraints

R /\ 00 = x /\ y
S /\ 00 = x /\ z

are specify what are the attributes of the two relations R and S. And, finally, the constraint

R /\ (E \/ (y /\ z)) = S /\ (E \/ (y /\ z))

tell us that R and S is essentially "the same" relation,

P.S. I propose small letters for empty relations as a convention. Received on Fri Feb 08 2008 - 02:12:16 CET

Original text of this message