Predicate Calculus Vs. Relational Calculus

[Srinivas Nayak]

Dear All,

What exactly is the difference between Predicate Calculus and
Relational Calculus?

I understand Predicate Calculus - program semantics defined in terms
of assertions / simple predicates.

How is program semantics defined in Relational Calculus?
Is it by some relation/function?
I had read Harlan D. Mill's book on structured programming.
Does this have any similarity with that?

Does Relational Calculus solves some aspects of Programming
methodology that is not elegantly expressed in terms of Predicate
Calculus ?

Sincerely,
Srinivas Nayak

[Jeremy Weissmann]

Srinivas,

   Relations are boolean functions on any number of arguments.  For example, the relation  <  is a boolean function of two real variables:

    3 < 4  ==  true

    4 < 3  ==  false    .

Predicates are a special case, namely a boolean function on ONE argument.  For example, the predicate  'even'  is a boolean function of one integer variable:

    even.3  ==  false

    even.4  ==  true     .

(In some sense a relation can be viewed as a predicate on a  "paired"  space.  For example,  <  could be viewed as a predicate on  PAIRS  of real variables:

    <.(3,4)  ==  true

    <.(4,3)  ==  false     .

But this is more or less a technicality.)

   We study predicate calculus because we want to study the relationships between PREDICATES.  For example, it may not just be that  P.2 => Q.2  and  P.3 => Q.3 ,  but maybe  P.x => Q.x  for any  x .   We study this state of affairs by writing  [ P => Q ] .   The reason for doing this is that now the domain of  x  has been pushed to the background, and the relationship between  P  and  Q  has been brought to the fore.  Dijkstra and Scholten (and others) have given us a language where we can discuss the predicates themselves, independently of the space they might be defined on.

   We study relational calculus for the same reason, but this time to study the relationships between relations.  (Sorry for the linguistic confusion!)

   You might want to have a look at the middle section of EWD1123 (http://www.cs.utexas.edu/~EWD/ewd11xx/EWD1123.PDF), starting on p 29, before delving into Rutger's work.  There is also a lovely note by Wim Feijen and Netty van Gasteren on the relational calculus, WF140 (http://mathmeth.com/wf/files/wf1xx/wf140.pdf).

   Also you must have a look at WF147 and WF148 (both found here: http://mathmeth.com/wf/wf1xx.shtml).  They demonstrate convincingly that There Is No One System.  Finding the right terminology/framework/interface in which to discuss a subject is a serious scientific and artistic concern!

   Best,

+j

     

--
You received this message because you are subscribed the mathmeth.com mailing list.
To unsubscribe from this group, send email to Calculational-Math...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/Calculational-Mathematics?hl=en

[Marnix Klooster]

On Tue, Feb 14, 2012 at 5:50 AM, Jeremy Weissmann <jer...@mathmeth.com> wrote:

Relations are boolean functions on any number of arguments.

[snip]

 

We study relational calculus for the same reason, but this time to study the relationships between relations.  (Sorry for the linguistic confusion!)

   You might want to have a look at the middle section of EWD1123 (http://www.cs.utexas.edu/~EWD/ewd11xx/EWD1123.PDF), starting on p 29, before delving into Rutger's work.  There is also a lovely note by Wim Feijen and Netty van Gasteren on the relational calculus, WF140 (http://mathmeth.com/wf/files/wf1xx/wf140.pdf).

So both EWD1123 and WF140 say that we can get relational calculus by taking predicate calculus and adding the tilde (~) and composition (;) operators, and one constant (J), and a bunch of postulates.  But what I still cannot grasp (also not from other EWDs) is some kind of _model_ for relational calculus.  Suppose R and S are relations (of two or perhaps five) variables: what does ~R mean, and R;S?  What does R.x mean (if anything)  Also, how can one interpret a _predicate_ P (like 'even') as a relation (given that relational calculus is introduced by EWD and WF as an extension of predicate calculus)?

If there is an EWD, WF, or other note or article (or perhaps part of RD's report, which I haven't started to read yet), which explains this in more detail, I'm interested!

Thanks!

Groetjes,
 <><
Marnix

--
Marnix Klooster
marnix....@gmail.com

[Jeremy Weissmann]

Strange... I thought for sure there is a model given in EWD1123. I believe it is:

   [ R ]  ==  (Ax,y :: xRy)

   x R y  ==  y (~R) x

   x (R;S) y  ==  (Ez :: xRz /\ zRy)

   x J y  ==  (x = y)

But look at EWD1123 again...

   

+j

Sent from my iPhone

[Jeremy Weissmann]

Also, how can one interpret a _predicate_ P (like 'even') as a relation (given that relational calculus is introduced by EWD and WF as an extension of predicate calculus)?

These are called left- and right-conditions.  They are studied in Rutger's work:

   x is a left-condition  ==  [ x;true => x ]

   x is a right-condition  ==  [ true;x => x ]     .

+j

[Jeremy Weissmann]

Have a look at EWD1123, p 40.

+j

[Marnix Klooster]

Found it, thanks!

--
Marnix Klooster
marnix....@gmail.com