Re: RL notation

From: Marshall <marshall.spight_at_gmail.com>
Date: Thu, 7 Feb 2008 13:10:34 -0800 (PST)

On Feb 7, 12:21 pm, Tegiri Nenashi <TegiriNena..._at_gmail.com> wrote:
> Marshall wrote:
> > Brass tacks:
>
> > X(x) -- the domain
> > R(a, b) -- the relation
>
> > X & (x=a) & (x=b) => R
>
> > X is a relation with one attribute, x.
> > R is a relation with attributes a and b, taken from
> > the members of X
>
> > The phrase "(x=a)" denotes the infinite relation of attributes
> > a and x where a = x. In set builder notation:
>
> > {(x, a) | x in X and x = a}
>
> > "&" is natural join. So
>
> > X & (x=a)
>
> > joins X with (x=a), creating a new relation with attributes x and a.
>
> > X & (x=a) & (x=b)
>
> > does the same thing, so now we have
>
> > {(x, a, b) | x in X and x = a and x = b}
>
> > "=>" is the generalized subset operator. It takes two relation
> > operands, and evaluates to true if the left operand has a
> > superset of the attributes, and a subset of the elements
> > of the right operand.
>
> I suspect only 3 people in the world are comfortable with this
> notation:-)

Certainly the number is very small. :-)

> It is imperfect for at least two reasons:
> 1. Equality relation, is it some kind of constant in the RA? Also the
> "=" symbol in the (a=b) conflicts with the equality among relations.
> Two levels of equality is something people never dealt before?

Ah, you noticed that. I suppose that should not be surprising for someone as deep into parsing as you. What is worse, I write relational equality as if it had precedence lower than &, and the other equality as if it had higher precedence.

In general, I have been trying to completely separate the relational operators and the scalar operators. Eliminating booleans in favor of DEE and DUM has made this easier, but we still have the problem of comparison and equality. If we use => for comparison, this is pleasing because the generalized subset is closely semantically related to implication. (In fact some books write implication with the subset character.) It vaguely feels like it's pointing the wrong way, though. And what's the reverse? <=? That's the usual programming language scalar less-than- or-equal. So maybe it's "=<"? I dunno. Maybe it should be << and >>. And then you still have the = problem, and the precedence thereof.

I'm not even absolutely sure there are two different equalities, though. Maybe there is just the one equality, and we define the relational comparison with it. Vice versa also works. But we need *something* besides just the two lattice operators or we can't compare relations.

> 2. Explicit column variables. Having two sorts of symbols -- realtion
> and attribute variables -- makes RL expressions less pretty.

I don't see any way around it. But I guess your point is that they should be syntactically distinct? Because I can recall you writing similar expressions, but with a different syntax.

X join {(x, y) | x = y}

I would write:

X & x = y

and you might write

X /\ `x=y`

Yes, there is some concern about relation variables and attribute names appearing at the same lexical level in expressions, but my tendency is to believe the brevity is worth the risk. Attributes and variables are all declared ahead of time, after all, so there is no direct source of ambiguity. The one real concern I have is with code changing over time. What if a name that appears free in an expression, and is thereby classified as an attribute name (as y is above) is, in a later version of a file, used at a higher lexical scope, changing the meaning of existing expressions? That seems like a bad thing, so it might be required to declare attributes before use that would otherwise appear free.

Marshall Received on Thu Feb 07 2008 - 15:10:34 CST

Original text of this message