Re: Relational symmetric difference is well defined
From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Sat, 16 Jun 2007 15:13:19 +0200 (CEST)
Message-ID: <Xns99515E25CE122vdghher_at_194.177.96.26>
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews:1181919464.037821.176760_at_p77g2000hsh.googlegroups.com:
>>
>>
>>
>> > On 15 jun, 16:00, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> Jan Hidders <hidd..._at_gmail.com> wrote
>> >> innews:1181910061.495472.280190_at_c77g2000hse.googlegroups.com:
>>
>> >> > On 1 jun, 03:40, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> >> Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote
>> >> >> innews:1180628927.976321.267880_at_a26g2000pre.googlegroups.com:
>>
>> >> >> > On May 30, 8:52 pm, Marshall <marshall.spi..._at_gmail.com>
>> >> >> > wrote:
>> >> >> >> Can you clarify the difference between set containment join
>> >> >> >> and set equality join? The inverse of join is much on my
>> >> >> >> mind these days.
>>
>> >> >> > Set equality join
>>
>> >> >> > A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}={y|A(y,z)} }
>>
>> >> >> > Set containment join
>>
>> >> >> > A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}>{y|A(y,z)} }
>>
>> >> >> > where the ">" is "subset of".
>>
>> >> >> The above formulas obviously are no longer first-order
>> >> >> expressions. Along with the increased expressive power (e.g.
>> >> >> it's trivial to define a powerset), you will reap the usual
>> >> >> drawbacks of the higher order logic.
>>
>> >> > This was perhaps already clear, but it is the *formulation* of
>> >> > the semantics which is not first-order. The semantics themselves
>> >> > are clearly first order since they can be defined in first order
>> >> > logic or the flat relational algebra.
>>
>> >> This is very intriguing !
>>
>> > Not really. It is pretty obvious that in the above formulation of
>> > the semantics of the joins you can replace the higher order
>> > expression with a first order formula.
>>
>> How ?
Date: Sat, 16 Jun 2007 15:13:19 +0200 (CEST)
Message-ID: <Xns99515E25CE122vdghher_at_194.177.96.26>
Jan Hidders <hidders_at_gmail.com> wrote in news:1181948397.949921.43300_at_n2g2000hse.googlegroups.com:
> On 15 jun, 23:17, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews:1181919464.037821.176760_at_p77g2000hsh.googlegroups.com:
>>
>>
>>
>> > On 15 jun, 16:00, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> Jan Hidders <hidd..._at_gmail.com> wrote
>> >> innews:1181910061.495472.280190_at_c77g2000hse.googlegroups.com:
>>
>> >> > On 1 jun, 03:40, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> >> Vadim Tropashko <vadimtro_inva..._at_yahoo.com> wrote
>> >> >> innews:1180628927.976321.267880_at_a26g2000pre.googlegroups.com:
>>
>> >> >> > On May 30, 8:52 pm, Marshall <marshall.spi..._at_gmail.com>
>> >> >> > wrote:
>> >> >> >> Can you clarify the difference between set containment join
>> >> >> >> and set equality join? The inverse of join is much on my
>> >> >> >> mind these days.
>>
>> >> >> > Set equality join
>>
>> >> >> > A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}={y|A(y,z)} }
>>
>> >> >> > Set containment join
>>
>> >> >> > A(x,y)/=B(y,z) is {(x,z)| {y|A(x,y)}>{y|A(y,z)} }
>>
>> >> >> > where the ">" is "subset of".
>>
>> >> >> The above formulas obviously are no longer first-order
>> >> >> expressions. Along with the increased expressive power (e.g.
>> >> >> it's trivial to define a powerset), you will reap the usual
>> >> >> drawbacks of the higher order logic.
>>
>> >> > This was perhaps already clear, but it is the *formulation* of
>> >> > the semantics which is not first-order. The semantics themselves
>> >> > are clearly first order since they can be defined in first order
>> >> > logic or the flat relational algebra.
>>
>> >> This is very intriguing !
>>
>> > Not really. It is pretty obvious that in the above formulation of
>> > the semantics of the joins you can replace the higher order
>> > expression with a first order formula.
>>
>> How ?
>
> For example, the formula
>
> {y|A(x,y)}={y|A(y,z)}
>
> is equivalent with
>
> (Forall y : A(x,y) -> A(y,z)) and (Forall y : A(y,z) -> A(x,y))
That's fine, but even with substituting a predicate expression for the set expression in the original expression you'd still quantify over predicates which is another way of saying 'over sets':
{x| (setA = setB)} is no different from {x| (A <=>B)} because forall (setA=setB) is the same like forall(A<=B), so you are still dealing with the second order quantification.
> > -- Jan Hidders > >Received on Sat Jun 16 2007 - 15:13:19 CEST