Chapter 6

Relational Query Languages

Introduction
Query languages: Allow manipulation
and retrieval of data from a database.
„
Query Languages != programming
languages!
„
QLs not intended to be used for complex
calculations.
„
QLs support easy, efficient access to large
data sets.
„
Relational model supports simple, powerful
query languages.
Cont…
 Formal Relational Query Languages
„There are varieties of Query languages used
by relational DBMS for manipulating
relations.
 „Some of them are procedural
 „User tells the system exactly what and how
to manipulate the data
 Others are non-procedural
„User states what data is needed rather than
how it is to be retrieved.
 Cont…
 Two mathematical Query Languages form the
basis for Relational languages
◦ „Relational Algebra:
◦ „Relational Calculus
 We may describe the relational algebra as
procedural language: it can be used to tell the
DBMS how to build a new relation from one
or more relations in the database.
 We may describe relational calculus as a non
procedural language: it can be used to
formulate the definition of a relation in terms
of one or more database relations.
Cont…
Formally the relational algebra and
relational calculus are equivalent to each
other. For every expression in the algebra,
there is an equivalent expression in the
calculus.
„
Both are non-user friendly languages. They
have been used as the basis for other,
higher-level data manipulation languages for
relational databases.
Cont…
 A query is applied to relation instances,
and the result of a query is also a relation
instance.
 „Schemas of input relations for a query
are fixed
 „The schema for the result of a given
query is also fixed! Determined by
definition of query language constructs.
Relational Algebra
 The basic set of operations for the relational
model is known as the relational algebra.
 These operations enable a user to specify
basic retrieval requests.
 The result of the retrieval is a new relation,
which may have been formed from one or
more relations.
 The algebra operations thus produce new
relations, which can be further manipulated
using operations of the same algebra.
 Cont…
 A sequence of relational algebra operations
forms a relational algebra expression, whose
result will also be a relation that represents
the result of a database query (or retrieval
request).
 Relational algebra is a theoretical language
with operations that work on one or more
relations to define another relation without
changing the original relation.
 „The output from one operation can become
the input to another operation (nesting is
possible)
Cont…
 There are different basic operations that could be
applied on relations on a database based on the
requirement.
 Selection ( σ ) Selects a subset of rows from a
„
relation.
 Projection ( π ) Deletes unwanted columns from a
„
relation.
 „Renaming: assigning intermediate relation for a
single operation
 „Cross-Product (x ) Allows us to combine two
relations.
 „Set-Difference ( - ) Tuples in relation1, but not in
relation2.
 Union (∪ ) Tuples in relation1 or in relation2.
 Intersection (∩) Tuples in relation1 and in relation2
 Join ( ) Tuples joined from two relations based on
a condition
Cont…
Example:Table1
 Sample table used to illustrate different
kinds of relational operations.
 The relation contains information about
employees, IT skills they have and the
school where they attend each skill
Employee table
Selection
Selects subset of tuples/rows in a relation that
satisfy selection condition.
„
Selection operation is a unary operator (it is
applied to a single relation)
„
The Selection operation is applied to each
tuple individually
„
The degree of the resulting relation is the
same as the original relation but the
cardinality (no. of tuples) is less than or equal
to the original relation.
„
The Selection operator is commutative.
Cont…
 Set of conditions can be combined using
Boolean operations (∧(AND), ∨(OR), and
~(NOT))
 No duplicates in result!
 Schema of result identical to schema of (only)
input relation.
 Result relation can be the input for another
relational algebra operation! (Operator
composition.)
 It is a filter that keeps only those tuples that
satisfy a qualifying condition (those satisfying
the condition are selected while others are
discarded.)
Cont…

 This query will extract every tuple from

a relation called Employee with all the
attributes where the SkillType attribute
with a value of “Database”.
Cont…
 The resulting relation will be the following.

 If the query is all employees with a SkillType

Database and School Unity the relational
algebra operation and the resulting relation
will be as follows.
 Projection
 Selects certain attributes while discarding the other
from the base relation.
 „The PROJECT creates a vertical partitioning – one with
the needed columns (attributes) containing results of
the operation and other containing the discarded
Columns.
 „Deletes attributes that are not in projection list.
 „Schema of result contains exactly the fields in the
projection list, with the same names that they had in the
(only) input relation.
 „Projection operator has to eliminate duplicates!
 „Note: real systems typically don‟t do duplicate
elimination unless the user explicitly asks for it.
 „If the Primary Key is in the projection list, then
duplication will not occur
 „Duplication removal is necessary to insure that the
resulting table is also a relation.
Cont…
 Cont…
 If we want to have the Name, Skill, and Skill
Level of an employee with Skill SQL and
SkillLevel greater than 5 the query will be:
Rename Operation
 We may want to apply several relational
algebra operations one after the other.
 The query could be written in two different
forms:
1. Write the operations as a single relational
algebra expression by nesting the operations.
2. 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 Rename Operation
 If we want to have the Name, Skill, and
Skill Level of an employee with salary
greater than 1500 and working for
department 5, we can write the expression
for this query using the two alternatives:
 A single algebraic expression:
 The above used query is using a single
algebra operation, which is:
 Using an intermediate relation by the
Rename Operation:

 Then Result will be equivalent with the

relation we get using the first alternative.
UNION Operation
 The result of this operation, denoted by R U
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.
 The two operands must be “type
compatible”.
Type Compatibility
 The operand relations R1(A1, A2, ..., An) and
R2(B1, B2, ..., Bn) must have the same number
of attributes, and the domains of
corresponding attributes must be compatible;
that is, Dom(Ai)=Dom(Bi) for i=1, 2, ..., n.
 Cont…
 The resulting relation for;
 R1 ∪ R2,
 R1 ∩ R2, or
 R1-R2 has the same attribute names as the
first operand relation R1 (by convention).
INTERSECTION Operation
 The result of this operation, denoted by R ∩ S,
is a relation that includes all tuples that are in
both R and S. The two operands must be "type
compatible"
 Cont…
Set Difference (or MINUS) Operation
 The result of this operation, denoted by R - S, is a
relation that includes all tuples that are in R but not in S.
The two operands must be "type compatible”.
Some Properties of the Set Operators
 Notice that 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-nary
operations applicable to any number of relations as both
are 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
CARTESIAN (cross product) Operation

 This operation is used to combine tuples from two

relations in a combinatorial fashion.
 That means, every tuple in Relation1(R) one will be
related with every other tuple in Relation2 (S).
 In general, the result of R(A1, A2, . . ., An) x S(B1,B2, .
. ., Bm) is a relation Q with degree n + m attributes
Q(A1, A2, . . ., An, B1, B2, . . ., Bm), in that order.
 Where R has n attributes and S has m attributes.
 The resulting relation Q has one tuple for each
combination of tuples:-one from R and one from S.
 Hence, if R has n tuples, and S has m tuples, then
| R x S | will have n* m tuples.
Cont…
 The two operands do NOT have to be
"type compatible”

 Then Employee X Dept will be of the form:

Cont…

 Then to extract employee information about

managers of the departments, the algebra
query and the resulting relation will be.
JOIN Operation
 The sequence of Cartesian product followed
by select is used quite commonly to identify
and select related tuples from two relations, a
special operation, called JOIN.
 Thus in JOIN operation, the Cartesian
Operation and the Selection Operations
are used together.
 JOIN Operation is denoted by a symbol.
 This operation is very important for any
relational database with more than a single
relation, because it allows us to process
relationships among relations.
Cont…
The general form of a join operation on two
relations
R(A1, A2,. . ., An) and S(B1, B2, . . ., Bm) is:

 Where R and S can be any relations that

result from general relational algebra
expressions.
 Since JOIN function in two relation, it is a
Binary operation.
Cont…

 Example:
 Thus in the above example we want to
extract employee information about
managers of the departments, the algebra
query using the JOIN operation will be.
 EQUIJOIN Operation
 The most common use of join involves join
conditions with equality comparisons only ( = ).
 Such a join, where the only comparison
operator used is called an EQUIJOIN.
 In the result of an EQUIJOIN we always have
one or more pairs of attributes (whose names
need not be identical) that have identical values
in every tuple since we used the equality logical
operator.
 For example, the above JOIN expression is an
EQUIJOIN since the logical operator used is
the equal to operator ( =).
NATURAL JOIN Operation
 The standard definition of natural join
requires that the two join attributes, or
each pair of corresponding join attributes,
have the same name in both relations.
 If this is not the case, a renaming operation
on the attributes is applied first.
OUTER JOIN Operation
 OUTER JOIN is another version of the
JOIN operation where non matching
tuples from the first Relation are also
included in the resulting
 Relation where attributes of the second
Relation for a non matching tuples from
Relation one will have a value of NULL
 Notation:
 Cont…
 When two relations are joined by a JOIN
operator, there could be some tuples in the
first relation not having a matching tuple
from the second relation, and the query is
interested to display these non matching
tuples from the first relation.
 Such query is represented by the OUTER
JOIN.
SEMIJOIN Operation
 A join where the result only contains
the columns from one of the joined
tables.
 Useful in distributed databases, so we
don't have to send as much data over the
network.
Relational Calculus
 A relational calculus expression creates a new
relation, which is specified in terms of
variables that range over rows of the stored
database relations (in tuple calculus) or over
columns of the stored relations (in domain
calculus).
 In a calculus expression, there is no order of
operations to specify how to retrieve the
query result.
 A calculus expression specifies only what
information the result should contain
rather than how to retrieve it.
 Cont…
 In Relational calculus, there is no description
of how to evaluate a query, this is the main
distinguishing feature between relational
algebra and relational calculus.
 Relational calculus is considered to be a
nonprocedural language.
 This differs from relational algebra, where we
must write a sequence of operations to specify
a retrieval request; hence relational algebra
can be considered as a procedural way of
stating a query.
 Cont…
 When applied to relational database, the calculus is
not that of derivative and differential but in a
form of first-order logic or predicate calculus, a
predicate is a truth-valued function with arguments.
 When we substitute values for the arguments in the
predicate, the function yields an expression, called a
proposition, which can be either true or false.
 If a predicate contains a variable, as in ‘x is a
member of staff ’, there must be a range for x.
When we substitute some values of this range for x,
the proposition may be true; for other values, it may
be false.
 Cont…
 If COND is a predicate, then the set off all
tuples evaluated to be true for the predicate
COND will be expressed as follows:

 Where t is a tuple variable and COND (t)

is a conditional expression involving t.
 The result of such a query is the set of all
tuples t that satisfy COND (t).
 If we have set of predicates to evaluate for a
single query, the predicates can be connected
using ∧(AND), ∨(OR), and ~(NOT)
Cont…
 A relational calculus expression creates
a new relation, which is specified in terms
of variables that range over rows of the
stored database relations (in tuple
calculus) or over columns of the stored
relations (in domain calculus).
Tuple-oriented Relational Calculus
 The tuple relational calculus is based on specifying
a number of tuple variables.
 Each tuple variable usually ranges over a
particular database relation, meaning that the
variable may take as its value any individual tuple
from that relation.
 Tuple relational calculus is interested in finding
tuples for which a predicate is true for a relation.
Based on use of tuple variables.
 Tuple variable is a variable that „ranges over‟ a
named relation: that is, a variable whose only
permitted values are tuples of the relation.
 If E is a tuple that ranges over a relation employee,
then it is represented as EMPLOYEE(E) i.e. Range
of E is EMPLOYEE
Cont…
 Then to extract all tuples that satisfy a
certain condition, we will represent is as all
tuples E such that COND(E) is evaluated
to be true.

 The predicates can be connected using the

Boolean operators:
 Cont…
 COND(t) is a formula, and is called a Well-
Formed-Formula (WFF) if:
 Where the COND is composed of n-nary
predicates (formula composed of n single
predicates) and the predicates are connected by
any of the Boolean operators.
 And each predicate is of the form A θ B and θ is
one of the logical operators { <, ≤ , >, ≥, ≠, = }which
could be evaluated to either true or false.
◦ And A and B are either constant or variables.
 Formulae should be unambiguous and should make
sense.
Cont…
 Example (Tuple Relational Calculus)
 Extract all employees whose skill
level is greater than or equal to 8
 {E | Employee(E) ∧ E.SkillLevel >= 8}
 Cont…
 To find only the EmpId, FName, LName,
Skill and the School where the skill is
attended where of employees with skill level
greater than or equal to 8, the tuple based
relational calculus expression will be:
{E.EmpId, E.FName, E.LName, E.Skill,
E.School | Employee(E) ∧ E.SkillLevel >= 8}
Quantifiers in Relation Calculus
 To tell how many instances the predicate
applies to, we can use the two quantifiers
in the predicate logic.
 One relational calculus expressed using
Existential Quantifier can also be
expressed using Universal Quantifier.
Existential quantifier ∃ (‘there exists’)

 Existential quantifier used in formulae that

must be true for at least one instance, such
as:
 An employee with skill level greater than or
equal to 8 will be:
{E | Employee(E) ∧ (∃E)(E.SkillLevel >= 8)}
 This means, there exist at least one tuple of
the relation employee where the value for
the SkillLevel is greater than or equal to 8
Universal quantifier ∀ (‘for all’)
 Universal quantifier is used in statements
about every instance, such as:
 An employee with skill level greater than
or equal to 8 will be:
{E | Employee(E) ∧ (∀E)(E.SkillLevel >= 8)}
 This means, for all tuples of relation
employee where value for the SkillLevel
attribute is greater than or equal to 8.
 Example:
 Let‟s say that we have the following Schema
(set of Relations)
Employee(EID, FName, LName, Dept)
Project(PID, PName, Dept)
Dept(DID, DName, DMangID)
WorksOn(EID, PID)
To find employees who work on projects
controlled by department 5 the query will be:
{E | Employee(E) ∧ (∀x)(Project(x) ∧
(∃w)(WorksOn(w) ∧ x.Dept=5 ∧ E.EID=W.EID))}