Re: more closed-world chatter

On May 9, 2:21 am, Jon Heggland <jon.heggl..._at_idi.ntnu.no> wrote:
> Marshall wrote:
> > On May 7, 4:15 am, Jon Heggland <jon.heggl..._at_idi.ntnu.no> wrote:
> >> The crux of the matter in that prescription is the equivalence between
> >> R1 & R2 and R1 - (R1 - R2). How do you handle that?
>
> > On further reflection, I don't think they're equivalent.
> > We would say two expressions e1 and e2 on variables
> > A and B were equivalent if
>
> > forall A: forall B: e1(A) = e2(B)
>
> > But that's clearly not the case here. All we have here is
>
> > exists A: exists B: e1(A) = e2(B)
>
> > And that's not a very strong claim. By those criteria,
> > we could say that sqrt(x) and x/2 were equivalent,
> > because, you know, 4. The fact that there is a *category*
> > of A and B values for which the equation holds is
> > a distraction, and not compelling.
>
> I'm not sure I understand. Are you disputing the equivalence
> of the set intersection A INTERSECT B and the difference
> A MINUS (A MINUS B)?
Well, the earlier question was, given

R1(a:t1)
R2(a:t2)

what is the type of a in R1 join R2?

TTM says most-specific-supertype(t1, t2); I say least-specific-subtype(t1, t2).

This to me is the primary question. There are other, related questions as well, but this is the most important one, as it affects join, which I consider to be the most important relational operator.

> Or are you pointing out that the equivalence only
> holds if the join R1 & R2 actually is an intersection?
> If so, sorry about not saying that explicitly, but I
> considered that obvious from the context of the IM
> prescription we're discussing; and anyway, I don't
> see what difference it makes.

I went back and reread IM 13 before I posted, so I was keying off of that.

It definitely makes a difference. The difference means the two expressions are *not* logically equivalent. For them to be equivalent, they have to produce the same result for *all* operands, and they don't.

Consider rational numbers and integers. Integers are a special case of rational numbers. Consider rational and integer multiplication:

  *r : ratio, ratio -> ratio

The result type *has* to be at least ratio, because there are rational operands that, when multiplied, yield non-integers.

  1/2 *r 1/3 = 1/6

Now the integer case:

  *i : int, int -> ?

All the argument that apply to relationship between join and intersection apply to *r and *i. The second is a special case of the first, applicable only for a subset of its domain. So what is the result type of *i? If we follow the logic used in IM 13, we would have to say ratio: (2 *i 3) is just a special case of (2 *r 3) . But this declaration won't make anyone happy:

  *i : int, int -> ratio

because in fact, every result of *i will be an integer, and declaring it to be a ratio just because that's what *r does is throwing away valuable information. (In fact, if we go that route, probably every arithmetic operator will be required to return complex real. So 1 + 1 = 2.0+0.0i)

>D&D's point is that intersection is a special case of join,
> as well as a special case of difference, so the rules
> for type inference ought to produce the same result
> in all three cases.

Right; and I disagree. "Special case" does not imply logical equivalence, nor any particular obligation on the codomain of functions.

> Or are you saying that it is (or might be) okay if expressions
> that are equivalent (e.g. the intersection/minus above;
> or T WHERE FALSE / T JOIN TABLE_DUM) have
> different types? That sounds like undermining the
> concept of equivalence, and possibly optimiser-inhibiting ...

(Under the relational lattice, T WHERE FALSE and T JOIN TABLE_DUM are not merely equivalent, but are actually the same expression. The RL WHERE is JOIN, and the RL FALSE is TABLE_DUM.)

As to A INTERSECT B and A \ (A \ B), I would again draw an arithmetic comparison. On the natural numbers, what the type of a + b? Is it natural, or integer? I would say natural. However, subtraction of naturals is not closed; the result type has to be integer. So a - (0-b) will have the result type integer.

(My above reasoning might only apply in situations where inverse operators are used. + and * are more "well-behaved" than - and /.)

> > We could try to rephrase the issue in terms of unary
> > relations, intersection, and subtraction, but that wouldn't
> > be very interesting, because we don't care much about
> > operators that only work on unary relations.
>
> You've lost me here, too. Why only unary relations?

I wasn't thinking clearly. INTERSECT and MINUS are not limited to unary relation operands, but rather to pairs of operands with the same headers.

My feeling is that INTERSECT isn't worthy of much inspection, because it's not a generic relational operator and it can't do anything that we can't already do with generic relational operators. The same goes for specialized MINUS. Generalized MINUS, on the other
hand, is worthy of attention.

Marshall Received on Wed May 09 2007 - 19:52:01 CEST