5.1. Relational Algebra and Relational Calculus
Many different DMLs can be designed to express database manipulations. Different DMLs
will probably differ in syntax, but more importantly they can differ in the basic operations
provided. For those familiar with programming, these differences are not unlike that found in
different programming languages. There, the basic constructs provided can greatly differ in
syntax and in their underlying approach to specifying computations. The latter can be very
contrasting indeed  look at, for example, the differences between procedural (eg. C) and
declarative (eg. Prolog) approaches to specifying computations.
Relational Algebra and Relational Calculus are two approaches to specifying manipulations on relational databases. The distinction between them is somewhat analagous to that between procedural and declarative programming. Thus, before looking at the details of these approaches, it is instructive to briefly digress and look at procedural and declarative programming a little more closely. We will then try to put into context how the algebra and calculus help in the design and implementation of DMLs.
Briefly, the procedural approach specifies a computation to be performed as explicit sequences of operations. The operations themselves are built from a basic set of primitive operations and structuring/control primitives that build higher level operations. An operation can determine the flow of control (ie. determines the next operation to be executed) and/or cause data to be transformed. Thus programming in the procedural style involves working out the operations and their appropriate order of execution to effect the desired transformation(s) on input data.
The declarative approach, in contrast, would specify the same computation as a description of the logical relationship between input and output data. These relationships are typically expressed as a set of truthvalued sentences about data objects. Neither operations nor their sequences are made explicit by the programmer. Operations are instead implicit in the predetermined set of rules of inference used to derive new sentences from those given (or derived earlier).
In other words, if you used a procedural programming language, you must specify how input is to be transformed to desired outputs using the basic operations available in the language. However, if you used a declarative language, you must instead describe what relationships must be satisfied between inputs and outputs, but essentially say nothing about how a given input is to be transformed to the desired output (it is for the system to determine how, typically by some systematic application of inference rules).
Amidst such differences, users are right to raise some basic concerns. Are these differences superficial? Or do they mean that there can be computations specifiable in one but not in the other? If the latter were the case, programmers must avoid choosing languages that simply cannot express some desired computation (assuming we know exactly the limitations of each and every programming language)! Fortunately for programmers, this is not the case. It is a wellknown result that every generalpurpose programming language (whether procedural or declarative) is equivalent to every other. That is, if something is computable at all, it can be specified in any of these languages. Such equivalence is established by reference to a fundamental model of computation that underlies the notion of computability.
Now what can we say about the different (existing and future) database languages? Can two
different languages be said to be equivalent in some sense? To answer this question we must
first ask whether, in relational databases, there is a fundamental model of database
manipulation? The answer is yes  Relational Calculus defines that model!
Recollect that the Universal Turing Machine (model of computation) is accepted as defining the class of all
computable functions. Every programming language shown to be equivalent to it is therefore
equivalent with every other.
Let us first state a fundamental definition:
Relational Calculus, as we shall see later, provides constructs (wellformed expressions) to specify relations. These constructs are very much in a declarative style. Relational Algebra, on the other hand, also provides constructs for relational database manipulations but in a more procedural style. Moreover, it has also been established that Relational Algebra is equivalent to Relational Calculus, in that every expression in one has an equivalent expression in the other. Thus relational completeness of a database language can also be established by showing that it can define any relation expressible in Relational Algebra.
Why then should we bother with different languages and styles of expression if they are all in some sense equivalent? The answer is that besides equivalence (relational or computational), there are other valid issues that different language designs try to address including the level of abstraction, precision, comprehensibility, economy of expression, ease of writing specifications, efficiency of execution, etc. Declarative constructs, by virtue of their descriptive nature (as opposed to the prescriptive nature of procedural constructs), are closer to natural language and thus easier to write and understand. Designers of declarative languages try to provide constructs that even endusers (with a little training) can use to formulate, for example, ad hoc queries. Declarative constructs, however, execute less efficiently than equivalent procedural ones. Attempts to make them more efficient typically involve first, automatic translation to equivalent procedural form, and second, optimising the resulting expressions according to some predetermined rules of optimisation. In fact, this was the original motivation for the Algebra, ie. providing a set of operations to which expressions of the Calculus could be translated and subsequently optimised for execution. But the efficency of even this approach cannot match that of carefully handcoded procedural specifications. Thus for periodical and frequently executed manipulations, it is more efficient to use algebraic forms of database languages.
Because of the fundamental nature and role of the Relational Algebra and Calculus in relational databases, we will look at them in depth in the ensuing chapters. This will provide readers with the basic knowledge of database manipulations possible in the model. We begin in this chapter with Relational Algebra.
5.2. Overview of Relational Algebra
Relational Algebra comprises a set of basic operations. An operation is the application of an
operator to one or more source (or input) relations to produce a new relation as a result.
This is illustrated in Figure 51 below. More abstractly, we can think of such an operation as
a function that maps arguments from specified domains to a result in a specified range. In this
case, the domain and range happen to be the same, ie. relations.
This is no different in principle to, say, operations in arithmetic. For example, the ‘add’ operation in arithmetic takes two numbers and produces a number as a result. In arithmetic, we are used to writing expressions to denote operations and their results. Thus, the ‘add’ operation is usually written using the ‘+’ symbol (the operator) placed between its two aguments, eg. 145 + 168. Moreover, because an expression denotes the result of the operation (which is of the same type as its input arguments), it itself can be written as an argument in another operation, allowing us to construct complex expressions to denote one result, eg. 145 + 168  20 x 3.
Complex expressions that combine different operations are evaluated by a sequence of reductions. The sequence, in the case of arithmetic expressions, is determined by the familiar precedence of operators. Thus, the expression 145 + 168  20 x 3 would be reduced as follows:
The analogy with arithmetic above has been useful to highlight the basic nature of relational algebra. However, the algebra’s basic operations are much more complex than those of arithmetic. They are in fact much more related to operations on sets (viz. intersection, union, difference, etc). This is not surprising as relations are after all special kinds of sets.
As mentioned above, a relational operation maps relations to a relation. As a relation is completely defined by its intension and extension, the complete definition of a relational operation must specify both the schema of the resultant relation and the rules for generating its tuples from the input relation(s). In the following, we will do just that. Moreover, in the interest of clarity as well as precision of presentation, we will define each basic operation both informally and formally.
While notations used to denote the basic operators and operations may differ in the literature, there is no disagreement in their basic logical definitions. It will be necessary for us to use some concrete notation in what follows and, rather than introducing yet more notations, we have chosen in fact to use Codd’s original notation.
5.3. Selection
Selection is used to extract tuples from a relation. A tuple from the source relation is
selected (or not) based on whether it satisfies a specified predicate (condition). A predicate
is a truthvalued expression involving tuple component values and their relationships. All
tuples satisfying the predicate are then collected into the resultant relation. The general effect
is illustrated in Figure 52.
For example, consider the ‘Customer’ source relation below:
The result of a selection operation applied to it with the condition that the attribute ‘Ccity’ must have the value "London" will be:
because these are the only tuples that satisfy the stated condition. Procedurally, you may think of the operation as examining each tuple of the source relation in turn (say from top to bottom), checking to see if it met the specified condition before turning attention to the next tuple. If a tuple satisfies the condition, it is included in the resultant relation, otherwise it is ignored.
We shall use the following syntax to express a selection operation:
In its simplest form, the <predicate> is a simple scalar comparison operation, ie. expressions of the form
<value_i> denotes a scalar value and is either a valid attribute name in the source relation, or a constant value. If an attribute name is specified, it denotes the corresponding value in the tuple under consideration. Thus, the example operation above could have been denoted by the following construct:
Of course, arguments to a comparator must reduce to values from the same domain.
The <predicate> may also take the more complex form of a boolean combination of simple comparison operations above, using the boolean operators ‘AND’, ‘OR’, and ‘NOT’.
The <resultrelationname> is a unique name that is associated with the result relation. It can be viewed as a convenient abbreviation that can be used as <sourcerelation name>s in subsequent operations. Thus, the full selection specification corresponding to the example above is:
As another example, consider the following relation. Each tuple represents a sales transaction recording the customer number of the customer purchasing the goods (C#), the product number of the goods sold (P#), the date of the transaction (Date) and the quantity sold (Qnt).
Suppose now that we are interested in looking at only those transactions which took place before January 26 with quantities of more than 25 or involving customer number 2. This need would be translated into the following selection:
and would yield the relation:
This example illustrates the use of boolean combinations in the <predicate>. However, formulating complex predicates is not as simple and straightforward as it may seem. The basic problem is having to deal with ambiguities at two levels.
First, the informal statement (typically in natural language) of the desired condition may itself be ambiguous. The alert reader would have noted that the phrase (in the above example)
Second, the formal boolean expressions involving AND, OR and NOT may also be ambiguous. The source of ambiguity is not unlike that for natural language (ambiguity of strength or order of binding).
Thus
1. expressions enclosed within parentheses have greater precedence (ie. binds stronger). Thus,
2. The order of precedence of the boolean connectives, unless overridden by parentheses, are (from highest to lowest) NOT, AND, OR
There is no limit to the level of ‘nesting’ of parentheses, ie. a parenthesised expression may have within it a parenthesised subexpression, which may in turn have within it a parenthesised subsubexpression, etc. Given any boolean expression and the above conventions, we can in fact construct a precedence tree that visually depicts its unique meaning.
Figure 53 illustrates this. A leaf node represents a basic comparison operation, whereas a nonleaf node represents a boolean combination of its children. A node deeper in the tree binds stronger than those above it. Alternatively, the tree can be viewed as a prescription for reducing (evaluating) a boolean expression to a truthvalue (true or false). To reduce a node:
a) if it is a leaf node, replace it with the result of its associated comparison operation
b) if it is a nonleaf node, reduce each of its children; then replace it with the result of applying its associated boolean operation on the truthvalues of its children
Using these simple conventions, we can check that expressions we construct indeed carry the intended meanings. (The reader can go back the the last example and ascertain that the intended interpretation was indeed correctly captured in the predicate of the selection statement).
At this point, we should say a few words about the notation, particularly in the context of the analogy to arithmetic expressions in the last section. Strictly speaking, the full selection syntax above is not an expression that can be used as an argument to another operation. This does not contradict the analogy, however. The selection syntax, in fact, has an expression component comprising the select and whereclauses only, ie. without the givingclause:
It would be clearer to write:
Mathematical notation too have various devices to introduce abbreviations to simplify and make expressions more readable. What we are doing here with the givingclause is analogous to, for example, writing:
The givingclause is thus mainly a stylistic device. It is important to note that that is all it is  introducing a temporary abbreviation to be used in another operation. In particular, it is not to be interpreted as permanently modifying the database schema with the addition of a new relation name.
In this book, we will favour this notational style because we think it leads to a simpler and more comprehensible notation. The reader should note, however, that while other descriptions in the literature may favour and use only the expression forms, the differences are superficial.
Formal Definition
If s denotes a relation, then let
S(s
) denote the finite set of attribute names of s
(ie. its intension)
T(s
) denote the finite set of tuples of s
(ie. its extension)
dom(a
), where a
Î
S(s
), denote the set of allowable values for a
t
·
a
, where t
Î
T(s
) and a
Î
S(s
), denote the value of attribute a
in tuple t
The selection operation takes the form
select s where p giving r
where p is a predicate expression.
The syntax of a predicate expression is given by the following BNF grammar (this should be viewed as an abstract syntax not necessarily intended for an enduser language):
pred_exp ::= comp_exp  bool_exp  ( pred_exp )
bool_exp ::= negated_exp  binary_exp
negated_exp ::= NOT pred_exp
binary_exp ::= pred_exp bool_op pred_expr
bool_op ::= AND  OR
comp_exp ::= argument comparator argument
comparator ::= >  <  ³  £  =
argument ::= attribute_name  literal
p is wellformed iff it is syntactically correct and
Further, let p (t ) denote the application of a wellformed predicate expression p to a tuple t Î T(s ). p (t ) reduces p in the context of t , ie. the occurrence of any a Î S(s ) in p is first replaced by t · a . The resulting expression is then reduced to a truthvalue according to the accepted semantics of comparators and boolean operators.
Then r , the resultant relation of the selection operation, is characterised by the following:
5.4. Projection
Whereas a selection operation extracts rows of a relation meeting specified conditions, a
projection operation extracts specified columns of a relation. The desired columns are
simply specified by name. The general effect is illustrated in Figure 55.
We could think of selection as eliminating rows (tuples) not meeting the specified conditions. In like manner, we can think of a projection as eliminating columns not named in the operation. However, an additional step is required for projection because removing columns may result in duplicate rows, which are not allowed in relations. Quite simply, any duplicate occurrence of a row must be removed so that the result is a relation (a desired property of relational algebra operators).
For example, using again the customer relation:
its projection over the attribute ‘Ccity’ would yield (after eliminating all columns other than ‘Ccity’):
Note the duplication of row 1 in row 3. Projection can result in duplication because the resultant tuples have a smaller degree whereas the uniqueness of tuples in the source relation is only guaranteed for the original degree of the relation.
For the final result to be a relation, duplicated occurrences must be removed, ie.
Thus the above operation would be written as:
<listofattributenames> is a commaseparated list of at least one identifier. Each identifier appearing in the list must be a valid attribute name of <sourcerelationname>.
And finally, <resultrelationname> must be a unique identifier used to name the resultant relation.
Why would we want to project a relation over some attributes and not others? Quite simply, we sometimes are interested in only a subset of an entity's attributes given a particular situation. Thus, if we needed to telephone all customers to inform them of some new product line, data about a customer’s number and the city of residence are superfluous. The relevant data, and only the relevant data, can be presented using:

Extending this example, suppose further that we have multiple offices sited in major cities and the task of calling customers is distributed amongst such offices, ie. the office in London will call up customers resident in London, etc. Now the simple projection above will not do, because it presents customer names and phone numbers without regard to their place of residence. If it was used by each office, customers will receive multiple calls and you will probably have many annoyed customers on your hands, not to mention the huge phone bills you unnecessarily incurred!
The desired relation in this case must be restricted to only customers from a given city. How can we specify this? The simple answer is that we cannot  not with just the projection operation. However, the alert reader would have realised that the requirement to restrict resultant rows to only those from a given city is exactly the sort of requirement that the selection operation is designed for! In other words, here we have an example of a situation that needs a composition of operations to compute the desired relation. Thus, for the office in London, the list of customers and phone numbers relevant to it is computed by first selecting customers from London, then projecting the result over customer names and phone numbers. This is illustrated in Figure 55. For offices in other cities, only the predicate of the selection needs to be appropriately modified.
Note that the order of the operations is significant, ie. a selection followed by a projection. It would not work the other way around (you can verify this by trying it out yourself).
Formal Definition
If s denotes a relation, then let
S(s
) denote the finite set of attribute names of s
(ie. its intension)
T(s
) denote the finite set of tuples of s
(ie. its extension)
t
·
a
, where t
Î
T(s
) and a
Î
S(s
), denote the value of attribute a
in tuple t
The projection operation takes the form
project s over d giving r
where d is a commaseparated list of attribute names. Formally, d (as a discrete structure) may be considered a tuple, but having a concrete enumeration syntax (commaseparated list).
Let S_{tuple}(x) denote the set of elements in the tuple x. Then, d must observe the following constraint:
S_{tuple}(d ) Ì S(s )
ie. every name occurring in d must be a valid attribute name in the relation s .
Furthermore, if t Î T(s ) and t ’ denotes a tuple, we define:
R(t , d , t ’) º " a · a Î S_{tuple}(d ) Û t · a Î S_{tuple}(t ’)
ie. a tuple element t · a is in the tuple t ’ if and only if the attribute name a occurs in d .
Then r , the resultant relation of the projection, is characterised by the following:
5.1. Natural Join
The next operation we will look at is the Natural Join (hereafter referred to simply as Join).
This operation takes two source relations as inputs and produces a relation whose tuples are
formed by concatenating tuples from each input source. It is basically a cartesian product of
the extensions of each input source. However, not all possible combinations of tuples
necessarily end up in the result. This is because it implicitly selects from among all possible
tuple combinations only those that have identical values in attributes shared by both
relations.
Thus, in a typical application of a Join, the intensions of the input sources share at least one attribute name or domain (we assume here that attribute names are global to a schema, ie. the same name occurring in different relations denote the same attribute and value domain). The Join is said to occur over such domain(s). Figure 56 illustrates the general effect. The shaded leftmost two columns of the inputs are notionally the shared attributes. The result comprise these and the concatenation of the other columns from each input. More precisely, if the degree of the input sources were m and n respectively, and the number of shared attributes was s, then the degree of the resultant relation is (m+ns).
As an example, consider the two relations below:
These relations share the attribute ‘C#’, as indicated. To compute the join of these relations, consider in turn every possible pair of tuples formed by taking one tuple from each relation, and examine the values of their shared attribute. So if the pair under consideration was
Thus, the resultant relation after considering all pairs would be:
The foregoing description is in fact general enough to admit operations on relations that do not share any attributes at all (s = 0). The join, in such a case, is simply the cartesian product of the input sources’ extensions (the condition that tuple combinations have identical values over shared attributes is vacuously true since there are no shared attributes!). However, such uses of the operation are atypical.
Syntactically, we will write the Join operation as follows:
join <sourcerelationname1> AND <sourcerelationname2>
If a Join is over a proper subset of shared attributes, then shared attributes not specified in the overclause will each have its own column in the result relation. But in such cases, the respective column labels will be qualified names. We will adopt the convention of writing a qualified name as ‘relation.column’, where column is the column label and relation the relation name in which column appears. As an illustration, consider the relations below: The operation
To see why Join is a necessary operation in the algebra, consider the following situation (assume as context the Customer and Transaction relations above): the company decided that customers who purchased product number 1 (P# = 1) should be informed that a fault has been discovered in the product and that, as a sign of good faith and of how it values its customers, it will replace the product with a brand new faultfree one. To do this, we need to list, therefore, the names and phone numbers of all such customers.
First, we need to identify all customers who purchased product number 1. This information is in the Transaction relation and, using the following selection operation, it is easy to limit its extension to only such customers:
Next, we note that the resultant relation only identifies such customers by their customer numbers. What we need, though, are their names and phone numbers. In other words, we would like to extend each tuple in A with the customer name and phone number corresponding to the customer number. As such items are found in the relation Customer which shares the attribute ‘C#’ with A, the join is a natural operation to perform:
With B, we have practically derived the information we need  in fact, more than we need, since we are interested only in the customer name (the ‘Cname’ column) and phone number (the ‘Cphone’ column). But as we’ve learned, the irrelevant columns may be easily removed using projection, as shown below.
As a final example, let us consider the query "Get the names and phone numbers of such customers who bought the product P# 1 ". Once again, this task will require a combination of operations which must involve a Join at some point because not all the information required are contained in one relation. The sequence of operations required is shown below.
Formal Definition
As before, if s denotes a relation, then let
S(s
) denote the finite set of attribute names of s
(ie. its intension)
T(s
) denote the finite set of tuples of s
(ie. its extension)
t
·
a
, where t
Î
T(s
) and a
Î
S(s
), denote the value of attribute a
in tuple t
Further, if t _{1} and t _{2} are tuples, let t _{1}^t _{2 }denote the tuple resulting from appending t _{2} to the end of t _{1}.
We will also have need to use the terminology introduced in defining projection above, in particular, S_{tuple }and the definition:
R(t , d , t ’) º " a · a Î S_{tuple}(d ) Û t · a Î S_{tuple}(t ’)
The (natural) join operation takes the form
join s AND n over d giving r
As with other operations, the input sources s and n must denote valid relations that are either defined in the schema or are results of previous operations, and r must be a unique identifier to denote the result of the join. d is a tuple of attribute names such that:
S_{tuple}(d ) Í (S(s ) Ç S(n ))
Let e = (S(s ) Ç S(n )) – S_{tuple}(d ), ie. the set of shared attribute names not specified in the overclause. We next define, for any relation r:
Rename(r, e ) º { a  a Î S(r) – e Ú (a = ‘r.p’ Ù p Î S(r) Ç e ) }
In the case that e = {} or S(r) Ç e = {}, Rename(r, e ) = S(r).
The Join operation can then be characterised by the following: