# Re: Relational symmetric difference is well defined

From: V.J. Kumar <vjkmail_at_gmail.com>

Date: Tue, 19 Jun 2007 15:28:56 +0200 (CEST)

Message-ID: <Xns9954607668228vdghher_at_194.177.96.26>

>> > On 16 jun, 15:13, "V.J. Kumar" <vjkm..._at_gmail.com> wrote:

Date: Tue, 19 Jun 2007 15:28:56 +0200 (CEST)

Message-ID: <Xns9954607668228vdghher_at_194.177.96.26>

Jan Hidders <hidders_at_gmail.com> wrote in news: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.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.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 ? You cannot do 'forall' over 'y' because your predicate will be false except in some trivial cases. What then ?

>and > hence this query is expressible in the relational algebra. That makes > it a first order expression by the usual definition of the term. What > other definition did you have in mind? > > -- Jan Hidders > >Received on Tue Jun 19 2007 - 15:28:56 CEST