Re: more closed-world chatter

From: Brian Selzer <brian_at_selzer-software.com>
Date: Fri, 11 May 2007 04:37:45 GMT
Message-ID: <tqS0i.882$y_7.359@newssvr27.news.prodigy.net>

"Marshall" <marshall.spight_at_gmail.com> wrote in message news:1178846755.641936.72930_at_l77g2000hsb.googlegroups.com...

> On May 10, 4:30 pm, "Brian Selzer" <b..._at_selzer-software.com> wrote:

>> "Marshall" <marshall.spi..._at_gmail.com> wrote in message
>>
>> news:1178830018.178288.305420_at_p77g2000hsh.googlegroups.com...
>>
>>
>>
>> > On May 9, 11:20 pm, "Brian Selzer" <b..._at_selzer-software.com> wrote:
>> >> "Marshall" <marshall.spi..._at_gmail.com> wrote in message
>>
>> >> > 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 could be wrong, but I think that t1 must be either a supertype or a
>> >> subtype of t2. If that were not true, then due to specialization by
>> >> constraint, the sets of elements for t1 and t2 must be disjoint, and
>> >> any
>> >> join would necessarily be empty.
>>
>> > Sure. However you say it like there are several cases at
>> > work here, and I think it's important to note that there
>> > is just one, which (as is the case with all operations) will
>> > produce different results depending on the operand values.
>>
>> I'm having trouble understanding your response here.

>
> The definition of join:
>
> R1{a, ab}
> R2{ab,b}
>
> (Here, a, ab, and b are *sets* of attributes)
>
> R1 join R2 =
>  {(a, ab, b) | (a, ab) in R1 and (ab,b) in R2}
>
> Note that no type system need be present. Note
> that even if pi_ab(R1) intersect pi_ab(R2) is empty,
> this is still the definition. There isn't any special
> handling for any special cases.
>
>

You're absolutely right. I agree with you. Domains are not types.

>> >> Each and every value must have one and
>> >> only one most specific subtype.
>>
>> > Yeah, everyone says that. It's common point in type
>> > theory. But it's not true in set theory, unless we
>> > consider it in the degenerate case where every
>> > values belong most specifically to the set containing
>> > only itself.
>>
>> > Programming language types are usually expressed as
>> > named sets of values with some common structure, but
>> > neither consideration exists in set theory. I speculate
>> > that we could just use unrestricted axiomatic set theory
>> > instead of type theory, and be able to express much
>> > more sophisticated theorems about source code.
>>
>> > Of course, this comes at a cost in complexity and
>> > decidability, but I think it's worth exploring.
>>
>> I think domains and types are orthogonal. A domains is a set of values,
>> and
>> each value in a domain has a type, but that doesn't mean that every value
>> in
>> a domain must have the same type. If that is a requirement, then it can
>> be
>> stated in the schema.

>
> Interesting!
>

Indeed. Domains are sets of values; types are sets of constraints.

>

>> >> So the type of a in R1 join R2 would be the
>> >> type, t1 or t2, that happens to be the supertype.
>>
>> > Yes, that's the D&D view. Not my view though.
>>
>> If you acknowledge the subtype-supertype relationship between t1 and t2,
>> then the supertype must be the type of a in the result of the join.
>> Consider the relations,
>> R1{a:t1, b} and R2{a:t2, c}.
>> Now assume that a:t1 is the key for R1 and a:t2 is the key for R2. Then
>> these functional dependencies apply to R1 and R2 respectively:
>>
>> a:t1 --> b
>> a:t2 --> c.
>>
>> In a join of R1 and R2, the functional dependencies
>>
>> a --> b
>> a --> c
>>
>> apply. Now if t1 is a subtype of t2, and if t1 is the type of a in the
>> join, then we have,
>>
>> a:t1 --> b
>> a:t1 --> c
>>
>> So in effect, values having type t1 could determine values for c. This
>> makes no sense because that relationship is not stated in the schema.

>
> It makes perfect sense to me. Can you be more specific about
> your objection than "it doesn't make sense." I also mention
> that the result *value* will be the same regardless of whether
> a has type t1 or t2 in the result.
>

After further reflection, I've discovered that you're right: the subtype definition between t1 and t2 indicates that the set of all values that have type t1 is a subset of the set of all values that have type t2. Since t2 defines a larger set of values than t1 does, the dependencies,

a:t2 --> b
a:t2 --> c

would be too broad for the result of the join.

>
> Marshall
> 

Received on Thu May 10 2007 - 23:37:45 CDT