Database Management System [BCS403] ]

1.1 Relational Model Constraints and Relational Database Schemas

Constraints are restrictions on the actual values in a database state. These constraints are
derived from the rules in the miniworld that the database represents. Constraints on databases
can generally be divided into three main categories:
1. Inherent model-based constraints or implicit constraints
2. Constraints that are inherent in the data model.
The characteristics of relations are the inherent constraints of the relational model and
belong to the first category. For example, the constraint that a relation cannot have
duplicate tuples is an inherent constraint.
3. Schema-based constraints or explicit constraints
Constraints that can be directly expressed in schemas of the data model, typically
by specifying them in the DDL.
The schema-based constraints include domain constraints, key constraints, constraints
on NULLs, entity integrity constraints, and referential integrity constraints.
4. Application-based or semantic constraints or business rules
Constraints that cannot be directly expressed in the schemas of the data model, and
hence must be expressed and enforced by the application programs.

[Link]
 Database Management System [BCS403] ]

Examples of such constraints are the salary of an employee should not exceed the
salary of the and the maximum number of hours an employee
can work on all projects per week is 56.

Domain Constraints specify that within each tuple, the value of each attribute A must be
an atomic value from the domain dom(A). The data types associated with domains
typically include standard numeric data types for integers (such as short integer, integer,
and long integer) and real numbers (float and double precision float). Characters,
Booleans, fixed-length strings, and variable-length strings are also available, as are date,
time, timestamp, and money, or other special data types.

1.1.1 Key Constraints and Constraints on NULL Values

All tuples in a relation must also be distinct. This means that no two tuples can have the
same combination of values for all their attributes. There are other subsets of attributes
of a relation schema R with the property that no two tuples in any relation state r of R should
have the same combination of values for these attributes.
Suppose that we denote one such subset of attributes by SK; then for any two distinct
tuples t1 and t2 in a relation state r of R, we have the constraint that: t1 t2[SK] .
such set of attributes SK is called a super key of the relation schema R

Super key
A super key SK specifies a uniqueness constraint that no two distinct tuples in any state r of
R can have the same value for SK. Every relation has at least one default super key the set
of all its attributes.

Key
A key K of a relation schema R is a super key of R with the additional property that
removing any attribute A from K leaves a set of attributes K that is not a super key of R
anymore. Hence, a key satisfies two properties:
1. Two distinct tuples in any state of the relation cannot have identical values for (all) the
attributes in the key. This first property also applies to a super key.

[Link]
 ]

2. It is a minimal super key that is, a super key from which we cannot remove any
attributes and still have the uniqueness constraint in condition 1 hold. This property is
not required by a super key.
Example: Consider the STUDENT relation

The attribute set {Ssn} is a key of STUDENT because no two student tuples can
have the same value for Ssn
Any set of attributes that includes Ssn for example, {Ssn, Name, Age} is a super
key
The super key {Ssn, Name, Age} is not a key of STUDENT because removing
Name or Age or both from the set still leaves us with a super key

In general, any super key formed from a single attribute is also a key. A key with multiple
attributes must require all its attributes together to have the uniqueness property.

Candidate key
A relation schema may have more than one key. In this case, each of the keys is called a candidate
key. For example, the CAR relation has two candidate keys: License_number and
Engine_serial_number
1.1.2 Relational Databases and Relational Database Schemas
A Relational database schema S is a set of relation schemas S = {R1, R2, ..., Rm} and a s et of
integrity constraints IC.
Example of relational database schema:
COMPANY = {EMPLOYEE, DEPARTMENT, DEPT_LOCATIONS, PROJECT,
WORKS_ON, DEPENDENT}

[Link]
 Figure (a): Schema diagram for the COMPANY relational database schema.
The underlined attributes represent primary keys

A Relational database state is a set of relation states DB = {r1, r2, ..., rm}.Each ri is a state of
R and such that the ri relation states satisfy integrity constraints specified in IC.

[Link]
 Database Management System [BCS403] ]

Figure 1.2.3(b) : One possible database state for the COMPANY relational database schema.
[Link]
 Database Management System [BCS403] ]

A database state that does not obey all the integrity constraints is called Invalid state and a state that
satisfies all the constraints in the defined set of integrity constraints IC is called a Valid state

Attributes that represent the same real-world concept may or may not have identical names in
different relations. For example, the Dnumber attribute in both DEPARTMENT and
DEPT_LOCATIONS stands for the same real-world concept the number given to a department.
That same concept is called Dno in EMPLOYEE and Dnum in PROJECT.
Alternatively, attributes that represent different concepts may have the same name in different
relations. For example, we could have used the attribute name Name for both Pname of PROJECT
and Dname of DEPARTMENT; in this case, we would have two attributes that share the same name
but represent different realworld concepts project names and department names.

Integrity, Referential Integrity, and Foreign Keys

Entity integrity constraint

The entity integrity constraint states that no primary key value can be NULL. This is because the
primary key value is used to identify individual tuples in a relation. Having NULL values for the
primary key implies that we cannot identify some tuples. For example, if two or more tuples had
NULL for their primary keys, we may not be able to distinguish them if we try to reference them
from other relations.
Key constraints and entity integrity constraints are specified on individual relations.

Referential integrity constraint

The referential integrity constraint is specified between two relations and is used to maintain the
consistency among tuples in the two relations. Informally, the referential integrity constraint states
that a tuple in one relation that refers to another relation must refer to an existing tuple in that
relation.
For example COMPANY database, the attribute Dno of EMPLOYEE gives the department number
for which each employee works; hence, its value in every EMPLOYEE tuple must match the
Dnumber value of some tuple in the DEPARTMENT relation.

To define referential integrity more formally, first we define the concept of a foreign key. The
conditions for a foreign key, given below, specify a referential integrity constraint between the two
relation schemas R1 and R2.

[Link]
 Database Management System [BCS403] ]
A set of attributes FK in relation schema R1 is a foreign key of R1 that references relation R2 if it
satisfies the following rules:
1. Attributes in FK have the same domain(s) as the primary key attributes PK of R2; the
attributes FK are said to reference or refer to the relation R2.
2. A value of FK in a tuple t1 of the current state r1(R1) either occurs as a value of PK for
some tuple t2 in the current state r2(R2) or is NULL.
In the former case, we have t1[FK] = t2[PK], and we say that the tuple t1 references or refers to the
tuple t2.
In this definition, R1 is called the referencing relation and R2 is the referenced relation. If these
two conditions hold, a referential integrity constraint from R1 to R2 is said to hold.

Chapter 2: Relational Algebra

Relational algebra is the basic set of operations for the relational model. These operations enable a
user to specify basic retrieval requests as relational algebra expressions. The result of an operation is
a new relation, which may have been formed from one or more input relations.
The relational algebra is very important for several reasons
First, it provides a formal foundation for relational model operations.
Second, and perhaps more important, it is used as a basis for implementing and optimizing
queries in the query processing and optimization modules that are integral parts of
relational database management systems (RDBMSs)
Third, some of its concepts are incorporated into the SQL standard query language for
RDBMSs

Unary Relational Operations: SELECT and PROJECT

The SELECT Operation
tuples from a relation
based on a selection condition. The selection condition acts as a filter that keeps only those tuples
that satisfy a qualifying condition. Alternatively, we can consider the SELECT operation to restrict
the tuples in a relation to only those tuples that satisfy the condition.
The SELECT operation can also be visualized as a horizontal partition of the relation into two sets
of tuples those tuples that satisfy the condition and are selected, and those tuples that do not satisfy
the condition and are discarded.
In general, the select operation is denoted by

[Link]
 Database Management System [BCS403] ]
<selection condition>(R)

where,
- the symbol is used to denote the select operator
- the selection condition is a Boolean (conditional) expression specified on the attributes of
relation R
- tuples that make the condition true are selected
appear in the result of the operation
- tuples that make the condition false are filtered out
discarded from the result of the operation

[Link]
 Database Management System [BCS403] ]

The Boolean expression specified in <selection condition> is made up of a number of clauses of the
form:
<attribute name> <comparison op> <constant value>
or
<attribute name> <comparison op> <attribute name>
where
<attribute name> is the name of an attribute of R,

<constant value> is a constant value from the attribute domain

Clauses can be connected by the standard Boolean operators and, or, and not to form a general
selection condition
Examples:

1. Select the EMPLOYEE tuples whose department number is 4.

DNO = 4 (EMPLOYEE)

2. Select the employee tuples whose salary is greater than $30,000.

SALARY > 30,000 (EMPLOYEE)

3. Select the tuples for all employees who either work in department 4 and make over $25,000
per year, or work in department 5 and make over $30,000

(Dno=4 AND Salary>25000) OR (Dno=5 AND Salary>30000)(EMPLOYEE)

The result of a SELECT operation can be determined as follows:

The <selection condition> is applied independently to each individual tuple t in R

If the condition evaluates to TRUE, then tuple t is [Link] the selected tuples appear in
the result of the SELECT operation

The Boolean conditions AND, OR, and NOT have their normal interpretation, as follows:

- (cond1 AND cond2) is TRUE if both (cond1) and (cond2) are TRUE; otherwise,it is

FALSE.

- (cond1 OR cond2) is TRUE if either (cond1) or (cond2) or both are TRUE; otherwise, it is

FALSE.

- (NOT cond) is TRUE if cond is FALSE; otherwise, it is FALSE.

[Link]
 Database Management System [BCS403] ]

The SELECT operator is unary; that is, it is applied to a single relation. The degree of the relation resulting
from a SELECT operation is the same as the degree of [Link] number of tuples in the resulting relation
is always less than or equal to the number of tuples in R. That is,
c

The fraction of tuples selected by a selection condition is referred to as the selectivity of the
condition.
The SELECT operation is commutative; that is,
<cond1> <cond2> <cond2> <cond1>(R))

Hence, a sequence of SELECTs can be applied in any [Link] can always combine a cascade (or
sequence) of SELECT operations into a single SELECT operation with a conjunctive (AND)
condition; that is,
<cond1> <condn>(R <cond1> AND<cond2> AND ... AND <condn>(R)
In SQL, the SELECT condition is specified in the WHERE clause of a [Link] example, the following
operation:
Dno=4 AND Salary>25000 (EMPLOYEE)
would to the following SQL query:
SELECT * FROM EMPLOYEE WHERE Dno=4 AND Salary>25000;

2.1.2 The PROJECT Operation

The PROJECT operation denoted by selects certain columns from the table and discards the other
columns Used when we are interested in only certain attributes of a relation. The result of the
PROJECT operation can be visualized as a vertical partition of the relation into two relations:
- one has the needed columns (attributes) and contains the result of the operation
- the other contains the discarded columns
The general form of the PROJECT operation is

<attribute list>(R)

where
- symbol used to represent the PROJECT operation,
<attributelist> - desired sublist of attributes from the attributes of relation R.
The result of the PROJECT operation has only the attributes specified in <attribute list> in the same order
as they appear in the list. Hence, its degree is equal to the number of attributes in <attribute list>

[Link]
 Database Management System [BCS403] ]

Example :

1. T
follows:

Lname, Fname, Salary(EMPLOYEE)

If the attribute list includes only nonkey attributes of R, duplicate tuples are likely to
occur. The result of the PROJECT operation is a set of distinct tuples, and hence a valid
relation. This is known as duplicate [Link] example, consider the following
PROJECT operation:

gender, Salary(EMPLOYEE)

T resulting relation even though this combination of

values appears twice in the EMPLOYEE relation.
The number of tuples in a relation resulting from a PROJECT operation is always less than or equal
to the number of tuples in R. Commutativity does not hold on PROJECT
<list1> <list2>(R <list1>(R)

as long as <list2> contains the attributes in <list1>; otherwise, the left-hand side is an incorrect
expression.
In SQL, the PROJECT attribute list is specified in the SELECT clause of a query. For example, the
following operation:
gender, Salary(EMPLOYEE)

would correspond to the following SQL query:

SELECT DISTINCT gender, Salary FROM EMPLOYEE

Sequences of Operations and the RENAME Operation

[Link]
 Database Management System [BCS403] ]
For most queries, we need to apply several relational algebra operations one after the other. Either
we can write the operations as a single relational algebra expression by nesting the operations, or we
can apply one operation at a time and create intermediate result relations. In the latter case, we must
give names to the relations that hold the intermediate results.
For example, to retrieve the first name, last name, and salary of all employees who work in
department number 5, we must apply a SELECT and a PROJECT operation. We can write a single
relational algebra expression, also known as an in-line expression, as follows:
Fname, Lname, Salary( Dno=5(EMPLOYEE))

Alternatively, we can explicitly show the sequence of operations, giving a name to each intermediate
relation, as follows:
Dno=5(EMPLOYEE)

Fname, Lname, Salary(DEP5_EMPS)

We can also use this technique to rename the attributes in the intermediate and result relations. To
rename the attributes in a relation, we simply list the new attribute names in parentheses
Dno=5(EMPLOYEE)

R Fname, Lname, Salary(TEMP)

If no renaming is applied, the names of the attributes in the resulting relation of a SELECT operation
are the same as those in the original relation and in the same [Link] a PROJECT operation with no
renaming, the resulting relation has the same attribute names as those in the projection list and in the
same order in which they appear in the list.
We can also define a formal RENAME operation which can rename either the relation name or the
attribute names, or both as a unary operator.

[Link]
 Database Management System [BCS403] ]

The general RENAME operation when applied to a relation R of degree n is denoted by any of the
following three forms:

1. S(B1, B2, ..., Bn)(R) RENAME operator

2. S(R) S new relation name

3. (B1, B (R) B1,B2 n- new attribute names

The first expression renames both the relation and its attributes. Second renames the relation only
and the third renames the attributes [Link] the attributes of R are (A 1, A2, ..., An) in that order, then
each Ai is renamed as Bi.

Renaming in SQL is accomplished by aliasing using AS, as in the following example:

SELECT [Link] AS First_name,

[Link] AS Last_name,

[Link] AS Salary

FROM EMPLOYEE AS E

WHERE [Link]=5,

Relational Algebra Operations from Set Theory

The UNION, INTERSECTION, and MINUS Operations

UNION: The result of this operation, denoted by R S, is a relation that includes all tuples
that are either in R or in S or in both R and S. Duplicate tuples are eliminated.
INTERSECTION: The result of this operation, denoted by R S, is a relation that includes
all tuples that are in both R and S.
SET DIFFERENCE (or MINUS): The result of this operation, denoted by R S, is a
relation that includes all tuples that are in R but not in S.
Example: Consider the the following two relations: STUDENT & INSTRUCTOR

[Link]
 Database Management System [BCS403] ]

STUDENT INSTRUCTOR STUDENT INSTRUCTOR

STUDENT INSTRUCTOR

Example: To retrieve the Social Security numbers of all employees who either work in department 5
or directly supervise an employee who works in department 5

Dno=5(EMPLOYEE)

Ssn(DEP5_EMPS)

Super_ssn(DEP5_EMPS)

RESULT2

[Link]
 ]

Single relational algebra expression:

Ssn Dno=5 (EMPLOYEE) ) Super_ssn ( Dno=5 (EMPLOYEE))

UNION, INTERSECTION and SET DIFFERENCE are binary operations; that is, each is applied to
two sets (of tuples). When these operations are adapted to relational databases, the two relations on
which any of these three operations are applied must have the same type of tuples; this condition has
been called union compatibility or type compatibility.
Two relations R(A1, A2, ..., An) and S(B1, B2, ..., Bn) are said to be union compatible (or type
compatible) if they have the same degree n and if dom(Ai) = dom(Bi
the two relations have the same number of attributes and each corresponding pair of attributes has
the same domain.
Both UNION and INTERSECTION are commutative operations; that is,

R S=S R and R S=S R

Both UNION and INTERSECTION can be treated as n-ary operations applicable to any number of
relations because both are also associative operations; that is,

R (S T) = (R S) T and (R S T=R S T)

The MINUS operation is not commutative; that is, in general,

R S S R

INTERSECTION can be expressed in terms of union and set difference as follows:

In SQL, there are three operations UNION, INTERSECT, and EXCEPT that correspond to the
set operations

]
\
The CARTESIAN PRODUCT (CROSS PRODUCT) Operation

The CARTESIAN PRODUCT operation also known as CROSS PRODUCT or CROSS JOIN
[Link]
 denoted by × is a binary set operation, but the relations on which it is applied do not have to be
union compatible. This set operation produces a new element by combining every member (tuple)
from one relation (set) with every member (tuple) from the other relation (set)

In general, the result of R(A1, A2, ..., An) × S(B1, B2, ..., Bm) is a relation Q with degree n + m
attributes Q(A1, A2, ..., An, B1, B2, ..., Bm), in that order. The resulting relation Q has one tuple for
each combination of tuples one from R and one from S. Hence, if R has nR tuples (denoted as |R| =
nR), and S has nS tuples, then R × S will have nR * nS tuples
Example
(EMPLOYEE)
Fname, Lname, Ssn(FEMALE_EMPS)

Ssn=Essn(EMP_DEPENDENTS)

Fname, Lname, Dependent_name (AC TUAL_DEPENDENTS)

[Link]
 ]

The CARTESIAN PRODUCT creates tuples with the combined attributes of two relations. We
can SELECT related tuples only from the two relations by specifying an appropriate selection
condition after the Cartesian product.
In SQL, CARTESIAN PRODUCT can be realized by using the CROSS JOIN option in joined
tables

Binary Relational Operations: JOIN and DIVISION

The JOIN Operation

The JOIN operation, denoted by is used to combine related tuples from two relations into
It allows us to process relationships among [Link] general form of a
JOIN operation on two relations R(A1, A2, ..., An) and S(B1, B2, ..., Bm) is

R <join conditio>S

Example: Retrieve the name of the manager of each department.

whose Ssn value matches the Mgr_ssn value in the department tuple

[Link]
 ]

The result of the JOIN is a relation Q with n + m attributes Q(A 1, A2, ..., An,B1, B2, ..., Bm in that
order.Q has one tuple for each combination of tuples one from R and one from S whenever the
combination satisfies the join condition. This is the main difference between CARTESIAN
PRODUCT and JOIN. In JOIN, only combinations of tuples satisfying the join condition appear
in the result, whereas in the CARTESIAN PRODUCT all combinations of tuples are included in
the result. The join condition is specified on attributes from the two relations R and S and is
evaluated for each combination of tuples.

Each tuple combination for which the join condition evaluates to TRUE is included in the resulting
relation Q as a single combined tuple. A general join condition is of the form

<condition> AND <condition> AND...AND <condition>

where each <condition> is of the form Ai Bj, Ai is an attribute of R, B is an attribute of S, Ai

and Bj A
JOIN operation with such a general join condition is called a THETA JOIN. Tuples whose join
attributes are NULL or for which the join condition is FALSE do not appear in the result.

2.1.3 Variations of JOIN: The EQUIJOIN and NATURAL JOIN

The most common use of JOIN involves join conditions with equality comparisons only. Such a
JOIN, where the only comparison operator used is =, is called an EQUIJOIN. In the result of an
EQUIJOIN we always have one or more pairs of attributes that have identical values in every tuple.

For example the values of the attributes Mgr_ssn and Ssn are identical in every tuple of
DEPT_MGR (the EQUIJOIN result) because the equality join condition specified on these two
attributes requires the values to be identical in every tuple in the result.

The standard definition of NATURAL JOIN requires that the two join attributes (or each pair of
join attributes) have the same name in both relations. If this is not the case, a renaming operation is
applied first. Suppose we want to combine each PROJECT tuple with the DEPARTMENT tuple that
controls the project. first we rename the Dnumber attribute of DEPARTMENT to Dnum so that
it has the same name as the Dnum attribute in PROJECT and then we apply NATURAL JOIN:

(Dname, Dnum, Mgr_ssn, Mgr_start_date) (DEPARTMENT)

The same query can be done in two steps by creating an intermediate table DEPT as follows:

(Dname, Dnum, Mgr_ssn,Mgr_start_date)(DEPARTMENT)

[Link]
 ]

The attribute Dnum is called the join attribute for the NATURAL JOIN operation, because it is the
only attribute with the same name in both relations.

If the attributes on which the natural join is specified already have the same names in both relations,
renaming is unnecessary. For example, to apply a natural join on the Dnumber attributes of
DEPARTMENT and DEPT_LOCATIONS, it is sufficient to write

In general, the join condition for NATURAL JOIN is constructed by equating each pair of join
attributes that have the same name in the two relations and combining these conditions with AND.
If no combination of tuples satisfies the join condition, the result of a JOIN is an empty relation with
zero tuples.
A more general, but nonstandard definition for NATURAL JOIN is

where,

<list1> : list of i attributes from R,

<list2> : list of i attributes from S

The lists are used to form equality comparison conditions between pairs of corresponding attributes
and then the conditions are then ANDed together. Only the list corresponding to attributes of the first
relation R <list1> is kept in the result Q.
 Database Management System [BCS403] ]

In general, if R has nR tuples and S has nS tuples, the result of a JOIN operation R <join condition> S
will have between zero and nR * nS tuples. The expected size of the join result divided by the
maximum size nR * nS leads to a ratio called join selectivity, which is a property of each join
condition. If there is no join condition, all combinations of tuples qualify and the JOIN degenerates
into a CARTESIAN PRODUCT, also called CROSS PRODUCT or CROSS JOIN.

A single JOIN operation is used to combine data from two relations so that related information can
be presented in a single table. These operations are also known as inner joins. Informally, an inner
join is a type of match and combine operation defined formally as a combination of CARTESIAN
PRODUCT and [Link] NATURAL JOIN or EQUIJOIN operation can also be specified
among multiple tables, leading to an n-way join. For example, consider the following three-way join:

This combines each project tuple with its controlling department tuple into a single tuple, and then
combines that tuple with an employee tuple that is the department manager. The net result is a
consolidated relation in which each tuple contains this project-department-manager combined
information.
In SQL, JOIN can be realized in several different ways
- The first method is to specify the <join conditions> in the WHERE clause, along with any
other selection conditions.
- The second way is to use a nested relation
- Another way is to use the concept of joined tables

A Complete Set of Relational Algebra Operations

, ×} is a complete set; that is, any of the other

original relational algebra operations can be expressed as a sequence of operations from this set.
For example, the INTERSECTION operation can be expressed by using UNION and MINUS as
follows:

R S R S) ((R S) (S R))

As another example, a JOIN operation can be specified as a CARTESIAN PRODUCT followed by a

SELECT operation,
 Database Management System [BCS403] ]

Similarly, a NATURAL JOIN can be specified as a CARTESIAN PRODUCT preceded by

RENAME and followed by SELECT and PROJECT operations. Hence, the various JOIN operations
are also not strictly necessary for the expressive power of the relational algebra.

The DIVISION Operation

The DIVISION operation, denoted by ÷, is useful for a special kind of query that sometimes occurs
in database applications. An example is Retrieve the names of employees who work on all the
this query using the DIVISION operation, proceed
as follows.

relation SMITH_PNOS:

Next, create a relation that includes a tuple <Pno, Essn> whenever the employee whose Ssn is
Essn works on the project whose number is Pno in the intermediate relation SSN_PNOS:

Finally, apply the DIVISION operation to the two relations, which gives the desired

[Link]
 Database Management System [BCS403] ]

In general, the DIVISION operation is applied to two relations R(Z) ÷ S(X), where the attributes of
R are a subset of the attributes of S; that is, X [Link] Y be the set of attributes of R that are not
attributes of S; that is, Y = Z X (and hence Z = X Y). The result of DIVISION is a relation T(Y)
that includes a tuple t if tuples tR appear in R with tR [Y] = t, and with tR [X] = tS for every tuple tS in
S. This means that, for a tuple t to appear in the result T of t

Figure below illustrates a DIVISION operation where X = {A}, Y = {B}, and Z = {A, B}.

The tuples (values) b1 and b4 appear in R in combination with all three tuples in S; that is why they
appear in the resulting relation T. All other values of B in R do not appear with all the tuples in S and
are not selected: b2 does not appear with a2, and b3 does not appear with a1.
operations as follows:

[Link]
 ]

Notation for Query Trees

Query tree (query evaluation tree or query execution tree) is used in relational systems to represent
queries internally. A query tree is a tree data structure that corresponds to a relational algebra
expression. It represents the input relations of the query as leaf nodes of the tree, and represents the
relational algebra operations as internal nodes.

An execution of the query tree consists of executing an internal node operation whenever its
operands represented by its child nodes are available, and then replacing that internal node by the
relation that results from executing the operation. The execution terminates when the root node is
executed and produces the result relation for the query.

[Link]
 ]

roject number, the controlling department

Leaf nodes P, D, and E represent the three relations PROJECT, DEPARTMENT, and EMPLOYEE.
The relational algebra operations in the expression are represented by internal tree nodes. The query
tree signifies an explicit order of execution in the following sense. The node marked (1) must begin
execution before node (2) because some resulting tuples of operation (1) must be available before
we can begin to execute operation (2). Similarly, node (2) must begin to execute and produce results
before node (3) can start execution, and so on.

A query tree gives a good visual representation and understanding of the query in terms of the
relational operations it uses and is recommended as an additional means for expressing queries in
relational algebra.

[Link]
 ]

Additional Relational Operations

Generalized Projection

The generalized projection operation extends the projection operation by allowing functions of
attributes to be included in the projection list. The generalized form can be expressed as:

F1, F2, ..., Fn (R)

where F1, F2, ..., Fn are functions over the attributes in relation R and may involve arithmetic
operations and constant values.
The generalized projection helpful when developing reports where computed values have to be
produced in the columns of a query result. For example,consider the relation EMPLOYEE (Ssn,
Salary,Deduction, Years_service). A report may be required to show
Net Salary = Salary Deduction,
Bonus = 2000 * Years_service, and
Tax = 0.25 * Salary.
generalized projection combined with renaming :

(Ssn, Net_salary, Bonus, Tax) Ssn, Salary Deduction, 2000 *

Years_service, 0.25 * Salary(EMPLOYEE)).

2.1.4 Aggregate Functions and Grouping

Aggregate functions are used in simple statistical queries that summarize information from the
database tuples. Common functions applied to collections of numeric values include
SUM,AVERAGE, MAXIMUM, and MINIMUM. The COUNT function is used for counting
tuples or values. For example, retrieving the average or total salary of all employees or the total
number of employee tuples.

Grouping the tuples in a relation by the value of some of their attributes and then applying an
aggregate function independently to each group. For example , group EMPLOYEE tuples by Dno, so
that each group includes the tuples for employees working in the same department. We can then list
each Dno value along with, say, the average salary of employees within the department, or the
number of employees who work in the department.

[Link]
 Database Management System [BCS403] ]

Aggregate function operation can be defined by using the symbol (script F) :

<grouping attributes> <function list> (R)

Where ,
<grouping attributes> : list of attributes of the relation specified in R
<function list> : list of (<function> <attribute>) pairs.
<function> - such as SUM, AVERAGE, MAXIMUM, MIN,IMUM,COUNT
<attribute> is an attribute of the relation specified by R
The resulting relation has the grouping attributes plus one attribute for each element in the function
list.
Example: To retrieve each department number, the number of employees in the department, and
their average salary, while renaming the resulting attributes

R(Dno, No_of_employees, Average_sal)(Dno COUNT Ssn, AVERAGE Salary (EMPLOYEE))

2.1.5 Recursive Closure Operations

Recursive closure operation is applied to a recursive relationship between tuples of the same type,
such as the relationship between an employee and a supervisor.
Example : Retrieve all supervisees of an employee e at all levels that is, all employees e
supervised by e, all employees directly supervised by each employee e
directly supervised by each employee e

[Link]
 Database Management System [BCS403] ]

To retrieve all employees supervised by Borg at level 2 that is, all employees supervised by
some employee who is directly supervised by Borg we can apply another JOIN to the result
of the first query, as follows:

UNION operation to the two results, as follows:

2.1.6 OUTER JOIN Operations

The JOIN operations match tuples that satisfy the join condition. For example, for a NATURAL
JOIN operation R * S, only tuples from R that have matching tuples in S and vice versa
appear in the result. Hence, tuples without a matching (or related) tuple are eliminated from the

[Link]
 Database Management System [BCS403]]

JOIN result. Tuples with NULL values in the join attributes are also eliminated. This type of join,
where tuples with no match are eliminated, is known as an inner join.
A set of operations, called outer joins, were developed for the case where the user wants to keep
all the tuples in R, or all those in S, or all those in both relations in the result of the JOIN,
regardless of whether or not they have matching tuples in the other relation.

For example, suppose that we want a list of all employee names as well as the name of the
departments they manage if they happen to manage a department; if they do not manage one, we
can indicate it with a NULL value. We can apply an operation LEFT OUTER JOIN, denoted by

to retrieve the result as follows:

The LEFT OUTER JOIN operation keeps every tuple in the first, or left, relation R in

R S; if no matching tuple is found in S, then the attributes of S in the join result are
filled or padded with NULL values.

A similar operation, RIGHT OUTER JOIN, denoted by

of R S.
A third operation, FULL OUTER JOIN, denoted by , keeps all tuples in both the left
and the right relations when no matching tuples are found, padding them with NULL values as
needed.

The OUTER UNION Operation

The OUTER UNION operation was developed to take the union of tuples from two relations
that have some common attributes, but are not union (type) compatible. This operation will take
the UNION of tuples in two relations R(X, Y) and S(X, Z) that are partially compatible,
meaning that only some of their attributes, say X, are union compatible.
[Link]
 Database Management System [BCS403]]
The attributes that are union compatible are represented only once in the result, and those
attributes that are not union compatible from either relation are also kept in the result relation
T(X, Y, Z). Two tuples t1 in R and t2 in S are said to match if t1[X]= t2[X]. These will be
combined (unioned) into a single tuple in t. Tuples in either relation that have no matching tuple
in the other relation are padded with NULL values.
For example, an OUTER UNION can be applied to two relations whose schemas are:
STUDENT(Name, Ssn, Department, Advisor)
INSTRUCTOR(Name, Ssn, Department, Rank)
Tuples from the two relations are matched based on having the same combination of values of
the shared attributes Name, Ssn, Department. All the tuples from both relations are included in
the result, but tuples with the same (Name, Ssn, Department) combination will appear only once
in the result. Tuples appearing only in STUDENT will have a NULL for the Rank attribute,
whereas tuples appearing only in INSTRUCTOR will have a NULL for the Advisor attribute.
A tuple that exists in both relations, which represent a student who is also an instructor, will
have values for all its attributes The resulting relation, STUDENT_OR_INSTRUCTOR, will
have the following attributes:
STUDENT_OR_INSTRUCTOR(Name, Ssn, Department, Advisor, Rank)

Examples of Queries in Relational Algebra

Query 1. Retrieve the name and address of all employees who work for the

Query 2. controlling department

address, and birth date.

[Link]
 Database Management System [BCS403] ]

Query 3. Find the names of employees who work on all the projects
controlled by department number 5.

Query 4. Make a list of project numbers for projects that involve an employee whose last
name is
that controls the project.

Query 5. List the names of all employees with two or more dependents.

Query 6. Retrieve the names of employees who have no dependents.

Query 7. List the names of mana gers who have at least one dependent.

[Link]
 Database Management System [BCS403] ]

[Link]