Re: Relational symmetric difference is well defined
From: V.J. Kumar <vjkmail_at_gmail.com>
Date: Tue, 19 Jun 2007 16:30:25 +0200 (CEST)
Message-ID: <Xns99546AE332909vdghher_at_194.177.96.26>
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews:1182159542.073157.146030_at_g4g2000hsf.googlegroups.com:
>>
>>
>>
>> > On 18 jun, 03:11, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> Jan Hidders <hidd..._at_gmail.com> wrote
>> >> innews: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.c
>> >> >> >> >> om:
>>
>> >> >> >> >> > 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.googlegroup
>> >> >> >> >> >> s.c om:
>>
>> >> >> >> >> >> > 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?
>>
>> >> [...snip..]
>>
>> >> 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 !
>>
>> > It makes the query that corresponds to the operator of the form
>> > { (x,z) | \phi(x,z) } with \phi a formula in first order logic
>>
>> No, it does not make that. Look, the set valued join was defined
>> as
>>
>> { (x,z)| Px <-> Pz } where Px def. A(x,y) for some fixed x and Pz
>> def. B (y,z) for some fixed z. Px and Pz are predicate variables,
>> that is second order variables. How do you intend to handle 'y' in
>> \phi(x,z) def. A(x,y) <-> B(x,y) so that it would become a first
>> order expression ?
Date: Tue, 19 Jun 2007 16:30:25 +0200 (CEST)
Message-ID: <Xns99546AE332909vdghher_at_194.177.96.26>
Jan Hidders <hidders_at_gmail.com> wrote in news:1182262078.054309.135620_at_n2g2000hse.googlegroups.com:
> On 19 jun, 15:28, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> Jan Hidders <hidd..._at_gmail.com> wrote
>> innews:1182159542.073157.146030_at_g4g2000hsf.googlegroups.com:
>>
>>
>>
>> > On 18 jun, 03:11, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:
>> >> Jan Hidders <hidd..._at_gmail.com> wrote
>> >> innews: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.c
>> >> >> >> >> om:
>>
>> >> >> >> >> > 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.googlegroup
>> >> >> >> >> >> s.c om:
>>
>> >> >> >> >> >> > 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?
>>
>> >> [...snip..]
>>
>> >> 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 !
>>
>> > It makes the query that corresponds to the operator of the form
>> > { (x,z) | \phi(x,z) } with \phi a formula in first order logic
>>
>> No, it does not make that. Look, the set valued join was defined
>> as
>>
>> { (x,z)| Px <-> Pz } where Px def. A(x,y) for some fixed x and Pz
>> def. B (y,z) for some fixed z. Px and Pz are predicate variables,
>> that is second order variables. How do you intend to handle 'y' in
>> \phi(x,z) def. A(x,y) <-> B(x,y) so that it would become a first
>> order expression ?
>
> ?? Do you really want me to spell that out for you?
>
> We start with
>
> (1) {(x,z)| {y|A(x,y)}={y|A(y,z)} }
The original posting contains a typo I think. It should ahve been:
{(x,z)| {y|A(x,y)}={y|B(y,z)} }
> > As already argued the proposition "{y|A(x,y)}={y|A(y,z)}" is > equivalent with the proposition "(Forall y : A(x,y) -> A(y,z)) and > (Forall y : A(y,z) -> A(x,y))". So simple substitution gives us: > > (2) {(x,z)| (Forall y : A(x,y) -> A(y,z)) and (Forall y : A(y,z) -> > A(x,y)) }
The substitution gives:
{(x,z)| (Forall y : A(x,y) <-> B(y,z) }
which is a different query altogether since forall y: A(x,y) <-> B(y,z)
evaluates to true only in trivial cases and does not give a set valued
join which was specified originally with set builder notation ! E.g. if
you have
A:
1 2
B:
2 a
1 3
2 5
2 6
3 a
5 b
6 b
then your formula will produce an empty set instead of {(1 a), (2 b)} !
>
> Voila, a query that corresponds to (1) and of the form { (x,z) |
> \phi(x,z) } with \phi a formula in first order logic.
>
> -- Jan Hidders
>
>
Received on Tue Jun 19 2007 - 16:30:25 CEST