Relational Database

Relational Model
• Tables, Columns and Rows
• Relationships and Keys
• Data Integrity
• Normalization
 Relational Model
• Salient features of a relational table
• Values are atomic. A special null value is used to represent
values that are unknown or inapplicable to certain tuples.
• Column values are of the same kind (Domain)
• Each Row is unique
• Sequence of columns is insignificant
• Sequence of rows is insignificant
• Each column must have a unique name
• Relationships and Keys
• Keys - Fundamental to the concept of relational databases
• Relationship - An association between two or more tables
defined by means of keys
 CHARACTERISTICS OF RELATIONS

• Notation:
– We refer to component values of a tuple t by
t[Ai] = vi (the value of attribute Ai for tuple t).
– Similarly, t[Au, Av, ..., Aw] refers to the subtuple
of t containing the values of attributes Au,
Av, ..., Aw, respectively.
 Relational Integrity Constraints

• Constraints are conditions that must hold on all valid

relation instances. There are three main types of
constraints:

1. Key constraints
2. Entity integrity constraints
3. Referential integrity constraints
 Keys
• Let K  R
• K is a superkey of R if values for K are sufficient to identify a unique tuple
of each possible relation r(R)
– by “possible r ” we mean a relation r that could exist in the enterprise
we are modeling.
– Example: {customer_name, customer_street} and
{customer_name}
are both superkeys of Customer, if no two customers can possibly
have the same name
• In real life, an attribute such as customer_id would be used
instead of customer_name to uniquely identify customers, but we
omit it to keep our examples small, and instead assume customer
names are unique.
 Keys (Cont.)
• K is a candidate key if K is minimal
Example: {customer_name} is a candidate key for Customer, since
it is a superkey and no subset of it is a superkey.
• Primary key: a candidate key chosen as the principal means of
identifying tuples within a relation
– Should choose an attribute whose value never, or very rarely,
changes.
– E.g. email address is unique, but may change
Key Constraints
 Entity Integrity
• Relational Database Schema: A set S of relation schemas
that belong to the same database. S is the name of the
database.
S = {R1, R2, ..., Rn}
• Entity Integrity: The primary key attributes PK of each relation
schema R in S cannot have null values in any tuple of r(R). This
is because primary key values are used to identify the
individual tuples.
t[PK]  null for any tuple t in r(R)

•  Note: Other attributes of R may be similarly constrained to disallow null

values, even though they are not members of the primary key.
 Referential Integrity

• A constraint involving two relations.

• Used to specify a relationship among tuples in two relations: the

referencing relation and the referenced relation.

• Tuples in the referencing relation R1 have attributes FK (called

foreign key attributes) that reference the primary key attributes
PK of the referenced relation R2. A tuple t1 in R1 is said to
reference a tuple t2 in R2 if t1[FK] = t2[PK].

• A referential integrity constraint can be displayed in a relational

database schema as a directed arc from R 1.FK to R2.PK
 Referential Integrity Constraint
Statement of the constraint

The value in the foreign key column (or columns) FK of the

the referencing relation R1 can be either:
(1) a value of an existing primary key value of the
corresponding primary key PK in the referenced
relation R2,, or..
(2) a null.

In case (2), the FK in R1 should not be a part of its own

primary key.
 Foreign Keys
• A relation schema may have an attribute that corresponds to the primary key
of another relation. The attribute is called a foreign key.
– E.g. customer_name and account_number attributes of depositor are
foreign keys to customer and account respectively.
– Only values occurring in the primary key attribute of the referenced
relation may occur in the foreign key attribute of the referencing relation.
• Schema diagram
 Relational Model
• Data Manipulation
• Relational tables are equivalent to sets
• Operations that can be performed on sets can be performed
on relational tables
• Relational Operations such as :
• Selection
• Projection
• Join
INTERSECTION
• Union
• Intersection UNION

• Difference
• Product
• Division

DIFFERENCE
 Query Languages
• Language in which user requests information from the database.
• Categories of languages
– Procedural
– Non-procedural, or declarative
• “Pure” languages:
– Relational algebra
– Tuple relational calculus
– Domain relational calculus
• Pure languages form underlying basis of query languages that
people use.
 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 a 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.

• 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

• Procedural language
• Six basic operators
– select: 
– project: 
– union: 
– set difference: –
– Cartesian product: x
– rename: 
• The operators take one or two relations as inputs and produce
a new relation as a result. Hence, it is closed.
 Select Operation – Example
• Selection
• SELECT operation is used to select a subset of the tuples from a
relation that satisfy a selection condition. It is a filter that keeps only
those tuples that satisfy a qualifying condition – those satisfying the
condition are selected while others are discarded.

A B C D E
1 A 212 Y 2
2 C 45 N 84
3 B 8656 N 4
4 D 324 N 56
5 C 5656 Y 34
6 A 445 N 4
7 B 546 Y 55

Select
Relation r
Operation – Example
A B C D

  1 7
  5 7
  12 3
  23 10

A=B ^ D > 5 (r)

A B C D

  1 7
  23 10
 Select Operation
• Notation:  p(r)
• p is called the selection predicate
• Defined as:

p(r) = {t | t  r and p(t)}

Where p is a formula in propositional calculus consisting of

terms connected by :  (and),  (or),  (not)
Each term is one of:
<attribute> op <attribute> or <constant>
where op is one of: =, , >, . <. 

• Example of selection:

 branch_name=“Perryridge”(account)
 Select Operation

Example: To select the EMPLOYEE tuples whose department number is four

or those whose salary is greater than $30,000 the following notation is
used:
DNO = 4 (EMPLOYEE)
SALARY > 30,000 (EMPLOYEE)

In general, the select operation is denoted by <selection condition>(R) where the

symbol  (sigma) is used to denote the select operator, and the selection
condition is a Boolean expression specified on the attributes of relation R
 Unary Relational Operations
SELECT Operation Properties
– The SELECT operation <selection condition>(R) produces a relation S
that has the same schema as R

– The SELECT operation is commutative; i.e.,

 <condition1>(< condition2> ( R)) = <condition2> (< condition1> ( R))

– A cascaded SELECT operation may be applied in any order; i.e.,

 <condition1>(< condition2> (<condition3> ( R))
 = <condition2> (< condition3> (< condition1> ( R)))

– A cascaded SELECT operation may be replaced by a single

selection with a conjunction of all the conditions; i.e.,
 <condition1>(< condition2> (<condition3> ( R))
 = <condition1> AND < condition2> AND < condition3> ( R)))
Unary Relational Operations (cont.)
 Relational Model
PROJECT Operation
This operation selects certain columns from the table and
discards the other columns. The PROJECT creates a vertical
partitioning – one with the needed columns (attributes) containing
results of the operation and other containing the discarded Columns.

A B C D E
1 A 212 Y 2
2 C 45 N 84
3 B 8656 N 4
4 D 324 N 56
5 C 5656 Y 34
6 A 445 N 4
7 B 546 Y 55
 Project Operation
• Example: To eliminate the branch_name attribute of account
account_number, balance (account)
• Example: To list each employee’s first and last name and salary, the
following is used: lname, fname, salary (employee)
• The general form of the project operation is <attribute list>(R) where 
(pi) is the symbol used to represent the project operation and <attribute
list> is the desired list of attributes from the attributes of relation R.

• Notation:  A1,A2 ,,Ak ( r ) where A1, A2 are attribute names and r

is a relation name.
• The result is defined as the relation of k columns obtained by
erasing the columns that are not listed
• The project operation removes any duplicate tuples, so the result of the
project operation is a set of tuples and hence a valid relation.
 Project Operation – Example
• Relation r: A B C

 10 1
 20 1
 30 1
 40 2

A,C (r) A C A C

 1  1
 1 =  1
 1  2
 2
Relational Algebra
Unary Relational Operations (cont.)
 Unary Relational Operations (cont.)

PROJECT Operation Properties

–
The number of tuples in the result of projection 
<list> Ris
always less or equal to the number of tuples in R.

– If the list of attributes includes a key of R, then the number of

tuples is equal to the number of tuples in R.

–
 <list2> R)<list1> Ras long
<list1>
as<list2>contains theattributes in<list2>
 Rename Operation
• Rename Operation
We may want 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.
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 as follows:

 FNAME, LNAME, SALARY ( DNO=5(EMPLOYEE))

OR We can explicitly show the sequence of operations, giving a name to each
intermediate relation:
DEP5_EMPS   DNO=5(EMPLOYEE)
RESULT   FNAME, LNAME, SALARY (DEP5_EMPS)
 Unary Relational Operations (cont.)
• Rename Operation (cont.)
The rename operator is 

The general Rename operation can be expressed by any of the

following forms:

 S (B1, B2, …, Bn ) ( R) is a renamed relationS based on R with column names B1, B1, …..Bn

 S ( R) is a renamed relationS based on R (which does not specify column names).

 (B1, B2, …, Bn ) ( R) is a renamed relationwith column names B1, B1, …..Bn which does

not specify a new relation name.

Unary Relational Operations (cont.)
 Relational Algebra Operations From
Set Theory

• 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.

– The resulting relation for R1R2,R1R2, or R1-R2 has

the same attribute names as the first operand relation
R1 (by convention).
 Union Operation
• UNION Operation
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.
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, we can use the union operation as follows:
DEP5_EMPS  DNO=5 (EMPLOYEE)
RESULT1   SSN(DEP5_EMPS)
RESULT2(SSN)   SUPERSSN(DEP5_EMPS)
RESULT  RESULT1  RESULT2
The union operation produces the tuples that are in either RESULT1 or
RESULT2 or both. The two operands must be “type compatible”.
 Union Operation – Example
• Relations r, s:
A B
A B
 1
A B  2  2

 1  3
 r  s:  1
r s
 2
 1
 3

Example: to find all customers with either an account or a loan

customer_name (depositor)  customer_name (borrower)

 Union Operation – Example
• UNION Example

STUDENTINSTRUCTOR
 Intersection Operation
• 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"

Defined as r  s = { t | t  r and t  s }
• Assume:
– r, s have the same attribute
– attributes of r and s are compatible
• Note: r  s = r – (r – s)
 Intersection Operation – Example
• INTERSECTION Example

STUDENT INSTRUCTOR
 • Relation r, s:
A B A B
 1  2
 2  3
 1

r s

• rs A B

 2

Intersection Operation – Example

 Set Difference 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”.

• Notation r – s
• Defined as:
r – s = {t | t  r and t  s}
• Set differences must be taken between compatible relations.
– r and s must have the same arity
– attribute domains of r and s must be compatible
 Set
• Relations r, s:
Difference – Example
A B A B

 1  2
 2  3
 1 s
r

 r – s:
A B

 1
 1
Set Difference – Example

STUDENT-INSTRUCTOR

INSTRUCTOR-STUDENT
 Cartesian Operation
• CARTESIAN (or cross product) Operation
– This operation is used to combine tuples from two relations in a
combinatorial fashion. 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. 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 x S | will have nR * nS tuples.
– The two operands do NOT have to be "type compatible”
– Assume that attributes of r(R) and s(S) are disjoint. (That is, R  S =
).
– If attributes of r(R) and s(S) are not disjoint, then renaming must be
used.
 Cartesian-Product – Example
 Relations r, s:
A B C D E

 1  10 a
 10 a
 2  20 b
r  10 b
s
 r x s:
A B C D E
 1  10 a
 1  10 a
 1  20 b
 1  10 b
 2  10 a
 2  10 a
 2  20 b
 2  10 b
Example:
FEMALE_EMPS   SEX=’F’(EMPLOYEE)
EMPNAMES   FNAME, LNAME, SSN (FEMALE_EMPS)

EMP_DEPENDENTS  EMPNAMES x DEPENDENT

 Binary Relational Operations
• 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. It is denoted by a

– This operation is very important for any relational database

with more than a single relation, because it allows us to
process relationships among relations.

– The general form of a join operation on two relations R(A1, A2,

. . ., An) and S(B1, B2, . . ., Bm) is:
R <join condition>S
where R and S can be any relations that result from general
relational algebra expressions.
 JOIN Operation (cont.)
Example: Suppose that we want to retrieve the name of the
manager of each department. To get the manager’s name,
we need to combine each DEPARTMENT tuple with the
EMPLOYEE tuple whose SSN value matches the MGRSSN
value in the department tuple. We do this by using the join
operation.
DEPT_MGR  DEPARTMENT MGRSSN=SSN EMPLOYEE
 JOIN Operation (cont.)
• EQUIJOIN Operation (or Theta join) theta

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 (whose names need not be identical) that have
identical values in every tuple.
The JOIN seen in the previous example was EQUIJOIN.

• 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 is applied first.
 JOIN Operation (cont.)
Example: To apply a natural join on the DNUMBER attributes of
DEPARTMENT and DEPT_LOCATIONS, it is sufficient to write:
DEPT_LOCS  DEPARTMENT DEPT_LOCATIONS
 Natural-Join Operation
 Notation: r s
• Let r and s be relations on schemas R and S respectively.
Then, r s is a relation on schema R  S obtained as follows:
– Consider each pair of tuples tr from r and ts from s.
– If tr and ts have the same value on each of the attributes in R  S, add a
tuple t from the relation R X S to the result, where
• t has the same value as tr on r
• t has the same value as ts on s
• Example:
R = (A, B, C, D)
S = (E, B, D)
– Result schema = (A, B, C, D, E)
– r s is defined as:
r.A, r.B, r.C, r.D, s.E (r.B = s.B  r.D = s.D (r x s))
 Natural Join – Example
• Relations r, s:

A B C D B D E

 1  a 1 a 
 2  a 3 a 
 4  b 1 a 
 1  a 2 b 
 2  b 3 b 
r s

 r s
A B C D E
 1  a 
 1  a 
 1  a 
 1  a 
 2  b 
 Additional Relational Operations
• The OUTER JOIN Operation
– In NATURAL JOIN tuples without a matching (or related) tuple are
eliminated from the join result. Tuples with null in the join attributes are
also eliminated. This amounts to loss of information.
– A set of operations, called outer joins, can be used when we want 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.
– 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, keeps every tuple in the second or
right relation S in the result 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.
 OUTER JOIN (cont.)
• The outer union operation was developed to take the union of tuples from
two relations if the relations are not union 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.
• 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).
• Example: An outer union to two schemas STUDENT(Name, SSN,
Department, Advisor) and 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. If a
student is also an instructor, both Advisor and Rank will have a value;
otherwise, one of these two attributes will be null.
STUDENT_OR_INSTRUCTOR (Name, SSN, Department, Advisor,
Rank)
 Outer Join – Example
• Relation loan

loan_number branch_name amount

L-170 Downtown 3000
L-230 Redwood 4000
L-260 Perryridge 1700

 Relation borrower

customer_name loan_number
Jones L-170
Smith L-230
Hayes L-155
 Outer Join – Example
• Join

loan borrower

loan_number branch_name amount customer_name

L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
 Left Outer Join

loan borrower
loan_number branch_name amount customer_name
L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-260 Perryridge 1700 null
 Outer Join – Example
 Right Outer Join

loan borrower

loan_number branch_name amount customer_name

L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-155 null null Hayes
 Full Outer Join

loan borrower
loan_number branch_name amount customer_name
L-170 Downtown 3000 Jones
L-230 Redwood 4000 Smith
L-260 Perryridge 1700 null
L-155 null null Hayes
 Null Values
• It is possible for tuples to have a null value, denoted by null, for
some of their attributes
• null signifies an unknown value or that a value does not exist.
• The result of any arithmetic expression involving null is null.
• Aggregate functions simply ignore null values (as in SQL)
• For duplicate elimination and grouping, null is treated like any
other value, and two nulls are assumed to be the same (as in
SQL)
 Null Values
• Comparisons with null values return the special truth value: unknown
– If false was used instead of unknown, then not (A < 5)
would not be equivalent to A >= 5
• Three-valued logic using the truth value unknown:
– OR: (unknown or true) = true,
(unknown or false) = unknown
(unknown or unknown) = unknown
– AND: (true and unknown) = unknown,
(false and unknown) = false,
(unknown and unknown) = unknown
– NOT: (not unknown) = unknown
– In SQL “P is unknown” evaluates to true if predicate P evaluates to
unknown
• Result of select predicate is treated as false if it evaluates to unknown
 Division Operation
• Notation: r  s
• Suited to queries that include the phrase “for all”.
• Let r and s be relations on schemas R and S
respectively where
– R = (A1, …, Am , B1, …, Bn )
– S = (B1, …, Bn)
The result of r  s is a relation on schema
R – S = (A1, …, Am)
r  s = { t | t   R-S (r)   u  s ( tu  r ) }
Where tu means the concatenation of tuples t and u to
produce a single tuple
 Division Operation – Example
 Relations r, s:
A B B
 1
1
 2
 3 2
 1 s
 1
 1
 3
 4
 6
 1
 2
 r  s: A r



 Another Division Example
 Relations r, s:
A B C D E D E

 a  a 1 a 1
 a  a 1 b 1
 a  b 1 s
 a  a 1
 a  b 3
 a  a 1
 a  b 1
 a  b 1
r
 r  s:
A B C

 a 
 a 
 Division Operation (Cont.)
• Property
– Let q = r  s
– Then q is the largest relation satisfying q x s  r
• Definition in terms of the basic algebra operation
Let r(R) and s(S) be relations, and let S  R

r  s = R-S (r ) – R-S ( ( R-S (r ) x s ) – R-S,S(r ))

To see why
 R-S,S (r) simply reorders attributes of r

 R-S (R-S (r ) x s ) – R-S,S(r) ) gives those tuples t in

R-S (r ) such that for some tuple u  s, tu  r.

 Assignment Operation
• The assignment operation () provides a convenient way to express 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.
– Assignment must always be made to a temporary relation variable.
• Example: Write r  s as
temp1  R-S (r )
temp2  R-S ((temp1 x s ) – R-S,S (r ))
result = temp1 – temp2
– The result to the right of the  is assigned to the relation variable on the left of the
.
– May use variable in subsequent expressions.
 Composition of Operations
• Can build expressions using multiple operations
• Example: A=C
A (r Bx s)C D E
• rxs  1  10 a
 1  10 a
 1  20 b
 1  10 b
 2  10 a
 2  10 a
 2  20 b
 2  10 b

 A=C(r x s) A B C D E

 1  10 a
 2  10 a
 2  20 b
 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)

• Find all loans of over $1200.
• Find the loan number for each loan of an amount greater than $1200.
• Find the names of all customers who have a loan, an account, or both, from the
bank.
• Find the names of all customers who have a loan at the Perryridge branch.
• Find the names of all customers who have a loan at the Perryridge branch but do not
have an account at any branch of the bank.
• Find the names of all customers who have a loan at the Perryridge branch.
• Find the largest account balance.
Modification of the Database
• The content of the database may be modified using the
following operations:
– Deletion
– Insertion
– Updating
• All these operations are expressed using the assignment
operator.
 Deletion
• A delete request is expressed similarly to a query, except
instead of displaying tuples to the user, the selected
tuples are removed from the database.
• Can delete only whole tuples; cannot delete values on
only particular attributes
• A deletion is expressed in relational algebra by:
rr–E
where r is a relation and E is a relational algebra query.
 Deletion Examples
• Delete all account records in the Perryridge branch.
account  account – branch_name = “Perryridge” (account )

 Delete all loan records with amount in the range of 0 to 50

loan  loan – amount 0and amount  50 (loan)

 Delete all accounts at branches located in Needham.

r1  branch_city = “Needham” (account branch )

r2   account_number, branch_name, balance (r1)
r3   customer_name, account_number (r2 depositor)
account  account – r2
depositor  depositor – r3
 Insertion
• To insert data into a relation, we either:
– specify a tuple to be inserted
– write a query whose result is a set of tuples to be inserted
• in relational algebra, an insertion is expressed by:
r r  E
where r is a relation and E is a relational algebra expression.
• The insertion of a single tuple is expressed by letting E be a
constant relation containing one tuple.
 Insertion Examples
• Insert information in the database specifying that Smith has $1200 in account
A-973 at the Perryridge branch.

account  account  {(“A-973”, “Perryridge”, 1200)}

depositor  depositor  {(“Smith”, “A-973”)}

 Provide as a gift for all loan customers in the Perryridge

branch, a $200 savings account. Let the loan number serve
as the account number for the new savings account.
r1  (branch_name = “Perryridge” (borrower loan))
account  account  loan_number, branch_name, 200 (r1)
depositor  depositor  customer_name, loan_number (r1)
 Updating
• A mechanism to change a value in a tuple without charging all
values in the tuple
• Use the generalized projection operator to do this task
r   F ,F ,,F , (r )
1 2 l

• Each Fi is either
– the I th attribute of r, if the I th attribute is not updated, or,
– if the attribute is to be updated Fi is an expression, involving
only constants and the attributes of r, which gives the new
value for the attribute
 Update Examples
• Make interest payments by increasing all balances by 5 percent.

account   account_number, branch_name, balance * 1.05 (account)

 Pay all accounts with balances over $10000, 6 percent interest

and pay all others 5 percent

account   account_number, branch_name, balance * 1.06 ( BAL  10000 (account ))

  account_number, branch_name, balance * 1.05 (BAL  10000 (account))