Difference between Relational Algebra and Relational calculus

mrg picture mrg · Sep 29, 2015 · Viewed 26.9k times · Source

What is the exact difference between relational algebra and relational calculus. At most of the reference, it will be

Relational algebra is procedural and calculus is non procedural.

So, what is these stands for. However, we can solve all the problems using relational algebra. Then why we would use relational calculus. Except definition, Explanation with example is much appreciated.

Answer

philipxy picture philipxy · Sep 29, 2015

TL;DR: Queries calling RA (relational algebra) operators & queries of the two relational calculi (RCs) TRC (tuple RC) & DRC (domain RC) are different syntax for the same thing: a relation value or the property/condition that a relation value's tuples have to meet. As is SQL (a mix(up) of them). As is the predicate calculus, the language of precision in mathematics, logic, science (including computer science) & engineering (including software engineering). And RA as procedural vs RCs as declarative is a myth.


A relation holds the tuples that make some predicate--statement template parameterized by attributes--into a true proposition--statement.

/* tuples where employee PERSONNAME lives on STREET in CITY */
Employee
/* tuples where employee PERSONNAME works at COMPANY for $SALARY */
WorksFor

A RA-style query expression involves attribute names, relation variable/constant names, relation literals (involving attribute names & values) & relation operators. The operators are JOIN, UNION, MINUS, PROJECT, RESTRICT, etc. It denotes the relation value that you get by evaluating the expression. But it is also requirements for the value to meet.

/* RA query for tuples where
    FOR SOME STREET & CITY [employee PERSONNAME lives on STREET in CITY]
AND NOT FOR SOME COMPANY & SALARY
        [employee PERSONNAME works at COMPANY for $SALARY AND COMPANY = 'FBC']
*/
    PROJECT PERSONNAME (Employee)
MINUS PROJECT PERSONNAME (RESTRICT COMPANY = 'FBC' (WorksFor))

A RC expression is set-builder notation for a relation value. It involves a predicate with relation variable/constant names, attribute names & values, predicate operators & quantified names (logic variables). The operators are AND, OR, NOT, FOR SOME/ALL and =. It is usually seen as requirements for the value to meet. But it also denotes the relation value that you get by evaluating the expression or a certain equivalent one.

The DRC has quantified names that are attributes. We use a shorthand for statements with one parameter per attribute:

Employee(PERSONNAME, STREET, CITY)
    means (PERSONNAME, STREET, CITY) IN Employee
    means employee PERSONNAME lives on STREET in CITY
WorksFor(PERSONNAME, COMPANY, SALARY)
    means (PERSONNAME, COMPANY, SALARY) IN WorksFor
    means employee PERSONNAME works at COMPANY for $SALARY

/* DRC query for the same tuples as the RA query above */
tuples like (PERSONNAME) where
    FOR SOME STREET & CITY [Employee(PERSONNAME, STREET, CITY)]
AND NOT FOR SOME COMPANY & SALARY
        [WorksFor(PERSONNAME, COMPANY, SALARY) AND COMPANY = 'FBC']

The TRC has quantified names that are tuples. We dot a name to get the value associated with an attribute name in it. (Like for a field of a programming language record.) We use a shorthand for statements with one parameter (a tuple):

Employee(T)
    means T IN Employee
    means employee T.PERSONNAME lives on T.STREET in T.CITY
Worksfor(T)
    means T IN Worksfor
    means employee T.PERSONNAME works at T.COMPANY for $T.SALARY

/* TRC query for the same tuples as the RA query above */
tuples equal to some tuple T like (PERSONNAME) where
    FOR SOME E [Employee(E) AND E.PERSONNAME = T.PERSONNAME]
AND NOT FOR SOME W [
        WorksFor(W)
    AND W.COMPANY = 'FBC'
    AND E.PERSONNAME = T.PERSONNAME
    ]

(A few variants on the originals of the RA and RCs are taught. Eg some identify arguments by order and others by name. Sometimes extra capabilities are added. Eg allowing a function call in a RC is as expressive as allowing a certain relation constant plus operator R RENAME A TO N in a RA.)

However, there is a correspondence between RA operators and RC operators & between RA expressions and RC expressions:

If:
• R -- holds tuples where R(...)
• S -- holds tuples where S(...)
then:
• R JOIN S holds tuples where R(...) AND S(...)
• R UNION S holds tuples where R(...) OR S(...)
• R MINUS S holds tuples where R(...) AND NOT S(...)
• R PROJECT columns to keep holds tuples where FOR SOME columns to drop, R(...)
• R RESTRICT condition holds tuples where R(...) AND condition

A RA expression's value is the tuples that satisfy the corresponding RC expression.

If we want to map from a RC expression to an RA expression on an operator-by-operator basis then we need extended RA operators: one generalizing UNION & one corresponding to NOT. Those aren't operators we would like to actually use in an implementation--the relations values returned are in a certain sense undesirably big. But every RC expression using them can be rearranged mechanically to a normal form that uses only basic RA operators.

So: RA as procedural vs RCs as declarative is a myth. Every RA operator has a corresponding RC operator, every RC operator has a (possibly extended) corresponding RA operator, and every expression of one has (in basic and extended senses) a corresponding expression of the other. They are two notations for the same things. An expression of either can be taken as "procedural" by executing it as parsed or normalized and as "declarative" by executing it otherwise. The myth is trying to capture the idea that a RC expression isn't operator-by-operator like an expression using basic RA operators. But a RC expression does identify its non-obvious normal form's RA expression using basic operators. And it is operator-by-operator like a RA expression including extended operators.

(The myth may be helped because of the history of the words. "Modern algebra" has expressions with operators taking & giving values and can be calculated. "The calculus" aka analysis--differentiation & integration--has expressions describing values via impossible-to-calculate infinite limits & summations. We calculate in other ways, in general only calculating approximations.)

(Also, ironically: "The predicate calculus" is considered to specify things "declaratively" without regard to how they may be otherwise calculated or estimated. But the standard semantics/meaning of such an expression is given by following an algorithm that walks the expression tree. So it has an obvious "procedural" interpretation.)