Chapter 7: Relational Calculus

Introduction

Ch.6 presented relational algebra, a prescriptive basis for manipulating the relational model.
    prescriptive - describe steps to obtaining a solution  (procedural)

Ch.7 presents relational calculus, a descriptive basis for manipulating the relational model.
    descriptive - describe desired result (non-procedural)

Relational algebra and calculus are equivalent in their expressive power.

Relational algebra provides a collection of explicit operations - join, union, projection, etc.
The operations are used to tell the system how to build some desired relation in terms of other relations.

The calculus merely provides a notation for formulating the definition of that desired relation in terms of those given relations.

Relation Algebra vs. Relational Calculus

Relational Algebra is procedural; it is more like a programming language;

Relational Calculus is nonprocedural. it is more close to a natural language.

For example, suppose you want to query:

            Get supplier numbers  for suppliers who supply part P2.

An algebraic version of this query might follow these steps:

  1. Form the natural join of relations S and SP on S#;
  2. Next, restrict the result of that join to tuples for part P2;
  3. Finally, project the result of that restriction on S#.
A calculus formulation might look like:

Get S#  for suppliers such that there exists a shipment SP with the same S# value and with P# value P2.

The calculus formation is descriptive while the algebraic one is prescriptive.

Why it is called relational calculus?

It is founded on a branch of mathematical logic called the predicate calculus.
 

Codd proposed the concept of a relational calculus (applied predicate calculus tailored to relational databases).

Tuple (range) Variables:

A fundamental feature is the notion of the tuple variable, also known as a range variable, meaning range over some relation.
Tuple variable: variable that ranges over some relation (its values are tuples of the relation).
 

                            Get supplier numbers for suppliers in London. 

Relational Calculus
RANGE OF SX IS S
RETRIEVE (SX.S#) WHERE SX.CITY = "London".
SQL
SELECT S.S#
FROM S
WHERE S.CITY = 'London'
SQL does not require the explicit introduction of a tuple variable,  it allows the relation name S to serve as an implicit tuple variable.

Relational Algebra

(S WHERE CITY = 'London') [S#]

Tuple-oriented relational calculus

The original relational calculus has come to be known as the tuple calculus to distinguish with an alternative calculus -- domain oriented calculus.

Tuple variables: a tuple variable is defined by means of a statement of the form

RANGE OF T IS X1, X2, ... , Xn

T is a tuple variable, while X1, ... Xn are relations names or tuple calculus expressions

GRAMMAR
range-variable-definition ::= RANGE OF variable IS range-item-commalist;
range-item ::= relation | expression
expression ::= (target-item-commalist) [WHERE wff]
target-item ::= variable | variable.attribute [AS attribute]
wff::= condition | NOT wff | condition AND wff | condition OR wff  | IF condition THEN wff | EXISTS variable (wff) | FORALL variable (wff) | (wff)
 

The WFF

Each occurrence of a tuple variable within a WFF is either free or bound.
  1. Within a simple comparison such as T.A < U.A, all tuple variable occurrences are free.
  2. Tuple variable occurrences in the WFFs (f) and NOT f are free or bound according as they are free or bound in f. Tuple variable occurrences in the WFFs f AND g and f OR g are free or bound according as they are free or bound in f or g.

    3. Occurrences of T that are free in f are bound in the WFFs EXISTS T(f) and FORALL T(f). Other tuple variable occurrences in f are free or bound in these WFFs according as they are free or bound in f.
     
Assuming:
RANGE OF SX IS S:
RANGE OF SPX IS SP;
RANGE OF SPX IS SP;
RANGE OF SPY IS SP;
RANGE OF SPZ IS SP;
 

Examples

Target Lists

Each item in a target item comma list is either a simple variable name such as T or an expression of the form  T.A [AS X]
(which is like x = T.A.)

Examples: 

SX.S#
SX.S# AS SNO
SX
SX.S#, SX.CITY, SPX.P#

Expressions

A tuple calculus expression is an expression of the form

target-item-commalist [WHERE f]

Example: 

SX.S#
SX.S# WHERE SX.CITY = 'London'
SX.S# AS SNO WHERE SX.CITY = 'London'
The first of these denotes the set of all supplier numbers in relation S; The second denotes that subset of those supplier numbers for which the city is London. The third is the same as the second, except that the sole attribute of the result has been renamed SNO. The last is a tuple calculus representation of the query "Get supplier numbers and cities for suppliers who supply part P2".

Examples

1. Get supplier numbers for suppliers in Paris with status > 20.

SX.S# WHERE SX.CITY = 'Paris' AND SX.STATUS > 20

3.2 Get all pairs of supplier numbers such that the two suppliers are located in the same city.

 SX.S# AS FIRSTS#, SY.S# AS SECOND#
                WHERE SX.CITY = SY.CITY AND SX.S# < SY.S#

3.3 Get supplier names for suppliers who supply part P2.

SX.SNAME WHERE EXISTS SPX (SPX.S# = SX.S# AND SPX.P# = 'P2')


3.4 Get supplier names for suppliers who supply at least one red part. 

SX.SNAME WHERE EXISTS SPX (SX.S# = SPX.S# AND 
                        EXISTS PX (SPX.P# = PX.P# AND PX.COLOR = 'Red' ))

Prenex normal form, in which all quantifiers appear at the front of the WFF. 

SX.SNAME WHERE EXISTS SPX ( EXISTS PX (SX.S# = SPX.S# AND SPX.P# = PX.P# AND PX.COLOR = 'Red' ))

Furthermore, it introduces the possibility of reducing the number of parentheses, as follows:

SX.SNAME WHERE EXISTS SPX EXISTS PX (SX.S# = SPX.S# AND SPX.P# = PX.P# AND PX.COLOR = 'Red')


3.5 Get supplier names for suppliers who supply at least one part supplied by suppliers S2.

SX.SNAME WHERE EXISTS SPX (EXISTS SPY (SX.S# = SPX.S# AND
                                SPX.P# = SPY.P# AND SPY.S# = 'S2' )


3.6 Get supplier names for suppliers who supply all parts.

SX.SNAME WHERE FORALL PX ( NOT EXISTS SPX 
                        (SPX.S# = SX.S# AND SPX.P# = PX.P#))


3.7 Get supplier names who do not supply part P2.

SX.SNAME WHERE NOT EXISTS SPX 
                (SPX.S# = SX.S# AND SPX.P# = 'P2')


3.8 Get supplier numbers for suppliers who supply at least all those parts supplied by suppliers S2.

SPX.S# WHERE FORALL SPY (SPY.S# <> 'S2' OR 
        EXISTS SPZ (SPZ.S# = SPX.S# AND SPZ.P# = SPY.S#) )


3.9 Get part number for parts that either weigh more than 16 pounds or are supplied by supplier S2, or both.


RANGE OF PU IS (PX.P# WHERE PX.WEIGHT > 16 ),
                        (SPX.P# WHERE SPX.S# = 'S2')

PU.P#

Relational Calculus VS. Relational Algebra

Codd's reduction algorithm:

An arbitrary expression of calculus can be reduced to a semantically equivalent expression of algebra.

Illustrate algorithms:

Consider the query: "Get names and cities for suppliers who supply at least one Athens project with at least 50 of every part." 

SX.SNAME, SX.CITY WHERE EXISTS JX FORALL PX EXISTS SPJX 
                ( JX.CITY = 'Athens' AND
                  JX.J# = SPJX.J# AND
                  PX.P# = SPJX.P# AND
                  SX.S# = SPJX.S# AND
                  SPJX.QTY >= 50 )
We now show how this expression can be evaluated to yield the desired result.
  1. For each tuple variable, retrieve the range, restricted if possible, to eliminate certain tuples from further consideration.
    2. SX: All tuples of S
PX: All tuples of P
JX: Tuples of J where CITY = "Athens"
SPJX: Tuples of SPJ where QTY >= 50
  2. Construct the Cartesian product of the ranges retrieved in Step 1, to yield S TIMES P TIMES J.
  3. Restrict the Cartesian product just built in accordance with the "join condition" portion of the WHERE clause. In the example, that portion is:
    4.         JX.J# = SPJX.J# AND PX.P# = SPJX.P# AND SX.S# = SPJX.S#
  4. Apply the quantifiers from right to left, as follows.
    5. In the example, the quantifiers are: EXISTS JX FORALL PX EXISTS SPJX
    1. Project away the attributes SPJ.S#, SPJ.P#, SPJ.J#, SPJ.QTY. Result:
    2. Divide by relation P.
    3. Project away the attributes J#, JNAME, CITY. Result:
  5. Project the result of Step 4 in accordance with the specifications in the target list. In our example, the target list is:
    6. SX.SNAME, SX.CITY
        ( ((S WHERE CITY = "Athens") [J#] JOIN 
        (SPJ WHERE QTY >= 50 [J#, P#, S#] )     JOIN
        S [S#, SNAME, CITY]  ) ) [SNAME, CITY]  DIVIDEBY P[P#]

Domain-Oriented Relational Calculus

The domain-oriented calculus differs from the tuple-oriented relational calculus in that it has domain variables instead of tuple variables. That is variables that range over domains instead of over relations.

Obvious distinction between the domain and tuple calculi is that the domain version supports an additional form of "comparison", which we refer to as the membership condition. A membership condition takes the form

R ( pair, pair, ... )

where R is a relation name, and each pair is of the form A:v, where A in turn is an attribute of R and v is either a domain variable or a literal.

For example, the expression

SP (S#:'S1', P#:'P1')

is a membership condition that evaluates to true if and only if there exists a tuple in relation SP with S# value S1 and P# value P1. Likewise, the membership condition

SP (S#:SX, P#:PX )

For example:

SX: denotes the set of all supplier numbers

SX WHERE S (S#:S) denotes the set of all supplier numbers in relation S

SX WHERE S (S#:SX, CITY:'London') denotes the set of all suppliers for which the city is London.

SX, CITYX WHERE S ( S#:SX, CITY:CITYX ) AND SP (S#:SX, P#:'P2')

Get supplier numbers ND cities for suppliers who supply part P2. 

1. Get supplier numbers for suppliers in Paris with status > 20.

SX WHERE EXISTS STATUSX ( STATUSX > 20 AND 
                        S (S#:SX, STATUS:STATUSX, CITY:'Paris')


2. Get all pairs of supplier numbers such that the two suppliers are located in the same city.

FIRSTS# = SX, SECONDS# = SY
        WHERE EXISTS CITYZ
                ( S ( S#:SX, CITY:CITYZ ) AND
                  S ( S#:SY, CITY:CITYZ ) AND
                  SX < SY )

3. Get supplier names for suppliers who supply at least one red part.

NAMEX WHERE EXISTS SX EXISTS PX
        ( S ( S#:SX, SNAME:NAMEX) AND
          SP ( S#:SX, P#: PX) AND
          P (P#: PX, COLOR: 'Red' ) )

4. Get supplier names for suppliers who supply at least one part supplied by supplier S2.

NAMEX WHERE EXISTS SX EXISTS PX
        ( S (S#:SX, SNAME:NAME )
          AND SP (S#:SX, P#:PX )
          AND SP (S#:'S2', P#:PX ) )

5. Get supplier names for suppliers who supply all parts.

NAMEX WHERE EXISTS SX 
        ( S (S#:SX, SNAME:NAMEX) AND
          FORALL PX ( IF P (P#:PX )
                            THEN SP (S#:SX, P#:PX )))

6. Get supplier names for suppliers who do not supply part P2.

NAMEX WHERE NOT EXISTS SX 
        ( S (S#:SX, SNAME:NAMEX) AND
          SP ( S#:SX, P#:PX) )

7. Get supplier names for suppliers who supply at least all those parts supplied by supplier S2.

SX WHERE FORALL PX (IF SP (S#:'S2', P#:PX) THEN 
                (SP (S#:SX, P#:PX) )

8. Get part numbers for parts that either weigh more than 16 pounds or are supplied by S2, or both.

PX WHERE EXISTS WEIGHTX
        (P ( P#:PX, WEIGHT:WEIGHTX ) AND
                WEIGHTX > 16 )
        OR SP (S#:'S2', P#:PX)