UNIT – II Relational Algebra

Relational Model

 A Relation is a mathematical concept based on the ideas of sets.

 Relational model is most widely used data model for commercial data-
processing. The reason it’s used so much is, simple and easy to
maintain.
 The model is based on a collection of tables. Users of the database can
create tables, insert new tables or modify existing tables. There are several
languages for database programming.
 SQL, Oracle, etc.
 Data is stored in tables called relations.
 Relations can be normalized.
 In normalized relations, values saved are atomic values.
 Each row in relation contains unique value
 Each column in relation contains values from a same domain.
Structure of Relational Databases

 A relational database is a collection of tables.The relational model

represents the database as a collection of relations
o Each table has a unique name.
o Each table consists of multiple rows.
o Each row is a set of values that by definition are related to each other
in someway; these values conform to the attributes or columns of
the table.
o Each attribute of a table defines a set of permitted values for that
attribute; this set of permitted set is the domain of that attribute.
 Each relation resembles a table of values
 When a relation is thought of as a table of values, each row in the table
represents a collection of related data values.

Attributes

 Attributes of a relation serve as names for the columns of the relation.

Usually, an attribute describes the meaning of entries in the column
below.
 Table = relation.
 Column headers = attributes.
Domains

 A Domain D is a set of atomic values.

 The set of allowed values for each attribute is called the domain of the
attribute
 Atomic means that each value in the domain is indivisible as far as the
relational model is concerned
 It means that if we separate an atomic value, the value itself become
meaningless, for example:
o SSN
o Local_phone_number
o Names
o Employee_ages..
 The special value null is a member of every domain
  The null value causes complications in the definition of many operations
We shall ignore the effect of null values in our main presentation and
consider their effect later

Tuples

 The rows of a relation, other than the header row containing. The attribute
names are called tuples.
 A tuple has one component for each attribute of the relation.

Relational Algebra
Basic or Fundamental operations:
1) Selection (σ ) Selects a subset of rows from relation unary
operations
2) Projection (π ) Deletes unwanted columns from relation
3) Union (U) Tuples in reln.1 and in reln. 2
4) Set-difference (- ) Tuples in reln. 1, but not in reln. 2 Binary
operations
5) Cross-product (× ) Allows us to combine two relations
6) Rename (ρ) unary operations

Additional operations:
 Intersection (∩), join(⟗)(INNER JOIN(⟕),OUTER JOIN(⟖)), division(÷),
renaming: not essential, but very useful
 Since each operation returns a relation, operations can be composed.
(Algebra is “closed”)
1. Selection (σ (sigma)):
 Selects tuples that satisfy the given predicate from a relation.
 This is a unary operation which returns a relation.
 A Comparison predicate is one of: =, ≠, >, ≥, <, ≤and also use
Predicates connectives : ∧(and), ∨(or), (not)
Example:
 σsubject="database"(Books) Output : Selects tuples from books where subject is
'database'.
  σsubject="database"and price="450"(Books) Output : Selects tuples from books
where subject is 'database' and 'price' is 450.
 σsubject="database"and price <"450"or year >"2010"(Books) Output : Selects tuples from
books where subject is 'database' and 'price' is 450 or the publication year
is greater than 2010, that is published after 2010.

2. Projection (π (pi))

 Projects column(s) that satisfy given predicate.

 Notation: ∏A1, A2, An (r)
 Where a1, a2 , an are attribute names of relation r.
 Duplicate rows are automatically eliminated, as relation is a set.

Example:∏subject, author(Books) Selects and projects columns named as subject

and author from relation Books.
3. Union Operation (∪)

 Union operation performs binary union between two given

relations.
 Notion: r U s
 Where r and s are either database relations or relation result set
(temporary relation).
 For a union operation to be valid, the following conditions must hold:
 r, s must have same number of attributes.
 Attribute domains must be compatible.
 Duplicate tuples are automatically eliminated.

Example:∏author(Books)∪∏author(Articles)Output : Projects the name of

author who has either written a book or an article or both.
4. Set Difference ( − )

 The result of set difference operation is tuples which present in one

relation but are not in the second relation.
 Notation: r − s
 Finds all tuples that are present in r but not s.

Example ;∏author(Books)−∏author(Articles) Output: Results the name of

authors who has written books but not articles.

5. Cartesian Product (Χ)

 Combines information of two different relations into one.

 Notation: r Χ s.

∏author='tutorialspoint'(BooksΧArticles)Output : yields a relation as result which shows

all books and articles written by tutorialspoint.
6. Rename operation ( ρ )
Rename (ρ (rho))
 This is a unary operator which changes attribute names for a relation
without changing any values.
 Renaming removes the limitations associated with set operators.
 Notation: ρ x (E)
 Where the result of expression E is saved with name of x.

Notation:
ρOldName→NewName(r)
For example,
ρFather→Parent(Paternity)

Additional operations are:

 Set intersection
 Assignment
 Natural join

JOIN Operator

 JOIN is used to combine related tuples from two relations:

 In its simplest form the JOIN operator is just the cross product of the two
relations.
  As the join becomes more complex, tuples are removed within the cross
product to make the result of the join more meaningful.
 JOIN allows you to evaluate a join condition between the attributes of the
relations on which the join is undertaken.

JOIN Example

Natural Join(⋈)
Courses
CID Course Dept
CS01 Database CS
ME01 Mechanics ME
EE01 Electronics EE
[Table: Relation Courses]
HoD
Dept Head
CS Alex
ME Maya
EE Mira
[Table: Relation HoD]
 Courses ⋈HoD
Dept CID Course Head
CS CS01 Database Alex
ME ME01 Mechanics Maya
EE EE01 Electronics Mira
[Table: Relation Courses ⋈HoD]

 Invariably the JOIN involves an equality test, and thus is often described
as an equi-join. Such joins result in two attributes in the resulting relation
having exactly the same value. A `natural join' will remove the duplicate
attribute(s).
 In most systems a natural join will require that the attributes have the
same name to identify the attribute(s) to be used in the join. This may
require a renaming mechanism.
 If you do use natural joins make sure that the relations do not have two
attributes with the same name by accident.

OUTER JOINs

 An extension of the join operation that avoids loss of information.Thereare

three forms of the outer join, depending on which data is to be kept.
 LEFT OUTER JOIN - keep data from the left-hand table
 RIGHT OUTER JOIN - keep data from the right-hand table
 FULL OUTER JOIN - keep data from both tables

OUTER JOIN example 1

Outer Joins

 All joins mentioned above, that is Theta Join, Equi Join and Natural Join
are called inner-joins. An inner-join process includes only tuples with
matching attributes, rest are discarded in resulting relation. There exists
methods by which all tuples of any relation are included in the resulting
relation.
 There are three kinds of outer joins:

Left outer join ( R S)

 All tuples of Left relation, R, are included in the resulting relation and if
there exists tuples in R without any matching tuple in S then the S-
attributes of resulting relation are made NULL.

Left
A B
100 Database
101 Mechanics
102 Electronics
[Table: Left Relation]
Right
A B
100 Alex
102 Maya
104 Mira
[Table: Right Relation]
Courses HoD
A B C D
100 Database 100 Alex
101 Mechanics --- ---
102 Electronics 102 Maya
[Table: Left outer join output]
Right outer join: ( R S)

 All tuples of the Right relation, S, are included in the resulting relation and
if there exists tuples in S without any matching tuple in R then the R-
attributes of resulting relation are made NULL.

Courses HoD
A B C D
100 Database 100 Alex
102 Electronics 102 Maya
--- --- 104 Mira
[Table: Right outer join output]
Full outer join: ( R S)

 All tuples of both participating relations are included in the resulting

relation and if there no matching tuples for both relations, their respective
unmatched attributes are made NULL.

Courses HoD
A B C D
100 Database 100 Alex
101 Mechanics --- ---
102 Electronics 102 Maya
--- --- 104 Mira
[Table: Full outer join output]
Outer Join – Example

 if F is a conjunction of equalities, then we have an equi-join

SET INTERSECT
 Takes the data from both result sets which are in common.
 INTERSECT returns any distinct values that are returned by both the
query on the left and right sides of the INTERSECT operand.
 Notation: r ∩ s
viewplaincopy to clipboardprint?

1. SELECT Name,TotalMarks FROM students2000 INTERSECT

2. SELECT Name,TotalMarks FROM students2005

Result Relation r, s:

Only the Robert and Rose records are returned, because they are found in both
tables.
Division

 Notation: r / s or r ÷ s
 Useful for expressing queries that include a “for all” or “for every”
phrase,
 Goal: Produce the tuples in one relation, r, that match all tuples in another
relation, s
 r (A1, …An, B1, …Bm)
 s (B1 …Bm)
 r/s, with attributes A1, …An, is the set of all tuples <a> such that for
every tuple <b> in s, <a,b> is in rCan be expressed in terms of
projection, set difference, and cross-product

Examples of Division A/B

ASSIGNMENT OPERATOR

 The assignment operation (←) provides a convenient way toexpress

complex queries.
 Write query as a sequential program consisting of
 a series of assignments
 followed by an expression whose value is displayed as a result
of the query.
o Assignment must always be made to a temporary relation variable.
 The assignment operation which works a lot like assignements in a
programming language. Its notated with the left pointing arrow ←:

variable ← E, where E is any relational algebra expression.

Revisiting the breakdown of the division operation, we can use assignment to
rewrite

(1) this way: temp1 ← ΠR−S(r)

temp2 ← ΠR−S((temp1 × s) − ΠR−S,S(r))

r ÷ s = temp1 − temp2

Union
 Combine two or more result sets into a single set, without duplicates.
Ex.Create two tables with same column name and data type.

1. CREATE TABLE Students2000(Name VARCHAR(15), TotalMark number)

2. CREATE TABLE Stundents2005( Name VARCHAR(15), TotalMark number)
3. INSERT INTO Students2000 VALUES('Robert',1063);
4. INSERT INTO Students2000 VALUES('John',1070);
5. INSERT INTO Students2000 VALUES('Rose',1032);
6. INSERT INTO Students2000 VALUES('Abel',1002);
7.
8. INSERT INTO Students2005 VALUES('Robert',1063);
9. INSERT INTO Students2005 VALUES('Rose',1032);
10. INSERT INTO Students2005 VALUES('Boss',1086);
11. INSERT INTO Students2005 VALUES('Marry',1034);

Result
Result Set for Students2000 table Result Set for Students2005 table

UNION ALL
The SQL UNION ALL Operator is used to list all records from two or more select
statements. All the records from both tables must be in the same order.
viewplaincopy to clipboardprint?

1. SELECT Name,TotalMarks FROM students2000 UNION ALL

2. SELECT Name,TotalMarks FROM students2005
Result

UNION
The SQL Union ALL Operator is used to combine two tables using select
statement when both tables have the same number of columns.Union works like
Distinct. Union all DOES NOT do distinct.
viewplaincopy to clipboardprint?

1. SELECT Name,TotalMarks FROM students2000 UNION

2. SELECT Name,TotalMarks FROM students2005

Result

The Robert and Rose records are duplicate records. Thus, these are returned
only once.
RELATIONAL CALCULUS

 Relational calculus is nonprocedural

 It has the same expressive power as relational algebra, i.e. it is
relationally complete
 It is a formal language based upon a branch of mathematical logic called
"predicate calculus
 There are two approaches: tuple relational calculus and domain relational
calculus
 Calculus has variables, constants, comparison ops, logical, connectives,
and quantifiers.
 Expressions in the calculus are called formulas. An answer tuple is
essentially an assignment of constants to variables that make the formula
evaluate to true

Tuple Relational Calculus (TRC)

 A TRC is a nonprocedural query language,(without giving any specific

procedure)
 where each query is of the form {t | P (t) }
 Results: the set of all tuples t such that predicate P is true for t
 t is a tuple variable, t [A] denotes the value of tuple t on attribute A, t ∈ r
denotes that tuple t is in relation r
 P is a formula similar to that of the predicate calculus
Tuple calculus
Variables in expressions represent a row of a relation(tuple variable)
Example: {c.last_name, c.first_name | c Î Costumer}

Domain calculus
Variables represent domain values of attributes of a relation of the DB (domain
variables)
Example: {[l,f] | $m,a,t( [m,l,f,a,t] Î Customer )}

TRC classifications:

1. Predicate Calculus Formula

2. Example Queries
3. Safety of expressions
1. Predicate Calculus Formula

Set of attributes and constants.

Set of comparison operators: (e.g., , , , , , )

Set of connectives: and (), or (v)‚ not ()

Implication (): x  y, if x if true, then y is true

xyx v y

Set of quantifiers:

 t  r (Q (t ))”there exists” a tuple in t in relation r such that predicate Q (t )

is true

tr (Q (t )) Q is true “for all” tuples t in relation r

Banking Example

 branch (branch_name, branch_city, assets )

 customer (customer_name, customer_street, customer_city)
 account (account_number, branch_name, balance )
 loan (loan_number, branch_name, amount )
 depositor (customer_name, account_number)
 borrower(customer_name, loan_number)

2.Example Queries

 Find the loan_number, branch_name, and amount for loans of over $1200
{t | tloant [amount ]  1200}

 Find the loan number for each loan of an amount greater than $1200
{t| s loan (t [loan_number] = s [loan_number] s [amount ]  1200)}

Notice that a relation on schema [loan_number] is implicitly defined

bythe query

 Find the names of all customers having a loan, an account, or both at the
bank
{t|s borrower ( t [customer_name] = s [customer_name])
udepositor ( t [customer_name] = u [customer_name])
 Find the names of all customers who have a loan and an accountat the
bank
{t|s borrower ( t [customer_name] = s [customer_name])
u depositor ( t [customer_name] = u [customer_name] )
3. Safety of Expressions
 It is possible to write tuple calculus expressions that generate infinite
relations.
 For example, { t | tr } results in an infinite relation if the domain of any
attribute of relation r is infinite
 To guard against the problem, we restrict the set of allowable expressions
to safe expressions.
 An expression {t | P (t )}in the tuple relational calculus is safe if every
component of t appears in one of the relations, tuples, or constants that
appear in P
NOTE: this is more than just a syntax condition.
E.g. { t | t [A] = 5 true } is not safe --- it defines an infinite
set with attribute values that do not appear in any relation or tuples or
constants in P.
Domain Relational Calculus(DRC)

 A nonprocedural query language equivalent in power to the tuple

relational calculus
DRC classifications:

1. Formal Definition
2. Example Queries
3. Safety of expressions
1.Formal Definition

Each query is an expression of the form:

{ x1, x2, …, xn | P (x1, x2, …, xn)}

x1, x2, …, xn represent domain variables

P represents a formula similar to that of the predicate calculus

2.Example Queries

 Find the loan_number, branch_name, and amount for loans of over

$1200
{l, b, a  | l, b, a loana > 1200}

 Find the names of all customers who have a loan of over $1200
{c | l, b, a (c, l borrower l, b, a loana> 1200)}

 Find the names of all customers who have a loan from the Perryridge
branch and the loan amount:
{c, a | l (c, lborrower b (l, b, a loan
 b = “Perryridge”))}

{c, a | l (c, lborrower l, “ Perryridge”, a loan)}

Find the names of all customers having a loan, an account, or both at

the Perryridge branch:

{c | l ( c, lborrower

b,a(l, b, a loanb = “Perryridge”))
a (c, adepositor
b,n(a, b, naccountb = “Perryridge”))}

3.Safety of Expressions

The expression:

{ x1, x2, …, xn | P (x1, x2, …, xn)}

is safe if all of the following hold:

1. All values that appear in tuples of the expression are values from dom(P )
(that is, the values appear either in P or in a tuple of a relation
mentioned in P ).
2. For every “there exists” subformula of the form x (P1(x )), the
subformula is true if and only if there is a value of x in dom(P1) such
that P1(x ) is true.
3. For every “for all” subformula of the form x (P1 (x )), the subformula is
true if and only if P1(x ) is true for all values x from dom(P1).