Re: Relational symmetric difference is well defined
From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Mon, 18 Jun 2007 03:11:14 +0200 (CEST)
Message-ID: <Xns9952D7DFB3994vdghher_at_194.177.96.26>
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews: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.
Date: Mon, 18 Jun 2007 03:11:14 +0200 (CEST)
Message-ID: <Xns9952D7DFB3994vdghher_at_194.177.96.26>
Jan Hidders <hidders_at_gmail.com> wrote in news:1182119546.370762.75420_at_n2g2000hse.googlegroups.com:
> On 16 jun, 15:13, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews: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.
> > Where in the formula that I gave did you see second order quantifiers > or quantification over predicates?
Did you actually read and understand this:
"That's fine, but even with substituting a predicate expression for the set expression in the original expression you'd still quantify over predicates"
Yes, your simple formulas expressing set equality are first order allright, but they don't help to make the formula describing a set valued join a first oder expression ! I recall you promised to convert the original set valued join to a first order expression, didnt you ?
> > -- Jan Hidders > > > >Received on Mon Jun 18 2007 - 03:11:14 CEST