RELATIONAL DATA MODEL

RELATIONAL MODEL CONCEPTS

The relational model represents the database as a collection of relations. Informally, each relation resembles
a table of values or, to some extent, a flat file of records. It is called a flat file because each record has a simple
linear or flat structure. When a relation is thought of as a table of values, each row in the table represents a
collection of related data values.
In the formal relational model terminology, a row is called a tuple, a column header is called an attribute,
and the table is called a relation. The data type describing the types of values that can appear in each column
is represented by a domain of possible values.
Domain, Attributes, Tuples and Relation
Domain: A common method of specifying a domain is to specify a data type from which the data values
forming the domain are drawn. Some examples of domains are as follow:
• Ind_phone_numbers. The set of eight-digit phone numbers valid in India.
• Adh_number: The set of valid twelve-digit unique identification number of a person.
• Names: The set of character strings that represent names of persons.
• Grade_point_averages. Possible values of computed grade point averages; each must be a real
(floating-point) number between 0 and 10.
• Employee_ages. Possible ages of employees in a company; each must be an integer value between 15
and 60.
• Academic_department_names. The set of academic department names in a university, such as
Computer Science, Economics, and Physics.
A relation schema R, denoted by R(A1, A2, … , An), is made up of a relation name R and a list of attributes,
A1, A2, … , An. Each attribute Ai is the name of a role played by some domain D in the relation schema R.
D is called the domain of Ai and is denoted by dom(Ai). R is called the name of this relation. The degree (or
arity) of a relation is the number of attributes n of its relation schema.
A relation of degree seven, which stores information about university students, would contain seven attributes
describing each student as follows:
STUDENT(Name, Ssn, Home_phone, Address, Office_phone, Age, Gpa)
Using the data type of each attribute, the definition is sometimes written as:
STUDENT(Name: string, Ssn: string, Home_phone: string, Address: string, Office_phone: string,
Age: integer, Gpa: real)
For this relation schema, STUDENT is the name of the relation, which has seven attributes. In the preceding
definition, we showed assignment of generic types such as string or integer to the attributes.
Relation State: A relation state is the current set of tuples (rows) in a relation (table) at a specific time.
Example: Consider the following relation schema
STUDENT(SID, Name, Age, Major)
 This defines:
• SID: Student ID
• Name: Student Name
• Age: Student Age
• Major: Student's field of study
In this example with give two possible relation states
Relation State 1 (Initial State)
SID Name Age Major
S01 Riya 20 Computer Sci
S02 Arjun 22 Physics
Relation State 2 (After Insert)
SID Name Age Major
S01 Riya 20 Computer Sci
S02 Arjun 22 Physics
S03 Neha 21 Math
The value can also be NULL.
Figure below shows an example of a STUDENT relation, which corresponds to the STUDENT schema just
specified. Each tuple in the relation represents a particular student entity (or object). We display the relation
as a table, where each tuple is shown as a row and each attribute corresponds to a column header indicating a
role or interpretation of the values in that column. NULL values represent attributes whose values are unknown
or do not exist for some individual STUDENT tuple.
Definition of relation using set theory concept:

Example:

RollNo Grade
1 A
2 B
3 A

Properties of Relation (DBMS, Set Theory View)

A relation in DBMS (i.e., a table) obeys certain rules because it is defined as a set of tuples.
1. Uniqueness of Tuples

• In set theory, a set cannot contain duplicate elements.

• Similarly, in a relation, no two tuples (rows) are identical.

Example: You cannot have two identical rows in a student table.

2. Ordering is Irrelevant

• In set theory, the order of elements in a set does not matter.

• In a relation, the order of rows (tuples) does not matter.
 • Likewise, the order of attributes (columns) does not matter, as long as their names are fixed.

Example:

RollNo Name Age

1 Raj 20

2 Anu 21

is the same relation as:

Name Age RollNo

Raj 20 1

Anu 21 2

3. Atomicity of Attributes (First Normal Form)

• Each attribute (column) must have atomic values (indivisible, single value from its domain).
• No sets, lists, or composite values are allowed in a single cell.

Example: A student’s "Phone" attribute should not contain {"12345", "67890"} together; instead, store them
in separate rows or another table.

4. Each Attribute has a Domain

• Each attribute is drawn from a specific domain (set of valid values).

• For example:
o RollNo → integers
o Name → strings
o Age → positive integers

Values outside the domain are not allowed.

5. Relation is a Subset of Cartesian Product

Values of NULLs in Tuples: NULL values are used to represent the values of attributes that may be unknown
or may not apply to a tuple.
In the relation of STUDENT, some STUDENT tuples have NULL for their office phones because they do not
have an office (that is, office phone does not apply to these students). Another student has a NULL for home
phone, presumably because either he does not have a home phone or he has one but we do not know it

Interpretation of a Relation: There are two ways of interpreting a relation. Assertion and Predicate.
Assertion: In assertion interpretation, a relation is viewed as a set of facts — that is, every tuple in the
relation is taken as a true statement (or fact) about the real world. Rather than thinking of the relation as a
test (predicate) that returns true or false, we assert that each tuple is true — and any other tuple (not in the
relation) is not asserted (could be treated as unknown).
Example: Consider the relation with the following tuples
STUDENT(SID, Name, Age)
SID Name Age

Riya 20
S01
S02 Aman 21

• S01 is a student named Riya who is 20 years old. → true

• S02 is a student named Aman who is 21 years old. → true
And we assert only what is listed.
• Nothing is said about S03, or whether Riya is also 21. Those facts are simply not asserted.
• So, if (S03, Riya, 21) is not in the relation, it’s just not claimed — we’re silent about it.
Predicate: In predicate interpretation, a relation is seen as a logical predicate — a Boolean-valued function
that returns true for only those tuples that exist in the relation. For remaining, it returns false.
For the above example
• STUDENT('S101', 'Riya', 20) → ✅ true

• STUDENT('S102', 'Arjun', 21) → ✅ true

• STUDENT('S103', 'Riya', 20) → ❌ false (if not in the relation)
RELATIONAL MODEL NOTATION
We will use the following notation in our presentation:
• A relation schema R of degree n is denoted by R(A1, A2, … , An)
• The uppercase letters Q, R, S denote relation names.
• The lowercase letters q, r, s denote relation states.
• The letters t, u, v denote tuples.
• An attribute A can be qualified with the relation name R to which it belongs by using the dot notation
R.A—for example, [Link] or [Link]. This is because the same name may be used
for two attributes in different relations. However, all attribute names in a particular relation must be
distinct.

RELATIONAL MODEL CONSTRAINTS AND RELATIONAL DATABASE

SCHEMAS
There are generally many restrictions or constraints on the actual values in a database state. Constraints on
databases can generally be divided into three main categories:
1. Constraints that are inherent in the data model. We call these inherent model-based constraints or
implicit constraints.
▪ Unique Row Constraint: No two tuples in a relation can be identical.
▪ Atomicity of attributes: Each attribute must be atomic, not a set or a list
▪ In a relation model, order of columns and rows does not matter.
▪ All attribute names must be unique.
2. Constraints that can be directly expressed in the schemas of the data model, typically by specifying them
in the DDL (data definition language). We call these schema-based constraints or explicit constraints.
▪ Primary Key Constraint: No two rows can have the same primary key value. A primary key
column cannot contain NULL values. Each table can have only one primary key.
 ▪ Foreign Key constraint: A foreign key is a column (or set of columns) in one table that refers to
the primary key in another table. We cannot insert a value in the foreign key column if it does
not exist in the referenced primary key column which is known as Referential Integrity.
▪ Unique constraint: Ensures that no two rows have the same value in the specified column
▪ Not NULL constraint
▪ Check constraint: Allows defining a condition that column values must specify.
▪ Default constraint: Sets a default value if none is provided during insertion.
3. Constraints that cannot be directly expressed in the schemas of the data model, and hence must be
expressed and enforced by the application programs or in some other way. We call these application-
based or semantic constraints or business rules. They are rules about the meaning or logic of data.
• A student cannot enroll in more than 5 courses in a semester.
• An employer’s salary must be higher than that of its subordinates.
• A professor cannot teach more than 2 courses per term.
• A bank account balance cannot go below Rs 500 after withdrawal.
• Age of an applicant must be greater than 18 for a driver’s licence.
DOMAIN CONSTRAINTS
Domain constraints specify that within each tuple, the value of each attribute A must be an atomic value from
the domain dom(A). It cannot be a list or a set
Example: STUDENT
Name Courses Correct/not
Riya Math Correct
Arjun {Math,Science} Not correct
The data types associated with domains include:
• Standard numeric data types for integers (such as short integer, integer, and long integer)
• Real numbers (float and double-precision float).
• Characters
• Booleans
• fixed-length strings, and variable-length strings
• date, time, timestamp
KEY CONSTRAINTS AND CONSTRAINTS ON NULL VALUES
• In the formal relational model, a relation is defined as a set of tuples. By definition, all elements of a
set are distinct; hence, 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.
• Suppose that we denote a 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[SK] ≠ t2[SK]
• Any such set of attributes SK is called a superkey of the relation schema R. 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.
Example: Consider an EMPLOYEE relation as shown below

EmpID Name Dept Email AadharNo

E001 Rahul HR rahul@[Link] 1234-5678-9012

E002 Priya Finance priya@[Link] 2345-6789-0123

E003 Amit IT amit@[Link] 3456-7890-1234

Here the Candidate Keys are (uniquely identifies a tuple)

{EmpID}, {AadharNo}, {Email} – All these are not repeated in any tuples/rows.
Superkeys can be obtained by combining Primary Keys with other attributed. Some of the valid super
keys here are:

{EmpID}, {Email}, {AadharNo}, {EmpID, Name}, {EmpID, Dept}, {Email, Name}, {AadharNo,
Email, Dept}, {EmpID, AadharNo, Email, Name, Dept}

The following are not super keys:

{Name}, {Dept}, {Name, Dept} as they are not unique.

Primary Key: There can be any number of candidate keys in a relation. The chosen candidate key is
called as a Primary Key. The primary key is underlined in the table. That is the method of recognizing
it. In the above example

{EmpID} or {AadharNo} or {Email} can be the Primary key (any one not all).

Example: Consider the CAR relation shown below:

Here the Candidate Keys are {License_number} and {Engine_serial_number}.

License_number is chosen as the Primary Key and is underlined in the table.

 • Another constraint on attributes specifies whether NULL values are or are not permitted. For example,
if every STUDENT tuple must have a valid, non-NULL value for the Name attribute, then Name of
STUDENT is constrained to be NOT NULL.

RELATIONAL DATABASES AND RELATIONAL DATABASE SCHEMAS

Relational Database Schema: A relational database schema S is a set of relation schemas

S = {R1, R2, … , Rm} and a set of integrity constraints IC.

Relational Database State: A relational database state DB of S is a set of relation states

DB = {r1, r2, … , rm} such that each ri is a state of Ri and such that the ri relation states satisfy the integrity
constraints specified in IC.

Example: Figure below shows a relational database schema that can be called

COMPANY = {EMPLOYEE, DEPARTMENT, DEPT_LOCATIONS, PROJECT, WORKS_ON,

DEPENDENT}

In each relation schema, the underlined attribute represents the primary key.

In Figure above, 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. Attributes that represent the same real-world concept may or may not have identical
names in different relations. 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
Figure below shows a relational database state corresponding to the COMPANY schema.
A database state that does not obey all the integrity constraints is called not valid, and a state that satisfies all
the constraints in the defined set of integrity constraints IC is called a valid state.
Each relational DBMS must have a data definition language (DDL) for defining a relational database schema.
Current relational DBMSs are mostly using SQL for this purpose.
ENTITY 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.
Referential Integrity Constraint: Key constraints and entity integrity constraints are specified on individual
relations. 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.
Example: For example, in Figure above, 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.
Referential integrity constraints typically arise from the relationships among the entities represented by the
relation schemas.
Example: Consider the database shown in Figure above. In the EMPLOYEE relation,
✓ The attribute Dno refers to the department for which an employee works; hence, we designate Dno to
be a foreign key of EMPLOYEE referencing the DEPARTMENT relation. This means that a value of
Dno in any tuple t1 of the EMPLOYEE relation must match a value of the primary key of
DEPARTMENT—the Dnumber attribute—in some tuple t2 of the DEPARTMENT relation
✓ The value of Dno can be NULL if the employee does not belong to a department or will be assigned
to a department later.
✓ Notice that a foreign key can refer to its own relation. For example, the attribute Super_ssn in
EMPLOYEE refers to the supervisor of an employee; this is another employee, represented by a tuple
in the EMPLOYEE relation. Hence, Super_ssn is a foreign key that references the EMPLOYEE
relation itself. In Figure above the tuple for employee ‘John Smith’ references the tuple for employee
‘Franklin Wong,’ indicating that ‘Franklin Wong’ is the supervisor of ‘John Smith’.
✓ We can diagrammatically display referential integrity constraints by drawing a directed arc from each
foreign key to the relation it references. For clarity, the arrowhead may point to the primary key of the
referenced relation.
OTHER TYPES OF CONSTRAINTS
Another class of general constraints, sometimes called semantic integrity constraints, are not part of the DDL
and have to be specified and enforced in a different way.
Examples of such constraints are the salary of an employee should not exceed the salary of the employee’s
supervisor and the maximum number of hours an employee can work on all projects per week is 56.
The types of constraints we discussed so far may be called state constraints because they define the
constraints that a valid state of the database must satisfy. Another type of constraint, called transition
constraints, can be defined to deal with state changes in the database.
An example of a transition constraint is: “An order can only transition from pending to payment received then
to processing and finally to shipped” – It would prevent an order from skipping the payment received stage
and going straight to shipped.
UPDATE OPERATIONS, TRANSACTIONS AND DEALING WITH CONSTRAINT
VIOLATIONS
Here we concentrate on the database modification or update operations. There are three basic operations that
can change the states of relations in the data base: Insert, Delete, and Update (or Modify). They insert new
data, delete old data, or modify existing data records, respectively. Insert is used to insert one or more new
tuples in a relation, Delete is used to delete tuples, and Update (or Modify) is used to change the values of
some attributes in existing tuples. Whenever these operations are applied, the integrity constraints specified
on the relational database schema should not be violated.
These operations are analyzed with the example relation COMPANY shown below
INSERT OPERATION
The Insert operation provides a list of attribute values for a new tuple t that is to be inserted into a relation R.
Insert can violate any of the four types of constraints.
✓ Domain constraints can be violated if an attribute value is given that does not appear in the
corresponding domain or is not of the appropriate data type.
 ✓ Key constraints can be violated if a key value in the new tuple t already exists in another tuple in the
relation r(R).
✓ Entity integrity can be violated if any part of the primary key of the new tuple t is NULL.
✓ Referential integrity can be violated if the value of any foreign key in t refers to a tuple that does not
exist in the referenced relation.
Here are some examples to illustrate this discussion.

In operation 3, the DBMS could either ask the user to change the value of Dno to some valid value (or set it
to NULL), or it could ask the user to insert a DEPARTMENT tuple with Dnumber = 7 and could accept the
original insertion only after such an operation was accepted. Notice that in the latter case the insertion violation
can cascade back to the EMPLOYEE relation if the user attempts to insert a tuple for department 7 with a
value for Mgr_ssn that does not exist in the EMPLOYEE relation.
THE DELETE OPERATION
The Delete operation can violate only referential integrity. This occurs if the tuple being deleted is referenced
by foreign keys from other tuples in the database. Here are some examples.
Several options are available if a deletion operation causes a violation.
• The first option, called restrict, is to reject the deletion.
• The second option, called cascade, is to attempt to cascade (or propagate) the deletion by deleting
tuples that reference the tuple that is being deleted.
For example, in operation 2,
the DBMS could automatically delete the offending tuples from WORKS_ON with Essn =
‘999887777’.
• A third option, called set null or set default, is to modify the referencing attribute values that cause the
violation; each such value is either set to NULL or changed to reference another default valid tuple.
Notice that if a referencing attribute that causes a violation is part of the primary key, it cannot be set
to NULL; otherwise, it would violate entity integrity.
For example, to avoid having operation 3 cause a violation,
The DBMS may automatically delete all tuples from WORKS_ON and DEPENDENT with Essn =
‘333445555’. Tuples in EMPLOYEE with Super_ssn = ‘333445555’ and the tuple in DEPARTMENT
with Mgr_ssn = ‘333445555’ can have their Super_ssn and Mgr_ssn values changed to other valid
values or to NULL.
THE UPDATE OPERATION
The Update (or Modify) operation is used to change the values of one or more attributes in a tuple (or tuples)
of some relation R. It is necessary to specify a condition on the attributes of the relation to select the tuple (or
tuples) to be modified. Here are some examples.
Updating an attribute that is neither part of a primary key nor part of a foreign key usually causes no problems;
the DBMS need only check to confirm that the new value is of the correct data type and domain. Modifying
a primary key value is simi lar to deleting one tuple and inserting another in its place because we use the
primary key to identify tuples.
THE TRANSACTION CONCEPT
A transaction is an executing program that includes some database operations, such as reading from the
database, or applying insertions, deletions, or updates to the database. At the end of the transaction, it must
leave the database in a valid or consistent state that satisfies all the constraints specified on the database
schema. A single transaction may involve any number of retrieval operations.
EXERCISE
Suppose that each of the following Update operations is applied directly to the database state shown in Figure
below. Discuss all integrity constraints violated by each operation, if any, and the different ways of enforcing
these constraints.
Example 2
LIBRARY MANAGEMENT SYSTEM
Relational Schema
BOOK

BOOK(Book_ID, Title, Author, Publisher, Price, Category)

• PK: Book_ID

MEMBER

MEMBER(Member_ID, Name, Address, Phone, Join_Date)

• PK: Member_ID

LIBRARIAN

LIBRARIAN(Librarian_ID, Name, Phone, Salary)

• PK: Librarian_ID

ISSUE

ISSUE(Issue_ID, Book_ID, Member_ID, Librarian_ID, Issue_Date, Due_Date)

• PK: Issue_ID
• FKs:
o Book_ID → BOOK(Book_ID)
o Member_ID → MEMBER(Member_ID)
o Librarian_ID → LIBRARIAN(Librarian_ID)
RETURN

RETURN(Return_ID, Issue_ID, Return_Date, Fine)

• PK: Return_ID
• FK: Issue_ID → ISSUE(Issue_ID)

BOOK

Book_ID Title Author Publisher Price Category

B101 DBMS Concepts Korth McGrawHill 550 CS
B102 Algorithms Made Easy Cormen PHI 720 CS
B103 Digital Logic Morris Mano Wiley 450 ECE
B104 Computer Networks Tanenbaum Pearson 650 CS
B105 Signals & Systems Oppenheim McGrawHill 500 ECE
B106 Operating Systems Galvin Wiley 700 CS
MEMBER

Member_ID Name Address Phone Join_Date

M01 Rahul Delhi 9876543210 2022-03-10
M02 Priya Mumbai 9988776655 2023-01-12
M03 Kunal Pune 8877665544 2023-02-10
M04 Sneha Bangalore 7766554433 2023-03-15
M05 Aarav Hyderabad 9988001122 2023-05-01

LIBRARIAN

Librarian_ID Name Phone Salary

L01 Anita 8899001122 35000
L02 Karan 7788990011 37000
L03 Neha 6677889900 36000

ISSUE

Issue_ID Book_ID Member_ID Librarian_ID Issue_Date Due_Date

I01 B101 M01 L01 2023-04-01 2023-04-15
I02 B103 M02 L02 2023-05-05 2023-05-20
I03 B104 M03 L01 2023-06-10 2023-06-25
I04 B102 M04 L02 2023-06-15 2023-07-01
I05 B106 M01 L03 2023-07-01 2023-07-15

RETURN

Return_ID Issue_ID Return_Date Fine

R01 I01 2023-04-17 50
R02 I02 2023-05-19 0
R03 I04 2023-07-02 20
Operations
a) Insert <B104, "AI Basics", "Russell", "Pearson", 800, "CS"> into BOOK.
b) Insert <M03, "Kunal", "Pune", 8877665544, "2023-02-10"> into MEMBER.
c) Insert <I03, B105, M01, L01, "2023-06-10", "2023-06-25"> into ISSUE.
d) Insert <R02, I05, "2023-06-30", 0> into RETURN.
e) Delete the BOOK tuple with Book_ID = B103.
f) Delete the MEMBER tuple with Member_ID = M02.
g) Delete the LIBRARIAN tuple with Librarian_ID = L02.
h) Modify the Price of BOOK tuple with Book_ID = B101 to NULL.
i) Modify the Librarian_ID of ISSUE tuple with Issue_ID = I01 to L03.
j) Modify the Return_Date of RETURN tuple with Return_ID = R01 to 2023-04-10.
k) Insert <B101, "DBMS Concepts", "Korth", "McGrawHill", 550, "CS"> into BOOK again.
 THE RELATIONAL ALGEBRA

UNARY RELATIONAL OPERATORS: SELECT AND PROJECT

THE SELECT OPERATION:
The SELECT operation is used to choose a subset of the tuples from a relation that satisfies a selection
condition. We can consider the SELECT operation to be 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.
Consider the example relation COMPANY given below
For example, to select the EMPLOYEE tuples whose department is 4, or those whose salary is greater than
$30,000, we can individually specify each of these two conditions with a SELECT operation as follows:

In general, the SELECT operation is denoted by

where the symbol σ (sigma) is used to denote the SELECT operator and the selection condition is a Boolean
expression (condition) specified on the attributes of relation R.

Where <attribute name> is the name of an attribute of R, <comparison op> is normally one of the operators
{=, , ≥, ≠}, and <constant value> is a constant value from the attribute domain.
For example,
To 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, we can specify the following SELECT operation:

The result is shown in the figure below

Notice that all the comparison operators {=, <, ≤, >, ≥, ≠} in the set can apply to attributes whose domains are
ordered values, such as numeric or date domains. If the domain of an attribute is a set of unordered values,
then only the comparison operators in the set {=, ≠} can be used.
An example of an unordered domain is the domain Color = { ‘red’, ‘blue’, ‘green’, ‘white’, ‘yellow’, …},
where no order is specified among the various colors.
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; other wise, 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.
The SELECT operator is unary; that is, it is applied to a single relation. Moreover, the selection operation is
applied to each tuple individually; hence, selection conditions cannot involve more than one tuple. The degree
of the relation resulting from a SELECT operation—its number of attributes—is the same as the degree of R.
Notice that the SELECT operation is commutative; that is,

we can always combine a cascade (or sequence) of SELECT operations into a single SELECT operation with
a conjunctive (AND) condition; that is,

Example:
Consider the relation called EMPLOYEE given below

EmpID Name Department Salary

101 Alice HR 50000
102 Bob IT 60000
103 Carol IT 45000
104 David HR 70000
105 Emma IT 80000
The following SELECT operation

σSalary > 50000 (σDepartment = 'IT' (Employee))

gives the result
EmpID Name Department Salary
102 Bob IT 60000
105 Emma IT 80000
THE PROJECT OPERATION
The PROJECT operation, on the other hand, selects certain columns from the table and discards the other
columns.
For example, to list each employee’s first and last name and salary, we can use the PROJECT operation as
follows:

The resulting relation is shown in the figure below.

The general form of the PROJECT operation is

where π (pi) is the symbol used to represent the PROJECT operation, and <attribute list> is the desired sublist
of attributes from the attributes of relation R.
The PROJECT operation removes any duplicate tuples, so the result of the PROJECT operation is a set of
distinct tuples, and hence a valid relation. This is known as duplicate elimination.
For example, consider the following PROJECT operation:

The result is shown in the figure below:

Notice that the tuple <’F’,25000>appears only once in Figure above, even though this combination of values
appears twice in the EMPLOYEE relation.
If duplicates are not eliminated, the result would be a multiset or bag of tuples rather than a set.
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. If the projection list is a superkey of R—that is, it includes some key of R—the resulting
relation has the same number of tuples as R. Moreover,

RENAME Operation (ρ)

We can rename just attributes without changing the relation name:

ρ(EmpName,EmpSSN,DeptNo)(EMPLOYEE)
This just changes attribute names inside the same relation.

SEQUENCES OF OPERATION AND RENAME OPERATION

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:

Alternatively, we can explicitly show the sequence of operations, giving a name to each intermediate relation,
and using the assignment operation, denoted by ← (left arrow), as follows:

We can also rename the attributes in the intermediate and result relations. This can be useful in connection
with more complex operations such as UNION and JOIN,
To rename the attributes in a relation, we simply list the new attribute names in parentheses, as in the following
example:

These two operations are illustrated in the figure below:

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 order.
RELATIONAL ALGEBRA OPERATIONS FROM SET THEORY
THE UNION, INTERSECTION AND MINUS OPERATION
The next group of relational algebra operations are the standard mathematical operations on sets. For 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:

The relation RESULT1 has the Ssn of all employees who work in department 5, whereas RESULT2 has the
Ssn of all employees who directly supervise an employee who works in department 5. The UNION operation
produces the tuples that are in either RESULT1 or RESULT2 or both while eliminating any duplicates. Thus,
the Ssn value ‘333445555’ appears only once in the result as shown in the figure below.
We can define the three operations UNION, INTERSECTION, and SET DIFFERENCE on two union-
compatible relations R and S as follows:
• 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.
Figure below illustrates the three operations. The relations STUDENT and INSTRUCTOR in Figure (a) are
union compatible and their tuples represent the names of students and the names of instructors, respectively.
The result of the UNION operation in Figure (b) shows the names of all students and instructors. Note that
duplicate tuples appear only once in the result. The result of the INTERSECTION operation (Figure (c))
includes only those who are both students and instructors.

THE CARTESIAN PRODUCT (CROSS PRODUCT OPERATION)

In its binary form, 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 n-ary CARTESIAN PRODUCT operation is an extension of the above concept, which produces new
tuples by concatenating all possible combinations of tuples from n underlying relations. The CARTESIAN
PRODUCT operation applied by itself is generally meaningless. It is mostly useful when followed by a
selection that matches values of attributes coming from the component relations.
For example, suppose that we want to retrieve a list of names of each female employee’s dependents. We can
do this as follows:

The resulting relations from this sequence of operations are shown in Figure (e) below. The
EMP_DEPENDENTS relation is the result of applying the CARTESIAN PRODUCT operation to
EMPNAMES from Figure (b) with DEPENDENT from Figure (c). In EMP_DEPENDENTS, every tuple from
EMPNAMES is combined with every tuple from DEPENDENT, giving a result that is not very meaningful
(every dependent is combined with every female employee). We want to combine a female employee tuple
only with her particular dependents—namely, the DEPENDENT tuples whose Essn value match the Ssn value
of the EMPLOYEE tuple. The ACTUAL_DEPENDENTS relation accomplishes this.

(a)

(b)
(c)

(d)
(e)
Example 2
EmpID Name
1 Alice
2 Bob

DeptID DeptName
10 HR
20 Engineering
Result of EMPLOYEE × DEPARTMENT

EmpID Name DeptID DeptName

1 Alice 10 HR
1 Alice 20 Engineering
2 Bob 10 HR
2 Bob 20 Engineering

BINARY RELATIONAL OPERATIONS

THE JOIN OPERATION (INNER JOIN)
The JOIN operation, denoted by , is used to combine related tuples from two relations into single “longer”
tuples. This operation is very important for any relational database with more than a single relation because it
allows us to process relationships among relations. To illustrate JOIN, 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 Mgr_ssn value in the department tuple. We do
this by using the JOIN operation and then projecting the result over the necessary attributes, as follows:

The first operation is illustrated in Figure BELOW. Note that Mgr_ssn is a foreign key of the DEPARTMENT
relation that references Ssn, the primary key of the EMPLOYEE relation. This referential integrity constraint
plays a role in having matching tuples in the referenced relation EMPLOYEE. The JOIN operation can be
specified as a CARTESIAN PRODUCT operation followed by a SELECT operation.
Theta 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.

where each <condition> is of the form Ai θ Bj, Ai is an attribute of R, Bj is an attribute of S, Ai and Bj have
the same domain, and θ (theta) is one of the comparison operators { =, <, ≤, >, ≥, ≠}. 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.
VARIATIONS OF JOIN: EQUIJOIN AND NATURAL JOIN
EQUIJOIN: 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. Both previous examples were
EQUIJOINs. Notice that in the result of an EQUIJOIN we always have one or more pairs of attributes that
have identical values in every tuple.
NATURAL JOIN: A natural join combines two relations (tables) by automatically matching all columns
with the same name and eliminating duplicate columns in the result.
Example:
Employee Table

EmpID Name DeptID

1 Alice 10
2 Bob 20
3 Carol 30

Department Table

DeptID DeptName
10 HR
20 Engineering
40 Marketing
Result of Natural Join

EmpID Name DeptID DeptName

1 Alice 10 HR

2 Bob 20 Engineering
Example 2

EmpID Name DeptID

1 Alice 10
2 Bob 20
3 Carol 10
4 Daniel 20
5 Eve 30

DeptID DeptName
10 HR
20 Engineering
30 Marketing

The result of Natural Join

EmpID Name DeptID DeptName

1 Alice 10 HR
3 Carol 10 HR
2 Bob 20 Engineering
4 Daniel 20 Engineering
5 Eve 30 Marketing

Example 3
Consider the Project Table

Pname Pnumber Plocation Dnum

ProjectX 1 New York 5
ProjectY 2 Houston 4
Consider the Department Table

Dname Dnumber Mgr_ssn Mgr_start_date

Research 5 123456 2010-01-01

Admin 4 654321 2012-06-15

 • In PROJECT, the controlling department is identified by attribute Dnum.
• In DEPARTMENT, department number is Dnumber.
They are logically the same, but have different attribute names.
• We rename DEPARTMENT's Dnumber → Dnum so that the attribute matches for the natural join
to work.

The resulting Department Table will be:

Dname Dnum Mgr_ssn Mgr_start_date

Research 5 123456 2010-01-01

Admin 4 654321 2012-06-15

• Now we can join Natural Join.

This joins the PROJECT and DEPT tables on the common attribute Dnum.

Pname Pnumber Plocation Dnum Dname Mgr_ssn Mgr_start_date

ProjectX 1 New York 5 Research 123456 2010-01-01

ProjectY 2 Houston 4 Admin 654321 2012-06-15

If the attributes on which the natural join is specified already have the same names in both relations, renaming
is unnecessary.

Notice that if no combination of tuples satisfies the join condition, the result of a JOIN is an empty relation
with zero tuples.

Feature Natural Join Inner Join

Join Automatically joins on all common Requires an explicit join condition (e.g., ON
Condition attribute names [Link] = [Link])
Column Duplicates are removed (only one copy of Both columns are usually retained unless
Names matching columns kept) specified
Manual
Less control (automatic) More control (you specify how to join)
Control
Risk of May join on unintended columns if names
Safer, as you choose the join condition
Errors match

A COMPLETE SET OF RELATIONAL ALGEBRA OPERATIONS

It has been shown that the 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:

As another example, a JOIN operation can be specified as a CARTESIAN PRODUCT followed by a SELECT
operation, as we discussed:

Similarly, a NATURAL JOIN can be specified as a CARTESIAN PRODUCT preceded by RENAME and
followed by SELECT and PROJECT operations.

THE DIVISION OPERATION

The DIVISION operation, denoted by ÷, is useful for a special kind of query that sometimes occurs in database
applications. T←R÷S

Notice that 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
An example is Retrieve the names of employees who work on all the projects that ‘John Smith’ works on. To
express this query using the DIVISION operation, proceed as follows.

1. Consider the following Relations

2. First, retrieve the list of project numbers that ‘John Smith’ works on in the intermediate relation
SMITH_PNOS:
 3. PROJECT Essn and Pno from WORKS_ON Relation.

4. Perform Division operation of SSN_PNOS and SMITH_PNOS. The division operation gives the Ssn
number of employees who work in all the projects worked by John Smith

5. Finally perform Natural Join of SSNS and EMPLOYEE and Project only the FName, MInit and
LName of these employees.

NOTATION FOR QUERY TREES

A query tree is a way of representing a relational algebra expression using a tree-like structure.
• Here Input relations (Tables) are represented as leaf nodes at the bottom of the Tree
• The Operations like SELECT, PROJECT, JOIN etc are represented as Internal Nodes in the middle of
the Tree.
• The final result is represented at the Root Node (Top of the Tree).
Execution Process:
• Start from leaf nodes: These are just the input relations (tables) from the database.
• Execute internal nodes step by step: Each internal node is a relational algebra operation (e.g., σ for
selection, π for projection, ⋈ for join). The operation is executed only when its child nodes are ready
(i.e., we have their result relations).
• Replace node with result relation: After an operation is done, its output (result relation) replaces
that node. This output becomes input for the next operation (closer to the root).
• Continue until the root node is executed: When the root operation is done, we get the final result
of the query.
Example: Suppose we the following request - For every project located in ‘Stafford’, list the project number, the
controlling department number, and the department manager’s last name, address, and birth date.
The query using Relational Algebra is

The Query Tree for this is given below

In order to execute this query, the node marked (1) in Figure 8.9 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.
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:

where F1, F2, … , Fn are functions over the attributes in relation R

Example: As an 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
Then a generalized projection combined with renaming may be used as follows:

AGGREGATE FUNCTIONS AND GROUPING

Examples of such functions include retrieving the average or total salary of all employees or the total number of
employee 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.
Another common type of request involves grouping the tuples in a relation. An example would be to 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.
The AGGREGATE FUNCTION is given by

where <grouping attributes> is a list of attributes of the relation specified in R, and <function list> is a list of (<function>
<attribute> ) pairs.
For example, to retrieve each department number, the number of employees in the department, and their average
salary, while renaming the resulting attributes, we write:
RECURSIVE CLOSURE OPERATIONS
In relational algebra, recursive closure (sometimes called transitive closure) is used when a relationship is
recursive — meaning a tuple in a relation can be related to another tuple in the same relation.
Super_ssn is a foreign key referencing Ssn of another employee (the supervisor). This is a recursive
relationship, because both supervisee and supervisor come from the same table.
Suppose we want all supervisees of James Borg
• Direct supervisees: Franklin T Wong, Jennifer S Wallace
• Indirect supervisees: Ramesh Narayan & Joyce English (supervised by Franklin T Wong),
Ahmad Jabbar (supervised by Jennifer S Wallace)
By using single JOIN we can only get direct supervisees.
Recursive Closure operation is a solution to it

OUTER JOIN OPERATIONS

• The JOIN operations described earlier 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 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.
• Left Outer Join: Returns all tuples from the left relation and the matching tuples from the right
relation, and fills NULLs where no match is found.
R⟕S
Example:
Employee (R)

EmpID Name DeptID

1 Alice 10
2 Bob 20
3 Carol 30

Department (S)

DeptID DeptName
10 Sales
20 HR
EMPLOYEE ⟕ DEPARTMENT Result is

EmpID Name DeptID DeptName

1 Alice 10 Sales
2 Bob 20 HR
3 Carol 30 NULL
• The LEFT OUTER JOIN operation keeps every tuple in the first, or left, relation R; if no matching
tuple is found in S, then the attributes of S in the join result are filled or padded with NULL values. T
• Right Outer Join: Returns all tuples from the right relation, and the matching tuples from the left
relation. If there is no match from the left, it fills with NULLs.
R⟖S
Example
Employee (R)

EmpID Name DeptID

1 Alice 10
2 Bob 20
 Department (S)

DeptID DeptName

10 Sales

20 HR

30 Marketing
The result of Right Outer Join is

EmpID Name DeptID DeptName

1 Alice 10 Sales
2 Bob 20 HR
NULL NULL 30 Marketing

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.
• It is used when we want to combine two relations with different schemas (i.e., different attribute
sets) by:
o Matching common attributes (by name or position),
o Retaining all tuples from both relations, and
o Filling missing attributes with nulls where needed.

Example:
Suppose we have the following two relations:

EmpID Name

1 Alice

2 Bob

MANAGER

MgrID Dept

10 Sales

20 HR
Now we perform outer union
EMPLOYEE ⨝⨝ MANAGER
Since the schemas are different, the result is:

EmpID Name MgrID Dept

1 Alice null null
2 Bob null null
Null null 10 Sales
Null null 20 HR
Let us take another example with atleast one attribute same in two relations
Student Relation

ID Name
1 Alice
2 Bob
Teacher Relation

ID Subject
3 Math
4 Science
The result of the outer Unioin is

ID Name Subject
1 Alice null
2 Bob null
3 null Math
4 null Science

EXAMPLES OF QUERIES IN RELATIONAL ALGEBRA

The following are additional examples to illustrate the use of the relational algebra operations. All examples
refer to the database in Figure below.
1. Retrieve the name and address of all employees who work for the ‘Research’ department.

As a single in-line expression, this query becomes:

2. For every project located in ‘Stafford’, list the project number, the controlling department
number, and the department manager’s last name, address, and birth date.

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

In this query, we first create a table DEPT5_PROJS that contains the project numbers of all projects
controlled by department 5. Then we create a table EMP_PROJ that holds (Ssn, Pno) tuples, and apply
the division operation. Notice that we renamed the attributes so that they will be correctly used in the
division operation. Finally, we join the result of the division, which holds only Ssn val ues, with the
EMPLOYEE table to retrieve the Fname, Lname attributes from EMPLOYEE.
4. Make a list of project numbers for projects that involve an employee whose last name is ‘Smith’,
either as a worker or as a manager of the department that controls the project.

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

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

7. List the names of managers who have at least one dependent.