Databases

Chapter 1: ER Model

U
n
and Relational Model4.3
Chapter 2: Structured Query Language4.21
Chapter 3: Normalization4.49
Chapter 4: Transaction and Concurrency
4.65
Chapter 5: File Management4.82

i
t
4
 Chapter 1
ER Model and Relational Model
LEARNING OBJECTIVES

 Data model  Entity types, entity sets and value sets

 Schemas  Weak entity set
 Three-schema architecture  Relational database
 ER model  NULL in tuples
 Types of attributes  Inherent constraint
 Mapping cardinality  Referential and entity integrity constraint
 Complex attributes

intRodUCtion Data Model

A database is a collection of related data. By data, we mean facts A data model is a collection of concepts that can be used to describe
that can be recorded and that have implicit meaning. the structure of a database. It provides the necessary means to
achieve abstraction.
Example: Consider the names, telephone numbers and addresses
of the people. We can record this data in an indexed address book
and store it as Excel file on a hard drive using a personal computer. sChEMas
This is a collection of related data with an implicit meaning and In any data model, it is important to distinguish between the
hence is a database. description of the database and the database itself. The descrip-
A database management system (DBMS) is a collection of pro- tion of a database is called the database schema, which is
grams that enables users to create and maintain a database. The specified during database design and is not expected to change
DBMS is a general-purpose software system that facilitates the frequently.
processes of defining, constructing, manipulating and sharing The actual data in a database may change frequently, for exam-
databases among various users and applications. ple the student database changes every time we add a student or
1. Defining the database involves specifying the data types, enter a new grade for a student. The data in the database at a par-
structures, and constraints for the data to be stored in the ticular moment in time is called a database state or snapshot. It
database. is also called the current set of occurrences or instances in the
2. Constructing the database is the process of storing the data database.
itself on some storage medium that is controlled by the The distinction between database schema and database state is
DBMS very important. When we define a new database, we specify its
3. Manipulating a database includes such functions as querying database schema only to the DBMS. At this point, the correspond-
the database to retrieve specific data, updating the database ing database state is the empty state with no data. We get the ini-
to reflect changes. tial state of the database when the database is first loaded with
4. Sharing a database allows multiple users and programs to the initial data. The DBMS stores the description of the schema
access the database concurrently. constructs and constraints, also called the metadata in the DBMS
5. Fundamental characteristics of the database approach is that catalog so that DBMS software can refer to the schema whenever
it provides some level of data abstraction by hiding details of it needs. The schema is sometimes called the intension, and the
data storage that are not needed by users. database state an extension of the schema.
4.4 | Unit 4 • Databases

Three-schema Architecture as entities. In general, there is no presumption that an entity

The goal of the three-schema architecture is to separate the is animate.
user applications and the physical database. 1. An object with a physical existence
Example: A particular person, car, house, employee.
Levels of Abstraction 2. An object with a conceptual existence
Example: A company, a job, a university course.
View 1 View 2 View 3 Each entity has attributes, the particular properties
that describe it.
Example: An employee entity can be described by
Conceptual schema
employee’s name, age, address, salary and job.

Physical schema
Entity Set
Set of entities of same type that shares the same properties.
Example: All persons, all companies etc.

Example: Entity sets of customer and loan

1. The external or view level includes a number of
external schemas or user views. Each external schema Table 1 Customer Entity Set
describes the part of the database that a particular Customer-id Cust-name Cust-street City
user group is interested in and hides the rest of the
C-143 John MG Road [Link]
database.
2. The conceptual level has a conceptual schema, which C-174 Mary SP Road [Link]
describes the structure of the whole database for a C-183 Tony KD Road [Link]
community of users. The conceptual schema hides the
C-192 Satya SG Road Eluru
details of physical storage structures and concentrates
on describing entities, data types, relationships, user
operations, and constraints.
3. The internal level has an internal schema, which Table 2 Loan Entity Set
describes the physical storage structures of the Loan-no Amount
database. It describes the complete details of data L-30 $3000
storage and access paths for the database.
L-31 $4000
L-32 $3500
ER Model L-33 $4500
Entity relationship model is a popular high-level conceptual L-34 $5000
data model. This model and its variations are used for the
conceptual design of database applications, and many data- An entity is represented by a set of attributes and by a descrip-
base design tools employ its concepts. ER model describes tive properties possessed by all members of an entity set.
data as entities, relationships and attributes. The basic object
that the ER model represents is an entity.
Types of Attributes
1. Simple versus composite
Entity 2. Single valued versus multivalued
It is an object that exists and is distinguishable from other 3. Stored versus derived.
objects
(or) Composite attribute: Composite attributes can be divided
Entity is a “thing” in the real world with an independent into smaller subparts, which represent more basic attribute
existence. that has their own meaning (Figure 1).
(or) Example: A common example is Address, it can be broken
An entity is something that has a distinct, separate exist- down into a number of subparts such as street address,
ence, although it need not be a material existence. In par- city, postal code; street address is further broken down into
ticular, abstractions and legal functions are usually regarded Number, street Name and Apartment number.
 Chapter 1 • ER Model and Relational Model | 4.5

Address One-to-one: An entity in A is associated with at most one

entity in B and an entity in B is associated with at most one
Street address City State Zip entity in A (Figure 3).

a1 b1
a2 b2
Number Street House-No a3 b3
a4 b4
Figure 1 A hierarchy of composite attributes.

Street address is a composite attribute. Attributes that are Figure 3 One-to-one relationship set.
not divisible are called simple (or) atomic attributes.
One-to-many: An entity in A is associated with any number
Single-valued versus multivalued attributes: Most attributes of entities in B. But an entity in B is associated with at most
have a single value for a particular entity, such attributes are one entity in A (Figure 4).
called single-valued attribute.
b1
Example: Age is a single-valued attribute a1
b2
Multivalued attributes: An attribute can have a set of values a2 b3
for the same entity. a3 b4
Example: College degrees attribute for a person b5
Example: Name is also a multivalued attribute (Figure 2).
Figure 4 One-to-many relationship set.
Name Many-to-one: An entity in A is associated with at most one
entity in B. But an entity in B can be associated with any
First name Last name number of entities in A (Figure 5).
Middle name
a1
Figure 2 Multivalued attribute. b1
a2
Stored versus derived attributes: Two (or) more attribute a3 b2
values are related. a4 b3
a5
Example: Age can be derived from a person’s date of birth.
The age attribute is called derived attribute and is said to be Figure 5 Many-to-one relationship set.
derivable from the DOB attribute, which is called a stored
attribute. Many-to-many: An entity in A is associated with any num-
ber of entities in B. But an entity in B can be associated with
Domain: The set of permitted values for each attribute.
any number of entities in A (Figure 6).
Example: A person’s age must be in the domain {0-130}
a1 b1
a2 b2
Relationship Sets a3 b3
A relationship is an association among several entities. a4 b4
Relationship sets that involve two entity sets are binary.
Figure 6 Many-to-many relationship set.
Generally, most relationships in databases are binary.
Relationship sets may involve more than two entity sets. Example: One customer can have multiple accounts
Example: Employee of a bank may have responsibilities at Customer(c-Name) (Acc. no, Amount)
multiple braches, with different jobs at different branches, then Table 3 Example of One-to-many Relationship Set
there is a ternary relation between employee, job and branch.
Arun A-101 $3000

Mapping Cardinality Bunny A-102 $3500

For a binary relationship set, mapping cardinality must be: Kate A-103 $2000
1. One-to-one Mary A-104 $2500
2. One-to-many John A-105 $4000
3. Many-to-one
4. Many-to-many In Table 3, many-to-one relationship is not possible.
4.6 | Unit 4 • Databases

Complex Attributes ({Phone (Areacode, phoneNumber)}, Address (StreetAddress

Composite and multivalued attributes can be nested in an (StreetNumber, streetName, ApartmentNumber), city, state,
arbitrary way. We can represent arbitrary nesting by group- zip))}
ing components of a composite attribute between parenthe-
ses () and separating the components with commas, and by Entity types, entity sets and value sets
displaying multivalued attributes between braces { }. Such
An entity type defines a collection of entities that have the
attributes are called complex attributes.
same attributes. Each entity type in the database is described
Example: A person can have more than one residence and each by its name and attribute. The following figure shows two
residence can have multiple phones, an attribute AddressPhone entity types, named STUDENT and EMPLOYEE and a list
for a person can be specified as shown below. {AddressPhone of attributes for each

ENTITY TYPE NAME STUDENT EMPLOYEE

ATTRIBUTES: [Link], Name, Grade Name, Salary, Age

S 1. e 1.

(86, Arun, A) (Kamal, 20K, 42)

ENTITY SET S2. e 2.

(87, Pavan, B) (Bharat, 25K, 41)

(EXTENSION)
S 3. e 3.

(89, Karan, A) (Bhanu, 26K, 41)

The collection of all entities of a particular entity type in the Binary relation If a relationship type is between entities
database at any point in time is called an entity set. in one type and entities in another type then it is called a
binary relation, because two entity types are involved in the
Types of relations relation.
1. Unary relation. 4. Quadnary relation.
2. Binary relation. 5. N-ary relation
Customer Purchased Product
3. Ternary relation.
Relationship
The above relation indicates that customers purchased prod-
uct (or) products are purchased by customers.
Number of
Degree Quadnary relation If a relationship type is among entities
entity types
of four different types, then it is called quadnary relation.
1. Unary
2. Binary
Lecturer
3. Ternary Cardinality Optionality
1:1 Optional
N–ary 1:N Mandatory
N:1
M:N Student Register Course
Unary relation If a relationship type is between entities in a
single entity type then it is called a unary relationship type.

Department
Employee Managed-by
In the above ER-diagram, any two entities can have a
relation.

In employee entity, we will have all the employees including N-ary relation ‘N’ number of entities will participate in
‘manager’, this relation indicates, employees are managed a relation, and each entity can have a relation with all the
by manager. other entities.
 Chapter 1 • ER Model and Relational Model | 4.7

E1 relationship, whereas partial participation is represented by

EN E2 a single line.

E6
ER Diagrams (Figure 7 and 8)
E3
E5 Cust-street
E4
C-name L No Amount
Cust-city
Cust-id
Cardinality Ratio Customer Borrower Loan
and Participation Constraints
The cardinality ratio for a binary relationship specifies the Figure 7 ER diagram.
maximum number of relationship instances that an entity
can participate in Notations:

1. The participation constraint specifies whether → Represents entity

the existence of an entity depends on its being
related to another entity via the relationship type. → Represents relationship sets
This constraint specifies the minimum number of –––– → Represents links between attributes to entity
relationship instances that each entity can participate sets and entity sets to relationship sets
in, and is some times called the minimum cardinality → Represents attributes
constraint. → Represents multivalued attributes
2. There are two types of participation constraints: → Represents primary key attribute
a. Total participation
b. Partial participation Phone-no DOB
Example: If a company policy states that every employee Age
must work for a department, then an employee entity Cust-id
can exist only if it participates (or) works for at least one
Customer
department.

EMPLOYEE WORKS-FOR DEPARTMENT Name

First name
Last
r1
e1 Middle name
d1
r2 name
e2
r3 Figure 8 ER diagram.
e3 d2
r4 → Derived attribute
e4 . → Multivalued attribute
. . .
. .

→ Weak entity

Every entity in the EMPLOYEE set must be related to a

DEPARTMENT entity via WORK-FOR. Total participa-
tion is also called existence dependency. If we do not expect → Weak entity set relation

every employee to manage a department, so the partici-

pation of EMPLOYEE in the relationship type is partial,
means not necessarily all employees’ entities are related to
some department entity.
Cardinality ratio and participation constraints are taken
together as the structural constraints of a relationship type. → Composite attribute
In ER diagrams, total participation is displayed as a dou-
ble line connecting the participating entity type to the
4.8 | Unit 4 • Databases

R
Many-to-many
E E Total Participation
of E2 in R1 Examples:
1. Many students are taught by many teachers.
1 N
E R E Cardinality 2. Many patients are treated by many doctors.
ratio 1: n 3. Many medications are taken by many patients.
Structural
4. Many customers buy many products.
(min, max) constraint on 5. Many books are written by many authors.
R E
participation of
E In R

Cardinality Constraints Customer Borrower Loan

One-to-one
Each entity of one entity set is related to at most one entity Customer is associated with several loans and loan is asso-
of the other set. Only one matching record exists between ciated with several customers.
two tables.
Example: Assume each owner is allowed to have only ER Diagram with a Ternary
one dog and each dog must belong to one owner. The own Relationship
relationship between dog and owner is one-to-one. One-to-
one relationships can often combine the data into one table. Title Level

Examples: Job
1. One birdfeeder is located in one place in the yard. E-name Street Assets
B-city
2. One state has one governor. E-id
City B-name
3. One yard has one address.
4. One patient has one phone number.
2. One student has one ID. Employee Works-on Branch

Figure 9 ER diagram with a ternary relationship.

Weak Entity Set

Customer Borrower Loan
An entity set that does not have a primary key is called weak
entity set.
One customer is associated to one loan via borrower Weak entity set is represented by →
Underline the primary key of a weak entity with a dashed line.
One-to-many
Example:
Examples:
P-date
1. One birdfeeder is visited by many birds.
2. One student can have many degrees. L-no
Amount Amount
3. One Book can be written by many authors. P-no
4. One yard contains many bird feeders.
5. One patient has many prescriptions. Loan
Loan payment Payment
In the one-to-many relationship, a loan is associated with
one customer via borrower.

Many-to-one Relational Database

Relational Model
The relational model represents the database as a collection
of relations. When a relation is thought of as a table of val-
Customer Borrower Loan
ues, each row in the table represents a collection of related
data values. Each row in the table represents a fact that typi-
A customer is associated with at most one loan via borrower. cally corresponds to a real-world entity. The table name and
 Chapter 1 • ER Model and Relational Model | 4.9

column names are used to help in interpreting the meaning •• Manipulative aspect: The operators available to
of the values in each row. the user for manipulating those tables, for purposes
In formal relational model terminology, a row is called a of data retrieval, these operators derive tables form
tuple, a column header is called an attribute, and the table tables, the most important operators are ‘SELECT’,
is called a relation. ‘PROJECT’ and JOIN.

Domain Relation Schema

A domain is a set of atomic values. A common method of A relation schema ‘R’ denoted by R(A1, A2, . . . An) is made
specifying a domain is to specify a data type from which the up of a relation name R and a list of attributes A1, A2, . . . An.
data values forming the domain are drawn. It is also useful Each Attribute Ai is the name of role played by some domain
to specify a name for the domain, to help in interpreting its D in the relation schema R. D is called the domain of Ai and
values is denoted by dom(Ai).
A relation schema is used to describe a relation and R is
Example:
called the name of this relation. The degree of a relation is
1. Set of telephone numbers: The set of valid numbers in the number of attributes ‘n’ of its relation schema.
a particular country.
2. Employee id numbers: The set of valid employee Example:
numbers in a company. A relation schema of degree ‘7’, which describes an
3. Names: The set of character strings that represent employee is given below:
names of persons.
EMPLOYEE (Name, EId, HomePhone, Address, Office
4. Grade-point average: Possible values of computed
phone, Age, Salary)
grade point averages, each must be real (floating
point) number between 0 and 4 Using the data type of each attribute, the definition is
5. Research department names: The set of research written as:
department names in a specialization, such as computer EMPLOYEE (Name: String, EId: INT, Homephone: INT,
science, chemistry and applied mathematics. Address: String, OfficePhone: String, Age: Real, Salary: INT)
6. Research department codes: The set of Research For this relation schema, EMPLOYEE is the name of the
department codes, such as CS, CHE, AM. relation, which has ‘7’ attributes.
2. A relation ‘r’ of the relation schema R(A1, A2 . . . An),
The preceding is called logical definitions of domains.
also denoted by r(R), is a set of n-tuples. r = {t1, t2 . . . tm}.
The data type for research department names is set of
Each n-tuple ‘t’ is an ordered list of n values t =
character strings that represent valid department names.
<V1, V2 . . . Nn>, where each value Vi, 1 ≤ i . . . n, is an
A domain is thus given a name, data type, and format.
element of dom(Ai) or is a special null value.
Additional information for interpreting the values of a
3. The ith value in tuple t, which corresponds to the
domain can also be given, for example a numeric domain
attribute Ai, is referred to as t[Ai].
such as person weights should have the units of measure-
4. The following figure shows EMPLOYEE relation.
ments, such as kilograms or pounds.
Each type in a relation represents a particular
1. The relational model is often described as having the employee entity. We display the relation as a table
following three aspects: where each tuple is shown as a row and each attribute
•• Structural aspect: The data in the database is per- corresponds to a column header, indicating a role or
ceived by the user as tables. interpretation of the values in that column. Null values
•• Integrity aspect: Those tables has to satisfy certain represent attributes whose values are unknown or do
integrity constraints. not exist for some individual EMPLOYEE tuple.

Employee

Home Office
Name EId Phone Address Phone Age Salary

Mahesh 30-01 870-223366 Warangal NULL 35 40 k

Ramesh 30-02 040-226633 Hyderabad NULL 36 40 k

Suresh 30-03 040-663322 Kolkata 040-331123 35 42 k

Dinesh 30-04 040-772299 Bangalore 040-321643 36 40 k

4.10 | Unit 4 • Databases

Fig: The attributes and tuples of a relation EMPLOYEE. The 3. Constraints that cannot be directly expressed in
earlier definition of a relation can be restated as follows: the schemas of the data model, and they must be
A relation r(R) is a mathematical relation of degree ‘n’ on expressed and enforced by the application programs are
the domains dom(A1), . . . , dom(An), which is a subset of the application-based constraints.
Cartesian product of the domains that define R:
r(R) C (dom(A1) × dom(A2) . . . × dom(An)) Inherent Constraint
The constraint that a relation cannot have duplicate tuples
Characteristics of Relations is an inherent constraint. Another important category of
There are certain characteristics that make a relation differ- constraints is data dependencies, which include ‘functional
ent from a file or a table. dependencies’ and ‘multivalued dependencies’. They are used
Ordering of tuples in a relation: A relation is defined mainly for testing the ‘goodness’ of the design of a relational
as a set of tuples. Tuples in a relation do not have any par- database and are utilized in a process called normalization.
ticular order. In a file, records are stored on disk in order.
This ordering indicates first, second, ith, and last records in Schema-based Constraints
the file. Similarly, when we display a relation as a table, the 1. Domain constraints
rows are displayed in a certain order. 2. Key constraints
Tuple ordering is not part of a relation definition, because 3. Constraints on nulls (Not null constraint)
a relation attempts to represent facts at a logical or abstract 4. Entity integrity constraints
level. Many logical orders can be specified on a relation. 5. Referential integrity constraints
Tuples in the EMPLOYEE relation could be logically 6. Unique constraint
ordered by values of Name or by EID or by Age or by some 7. Check constraint
other attribute. When a relation is implemented as a file or
displayed as a table, a particular ordering may be specified Domain constraints
on the records of the file or the rows of the table. Domain constraints specify that within each tuple, the value
of each attribute ‘X’ must be an atomic value from the
NULL in Tuples domain dom(X).
Each value in a tuple is an atomic value; that is, it is not The data types associated with domains include standard
divisible into components. Hence, composite and multi- numeric data types for integers
valued attributes are not allowed. This model is sometimes 1. Short integer
called the flat relational model. Multivalued attributes must 2. Integer
be represented by separate relations, and composite attrib- 3. Long integer
utes are represented only by their simple component attrib- 4. Real numbers
utes in the basic relational model. •• Float
NULLS are used to represent the values of attributes that •• Double-precision float
may be unknown or may not apply to tuple. For example,
5. Characters
some student tuples have null in their office phones because
6. Booleans
they do not have an office. In this case, the meaning behind
7. Fixed-length strings
NULL is not applicable. If a student has a NULL for home
8. Variable-length strings
phone, it means either he/she does not have a home phone
9. Date, time, time stamp
or he/she has one but we do not know it, in this case the
10. Money data types
meaning of NULL is ‘Unknown’.
Key constraints
Relational Model Constraints A relation is a set of tuples. All elements of a set are dis-
In a relational database, there will be many relations, and tinct; hence, all tuples in a relation must also be distinct.
the tuples in those relations are related in various ways. This means no two tuples can have the same combination of
There are many restrictions or constraints on the actual val- values for all their attributes.
ues in a database state.
1. There are other subsets of attributes of a relation
Constraints on database can generally be divided into
schema R with the property that no two tuples
three main categories as follows:
in any relation state ‘r’ of R should have the same
1. Constraints that are inherent in the data model, we combination of values of these attributes.
call them inherent model-based constraints.   Suppose that we denote one subset of attributes by
2. Constraints that can be directly expressed in the ‘SK’, then for two distinct tuples t1 and t2 in a relation
schemes of the data model, by specifying them in state ‘r’ of R, we have the following constraint:
the DDL (Data Definition Language). We call these
schema-based constraints. t1[SK] = t2[SK]
 Chapter 1 • ER Model and Relational Model | 4.11

2. Any such set of attributes SK is called a super key of Another constraint on attributes specifies whether null
the relation schema R. values are permitted in tuples or not. If we want some tuples
  SK specifies a uniqueness constraint that no two to have a valid (or) non-null value, we need to use NOT
distinct tuples in any state r or R can have the same NULL constraint on that attribute.
value for SK.
3. Every relation has at least one default super key, the Referential and entity integrity constraint
set of all its attributes. A key, ‘K’ of a relation schema
The entity Integrity constraint states that no primary key
R is a super key of R with the additional property that
value can be null. If we have NULL values in the primary
removing any attributes ‘X’ from K leaves a set of
key column, we cannot identify some tuples in a relation.
attributes K’ that is not a super key of R any more.
1. Key constraints and entity Integrity constraints are
A key satisfies the following two constraints:
specified on individual relations
1. Two distinct tuples in any state of the relation cannot 2. Referential integrity constraint is specified between
have identical values for all the attributes in the key. relations and used to maintain the consistency among
2. A super key from which we cannot remove any tuples in the two relations.
attributes and still have the uniqueness constraints 3. Referential Integrity constraints states that a tuple in
mentioned in above condition is known as a minimal one relation that refers to another relation must refer
super key. to an existing tuple in that relation.
     The first condition applies to both keys and super 4. To understand the concept of Referential Integrity,
keys. The second condition is required only for keys. first we have to understand the concept of
Example: Consider the employee relation in Page no. 9. FOREIGN KEY.
The attribute set {EId} is a key of employee because no two 5. Suppose we have two relations R1 and R2. A set of
employee tuples can have the same value for EId. attributes FK in relation schema R1 is a foreign key
Any set of attributes that include EId will form a super key. of R1 that references relation R2 if it satisfies the
1. {EId, Homephone, Name} following two rules:
2. {EId, Age, Salary} •• The attributes in FK have the same domains as the
3. {Name, EId, Address} primary key attributes PK of R2, FK will have to
refer to PK.
However, the super key {EId, Name, Age} is not a key of
•• A value of FK in a tuple t1 of the current state r1(R1)
EMPLOYEE, because removing Name or age or both from
either occurs as a value of PK for some tuple t2 in
the set leaves us with a super key. Any super key formed from
the current state r2(R2) or is null. We have t1[FK]
a single attributes is also a key. A key with multiple attributes
= t2[PK], and we say that the tuple t1 references to
must require all its attributes to have the uniqueness property.
the tuple t2. In this definition, R1 is called the ref-
A relation schema may have more than one key. In that
erencing relation and R2 is the referenced relation.
case, each of the keys is called a candidate key.
6. A foreign key can refer to its own relation. We
Example: Employee relation has three candidate keys. can diagrammatically display referential integrity
{Name, EId, Homephone} constraints by drawing a directed Arc from each foreign
One of the candidate keys is chosen as primary key of the key to the relation it references. The arrow head may
relation. point to the primary key of the referenced relation.

Example:
EMPLOYEE
FNAME LNAME EID DOB GENDER SALARY DNO

DEPARTMENT

DNO DNAME DLOCATION DMANAGER

DEPENDENT

EID DEPENDENT-NAME GENDER DOB RELATIONSHIP

WORKS

EID PROJ-NO HOURS

4.12 | Unit 4 • Databases

7. Referential integrity rule: The database must not 3. It is like checking a condition before saving data into
contain any unmatched foreign key values. a column.
If ‘B’ References ‘A’, then A must exist. Example: Create table student (RNo:INT CHECK
(Rno>0)
NOT NULL constraint Name:varchar(60)
1. NOT NULL constraint restricts a column from having Dept:varchar(4))
a NULL value. NOT NULL constraint can be applied Suppose the following tuple is inserted into student table.
to any column in a table.
1. Insert into student values <-4, ‘Bhanu’, ‘CS’>
2. We cannot give NULL values under that column
2. CHECK constraint is enforced on RNo column, the
3. NOT NULL Constraint enforces a column to contain
RNo should be greater than ‘0’, but ‘-4’ is given.
a proper value.
3. CHECK constraint is violated.
4. This constraint cannot be defined at table level.
Creating table from a table: A view is called a derived table
Example: CREATE TABLE (or) virtual table, because the data stored in views is taken
student(RNo:INT Name:varchar(70) NOT NULL age:INT) from already existing tables.
Suppose a row is inserted into the following table, A view can also be defined as a logical subset of data
Insert into student values <11, NULL, 20> from one or more tables.
In the schema, we enforced NOT NULL constraint on Name Syntax:
column, means Name cannot have NULL value, when the CREATE view view-name As
above insert command is executed, the system gives, NOT SELECT column-names
NULL constraint violation. FROM table-name
WHERE condition
UNIQUE constraint
Example: Consider the following table “sales”.
The column on which UNIQUE constraint is enforced
should not have any duplicate values. Sales
Order Previous
1. UNIQUE constraint can be enforced on any column
Order-Id Name Balance Customer
except the primary key column.
21 Order 3 3000 Ana
2. By default primary key column will not accept any
22 Order 4 1000 Adam
duplicate values that are handled by key constraint.
23 Order 5 3000 Brat
3. UNIQUE constraint can be applied at column level or
table level. 24 Order 6 2000 John
25 Order 7 2000 Ana
Example: CREATE TABLE 26 Order 8 4000 Ana
student (RNo:INT  Name:varchar(60)  Grade:CHAR(1))
Assume that the table contains following tuples Query to create a view:
CREATE view sales-view As
Student
SELECT *
R no. Name Grade
FROM Sales
11 Sita B
WHERE customer = ‘Ana’
12 Anu A
13 Bala A 1. The data fetched from select statement will be stored
Suppose the following tuple is inserted into the student table. in an object called ‘sales-view’.
2. To display the contents stored in view, execute the
1. Insert into student values <14, ‘Anu’, ‘B’> following statement.
2. UNIQUE constraint is enforced on Name column, in
SELECT *
the student table we have ‘Anu’, and again the new
FROM Sales-view
tuple contains name ‘Anu’, this Insert command
violates the UNIQUE constraint. Removal of specific rows:
Consider the following SQL query:
CHECK constraint Delete *
This constraint is used to restrict a value of a column FROM Sales
between a range. The above query will delete all the tuples from sales.
1. When a value is inserted into particular column, To remove specific rows, we have to specify the condi-
before storing that, a check will be performed to see tion in WHERE clause.
whether the values lie within the specified range. Consider the table “sales” given in the above example.
2. If the value entered is out of range, it will not accept Remove the rows from sales table whose previous bal-
and violation happens. ance is 3000.
 Chapter 1 • ER Model and Relational Model | 4.13

SQL query: SHIPMENTS:

Delete *
FROM Sales Supplier Part Project
Number Number Number Quantity
WHERE Previous-balance = 3000
Output: SN1 PN1 PJ1 300

SN1 PN1 PJ4 400

Order Previous
Order Id Name Balance Customer SN2 PN3 PJ1 350
22 Order 4 1000 Adam
SN2 PN3 PJ2 450
24 Order 6 2000 John
25 Order 7 2000 Ana SN2 PN3 PJ3 640
26 Order 8 4000 Ana
SN2 PN3 PJ4 320
Referential actions: Referential Integrity can be violated if SN2 PN3 PJ5 330
the value of any foreign key refers to a tuple that does not
exist in the referenced relation. SN2 PN3 PJ6 520
When certain violations occur, we need to perform some SN2 PN3 PJ7 480
alternate action. Those actions are as follows:
SN2 PN5 PJ2 460
1. ON DELETE CASCADE SN3 PN3 PJ1 440
2. ON UPDATE CASCADE
SN3 PN4 PJ2 410
3. ON DELETE SET NULL
4. ON DELETE SET DEFAULT SN4 PN6 PJ3 310

Example: Consider the given database: SN4 PN6 PJ7 320

SN5 PN2 PJ2 340

SUPPLIERS:
SN5 PN2 PJ4 350
Supplier Supplier
Number Name Status City SN5 PN5 PJ5 360
SN1 Suma 30 Hyderabad SN5 PN5 PJ7 370
SN2 Hari 20 Chennai
SN5 PN6 PJ2 380
SN3 Anu 10 Hyderabad
SN5 PN1 PJ4 420
SN4 Mahesh 20 Bombay
SN5 Kamal 30 Delhi SN5 PN3 PJ4 440

SN5 PN4 PJ4 450

PARTS:
SN5 PN5 PJ4 400
Part Part
SN5 PN6 PJ4 410
number name Colour Weight City
PN1 X Red 13.0 Chennai
PN2 Y Green 13.5 Bombay Consider the following statement:
PN3 X Yellow 13.2 Hyderabad
PN4 Y Green 14.1 Calcutta DELETE FROM SUPPLIER
PN5 Z Red 14.3 Hyderabad WHERE SUPPLIER - NUMBER = ‘SN1’
PN6 Z Blue 14.2 Bombay
It deletes the supplier tuple for supplier ‘SN1’. The
PROJECT: database has some other tables which have ‘SN1’ tuple
Project Number Project Name City (Shipments table). The application does not delete those
PJ1 Display Chennai
suppliers, then it will find a violation, and an exception
will be raised.
PJ2 OCR Bombay
An alternate approach is possible, one that might be pref-
PJ3 RAID Chennai erable in some cases, and that is for the system to perform
PJ4 SORTER Hyderabad an appropriate ‘compensating action’ that will guarantee
PJ5 EDS Chennai that the overall result does still satisfy the constraint. In the
PJ6 Tape Bombay
example, the compensating action would be for the system
to delete the shipments for supplier SN1 “automatically”.
PJ7 Console Hyderabad
4.14 | Unit 4 • Databases

We can achieve this effect by extending the foreign key as In general, CREATE TRIGGER specifies, among other
indicated below: things, an event, a condition, and an action.
The event is an operation on the database (“INSERT ON
CREATE TABLE SHIPMENT{.....}....... HYDERABAD - SUPPLIER” in the example)
FOREIGN KEY {SUPPLIER - NUMBER} 1. The “condition” is a Boolean expression that has to
REFERENCES evaluate to TRUE in order for the action to be executed.
SUPPLIER ON DELETE CASCADE 2. The ‘action’ is the triggered procedure (“INSERT
INTO SUPPLIERS . . .)
The specification ON DELETE CASCADE defines a 3. The event and condition together are sometimes
delete rule for this particular foreign key, and the speci- called the triggering event. The combination of all
fication CASCADE is the referential action for that three (event, condition, and action) is usually called a
delete rule. The meaning of these specifications is that a trigger.
DELETE operation on the suppliers relvar will ‘Cascade” 4. Possible events include INSERT, DELETE, UPDATE,
to delete matching tuples (if any) in the shipments relvar reaching end-of-transaction (COMMIT) reaching a
as well. specified time of day, exceeding a specified elapsed
Same procedure is applied for all the referential actions. time, violating a specified constraint, etc.
5. A database that has associated triggers is sometimes
called an active database.
Triggers
Triggers are precompiled procedures that are stored along
with the database and invoked automatically whenever Base Table Constraints
some specified event occurs. SQL-base table constraints are specified on either CERATE
Suppose we have a view called HYDERABAD - TABLE or ALTER TABLE. Each such constraint is a can-
SUPPLIER defined as follows: didate key constraint, a foreign key constraint, or a CHECK
constraint.
CREATE VIEW HYDERABAD-SUPPLIER Candidate keys: An SQL candidate key definition takes one
AS SELECT SUPPLIER - NUMBER, SUPPLIER- of the following two forms:
NAME, STATUS
FROM SUPPLIER
WHERE CITY = ‘HYDERABAD’, PRIMARY KEY (< column name comma list>)
UNIQUE (< column name comma list>)
Normally, if the user tries to insert a row into this view, The following example illustrates base table con-
SQL will actually insert a row into the underlying base straints of all three kinds:
table SUPPLIERS with CITY value whatever the default CREATE TABLE SHIPMENTS
is for the CITY column. Assuming that default is not (SUPPLIER-NUMBER. SUPPLIER-NUMBER
Hyderabad, the net effect is that the new row will not NOT NULL, PART - NUMBER PART-NUMBER
appear in the view; therefore, let us create a triggered pro- NOT NULL, QUANTITY NOT NULL
cedure as follows: PRIMARY KEY (SUPPLIER - NUMBER,
PART NUMBER)
FOREIGN KEY (SUPPLIER-NUMBER)
CREATE TRIGGER HYDERABAD -
REFERENCES SUPPLIERS
SUPPLIER - INSERT
ON DELETE CASCADE
INSTEAD OF INSERT ON HYDERABAD
ON UPDATE CASCADE,
- SUPPLIER
FOREIGN KEY (PART-NUMBER)
REFERENCING NEW ROW AS R
REFERENCES PARTS
FOR EACH ROW
ON DELETE CASCADE
INSERT INTO SUPPLIERS (SUPPLIER -
ON UPDATE CASCADE
NUMBER, SUPPLIER - NAME, STATUS, CITY)
CHECK(QUANTITY ≤ QUANTITY (0) AND
VALUES (R. SUPPLIER - NUMBER, R.
SUPPLIER - NAME, R. STATUS, ‘HYDERABAD’); QUANTITY ≤ QUANTITY (1000));

Inserting a row into the view will now cause a row to be A check constraint of the form CHECK (< column name >
inserted into the underlying base table with CITY value IS NOT NULL) can be replaced by a simple NOT NULL
equal to Hyderabad inserted of the default value. specification in the definition of the column.
 Chapter 1 • ER Model and Relational Model | 4.15

Exercises
Practice Problems 1 B
Directions for questions 1 to 20: Select the correct alterna- Id Name Age
tive from the given choices. 15 Shreya 24
1. Consider the following two tables T1 and T2. Show the 25 Hari 40
output for the following operations: 98 Rohit 20
Table T1 99 Rohit 11

P Q R C
11 a 6 Id Phone Area

16 b 9 10 2200 02

26 a 7 99 2100 01

Table T2 How many tuples does the result of the following rela-
tional algebra expression contain? Assume that the
A B C scheme of (A∪B) is the same as that of A.
11 b 7 (A∪B)⋈[Link]>40 v [Link]<15C
26 c 4 (A) 6 (B) 7
11 b 6 (C) 8 (D) 9
4. Consider the relations A, B and C given in Question 3.
What is the number of tuples present in the result of
How many tuples does the result of the following SQL
given algebraic expressions?
query contain?
(i) T1 ⋈T1.P = T2.AT2
SELECT [Link]
(A) 2 (B) 3 FROM A
(C) 4 (D) 5
WHERE [Link]>
(ii) T1 ⋈T1.Q = T2.BT2

ALL (SELECT [Link]
(A) 2 (B) 3 FROM B
(C) 4 (D) .5
WHERE [Link] = ‘Arun’)?
(iii) T1 ⋈(T1.p = T2.A AND T1.R = T2.C)T2 (A) 0 (B) 1
(A) 1 (B) 2 (C) 2 (D) 3
(C) 3 (D) .4 5. Consider a database table T containing two columns
2. Suppose R1(A, B) and R2(C, D) are two relation schemas. X and Y each of type integer. After the creation of the
Let R1 and R2 be the corresponding relation instances. B table, one record (X = 1, Y = 1) is inserted in the table.
is a foreign key that refers to C in R2. If data in R1 and Let MX and MY denote the respective maximum value
R2 satisfy referential integrity constraints, which of the of X and Y among all records in the table at any point
following is true? in time. Using MX and MY, new records are inserted in
the table 128 times with X and Y values being MX + 1,
(A) π B ( R1 ) − π c ( R2 ) = φ 2 * MY + 1, respectively. It may be noted that each time
(B) π C ( R2 ) − π B ( R1 ) = φ after the insertion, values of MX and MY change. What
will be the output of the following SQL query after the
(C) π B ( R1 ) − π C ( R2 ) ≠ φ steps mentioned above are carried out?
(D) Both A and B Select y from t where x = 7;?
3. Consider the following relations: (A) 15 (B) 31
(C) 63 (D) 127
A, B and C
6. Database table by name loan records is given below:
A
Id Name Age Borrower Bank Manager Loan Amount
12 Arun 60 Ramesh Sunderajan 10000
15 Shreya 24 Suresh Ramgopal 5000
99 Rohit 11 Mahesh Sunderajan 7000
4.16 | Unit 4 • Databases

What is the output of the following SQL Query For any arbitrary predicate P, this query is equivalent to
SELECT count (*) which relational algebra expression?
FROM((SELECT Borrower, Bank-manager (A) Π a1 , a2 , … an (σ p R1 × R2 ×…× Rm )
FROM Loan-Records)AS S
(B) σ a1 , a2 , … an (σ p R1 × R2 ×…× Rm )
NATURAL JOIN
(SELECT Bank-manager, Loan-Amount (C) σ a1 , a2 , … an (∏ p R1 × R2 ×…× Rm )
FROM Loan-Records) AS T);
(D) Π R1 , R2 , … Rm (σ p a1 × a2 ×…× ( an )
(A) 3 (B) 4
(C) 5 (D) 6 11. Consider the following relation schema pertaining to a
7. Consider the following ER diagram: student’s database:
Student (Rollno, name, address)
m1 m2 m3 P1 P2 N1 N2 Enroll (Rollno, courseno, coursename)
Where the primary keys are shown underlined. The
m R1 P R2 N number of tuples in the student and Enroll tables are
120 and 6, respectively. What are the maximum and
What is the minimum number of tables needed to rep- minimum number of tuples that can be present in
resent M, N, P, R1, R2? (student * Enroll)
(A) 2 (B) 3 Where ‘*’ denotes natural join?
(C) 4 (D) 5 (A) 6, 6 (B) 6, 120
8. Let E1 and E2 be two entities in an ER diagram with (C) 120, 6 (D) 120, 120
simple single-valued attributes. R1 and R2 are two rela- 12. A relational schema for a train reservation database is
tionships between E1 and E2, where R1 is one-to-many given below
and R2 is many-to-many. R1 and R2 do not have any
Table 4 Passenger
attributes of their own. What is the minimum number
of tables required to represent this situation in the rela- Pid P Name Age
tional model? 0 ‘Sachin’ 65
(A) 2 (B) 3 1 ‘Rahul’ 66
(C) 4 (D) 5
‘Sourav’ 67
9. The following table has two attributes A and C where A 3 ‘Anil’ 69
is the primary key and C is the foreign key referencing
A with ON DELETE CASCADE.
Table 5 Reservation
A C Pid Class Tid
2 4 0 AC 8200
3 4 1 AC 8201
4 3 2 SC 8201
5 2 5 AC 8203
7 2 1 SC 8204
9 5 3 AC 8202
6 4
What pid’s are returned by the following SQL query for
What is the set of all tuples that must be additionally the above instance of the tables?
deleted to preserve referential integrity when the tuple SELECT pid
(2, 4) is deleted?
FROM Reservation
(A) (5, 2),(7, 2) (B) (5, 2), (7, 2),(9, 5)
(C) (5, 2),(9, 5) (D) (2, 4), (7, 2) WHERE class = ‘AC’ AND
10. Consider the following SQL query EXISTS (SELECT *
SELECT DISTINCT a1, a2, a3 … an FROM passenger
FROM R1, R2 … Rm WHERE age > 65 AND
WHERE P [Link] = [Link])
 Chapter 1 • ER Model and Relational Model | 4.17

(A) 0, 1 (B) 1, 3 (A) The above query displays DA and gross for all
(C) 1, 5 (D) 0, 3 those employees whose basic is ≥ 2000
13. Given {customer} is a candidate key, [customer name, (B) The above query displays DA and gross for all em-
customer street} is another candidate key then ployees whose basic is less than 2000
(A) {customer id, customer name} is also a candidate (C) The above query displays DA as well as gross for
key. all those employees whose basic is >2000
(B) {customer id, customer street} is also a candidate (D) Above all
key. 17. Which of the following query transformations is correct?
(C) {customer id, customer name, customer street} is R1 and R2 are relations C1, C2 are selection conditions
also a candidate key. and A1 and A2 are attributes of R1
(D) None (A) σC1(σC1(R1))→σC2(σC2(R1))
Common data for questions 14 and 15: Consider the fol- (B) σC1(σA1(R1))→σA1(σC1(R1))
lowing diagram, (C) pA2(pA(R1))→pA(pA2(R1))
(D) All the above
X1 X2 X3 18. Consider the following query select distinct a1, a2, …an
from r1, r2 . . . rm where P for an arbitrary predicate P,
this query is equivalent to which of the following rela-
X
tional algebra expressions:
(A) π σ p ( r1 × r2 × ... × rm )
a1 ... an
R1
(B) π σ p ( r1 × r2 × r3 ×…. × rm )
a1 ... an
Y1 Z1
(C) σ π p ( r1 × r2 × ... × rm )
a1 ... an
Y R1 Z
(D) σ π p ( r1 × r2 ×…× rm )
Y2 Z1 a1 ... an

19. The relational algebra expression equivalent to the fol-

14. The minimum number of tables needed to represent X, lowing tuple calculus expression
Y, Z, R1, R2 is {a} a ∈ r ^ (a[A] = 10 ^ a[B] = 20) is
(A) 2 (B) 3 (A) s(A = 10 r B = 20)r
(C) 4 (D) 5 (B) s(A = 10 ) (r) ∪ s(B = 20) (r)
15. Which of the following is a correct attribute set for (C) s(A = 10 ) (r) ∩ s(B = 20) (r)
one of the tables for the correct answer to the above (D) s(A = 10 ) (r) – s(B = 20) (r)
questions? 20. Which of the following is/are wrong?
(A) {X1, X2, X3, Y1} (B) {X1, Y1, Z1, Z2} (A) An SQL query automatically eliminates dupli-
(C) {X1, Y1, Z1} (D) {M1, Y1} cates.
16. UPDATE account SET (B) An SQL query will not work if there are no in-
dexes on the relations.
DA = basic * .2, (C) SQL permits attribute names to be repeated in the
GROSS = basic * 1.3, same relation
Where basic > 2000; (D) All the above

Practice Problems 2 2. The example of derived attribute is

Directions for questions 1 to 20: Select the correct alterna- (A) Name if age is given as other attribute
tive from the given choices. (B) Age if date_of_birth is given as other attribute
(C) Both (A) and (B)
1. If ABCDE are the attributes of a table and ABCD is a (D) None
super key and ABC is also super key then
3. The weak entity set is represented by
(A) A B C must be candidate key
(A) box
(B) A B C cannot be super key (B) ellipse
(C) A B C cannot be candidate key (C) diamond
(D) A B C may be candidate key (D) double outlined box
4.18 | Unit 4 • Databases

4. In entity relationship diagram double lines indicate (C) query which involves a Cartesian product and a
(A) Cardinality projection
(B) Relationship (D) None
(C) Partial participation 12. The number of entities participating in the relationship
(D) Total participation is known as
5. An edge between an entity set and a binary relationship (A) maximum cardinality (B) composite identifiers
set can have an associated minimum and maximum (C) degree (D) None
cardinality, shown in the form 1… h where 1 is the 13 A minimum cardinality of 0 specifies
minimum and h is the maximum cardinality A mini- (A) non-participation
mum value 1 indicates: (B) partial participation
(A) total participation (B) partial participation (C) total participation
(C) double participation (D) no participation (D) zero participation
6. Let R be a relation schema. If we say that a subset k
14. What is not true about weak entity?
of R is a super key for R, we are restricting R, we are
(A) They do not have key attributes.
restricting consideration to relations r(R)in which no
(B) They are the examples of existence dependency.
two district tuples have the same value on all attributes
(C) Every existence dependency results in a weak entity
in K. That is if t1 and t2 are in r and t1 ≠ t2
(D) Weak entity will have always discriminator attributes
(A) t1[k] = 2t2[K] (B) t2[K] = 2t1[k]
(C) t1[k] = t2[k] (D) t1[k] ≠ t2[k] 15. Which one is the fundamental operation in the rela-
tional algebra?
7. Which one is correct?
(A) Natural join (B) Division
(A) Primary key ⊂ Super key ⊂ Candidate key
(C) Set intersection (D) Cartesian product
(B) Candidate key ⊂ Super key ⊂ Primary key
(C) Primary key ⊂ Candidate key ⊂ Super key 16. For the given tables
(D) Super key ⊂ Primary key ⊂ Candidate key
A B
8. If we have relations r1(R1) and r2(R2), then r1 (r2 is a X Y Y
relation whose schema is the
a1 b1 b1
(A) concatenation (B) union
(C) intersection (D) None a2 b1 b2
a1 b2
9. Match the following:
a2 b2
I Empid 1 Multivalued
II Name 2 Derived
A ÷ B will return
III Age 3 Composite (A) a1, a2 (B) a1
IV Contact No. 4 Simple (C) a2 (D) None
(A) I – 4, II – 3, III – 2, Iv – 1 17. The number of tuples selected in the above answer is
(B) I – 3, II – 2, III – 4, Iv – 1 (A) 2 (B) 1
(C) I – 2, II – 1, III – 4, Iv – 3 (C) 0 (D) 4
(D) I – 1, II – 3, III – 2, IV – 4
Common data for questions 18 and 19: Consider the fol-
10. Match the following: lowing schema of a relational database.
I Double-lined ellipse 1 Multivalued attribute Emp (empno, name, add)
II Double line 2 Total participation Project (Pno, Prame)
III Double-lined box 3 Weak entity set Work on (empno, Pno)
IV Dashed ellipse 4 Derived attribute Part (partno, Pname, qty, size)
(A) I – 1, II – 2, III – 3, IV – 4 Use (empno, pno, partno, no)
(B) I – 2, II – 3, III – 4, IV – 1 18. ((name(emp) ( (name(emp ⋈ workon) displays
(C) I – 3, II – 4, III – 2, IV – 2 (i) The names of the employees who are not working
(D) I – 4, II – 3, III – 2, IV –1 in any project
11. The natural join is a (ii) The names of the employees who were working in
(A) binary operation that allows us to combine certain every project.
selections and a Cartesian product into one operation (A) Only (i) (B) Only (ii)
(B) unary operations that allows only Cartesian product (C) Both (A) and (B) (D) None
 Chapter 1 • ER Model and Relational Model | 4.19

19. List the partno and names of the parts used in both the 20. The following query shows. SELECT job-status, sum
projects DBMS & MIS: (basic – salary) AVG (basic – salary) from employees
(A) spartno, pname,(part ⋈ (ppartno (spname = “DBMS”(project) ⋈ group by job – status.
use).
∩ ppartno (spname = “MIS”(project) ⋈ use)) (i) It shows job status, sum, AVG of all data
(B) (partno, pname(part ⋈ ((partno ((pname = (ii) It shows job status, Sum, AVG, with group by
“DBMS”(project ⋈ use) ((partno(spname = clause in use.
“MIS”(project) ⋈ use))) (A) only (i)
(C) ppartno, pname(part ⋈ (spartno (spname = “DBMS”(project ⋈ (B) only (ii)
use)
( (partno ((pname = “MIS”(project) ⋈ use))) (C) both (A) and (B)
(D) None (D) None

Previous Years’ Questions

1. Let E1 and E2 be two entities in an E/R diagram, with
M1 M 2 M3 P1 P2 N1 N2
simple single-valued attributes. R1 and R2 are two
relationships between E1 and E2, where R1 is one-to-
many and R2 is many-to-many. R1 and R2 do not have M R1 M R2 N
any attributes of their own. What is the minimum
number of tables required to represent this situation 4. The minimum number of tables needed to represent
in the relational model? [2005] M, N, P, R1, R2 is? [2008]
(A) 2 (B) 3 (A) 2 (B) 3
(C) 4 (D) 5 (C) 4 (D) 5
2. The following table has two attributes A and C where 5. Which of the following is a correct attribute set for
A is the primary key and C is the foreign key referenc- one of the tables for the correct answer to the above
ing A with on-delete cascade. question?[2008]
(A) {M1, M2, M3, P1} (B) {M1, P1, N1, N2}
A C (C) {M1, P1, N1} (D) {M1, P1}
2 4 6. Consider a relational table with a single record for
3 4 each registered student with the following attributes.
4 3 1.  Registration_Num: Unique registration number
of each registered student
5 2
2. UID: Unique identity number, unique at the
7 2 national level for each citizen
9 5 3.  BankAccount_Num: Unique account number at
6 4 the bank. A student can have multiple accounts or
joint accounts. This attribute stores the primary
The set of all tuples that must be additionally deleted account number
to preserve referential integrity when the tuple (2, 4) 4. Name: Name of the student
is deleted is: [2005] 5. Hostel_Room: Room number of the hostel
(A) (3, 4) and (6, 4)
(B) (5, 2) and (7, 2) Which of the following options is incorrect? [2011]
(C) (5, 2), (7, 2) and (9, 5) (A) BankAccount_Num is a candidate key
(D) (3, 4), (4, 3) and (6, 4) (B) Registration_Num can be a primary key
(C) UID is a candidate key if all students are from
3. Which of the following tuple relational calculus the same country
expression(s) is/are equivalent to ∀t ∈ r (P(t))? (D) If S is a super key such that S ∩ UID is NULL
I. ¬ ∃t ∈ r (P(t)) then S ∪ UID is also super key.
II. ∃t ∉ r (P(t)) 7. Given the basic ER and relational models, which of
III. ¬ ∃t ∈ r (¬P(t)) the following is incorrect?[2012]
IV. ∃t ∈ r (¬P(t)) [2008] (A) An attribute of an entity can have more than one value
(A) I only (B) II only (B) An attribute of an entity can be composite
(C) III only (D) III and IV only (C) In a row of a relational table, an attribute can
have more than one value
Common data for questions 4 and 5: Consider the fol- (D) In a row of a relational table, an attribute can
lowing ER diagram: have exactly one value or a NULL value
4.20 | Unit 4 • Databases

8. An ER model of a database consists of entity types A set E2. Assume that E1 and E2 participate totally in
and B. These are connected by a relationship R which R and that the cardinality of E1 is greater than the
does not have its own attribute, Under which one of cardinality of E2.
the following conditions, can the relational table for R Which one of the following is true about R?[2018]
be merged with that of A?[2017]
(A) Every entity in E1 is associated with exactly one
(A) Relationship R is one-to-many and the participa-
entity in E2.
tion of A in R is total.
(B) Some entity in E1 is associated with more than
(B) Relationship R is one-to-many and the participa-
one entity in E2.
tion of A in R is partial.
(C) Every entity in E2 is associated with exactly one
(C) Relationship R is many-to-one and the participa-
entity in E1.
tion of A in R is total.
(D) Every entity in E2 is associated with at most one
(D) Relationship R is many-to-one and the participa-
entity in E1.
tion of A in R is partial.
9. In an Entity-Relationship (ER) model, suppose R is a
many-to-one relationship from entity set E1 to entity

Answer Keys
Exercises
Practice Problems 1
1. (i) B  (ii) A  (iii) A 2. A 3. B 4. D 5. D 6. D 7. B 8. B
9. B 10. A 11. A 12. B 13. D 14. A 15. A 16. C 17. B 18. B
19. C 20. D

Practice Problems 2
1. D 2. B 3. C 4. A 5. A 6. D 7. C 8. A 9. A 10. A
11. A 12. C 13. C 14. A 15. D 16. A 17. A 18. A 19. C 20. B

Previous Years’ Questions

1. B 2. C 3. D 4. B 5. A 6. A 7. C 8. C 9. A
 Chapter 2
Structured Query Language

LEARNING OBJECTIVES

 Relational algebra  Correlated nested queries

 Select operator  Relational calculus
 Project operator  Tuple relational calculus
 Set operators  Tuple relational calculus
 Union compatible relations  DML
 Union operation  Super key
 Aggregate operators  SQL commands

RelaTional algeBRa Relational operations

1. A set of operators (unary or binary) that take relation instances
as arguments and return new relations. Unary operators Binary operators
2. Gives a procedural method of specifying a retrieval query 1. Select 1. Union
2. Project 2. Intersection
3. Forms the core component of a relational query engine 3. Difference
4. SQL queries are internally translated into RA expressions 4. Join
5. Provides a framework for query optimization 5. Divide
6. Cartesian product

SQL query Select Operator (s)

Select operator is an unary operator. It can be used to select those
tuples of a relation that satisfy a given condition.
Relational algebra expression
Notation: sθ (r)
s : Select operator(read as sigma)
Query expression plan
θ : Selection condition
r : Relation name
Executable code Result is a relation with the same scheme as r consisting of the
tuples in r that satisfy condition θ
Figure 1 Role of relational algebra in DBMS: Syntax: scondition (relation)
Example:
Relational Operations Table 2.1 Person

A collection of simple ‘low-level’ operations used to manipulate Id Name Address Hobby

relations. 112 John 12, SP Road Stamp collection

1. It provides a procedural way to query a database. 113 John 12, SP Road Coin collection
2. Input is one (or) more relations. 114 Mary 16, SP Road Painting
3. Output is one relation. 115 Brat 18, GP Road Stamp collection
4.22 | Unit 4 • Databases

σ Hobby = ‘stamp. Collection’(person) In the output table, John name has appeared once, project
The above given statement displays all tuples (or) records operation eliminated duplicates.
with hobby ‘stamp collection’. 2. pName, address (person)
Output: Output:
Id Name Address Hobby Name Address

112 John 12, SP Road Stamp collection John 12, SP Road

115 Brat 18, GP Road Stamp collection Mary 16, SP Road
Bart 18,GP Road
Selection condition can use following operators:
<, ≤, >, ≥, =, ≠ Expressions:
1. <attribute> operator <attribute>
pid,name (s hobby = ‘stamp collection’ OR Hobby= ‘coin collection’ (person))
2. <attribute> operator <constant> Output:
Example: Salary ≥ 1000 Id Name
3. <Condition> AND/OR <condition> 112 John
Example: (Experience > 3) AND (Age < 58) 115 Bart
4. NOT <condition>
The above given relational algebra expression gives Ids,
Selection operation examples: names of a person whose hobby is either stamp collection
1. σ Id > 112 OR Hobby = ‘paint’ (person) (or) coin collection.
It displays the tuples whose ID > 112 or Hobby is paint
2. σ Id > 112 AND Id < 115 (person) Set Operators
It displays tuples whose ID is greater than 112 and less Union (∪), Intersection (∩), set difference (–) are called
than 115 set operators. Result of combining two relations with a set
3. σ NOT (hobby = ‘paint’) (person) operator is a relation ⇒ all its elements must be tuples hav-
ing same structure. Hence scope of set operations is limited
It displays tuples whose hobby is not paint
to union compatible relations.
4. σ Hobby ≠ ‘paint’ (person)
It displays tuples whose hobby is not paint, displays all
tuples other than hobby paint. Union Compatible Relations
Selection operator: Produces table containing subset Two relations are union compatible if
of rows of argument table which satisfies condition. 1. Both have same number of columns
2. Names of attributes are same
3. Corresponding fields have same type
Project Operator (p) 4. Attributes with the same name in both relations have
The project operator is unary operator. It can be used to same domain.
keep only the required attributes of a relation instance and 5. Union compatible relations can be combined using
throw away others. Union, Intersection, and set difference.
Notation: pA2, A2, … Ak(r) Where A1, A2, … AK is a list L of Example:
desired attributes in the scheme of r. Consider the given tables.
Result = { ( V1, V2, … VK)/Vi ∈ DOM (Ai), 1< i < k and Person (SSN, Name, Address, Hobby)
there is some tuple t in r, such that t.A1 = v1, t.A2 Professor (Id, Name, office, phone)
= v2, … [Link] = VK} person and professor tables are not union compatible.
  p Attribute List (Relation)
Take table 2.1 as reference. Union
1. pName (person) The result of union will be a set consisting of all tuples
appearing in either or both of the given relations. Relations
Output:
cannot contain a mixture of different kinds of tuples, they
Name
must be ‘tuple – homogeneous’. The union in the relational
John
algebra is not the completely general mathematical union;
Mary
rather, it is a special kind of union, in which we require the
Bart
two input relations to be of the same type.
 Chapter 2 • Structured Query Language | 4.23

The general definition of relational union operator: Difference

Given are two relations ‘a’ and ‘b’ of the same type. The Like union and intersection, the relational difference opera-
union of those two relations, a union b, is a relation of the tor also requires its operands to be of the same type. Given
same type, with body consisting of all tuples ‘t’ such that ‘t’ are two relations ‘a’ and ‘b’ of the same type, Then, the dif-
appears in a or b or both. ference between those two relations, ‘a’ MINUS ‘b’ (in that
* Union operation eliminates duplicates. order), is a relation of the same type, with body consisting
of all types t such that t appears in a and not b.
Here is a different but equivalent definition:
Given are two relations ‘a’ and ‘b’ of the same type. The 1. MINUS has a directionality to it, just as subtraction
union of those two relations, a union b, is a relation of the does in ordinary arithmetic (e.g., ‘6 – 3’ and ‘3 – 6’ are
same type, with body consisting of all tuples t such that t is not the same thing)
equal to (i.e., is a duplicate of) some tuple in a or b or both. 2. Redundant duplicate rows are always eliminated from
the result of UNION, INTERSECTION, EXCEPT
Union Operation (U) operations.
3. SQL also provides the qualified variants UNION ALL,
When union operation is applied on two tables it gives all INTERSECT ALL and EXCEPT ALL, where dupli-
the tuples in both without Repetition. cates are retained
Example: Set difference operation returns the tuples in the first
table which are not matching with the tuples of other table.
Table 2 Result of union operation

Roll. no. Name Semester Percentage Table 4 Result of R – S

22 Arun 7 45% Roll
Name Semester Percentage
R 31 Bindu 6 55% R–S= no.
58 Sita 5 35% 22 Arun 7 45%

Roll no. Name Semester Percentage Table 5 Result of S – R

S 28 Suresh 4 65% S–R= Roll no. Name Semester Percentage
31 Bindu 6 55% 28 Suresh 4 65%
44 Pinky 4 75% 44 Pinky 4 75%
58 Sita 5 35%
* R – S ≠ S –R (both are different)
Roll no. Name Semester Percentage
22 Arun 7 45% Example:
R∪S
31 Bindu 6 55% A
58 Sita 5 35% Supplier number Supplier name Status City
44 Pinky 4 75% SN1 MAHESH 40 HYDERABAD
28 Sita 5 35% SN3 SURESH 40 HYDERABAD

Intersection B

Like union, Intersection operator requires its operands to Supplier number Supplier number Status City
be of the same type. Given are two relations a and b of the SN3 SURESH 40 HYDERABAD
same type, then, the intersection of those two relations, ‘a’ SN4 RAMESH 30 CHENNAI
INTERSECT ‘b’, is a relation of the same type, with body
consisting of all tuples t such that t appears in both ‘a’ and UNION (A ∪ B)
‘b’.
Supplier number Supplier name Status City
Intersection operation returns tuples which are common
SN1 MAHESH 40 HYDERABAD
to both tables
SN3 SURESH 40 HYDERABAD
Table 3 Result of intersection operation SN4 RAMESH 30 CHENNAI

R∩S= Roll no. Name Semester Percentage

INTERSECTION (A ∩ B)
31 Bindu 6 55%
58 Sita 5 35% Supplier number Supplier name Status City
SN3 SURESH 40 HYDERABAD
4.24 | Unit 4 • Databases

DIFFERENCE (A – B) Aggregate Operators

Supplier name Supplier name Status City SQL Supports the usual aggregate operators COUNT,
SN1 MAHESH 40 HYDERABAD SUM, AVG, MAX, MIN, EVERY and ANY, but there are a
few SQL-specific points.
DIFFERENCE (B – A)
1. The argument can optionally be preceded by the key-
Supplier name Supplier name Status City word DISTINCT, for example SUM (DISTINCT
SN4 RAMESH 30 CHENNAI column -name) to indicate that duplicates are to be
eliminated before the aggregation is done. For MAX,
MIN, EVERY and ANY, however, DISTINCT has no
Cartesian Product effect and should not be specified.
The Cartesian product of two sets is the set of all ordered 2. The operator COUNT (*), for this DISTINCT is not
pairs such that in each pair, the first element comes from allowed, and is provided to count all rows in a table
the first set and the second element comes from second without any duplicate elimination.
set.
3. Any NULLS in the argument column are eliminated
The result consists of all the attributes from both of the
before the aggregation is done, regardless of whether
two input headings. We define the Cartesian product of two
DISTINCT is specified, except in the case of COUNT
relations ‘a’ and ‘b’, as
(*), where nulls behave as if they were values.
‘a’ times ‘b’, where a and b have no common attrib-
ute names (If we need to construct the Cartesian product 4. After NULLS if any have been eliminated, if what is
of two relations that do have any such common attribute left is an empty set, COUNT returns zero. The other
names, therefore, we must use the RENAME operator first operators return NULL.
to rename attributes appropriately). AVG, MIN, MAX, SUM, COUNT
The Cartesian product operation is also known as CROSS
These functions operate on the multiset of values of col-
PRODUCT. This is also a binary set operation, but the rela-
umn of a relation and returns a value.
tions on which it is applied need not to be union compatible.
This operation is used to combine tuples from two relations 1. Find the average account balance at the Perryridge
in a combinational fashion. branch.
Example: Solution: SELECT AVG (balance) FROM account
A B WHERE [Link] = ‘perryridge’
R X1 X2
X3 X4
2. Find the number of tuples in customer relation.

Solution: SELECT count (*) FROM customer

C D
3. Find the number of depositors for each branch.
S Y1 Y2
Y3 Y4 Solution: SELECT [Link], COUNT (distinct
customer-name) FROM depositor, account WHERE
depositor. account-no = account account-no GROUPBY
A B C D
branch-name.
R×S= X1 X2 Y1 Y2
X1 X2 Y3 Y4
X3 X4 Y1 Y2 Nested Queries
X3 X4 Y3 Y4 Some queries require that existing values in the database be
fetched and then used in a comparison condition.
Such queries can be conveniently formulated by using
Example: Transcript (StuId, coursecode, semester, grade)
nested queries, which are complete SELECT – FROM
Teaching (ProfId, coursecode, semester)
–WHERE blocks within the WHERE clause of another
pstuId,coursecode (Transcript) × pprofId,coursecode (Teaching) query. The other query is called the outer query.
The above expression returns
Table 6 Result of cross product In-Comparison Operator
Stu Id Course code Prof Id Course code The comparison operator IN, which compares a value ‘v’
... ... ... ... with a set of values ‘V’ and evaluates to TRUE if ‘v’ is one
of the elements in V.
 Chapter 2 • Structured Query Language | 4.25

Example: Consider the given database scheme and the 1. In co-related nested queries, the inner query depends
statement: on the outer query for its value.
2. Sub-query is executed repeatedly, once for each row
EMPLOYEE that is selected by the outer query.
FNAME INITIAL LNAME ENO DOB ADDRESS SALARY DNO 3. A correlated subquery is a sub query that contains a
reference to a table that also appears in the outer query.

DEPARTMENT
Example: Consider the following correlated nested query:
SELECT *
D NAME DNO MANAGER-NO FROM table1
WHERE col1 ≥ ALL
DEPARTMENT–LOCATIONS
(SELECT col1 FROM table2 WHERE table2. col2 =
table1. col2)
DNO D-LOCATION
1. The subquery contains reference to a column of table1,
even though the sub-queries FROM clause does not
PROJECT mention a table table1
2. SQL has to check outside the sub-query and find Table
PNAME PNO P-LOCATION DNO
1 in the outer query
3. Suppose that Table 1 contains a row where col1 = 3 and
col2 = 4 and Table 2 contains a row where col1 = 5 and
WORKS–ON
col2 = 4
ENO PNO HOURS 4. The expression

WHERE col1 ≥ All (SELECT col1

Example: Select distinct PNO from project where PNO FROM table2
IN (select PNO from project, department, employee where
P. DNO = D. DNO AND MANAGER. NO = ENO AND
3 ≥ 5 (false)
LNAME = ‘RAMYA’)
The first query selects. The project numbers that have a
‘Ramya’ involved as manager, while the second selects the (WHERE condition TRUE) Table1.
project numbers of projects that have a ‘Ramya’ involved col2 = table2. col2 4 = 4
as worker.
If a nested returns a single value, in such cases, it is per- So the expression as a whole is FALSE.
missible to use = instead of IN for the comparison operator. 5. It is evaluated from outside to inside
In general, the nested query will return a table, Which is
a set of multiset of tuples.
* SQL allows the use of tuples of values in comparisons by
Relational Calculus
placing them within parentheses. Relational calculus can define the information to be retrieved

Example: SELECT DISTINCT ENO FROM WORKS - 1. In this, there is no specific series of operations.
ON WHERE (PNO, HOURS) IN (SELECT PNO, HOURS 2. Relational algebra defines the sequence of operations.
FROM WORKS - ON WHERE ENO = 929). 3. Relational calculus is closer to how users would for-
mulate queries, in terms of information requirements,
This query will select the employee numbers of all rather than in terms of operations.
employees who work on the same (PROJECT, HOURS)
combination on some project a particular employee whose Relational Calculus
ENO = ‘929’ works on. In this example, the IN operator
compares the subtuple of values in parentheses (PNO,
HOURS) for each tuple in works on with the set of union- Tuple Relational Domain Relational
compatible tuples produced by the nested query. calculus (variables Calculus (variables
range over tuples) range over domain
Correlated nested queries: Nested queries can be evaluated attributes)
by executing the sub query (or) Inner query once and sub-
stituting the resulting value (or) values into the WHERE 4. Relational calculus is based on predicate logic, gives
clause of the outer query. the usual quantifiers to construct complex queries.
4.26 | Unit 4 • Databases

Tuple Relational Calculus Example: ∃ × ((X ∈ Boats) ∧ [Link]) = ‘Red’)

There exists a tuple X in the boats relation whose color
Example: Employee
is red.
E Id F Name L Name S alary (or)
201 John James 3000
∃ × ∈ Boats ([Link] = ‘Red’)
202 Brat Frank 2000 Examples:
203 Mary Jennifer 3000 1. Find all sailors with rating above 8.
204 Adam Borg 2000
Sid Sname Rating Age
205 Smith Joyce 1000
28 Yuppy 9 35
Query 1: Display the employees whose salary is above 2000. Sailors: 35 Rubber 8 55
{E | ∃ E ∈ Employee([Link] > 2000)} 44 grove 5 35
58 rusty 10 35
Output:
E Id F Name L Name Salary Solution: {s|s ∈ sailors ∧ s. rating > 8}
201 John James 3000 Output
203 Mary Jennifer 3000
Sid Sname Rating Age
Query 2: Display the employee Ids whose salary is above R= 28 yuppy 9 35
1000 and below 3000. 58 rusty 10 35
{P | ∃ E ∈ Employee (([Link] > 1000 ∧ [Link] <
3000) ∧ [Link] = [Link])} 2. Find names and ages of sailors with rating > 8.
P is a table, in which EIds are stored, from tuples which
satisfies the given condition. Solution:
{R | ∃ S ∈ sailors ([Link] > 8 ∧ [Link] =
[Link] ∧ [Link] = [Link])
Output:
Tuple Relational Calculus

sname age
A non-procedural language, where each query is of the
yuppy 35
form {t| p(t)}. It is a set of all tuples t such that predicate p
rusty 35
is true for t, t is a tuple variable, t [A] denotes the value of
tuple ‘t’ on attribute A.
{T| p (T)} Join Operation in Tuple Relational Calculus
T is a tuple and P (T) denotes a formula in which tuple vari- Examples:
able T appears. 3. Find sailors rated > 7 who have reserved boat = 103.
1. ∀ × (P(X)) Solution: {S | S ∈ sailors ∧ [Link] > 7 ∧ ∃ R (R ∈ reserves
∀ is called the universal or ‘for all’ quantifier because ∧ [Link] = [Link] ∧ [Link] = 103)}
every tuple in ‘the universe of’ tuples must make F 4. Find sailors rated > 7 who have reserved a red boat.
true to make the quantified formula true.
Only true if p(X) is true for every X in the universe. Solution: {S | S ∈ sailors ∧ [Link] > 7 ∧ ∃ R (R ∈ reserves ∧
[Link] = [Link] ∧ ∃ B( Boats ∧ [Link] = [Link] ∧ [Link] = ‘Red’))}
Example: ∀ × ([Link] = ‘Red’)
means everything that exists is red.
Division Operation in Tuple
Example: ∀ × ((x ∈ Boats) ⇒ (X. color = ‘Red’)) Relational Calculus
‘⇒’ is a logical implication. a ⇒ b means that if a is Examples
true, b must be true 1. Find sailors who have reserved all boats.
(or)
∃ × ∈ Boats ([Link] = ‘Red’) Solution: {S | S ∈ sailors ∧ ∀ B ∈ boats (∃ R ∈ reserves
For every ‘x’ in the boats relation, the color must be ([Link] = [Link] ∧ [Link] = [Link]))}
red.
Domain Relational Calculus
2. ∃ × (P(X))
1. Tuple relational and domain relational are semantically
∃ is called the existential or ‘there exists’ quantifier
similar.
because any tuple that exists in ‘the universe of’ tuples
2. In TRC, tuples share an equal status as variables, and
may take F true, to make the quantified formula true.
field referencing can be used to select tuple parts.
 Chapter 2 • Structured Query Language | 4.27

3. In DRC formed variables are explicit. Features

4. DRC query has the following form. 1. Strong data protection
{<x1, x2, … xn > /P(<x1, x2, … , xn>} 2. Robust transactional support
Result included all tuples <x1, x2, … xn > 3. High performance
That make the formula p(<x1, x2, … xn>) true. 4. High availability
5. Formula given in DRC is recursively defined. First start 5. Security and flexibility to run anything
with simple atomic formula and expand the formulas 6. Easy to manage
by using the logical connectives. 7. User friendly
6. A variable that is not bound is free.
7. The variable X1, X2, …, Xn that appear in the left side of General Structure
‘/’ must be the only free variable in the formula p(…). SELECT ... FROM ... WHERE
Example: Consider the employee table given in the above SQL is divided into two languages
Example. 1. DML (data manipulation language)
The use of quantifiers ∃ x and ∀ x in a formula is said to SELECT: Extracts data from a database table.
bind x UPDATE: Updates data in a database table.
Query 1: Display the Employees whose salary is above DELETE: Deletes data from a database table.
2000? INSERT INTO: Inserts new data into database table.
{<I, F, L, S> / <I, F, L, S> ∈ Employee ∧ S > 2000} 2. DDL (data definition language)
Query 2: Display the EIds of Employees, whose salary is CREATE TABLE - creates a new database table.
above 1000 and below 3000? ALTER TABLE - Alters a database table.
{<I> / ∃F, L, S(<I, F, L, S > ∈ Employee ∧ (S > 1000 ∧ S < 3000))} DROP TABLE - deletes a database table.
CREATE INDEX - Creates an index (search key).
SQL (Structured Query Language) DROP INDEX - Deletes an index.
RENAME – Changes the name of the table.
When a user wants to get some information from a database
file, he/she can issue a query. A query is a user-request to Types of keys:
retrieve data (or) information with a certain condition. SQL 1. Candidate key
is a query language that allows user to specify the condi- 2. Primary key
tions (instead of algorithms) 3. Super key
4. Foreign key
Concept of SQL 5. Composite primary key
The user specifies a certain condition. The program will go In relational database, ‘keys’ play a major role. Keys are
through all the records in the database file and select those used to establish and identify relation between relations (or)
records that satisfy the condition. The result of the query tables.
will be stored in the form of a table. Keys are used to ensure that each record within a table
can be uniquely identified by combining one or more fields
Features of SQL (or) column headers within a table.
1. SQL is a language of database. It includes database Candidate key: A candidate key is a column or set of col-
creation, deletion, fetching rows and modifying rows. umns in a table that contains unique values, with these we
2. SQL is a structured query language for storing, manip- can uniquely identify any database record without referring
ulating and retrieving data stored in relational database. to any other columns data.
3. It allows users to describe the data. Each table may have one or more candidate keys, among
4. It allows users to create and drop database and tables. the available candidate keys, one key is preserved for pri-
5. It allows users to create view, functions in a database. mary key.
6. Allows users to set permissions on tables and views. A candidate key is a subset of a super key.
7. The standard SQL commands to interact with rela- Example: Student
tional database are CREATE, SELECT, UPDATE, First
INSERT, DROP and DELETE. StudentId Last name Course Id
name
8. The commands can be classified as follows: CS00345 Jim Black C2
•• Data query language: SELECT – It retrieves par- CS00254 Carry Norris C1
ticular rows which satisfies the given condition. CS00349 Peter Murray C1
•• Data definition language: CREATE, ALTER, DROP. CS00196 John Mc Cloud C3
•• Data manipulation language: INSERT, UPDATE, CS00489 Brat Holland C4
DELETE CS00553 Mary Smith C5
4.28 | Unit 4 • Databases

In the above table, we have studentId that uniquely identifies Foreign key: A foreign key is a column or group of columns
the students in a student table. This would be a candidate in a relational database table that provides connectivity
key. between data in two tables.
In the same table, we have student’s first name and last 1. The majority of tables in a relational database system
name, which are also candidate keys. adhere to the concept of foreign key.
1. If we combine first name and last name then also it 2. In complex databases, data must be added across mul-
becomes a candidate key. tiple tables, thus the link or connectivity has to be
2. Candidate key must (have) maintained among the tables.
•• Unique values 3. The concept of Referential Integrity constraint is
•• No null values derived from Foreign key.
•• Minimum number of fields to ensure uniqueness. Example: Emp
•• Uniquely identify each record in the table.
EId EName Dept – No
3. The candidate keys which are not selected for primary
key are known as secondary keys or alternative keys.
Dept
Primary key: A primary key is a candidate key that is most Dept-No DName
suitable (or) appropriate to become main key of the table.
1. It is a special relational database table column ((or)
In the above specified tables, Dept-No is common to both
combination of columns)
the tables, In Dept table it is called as primary key and in
2. Primary key main features are
Emp table it is called as foreign key.
•• It must contain a unique value for each row of data.
These two tables are connected with the help of
•• It cannot contain null values.
‘Dept-No’ field
Example: We can choose primary key as studentId which 1. For any column acting as a foreign key, a correspond-
is mentioned in the table given in above example. ing value should exist in the link (or) connecting table.
Composite primary key: A key that consists of two or more 2. While inserting data and removing data from the for-
attributes that uniquely identify an entity is called compos- eign key column, a small incorrect insertion or dele-
ite key or composite primary key. tion destroys the relationship between the two tables.

Example: Customer
SQL Commands
Cust-Id Order-Id Sale-details
SELECT statement
C1 O–2 Sold
The most commonly used SQL command is SELECT state-
C1 O–3 Sold
ment. The SQL SELECT statement is used to query or retrieve
C2 O–2 Sold data from a table in the database. A query may retrieve infor-
C2 O–3 Sold mation from specified columns or from all of the columns in
the table. To create a simple SQL SELECT statement, you
Composite primary key is {cust-Id, order-Id} must specify the column(s) names and the table name.
Super key: A super key is a combination of attributes that Syntax: SELECT column-name (s) from table name
can be uniquely used to identify a database record. A table
can have any number of super keys. Example: Persons
Lastname Firstname Address City
1. Candidate key is a special subset of super keys.
Hansen Ola SpRoad,-20 Hyd
Example: Customer
Svendson Tove GPRoad,-18 Secbad
Customer name Customer Id SSN Address DOB Petterson Kari RpRoad,-19 Delhi

1. SELECT lastname FROM persons

Assume that we can guarantee uniqueness only for SSN
field, then the following are some of the super keys possible. Output:
Lastname
1. {Name, SSN, DOB}
Hansen
2. {ID, Name, SSN}
Svendson
In a set of attributes, there must be at least one key (could
Petterson
be primary key or candidate key)
 Chapter 2 • Structured Query Language | 4.29

2. SELECT lastname, firstname FROM persons BETWEEN - Between an inclusive range.

Output: LIKE - Search for a pattern
Lastname Firstname Example: Persons
Hansen Ola
Lastname Firstname Address City Year
Svendson Tove
Hansen Ola SPRoad, 16 Hyd 1956
Petterson Kari
Svendson Tiva GPRoad, 18 Sec 1977
Smith Ole RPRoad, 19 Hyd 1986
DISTINCT statement
Petterson Kari SPRoad, 17 Sec 1985
Returns distinct values. It eliminates duplicate values.
Syntax: Select DISTINCT column_name (s) from table-name 1. SELECT * FROM persons
Example: Orders Output: It displays the entire table
Company [Link] 2. SELECT * FROM persons WHERE city = ‘Hyd’
IBM 3412

Output:
DELL 5614
WIPRO 4412 Lastname Firstname Address City Year

DELL 4413 Hansen Ola SPRoad, 16 Hyd 1956

Smith Ole RPRoad, 19 Hyd 1986
1. SELECT company FROM orders
Output: LIKE condition
Company The LIKE operator is used to list all rows in a table whose
IBM column values match a specified pattern. It is useful when
DELL you want to search rows to match a specific pattern, or when
WIPRO you do not know the entire value. For this purpose, we use a
DELL wildcard character ‘%’.
2. SELECT DISTINCT company FROM orders The LIKE condition is used to specify a search for a pat-
tern in a column.
Company A ‘%’ sign can be used to define wildcards (missing let-
IBM ters in the pattern) both before and after the pattern.
DELL Syntax: SELECT column FROM table WHERE column
WIPRO LIKE pattern
1. SELECT * FROM persons WHERE Firstname LIKE
WHERE statement ‘O%’
The WHERE clause is used when you want to retrieve spe-
cific information from a table excluding other irrelevant Solution: SQL statement will return persons with first
data. By using WHERE clause, we can restrict the data that names that start with a letter ‘O’
is retrieved. The condition provided in the WHERE clause Output:
filters the rows retrieved from the table and gives only those Lastname Firstname Address City Year
rows which were expected. WHERE clause can be used
Hansen Ola SPRoad, 16 Hyd 1956
along with SELECT, DELETE, UPDATE statements.
The WHERE clause is used to specify a selection condi- Smith Ole RPRoad, 19 Hyd 1986
tion. All conditions are specified in this clause.
2. SELECT * FROM persons WHERE Firstname LIKE
Syntax: SELECT column FROM table WHERE column ‘%a’
operator value. Solution: SQL statement will return persons whose first
Operates used in where clause: name ends with letter ‘a’.
= Output:
< > (not equal) (or) ! =
Last name First name Address City Year
>
< Hansen Ola SPRoad, 16 Hyd 1956
>= Svendson Tiva GPRoad, 18
Sec.
1977
<= bad
4.30 | Unit 4 • Databases

3. SELECT * FROM persons WHERE firstname LIKE UPDATE

‘%la%’ The update statement is used to modify the data in a table.
Solution: SQL statement returns persons whose firstname Syntax: UPDATE table_name
contains ‘la’. The word sequence ‘la’ may come at any place SET Column_name = new_value
in the word. WHERE column_name = some_value.
Output: 1. Add a first name (Nine) to the person whose last name
Last name First Name Address City Year is ‘Rasmussen’?
Hansen Ola SPRoad, 16 Hyd 1956 Solution: UPDATE person SET Firstname = ‘Nine’
WHERE Lastname = ‘Rasmussen’
String operations 2. Change the address and add the name of the city as
1. ‘%idge%’matches ‘Rockridge’, ‘Ridgeway’, ‘Perryridge’. Hyd of a person with last name Rasmussen?
2. ‘_____’ matches a string of three characters.
Solution: UPDATE person
3. ‘_____%’ matches a string of at least rhree characters.
SET Address = ‘street 12’,
city = ‘Hyd’
INSERT INTO statement WHERE Lastname = ‘Rasmussen’
This statement is used to insert new rows into a table. While
inserting a row, if you are adding values for all the columns
of the table you need not specify the column(s) name in the DELETE statement
SQL query. But you need to make sure the order of the val- The DELETE statement is used to delete rows from a table.
ues is in the same order as the columns in the table. When The WHERE clause in the SQL delete command is optional,
adding a row, only the characters or data values should be and it identifies the rows in the column that gets deleted. If
enclosed with single quotes and ensure the data type of the you do not include the WHERE clause, all the rows in the
value and the column matches. One can specify the columns table will be deleted.
for which you want to insert data Syntax: DELETE FROM table_name
Syntax: INSERT INTO table-name (column1, column2 . . .) WHERE column_name = some_value
VALUES (value 1, value2 . . .) 1. Delete all rows?
1. INSERT INTO persons VALUES (‘Hetland’, ‘Camilla’, Solution: DELETE * FROM table_name
‘HPRoad 20’, ‘Hyd’)
Output:
Cartesian product
Last name First Name Address City
The Cartesian product of two sets is the set of all ordered
Hansen Ola S.P Road 16 Hyd pairs of elements such that the first element in each pair
Svesdon Tiva GP Road 18 Secbad belongs to the first set and the second element in each pair
Smith Ole RP Road 19 Hyd belongs to the second set. It is denoted by cross(X).
Petterson Kari SP Road 17 Secbad
For example, given two sets:
Hetlan Camilla HPRoad, 20 Hyd
S1 = {1, 2, 3} and S2 = {4, 5, 6}
2. Insert data into specified columns The Cartesian product S1 × S2 is the set
INSERT INTO persons (Lastname, Address) VALUES {(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5),
(‘Rasmussen’, ‘street 67’) (3, 6)}
Output:
Example:
Last name First Name Address City
Female Male
Hansen Ola SP Road 16 Hyd
Name Job Name Job
Svesdon .Tiva GP Road 18 Secbad
Komal Clerk Rohit Clerk
Smith Ole RP Road 19 Hyd
Ankita Sales Raju Sales
Petterson Kari SP Road 17 Secbad
Hetlan Camilla HP Road 20 Hyd Assume that the tables refer to male and female staff,
Rasmussen Street 67 respectively. Now, in order to obtain all possible inter-staff
marriages, the cartesian product can be taken.
 Chapter 2 • Structured Query Language | 4.31

Male-Female We may specify ‘desc’ for descending order (or) ‘asc’ for
ascending order. - ‘asc’ is default.
Female name Female job Male name Male job
Komal Clerk Rohit Clerk Example: ORDERBY customer-name desc.
Komal Clerk Raju Sales
Join (⋈)
Ankita Sales Rohit Clerk SQL Join is used to get data from two (or) more tables,
Ankita Sales Raju Sales which appear as single table after joining.

Examples: 1. Join is used for combining columns from two or more

tables by using values common to both tables.
1. Find the Cartesian product of borrower and loan?
2. Self Join: A table can also join to itself is known as self
Solution: SELECT * FROM borrower, loan join. Types of JOIN
2. Find the name, loan-no, and loan amount of all cus- 1. INNER JOIN
tomers having a loan at the Perryridge branch? 2. OUTER JOIN
(i) LEFT OUTER JOIN
Solution: SELECT customer_name, borrower. loan_ (ii) RIGHT OUTER JOIN
number, amount FROM borrower, loan WHERE borrower. (iii) FULL OUTER JOIN
loan-no = Loan.loan_no AND branch_name = ‘perryridge’
1. INNER JOIN (or) EQUI JOIN
3. Find all loan numbers for loans made at the perryridge
branch with loan amount greater than 1200? It is a simple JOIN in which result is based on matching
tuple, depending on the equality condition specified in the
Solution: SELECT loan-no FROM loan WHERE branch. query.
name = ‘perryridge’ AND amount > 1200
Syntax: SELECT Column-names FROM table name1
Comparison operator INNER JOIN table name 2 WHERE table name 1. Column
name = table name [Link] – name.
Relation algebra includes six comparison operators (=, < >,
<, >, < =, > =). These are proposition forming operators on Example: Class
terms. For example, x < > 0 asserts that x is not equal to 0. SID Name
It also includes three logical operators (AND, OR, NOT).
11 Ana
These are proposition forming operators on propositions.
12 Bala
Example: x > 0 and x < 8 13 Sudha
Comparison results can be combined using the logical con- 14 adam
nections AND, OR NOT
Info
1. Find the loan-no of those loans with amounts between
90,000 and 1,00,000? SID City
11 Bangalore
Solution: SELECT loan-no FORM loan WHERE amount
12 Delhi
BETWEEN 90,000 AND 1,00,000. SQL allows renewing
relations and attributes using ‘AS’ clause 13 Hyderabad

2. Find the name, loan-no and loan amount of all custom- SELECT *
ers, rename the column name loan-no as [Link]? FROM Class INNER JOIN Info
Solution: SELECT [Link], [Link] no AS WHERE [Link] = [Link]
[Link], amount FROM borrower, loan, WHERE borrower. Result:
loan-no = [Link]-no
SID Name SID City

Ordering of Tuples 11 Ana 11 Banglore

12 Bala 12 Delhi
It lists the tuples in alphabetical order.
13 Sudha 13 Hyderabad
Example: List in alphabetic order, the names of all customers
having a loan in Perryridge branch? NATURAL JOIN:
Solution: SELECT customer-name FROM borrower NATURAL JOIN is a type of INNER JOIN which is based
WHERE [Link] = ‘perryridge’ ORDERBY customer- on column having same name and same data type present in
name two tables on which join is performed.
4.32 | Unit 4 • Databases

Syntax: SELECT * Query:

FROM table-name1 NATURAL JOIN table-name 2 SELECT *
FROM Class1 RIGHT OUTER JOIN Info1
Example: Consider the tables class and Info, and the
ON([Link] = [Link])
following Query
SELECT * Result:
FROM   class NATURAL JOIN Info SID Name City
16 Arun Chennai
Result:
18 NULL Noida
SID Name City
11 Ana Bangalore FULL OUTER JOIN: The full outer Join returns the tuples
12 Bala Delhi with the matched data of two tables, remaining rows of both
13 Sudha Hyderabad
left table and Right table are also included.

Both tables being joined have SID column (same name and Example: Consider the tables class 1 and Info1
same data type), the tuples for which value of SID matches Query:
in both the tables, appear in the result. SELECT *
FROM class1 FULL OUER JOIN Info1
Dangling tuple: When NATURAL JOIN is performed on ON([Link] = [Link])
two tables, there would be some missing tuples in the result
Result:
of NATURAL JOIN
SID Name City
Those missing tuples are called Dangling tuples. In the
16 Arun Chennai
above example, the number of dangling tuples is 1 that is
17 Kamal NULL
14 Adam 18 NULL Noida
OUTER JOIN: Outer Join is based on both matched and ALTER command: ALTER command is used for altering the
unmatched data. table structure
LEFT OUTER JOIN: Left outer Join returns the tuples 1. It is used to add a new column to existing table.
available in the left side table with the matched data of 2 2. To rename existing column.
tables and null for the right tables column. 3. ALTER is used to drop a column.
Example: Consider the table’s class and Info 4. It is used to change data type of any column or modify
SELECT * its size.
FROM class LEFT OUTER JOIN Info Add new column: By using alter command, we can add a
ON([Link] = Info. SID) new column to the table.
Result:
Syntax: ALTER table table-name ADD(column-name data
SID Name City type).
11 Ana Banglore
Example: Consider a student table.
12 Bala Delhi
SID S Name Grade
13 Sudha Hyderabad
14 adam NULL

RIGHT OUTER JOIN: RIGHT OUTER JOIN returns the Add a new column called address
tuples available in the Right side table with the matched ALTER table student ADD (address char);
data of 2 tables and NULL for the left table’s column.
Example: Class 1 Example: Add multiple columns, parent-name, course-
Name, date-of-birth to student table.
SID Name
16 Arun ALTER table student ADD (parent-name
17 Kamal varchar(60), course-Name varchar(20),
date-of-birth date);
Info 1
SID City Example: Change the data type of column address to varchar?
16 Chennai
17 Noida ALTER table student modify(address varchar(30))
 Chapter 2 • Structured Query Language | 4.33

Example: Rename a column address to Location Syntax: Drop table table-name

Rename: This command is used to rename a table.
ALTER table student rename address to Location
Syntax: Rename table old-table-name to new-table-name.
TRUNCATE command: Truncate command removes all Example: Rename table Employee to New-Employee.
tuples from a table, this command will not destroy the tables
DROP a column: Alter command can be combined with
structure.
DROP command to remove columns from a table.
Syntax: Truncate table table-name
Syntax: alter table table-name DROP(column-name)
DROP Command: DROP query removes a table completely
from database. This command will destroy the table structure. Example: Alter table student DROP (grade)

Exercises
Practice Problems 1 (C) SELECT *
Directions for questions 1 to 20: Select the correct alterna- FROM Persons
tive from the given choices. WHERE last-name=’svendson’
AND (first-name=’tove’ AND first-name=’ola’)
1. Consider the given table called Persons (D) SELECT *
FROM Persons
P-Id Lastname Firstname Address City
WHERE last-name=’svendson’
1 Hansen ola Timoteivn -10 Sandnes OR (first-name=’tove’ AND first-name=’ola’)
2 Svendson Tove Brazil-50 Sandnes 3. Write an SQL statement to add a new row, but only in
3 Petterson Kari Storgt-20 Stavanger specified columns, for the persons table add data into
4 Joseph ole Brazil-20 Sandnes columns ‘P-Id’, ‘Last name’ and the ‘First name’ with
values (5, Teja, Jakob)?
Write a query to select the persons with first name (A) INSERT INTO Persons VALUES(5,‘teja’,‘jakob’)
‘Tove’ and last name ‘Svendson’? (B) INSERT INTO Persons VALUES(5,teja,jakob)
(A) SELECT * (C)  INSERT INTO Persons (P-Id, last-name, first-
FROM Persons name) VALUES(5,’teja’,’jakob’)
WHERE first-name=’tove’ (D)  INSERT INTO Persons(P-Id, last-name, first-
AND last-name=’svendson’ name) VALUES(5,teja,jakob)
(B) SELECT * 4. Write an SQL statement:
FROM Persons (i) To select the persons living in a city that starts
WHERE first-name=’tove’ with ‘S’ from the ‘Persons’ table?
OR last-name=’svendson’ (A) SELECT *
(C) SELECT first-name FROM Persons
FROM Persons WHERE city LIKE ‘s__’.
WHERE first-name=’tove’ (B) SELECT *
AND last-name=’svendson’ FROM Persons
(D) SELECT last-name WHERE city LIKE ‘s%’.
FROM Persons (C) SELECT *
WHERE first-name=’tove’ FROM Persons
AND last-name=’svendson’ WHERE city LIKE ‘%s’.
(D) SELECT *
2. Write a query to select only the persons with last name
FROM Persons
‘Svendson’ and the first name equal to ‘Tove’ or ‘ola’?
WHERE city LIKE ‘_s%’.
(A) SELECT * (ii) To select the persons living in a city that contains
FROM Persons the pattern ‘tav’ from ‘Persons’ table?
WHERE last-name=’svendson’ (A) SELECT *
AND first-name=’tove’ FROM Persons
(B) SELECT * WHERE city LIKE ‘_tav_’.
FROM Persons (B) SELECT *
WHERE last-name=’svendson’ FROM Persons
AND (first-name=’tove’ OR first-name=’ola’) WHERE city LIKE ‘_tav%’.
4.34 | Unit 4 • Databases

(C) SELECT * (i) Find out the students who have scored more than
FROM Persons 80 marks, and display them in descending order
WHERE city LIKE ‘%tav_’. according to their marks?
(D) SELECT * (A) SELECT student-name,marks
FROM Persons FROM Result
WHERE city LIKE ‘%tav%’. WHERE marks > 80
(iii) To select the persons whose last name starts with ORDERBY marks DESC
‘b’ or ‘s’ or ‘p’ ? (B) SELECT *
(A) SELECT * FROM Result
FROM Persons WHERE marks > 80
WHERE last-name LIKE ‘b-s-p’ ORDERBY marks DESC
(B) SELECT * (C) SELECT student-name,marks
FROM Persons FROM Result
WHERE last-name LIKE ‘b%s%p’ WHERE marks > 80
(C) SELECT * ORDERBY marks
FROM Persons (D) (A) and (B)
WHERE last-name LIKE ‘b%s%p%’ (ii) 
From the above table, find out the top-most three
(D) SELECT * students.
FROM Persons (A) SELECT student-name
WHERE last-name LIKE ‘[bsp]%’ FROM Result
5. Consider the given table called ‘Persons’ ORDERBY marks DESC > 3
(B) SELECT student-name
P-Id Last-name First-name Address City FROM Result
1 Hansen ola Timoteivn-10 Sandnes ORDERBY marks DESC = 3
2 Svendson Tove Brazil-50 Sandnes (C) SELECT student-name
3 Petterson Kari Storgt-20 Stavanger FROM Result
ORDERBY marks DESC limit 3
and the ‘Orders’ table (D) None of these
O-Id Order No P-Id 8. From the table ‘Results’, Identify the suitable SQL
11 77895 3 expression?
12 44678 3 (i) Find out the student Who stood 2nd?
13 22456 1 (A) SELECT student-name
14 24562 1
FROM Result
ORDERBY marks DESC limit 2
15 34764 5
(B) SELECT student-name
perform NATURAL JOIN operation on both the tables FROM Result
and what is are the O_Id’s displayed in the result? ORDERBY marks DESC limit 1,1
(A) 11, 12, 13 (B) 11, 13, 14 (C) SELECT student-name
(C) 11, 12, 13, 14 (D) 12, 13, 14 FROM Result
6. Write an SQL to perform FULL JOIN operation on ORDERBY marks DESC limit 1,2
both ‘Person’ and ‘Orders’ tables and What is the num- (D) SELECT student-name
ber of tuples in the Result? FROM Result
(A) 4 (B) 5 ORDERBY marks DESC limit 2,1
(C) 6 (D) 7 (ii) Find out how many students scored > = 80.
(A) SELECT COUNT(*)
7. Consider the given table ‘Result’. FROM Result
Student Name Marks WHERE marks > = 80
A 55 (B) SELECT COUNT
B 90 FROM Result
C 40 WHERE marks > = 80
(C) SELECT SUM(*)
D 80
FROM Result
E 85
WHERE marks > = 80
F 95 (D) SELECT SUM
G 82 FROM Result
WHERE marks > = 80
 Chapter 2 • Structured Query Language | 4.35

9. Consider the given tables: (ii) 

Find the loan-numbers from loan table where
branch-name is Dhaka?
Customer
(A) SELECT loan-number
Customer name Customer street Customer city FROM loan
Sonam Mirpurroad Dhaka WHERE branch-name=’dhaka’
Sonam Aga KhaRoad Bogra (B) SELECT loan-number
Anusha XYZRoad Kanchi
FROM branch-name=’dhaka’
(C) SELECT loan-number
Nandy MirpurRoad Dhaka
FROM Loan × Borrower
Account (D) Both (A) and (C)
11. (i) Find all customers who have only accounts but no
Account number Customer name Balance
loans.
A-101 Anusha 1000 (A) SELECT customer-name
A-102 Anusha 1500 FROM depositor LEFT OUTER JOIN Bor-
A-103 Sonam 2000 rower ON
A-104 Nandy 2500 [Link]-name=[Link]-
tomer-name
From the customer table, find out the names of all the WHERE loan-number IS NULL
customers who live in either Dhaka or Bogra? (B) SELECT customer-name
(A) SELECT customer-name FROM depositor LEFT OUTER JOIN Bor-
FROM customer rower ON
WHERE customer-city=’dhaka’ OR [Link]-name = [Link]-
customer-city=’bogra’ tomer-name
(B) SELECT customer-name WHERE loan-number=NULL
FROM customer (C) SELECT customer-name
WHERE customer-city=dhaka OR  FROM depositor RIGHT OUTER JOIN
customer-city=’bogra’ Borrower ON
(C) SELECT customer-name [Link]-name=[Link]-
FROM customer tomer-name
WHERE customer-city=’dhaka’ AND WHERE loan-number IS NULL
customer-city=’bogra’ (D) SELECT customer-name
(D) SELECT customer-name  FROM depositor RIGHT OUTER JOIN
FROM customer Borrower ON
WHERE customer-city=’dhaka’ EXIST [Link]-name=[Link]-
customer-city=’bogra’ tomer-name
10. Consider the given tables WHERE loan-number=NULL
Loan (ii) Find the names of all customers who have either
Loan Number Branch Name Amount an account or loan but not both.
L-101 Dhaka 1000
Borrower
L-103 Khulna 2000
Customer name Loan no.
Borrower: Sonam L-101
Customer name Loan number Sonam L-102
Sonam L-101 Anusha L-103
Nandy L-103
Anusha L-103 Depositor
Customer name Account no.
(i) What are the number of tuples present in the result
Anusha A-102
of cross product of the above two tables?
(A) 4 (B) 5 Sonam A-103
(C) 6 (D) 7 Nandy A-104
4.36 | Unit 4 • Databases

(A) SELECT customer name (C) SELECT SUM(salary)

FROM depositor FULL OUTER JOIN FROM Employee
Borrower ON GROUP BY Branch-name
[Link]-name=[Link]- (D) SELECT branch-name, SUM(salary)
name FROM Employee
 WHERE loan-number IS NULL OR Account- (iii) Find branch city, branch name Wise total salary,
number=NULL average salary and also number of employees.
(B) SELECT customer-name (A) SELECT branch-city, branch-name,
FROM depositor FULL OUTER JOIN SUM (salary), AVG(salary),
Borrower ON COUNT (Employee-name)
[Link]-name = [Link]- FROM Employee
name GROUP BY branch-city, branch-name
 WHERE loan-number IS NULL OR Account- (B) SELECT branch-city, branch-name,
number IS NULL SUM (salary), AVG (salary),
(C) SELECT customer-name COUNT (Employee-name)
FROM depositor FULL OUTER JOIN FROM Employee
Borrower ON GROUP BY branch-city
[Link]-name = [Link]- (C) SELECT branch-city, branch-name,
name SUM (salary), AVG (salary), COUNT (Em-
WHERE loan-number = NULL OR Account-num- ployee-name)
ber = NULL FROM Employee
(D) SELECT customer-name GROUP BY branch-name
FROM depositor FULL OUTER JOIN Borrower (D) SELECT branch-name, SUM (salary),
ON AVG (salary), COUNT (Employee-name)
[Link]-name = [Link]- FROM Employee
name GROUP BY branch-city, branch-name
WHERE loan-number=NULL OR Account-num- Common data for questions 13 to 15: Consider the SHIP­
ber IS NULL MENTS relation and write the SQL statements for the below
12. Consider the following ‘employee’ table
Employee name Branch name Branch city Salary SUPPLIERS
A DU Dhaka 1000 Supplier number Supplier name Status City

B DU Dhaka 2000 SN1 Suma 30 Hyderabad

SN2 Hari 20 Chennai
C BUET Dhaka 3000
SN3 Anu 10 Hyderabad
D KUET Khulna 4000
SN4 Mahesh 20 Bombay
E KU Khulna 5000 SN5 Kamal 30 Delhi
F RU Rajshahi 6000
PARTS
(i) Find the distinct number of branches appearing in Part number Part name Color Weight City
the employee relation. PN1 X Red 13.0 Chennai
(A) SELECT COUNT(branch-name) PN2 Y Green 13.5 Bombay
FROM Employee PN3 X Yellow 13.2 Hyderabad
(B) SELECT COUNT(DISTINCT branch-name) PN4 Y Green 14.1 Calcutta
FROM Employee PN5 Z Red 14.3 Hyderabad
(C) SELECT DISTINCT COUNT(branch-name) PN6 Z Blue 14.2 Bombay
FROM Employee
(D) SELECT COUNT(*) PROJECT
FROM Employee Project number Project name City
(ii) 
Find the total salary of all employees at each PJ1 Display Chennai
branch of the bank. PJ2 OCR Bombay
(A) SELECT branch-name, SUM(salary) PJ3 RAID Chennai
FROM Employee PJ4 SORTER Hyderabad
GROUP BY Branch-city PJ5 EDS Chennai
(B) SELECT branch-name, SUM(salary) PJ6 Tape Bombay
FROM Employee PJ7 Console Hyderabad
GROUP BY Branch-name
 Chapter 2 • Structured Query Language | 4.37

SHIPMENTS (B) SELECT [Link]-number

Supplier number Part number Project number Quantity FROM Shipments
GROUP BY [Link]-number
SN1 PN1 PJ1 300
HAVING COUNT([Link]-num-
SN1 PN1 PJ4 400
ber)>=2
SN2 PN3 PJ1 350 (C) SELECT [Link]-number
SN2 PN3 PJ2 450 FROM Shipments
SN2 PN3 PJ3 640 GROUP BY [Link]-number>2
SN2 PN3 PJ4 320 (D)  SELECT [Link]-number, COUNT
([Link]-number)>2
SN2 PN3 PJ5 330
FROM Shipments
SN2 PN3 PJ6 520
GROUP BY [Link]-number
SN2 PN3 PJ7 480
(iii) Get supplier names for suppliers who supply part
SN2 PN5 PJ2 460 PN3?
SN3 PN3 PJ1 440 (A) SELECT DISTINCT [Link]-name
SN3 PN4 PJ2 410 FROM Supplier
SN4 PN6 PJ3 310 WHERE [Link]-number IN (SE-
SN4 PN6 PJ7 320
LECT [Link]-number
FROM Shipments
SN5 PN2 PJ2 340
WHERE [Link]-number=’PN3’)
SN5 PN2 PJ4 350
(B) SELECT DISTINCT [Link]-name
SN5 PN5 PJ5 360 FROM Supplier
SN5 PN5 PJ7 370  WHERE [Link]-number NOT
SN5 PN6 PJ2 380 IN(SELECT [Link]-number
SN5 PN1 PJ4 420 FROM Shipments
SN5 PN3 PJ4 440
WHERE [Link]-number=’PN3’)
(C) SELECT DISTINCT [Link]-name
SN5 PN4 PJ4 450
FROM Supplier
SN5 PN5 PJ4 400 WHERE [Link]-number EXCEPT
SN5 PN6 PJ4 410 (SELECT [Link]-number
13. (i)  For each part supplied, get the part number and the FROM Shipments
total shipment quantity? WHERE [Link]-number=’PN3’)
(A) SELECT [Link]-number, SUM (ship- (D) SELECT DISTINCT suppliers, supplier-name
[Link]) FROM Supplier
FROM Shipments WHERE [Link]-number
GROUP BY [Link]-number UNION
(B) SELECT SUM([Link]) SELECT [Link]-number
FROM Shipments FROM Shipments
GROUP BY [Link]-number WHERE [Link]-number=’PN3’
(C) SELECT [Link]-number, SUM (ship- 14. (i) 
Get supplier names for suppliers who supply at
[Link]) least one blue part.
FROM Shipments (A) SELECT DISTINCT [Link]-name
GROUP BY [Link] FROM Suppliers
(D) SELECT [Link]-number, SUM (ship- WHERE [Link]-number
ments. part-number) IN (SELECT [Link]-number
FROM Shipments FROM Shipments
GROUP BY [Link]-number WHERE [Link]-number
(ii) Get part numbers for parts supplied by more than IN (SELECT [Link]-number
two suppliers? FROM Parts
(A) SELECT [Link]-number WHERE [Link]=’Blue’))
FROM Shipments (B) SELECT DISTINCT [Link]-name
GROUP BY [Link]-number FROM Suppliers
HAVING COUNT([Link]-num- WHERE [Link]-number
ber) > 2 IN (SELECT [Link]-number
FROM Shipments
4.38 | Unit 4 • Databases

WHERE [Link]-number NOT (B) SELECT DISTINCT [Link]-name

IN( SELECT [Link]-number FROM Suppliers
FROM Parts WHERE NOT EXIST(SELECT *
WHERE [Link]=’Blue’)) FROM Shipments
(C) SELECT DISTINCT [Link]-name WHERE [Link]-number = sup-
FROM Suppliers [Link]-number
 WHERE [Link]-number NOT AND
IN(SELECT [Link]-number [Link]-number=’PN2’)
FROM Shipments (C) SELECT DISTINCT [Link]-name
WHERE [Link]-number FROM Suppliers
IN (SELECT [Link]-number WHERE EXIST(SELECT *
FROM Parts FROM Shipments
WHERE [Link]=’Blue’)) WHERE [Link]-number = sup-
(D) SELECT DISTINCT [Link]-name [Link]-number
FROM Suppliers OR
WHERE [Link]-number [Link]-number=’PN2’)
IN (SELECT [Link]-name (D) SELECT DISTINCT [Link]-name
FROM Shipments FROM Suppliers
WHERE [Link]-number WHERE EXIST(SELECT *
IN (SELECT [Link]-number FROM Shipments
FROM Parts WHERE [Link]-number = sup-
WHERE [Link]=’Blue’)) [Link]-number
(ii) Get supplier numbers for suppliers with status less UNION
than the current maximum status in the suppliers [Link]-number=’PN2’)
table: 15. (i) Get supplier names for suppliers who do not sup-
(A) SELECT [Link]-number ply part PN2.
FROM suppliers (A) SELECT DISTINCT [Link]-name
WHERE [Link] < (SELECT MAX FROM Suppliers
([Link]) WHERE NOT EXIST(SELECT *
FROM Suppliers) FROM Shipments
(B) SELECT [Link]-number WHERE [Link]-number = sup-
FROM suppliers [Link]-number
WHERE [Link]<=(SELECT MAX AND
([Link]) [Link]-number=’PN2’)
FROM Suppliers) (B) SELECT DISTINCT [Link]-name
(C) SELECT [Link]-number, FROM Suppliers
WHERE EXIST(SELECT *
MAX ([Link])
FROM Shipments
FROM suppliers
WHERE [Link]-number = sup-
WHERE [Link]
[Link]-number
(D) SELECT [Link]-number AND
FROM suppliers [Link]-number=’PN2’)
WHERE [Link]=MAX(Suppliers. (C) SELECT DISTINCT [Link]-name
status) FROM Suppliers
(iii) Get supplier names for suppliers who supply part WHERE EXCEPT(SELECT *
PN2? FROM Shipments
(A) SELECT DISTINCT [Link]-name WHERE [Link]-number = sup-
FROM Suppliers [Link]-number
WHERE EXIST(SELECT * AND
FROM Shipments [Link]-number=’PN2’)
WHERE [Link]-number = sup- (D) SELECT DISTINCT [Link]-name
[Link]-number FROM Suppliers
AND WHERE NOT EXIST(SELECT *
[Link]-number=’PN2’) FROM Shipments
 Chapter 2 • Structured Query Language | 4.39

WHERE [Link]-number = sup- (B) SELECT [Link]-number

[Link]-number FROM parts
OR WHERE [Link]>18
[Link]-number=’PN2’) UNION
(ii) Get supplier names for suppliers who supply all SELECT [Link]-name
parts. FROM shipments
(A) SELECT DISTINCT [Link]-name WHERE [Link]-number=’SN2’
FROM Suppliers (C) SELECT [Link]-number
WHERE NOT EXIST(SELECT * FROM parts
FROM Part WHERE [Link]>18
 WHERE NOT EXIST(SELECT * FROM UNION
Shipments SELECT [Link]-number,Shipments.
WHERE [Link]-number = sup- supplier-name
[Link]-number FROM shipments
AND WHERE [Link]-number=’SN2’
[Link]-number=[Link]-number)) (D) SELECT [Link]-Number, [Link]
(B) SELECT DISTINCT [Link]-name FROM parts
FROM Suppliers WHERE [Link]>18
UNION
WHERE EXIST(SELECT *
SELECT [Link]-number
FROM Part
FROM shipments
 WHERE NOT EXIST(SELECT * FROM
WHERE [Link]-number=’SN2’
Shipments
WHERE [Link]-number = sup- Common data for questions 16 and 17: Consider the fol-
[Link]-number lowing relation: Teach
AND
Name Address course
[Link]-number=[Link]-number))
(C) SELECT DISTINCT [Link]-name Zohar 40B,east city MD
Nisha 16/2, hyd BDS
FROM Suppliers
Zohar 40B, East city MS
WHERE NOT EXIST(SELECT *
Ravi New York MBA
FROM Part
WHERE EXIST(SELECT * FROM Shipments 16. The teacher with name Zohar teaching the course MS?
WHERE [Link]-number = sup- (A) sName = ‘Zohar’ teach = MS.
[Link]-number (B) pName = ‘Zohar’ teach = MS.
AND (C) sname = ‘Zohar’ and course = ‘MS’ (teach).
[Link]-number=[Link]-number)) (D) pName = ‘Zohar’ and course = ‘MS’ (teach).
(D) SELECT DISTINCT [Link]-name 17. Select the names of courses taught by Zohar?
FROM Suppliers (A) pcourse(sName = ‘Zohar’ (Teach))
WHERE EXIST(SELECT * (B) scourse(pName = ‘Zohar’ (Teach))
FROM Part (C) pcourse(sName = ‘MD’ (Teach))
WHERE EXIST(SELECT * FROM Shipments (D) None
WHERE [Link]-number = sup- 18. Consider the join of a relation A with a relation B. If A
[Link]-number has m tuples and B has n tuples. Then the maximum and
AND minimum sizes of the join respectively are.
[Link]-number=[Link]-number)) (A) mn and m + n    (B) m + n and (m –n)
(iii) Get part numbers for parts that either weigh more (C) mn and m       (D) mn and 0
than-16 pounds or are supplied by supplier SN3, or 19. Match the following:
both?
(A) SELECT [Link]-number I Set intersection 1 R |×| S
FROM parts II Natural join 2 r – (r – s)
WHERE [Link]>18 III Division 3 ←
UNION
pR – S(r) – pR –S
SELECT [Link]-number
IV Assignment 4 (π R−S (r ) × s)
FROM shipments
−π R−S , s(r )
WHERE [Link]-number=’SN2’
4.40 | Unit 4 • Databases

(A) I – 2, II – 1, III – 4, IV – 3 (A) r ÷ s

(B) I – 3, II – 4, III – 2, IV – 1 (B) π R − S (r ) − π R − S ((π R − S (r ) × s ) − π R − S ), s (r )
(C) I – 1, II – 2, III – 3, IV – 4 (C) Temp 1 ← pR – S (r)
(D) I – 2, II – 3, III – 4, IV – 1 Temp 2 ← pR – S(temp1 × s) –pR – S, s(r)
20. Which one is correct for division operations for rela- result = temp 1 – temp 2
tion r and s (D) All the above

Practice Problems 2 7. Select the persons whose hobby is either painting (or)
Directions for questions 1 to 20: Select the correct alterna- singing.
tive from the given choices. (A) sHobby = ‘painting’ OR Hobby = ‘singing’ (person)
1. The correct order of SQL expression is (B) sHobby = ‘painting’,’ singing’ (person)
(A) Select, group by, where, having (C) sHobby = ‘painting’ OR ‘singing’ (person)
(B) Select, where, group by, having (D) All are correct
(C) Select, group by, having, where 8. Select the persons whose age is above 21 and below 32:
(D) Select, having, where, group by (A) sage > 21 AND age < 32 (person)
2. Which one is not a query language? (B) s21 < age < 32 (person)
(A) SQL (B) QBE
(C) sage > 21 OR age < 32 (person)
(C) Data log (D) MySQL
(D) sage < 21 AND age > 32 (person)
3. Like ‘a b \ % c d’ escape ‘\’ matches all the strings
(A) Ending with a b c d Common data for questions 9 and 10: Consider the fol-
(B) Beginning with a b c d lowing relation: Teach
(C) Beginning with a b c d
Name course Rating Age
(D) Beginning with a b % c d
Zohar MD 7 35
4. ‘_ _ _%’ matches any string of
(A) At least three characters Nisha BDS 8 27
(B) At most three characters Zohar MS 7 34
(C) Exactly three characters Ravi MBA 9 33
(D) exactly three characters ending with %
5. Which of the following are set operations? 9. Select the teachers whose rating is above 7 and whose
(i) Union age is less than 32?
(ii) Intersection (A) sRating > 7 AND Age < 32 (Teach)
(iii) Set Difference (B) sRating ≥ 7 AND Age < 32 (Teach)
(iv) Cartesian Product (C) sRating > 7 AND < 32 (Teach)
(A) (i), (ii), (iii) (D) Both (A) and (B)
(B) (i), (iii), (iv)
10. Select the courses with rating above 7?
(C) (i), (iii), (ii), (iv)
(D) (i), (ii), (iv) (A) pcourse (srating > 7 (Teach))
(B) scourse (p rating > 7(Teach))
6. What is the purpose of project operation?
(C) pname, course (srating > 7 (Teach))
(A) It selects certain columns
(B) It selects certain rows (D) None
(C) It selects certain strings Common data for questions 11 and 12: Consider the follow-
(D) It selects certain integers ing schema of a relational database employee (empno, ename,
eadd) project (pno, pname) Work–on (empno, pno) Part(partno,
Common data for questions 7 and 8: Person partname, qty-on-hand, size) Use (empno, pno, partno, number)
Id Name Age Hobby 11. Display the names of the employees who are working
11 Anu 21 Stamp Collection on a project named ‘VB’.
22 Kamal 32 Painting
(A) sname(employee ⋈ (spname = ‘VB’ project) ⋈ worked on)
(B) sname (employee ⋈ (ppname = ‘VB’ (project) ⋈ work on)
33 Ravi 24 Dancing
(C) pname (employee ⋈ (spname = ‘VB’ (project) ⋈ work on)
44 Ram 22 Singing
(D) pname (employee ⋈ (ppname = ‘VB’ (project) ⋈ work on)
 Chapter 2 • Structured Query Language | 4.41

12. Display the names of the people who are not working (A) Names of the students who are working in either
for any project. projects ‘MS’ or ‘MD’
(A) pname (employee ⋈(pname (employee + work on) (B) Names of the students who are working in both the
(B) pname (employee – pname (employee ∩ work on) projects ‘MS’ or ‘MD’
(C) pname (employee – pname (employee ⋈ work on) (C) Names of the students who are not working in any of
the projects ‘MS’ or ‘MD’
(D) sname (employee – sname (employee ⋈ work on)
(D) None of the above
13. Consider the following tables: 16. ‘All rows corresponding to students whose sno’s are
A B C D C D between 10 and 20
b c e f e f
(i) Select * form student where SNo are between 5
AND 10
a b i j g h
(ii) Select * from student where SNO IN(5, 10)
b c g h (A) Only (i) (B) Only (ii)
b c a d (C) Both (A) and (B) (D) None
d i g h 17. UPDATE account SET
d j j k DA = basic * .2,
d i e f GROSS = basic * 1.3, Where basic > 2000;
(A) The above query displays DA and gross for all
R÷S those employees whose basic is ≥ 2000
A B (B) The above query displays DA and Gross for all
b c employees whose basic is less than 2000
(C) The above query displays updated values of DA as
d i
well as gross for all those employees whose basic
Which of the following statements is true? is > 2000
(A) R ÷ S = pA, B(R) – pA, B(pA, B(R) × S + R) (D) All the above
(B) R ÷ S = pA, B(R) – pA, B(pA, BR × S – R) 18. Given two union compatible relations R1(A, B) and R2(C,
D), what is the result of the operation
(C) R ÷ S = pA, B(R) – pA, B((pA, B(R) × S) – R)
R1 A = CAB = DR2?
(D) R ÷ S = pA, B(R) – pA, B(pA, B(R) × R – S) (A) R1 ∪ R2 (B) R1 × R2
(C) R1 – R2 (D) R1 ∩ R2
Common data for questions 14 and 15: Consider the fol-
lowing schema of a relational data base 19. Which of the following queries finds the clients of banker
student (sno, name, address) Agassi and the city they live in?
project (pno, Pname) work-on (sno, pno) [Link]([Link] = customer c name (sBanker.
(A) 
Part (part no, part name, qtyon hand size) name = Aggassi
(client × customer)
Use (sno, pno, part no, number) (B) pClient.c city (sBanker name = ‘Aggasi’(client × customer)
14. List the names of the students who are participating in pclient.c [Link](sclient.c name = ‘Aggasi’ ([Link] = Cutomer
(C) 
every project and have used every part. (client × customer)
(A) sname(student ⋈(((Workon) ÷ spro(project)) ∩ (ssno, part p .c [Link](sBankers name = name (sBanker. = agassi (cli-
(D) 
no
(use) ÷ spart no (part))) ent × customer)
(B) pname(student ⋈(((Workon) ÷ ppro(project)) ∩ (psno, 20. Consider the following schema pertaining to students data
partno
(use) ÷ spart no (part))) Student (rno, name, add)
(C) pname(student ⋈(((Workon) ÷ ppartno (project)) ∩ (psno, Enroll (rno, Cno, Cname) Where the primary keys are
partno
(use) ÷ spart no (part))) shown Underlined. The no. of tuples in the student and
(D) pname(student ∞ (((Workon) ÷ ppro(project)) ∪ (pssno, Enroll tables are 120 and 8 respectively. What are the
partno
(use) ÷ ppart no (part))) maximum and minimum no. of tuples that can be pre-
sent in (student * Enroll) where ‘*’ denotes natural join.
15. The following query gives pname (employee ⋈(work on ÷
(A) 8, 8 (B) 120, 8
ppro (sPname = ‘MS’ AND ‘MD’(project))) (C) 960, 8 (D) 960, 120
4.42 | Unit 4 • Databases

Previous Years’ Questions

1. Consider the relation account (customer, balance) (C) There exist databases for which Query3 returns
where customer is a primary key and there are no null strictly fewer rows than Query2
values. We would like to rank customers according (D) There exist databases for which Query4 will en-
to decreasing balance. The customer with the largest counter an integrity violation at runtime
balance gets rank 1, ties are not broke but ranks are
skipped; if exactly two customers have the largest bal- 3. Consider the relation enrolled (student, course), in
ance they each get rank 1 and rank 2 is not assigned. which (student, course) is the primary key, and the
relation paid (student, amount) where student is the
 Query 1: select [Link], count ([Link]) from primary key. Assume no null values and no foreign
account A, account B where [Link] <= [Link] keys or integrity constraints. Assume that amounts
group by [Link] 6000, 7000, 8000, 9000 and 10000 were each paid by
Query 2: select [Link], 1 + count ([Link]) 20% of the students. Consider these query plans (plan
from account A, account B where [Link] < 1 on left, plan 2 on right) to ‘list all courses taken by
[Link] group by [Link] Consider these state- students who have paid more than x’
ments about Query1 and Query2. Enrolled Paid Enrolled Paid
1. Query1 will produce the same row set as Query2
for some but not all databases. Probe index Sequential Probe index Sequential scan
2. Both Query1 and Query2 are correct implementa- on student scan, select on student
tion of the specification. amout > x
3. Query1 is a correct implementation of the specifi-
cation but Query2 is not. Indexed nested loop join
Indexed nested loop join
4. Neither Query1 nor Query2 is a correct implemen-
Select on amount > x
tation of the specification.
Project on course
5. Assigning rank with a pure relational query takes
Project on course
less time than scanning in decreasing balance or-
der assigning ranks using ODBC.
Which two of the above statements are correct?[2006] A disk seek takes 4 ms, disk data transfer bandwidth
(A) 2 and 5 (B) 1 and 3 is 300 MB/s and checking a tuple to see if amount is
(C) 1 and 4 (D) 3 and 5 greater than x takes 10 ms. Which of the following
statements is correct? [2006]
2. Consider the relation enrolled (student, course) in (A) Plan 1 and Plan 2 will not output identical row
which (student, course) is the primary key, and the sets for all databases
relation paid (student, amount) where student is the (B) A course may be listed more than once in the
primary key. Assume no null values and no foreign output of Plan 1 for some databases
keys or integrity constraints. Given the following four (C) For x = 5000, Plan 1 executes faster than Plan 2
queries: for all databases
Query1: select student from enrolled where student in (D) For x = 9000, Plan 1 executes slower than Plan 2
(select student from paid) for all databases
Query2: select student from paid where student in (se- 4. Information about a collection of students is given by
lect student from enrolled) the relation studinfo (studId, name, sex). The rela-
tion enroll (studId, courseId) gives which student has
Query3: select [Link] from enrolled E, paid P enrolled for (or taken) what course(s). Assume that
where [Link] = [Link] every course is taken by at least one male and at least
Query4: select student from paid where exists (select one female student. What does the following rela-
* from enrolled where [Link] = [Link]- tional algebra expression represent?
dent)
Πcourseld((Πstudid(ssex = ‘female’(studInfo))
Which one of the following statement is correct?[2006]
× Πcourseld (enroll)) - enroll) [2007]
(A) All queries return identical row sets for any data-
base (A) Courses in which all the female students are en-
(B) Query2 and Query4 return identical row sets for rolled
all databases but there exist databases for which (B) Courses in which a proper subset of female stu-
Query1 and Query2 return different row sets dents are enrolled.
 Chapter 2 • Structured Query Language | 4.43

(C) 
Courses in which only male students are en- 8. Let R and S be relational schemes such that R =
rolled. {a,b,c} and S = {c}. Now consider the following que-
(D) None of the above ries on the database:
I. π R − S (r ) − π R − S (π R − S (r ) × s − π R − S , S (r ))
5. Consider the relation employee (name, sex, super-
visorName) with name as the key. supervisorName II. {t | t ∈ π R − S (r ) ∧ ∀u ∈ s (∃v ∈ r (u = v[ s ] ∧ t
gives the name of the supervisor of the employee = v[ R − S ]))}
under consideration. What does the following Tuple
Relational Calculus query produce? III. {t | t ∈ π R − S (r ) ∧ ∀v ∈ r (∃u ∈ s (u = v[ s ] ∧ t
e ⋅ name | employee(e) ∧ = v[ R − S ]))}

(∀x)[¬employee( x) ∨ x ⋅ supervisor Name ≠ e ⋅ name ∨ IV. SELECT R.a, R.b

FROM R, S
 x ⋅ sex = "male"]} [2007] WHERE R.c = S.c
(A) Names of employees with a male supervisor. Which of the above queries are equivalent? [2009]
(B) Names of employees with no immediate male (A) I and II (B) I and III
subordinates. (C) II and IV (D) III and IV
(C) Names of employees with no immediate female
subordinates. Common data for questions 9 and 10: Consider the fol-
(D) Names of employees with a female supervisor. lowing relational schema: Suppliers (sid: integer, sname:
string, city: string, street: string) Parts(pid: integer, pname:
6. Consider the table employee (empId, name, depart-
string, color: string) Catalog (sid: integer, pid: integer,
ment, salary) and the two queries Q1, Q2 below.
cost: real)
Assuming that department 5 has more than one
employee, and we want to find the employees who 9. Consider the following relational query on the above
get higher salary than anyone in the department 5, database:
which one of the statements is TRUE for any arbi- SELECT  [Link]
trary employee table? FROM     Suppliers S
Q1: SELECT [Link] WHERE [Link] NOT IN (SELECT [Link]
FROM Catalog C
FROM employee e
WHERE [Link] NOT IN (SELECT [Link] FROM Parts P
WHERE not exists
WHERE [Link] <> ‘blue’))
(Select * From employee s where [Link] = ‘5’
and [Link] >=[Link]) Assume that relations corresponding to the above
schema are not empty. Which one of the following is
Q2: SELECT [Link]
the correct interpretation of the above query? [2009]
FROM employee e
(A) Find the names of all suppliers who have sup-
WHERE [Link] > Any plied a non-blue part.
(Select distinct salary From employee s Where (B) Find the names of all suppliers who have not sup-
[Link] = ‘5’) [2007] plied a non-blue part.
(A) Q1 is the correct query (C) Find the names of all suppliers who have sup-
(B) Q2 is the correct query plied only blue parts.
(C) Both Q1 and Q2 produce the same answer. (D) Find the names of all suppliers who have not sup-
(D) Neither Q1 nor Q2 is the correct query plied only blue parts.
7. Let R and S be two relations with the following schema 10. A relational schema for a train reservation database is
R (P, Q, R1, R2, R3) given below
S (P, Q, S1, S2) Passenger (pid, pname, age)
Where {P, Q} is the key for both schemas. Which of Reservation (pid, cass, tid)
the following queries are equivalent? Table :Passenger
I. ΠP (R ⋈ S) Table :Reservation
II. ΠP (R) ⋈ ΠP (S)
Pid pname Age Pid class tid
III. ΠP (ΠP, Q (R) ∩ ΠP, Q (S))
IV. ΠP (ΠP, Q (R) – (ΠP, Q (R) – (ΠP, Q (S))) [2008] 0 ‘Sachin’ 65 0 ‘AC’ 8200

(A) Only I and II (B) Only I and III 1 ‘Rahul’ 66 1 ‘AC’ 8201
(C) Only I, II and III (D) Only I, III and IV 2 ‘Sourav’ 67 2 ‘SC’ 8201
4.44 | Unit 4 • Databases

3 ‘Anil’ 69 5 ‘AC’ 8203 Let MX and MY denote the respective maximum values
of X and Y among all records in the table at any point
1 ‘SC’ 8204 in time. Using MX and MY, new records are inserted
3 ‘AC’ 8202 in the table 128 times with X and Y values being MX
+ 1, 2 * MY + 1 respectively. It may be noted that each
time after the insertion, values of MX and MY change.
What pids are returned by the following SQL query for the
What will be the output of the following SQL query
above instance of the tables?
after the steps mentioned above are carried out?
SELECT pid SELECT Y FROM T WHERE X = 7; [2011]
FROM Reservation (A) 127 (B) 255
WHERE class = ‘AC’ AND (C) 129 (D) 257
EXISTS (SELECT * 14. Which of the following statements are true about an
FROM Passenger SQL query?
WHERE age > 65 AND P: An SQL query can contain a HAVING clause
[Link] = [Link]) [2010] even if it does not have a GROUP BY clause
(A) 1, 0 (B) 1, 2 Q: An SQL query can contain a HAVING clause
(C) 1, 3 (D) 1, 5 only if it has a GROUP BY clause
11. Consider a relational table r with sufficient number of R: All attributes used in the GROUP BY clause must
records, having attributes A1, A2, … An and let 1 ≤ p ≤ n. appear in the SELECT clause
Two queries Q1 and Q2 are given below. S: Not all attributes used in the GROUP BY clause
need to appear in the SELECT clause  [2012]
Q1: π A1 … An (σ Ap=c (r )) where c is a constant.
(A) P and R (B) P and S
Q2: π A1 … An (σ c1 ≤ Ap ≤ c2 (r )) where c1 and c2 are constants. (C) Q and R (D) Q and S
The database can be configured to do ordered indexing 15. Suppose R1(A, B) and R2(C, D) are two relation
on AP or hashing on Ap. Which of the following state- schemas. Let r1 and r2 be the corresponding relation
ments is TRUE? [2011] instances. B is a foreign key that refers to C in R2.
(A) Ordered indexing will always outperform hash- If data in r1 and r2 satisfy referential integrity con-
ing for both queries straints, which of the following is always true?[2012]
(B) Hashing will always outperform ordered index- (A) ΠB (r1) – ΠC(r2) = ∅
ing for both queries. (B) ΠC(r2) – ΠB (r1) = ∅
(C) Hashing will outperform ordered indexing on (C) ΠB (r1) = ΠC (r2)
Q1, but not on Q2.
(D) Hashing will outperform ordered indexing on (D) ΠB (r1) – ΠC (r2) ≠ ∅
Q2, but not on Q1.
Common data for questions 16 and 17: Consider the fol-
12. Database table by name Loan_Records is given below.
lowing relations A, B and C:
Borrower Bank manager Loan amount (A)
Ramesh Sunderajan 10000.00 Id Name Age

Suresh Ramgopal 5000.00 12 Arun 60

Mahesh Sunderajan 7000.00 15 Shreya 24

99 Rohit 11
What is the output of the following SQL query?
SELECT count ( * ) (B)
FROM (Select Borrower, Bank_Manager FROM Id Name Age
Loan Records) AS S 15 Shreya 24
NATURAL JOIN 25 Hari 40
(SELECT Bank_Manager, Loan_Amount FROM 98 Rohit 20
Loan_Records) AS T; [2011] 99 Rohit 11
(A) 3 (B) 9 (C)
(C) 5 (D) 6 Id Phone Area
13. Consider a database table T containing two columns 10 2200 02
X and Y each of type integer. After the creation of the 99 2100 01
table, one record (X = 1, Y = 1) is inserted in the table.
 Chapter 2 • Structured Query Language | 4.45

16. How many tuples does the result of the following 20. Given the following schema:
SQL query contain? Employees (emp–id, first-name, last– name, hire–
SELECT [Link] date, dept–id, salary)
FROM A  Departments (dept–id, dept–name, manager–id,
WHERE A. Age > ALL (SELECT B. Age location–id)
FROM B  you want to display the last names and hire dates of
WHERE B. Name = ‘Arun’) [2012] all latest hires in their respective departments in the
(A) 4 (B) 3 location ID 1700. You issue the following query:
(C) 0 (D) 1 SQL > SELECT last–name, hire–date
17. How many tuples does the result of the following FROM employees
relational algebra expression contain? Assume that WHERE (dept–id, hire–date) IN
the schema of A ∪ B is the same as that of A. (SELECT dept–id, MAX (hire–date)
(A⋃B) ⋈[Link] > 40 V [Link] <15C [2012]  FROM employees JOIN departments USING
(A) 7 (B) 4 (dept–id)
(C) 5 (D) 9 WHERE location–id = 1700
18. Consider the following relational schema. Students GROUP BY dept–id);
(rollno: integer, sname: string) Courses (courseno: What is the outcome? [2014]
integer, cname: string) Registration(rollno:integer,co (A) It executes but does not give the correct result.
urseno: integer, percent: real) (B) It executes and gives the correct result.
  Which of the following queries are equivalent to (C) It generates an error because of pair wise compari-
this query in English? son.
  ‘Find the distinct names of all students who score (D) It generates an error because the GROUP BY
more than 90% in the course numbered 107’ clause cannot be used with table joins in a sub-
(I) SELECT DISTINCT [Link] FROM Students query.
as S, Registration as R WHERE [Link]=[Link] 21. Given an instance of the STUDENTS relation as
AND [Link]=107 AND [Link]>90 shown below:
(II) psname(σcourseno=107^percent>90 Registration⑅Students) Student Student
Student ID Name Student Email Age CPI
(III) {T |∃ S ∈ Students, ∃R∈ Registration ([Link]=R.
rollno ∧ [Link]=107 ∧ [Link]>90∧T. 2345 Shankar shaker @ math X 9.4
sname=[Link])} 1287 Swati swati @ ee 19 9.5

(IV) {<SN> |∃SR∃RP (<SR, SN> ∈ Students ∧ <SR, 107, 7853 Shankar shankar @ cse 19 9.4

RP> ∈ Registration ∧ RP>90)} [2013] 9876 Swati swati @ mech 18 9.3

(A) I, II, III and IV (B) I, II and III only 8765 Ganesh ganesh@ civil 19 8.7

(C) I, II and IV only (D) II, III and IV only For (StudentName, StudentAge) to be a key for this
instance, the value X should NOT be equal to _____.
19. Given the following statements:  [2014]
S1: A foreign key declaration can always be replaced
22. Consider a join (relation algebra) between relations
by an equivalent check assertion in SQL.
(r(R)) and (s(S)) using the nested loop method. There
S2: Given the table R (a, b, c) where a and b together
are three buffers each of size equal to disk block size,
form the primary key, the following is a valid ta-
out of which one buffer is reserved for intermediate
ble definition.
results. Assuming size r(R) < size s(S), the join will
CREATE TABLE S (
have fewer number of disk block accesses if [2014]
a INTEGER
(A) Relation r(R) is in the outer loop
d INTEGER,
(B) Relation s(S) is in the outer loop
e INTEGER,
(C) Join selection factor between r(R) and s(S) is
PRIMARY KEY (d),
more than 0.5
FOREIGN KEY (a) references R)
(D) Join selection factor between r(R) and s(S) is less
Which one of the following statements is CORRECT? than 0.5
 [2014]
23. SQL allows duplicate tuples in relations, and corre-
(A) S1 is TRUE and S2 is FALSE
spondingly defines the multiplicity of tuples in the
(B) Both S1 and S2 are TRUE result of joins. Which one of the following queries
(C) S1 is FALSE and S2 is TRUE always gives the same answer as the nested query
(D) Both S1 and S2 are FALSE shown below:
4.46 | Unit 4 • Databases

Select * from R where a in (select S. a from S)[2014] (C) Names of all the employees with none of their cus-
(A) Select R.* from R, S where R. a = S. a tomers having a ‘GOOD’ rating.
(B) Select distinct R * from R, S where R . a = S . a (D) Names of all the employees with all their customers
(C) Select R.* from R, (select distinct a from S) as S1 having a ‘GOOD’ rating.
where R.a = S1.a 27. SELECT operation in SQL is equivalent to [2015]
(D) Select R.* from R, S where R.a = S.a and is unique (A) The selection operation in relational algebra
R (B) The selection operation in relational algebra,
except that SELECT in SQL retains duplicates.
24. What is the optimized version of the relation algebra
(C) The projection operation in relational algebra.
expression π A1 (π A2 (σ F1 (σ F2 ( r ) ))), where A1, A2 are sets
(D) The projection operation in relational algebra,
of attributes in r with A1 ⊂ A2 and F1, F2 are Boolean except that SELECT in SQL retains duplicates.
expressions based on the attributes in r? [2014]
28. Consider the following relations:
(A) π A1 (σ ( F ∧ F )( r ) )
1 2
Student
(B) π A1 (σ ( F ∨ F )( r ) ) Roll No Student Name
1 2

(C) π A2 (σ ( F ∧ F )( r ) ) 1 Raj
1 2
2 Rohit
(D) π A2 (σ ( F ∨ F )( r ) ) 3 Raj
1 2

25. Consider the relational schema given below, where Performance

eld of the relation dependent is a foreign key refer-
Roll No Course Marks
ring to empId of the relation employee. Assume that
every employee has at least one associated dependent 1 Math 80
in the dependent relation. 1 English 70
Consider the following relational algebra query: 2 Math 75
employee (empId, empName, empAge) 3 English 80
dependent (depId, eId, depName, depAge)
2 Physics 65
pempId(employee)- pempId (employee ⋈ (empId = eID) ∧ (empAge ≤
3 Math 80
depAge)
dependent)
The above query evaluates to the set of empIds of em- Consider the following SQL query.
ployees whose age is greater than that of  [2014]
SELECT S.Student_Name, sum ([Link])
(A) some dependent.
FROM Student S, Performance P
(B) all dependents.
WHERE S.Roll_No = P.Roll_No
(C) some of his/her dependents.
GROUP BY S.Student_Name
(D) all of his/her dependents.
The number of rows that will be returned by the SQL
26. Consider the following relational schema: query is ______ [2015]
employee (empId, empName, empDept)
customer(custId, custName, salesRepid, rating) 29. Consider two relations R1(A, B) with the tuples (1, 5),
salesRepId is a foreign key referring to empId of the (3, 7) and R2(A, C) = (1, 7), (4, 9). Assume that R(A, B,
employee relation. Assume that each employee makes C) is the full natural outer join of R1 and R2. Consider
a sale to at least one customer. What does the follow- the following tuples of the form (A, B, C): a = (1, 5,
ing query return? null), b = (1, null, 7), c = (3, null, 9), d = (4, 7, null), e
SELECT empName = (1, 5, 7), f = (3, 7, null), g = (4, null, 9). Which one
FROM employee E of the following statements is correct? [2015]
WHERE NOT EXISTS (A) R contains a, b, e, f, g but not c, d.
(SELECT custId (B) R contains all of a, b, c, d, e, f, g.
FROM customer C (C) R contains e, f, g but not a, b.
WHERE [Link] = [Link] (D) R contains e but not f, g.
AND [Link] < > ‘GOOD’); [2014] 30. Consider the following relation
(A) Names of all the employees with at least one of
Cinema (theater, address, capacity)
their customers having a ‘GOOD’ rating.
(B) Names of all the employees with at most one of Which of the following options will be needed at the
their customers having a ‘GOOD’ rating. end of the SQL query
 Chapter 2 • Structured Query Language | 4.47

SELECT [Link] (D) WHERE [Link] > Any (select max(P2.

FROM Cinema P1 capacity) from Cinema P2)
such that it always finds the addresses of theaters with 31. Which of the following is NOT a superkey in a rela-
maximum capacity? [2015] tional schema with attributes V, W, X, Y, Z and primary
(A) WHERE [Link] > = All (select P2. Capacity key VY? [2016]
from Cinema P2) (A) V XYZ (B) V WXZ
(B) WHERE [Link] >= Any (select P2. Capacity (C) V WXY (D) V WXYZ
from Cinema P2) 32. Consider a database that has the relation schema EMP
(C) WHERE [Link] > All (select max(P2. (EmpId, EmpName and DeptName). An instance of
capacity) from Cinema P2) the schema EMP and a SQL query on it are given
below.

EMP
EmpId EmpName DeptName
1 XYA AA SELECTIVE AVG ( [Link] )
2 XYB AA FROM EC
3 XYC AA
WHERE ( DeptName, Num ) IN
4 XYD AA
(SELECT DeptName, COUNT ( EmpId ) AS
5 XYE AB
6 XYF AB EC ( DeptName, Num )
7 XYG AB FROM EMP
8 XYH AC GROUP BY DeptName)
9 XYI AC
10 XYJ AC
11 XYK AD
12 XYL AD
13 XYM AE

The output of executing the SQL query is ______.

CR
 [2017]
StudentName CourseName
33. Consider a database that has the relation sche-
SA CA
mas EMP(EmpId, EmpName, DeptId), and
DEPT(DeptName, DeptId), Note that the DeptId SA CB
can be permitted to be NULL in the relation EMP. SA CC
Consider the following queries on the database SB CB
expressed in tuple relational calculus. SB CC
(I) {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∀ SC CA
v ∈ DEPT(t[DeptId] ≠ v[DeptId]))} SC CB
(II) {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃
SC CC
v ∈ DEPT(t[DeptId] ≠ v[DeptId]))}
(III) {t | ∃u ∈ EMP(t[EmpName] = u[EmpName] ∧ ∃ SD CA
v ∈ DEPT(t[DeptId] = v[DeptId]))} SD CB

Which of the above queries are safe? [2017] SD CC

(A) (I) and (II) only SD CD
(B) (I) and (III) only SE CD
(C) (II) and (III) only SE CA
(D) (I), (II) and (III) SE CB
34. Consider a database that has the relation schema CR SF CA
(studentName, CourseName). An instance of the SF CB
schema CR is as given below.
SF CC
4.48 | Unit 4 • Databases

The following query is made on the database. 36. Consider the following two tables and four queries in
SQL.
T 1 ← pCouraseName (sStudentName =' SA ' (CR))
Book (isbn, bname), Stock (isbn, copies)
T 2 ← CR ÷ T 1 Query 1: SELECT [Link], [Link]
The number of rows in T2 is . [2017] FROM Book B INNER JOIN Stock S
35. Consider the following database table named ON [Link] = [Link];
top_scorer. Query 2: SELECT [Link], [Link]
FROM Book B LEFT OUTER
top_scorer
JOIN Stock S
player country goals
ON [Link] = [Link];
Klose Germany 16
Query 3: SELECT [Link], [Link]
Ronaldo Brazil 15 FROM Book B RIGHT OUTER
G Miiller Germany 14 JOIN Stock S
Fontaine France 13 ON [Link] = [Link];
Pelé Brazil 12 Query 4: SELECT [Link], [Link]
Klinsmann Germany 11 FROM Book B FULL OUTER
Kocsis Hungary 11 JOIN Stock S
ON [Link] = [Link];
Batistuta Argentina 10
Cubillas Peru 10 Which one of the queries above is certain to have an
Lato Poland 10
output that is a superset of the outputs of the other
three queries? [2018]
Lineker England 10
(A) Query 1 (B) Query 2
T Muller Germany 10
(C) Query 3 (D) Query 4
Rahn Germany 10
37. Consider the relations r(A, B) and s(B, C), where s ⋅ B
Consider the following SQL query: is a primary key and r ⋅ B is a foreign key referencing
SELECT [Link] FROM top_scorer AS ta s ⋅ B. Consider the query
WHERE [Link] >ALL (SELECT [Link] Q: r  (σB<5 (S))
FROM top_scorer AS tb Let LOJ denote the natural left outer-join operation.
WHERE [Link] = ‘Spain’) Assume that r and s contain no null values.
AND [Link] >ANY (SELECT [Link]
Which one of the following queries is NOT equiva-
FROM top_scorer AS tc
lent to Q? [2018]
WHERE tc. country = ‘Germany’)
(A) σB<5(r  s) (B) σB<5(r LOJ s)
The number of tuples returned by the above SQL (C) r LOJ (σB<5(s)) (D) σB<5(r) LOJ s
query is _________. [2017]

Answer Keys
Exercises
Practice Problems 1
1. A 2. B 3. C 4. (i) B   (ii) D   (iii) D 5. C 6. C 7. (i) A   (ii) C
8. (i) B   (ii) A 9. A 10. A 11. (i) A   (ii) B 12. (i) B  (ii) B  (iii) A
13. (i) A  (ii) A  (iii) A 14. (i) A  (ii) A  (iii) A 15. (i) A  (ii) A  (iii) A 16. C
17. A 18. D 19. A 20. D

Practice Problems 2
1. B 2. D 3. D 4. A 5. C 6. A 7. A 8. A 9. A 10. A
11. C 12. C 13. C 14. C 15. C 16. B 17. C 18. D 19. B 20. A

Previous Years’ Questions

1. C 2. A 3. C 4. B 5. C 6. B 7. D 8. A 9. A 10. C
11. C 12. C 13. A 14. C 15. A 16. B 17. A 18. A 19. D 20. B
21. 19 22. A 23. C 24. A 25. D 26. D 27. D 28. 2 29. C 30. A
31. B 32. 2.6 33. D 34. 4 35. 7 36. D 37. C
 Chapter 3
Normalization

LEARNING OBJECTIVES

 Normalization  Second normal form

 Anomalies  Third normal form
 First normal form  Higher normal forms (Boyce-Codd normal form)
 Functional dependency  Fifth normal form
 Inference rules  Courses

NormaliZatioN requirements of the preceding forms have been met. Many rela-
tional database designers feel that, if their tables are in third nor-
Database design theory includes design standards called normal
mal form, most common design problems have been addressed.
forms. The process of making data and tables match these stand-
However, the higher-level normal forms can be of use and are
ards is called normalizing data or data normalization. By normal-
included here.
izing data, we eliminate redundant information and organize table
Database normalization is the process of removing redundant data
to make it easier to manage the data and make future changes to
from tables to improve storage efficiency, data integrity and scalability.
the table and database structure. This process removes the inser-
tion, deletion, and modification anomalies. In normalizing your 1. In the relational model, methods exists for quantifying how
data, we usually divide large tables into smaller, easier to maintain efficient a database is, these classifications are called q′.
tables. We can then use the technique of adding foreign keys to 2. Normalization generally involves splitting existing tables
enable connections between the tables. into multiple ones, which must be rejoined (or) linked each
Data normalization is part of the database design process and time a query is issued.
is neither specific nor unique to any particular RDBMS. These 3. Edgar F. Codd originally established three normal forms: 1NF,
are in order, such as first, second, third, Boyce-Codd, fourth, and 2NF, 3NF. There are others also, but 3NF is widely considered
fifth normal forms. Each normal form represents an increasingly to be sufficient for most applications, most tables when
stringent set of rules; that is, each normal form assumes that the reaching 3NF are also in BCNF (Boyce–Codd normal form).

Table 1
Title Author 1 Author 2 I SBN Subject Pages Publisher
Database system concepts Abraham Silber schatz Henry F. Korth 0072958863 My SQL, computers 1160 McGraw-Hill
OS concepts Abraham Silberschatz Henry F. Korth 0471694665 Computers 990 McGraw-Hill

Anomalies
Problems: An anomaly is a variation that differs in some way from what is
1. This table is not very efficient with storage. said to be normal, with respect to maintaining a database.
2. This design doesn’t protect data integrity. 1. The basic operations performed on Databases are Record
3. This table doesn’t scale well. insertion, Record updation, Record deletion.
4.50 | Unit 4 • Databases

2. It is desirable for these operations to be straight If we delete a tuple where SNo = S43, he is the only (or) last
forward and efficient. student in the accounts department, we will lose data about
3. When relations are not fully normalized they exhibit student ‘S43, Arun’ as well as data about Accounts course
anomalies. that is ‘C9608, Accounts’.
4. The design goal of database is too easily to understand
Updation anomaly An updation anomaly occurs when one
and to maintain.
or more instances of duplicated data are updated but not all.
5. Anomalies are problems that occur in un-normalized
databases where all the data is stored in one table. Example: Consider the ‘course’ table given in the above
example.
If we want to update course – No (Cno) of sales C9201
Types of anomalies to C8686, in the course table.
There are three types of anomalies that can arise in the data-
1. It might happen that, the tuple with S No = S41
base because of redundancy as follows:
updated its CNo to C8686, but not the tuple with SNo
1. Insertion anomaly = S43.
2. Deletion anomaly 2. Inconsistency occurs in the table, because for the same
3. Updation anomaly course sales we have 2 different course Numbers.
Insertion anomaly An insertion anomaly occurs when par- Determining keys For a table ‘R’, its schema R consists of
ticular attributes cannot be inserted into the database with- all attributes of R, we say X is a key to R
out the presence of other attributes. if X → R means
Example: Consider the following table: Sales X determines R
Sales-Rep-Id Name Hire-Date Client R is dependent upon X
1 Ana 1/1/2015 Madison If you know x then you know R
2 Sudha 2/4/2014 Peterson
Example: Consider a relation schema R(ABCDE) and the
3 Joey 3/2/2014 John
functional dependencies:
* New
AC → D
B→E
Insertion anomaly occurs in the above table which stores
records for a company’s sales representatives and the clients DA → B
for whom they are responsible. The closure of AC determines all the attributes present in
Relation R, so the key for R is ‘AC’.
1. It is not possible to add records for newly hired Sales
representatives until they have been assigned to one AC+ =
{AC} (self determination)
or more clients.
2. If we insert a record for newly hired, client column {ACD} (AC → D)
will be NULL, which is a required field for the table. {ACDB} (DA → B)
3. It is not possible to record newly hired in the table
during training. {ACDBE} (B → E)
\ key = AC
Deletion anomaly Deletion anomaly occurs when some
particular attributes are lost because of the deletion of other Any attribute which does not appear on the right-hand-side
attributes. of a given functional dependency appears in any one of the
candidate keys.
Example: Consider the following table ‘course’.
1. From the above example, neither A (or) C appears in
S No C No S Name Course
the right hand side of any functional dependency.
S41 C9201 John Sales
S42 C9401 Brat Finance
S40 C9201 Amit Sales
First Normal Form (1NF)
S43 C9608 Arun Accounts In Table 1, we have two violations of 1NF such as:
1. More than one author field and
Execute the following SQL query: 2. Subject field contains more than one piece of
Delete * information with more than one value in a single
From course field; thus, it would be very difficult to search for all
Where S No = S43 books on a given subject.
 Chapter 2 • Normalization | 4.51

Table 2 1NF table

Title Author ISBN Subject Pages Publisher

Database system concept Abrahem Silbers Chatt 0072958863 My SQL 1160 McGraw-Hill
Database system concept Henry K. Forth 0072958863 Computers 1160 McGraw-Hill
OS concepts Henry K. Forth 0471694665 Computers 990 McGraw-Hill
OD concepts Abraham Silber Schatz 0471694665 Computers 990 McGraw-Hill

In Table 2, we have two rows for a single book. Additionally, Table 5 Book table
we would be violating the second NF. A better solution to the ISBN Title Pages Publisher
problem would be to separate the data into separate tables—
00729 Database System 1160 McGraw-Hill
an author table and a subject table to store our information, 58863 Concepts
removing that information from the book table.
04716 OS concepts 990 McGraw-Hill
Table 3 Subject table 94665

Subject–ID Subject
Each table has a primary key, used for joining tables together
1 My SQL
when querying the data.
2 computers A table is in first normal form (1NF) if there are no
Table 4 Author table
repeating groups. A repeating group is a set of logically
related fields or values that occur multiple times in one
Author–ID Last Name First name record. The sample tables below do not comply with first
1 Silberschatz Abraham normal form. Look for fields that contain too much data and
2 Korth Henry repeating group of fields.

EMPLOYEES_PROJECTS_TIME
A table with fields containing too much data.
Employee ID Name Project Time
EN1-26 Sean O’Brien 30-452-T3, 30-457-T3, 32-244-T3 0.25, 0.40, 0.30
EN1-33 Amy Guya 30-452-T3, 30-382-TC, 32-244-T3 0.05, 0.35, 0.60
EN1-35 Steven Baranco 30-452-T3, 31-238-TC 0.15, 0.80
EN1-36 Elizabeth Roslyn 35-152-TC 0.90
EN1-38 Carol Schaaf 36-272-TC 0.75
EN1-40 Alexandra Wing 31-238-TC, 31-241-TC 0.20, 0.70

The example above is also related to another design issue, Why is this table design a problem?
namely, that each field should hold the smallest meaning- There would be no way to sort by last names or to know
ful value and that there should not be multiple values in a which allocation of time belonged to which project.
single field.

EMPLOYEES_PROJECTS_TIME
Table 5 A table with repeating groups of fields.

Emp ID Last Name First Name Project1 Time1 Project2 Time2 Project3 Time3
EN1-26 O’Brien Sean 30-452-T3 0.25 30-457-T3 0.40 32-244-T3 0.30
EN1-33 Guya Amy 30-452-T3 0.05 30-382-TC 0.35 32-244-T3 0.60
EN1-35 Baranco Steven 30-452-T3 0.15 31-238-TC 0.80
EN1-36 Roslyn Elizabeth 35-152-TC 0.90
EN1-38 Schaaf Carol 36-272-TC 0.75
EN1-40 Wing Alexandra 31-238-TC 0.20 31-241-TC 0.70
4.52 | Unit 4 • Databases

If an employee was assigned to a fourth project, you would EMPLOYEES

have to add two new fields to the table. Also, it would be
EmployeeID Last Name First Name
very difficult to total the amount of time devoted to a par-
ticular project. EN1-26 O’Brien Sean
The design problems addressed are very common, EN1-33 Guya Amy
particularly among new designers who are accustomed EN1-35 Baranco Steven
to tracking data in a spreadsheet. Often, when building a EN1-36 Roslyn Elizabeth
spreadsheet, we arrange the data horizontally, laying it out EN1-38 Schaaf Carol
across the spreadsheet. When designing tables, we have to EN1-40 Wing Alexandra
think more vertically. Similar data belongs in the same col-
umn or field with a single value in each row.
Now we will take the table you saw above and redesign it PROJECTS_EMPLOYEES_TIME
so it will comply with first normal form.
Project Num EmployeeID Time
Look at the repeating groups of data. Identify tables and
fields that will hold this data without the repeating groups. 30-328-TC EN1-33 0.35
Think vertically and remember that similar data belongs in 30-452-T3 EN1-26 0.25
the same field. 30-452-T3 EN1-33 0.05
Enter the sample data from the table to make sure you 30-452-T3 EN1-35 0.15
don’t have repeating groups. If necessary, include foreign 31-238-TC EN1-35 0.80
key field(s) to connect the tables.
30-457-T3 EN1-26 0.40
31-238-TC EN1-40 0.20
EMPLOYEES
31-241-TC EN1-40 0.70
EmployeeID Last Name First Name 32-244-T3 EN1-33 0.60
EN1-26 O’Brien Sean 35-152-TC EN1-36 0.90

EN1-33 Guya Amy 36-272-TC EN1-38 0.75

EN1-35 Baranco Steven If an employee was assigned to an additional project, it

EN1-36 Roslyn Elizabeth would involve merely adding a new record. Also, it would
be much easier to search for a particular project number as
EN1-38 Schaaf Carol
they are all held in a single column.
EN1-40 Wing Alexandra

Functional Dependency
PROJECTS_EMPLOYEES_TIME A functional dependency is a relationship between fields so
that the value in Field A determines the value in Field B, and
Project Num EmployeeID Time there can be only one value in Field B. In that case, Field B
30-328-TC EN1-33 0.35 is functionally dependent on Field A. Consider the follow-
ing sample table:
30-452-T3 EN1-26 0.25
30-452-T3 EN1-33 0.05 Airport City
30-452-T3 EN1-35 0.15 National Washington, DC

31-238-TC EN1-35 0.80 JFK New York

LaGuardia New York
30-457-T3 EN1-26 0.40
Logan Boston
31-238-TC EN1-40 0.20
Dulles Washington, DC
31-241-TC EN1-40 0.70
32-244-T3 EN1-33 0.60 Each airport name is unique and each airport can be in only
35-152-TC EN1-36 0.90
one city. Therefore, City is functionally dependent on Airport.
The value in the Airport field determines what the value will
36-272-TC EN1-38 0.75
be in the City field (making Airport the determinant field)
and there can be only one value in the City field. This does
Mark the primary key field(s) and foreign keys in each table. not need to work in the reverse. As shown in the table, a city
Shown below with * indicating the Primary key. can have more than one airport, so Airport is not functionally
 Chapter 2 • Normalization | 4.53

dependent on City; the value in City does not necessarily

IR 1 (reflexive rule): if X ⊇ Y , then X → Y
determine what the value in Airport will be.
IR 2 (Augmentation rule): {X → Y } = XZ → YZ
You will sometimes see a functional dependency written
IR 3 (transitive rule): {X → Y, Y → Z} = X → Z
in this format:
IR 4 (complementation rule): {X → → Y} = {X → →
Determinant field(s) → Functionally dependent field
(R – (X ∪ Y ))}
as in: IR5 (augmentation rule for MVD’s): if X → → y and W
Airport → City → Z then WX ⊇ YZ
Functional dependency describes the relationship bet­ IR6 (transitive rule for MVD’s):
ween attributes in a relation. {X → → Y, Y → → Z} = X → → (Z – Y )
Example: If A and B are attributes of relation R, and B is
functionally dependent on A (A → B) if each value of A is
associated with one value of B. Second Normal Form
A table is said to be in second normal form if it is in first
B is functionally normal form and each non-key field is functionally depend-
A B
Dependent on A ent on the entire primary key.
Look for values that occur multiple times in a non-key field.
Determinant refers to the attributed (or) group attributes on This tells us that we have too many fields in a single table.
the left-hand side of the arrow of a functional dependency. Example: In the example below, see all the repeating values
in the name and Project Title fields. This is an inefficient way
Inference Rules to store and maintain data. In a well-designed database, the
The following inference rules IR 1 through IR 6 form a only data that is duplicated is in key fields used to connect
complete set for inferring functional and multi-valued tables. The presumption is that the data in key fields will
dependencies from a given set of dependencies rarely change, while the data in non-key fields may change
Assume that all attributes are included in a ‘universal’ frequently.
relation schema R = {A1, A2,…AN) and that X, Y, Z and W A table with a multifield primary key and repeating data
are subsets of R. in non-key fields

EmployeeID Last Name First Name Project Number Project Title

EN1-26 O’Brien Sean 30-452-T3 STAR manual

EN1-26 O’Brien Sean 30-457-T3 ISO procedures
EN1-26 O’Brien Sean 31-124-T3 Employee handbook
EN1-33 Guya Amy 30-452-T3 STAR manual
EN1-33 Guya Amy 30-482-TC Web Site
EN1-33 Guya Amy 31-241-TC New catalogue
EN1-35 Baranco Steven 30-452-T3 STAR manual
EN1-35 Baranco Steven 31-238-TC STAR prototype
EN1-36 Roslyn Elizabeth 35-152-TC STAR pricing
EN1-38 Schaaf Carol 36-272-TC Order system
EN1-40 Wing Alexandra 31-238-TC STAR prototype
EN1-40 Wing Alexandra 31-241-TC New catalogue

If a ProjectTitle changed, we would have to edit it in containing the titles and an employee was assigned to only
several records. And what would happen in this table if the that project, you would also delete that employee’s record,
EmployeeID was part of the primary key and we wanted something that we may not want to do.
to add a new ProjectNum and ProjectTitle even though no In the above example, the asterisks indicate the fields
employees had yet been assigned? that make up the primary key of this table as it now stands.
The primary key cannot contain a null value so you A multifield primary key is necessary because neither the
couldn’t add the new project. Additionally, if a project EmployeeID nor the ProjectNum fields contain unique values.
ended and you wanted to delete it, you would have to delete The reason there are repeated values in LastName,
the individual values because, if we deleted the records FirstName, and ProjectTitle is that these fields are dependent
4.54 | Unit 4 • Databases

on only part of the primary key. The value in EmployeeID Now we’ll take the table above and design new tables
determines what the value in LastName will be, but the that will eliminate the repeated data in the non-key fields.
value in ProjectNum has nothing to do with it. Similarly, the
value in ProjectNum determines the value in ProjectTitle, 1. To decide what fields belong together in a table, think
but EmployeeID does not. These non-key fields relate to about which field determines the values in other fields.
only part of the primary key. They are not functionally Create a table for those fields and enter the sample data.
dependent on the entire primary key. 2. Think about what the primary key for each table would
The solution to this lies in breaking the table into smaller be and about the relationship between the tables. If
tables that do meet second normal form. You will find that necessary, add foreign keys or a junction table.
more tables are the solution to most problems encountered 3. Mark the primary key for each table and make sure
during data normalisation. that you don’t have repeating data in non-key fields.

EMPLOYEES PROJECTS
EmployeeID Last Name First Name Projec tNum Project Title
EN1-26 O’Brien Sean 30-452-T3 STAR manual
EN1-33 Guya Amy
30-457-T3 ISO procedures
EN1-35 Baranco Steven
30-482-TC Web site
EN1-36 Roslyn Elizabeth
31-124-T3 Employee handbook
EN1-38 Schaaf Carol
31-238-TC STAR prototype
EN1-40 Wing Alexandra
31-238-TC New catalog
35-152-TC STAR pricing

EMPLOYEES_PROJECTS 36-272-TC Order system

EmployeeID Project Num Examine the tables to make sure there are no repeating values
EN1-26 30-452-T3
in non-key fields and that the value in each non-key field is
determined by the value(s) in the key field(s). This removes
EN1-26 30-457-T3
the modification anomaly of having the repeated values.
EN1-26 31-124-T3
EN1-33 30-328-TC
EN1-33 30-452-T3 Third Normal Form
EN1-33 32-244-T3 A table is said to be in third normal form if it is in second
EN1-35 30-452-T3 normal form (2NF) and there are no transitive dependencies.
EN1-35 31-238-TC
A transitive dependency is a type of functional depend-
ency in which the value in a non-key field is determined
EN1-36 35-152-TC
by the value in another non-key field and that field is not a
EN1-38 36-272-TC candidate key. Again, look for repeated values in a non-key
EN1-40 31-238-TC field as in the following example.
EN1-40 31-241-TC
A table with a single field primary key and repeating
values in non-key fields.

Project Num Project Title Project Mgr Phone

30-452-T3 STAR manual Garrison 2756
30-457-T3 ISO procedures Jacanda 2954
30-482-TC Web site Friedman 2846
31-124-T3 Employee handbook Jones 3102
31-238-TC STAR prototype Garrison 2756
31-241-TC New catalog Jones 3102
35-152-TC STAR pricing Vance 3022
36-272-TC Order system Jacanda 2954
 Chapter 2 • Normalization | 4.55

The phone number is repeated each time a manager’s key). This normal form applies to situations where you have
name is repeated. It is dependent on the manager, which is overlapping candidate keys.
dependent on the project number (a transitive dependency). If a table has no non-key fields, it is automatically in
The Project Manager field is not a candidate key, because BCNF (Figure 1). Look for potential problems in updating
the same person manages more than one project. Again, the existing data (modification anomaly) and in entering new
solution is to remove the field with repeating data to a sepa- data (insertion anomaly).
rate table. Imagine that we were designing a table for a college
Take the above table and create new tables to fix the to hold information about courses, students, and teaching
problem. assistants. We have the following business rules:
1. Think about which fields belong together and create 1. Each course can have many students.
new tables to hold them. 2. Each student can take many courses.
2. Enter the sample data and check for unnecessarily 3. Each course can have multiple teaching assistants (TAs).
(not part of primary key) repeated values. 4. Each TA is associated with only one course.
3. Identify the primary key for each table and, if 5. For each course, each student has one TA.
necessary, add foreign keys. Some sample data:
COURSES_STUDENTS_TA’s
PROJECTS
CourseNum Student TA
Project Num Project Title Project Mgr
ENG101 Jones Clark
30-452-T3 STAR manual Garrison
ENG101 Grayson Chen
30-457-T3 ISO procedures Jacanda
ENG101 Samara Chen
30-482-TC Web site Friedman
MAT350 Grayson Powers
31-124-T3 Employee handbook Jones
MAT350 Jones O’Shea
31-238-TC STAR prototype Garrison
MAT350 Berg Powers
31-241-TC New catalog Jones
35-152-TC STAR pricing Vance To uniquely identify each record, we could choose
36-272-TC Order system Jacanda CourseNum + Student as a primary key. This would sat-
isfy third normal form also because the combination of
MANAGERS CourseNum and Student determines the value in TA.
Another candidate key would be Student + TA. In this case,
Project Manager Phone you have overlapping candidate keys (Student is in both).
Friedman 2846 The second choice, however, would not comply with third
Garrison 2756 normal form, because the CourseNum is not determined by
Jacanda 2954
the combination of Student and TA; it only depends on the
value in TA. This is the situation that Boyce-Codd normal form
Jones 3102
addresses; the combination of Student + TA could not be consid-
Vance 3022
ered to be a candidate key.
Reexamine your tables to make sure there are no unneces- If we wanted to assign a TA to a course before any stu-
sarily repeating values in non-key fields and that the value in dents enrolled, we couldn’t because Student is part of the
each non-key field is determined by the value(s) in the key primary key. Also, if the name of a TA changed, would
field(s). In most cases, 3NF should be sufficient to ensure have to update it in multiple records. If assume have just
that your database is properly normalised. these fields, this data would be better stored in three tables:
one with CourseNum and Student, another with Student
and TA, and third with CourseNum and TA.
Higher Normal Forms
COURSES
(Boyce–Codd Normal Form) Course Num Student
A table is in third normal form (3NF), and all determinants
ENG101 Jones
are candidate keys.
ENG101 Grayson
Boyce–Codd normal form (BCNF) can be thought of
ENG101 Samara
as a ‘new’ third normal form. It was introduced to cover
MAT350 Grayson
situations that the ‘old’ third normal form did not address.
The mean of a determinant (determines the value in another MAT350 Jones
field) and candidate keys (qualify for designation as primary MAT350 Berg
STUDENTS
4.56 | Unit 4 • Databases

Student TA *CourseNum *TA

Jones Clark
ENG101 Clark
Grayson Chen
ENG101 Chen
Samara Chen
Grayson Powers MAT350 O’Shea
Jones O’Shea MAT350 Powers
Berg Powers
Figure 1 Tables that comply with BCNF.
TA’s

Fourth Normal Form data maintenance problems that causes and you would have
trouble with deletion anomalies.
A table is in Boyce-Codd normal form (BCNF) and there
The Star and the Producer really aren’t logically related.
are no multi-valued dependencies.
The Movie determines the Star and the Movie determines
A multi-valued dependency occurs when, for each value
the Producer. The answer is to have a separate table for each
in field A, there is a set of values for field B and a set of val-
of those logical relationships: one holding Movie and Star
ues for field C but fields B and C are not related.
and the other with Movie and Producer, as shown below:
Look for repeated or null values in non-key fields. A multi-
valued dependency occurs when the table contains fields that
are not logically related. An often used example is the fol- STARS
lowing table: *Movie *Star
Once Upon a Time Julie Garland
MOVIES
Once Upon a Time Mickey Rooney
Movie Star Producer
Moonlight Humphrey Bogart
Once Upon a Time Julie Garland Alfred Brown
Moonlight Julie Garland
Once Upon a Time Mickey Rooney Alfred Brown
Once Upon a Time Julie Garland Muriel Humphreys PRODUCERS
Once Upon a Time Mickey Rooney Muriel Humphreys
*Movie *Producer
Moonlight Humphrey Bogart Alfred Brown
Once Upon a Time Alfred Brown
Moonlight Julie Garland Alfred Brown
Once Upon a Time Muriel Humphreys
A movie can have more than one star and more than one Moonlight Alfred Brown
producer. A star can be in more than one movie. A producer
can produce more than one movie. The primary key would Above, showing tables that comply with 4NF
have to include all three fields, and so this table would be in Below is another example of a common design error, and
BCNF. But you have unnecessarily repeated values, with the it’s easily spotted by all the missing or blank values.

PROJECTS_EQUIPMENT
Dept Code Project Num Project Mgr ID Equipment Property ID
IS 36-272-TC EN1-15 CD-ROM 657
IS VGA desktop monitor 305
AC 35-152-TC EN1-15
AC Dot-matrix printer 358
AC Calculator with tape 239
TW 30-452-T3 EN1-10 486 PC 275
TW 30-457-T3 EN1-15
TW 31-124-T3 EN1-15 Laser printer 109
TW 31-238-TC EN1-15 Handheld scanner 479
RI Fax machine 775
MK Laser printer 858
MK Answering machine 187
TW 31-241-TC EN1-15 Standard 19200 bps modem 386
SL 486 Laptop PC 772
SL Electronic notebook 458
 Chapter 2 • Normalization | 4.57

A table with many null values (Note: It also does not com- A cyclic dependency can occur only when you have a
ply with 3NF and BCNF). multifield primary key consisting of three or more fields.
It is the same problem here because not all of the data is For example, let’s say your primary key consists of fields
logically related. As usual, the answer is more tables: one to A, B, and C. A cyclic dependency would arise if the val-
hold the information on the equipment assigned to depart- ues in those fields were related in pairs of A and B,
ments (with PropertyID as the primary key) and another B and C, and A and C.
with projects and departments. We would now the business Fifth normal form is also called projection-join normal
rules to know whether a project might involve more than form. A projection is a new table holding a subset of fields
one department or manager and be able to figure out the from an original table. When properly formed projections
primary key. Assuming a project can have only one man- are joined, they must result in the same set of data that was
ager and be associated with only one department, the tables contained in the original table.
would be as follows: Look for the number of records that will have to be added
or maintained
EQUIPMENT Following is some sample data about buyers, the prod-
ucts they buy, and the companies they buy from.
*Property ID Equipment DeptCode
657 CD-ROM IS BUYING
305 VGA desktop monitor IS
Buyer Product Company
358 Dot-matrix printer AC
Chris Jeans Levi
239 Calculator with tape AC
Chris Jeans Wrangler
275 486 PC TW
Chris Shirts Levi
109 Laser printer TW
Lori Jeans Levi
479 Handheld scanner TW
775 Fax machine RI Figure 3 A table with cyclic dependencies.

858 Laser printer MK

The primary key consists of all three fields. One data
187 Answering machine MK maintenance problem that occurs is that you need to add
Standard 19200 bps a record for every buyer who buys a product for every
386 TW
modem company that makes that product or they can’t buy from
772 486 Laptop PC SL them. That may not appear to be a big deal in this sam-
ple of two buyers, two products, and two companies
458 Electronic notebook SL
(2 × 2 × 2 = 8 total records). But what if we went to 20
buyers, 50 products, and 100 companies (20 × 50 × 100 =
PROJECTS_EQUIPMENT 100,000 potential records)? It quickly gets out of hand and
becomes impossible to maintain.
Project Num Project Mgr ID Dept Code We might solve this by dividing this into the following
two tables:
36-272-TC EN1-15 IS
35-152-TC EN1-15 AC BUYERS
30-452-T3 EN1-10 TW Buyer Product
30-457-T3 EN1-15 TW Chris jeans
31-124-T3 EN1-15 TW Chris shirts
31-238-TC EN1-15 TW
Lori jeans
31-241-TC EN1-15 TW

Figure 2 Tables that eliminate the null values and comply with PRODUCTS
4NF.
Product Company
jeans Wrangler
Fifth Normal Form jeans Levi
A table is in fourth normal form (4 NF) and there are no shirts Levi
cyclic dependencies.
4.58 | Unit 4 • Databases

However, if you joined the two tables above on the Product PRODUCTS
field, it would produce a record not part of the original data *Product *Company
set (it would say that Lori buys jeans from Wrangler). This jeans Wrangler
is where the projection-join concept comes in. jeans Levi
The correct solution would be three tables: shirts Levi

BUYERS
COMPANIES
*Buyer *Product *Buyer *Company
Chris jeans Chris Levi
Chris shirts Chris Wrangler
Lori jeans Lori Levi
Figure 4 Tables that comply with 5NF.

When the first two tables are joined by Product and the result joined to the third table by Buyer and Company, the result
is the original set of data.

Exercises
Practice Problems 1 Which functional dependencies are violating 2NF
Directions for questions 1 to 20: Select the correct alterna- property?
tive from the given choices. (A) FD1 (B) FD2
(C) FD3 (D) Both A and B
1. Consider the given functional dependencies
A→B 4. Consider the given relation
BC → DE EMPLOYEE-DEPARTMENT
AEF → G EName ENo DOB Address DNo. DName DManager

Which of the following is true?

FD1
(A) Functional dependency ACF→ DG implied by the set FD2
(B) Functional dependency ACF → DG cannot be im-
plied by the set Which functional dependencies are violating 3NF ?
(C) Functional dependency AB → G implied by the set (A) FD1 (B) FD2
(D) Both (B) and (C) (C) Both (D) None of these
2. Consider the given relation 5. Consider the given relation R(A, B, C, D)and functional
dependencies:
DNAME DNO MGRNO LOCATION
FD = (AB → C
RESEARCH 5 333 {BANGLORE,DELHI,
HYDERABAD} C→B
ADMINISTRATION 4 987 {CHENNAI} C → D)
EXECUTIVES 1 885 {HYDERABAD} Determine the key, prime attributes and non-prime
attributes.
Department (A) {A}, {AB}, {CDE}
The given relation is (B) {AB, AC}, {ABC}, {D}
(A) is not in 1NF (B) in 1NF (C) {AB, BC}, {ABC}, {D}
(C) in 2NF (D) in 3NF (D) {AB, AC}, {AB}, {D}
3. Consider the given Relational scheme 6. Consider the given relation and functional dependencies
Student-project R(ABCDE)
RNo. Proj-No Hours Stu-Name Proj-Name Proj-Location FD = (ABD → C
BC → D
FD1 CD → E)
FD2 Determine the key, prime attributes, non-prime attrib-
FD3
utes and the normal form of the relation?
 Chapter 2 • Normalization | 4.59

(A) {AB, AD}, {ABCD}, {E} (A) 1NF (B) 2NF

(B) {ABC, ABD}, {ABCD}, {E} (C) 3NF (D) BCNF
(C) {AB, AD}, {ABC}, {DE}
11. Consider the given functional dependencies:
(D) {ABC, ABD}, {AB}, {CDE}
AB → CD
7. Consider the given relation and functional dependencies
R(ABC) AF → D
FD = (AB → C DE → F
C → A) C       → G
The relation is in which normal form?
F →E
(A) 1NF (B) 2NF
(C) 3NF (D) BCNF G →A
8. Consider the given relation and its functional Which of the following is false?
dependencies: (A) {CF}+ = {ACDEFG}
R(ABCDE) (B) {BG}+ = {ABCDG}
(C) {AF}+ = {ACDEFG}
FD = (AB → C
(D) {AB}+ = {ABCDG}
C→E
B →D 12. What should be the key to make the given relation
E → A) to be in BCNF? The dependencies for the following,
‘Grades’ relation are GRADES (student-Id, course#,
The relation is further decomposed into two relations:
semester#, Grade) student-Id, course#, semester# →
R1(BCD), R2(ACE) Grade
(A) Decomposition is lossy and dependency preserving (A) student-Id
(B) Decomposition is lossless and dependency pre- (B) course#
serving (C) semester#
(C) Decomposition is lossy and not dependency pre- (D) student-Id, course#, semester #
serving
(D) Decomposition is lossless and not dependency 13. What normal from is the following relation in?
preserving STORE_ITEM (SKU, promotionID, vendor, style,
9. Consider the following relational instance: price)
SKU, promotionID → vendor, style, price
X Y Z
SKU → vendor, style
1 4 2
(A) 1NF (B) 2NF
1 5 3
(C) 3NF (D) 4NF
1 6 3
3 2 2 14. What normal form is the following relation in?
Only H, I can act as the key
Which of the following functional dependencies are STUFF (H, I, J, K, L, M, N, O)
satisfied by the instance? H, I → J,K,L
(A) xy → z and z → y J→M
(B) yz → x and y → z
K→N
(C) yz → x and x → z
(D) xz → y and y → x L → O?
(A) 1NF (B) 2NF
10. Consider the following functional dependencies:
(C) 3NF (D) BCNF
DOB → Age
Age → Eligibility 15. What normal form the following relation is in?
Name → RNo STUFF2(D, O, N, T, C, R, Y )
RNo → Name
D, O → N, T, C, R, Y
CourseNo → CourseName
CourseNo → Instructor C, R → D
(RNo, CNo) → Grade D → N?
The relation (RNo, Name, DOB, Age) is in which nor- (A) 1NF (B) 2NF
mal form? (C) 3NF (D) BCNF
4.60 | Unit 4 • Databases

16. The given table is in the BCNF form, convert it to the 18. Which of the following FDs are satisfied by the instance
4th normal form. from the below relation:

Employee Skill Language A B C

Jones Electrical French 2 8 4
Jones Electrical German 2 10 6
Jones Mechanical French 2 12 6
Jones Mechanical German
6 4 4
Smith Plumbing Spanish
(A) AB → C and C → B
(A) (B) BC → A and B → C
Employee Skill
(C) BC → A and A → C
(D) AC → B and B → A
(B) 19. Consider the following database:
Employee Language
Course # → Title
Course # time → location
Emp – ID → T –Name salary
(C) Skill Language is in
(A) 3NF (B) 2NF
(C) 1NF (D) BCNF
(D) Both A and B
20. Consider the following schema
17. For a database relation x(a, b, c, d ), where all the A = (w, x, y, z) and the dependencies are
domains of a, b, c, d, include only atomic values, only
W → X, X → Y, Y → Z, and Z → W
the following FDs and those that can be inferred from
them hold. Let A = (A1 and A2) be a decomposition such that
A1 ∩ A2 = f
a → b, c → d
the relation is The decomposition is
(A) In 1st NF but not in 2nd NF (A) In 1NF and in 2NF
(B) In 2nd NF but not in 3rd NF (B) In 2NF and not in 3NF
(C) In 2nd NF (C) In 2NF and in 3NF
(D) In 3rd NF (D) Not in 2NF and in 3NF

Practice Problems 2 4. A relation will be in 2NF, if we

Directions for questions 1 to 20: Select the correct alterna- (A) remove repeating groups
tive from the given choices. (B) remove partial dependency
(C) remove transitive dependency
1. Integrity constraints ensures that changes made to the (D) have overlapping candidate key
database by authorized users do not result in
(A) Loss of FDs 5. Relation R =(A, B, C, D) with AB as primary key, choose
(B) Loss of keys the FD so that R should be in 2NF but not in 3NF.
(C) Loss of tables (A) D → C (B) AB → C
(D) Loss of data consistency (C) AB → D (D) A → B
2. Relation R = ( A, B, C , D) with AB as primary key. 6. If a relation is in 2NF, then it can be in 3NF by removing
Choose one FD such that R should be in 1NF but not in (A) repeating groups
2NF (B) partial dependencies
(A) AB → C (C) transitive dependencies
(B) AB → D (D) overlapping dependencies
(C) A → D
(D) AB → CD 7. BCNF can be achieved from 3NF by removing
3. A normalized relation (1NF) can be retrieved from (A) repeating groups
unnormalized relation by removing (B) partial dependencies
(A) repeating groups (B) duplicate tuples (C) transitive dependencies
(C) transitive dependency (D) primary key (D) overlapping dependencies
 Chapter 2 • Normalization | 4.61

8. Which one of the following is not possible? 16. For a database relation x(a, b, c, d), where all the
(A) Relation is in BCNF but not in 4NF domains of a, b, c, d, include only atomic values, only
(B) Relation is in 3NF but not in BCNF the following FDs and those that can be inferred from
(C) Relation is in 2NF but not in 3NF them hold.
(D) Relation is in 3NF but not in 2NF a → b, c → d
Common data for questions 9 and 10: Let R be a relation The relation is decomposed into R1(ab), R2(cd). Which of
schema R (A, B, C, D); the following is true, The decomposition
F = {AB → CD; C → A} F is the set of functional (A) is dependency preserving
dependencies (B) is not dependency preserving
9. How many prime attributes are there? (C) is loss less
(A) 1 (B) 2 (D) Both A and C
(C) 3 (D) 4 17. Which of the following FDs are satisfied by the instance
10. The highest normal form of the above relation is from the below relation?
(A) 1NF (B) 2NF A B C
(C) 3NF (D) 4NF
4 12 8
Linked answer questions 4 14 10
11. For a given relation schema R = {A, B, C, D, E} 4 16 10
A → BC
10 8 8
CD → E
B→D (A) AB → C and C → B
E→A (B) BC → A and B → C
Which of the following is not a candidate key? (C) BC → A and A → C
(A) A (B) B (D) AC → B and B → A
(C) E (D) BC 18. Indicate which of the following statements are false: ‘A
12. For the above answer, what is the closure? relational database, which is in 3NF still have undesirable
(A) BD (B) ABC data redundancy because there may exist.
(C) ABCDE (D) BC (A) Below all
13. Consider the following functional dependencies: (B) Non trivial FDs involving prime attributes on the
A→B right side.
C→D (C) Non-trivial FDs involving prime attributes on the
B→E left side
F→A (D) Non-trivial FDs involving only prime attributes
The relation (A, B, C, D) is 19. Consider the following database:
(A) in second normal form, but not in third normal form SOFTWARE (software-vendor, product, Release-date,
(B) in third normal form, but not in B C N F systemReq, warranty)
(C) in B C N F FD: (software-vendor, product, Releasedate) → system
(D) None of the above Req, price, Warranty.
Common data for questions 14 and 15: Which of the following are non–prime attributes?
R = (A, B, C, D, E, F ) (A) SystemReq
FDs = A → B (B) Price
C → DF (C) Warranty
AC → E (D) All the above
D→F 20. Consider a relation schema R (A, B, C, D, E, X, Y) with
14. Determine the key from the given FDs: the following FDs
(A) AB (B) AC F = {0 → A, XD → C, DA → B, A → X, XE → B, E →
(C) ACB (D) ACD A, B → D, DA → B, EB → C, AB → C, Y → B, C → B}
15. Decompose the FDs into 2NF is in
(A) R1(AB) R2(CDF) R3(ACE) (A) 2NF
(B) R1(AB) R2(CDEF) (B) 3NF
(C) R1(ABC) R2(CDF) (C) 4NF
(D) R1(AB) R2(CD) R3(EF ) (D) BCNF
4.62 | Unit 4 • Databases

Previous Years’ Questions

1. Which one of the following statements is false? 6. The relation R is[2013]
[2007] (A) in 1NF, but not in 2NF
(A) Any relation with two attributes is in BCNF (B) in 2NF, but not in 3NF
(B) A relation in which every key has only one at- (C) in 3NF, but not in BCNF
tribute is in 2NF (D) in BCNF
(C) A prime attribute can be transitively dependent
on a key in a 3NF relation. 7. Assume that in the suppliers relation above, each
(D) A prime attribute can be transitively dependent supplier and each street within a city has a unique
on a key in a BCNF relation. name, and (sname, city) forms a candidate key. No
other functional dependencies are implied other
2. Consider the following relational schemas for a than those implied by primary and candidate keys.
library database: Which one of the following is true about the above
Book (Title, Author, Catalog_ no, Publisher, Year, schema?[2009]
Price) (A) The schema is in BCNF
Collection (Title, Author, Catalog_ no) (B) The schema is in 3NF but not in BCNF
with the following functional dependencies: (C) The schema is in 2NF but not in 3NF
I. Title Author → Catalog_no (D) The schema is not in 2NF
II. Catalog_no → Title Author Publisher Year 8. Consider the relation scheme R = (E, F, G, H, I, J, K,
III. Publisher Title Year → Price L, M, N) and the set of functional dependencies {{E,
F} → {G}, {F} → {I, J }, {E, H} → {K, L}, {K} →
Assume {Author, Title} is the key for both schemas.
{M}, {L} → {N}} on R. What is the key for R?
Which of the following statements is true? [2008]
(A) Both Book and Collection are in BCNF [2014]
(B) Both Book and Collection are in 3NF only (A) {E, F} (B) {E, F, H}
(C) Book is in 2NF and Collection is in 3NF (C) {E, F, H, K, L} (D) {E}
(D) Both Book and Collection are in 2NF only 9. Given the following two statements:
3. The following functional dependencies hold for rela- S1: Every table with two single-valued attributes is in
tions R(A, B, C) and S(B, D, E) 1NF, 2NF, 3NF and BCNF
B → A, S2: AB → C, D → E, E → C is a minimal cover for
A→C the set of functional dependencies AB → C, D →
The relation R contains 200 tuples and the relation S E, AB → E, E → C
contains 100 tuples. What is the maximum number of Which one of the following is correct?[2014]
tuples possible in the natural join R ⋈ S?[2010]
(A) S1 is true and S2 is false
(A) 100 (B) 200
(B) Both S1 and S2 are true
(C) 300 (D) 2000
(C) S1 is false and S2 is true
4. Which of the following is true?[2012]
(D) Both S1 and S2 are false
(A) Every relation in 3NF is also in BCNF
(B) A relation R is in 3NF if every non-prime attrib- 10. The maximum number of super-keys for the relation
ute of R is fully functionally dependent on every schema R (E, F, G, H) with E as the key is _____.
key of R [2014]
(C) Every relation in BCNF is also in 3NF
11. A prime attribute of a relation scheme R is an attrib-
(D) No relation can be in both BCNF and 3NF
ute that appears  [2014]
Common data questions 5 and 6: Relation R has eight (A) in all candidate keys of R
attributes ABCDEFGH, Fields of R contain only atomic (B) in some candidate key of R
values. (C) in a foreign key of R
F = {CH → G, A → BC, B → CFH, E → A, F → EG} (D) only in the primary key of R
is a set of functional dependencies (FDs) so that F+ is 12. Consider an entity-Relationship (ER) model in which
exactly the set of FDs that hold for R. entity sets E1 and E2 are connected by an m:n relation-
5. How many candidate keys does the relation R have? ship R12. E1 and E3 are connected by a 1:n (1 on the
[2013] side of E1 and n on the side of E3) relationship R13.
(A) 3 (B) 4 E1 has two single-valued attributes a11 and a12 of
(C) 5 (D) 6 which a11 is the key attribute. E2 has two single-valued
 Chapter 2 • Normalization | 4.63

attributes a21 and a22 of which a21 is the key attrib- 3 Bikaner 20
ute. E3 has two single-valued attributes a31 and a32 of 1 Churu 20
which a31 is the key attribute. The relationships do not 2 Churu 20
have any attributes. 1 Dungargarh 10
If a relational model is derived from the above ER The number of tuples returned by the following SQL
model, then the minimum number of relations that query is ______ .
would be generated if all the relations are in 3 NF is with total (name, capacity) as
_______.[2015] select district _ name, sum (capacity)
13. Consider the relation X(P, Q, R, S, T, U) with the fol- from water _ schemes
lowing set of functional dependencies group by district _ name
F = { with total _avg (capacity) as
select avg (capacity)
{P, R} → {S, T}
from total
{P, S, U} → {Q, R}
select name
}
from total, total _ avg
Which of the following is the trivial functional where total . capacity ≥ total_avg. capacity
dependency in F +, where F + is closure of F ?[2015] 16. The following functional dependencies hold true for
(A) {P, R} → {S, T} the relational schema R {V, W, X, Y, Z}:
(B) {P, R} → {R, T}
(C) {P, S} → {S} V →W
(D) {P, S, U} → {Q} VW → X
14. A database of research articles in a journal uses the Y → VX
following schema. [2016] Y→Z
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, Which of the following is irreducible equivalent for
TITLE, YEAR, PRICE) this set of set of functional dependencies? [2017]
The primary key is (VOLUME, NUMBER, (A) V → W (B) V → W
STARTPAGE,ENDPAGE) and the following func- V → X W→X
tional dependencies exist in the schema. Y → V Y →V
(VOLUME, NUMBER, STARTPAGE, ENDPAGE) Y → Z Y→Z
→ TITLE (C) V → W (D) V → W
V → X W→X
(VOLUME, NUMBER) → YEAR Y → V Y →V
(VOLUME, NUMBER, Y → X Y→X
STARTPAGE,ENDPAGE) → PRICE Y → Z Y→Z
The database is redesigned to use the following 17. Consider the following tables T1 and T2.
schemas. T1 T2
(VOLUME, NUMBER, STARTPAGE, ENDPAGE, P Q R S
TITLE, PRICE)
2 2 2 2
(VOLUME, NUMBER, YEAR)
3 8 8 3
Which is the weakest normal form that the new data-
base satisfies, but the old one does not? 7 3 3 2
(A) 1NF (B) 2NF 5 8 9 7
(C) 3NF (D) BCNF
6 9 5 7
15. Consider the following database table water_
schemes:[2016] 8 5 7 2
water_schemes 9 8
scheme_no District name Capacity
In table T1, P is the primary key and Q is the foreign
1 Ajmer 20 key referencing R in table T2 with on-delete cascade
1 Bikaner 10 and on-update cascade. In table T2, R is the primary
2 Bikaner 10 key and S is the foreign key referencing P in table Tl
4.64 | Unit 4 • Databases

with on-delete set NULL and on-update cascade. In email → rollno

order to delete record 〈3, 8〉 from table T1, the num- Schema III:
ber of additional records that need to be deleted from
Registration (rollno, courseid, marks, grade)
table T1 is __________.[2017]
Non-trivial functional dependencies:
18. Consider the following four relational schemas. For
each schema, all non-trivial functional dependencies Rollno, courseid → marks, grade
are listed. The underlined attributes are the respective Marks → grade
primary keys. Schema IV:
Schema I: Registration (rollno, courseid, credit)
Registration (rollno, courses) Non-trivial functional dependencies:
Field ‘courses’ is a set-valued attribute containing the Rollno, courseid → credit
set of courses a student has registered for.
Courseid → credit
Non-trivial functional dependency:
Which one of the relational schemas above is in 3NF
Rollno → courses but not in BCNF? [2018]
Schema II: (A) Schema I
Registration (rollno, courseid, email) (B) Schema II
(C) Schema III
Non-trivial functional dependencies:
(D) Schema IV
Rollno, courseid → email

Answer Keys
Exercises
Practice Problems 1
1. A 2. A 3. D 4. B 5. B 6. B 7. C 8. D 9. B 10. A
11. C 12. D 13. A 14. B 15. A 16. D 17. A 18. B 19. C 20. C

Practice Problems 2
1. D 2. C 3. A 4. B 5. A 6. C 7. D 8. D 9. C 10. C
11. B 12. A 13. D 14. B 15. A 16. A 17. C 18. C 19. D 20. B

Previous Years’ Questions

1. D 2. C 3. A 4. C 5. B 6. A 7. B 8. B 9. A 10. 8
11. B 12. 4 13. C 14. B 15. 2 16. A 17. 0 18. B
 Chapter 4
Transaction and Concurrency

LEARNING OBJECTIVES

 Transactions and concurrency control  Two-phase locking to ensure serializability

 Transaction  Concurrency control with time stamping methods
 Transaction properties  Concurrency control with optimistic methods
 Uncommitted data  Recoverability
 Transaction processing systems  Equivalence of schedules
 Concurrency control with locking methods  Testing for conflict serializability

introduCtion Concurrency control is the management of concurrent transac-

A transaction is a logical unit of work. It begins, with the execution tions execution. When many users are able to access the database,
of a BEGIN TRANSACTION operation, and ends with the execu- the number of concurrent transactions tends to grow rapidly; as
tion of a COMMIT or ROLLBACK operation. The logical unit of a result, concurrency control is especially important in multiuser
work that is, a transaction does not necessarily involve just a single database environments.
database operation. Rather, it involves a sequence of several such
operations as follows: transaCtion
1. Database updates are kept in buffers in main memory and A transaction is a logical unit of work that must be either entirely
not physically written to disk until the transaction commits. completed or aborted, no intermediate states are acceptable, that is,
That way, if the transaction terminates unsuccessfully, there multicomponent transactions like the previously mentioned sale,
will be no need to undo any disk updates. must not be partially completed. If you read from and/or write to
2. Database updates are physically written to disk as part of the (update) the database, you create a transaction. Another example
process of honouring the transaction’s COMMIT request. is using SELECT, to generate a list of table contents. Many real-
That way if the system subsequently crashes, we can be sure world database transactions are formed by two or more database
that there will be no need to redo any disk updates. requests. A database request is the equivalent of a single SQL
statement in an application program or transaction. Each database
Transactions and Concurrency Control request generates several input/output operations. A transaction
that changes the contents of a database must alter the database
Database transactions reflect real-world transactions that are trig-
from one consistent state to another. A consistent database state is
gered by events, such as buying a product, registering for a course, or
one in which all data integrity constraints are satisfied.
making a deposit in your checking account. Transactions are likely to
contain many parts, for example, a sales transaction consists of at least Example:
two parts. 1. Checking an account balance:
UPDATE inventory by subtracting number of units sold from SELECT ACC_NUM, ACC_BALANCE
the PRODUCT table’s available quantity on hand and UPDATE the FROM CHECKACC
ACCOUNTS RECEIVABLE table in order to bill the CUSTOMER. WHERE ACC_NUM = ‘0908110638’;
All parts of a transaction must be completed to prevent data integ- Even though we did not make any changes to the
rity problems. Therefore, executing and managing transactions are CHECKACC table, the SQL code represents a transaction,
important database system activities. because we accessed the database.
4.66 | Unit 4 • Databases

2. Registering a credit sale of 100 units of product X to Durability

customer Y in the amount of $500.00 first, product It indicates the permanence of the database’s consistent
X’s quantity on hand (QOH) needs to be reduced by state. When a transaction is completed, the database reaches
100. a consistent state, and that state cannot be lost, even in the
event of the system’s failure.
UPDATE PRODUCT
SET PROD_QOH = PROD_QOH_100
WHERE PROD_CODE = ‘x’; Transaction Management with SQL
Then, $500 needs to be added to customer Y’s The ISO standard defines a transaction model based on two
accounts receivable SQL statements: COMMIT and ROLLBACK. The standard
UPDATE ACCT_RECEIVABLE specifies that an SQL transaction automatically begins with
SET ACCT_RECEIVABLE = ACCT_BALANCE + a transaction-initiating SQL statement executed by a user
500 or program (e.g., SELECT, INSERT, UPDATE). Changes
WHERE ACCT_NUM = ‘Y’; made by a transaction are not visible to other concurrently
executing transactions until the transaction completes.
In Example 2, both the SQL, transactions must be com- When a transaction sequence is initiated, it must continue
pleted in order to represent the real-world sales transaction. through all succeeding SQL, statements until one of the fol-
If both transactions are not completely executed, the trans- lowing four events occur:
action yields an inconsistent database.
1. A COMMIT statement ends the transaction successfully,
If a transaction yields an inconsistent database, the
making the database changes permanent.
DBMS must be able to recover the database to a previous
A new transaction starts after COMMIT with the next
consistent state.
transaction initiating statement.
2. For programmatic SQL, successful program termination
Transaction Properties ends the final transaction successfully, even if a
All transactions must display atomicity, consistency, isola- commit statement has not been executed (equivalent to
tion and durability. These are known as ACID properties of COMMIT)
transactions. 3. For programmatic SQL, abnormal program termination
aborts the transaction (equivalent to ROLLBACK)

Atomicity Example:
It requires that all operations of a transaction be completed; UPDATE PRODUCT
if not, the transaction is aborted. Therefore, a transaction is SET PROD_QOH = PROD_QOH_100
treated as a single, logical unit of work. WHERE PROD_CODE = ‘345TYX’;
UPDATE ACCREC
SET AR_BALANCE = AR_BALANCE + 3500
Consistency WHERE AR_NUM = ‘60120010’;
It describes the result of the concurrent execution of COMMIT;
several transactions. The concurrent transactions are
treated as though they were executed in serial order. This
property is important in multiuser and distributed data-
Concurrency Control
base, where several transactions are likely to be executed The coordination of simultaneous execution of transactions
concurrently. in a multiprocessing database system is known as concur-
rency control. The objective of concurrency control is to
ensure the serializability of transaction in a multiuser data-
Isolation base environment. Concurrency is important, because the
It means that the data used during the execution of a simultaneous execution of transactions over a shared data-
transaction cannot be used by a second transaction until base can create several data integrity and consistency prob-
the first one is completed. Therefore, if a transaction T1 lems. Three main problems are lost updates, uncommitted
is being executed and is using the data item X1, that data data and inconsistent retrievals.
item cannot be accessed by any other transaction (T2…
Tn) until T1 ends. This property is particularly useful in Lost Updates
multiuser database environment, because several differ- Consider the following two concurrent transactions where
ent users can access and update the database at the same PROD_QOH represents a particular PRODUCT’s quantity
time. on hand. (PROD_QOH is an attribute in the Product table)
 Chapter 4 • Transaction and Concurrency | 4.67

Assume the current PROD_QOH value for the product con- 2. At the same time, T2 updates the PROD_QOH for
cerned is 35. two of the PRODUCT table’s products (T2 represents
the correction of a typing error: the user added 30
Table 1 units to product 345TYX’s PROD_QOH but meant to
Transaction Computation
add the 30 units to 125TYZ’s PROD_QOH to correct
the problem, the user subtracts 30 from product
T1: purchase 100 units PROD_QOH = PROD_QOH + 100
345TYX’s PROD_QOH and adds 30 to product
T2: sell 30 units PROD_QOH = PROD_QOH - 30 125TYZ’s PROD_QOH).
Table 1 shows the serial execution of these transactions The computed answer 485 is obviously wrong, because we
under normal circumstances, yielding the correct answer: know the correct answer to be 455.
PROD_QOH = 105. But suppose that a transaction is able
to read a product’s PROD_QOH value from the table before
a previous transaction (using the same product) has been Transaction Processing Systems
committed. The sequence depicted in Table 2 shows how the Transaction processing systems are systems with large data-
cost update problem can arise. Note that the first transaction bases and hundreds of concurrent users that are executing
(T1) has not yet been committed when the second transaction database transactions. For example, banking, credit card
(T2) is executed. Therefore T2 still operates on the value 135 processing, stock markets, supermarket checkout, etc.
to disk which is promptly over written by T2. As a result, the They require high availability and fast response time for
addition of 100 units is “lost” during the process. hundreds of concurrent users.
1. A transaction includes one or more database access
Uncommitted Data operations. These can include insertion, deletion,
Data are not committed when two transactions, T1 and T2 are modification, or retrieval operations.
executed concurrently and the first transaction (T1) is rolled 2. Basic operations: The basic database access
back after the second transaction (T2) has already accessed operations that a transaction can include are as
the uncommitted data, thus violating the isolation property follows:
of transaction. Consider the same transactions from T1 and •• read_item (X): Reads a database item named X into
T2, from above. However, this time T1 is rolled back to elim- a program variable.
inate the addition of the 100 units. Because T2 subtracts 30 •• Write_item (X): Writes the value of program vari-
from the original 35 units, the correct answer should be 5. able X into the database item named X
Table 2 Executing a read_item (X): Command includes the follow-
ing steps:
Computation
1. Find the address of the disk block that contains item X
T1: purchase PROD_QOH = PROD_QOH + 100 (Rolled
100 units Back)
2. Copy that disk block into a buffer in main memory (if
that disk block is not in main memory buffer).
T2: sell PROD_QOH = PROD_QOH_30
30 units
3. Copy item X from the buffer to the program variable
named x
Table 2 shows how, under normal circumstances, the serial Executing a write_item (X) command includes the follow-
execution of these transactions yield the correct answer. The ing steps:
uncommitted data problem can arise when the ROLLBACK
is completed after T2 has begun its execution. 1. Find the address of the disk block that contains item X
2. Copy that disk block into a buffer in main memory (if
Inconsistent Retrievals that disk block is not in main memory buffer)
3. Copy item X from the program variable named X into
Inconsistent retrievals occur when a transaction calculates its correct location in the buffer
some summary (aggregate) functions over a set of data, 4. Store the updated block from the buffer back to
while other transactions are updating the data. The prob- disk.
lem is that the transaction might read some data before they
are changed and other data after they are changed, thereby Step 4 actually updates the database on disk.
yielding inconsistent results. The decision about when to store back a modified disk
Example: block that is in a main memory buffer is handled by the
recovery manager of the DBMS in cooperation with the
1. T1 calculates the total PROD_QOH of the products underlying operating system.
stored in the PRODUCT table
4.68 | Unit 4 • Databases

READ / WRITE

BEGIN COMMIT
END
ACTIVE PARTIALLY COMMITTED

ABORT ABORT

FAILED TERMINATED

Figure 1 Transactions execution state transition diagram.

For the purpose of recovery, the system needs to keep track Concurrency Control with
of when the transaction starts, terminates, and commits or
aborts. Hence, the recovery manager keeps track of the fol- Locking Methods
lowing operations: A lock guarantees exclusive use of a data item to a transac-
tion. In general, if transaction T1 holds a lock on a data item
1. BEGIN_TRANSACTION: It shows the beginning (e.g., an employee’s salary) then transaction T2 does not
of Execution of a transaction. have access to that data item. A transaction acquires a lock
2. READ/WRITE: These specify read or write prior to data access; the lock is released (unlocked) when
operations on the database items. the transaction is completed, so that another transaction can
3. END_TRANSACTION: This specifies that READ lock the data item for its exclusive use. All lock informa-
and WRITE operations have ended and marks the end tion is managed by a lock manager, which is responsible for
of transaction execution. assigning and policing the locks used by the transactions.
4. COMMIT_TRANSACTION: This shows a
successful end of the transaction so that any changes
executed by the transaction can be safely committed Lock Granularity
to the database and will not be undone. Lock granularity indicates the level of lock use. Locking
5. ROLL BACK OR ABORT: This shows that the can take place at the following levels: database level, table
transaction has ended unsuccessfully, so that any level, page level, row level and field (or attribute) level.
changes or effects that the transaction may have
applied to the database must be undone.
Database Level
6. ACTIVE STATE: A transaction goes into an active
state immediately after it starts execution where it can In a database-level lock, the entire database is locked, thus
issue READ and WRITE operations. preventing the use of any tables in the database by transaction
7. PARTIALLY COMMITTED: When the transaction T2 while transaction T1 is being executed. Transaction T1 and
ends, it moves to the partially committed state T2 cannot access the database concurrently, even if they use
8. COMMIT: A transaction reaches its commit point different tables. This level of locking is suitable for batch pro-
when all its operations that access the database cesses, but it is not unsuitable for online multiuser DBMSs.
have been executed successfully, and the effect of
all the transaction operations on the database have Table Level
been recorded in the log. Beyond the commit point, In a table-level lock, the entire table is locked, preventing
the transaction is said to be committed, and its access to any row by transaction T2 while transaction T1 is
effect is assumed to be permanently recorded in the using Table 2 transactions can access the same database, as
database. long as they access different tables. Transactions T1 and T2
9. FAILED_STATE: A transaction can go to the failed cannot access the same table even if they try to use different
state if the transaction is aborted during its active rows, T2 must wait until T1 unlocks the table.
state. The transaction may then have to be rolled back
to undo the effect of its WRITE operations on the
database. Page level
10. TERMINATIED: The terminated state corresponds In a page level lock, the DBMS will lock an entire disk page (a
to the transactions leaving the system. disk page or page is the equivalent of a disk block, which can
 Chapter 4 • Transaction and Concurrency | 4.69

be described as a (referenced ) section of a disk). Transactions Binary Locks

T1 and T2 access the same table while locking different disk A binary lock has only two states: locked (1) or unlocked
pages. If T2 requires the use of a row located on a page that is (0). If an object, that is, a database, table, page, or row is
locked by T1, T2 must wait until the page is unlocked by T1. locked by a transaction, no other transaction can use that
object. If an object is unlocked, any transaction can lock
Row level the object for its use. As a rule, a transaction must unlock
The row-level lock is much less restrictive than the locks the object after its termination. Every database operation
discussed earlier. The DBMS allows concurrent transac- requires that the affected object be locked. Therefore, every
tions to access different rows of the same table, even if the transaction requires a lock and unlock operation for each
rows are located on the same page. A lock exists for each data item that is accessed. Such operations are automati-
row in each table of the database. cally scheduled by the DBMS, the user need not concerned
about locking or unlocking data items. Binary locks are
Field level now considered too restrictive to yield optimal concurrency
conditions. For example if two transaction want to read the
The field-level lock allows concurrent transactions to access same database object, the DBMS will not allow this to hap-
same row as long as they require the use of different fields pen, even though neither transaction updates the database
(attributes) within the row. Although, field-level locking (and therefore, no concurrency problems can occur) con-
clearly yields the most flexible multi user data access, it currency conflicts occur only when two transactions execute
requires a high level of computer over head. concurrently and one of them updates the database.

Lock Types Shared/Exclusive locks

1. Binary locks The tables “shared’ and “exclusive” indicate the nature of the
2. Shared/Exclusive locks lock. The following table comparatively explains both locks.

Exclusive Locks Shared Locks

An exclusive lock exists when access is specifically A shared lock exists when concurrent transactions are
reserved for the transaction that locked the object. granted READ access on the basis of a common lock.
The exclusive lock must be used when the potential for A shared lock produces no conflict as long as the concur-
conflict exists. rent transactions are read only.
(An exclusive lock is issued when a transaction wants to A shared lock is issued when a transaction wants to read
write (update) a data item and no locks are currently held data from the database and no exclusive lock is held on
on that data item by any other transaction. that data item.

Using the shared/exclusive locking concept, a lock can a big city and are caused when two transactions wait
have three states: unlocked, shared (READ) and exclusive for each other to unlock data.
(WRITE). 2 READ transactions can be safely executed and Both problems can be solved. Serializability is guaranteed
shared locks allow several READ transactions to concurrently through a locking protocol known as two-phase locking and
read the same data item. For example, if transaction T1 has a deadlocks can be eliminated by using deadlock detection, and
shared lock on data item X, and transaction T2 wants to read prevention techniques. We shall examine these techniques next.
data item X, T2 may also obtain a shared lock on data item X.
If transaction T2 updates data item X, then an exclusive
lock is required by T2 over data item X. The exclusive lock Two-phase Locking to Ensure
is granted if and only if no other locks are held on the data Serializability
item. Therefore, if a shared or exclusive lock is already held The two-phase locking protocol defines how transactions
on data item X by transaction T1, an exclusive lock cannot acquire and relinquish locks. It guarantees serializability, but
be granted to transaction T2. it does NOT prevent deadlocks. The two phases are as follows:
1. A growing phase, in which a transaction acquires all
Potential problems with locks the required locks without unlocking any data. Once
Although locks prevent serious data inconsistencies, their all locks have been acquired, the transaction is in its
use may lead to two major problems: locked point.
2. A shrinking phase, in which a transaction releases all
1. The resulting transaction schedule may not be
locks and cannot obtain any new lock.
serializable.
2. The schedule may create deadlocks. Database The two-phase locking protocol is governed by the follow-
deadlocks are the equivalent of a traffic gridlock in ing rules”
4.70 | Unit 4 • Databases

1. Two transactions cannot have conflicting locks. Example:

2. No unlock operation can precede a lock operation in
T1 T2
the same transaction.
3. No data are affected until all locks are obtained, that Write lock (z)
is, until the transaction is in its locked point. Read lock (z)
Read lock (y)
Deadlocks Write lock (y)

Deadlocks exist when two transactions, T1 and T2, exist in Transaction T1 is waiting for Y which is locked by Transaction
the following mode: T2 and transaction T2 is waiting for z which is locked by
1. T1 would like to access data item X and then data transaction T1. The below graph is called wait for graph.
item Y. (So far, T1 has locked data item X and T1 is in
Y
progress, it will eventually require to lock data item Y.)
2. T2 needs to access data items X and Y, to begin. (So T1 T2
far, T2 has locked data item Y.)
If T1 has not unlocked data item X, T2 cannot begin; if Z
T2 has not unlocked data item Y, T1 cannot continue.
Consequently, T1 and T2 wait indefinitely, each waiting for Deadlock Prevention
the other to unlock the required data item. Such in a real- There are number of deadlock prevention schemes that make
world DBMS, many transactions can be executed simulta- a decision about what to do with a transaction involved in a
neously, thereby increasing the probability of generating possible deadlock situation:
deadlocks. Note that deadlocks are possible only if one
of the transactions wants to obtain an exclusive lock on a 1. Should it be blocked and made to wait
data item; no deadlock condition can exist among shared 2. Should it be aborted
locks. 3. Should the transaction pre-empt and abort another
Three basic techniques exist to control deadlocks: transaction.

1. Deadlock prevention: A transaction requesting a new

lock is aborted if there is a possibility that a deadlock
Concurrency Control
can occur. If the transaction is aborted, all the changes with Time Stamping Methods
made by this transaction are ROLLED BACK, and The time stamping approach to scheduling concurrent trans-
all locks obtained by the transaction are released. actions assigns a global unique time stamp to each trans-
The transaction is then rescheduled for execution. action. The time stamp value produces an explicit order
Deadlock prevention works because it avoids the in which transactions are submitted to the DBMS. Time
conditions that lead to deadlocking. stamps must have two properties: uniqueness and monoto-
2. Deadlock detection: The DBMS periodically tests the nicity. Uniqueness ensures that no equal time stamp values
database for deadlocks. If a deadlock is found, one of can exist, and monotonicity ensures that time increases.
the transactions (the “victim”) is aborted (ROLLED All database operations (READ and WRITE) within
BACK and restarted), and the other transaction the same transaction must have the same time stamp. The
continues. DBMS executes conflicting operations in time stamp order,
3. Deadlock avoidance: The transaction must obtain all thereby ensuring serializability of the transactions. If two
the locks it needs before it can be executed. transactions conflict, one often is stopped, rescheduled, and
The best deadlock control method depends on the data- assigned a new time stamp value.
base environment. For example, if the probability of The concept of transaction time stamp TS(T), which is a
deadlocks is low, deadlock detection is recommended. unique identifier assigned to each transaction. The time stamps
However, if the probability of deadlocks is high, deadlock are based on the order in which transactions start. If transaction
prevention is recommended. If response time is not high T1 starts before transaction T2, then T S (T1) < T S(T2)
on the system priority list, deadlock avoidance might be 1. Older transaction will have the smaller time stamp value
employed. 2. Two schemes that prevent deadlock are
Deadlock occurs when each transaction T in a set •• Wait-die
of two or more tractions is waiting for some item that •• Wound-wait
is locked by some other transaction T1 in the set. Each
transaction in the set is on a waiting queue, waiting for Suppose that transaction Tk tries to lock an item x but is
one of the other transactions in the set to release the lock not able to because x is locked by some other transaction TL
on an item with a conflicting lock.
 Chapter 4 • Transaction and Concurrency | 4.71

The rules followed by these schemes are as follows: Two-phase Locking Theorem
1. Wait-die: If Ts (Tk) < Ts (TL), then (Tk older than TL) If all transactions obey the two phase locking protocol, then
Tk is allowed to wait; otherwise (Tk younger than TL) all possible interleaved schedule are serializable.
abort Tk and restart it later with the same time stamp 1. Before operating on any object (it could be a database
2. Wound-wait: If Ts (Tk) < Ts (TL) then (Tk older than tuple), a transaction must acquire a lock on the object
TL) abort TL and restart it later with the same time 2. After releasing a lock, a transaction must never go on
stamp; otherwise (Tk younger than TL) Tk is allowed to to acquire any more locks.
wait A transaction that obeys this protocol thus has two
Both schemes end up aborting the younger of the two phases: a lock acquisition or “growing phase and a lock
transactions that may be involved in a deadlock releasing or “shrinking” phase
Let ‘I’ be an interleaved schedule involving some set of
transactions T, T2, T3, . . . Tn.
Concurrency Control with
If ‘I’ is serializable, then there exists at least one serial
Optimistic Methods schedule ‘S’ involving T1, T2, . . . Tn such that ‘I’ is equivalent
Optimistic methods are based on the assumption that the to ‘S’ is said to be a serialization of ‘I’
majority of the database operations do not conflict. A trans- Let Ti and Tj be any two distinct transactions in the set
action is executed without restrictions until it is committed. T1, T2, T3, . . . Tn. Let Ti precede Tj in the serialization ‘S’. In
Each transaction moves through two or three phases: the interleaved schedule I, then the effect must be as if Ti
Read phase: The transaction reads the database, executes really did execute before Tj. In other words, if A and B are
the needed computations, and makes the updates to a pri- any two transactions involved is some serializable schedule,
vate copy of the database values. then either A logically precedes B or B logically precedes A
in that schedule, that is, either B can see A’s output or A can
Validation phase: The transaction is validated to assure that see B’s. If the effect is not as if either A ran before B or B ran
the changes made will not affect the integrity and consist- before A, then the schedule is not serializable and not correct.
ency of the database.
If the validation test is positive, transaction goes to the 1. A schedule ‘S’ of ‘n’ transactions T1, T2 . . . Tn is an
Write Phase. ordering of the operations of the transactions subject
If the validation test is negative, transaction is restarted, to the constraint that, for each transaction Ti that
and changes are discarded. participates in ‘S’, the same order in which they occur
Write phase: The changes are permanently applied to the in Ti.
database. 2. For the purpose of recovery and concurrency control,
we are mainly interested in the ‘read item’ and ‘write
item’ operations of the transactions, as well as the
Serializability COMMIT and ABORT operations. A shorthand
Serializabilty is accepted as ‘criterion for correctness’ for notation for describing a schedule uses the symbols,
the interleaved execution of a set of transactions, such an ‘R’, ‘W’, ‘C’ and ‘A’ for the operations read item, write
execution is considered to be correct if and only if it is item, commit, and abort respectively, and appends as
serializable. subscript the transition-id (transaction number) to
each operation in the schedule
1. A set of transactions is serializable if and only if it
is equivalent to some serial execution of the same Example: The schedule of the given set of transactions can
transactions be written as follows:
2. A serial execution is one in which the transactions are T1 T2
run one at a time in some sequence Read item (x);
Schedule: Given a set of transactions, any execution of those X = X – N;
transactions interleaved or otherwise is called a schedule. Read item (x);

1. Executing the transactions one at a time, with no X = X + M;

interleaving constitutes a serial schedule. A schedule Write item (x)
that is not serial is an interleaved schedule (or) non- Read item (y)
serial schedule. Write item (x)
2. Two schedules are said to be equivalent if and only if
Write item (y)
they are guaranteed to produce the same result as each
other. Thus, a schedule is serializable, and correct, if Y=Y+N
and only if it is equivalent to some serial schedule. Write item (y) Commit
4.72 | Unit 4 • Databases

Schedule: A transaction T reads from transaction T1 in a schedule

S if some item x is first written by T1 and later read by T.
S: R1(X); R2(X); W1 (X); R1(Y); In addition, T1 should not have been aborted before T reads
W2(X); W2(Y); W1(Y); C2 item x, and there should be no transactions that write x after
T1 writes it and before T reads it (unless those transactions,
Conflicts: Two operations in a schedule are said to have con- if any, have aborted before T reads x)
flict if they satisfy all three conditions, if
Example:
1. they belong to different transactions Consider the given schedule, check whether it is recover-
2. they access the same data item able or not:
3. at least one of the operations is a write item S: R1(X); R2(X); W1(X); R1(Y); W2(X); C2, W1(Y); C1?
For example, In the schedule ‘S’ given above, the operations Solution:
r1(x) and w2(x) conflict, as do The given schedule can also be represented as follows:
The operations r2 (x) and w1(x) and the operations w1(x)
and w2(x). However the operations r1(x) and r2(x) do not T1 T2
conflict, since they are both read operations; R1(x)
The operations w1(x) and w2(y) do not conflict because R2(x)
they operate on distinct data items x and y. The operations W1(x)
r1(x) and w1(x) do not conflict, because they belong to the
R1(y)
same transaction.
W2(x)
Complete schedule: A schedule S of ‘n’ transactions T1, T2, C2
T3 . . . Tn is said to be a complete schedule if the following
W1(y)
conditions hold.
C1
1. The operations is ‘S’ are exactly those operations in
T1, T2, . . . Tn including a commit or abort operation as There are two WR conflicts, if the schedule consists of RW
the last operation for each transaction in the schedule. conflict, then we may say that the schedule is not recover-
2. For any pair of operations from the same transaction able (if the transaction which is performing read operation
Ti, their order of appearance in ‘S’ is the same as their commits first)
order of appearance in Ti
3. For any two conflicting operations, one of the two must Cascadeless Schedule
occur before the other in the schedule.
In a recoverable schedule, no committed transaction ever
The preceding condition (3) allows for two non-conflicting needs to be rolled back. It is possible for a phenomenon
operations to occur in the schedule without defining which known as cascading rollback to occur, when an uncommit-
occurs first, thus leading to the definition of a schedule as a ted transaction has to be rolled back because it read an item
partial order of the operations in the ‘n’ transactions. from a transaction that failed.
It is difficult to encounter complete schedules in a trans- This is illustrated in the following schedule:
action processing system, because new transactions are
Example:
continually being submitted to the system. Hence, it is use-
ful to define the concept of the ‘committed projection C(S) S: R1(X); W1(X); R2(X); R1(Y); W2(X); W1(Y); A1, A2
of schedule S; which include only the operations in S that The above schedule is represented as follows:
belong to committed transactions, that is, transaction Ti
T1 T2
whose commit operation is Ci.
R1(x)
W1(x)
R2(x)
Recoverability R1(y)
Recoverability ensures that once a transaction T is com-
W2(x)
mitted, it should never be necessary to roll back T. The
schedules that theoretically meet this criterion are called W1(y)
recoverable schedules and those that do not are called non- A1
recoverable, and hence should not be permitted A2
A schedule ‘S’ is recoverable if no transaction T in ‘S’
commits until all transactions T1 that have written an item Transaction T2 has to be rolled back because it reads item x
that T reads have committed from T1, and T1 is then aborted, because cascading rollback
 Chapter 4 • Transaction and Concurrency | 4.73

can be quite time consuming since numerous transactions can Example:

be rolled back. It is important to characterize the schedules
where this phenomenon is guaranteed not to occur. S1 S3
A scheduled is said to be cascadeless if every transaction r1(x) W1(x)
in the schedule reads only items that were written by com- W2(x) W2(x)
mitted transaction. In this case, all items read will not be
discarded, so no cascading rollback will occur.
S2 S4
W2(x) W2(x)
Strict Schedule
r1(x) W1(x)
A schedule is called strict schedule, in which transactions
can neither read nor write an item x until the last transaction The value read by r1(x) can be different in the two sched-
that wrote x has committed or aborted ules. Similarly, if two write operations occur in the order
1. All strict schedules are cascadeless w1(x), w2(x) in s3, and in the reverse order w2(x), w1(x) in s4,
2. All cascadeless schedules are recoverable the next r(x) operation in the two schedules will read poten-
tially different values.
Equivalence of Schedules
There are several ways to define equivalence of schedules Testing for Conflict Serializability
as follows: The following algorithm can be used to test a schedule for
1. Result equivalent conflict serializability. The algorithm takes read item and
2. Conflict equivalent write item operations in a schedule to construct a prec-
3. View equivalent edence graph or serialization graph, which is a directed
graph G(N, E) here N is a set of Nodes N = {T1, T2, …. Tn} and E
Result Equivalent is a set of directed edges E = {e1, e2, ….. Em} There is one node
in the graph for each transaction. Ti in the schedule. Each
Two schedules are called result equivalent if they produce edge ei in the graph is of the form (Tj→ Tk), 1 ≤ j ≤ n, 1 ≤ k ≤ n,
the same final state of the database. However, two different Where Tj is the starting node of ei and Tk is the ending
schedules may accidentally produce the same final state. node of ei.
Example: Check whether the two schedules are result Edge is created if one of the operations in Tj appears in
equivalent or not: the schedule before some conflicting operation in Tk

S1 S2
Read item (x); Read item (x)
Algorithm
1. For each transaction Ti participating in schedule S,
X = X + 20; X = X * 1.1;
create a node labelled Ti in the precedence graph
Write item (x); Write item (x);
2. For each case in S where Tj executes a read item (x)
after Ti executes a write item (x), create an edge (Ti →
Solution: Tj) in the graph
Schedules S1 and S2 will produce the same final database 3. For each case in S where Tj executes a write item (x)
state if they execute on a database with an initial value of x after Ti executes a read item (x), create an edge (Ti →
= 200; but for other initial values of x, the schedules are not Tj) in the graph
result equivalent 4. For each case in S where Tj executes a write item (x)
For two schedules to be equivalent, the operations after Ti executes a write item (x), create an edge (Ti →
applied to each data item affected by the schedules should Tj) in the precedence graph
be applied to that item in both schedules in the same order. 5. The schedule S is serializable, if the precedence graph
The other two definitions of equivalence of schedules gen- contains no cycles
erally used are conflict equivalence and view equivalence
A cycle in a directed graph is a sequence of edges C = ((Tj
Conflict Equivalence → Tk), (Tk → Tp), . . . (Ti → Tj))
With the property that the starting node of each edge,
Two schedules are said to be conflict equivalent if the order
except the first edge is the same as the ending node of the
of any two conflicting operations is the same in both sched-
previous edge, and the starting node of the first edge is the
ules. If two conflicting operations are applied in different
same as the ending node of the last edge.
orders in two schedules, the effect can be different on the
database or on other transactions in the schedule, and hence Example: Check whether the given schedule is conflict
the schedules are not conflict equivalent. serializable or not by drawing precedence graph:
4.74 | Unit 4 • Databases

T1 T2 T3 View Equivalence and View Serializability

R1(x) View equivalence is less restrictive compared to conflict
W2(x) equivalence. Two schedules S and S′ are said to be view
equivalent if the following three conditions hold:
R3(x)
W1(x) 1. The same set of transactions participate in S and S′,
W3(x) and S and S′ include the same operations of those
transactions
R1(x)
2. For any operation ri(x) of Ti in S, if the value of x read
Solution: by the operation has been written by an operation wj
First identify the conflicts: (x) of Tj, the same condition must hold for the value
(T1 → T2) WR conflict of x read by operation ri (x) of Tj in S′
(T2 → T1) WW conflict 3. If the operation wk(y) of Tk is the last operation to
(T2 → T3) RW conflict write Y in S, then Wk (y) of Tk must also be the last
(T3 → T1) WR conflict operation to write item Y in S′
(T1 → T3) WW conflict The idea behind view equivalence is that as long as each
Take transactions as nodes in the precedence graph: read operation of a transaction reads the result of the same
write operation in both schedules, the write operations of
T1 T2
each transaction must produce the same result. Hence the
read operation is said to see the same view in both schedules:
T3 1. A schedule S is said to be view serializable if it is
view equivalent to a serial schedule.
The precedence graph has cycle, which says that the sched- 2. All conflict serializable schedules are view
ule is not serializable. serializable, but vice versa is not true.

Exercises
Practice Problem 1 3. Consider the three data items D1, D2 and D3 and the
Directions for questions 1 to 20: Select the correct alterna- following execution of schedules of transactions T1, T2
tive from the given choices. and T3:
1. Consider the given schedules S1 and S2
T1 T2 T3
S1: r1(x), r1(y), r2(x), r2(y), w2(y), w1(x)
R(D2)
S2: r1(x), r2(x), r2(y), w2(y), r1(y), w1(x)
R(D2)
Which schedule is conflict serializable?
W(D2)
(A) S1 (B) S2
R(D2)
(C) S1 and S2 (D) None of these
R(D3)
2. Consider the given schedule with three transactions T1,
T2 and T3: R(D1)

T1 T2 T3 W(D1)

r1(x) W(D2)

r2(y) W(D3)

r3(y) R(D1)

w2(y) R(D2)

w1(x) W(D2)

w3(x) W(D1)

r2(x)
Which of the following is true?
w2(x)
(A) The schedule is conflict serializable
Which of the following is correct serialization? (B) The schedule is not conflict serializable
(A) T2 → T1 → T3 (B) T1 → T3 → T2 (C) The schedule has deadlock
(C) T3 → T1 → T2 (D) None of these (D) Both (A) and (C)
 Chapter 4 • Transaction and Concurrency | 4.75

4. Consider the given schedule T2: read(Q)

T3 T4 T7
Read(P)
R(Q) if Q = 0 then p = p + 1
W(Q) Write (P)
W(Q) Any non-serial interleaving of T1 and T2 for concurrent
R(Q) execution leads to
(A) a serializable schedule
W(Q)
(B) a schedule that is not conflict serializable
Which of the following is the correct precedence graph (C) a conflict serializable schedule
for the above schedule? (D) a schedule for which a precedence graph cannot be
drawn
7. Consider the concurrent execution of two transactions
(A) T3 T4 T7 T1 and T2, if the initial values of x, y, M and N are 200,
100, 10, 20 respectively. What are the final values of x
and y?

T1 T2
read-item(x)
(B) T3 T7 T4
x=x–N
read-item(x)
x=x+M
Write-item(x)
(C) T7 T4 T3
read-item(y)
Write-item(x)
y=y+N
Write-item(y)
(D) T3 T4 T7
(A) 220, 110 (B) 210, 120
(C) 220, 120 (D) 210, 110
5. Consider two Transactions T1 and T2 and four sched- 8. For the above data, if the transactions are executed in
ules: S1, S2, S3 and S4 of T1 and T2: serial manner, what would be the values of X and Y at
the end of the serial execution of T1 and T2?
T1: r1(x), w1(x), w1(y)
T2: r2(x), r2(y), w2(y) T1 T2
S1: r1(x), r2(x), r2(y), w1(x), w1(y), w2(y) Read-item(x)
S2: r1(x), r2(x), r2(y), w1(x), w2(y), w1(y) X=X–N
S3: r1(x), w1(x), r2(x), w1(y), r2(y), w2(y) Write-item(x)
S4: r2(x), r2(y), r1(x), w1(x), w1(y), w2(y) Read-item(y)
Which schedules are conflict serializable in the given Y=Y+N
schedules? Write-item(y)
(A) S1 and S2 Read-item(x)
(B) S1 and S3
X=X+M
(C) S2 and S3
Write-item(x)
(D) S1 and S4
6. Consider the following transactions with data items P (A) 190, 120
and Q initialized to ‘0’: (B) 180, 120
T1: read(P) (C) 190, 110
Read(Q) (D) 180, 110
if p = 0 then Q = Q + 1 9. Consider the given two transactions T1 and T2:
Write(Q) T1: r1(x), w1(x), r1(y)
4.76 | Unit 4 • Databases

T2: r2(x), r2(y), w2(x), w2(y) (A) r3(x), r3(y), w3(y), r1(x), r1(z), w1(x), r2(z), r2(y),
Which of the following schedules are complete schedules? w2(z), w2(y)
(A) r1(x), r2(x), w1(x), r1(y), r2(y), w2(x), w2(y) (B) r1(x), r1(z), w1(x), r2(z), r2(y), w2(z), w2(y), r3(x),
(B) r2(x), r1(x), r2(y), w1(x), w2(x), r1(y), w2(y) r3(y), w3(y)
(C) r1(x), r1(y), r2(x), r2(y), w1(x), w2(x), w2(y) (C) r2(z), r2(y), w2(z), w2(y), r3(x), r3(y), w3(y), r1(x),
(D) All the above r1(z), w1(x)
(D) r2(z), r2(y), w2(z), w2(y), r1(x), r1(z), w1(x), r3(x),
10. Consider the given schedule with data-locks on data-
r3(y), w3(y)
items, check whether it has dead-lock or not. The locks
are shared-lock(S) and Exclusive-lock(X). Shared-lock 13. Consider schedule S3, which is a combination of transac-
is also called Read-lock, Exclusive-lock is also called tions T1, T2 and T3 from Q. No.11.
Write-lock. Read and Write operations are denoted by S3: r1(x), r2(z), r1(z), r3(x), r3(y), w1(x), c1, w3(y), c3,
R and W, respectively. r2(y), w2(z), w2(y), c2?
Which of the following is true?
T1 T2 T3 T4
(A) Recoverable and conflict serializable
S(A)
(B) Recoverable but not conflict serializable
R(A) (C) Conflict serializable but not Recoverable
X(B) (D) Not recoverable and not conflict serializable
W(B) 14. Consider the given schedule:
S(B) S4: r1(x), r2(z), r1(z), r3(x), r3(y), w1(x), w3(y), r2(y),
S(C) w2(z), w2(y), c1, c2, c3:
R(C) Which of the following is true?
X(C) (A) Recoverable and conflict serializable
X(B) (B) Recoverable but not conflict serializable
(C) Conflict serializable but not Recoverable
X(A)
(D) Not recoverable and not conflict serializable
Which of the following is incorrect? 15. Which of the following is correct for the below com-
(A) T1 → T2 (B) T3 → T1 patibility matrix?
(C) T2 → T3 (D) T4 → T3
Mode of Locks Shared-Lock Exclusive-Lock
11. Consider the three transactions T1, T2 and T3 and the Currently held by
schedule S1 as given below. Draw the serializability other S
(precedence) graph for S1, and state whether the sched- transactions
X
ule is serializable or not. If a schedule is serializable,
which one of the following is equivalent serial schedule? S – shared - Lock, X – Exclusive - Lock
T1: r1(x), r1(z), w1(x) (A)
T2: r2(z), r2(y), w2(z), w2(y) S X
T3: r3(x), r3(y), w3(y)
S No No
S1: r1(x), r2(z), r1(z), r3(x), r3(y), w1(x), w3(y), r2(y), X Yes No
w2(z), w2­(y)? (B)
(A) r3(x), r3(y), w3(y), r1(x), r1(z), w1(x), r2(z), r2(y),
S X
w2(z), w2(y)
(B) r1(x), r1(z), w1(x), r2(z), r2(y), w2(z), w2(y), r3(x), S Yes No
r3(y), w3(y) X No No
(C) r2(z), r2(y), w2(z), w2(y), r3(x), r3(y), w3(y), r1(x),
(C)
r1(z), w1(x)
(D) r2(z), r2(y), w2(z), w2(y), r1(x), r1(z), w1(x), r3(x), S X
r3(y), w3(y) S Yes Yes
12. Consider the data given in the above question. Draw the X No No
precedence graph for S2 and state whether each sched-
(D)
ule is serializable or not. If a schedule is serializable,
which of the following is equivalent serial schedule? S X
S2: r1(x), r2(z), r3(x), r1(z), r2(y), r3(y), w1(x), w2(z), S No Yes
w3(y), w2(y) X No No
 Chapter 4 • Transaction and Concurrency | 4.77

16. Consider the following schedule with locking: FROM Account

ROLL BACK
T1 T2
COMMIT
Lock – X(A)
R(A) The above problem is a case of
W(A) (A) READ UNCOMMITTED
Lock – X(B)
(B) READ COMMITTED
(C) DIRTY READ
R(B)
(D) BOTH A and C
W(B)
19. Consider the following set of transactions
Lock – X(A)
Lock – X(B) T1 T2
SELECT AVG (balance)
Which of the following is true?
FROM Account
(A) schedule is in Dead–Lock state
UPDATE Account
(B) schedule is conflict serializable
(C) schedule is not conflict serializable SET balance =
balance – 4000
(D) Both A and B
WHERE number = 586;
17. Consider the given set of transactions:
COMMIT
T1 T2 SELECT AVG (balance)
SELECT AVG (balance) FROM Account
FROM Account COMMIT
INSERT INTO Account
VALUES The above problem is a case of
(487, 2000); (A) READ UNCOMMITTED
COMMIT (B) READ COMMITTED
SELECT AVG (balance) (C) REPEATABLE READ
(D) DIRTY READ
FROM Account
20. Consider the following schedule with locks on data
COMMIT
items:
The above problem is a case of
(A) READ UNCOMMITTED T1 T2 T3
(B) RAD COMMITTED X(A)
(C) REPEATABLE READ X(A)
(D) DIRTY READ X(A)
18. Consider the given set of transactions S(B)
S(B)
T1 T2
UPDATE ACCOUNT
SET balance = balance – 1000
Which of the following is incorrect?
(A) T2 → T1
WHERE number = 586;
(B) T3 → T2
SELECT AVG (balance) (C) T3 → T1
(D) T1 → T3

 p  
Practice Problem 2 (B) Each leaf node has at most    values.
 2  
Directions for questions 1 to 20: Select the correct alterna- (C) Each internal node, except the root, has at least
tive from the given choices.
 p  
1. Which of the following is false with respect to B+ -  2   tree pointers.
trees of order p?   
(A) Each internal node has at most p tree pointers. (D) All leaf nodes are at same level.
4.78 | Unit 4 • Databases

2. Consider below transactions: 6. Match the following:

T1 T2 LIST I LIST II

Read - item(X); 1. Primary index A. Ordered key field

X : = X - N; 2. Clustering index B. Non-ordered

field
Read - item (X);
3. Secondary index C. Ordered non-key
X: = X + M; field
Write - item(X);
(A) 1 – A, 2 – B, 3 – C
Read - item (Y); (B) 1 – A, 2 – C, 3 – B
Write - item (X); (C) 1 – C, 2 – B, 3 – A
Y: = Y + N; (D) 1 – C, 2 – A, 3 – B
Write - item (Y); 7. Consider a file with 30,000 fixed length records of size
100 bytes stored on a disk with block size 1024 bytes.
Which of the following problem will occur during the Suppose that a secondary index on a non-ordering key
concurrent execution of the above transactions? field is constructed with key field size 9 bytes and block
(A) Lost update problem because of incorrect X. pointer 6 bytes. What will be the number of blocks
(B) Lost update problem because of incorrect Y. needed for the index?
(C) Dirty read problem because of incorrect X. (A) 68 (B) 442
(D) Dirty read problem because of incorrect Y. (C) 1500 (D) 3000
3. Consider the scheduled: 8. Match the following:
S: r1(X); r2(X); w1 (X); r1(Y); w2(X); C2; w1(Y); C1; Index type Number of Index entries
This schedule is 1. Primary Index A. Blocks in data file
(A) Recoverable (B) Non-recoverable
2. Clustering B. Record in data file
(C) Strict schedule (D) Both (A) and (C) index
4. Consider below schedule: 3. Secondary C. Distinct index filed values
key index
T1 T2
Read - item(X); (A) 1 – A, 2 – B, 3 – C (B) 1 – A, 2 – C, 3 – B
(C) 1 – C, 2 – B, 3 – A (D) 1 – C, 2 – A, 3 – B
X : = X - N;
9. Which of the following is true with respect to B – Tree
Read - item (X);
of order p?
X: = X + M;
(A) Each node has at most p tree pointers.
Write - item(X); (B) Each node, except the root and leaf nodes, has at
Read - item (Y);
least   tree pointers.
p
Write - item (X);
2
Y: = Y + N; (C) All leaf nodes are at the same level.
Write - item (Y); (D) All of these.
This schedule is 10. What is the amount of unused space in allocation of uns-
(A) Serializable panned fixed records of size R on a block of size B bytes?
(B) Not serializable (A) B - R (B) B −  B 
(C) Under dead lock R
 
(D) Both (B) and (C)
 B  B 
5. Let, current number of file records = r (C) B −    ∗ R  4 (D)    ∗ R  − B
 R    R  
maximum number of records = bfr
11. What is the average time required to access a record in
current number of file buckets = N
a file consisting of b blocks using unordered heap linear
Then what will be the file load factor? search?
r (A) b (B) b/2
(A) (B) r + (bfr * N) (C) log 2
b
(D) b2
(bfr ∗ N )
12. Consider a file of fixed length records of size R bytes. If
(C) r * (bfr * N) (D) r * (bfr + N) the block size is B bytes, then the blocking factor will be
 Chapter 4 • Transaction and Concurrency | 4.79

B (A) 114 (B) 171

(A) B × R records (B)   records (C) 341 (D) 68
R
16. For a set of n transactions, there exist ______ different
B valid serial schedules
(C)   records (D) B + R records
R (A) n (B) n2
13. Consider the following relation instance: (C) n/2 (D) n!
17. The number of possible schedules for a set of n transac-
P Q R
tions is
1 4 2 (A) lesser than n! (B) much larger than n!
1 5 3 (C) n! (D) None
1 6 3 18. Which one of the following is conflict operation?
3 2 2 (A) Reads and writes from the same transaction
(B) Reads and writes from different transaction
Which of the following FDs are satisfied by the instance? (C) Reads and writes from different transactions on
(A) PQ → R and R → Q (B) QR → P and Q → R different data items.
(C) QR → P and P → R (D) PR → Q and Q → P (D) Reads and writes from different transaction on
14. Consider an ordered file with 30,000 records stored on same data.
a disk with block size of 1024 bytes. The records are
19. The following schedule S: r3(x), r2(x), w3(x), r1(x), w1(x)
of fixed size and are of unspanned, with record length
is conflict equivalent to serial schedule
100 bytes. What is the number of accesses required to
(A) T1 → T3 → T1 (B) T2 → T1 → T3
access a data file using binary search?
(C) T1 → T2 → T3 (D) None
(A) 10 (B) 12
(C) 1500 (D) 3000 20. The following schedule S: R1(x), R2(x), W1(x), W2(x) is
15. What is the blocking factor for an index if the ordering (A) Conflict serializable (B) View serializable
key field size is 9 bytes and block pointer is 6 bytes (C) Both (D) None
long, and the disk block size is 1024 bytes?

Previous Years’ Questions

1. Consider the following four schedules due to three trans- (A) S is conflict-serializable but not recoverable
actions (indicated by the subscript) using read and write (B) S is not conflict-serializable but is recoverable
on a data item x, denoted by r(x) and w(x), respectively. (C) S is both conflict-serializable and recoverable
Which one of the them is conflict serializable? [2014] (D) S is neither conflict-serializable nor it is recover-
(A) r1(x); r2(x); w1(x); r3(x); w2(x) able
(B) r2(x); r1(x); w2(x); r3(x); w1(x) 3. Consider the following transaction involving two
(C) r3(x); r2(x); r1(x); w2(x); w1(x) bank accounts x and y.
(D) r2(x); w2(x); r3(x); r1(x); w1(x)
read (x) ; x : = x – 50; write (x) ; read(y); y : = y + 50;
2. Consider the following schedule S of transactions T1, write(y)
T2, T3, T4:
The constraint that the sum of the accounts x and y
T1 T2 T3 T4 should remain constant is that of  [2015]
Reads (X) (A) Atomicity (B) Consistency
Writes (X)
(C) Isolation (D) Durability
Commit 4. Consider a simple checkpointing protocol and the fol-
Writes (X) lowing set of operations in the log.
Commit (start, T4); (write, T4, y, 2, 3); (start, T1); (commit, T4);
Writes (Y) (write, T1, z, 5, 7);
Reads (Z)
Commit (checkpoint);
Reads (X) (start, T2); (write, T2, x, 1, 9); (commit, T2); (start, T3),
Reads (Y) (write, T3, z, 7, 2);
Commit If a crash happens now and the system tries to recover
Which one of the following statements is correct? using both undo and redo operations. What are the
 [2014] contents of the undo list and the redo list? [2015]
4.80 | Unit 4 • Databases

(A) Undo: T3, T1; Redo: T2 (A) guarantee serializability and deadlock-freedom.
(B) Undo: T3, T1; Redo: T2, T4 (B) guarantee neither serializability nor deadlock-
(C) Undo: none; Redo: T2, T4, T3, T1 freedom.
(D) Undo: T3, T1, T4; Redo: T2 (C) guarantee serializability but not deadlock-free-
5. Consider the following partial schedule S involving dom.
two transactions T1 and T2. Only the read and the write (D) 
guarantee deadlock-freedom but not serializa-
operations have been shown. The read operation on bilty.
data item P is denoted by read(P) and the write opera- 8. Suppose a database schedule S involves transactions
tion on data item P is denoted by write(P) T1,….Tn. Construct the precedence graph of S with
vertices representing the transactions and edges rep-
resenting the conflicts. If S is serializable, which one
Transaction – id of the following orderings of the vertices of the prec-
Time Instance T1 T2 edence graph is guaranteed to yield a serial schedule?
1 read(A) [2016]
2 write(A)
(A) Topological order
(B) Depth - first order
3 read(C)
(C) Breadth - first order
4 write(C) (D) Ascending order of transaction indices
5 read(B) 9. Consider the following database schedule with two
6 write(B) transactions T1 and T2.
7 read(A) S = r2(X); r1(X); r2(Y); w1(X); r1(Y); w2(X); a1;a2
8 commit Where ri (Z) denotes a read operation by transaction
9 read(B) Ti on a variable Z, wi(Z) denotes a write operation by
Schedule S Ti on a variable Z and ai denotes an abort by transac-
Suppose that the transaction T1 fails immediately after tion Ti.
time instance 9. Which one of the following state- Which one of the following statements about the
ments is correct? [2015] above schedule is TRUE? [2016]
(A) T2 must be aborted and then both T1 and T2 must (A) S is non - recoverable
be re-started to ensure transaction atomicity. (B) S is recoverable, but has a cascading abort
(B) Schedule S is non-recoverable and cannot ensure (C) S does not have a cascading abort
transaction atomicity. (D) S is strict.
(C) Only T2 must be aborted and then re-started to 10. In a database system, unique timestamps are assigned
ensure transaction atomicity. to each transaction using Lamport’s logical clock. Let
(D) Schedule S is recoverable and can ensure atomic- TS(T1) and TS(T2) be the timestamps of transactions
ity and nothing else needs to be done. T1 and T2 respectively. Besides, T1 holds a lock on the
6. Which one of the following is NOT a part of the resource R, and T2 has requested a conflicting lock on
ACID properties of database transactions? [2016] the same resource R. The following algorithm is used
(A) Atomicity to prevent deadlocks in the database system assum-
(B) Consistency ing that a killed transaction is restarted with the same
(C) Isolation timestamp.
(D) Deadlock - freedom if TS(T2) < TS(T1) then
7. Consider the following two phase locking protocol. T1 is killed
Suppose a transaction T accesses (for read or write else T2 waits.
operations), a certain set of objects {O1, ….. , Ok). Assume any transaction that is not killed terminates
This is done in the following manner: [2016] eventually. Which of the following is TRUE about the
Step 1. T acquires exclusive locks to O1,….Ok in database system that uses the above algorithm to pre-
increasing order of their addresses. vent deadlocks? [2017]
(A) The database system is both deadlock-free and
Step 2. The required operations are performed. starvation-free.
Step 3. All locks are released. (B) The database system is deadlock-free, but not
This protocol will starvation-free.
 Chapter 4 • Transaction and Concurrency | 4.81

(C) The database system is starvation-free, but not T2 : r2 (Y)w2 (Y)r2 (Z)w2 (Z)
deadlock-free. where ri (V) denotes a read operation by transaction
(D) The database system is neither deadlock-free nor Ti on a variable V and wi (V) denotes a write operation
starvation-free. by transaction Ti on a variable V. The total number of
11. Two transactions T1 and T2 are given as conflict serializable schedules that can be formed by
T1 : r1(X)w1 (X)r1 (Y)w1 (Y) T1 and T2 is _______. [2017]

Answer Keys
Practice Problem 1
1. B 2. B 3. B 4. B 5. C 6. B 7. B 8. A 9. A 10. D
11. A 12. A 13. A 14. C 15. B 16. D 17. C 18. D 19. B 20. D

Practice Problem 1
1. B 2. A 3. A 4. D 5. A 6. B 7. B 8. B 9. D 10. C
11. B 12. B 13. B 14. B 15. D 16. D 17. C 18. D 19. A 20. D

Previous Years’ Questions

1. D 2. C 3. B 4. A 5. B 6. D 7. A 8. A 9. C 10. A
11. 54
 Chapter 5
File Management

LEARNING OBJECTIVES

 Files  Extendible hashing

 Memory hierarchies  Index update
 Description of disk devices  Clustering index
 File records  B -Trees
 Sorted files  B +Trees
 Hashing techniques  Over flow in internal node

files Index files These files are used to access a record in the file. The
entire index file is loaded into main memory data and indexes are
Databases are stored on magnetic disks as files of records.
stored in the same file. The term ‘index file’ is used as a synonym
Computer storage media form a storage hierarchy that includes
for the term ‘database file’. The index file contains parameters that
two main categories.
specify the name and location of file used to store DB.
Primary storage This category includes storage media that can be
Indexing Indexing mechanism is used to speed up access to
operated on, directly by CPU, such as the computer main memory
desired data. An index file consists of records (called index entries)
and cache memory. Primary storage provides fast access but is of
of the form.
limited storage capacity.
Search-key Pointer
Secondary storage This category includes magnetic disks, optical
disks, and tapes. These devices usually have a larger capacity, less Index files are typically much smaller than the original file.
cost, and slower access to data. Data in secondary storage cannot
be processed directly by the CPU, it must be copied into primary Ordered indices In ordered index, index entries are stored, sorted
storage. on the search-key value.
Example: Author catalogue in library.
File Structure
Taxonomy of file structure MeMorY HierarcHies
At the primary storage level, the memory hierarchy includes cache
Files memory which is a static RAM.
access methods The next level of primary storage is DRAM (dynamic RAM)
which provides the main work area for the CPU for keeping pro-
Sequential Random
grams and data and is called the main memory.
At the secondary storage level, the hierarchy includes magnetic
Index file Hashed file disks, as well as mass storage in the form of CD-ROM (compact
Sequential file
disk read-only memory) and tapes. Programs reside in DRAM and
large permanent databases reside on secondary storage.
Sequential file A sequential file is one in which records can only Another form of memory, flash memory, is non-volatile.
be accessed sequentially, one after another from beginning to end. Flash memories are high-density, high-performance memories
Records are stored contiguously on the storage device. using EEPROM (electrically erasable programmable read-only
 Chapter 5 • File Management | 4.83

memory) technology. The advantage of flash memory is the Record type A collection of field names and their correspond-
fast access speed, the disadvantage is that an entire block ing data types constitutes a record type (or) record format.
must be erased and written over at a time. Finally, magnetic A file is a sequence of records. If every record in the
tapes are used for archiving and backup storage of data. file has exactly the same size (in bytes), the file is said to
be made up of fixed-length records. If different records in
the file have different sizes, the file is said to be made up of
Description of Disk Devices variable-length records.
Magnetic disks are used for storing large amounts of data.
The capacity of a disk is the number of bytes it can store. A Spanned Versus Unspanned Records
disk is single sided if it stores information on only one of
The records of a file must be allocated to disk blocks because
its surfaces and double sided if both surfaces are used. To
a block is the unit of data transfer between disk and memory.
increase storage capacity, disks are assembled into a disk
When the block size is larger than the record size, each block
pack, which may include many disks and hence many sur-
will contain numerous records, although some files may
faces. Information is stored on a disk surface in concentric
have unusually large records that cannot fit in one block.
circles with small width, each having a distinct diameter.
Suppose that the block size is B bytes. For a file of fixed-
Each circle is called a track. For disk packs, the tracks with
length records of size R bytes, with B ≥ R, we can fit
the same diameter on the various surfaces are called a cyl-
inder because of the shape they would form if connected in bfr = ⎣B/R⎦ records per block
space.
The value bfr is called the blocking factor for the file. Some
A track usually contains a large amount of information;
times R may not divide B exactly, so we have some unused
it is divided into smaller blocks (or) sectors. The division
space in each block equal to B – (bfr * R) bytes. To uti-
of track into equal-sized disk blocks (or pages) is set by the
lize this unused space, we can store part of a record on one
operating system during disk formatting.
block and the rest on another. A pointer at the end of the
Blocks are separated by fixed-size inter-block gaps,
first block points to the block containing the remainder of
which include specially coded control information writ-
the record in case it is not the next consecutive block on
ten during disk initialization. This information is used
disk. This organization is called spanned, because records
to determine which block on the track follows each inter
can span more than one block. Whenever a record is larger
block gap. Transfer of data between main memory and
than a block, we must use a spanned organization. If records
disk takes place in units of disk blocks. The hardware
are not allowed to cross block boundaries, the organization
address of a block is the combination of a cylinder num-
is called unspanned. This is used with fixed-length records
ber, track number and block number is supplied to the disk
having B > R, because it makes each record start at a known
I/O hardware.
location in the block. For variable-length records, either a
The actual hardware mechanism that reads or writes a
spanned or an unspanned organization can be used.
block is the disk read/write head, which is part of a sys-
For variable-length records using spanned organization,
tem called a disk drive. A disk is mounted in the disk drive,
each block may store a different number of records. In this
which includes a motor that rotates the disk. To transfer a
case, the blocking factor bfr represents the average number
disk block, given its address, the disk controller must first
of records per block for the file. We can use bfr to calculate
mechanically position the read/write head on the correct
the number of blocks ‘b’ needed for a file of ‘r’ records.
track. The time required to do this is called the seek time.
b = ⎡(r/bfr)⎤ blocks
There is another delay called rotational delay or latency; the
beginning of the desired block rotates into position under Block x Record 1 Record 2 Record 3
the read/write head. It depends on the RPM of the disk.
Finally, some additional time is needed to transfer the data, Block x + 1 Record 4 Record 5
which is called block-transfer time. Hence, the total time
needed to locate and transfer an arbitrary block, given its Figure 1 Unspanned records
address is the sum of the seek time, rotational delay and
block transfer time. The seek time and rotational delay are Block x Record 1 Record 2 Record 3 Record 4 P
usually much larger than the block transfer time.

File Records Block x + 1 Record 4 Record 5 Record 6 Record 7 P

Data is usually stored in the form of records. Each record Figure 2 Spanned
consists of a collection of related data values or items where
each value is of one or more bytes and corresponds to a There are several standard techniques for allocating the
particular field of the record. Records describe entities and blocks of a file on disk. In contiguous allocation, the file
their attributes. blocks are allocated to consecutive disk blocks. In linked
4.84 | Unit 4 • Databases

allocation, each file block contains a pointer to the next Hashing Techniques
file block. A combination of the two allocates clusters
The other type of primary file organization is based on
of consecutive disk blocks, and the clusters are linked.
hashing, which provides very fast access to records on cer-
Clusters are sometimes called file segments (or) extents.
tain search conditions. This organization is usually called a
Another possibility is to use indexed allocation, where
hash file.
one or more index blocks contain pointers to the actual
The search condition must be an equality condition on
file blocks.
a single field, called the hash field of the file. If the hash
is also a key field of the file, in which case it is called the
Sorted Files (Ordered Records) hash key.
We can physically order the records of a file on disk based The idea behind hashing is to provide a function ‘h’,
on the values of the one of their fields called the ordering called a hash function or randomizing function, which is
field. This leads to an ordered or sequential file. If the order- applied to the hash field value of a record and yields the
ing field is also a key field of the file, a field guaranteed to address of the disk block in which the record is stored. We
have a unique value in each record, then the field is called need only a single-block access to retrieve that record.
the ordering key for the file. Example:

Advantages NAME RNO CLASS GRADE

0
1. Reading the records in order of the ordering key 1
values becomes extremely efficient, because no 2
sorting is required. 3
. .
2. Finding the next record from the current one in order
. .
of the ordering key usually requires no additional block .
.
access, because the next record is in the same block as
the current one. m −2
3. Using a search condition based on the value of an m −1
ordering key field results in faster access when the
binary search technique is used. This constitutes an
improvement over linear searches, although it is not Internal Hashing
often used for disk files. For internal files, hashing is implemented as a hash table
A binary search for disk files can be done on the blocks through the use of an array of records. Suppose that the
rather than on the records. Suppose that a file has ‘b’ blocks array index range is from 0 to M – 1, then we have M
numbered 1, 2 ,…, b, the records are ordered by ascend- slots whose addresses corresponds to the array indexes.
ing value of their ordering key field and we are searching We choose a hash function that transforms the hash field
for a record whose ordering key field value is K. Assuming value into an integer between 0 and M – 1. One com-
that disk addresses of the file blocks are available in the file mon hash function is the h(K) = K mod M function, which
header, the binary search usually accesses log2(b) blocks, returns the remainder of an integer hash field value K
whether the record is found (or) not, an improvement after division by M; this value is then used for the record
over linear searches, where, on the average, (b/2) blocks address.
are accessed when the record is found and ‘b’ blocks are Non-integer hash field values can be transformed into
accessed when the record is not found. integers before the mod function is applied. For character
strings, the numeric (ASCII) codes associated with charac-
Average Time to ters can be used in the transformation.
Type of Access a Specific A collision occurs when the hash field value of a record
Organization Access Method Record
that is being inserted hashes to an address that already con-
Heap (unordered) Sequential scan b/2 tains a different record. In this situation, we must insert the
(linear search)
new record in some other position, since its hash address is
Ordered Ordered scan b/2 occupied. The process of finding another position is called
Ordered Binary search log2b collision resolution. There are different methods for colli-
sion resolution as follows:
Ordered files are rarely used in database applications
unless an additional access path, called a primary index, Open addressing Proceeding from the occupied position
is used; this results in an indexed sequential file. This fur- specified by the hash address, the program checks the sub-
ther improves the random access time on the ordering key sequent positions in order until an unused (empty) position
field. is found.
 Chapter 5 • File Management | 4.85

Chaining For this method, various overflow locations blocks. The hashing function maps a key into a relative
are kept, usually by extending the array with a number of bucket number, rather than assigning an absolute block
overflow positions. In addition, a pointer field is added to address to the bucket. A table maintained in the file header
each record location. A collision is resolved by placing the converts the bucket number into the corresponding disk
new record in an unused overflow location and setting the block address.
pointer of the occupied hash address location to the address The collision problem is less severe with buckets,
of that overflow location. A linked list of overflow records because as many records as will fit in a bucket can hash to
for each hash address is thus maintained. the same bucket without causing problems. If the capacity
of bucket exceeds, we can use a variation of chaining in
Multiple hashing The program applies a second hash which a pointer is maintained in each bucket to a linked
function if the first results in a collision. If another collision list of overflow records for the bucket. The pointers in the
results, the program uses open addressing or applies a third linked list should be record pointers, which include both
hash function and then uses open addressing if necessary. a block address and a relative record position within the
If we expect to have ‘r’ records to store in the table, we block.
should choose M locations for the address space such that
(r/M) is between 0.7 and 0.9. It may also be useful to choose
a prime number for M, since it has been demonstrated that Block
address
this distributes the hash addresses better over the address on disk
space when the ‘mod’ hashing function is used. Other hash 0 . . . . .
functions may require M to be a power of 2. 1
2 . . . . .
Bucket . .
External Hashing number .
.
.
.
.
.
. .
.
.
Hashing for disk files is called external hashing. To suit the . . .
n −2
characteristics of disk storage, the target address space is . . . . .
n −1
made of buckets, each of which holds multiple records. A
bucket is either one disk block or a cluster of contiguous
Bucket 0
22
Overflow
31
86 Record pointer

Record pointer
Record pointer
25 Record pointer
Bucket 1 NULL
62
74 Record pointer
57
81
Record pointer

Record pointer
Record pointer

Bucket 2
32
62

Record pointer

The hash function is h(k) = k mod 10 and the hashing records will fit in the allocated space. If the number of
scheme described above is called static hashing because a records turns out to be substantially fewer than (m * M), we
fixed number of buckets M is allocated. It can be a draw- are left with a lot of unused space.
back for dynamic files. Suppose that we allocate M buckets If the number of records increases to substantially more
for the address space and let ‘m’ be the maximum number than (m * M), numerous collisions will result and retrieval
of records that can fit in one bucket, then at most (m * M) will be slowed down because of the long lists of overflow
4.86 | Unit 4 • Databases

records. In either case, we may have to change the number The value of d can be increased and decreased by one at a
of blocks M allocated and then use a new hashing function time, thus doubling or halving the number of entries in the
(based on the new value of M) to redistribute the records. directory array. Doubling is needed if a bucket, whose local
These organizations can be quite time consuming for large depth d′ is equal to the global depth d, overflows. Halving
files. Newer dynamic file organizations based on hashing occurs if d > d′ for all the buckets after some locations
allows the number of buckets to vary dynamically with only occur. Most record retrievals require two block accesses:
localized reorganization. one to the directory and the other to the bucket.
The main advantage of extendible hashing is the per-
Hashing Techniques with Dynamic formance of the file does not degrade as the file grows,
File Expansion as opposed to static external hashing where collisions
increases and the corresponding chaining causes addi-
The disadvantage of static hashing is that the hash address
tional accesses. No space is allowed in extendible hashing
space is fixed. Hence, it is difficult to expand or shrink the
for future growth, but additional buckets can be allocated
file dynamically. The first scheme is extendible hashing, It
dynamically as needed. The space overhead for the direc-
stores an access structure in addition to the file hence it is
tory table is negligible.
similar to indexing. The main difference is that the access
Another advantage is that splitting causes minor reorgan-
structure is based on the values that result after applica-
ization in most cases, since only the records in one bucket
tion of the hash function to the search field. In indexing,
are redistributed to the two new buckets. The only time a
the access structure based on the values of the search field
reorganization is more expensive is when the directory has
itself. The second technique, called linear hashing, does not
to be doubled (or) halved.
require additional access structure.
A disadvantage is that the directory must be searched
These hashing schemes take advantage of the fact that
before accessing the buckets themselves, resulting in two
the result of applying a hashing function is a non-negative
block accesses instead of one in static hashing.
integer and hence can be represented as a binary number.
The access structure is built on the binary representation
of the hashing function result, which is a string of bits. We Indexing
call this the hash value of a record. Records are distributed Indexes are auxiliary access structures, which are used to
among buckets based on the values of the leading bits in speed up the retrieval of records in response to certain search
their hash values. conditions. The index structure typically provides secondary
access paths, which provide alternative ways of accessing the
Extendible Hashing records without affecting the physical placement of records
on disk. They enable efficient access to records based on the
In extendible hashing, a type of directory, an array of 2d indexing fields that are used to construct the index.
bucket addresses is maintained, where d is called the global Any field of the file can be used to create an index and
depth of the directory. The integer value corresponding to multiple indexes on different fields can be constructed on the
the first (high-order) d bits of a hash value is used as an same file. To find a record or records in the file based on a cer-
index to the array to determine a directory entry, and the tain selection criterion on an indexing field, one has to initially
address in that determines the bucket in which the corre- access the index, which points to one or more blocks in the
sponding records are stored. Several directory locations file where the required records are located. The most preva-
with the same first d′ bits for their hash values may contain lent types of indexes are based on ordered files (single-level
the same bucket address if all the records that hash to these indexes) and tree data structures (multilevel indexes, B+ trees).
locations fit in a single bucket. A local depth d′ is stored Dense Index files: Index record appears for every search-
with each bucket specifies the number of bits on which the key value in the file.
bucket contents are based.
Brighton A-217 Brighton 750
3
000 Downtown A-101 Downtown 600
Bucket A
001 Mianus A-110 Downtown 300
2 Perryridge A-215 Mianus 400
010
Bucket B
011
A102 Perryridge 800
100 2 Figure 3 Dense index file.

101 Bucket C
Sparse index files These files contain index records for
110 3 only some search-key values. Applicable when records are
111 Bucket D sequentially ordered on search key.
 Chapter 5 • File Management | 4.87

Brighton A-217 Brighton 700 Single-level Ordered Indexes

Mianus A-101 Downtown 710 A file with a given record structure consisting of several
fields (or attributes), an index access structure is usually
Red wood A-110 Downtown 800
defined on a single field of a file is called an indexing field
A-215 Mianus 600 or indexing attribute. The index typically stores each value
A102 Perryridge 680 of the index field along with a list of pointers to all disk
A-201 Perryridge 700 blocks that contain records with that field value. The values
in the index are ordered so that we can do a binary search
A-601 Red wood 700
on the index.
Figure 4 Sparse index file.
The index file is much smaller than the data file, so
searching the index using a binary search is reasonably effi-
Compared to dense index, sparse index takes less space and cient. Multilevel indexing does away the need for a binary
less maintenance over head for insertions and deletions. It is search at the expense of creating indexes to the index itself.
slower than dense index for locating records.
Types of Ordered Indexes
Index Update 1. Primary index
Record deletion If delete key was the only record in the 2. Clustering index
file with its particular search-key value, the search key is 3. Secondary index
deleted from the index also.
In dense index, delete the search key. Primary index A primary index is an ordered file whose
In spare index, if deleted key value exists in the index, records are of fixed length with two fields. The first field is
the value is replaced by next search-key value in the file. of the same data type as the ordering key field called the pri-
If the next search-key value already has an index entry, the mary key of the data file, and the second field is a pointer to
entry is deleted instead of being replaced. a disk block (block address). There is one index entry (index
record) in the index file for each block in the data file. Each
Record insertion In dense index, if the search-key value index entry has the value of the primary key field for the
doesn’t appear in the index insert it. record in a block and a pointer to that block as its two field
If index stores an entry for each block of the file, no values. The two field values of index entry i is <k(i), p(i)>.
change needs to be made to the index unless a new block Example:
is created. If a new block is created, the first search-key
NAME RNO DOB GRADE AGE
value appearing in the new block is inserted into the
Abhi
index.
Block 1 Agarkar

350 A-217 Brighton 750

A-101 Downtow 500
400 Akash
A-110 Downtown 600
500 Akram
A-215 Mianus 700 Block 2
600
A-102 Perryridge 400
700
A-201 Perryridge 900 Watson
750 Williams
A-218 Perryridge 700
900 Block n-1
A-222 Redwoo 700
A-305 Red will 350 Zaheer

Zakir
Block n Zamal

Figure 5 Secondary index.

To create a primary index on the ordered file shown in
Secondary index example: the above figure, we use the NAME field as primary key,
because that the ordering key field on the file (assuming that
1. Index record points to a bucket that contains pointers each value of NAME is unique). Each entry in the index has
to all the actual records with that particular search – a NAME value and a pointer. Some sample index entries
key value are as follows:
2. secondary index have to be dense
4.88 | Unit 4 • Databases

A record whose primary key value is k lies in the block

< k(1) = (Abhi), p(1) = address of block 1 >
whose address is p(i), where k(i) ≤ k ≤ k(i + 1). The ith
< k(2) = (Akram), p(2) = address of block 2 >
block in the data file contains all such records because of
< k(3) = (Brat), p(3) = address of block 3 >
the physical ordering of the file records on the primary key
The below figure illustrates this primary index. The total number field. To retrieve a record, given the value k of its primary
of entries in the index is the same as the number of disk blocks key field, we do a binary search on the index file to find
in the ordered data file. The first record in each block of the data the appropriate index entry i, and then retrieve the data file
file is called the anchor record of the block (or) block anchor. block whose address is p(i).
DATA FILE
The following example illustrates the saving in block
accesses that is attainable when a primary index is used to
(PRIMARY KEY FIELD) search for a record.
NAME RNO DOB GRADE AGE Example: Suppose that we have an ordered file with r =
INDEX FILE
Abhi 24,000 records stored on a disk with block size B = 512
Agarkar bytes. File records are of fixed size and are unspanned, with
(<k(i ), p(i )> entries)
record length R = 120 bytes.
BLOCK
ANCHOR Akash The blocking factor for the file would be bfr = B/R
BLOCK
PRIMARY POINTER
KEY VALUE Akram  512 
=  = 4.26 = 4 records per block
Abhi  120 
Akram
…. ….
….
The number of blocks needed for the file is
….
…. ….
Watson
Watson  r    24, 000 
Zakir b =   =   = 6000 blocks
Williams
 bfr    42 

Zaheer A binary search on the data file would need

Zakir
log2b = log26000 = 13 block accesses
Zamal
Example: For the above data, suppose that the ordering
key field of the file is V = 7 bytes long, a block pointer, P =
5 bytes long, and we have constructed a primary index for
Figure 6 Primary index on the ordering key field of the file. the file.
Indexes can also be characterized as dense or sparse. A The size of each index entry is Ri = (7 + 5) = 12 bytes, so
dense index has an index entry for every search-key value the blocking factor for the index is bfri = (B/Ri)
(every record) in the data file. A sparse (non-dense) index 512/12 = 42.66 = 42 entries per block.
has index entries only for some of the search values. A pri- The total number of index entries ri is equal to number of
mary index is non-dense (sparse) index, since it includes an blocks in the data file, which is 6000. The number of index
entry for each disk block of the data file and the keys of its blocks is hence
anchor record rather than for every search value. bi = (ri/bfri) = 6000/42 = 142 blocks
The index file for primary index needs fewer blocks than
does the data file, for two reasons as follows: To perform a binary search on the index file would need
log2bi = log2142 = 8 block accesses. To search for a
1. There are fewer index entries than there are records in record using the index, we need one additional block access
the data file. to the data file for a total of ‘9’ block accesses.
2. Each index entry is typically smaller in size than a
data record because it has only two fields. So more Disadvantage: A major problem with a primary index is
index entries than data records can fit in one block. insertion and deletion of records. If we attempt to insert a
record in its correct position in the data file, we have to not
A binary search on the index file requires fewer block only move records to make space for the new record but also
accesses than a binary search on the data file. The binary change some index entries.
search for an ordered data file required log2b block accesses.
But if the primary index file contains bi blocks, then to Clustering Index If records of a file are physically ordered
locate a record with a search-key value requires a binary on a non-key field, which does not have a distinct value for
search of that index and access to the block containing that each record, that field is called the clustering field. We can
record, a total of log2bi + 1 accesses. create a different type of index called clustering index to
 Chapter 5 • File Management | 4.89

speed up the retrieval of records that have the same value to different leaf nodes are of the same length (balanced path
for the clustering field. length). All leaf nodes are at the same depth level.
A clustering index is also an ordered file with two fields, This ensures that number of disk accesses required for
the first field is of the same type as the clustering field of the all the searches are same. The lesser the depth (level) of an
data file, and the second field is a block pointer. index tree, the faster the search.
There is one entry in the clustering index for each dis-
tinct value of the clustering field, containing the value and
Insertion into B+ tree
a pointer to the first block in the data file that has a record
with that value for its clustering field. Given nodes 8 5 1 7 3 12 Initially start with root node (has
The record insertion and deletion still cause problems, no children)
because the data records are physically ordered. To alleviate
the problem of insertion, reserve a whole block (or a cluster 5 8 Insert 1 (overflow)
of contiguous blocks) for each value of the clustering field,
all records with that value are placed in the block (or block
5
cluster). A clustering index is an example of a non-dense Insert 7
index, because it has an entry for every distinct value of the
1 5 8
indexing field which is a non-key.

Secondary Index A secondary index provides a secondary

means of accessing a file for which some primary access Overflow in Leaf Node
already exists. The secondary index may be on a field which Split the leaf node First, j = ceiling ((pleaf + 1)/2) entries are
is a candidate key and has a unique value in every record, or kept in the original node and the remaining moved to the
a non-key with duplicate values. The index is an ordered file new leaf.
with two fields. The second field is either a block pointer or
a record pointer. There can be many secondary indexes for 1. Create a new internal node, and jth index value is
the same file. replicated in the parent internal node.
First consider a secondary index access structure on a 2. A pointer is added to the newly formed leaf node.
key field that has a distinct value for every record such a
field is some times called a secondary key. 5
The records of the data file are not physically ordered
1 5 7 8
by values of the secondary key field, we cannot use block
anchors. That is why an index entry is created for each
record in the data file, rather than for each block, as in the Insert 3 → overflow
case of a primary index.
3 5
B- Trees
1. A commonly used index structure 1 3 5 7 8
2. Non-sequential, ‘balanced’
3. Adapts well to insertions and deletions Insert 12 (overflow, split propagates, new level)
4. Consists of blocks holding at most n keys and n + 1
pointers. 5
5. We consider a variation actually called a B+ tree
3 7 8
B+ Trees
B+ trees are a variant of B– trees. In B+ trees data stored only 1 3 5 7 8 12
in leaves, leaves form a sorted linked list.
Parameter – n
Branching factor – n + 1
Overflow in Internal Node
30 120 240 Split the internal node, the entries up to Pj where j = floor ((p
Keys 240 ≤ k + 1)/2) are kept in the original node and remaining moved to
the new internal node
Keys k < 30 Keys 120 ≤ k < 240
1. Create a new internal node and the jth index value
Keys 30 ≤ k ≤ 120
is moved to the parent internal node (without
Each node (except root) has at least n/2 keys. B– tree stands replication)
for balanced tree. All the paths through a B– tree from root 2. Pointers are added to the newly formed nodes.
4.90 | Unit 4 • Databases

3. B+ tree ensures some space always left in nodes for 3. Each node in a tree should correspond to a block of
new entries. Also makes sure all nodes are at least data.
half full. 4. Each node can store many data items and has many
successors.
5. The B– tree has fewer levels but search for an item
Deletion in B+ Trees
takes more comparisons at each level.
Delete 5,12,9 from the below B+ tree: 6. If a B– tree has order ‘d’, then each node (except root)
7
has at least d/2 children, then the depth of the tree is
at most log d/2 (size) + 1.
1 6
9
7. In the worst case, we need (d - 1) comparisons in
each node (using linear search)
1 5 6 7 8 9 8. Fewer disk accesses are required compared to binary
12
Tree.
Delete 5: 9. The usual data structure for an index is the B+ tree.
10. Every modern DBMS contains some variant of B–
7 trees in addition with other index structures depending
on the application.
11. B– trees and B+ trees are one and the same. They differ
1 6 9 from B– trees in having all data in the leaf blocks.
12. Compared to binary trees, B– trees will have higher
branching factor.
1 6 7 8 9 12 13. Binary trees can degenerate to a linear list,
B– trees are balanced, so this is not possible.
Delete 12: 14. In B+ tree, the values in inner nodes are repeated in
Under flow has occurred, so redistribute. the leaf nodes.
7 15. The height of the tree might decrease, because the
data pointer is needed only in the leaf nodes, we can
1 6 8 also get a sorted sequence.
16. In B– trees, all leaves have the same distance from
1 6 7 8 9
root hence B– trees are balanced. This ensures that the
chain of links followed to access a leaf node is never
Delete 9: Underflow (merge with left) redistribute.
too long.
6 17. The time complexity of search operation in B– tree
1 7 (tree height) is O(log n), where ‘n’ is the number of
entries.
1 6 7 8
18. Advantage of B+ tree automatically reorganizes itself
with small and local changes while doing insertions
Advantages and deletions, reorganization of entire file is not
required to maintain performance.
1. B– Trees and B+ trees: B– tree is a data structure used
19. Disadvantage of B+ tree, extra Insertion and deletion
for external memory.
overhead, space overhead.
2. B– trees are better than binary search trees if data is
20. B+ trees can be used as dynamic multilevel Indexes.
stored in external memory.

Exercises
Practice Problems 1 (A) 124000 (B) 1260000
Directions for questions 1 to 20: Select the correct alterna- (C) 5120000 (D) 512000
tive from the given choices. (ii) What is the capacity of disk excluding Inter block
1. Consider the following specifications of a disk. Block gap?
size of a disk is 512 bytes, inter-block gap size is 128 (A) 25400 (B) 25600
bytes Number of blocks per track is 20 and number of (C) 25800 (D) 25900
tracks per surface is 400. 2. Consider the following specifications of a disk. Block
(i) What is the capacity of disk including Inter block size of disk is 512 bytes, 2000 tracks per surface, 50
gap? sectors per track and 5 double sided platters.
 Chapter 5 • File Management | 4.91

(i) What is the capacity of track in bytes? (i) What is the blocking factor?
(A) 4096000 (B) 4086000 (A) 16 (B) 17
(C) 4076000 (D) 4066000 (C) 18 (D) 19
(ii) What is the capacity of surface in bytes? (ii) What is the number of blocks needed for the file?
(A) 25600000 (B) 512000 (A) 2642 (B) 2644
(C) 5120000 (D) 51200000 (C) 2646 (D) 2648
(iii) What is the capacity of disk in bytes? (iii) How many block accesses are required to search
(A) 512*10^4 (B) 512*10^5 for a particular data file using binary search?
(C) 512*10^6 (D) 512*10^7 (A) 10 (B) 11
(iv) How many cylinders does it have? (C) 12 (D) 13
(A) 512 (B) 1000 8. Suppose that the ordering key field of the file is 12
(C) 2000 (D) 2048 bytes long, a block pointer is 8 bytes long, and we have
(v) Identify the In valid disk block size from below: constructed a primary index for the file. Consider the
(A) 2048 (B) 51200 file specifications given in the above questions.
(C) 4098 (D) 4096 (i) What is the size of each index entry?
3. What is the order of internal node of B+ tree suppose (A) 16 (B) 18
that a child pointer takes 6 bytes, the search field value (C) 20 (D) 22
takes 14 bytes and the block size is 512 bytes? (ii) What is the blocking factor for the index?
(A) 23 (B) 24 (A) 101 (B) 102
(C) 25 (D) 26 (C) 103 (D) 104
4. The order of a leaf node in a B+ tree is the maximum (iii) What is the total number of index entries?
number of (value, data, record pointer) pairs it can (A) 2642 (B) 2644
hold. Given that block size is 1 k bytes (1024 bytes), (C) 2646 (D) 2648
data record pointer is 7 bytes long, the value field is ‘9’ (iv) What is the number of index blocks?
bytes long and block pointer is 6 bytes. (A) 22 (B) 24
(A) 63 (B) 64 (C) 26 (D) 28
(C) 65 (D) 66
(v) How many block accesses are required, if binary
5. The following key values are inserted into a B+ tree search is used?
in which order of the internal nodes is 3, and that of (A) 3 (B) 4
the leaf nodes is 2, in the sequence given below. The (C) 5 (D) 6
order of internal nodes is the maximum number of tree
pointers in each node, and the order of leaf nodes is the 9. For the file specifications given in Q. No. 7, if we con-
maximum number of data items that can be stored in it. struct secondary index on a non-ordering key field of
The B+ tree is initially empty. 10, 3, 6, 8, 4, 2, 1. What the file that is 12 bytes long, a block-pointer of size 8
is the maximum number of times leaf nodes would get bytes, each index entry is 20 bytes long and the block-
split up as a result of these insertions? ing factor is 102 entries per block.
(A) 3 (B) 4 (i) What is the total number of index blocks?
(C) 5 (D) 6 (A) 422 (B) 424
6. For the same key values given in the above question, sup- (C) 442 (D) 444
pose the key values are inserted into a B– tree in which (ii) How many block accesses are required to access
order of the internal nodes is 3 and that of leaf nodes is 2. the secondary index using binary search?
The order of internal nodes is the maximum number of (A) 6 (B) 7
tree pointers in each node and the order of leaf nodes is (C) 8 (D) 9
the maximum number of data items that can be stored 10. For the file specifications given in Q. No. 8, if we construct
in it. The B– tree is initially empty. What is the maxi- a multilevel index, number of 1st-level blocks are 442,
mum number of times leaf nodes would get split up as blocking factor is 102, each index entry is 20 bytes long.
a result of these insertions?
(A) 1 (B) 2 (i) What is the number of 2nd-level blocks?
(C) 3 (D) 4 (A) 4 (B) 5
(C) 6 (D) 7
7. Suppose that we have an ordered file with 45,000
records stored on a disk with block size 2048 bytes. (ii) What is the number of 3rd-level blocks?
File records are of fixed size and are unspanned with (A) 0 (B) 1
record length 120 bytes. (C) 2 (D) 3
4.92 | Unit 4 • Databases

11. Construct a B+ tree for (1,4,7,10,17,21,31) with n = 4, 16. What will be the number of index records/block?
which nodes will appear two times in a final B+ tree? (A) 68 (B) 65
(A) 17,7,20 (B) 17,7,20,25 (C) 69 (D) None
(C) 17,20,25 (D) 7,17.25 17. What will be the number of index blocks?
12. Suppose the hash function is h(x) = xmod 8 and each (A) 442 (B) 440
bucket can hold at most two records. The extendable (C) 400 (D) None
hash structure after inserting 1, 4, 5 ,7, 8, 2, 20, what is
18. Consider the following:
the local depth of ‘4’?
(A) 0 (B) 1 Block size = 1025 bytes
(C) 2 (D) 3 Record length in data file = 100 bytes
13. Consider the given B+ tree, insert 19 into the tree, what Total number of records = 30000
would be the new element in level 2? Search key = 9 bytes
13 30 Pointer = 6 bytes
What is the number of index blocks?
5 10 20 40 50 (A) 44 (B) 45
(C) 46 (D) None
1 4 5 9 11 12 13 18 20 29 30 38 41 45 60 70 19. Which of the following is maximum search time tmax in
B– trees?
(A) 13 (B) 18
(C) 20 (D) 29
(A) t = a log  N   a + d + bm + c 
14. Consider the given B+ tree, delete 70 and 25 from the max 2  
 2   log 2 m log 2 m 
tree, what are the elements present in level 2? (∴ root
is at level 1)
 N  a + d bm 
60 (B) tmax = a log 2    + + c
 2   log 2 m log 2 m 
25 50 75 85
 a+d bm 
(C) tmax = a log 2 N  + + c
 log 2 m log 2 m 
5 10 15 20 25 28 30 50 55 60 65 70

75 80 85 90 95  a bm 
(D) tmax = a log 2 ( N )  + + c
 log 2 m log 2 m 
(A) 25, 50, 75 (B) 25, 50,75, 85
(C) 28, 50, 75, 85 (D) 28, 50, 65, 75 20. Consider a B+ tree. A child pointer takes 3 bytes, the
15. Delete 60 from the above given tree (Q. No. 14). After search field value takes 7 bytes, and the block size is
deletion, what is the total number of nodes present in 256 bytes. What is the order of the internal node?
the tree? (A) 63 (B) 64
(C) 65 (D) 66
60

25 50 75 85

5 10 15 20 25 28 30 50 55 60 65 70

75 85 85 90 95

(A) 5 (B) 6
(C) 7 (D) 8
 Chapter 5 • File Management | 4.93

Practice Problems 2 (A) When a transaction Ti issues a read (Q) operation, the
Directions for questions 1 to 20: Select the correct alterna- system issues a lock s(Q) instruction followed by the
tive from the given choices. read instruction.
(B) When Ti issues a write Q operation, the system
1. Which of the following is true? checks to see whether Ti already holds a shared
(A) Every conflict serializable is view serializable lock on Q. If it does, then the system issues an
(B) Every view serializable is conflict serializable upgrade Q instruction followed by the write Q
(C) Both A and B instruction, otherwise the system issues a lock
(D) A schedule can be either only conflict serializable -X(Q) instruction, followed by the write Q
or only view-serializable. instruction.
2. Which one is the 2-phase locking rule? (C) All locks obtained by a transaction are unlocked
(A) Two transactions cannot have conflicting locks after that transaction commits or aborts.
(B) No unlock operation can precede a lock operation (D) All of the above
in the same transaction. 8. Which one is correct?
(C) No data is/are affected until all locks are obtained (A) A lock manager can be implemented as a process
and until the transaction is in its locked point. that receives messages from transactions and sends
(D) All of the above messages in reply.
3. If Transaction Ti has obtained an exclusive mode lock (B) It uses linked list of records.
on item Q, then (C) It uses hash table called lock table.
(A) Ti can read Q (D) All of the above
(B) Ti can write Q Common data questions 9 and 10: Transaction T1 has 5
(C) Ti can read and write instructions. Transaction T2 has 3 instructions.
(D) Neither read nor write
9. The number of non-serial transactions will be
4. Phantom phenomenon is (A) 15 (B) 8
(A) A transaction retrieves a collection of objects but (C) 2 (D) 56
sees same result.
10. The number of serial transaction schedules will be
(B) A transaction retrieves a collection of objects but
(A) 15 (B) 8
sees different results.
(C) 2 (D) 56
(C) Transaction T1 waits for T2 and T2 waits for T1
(D) This problem arises when the transaction has not 11. In a heap file system, which of the following function
locked all the objects. finds ‘average number of blocks to be read’?

5. We can avoid the starvation of transactions by granting i 1 n

(A) = (1 + n) =
locks by following manner: n 2 2
When a transaction Ti requests a lock on a data item Q i 1 n
∑
n
in a particular mode M, the concurrency control man- (B) i =1
= (1 + n) =
n 2 2
ager grants the lock provided that
(A) There is no other transaction holding a lock on Q i 1 n
∑
n −1
(C) = (1 + n) =
in a mode that conflicts with M. i =0
n 2 2
(B) There is no other transaction that is waiting for a
(D) All of the above
lock on Q,
(C) (A) and (B) 12. What is the disadvantage in one directory per user?
(D) None (A) Different applications can be divided into separate
groups.
6. Which one is correct?
(B) Different applications cannot be divided into sepa-
(A) Upgrading can take place only in shrinking phase
rate groups
(B) 
Upgrading can take place only in growing
(C) All files are in a single group
phase.
(D) All of the above
(C) 
Downgrading can take place only in growing
phase 13. What are the possible violations if an application pro-
(D) (A) and (C) both gram uses isolation-level ‘Read uncommitted’?
7. A simple but widely used scheme automatically gen- (A) Dirty read problem
erates the appropriate lock and unlock instructions for (B) Non-repeatable read problem
a transaction, on the basis of read and write requests (C) Phantom phenomenon
from the transaction: (D) All of the above
4.94 | Unit 4 • Databases

14. The two-phase locking protocol 18. To have a file, holding a list is necessary to
(A) ensures serializability (i) Identify the records in the list
(B) issues locks in two phases
(ii) Identify the name, and type of the fields of each
(C) unlocks in two phases
record.
(D) All of the above
(iii) Decide which fields will be used as sort of index
15. The point in the schedule where the transaction has obtained
keys.
its final lock (the end of its growing phase) is called the
(A) Only (i) and (ii)
(A) block point (B) critical section
(B) Only (i) and (iii)
(C) growing point (D) lock point
(C) Only (ii) and (iii)
16. Which of the following is not a problem of file manage- (D) All of the above
ment system?
19. Two files may be joined into a third file, if the following
(A) Data redundancy
is true:
(B) Lack of data independence
(A) if they have row in common
(C) Program dependence
(B) if they have a field in common
(D) All of the above
(C) Both (A) and (B)
17. Which of the following is/are true about master list of (D) None
an index file?
20. The minimum number of record movements required to
(i) Is sorted in ascending order merge four files w(with 10 records), x(with 20 records),
(ii) A number is assigned to each record. y(with 15 records) and z(with 5 records) is:
(A) Only (i) (B) Only (ii) (A) 50 (B) 40
(C) Both (i) and (ii) (D) None of the above (C) 30 (D) 35

Previous Years’ Questions

1. A clustering index is defined on the fields which are of tree pointers in each node, and the order of leaf
of type [2008] nodes is the maximum number of data items that can
(A) non-key and ordering be stored in it. The B+ tree is initially empty.
(B) non-key and non-ordering 10, 3, 6, 8, 4, 2, 1
(C) key and ordering
(D) key and non-ordering The maximum number of times leaf nodes would get
split up as a result of these insertions is [2009]
2. A B– tree of order 4 is built from scratch by 10 succes- (A) 2 (B) 3
sive insertions. What is the maximum number of node (C) 4 (D) 5
splitting operations that may take place? [2008] 5. Consider a B tree in which the maximum number of
+
(A) 3 (B) 4 keys in a node is 5. What is the minimum number of
(C) 5 (D) 6 keys in any non-root node? [2010]
3. Consider a file of 16384 records. Each record is 32 (A) 1 (B) 2
bytes long and its key field is of size 6 bytes. The file (C) 3 (D) 4
is ordered on a non-key field, and the file organization 6. An index is clustered, if [2013]
is unspanned. The file is stored in a file system with (A) it is on a set of fields that form a candidate key.
block size 1024 bytes, and the size of a block pointer (B) it is on a set of fields that include the primary
is 10 bytes. If the secondary index is built on the key key.
field of the file, and a multilevel index scheme is used (C) the data records of the file are organized in the
to store the secondary index, the number of first-level same order as the data entries of the index.
and second-level blocks in the multilevel index are (D) the data records of the file are organized not in
respectively [2008] the same order as the data entries of the index.
(A) 8 and 0 (B) 128 and 6
7. A file is organized so that the ordering of data records
(C) 256 and 4 (D) 512 and 5
is the same as or close to the ordering of data entries
4. The following key values are inserted into a B+ tree in some index. Then that index is called [2015]
in which order of the internal node s is 3, and that (A) Dense (B) Sparse
of the leaf nodes is 2, in the sequence given below. (C) Clustered (D) Unclustered
The order of internal nodes is the maximum number
 Chapter 5 • File Management | 4.95

8. With reference to the B+ tree index of order 1 shown each non-leaf node of the tree is ________.[2015]
below, the minimum number of nodes (including the 10. B+ Trees are considered BALANCED because
Root node) that must be fetched in order to satisfy the  [2016]
following query: “Get all records with a search key (A) The lengths of the paths from the root to all leaf
greater than or equal to 7 and less than 15” is _______ nodes are all equal.
[2015] (B) The lengths of the paths from the root to all leaf
9 nodes differ from each other by at most 1.
(C) The number of children of any two non - leaf sib-
5 13 17 ling nodes differ by at most 1.
(D) The number of records in any two leaf nodes dif-
1 3 5 7 9 11 13 15 17
fer by at most 1.
11. In a B+ tree, if the search-key value is 8 bytes long,
9. Consider a B+ tree in which the search key is 12 bytes
the block size is 512 bytes and the block pointer size
long, block size is 1024 bytes, record pointer is 10
is 2 bytes, then the maximum order of the B+ tree is
bytes long and block pointer is 8 bytes long. The max-
__________. [2017]
imum number of keys that can be accommodated in

Answer Keys
Exercises
Practice Problems 1
1. (i) C (ii) A 2. (i) B (ii) D (iii) C (iv) C (v) C 3. C 4. A 5. C 6. B
7. (i) B (ii) D (iii) C 8. (i) C (ii) B (iii) D (iv) C  (v) C 9. (i) C (ii) D
10. (i) B (ii) B 11. B 12. D 13. B 14. C 15. B 16. A 17. A 18. B
19. A 20. C
Practice Problems 2
1. A 2. D 3. C 4. B 5. C 6. B 7. D 8. D 9. D 10. C
11. B 12. B 13. D 14. D 15. D 16. D 17. B 18. D 19. B 20. B

Previous Years’ Questions

1. A 2. C 3. C 4. C 5. B 6. C 7. C 8. 5 9. 50 10. A
10. 52
4.96 | Unit 4 • Databases

Test

Databases Time: 60 min.

1. Which of the following are used in DBMS files? (A) (i) only (B) (i) and (iii)
(i) Data dictionary (ii) DML (C) (i), (ii) and (iii) (D) (iii) and (iv)
(iii) Query language (iv) Transaction log 8. In which of the following, the structure of data files is
(A) (i) and (ii) (B) (ii) and (iii) stored?
(C) (iii) and (iv) (D) (i) and (iv) (A) Metadata (B) Database catalog
2. Which among the following is not a problem of file (C) Database schema (D) Data model
management system? 9. A schedule is a collection of
(A) Data redundancy (A) Data models (B) Transactions
(B) Lack of data independence (C) Schemas (D) Tables
(C) Program independence
10. Select from the following which matches the term
(D) None of these
‘Impedance mismatch problem’:
3. A transparent DBMS (A) In compatibility of storage and data structure
(A) cannot hide sensitive information from users (B) Mismatch in user authentication
(B) keeps its logical structure hidden from users (C) File structure mismatching
(C) keeps its physical structure hidden from users (D) None of these
(D) All of the above
11. Which of the following is not a/an integrity constraint?
4. If the field size is too small, for the longest piece of data (A) Entity integrity
to be entered, (B) Candidate key constraint
(A) database program will be freezed (C) Business rules
(B) field will automatically expand (D) None of the above
(C) part of the data will be cut off
(D) All of the above 12. Select from the following which is concerned with
‘Query Optimizer’:
5. Which of the following functional dependencies are (A) Extracts DML commands from an application
satisfied by the instance from the below relation? program in a high-level language
A B C (B) Parsing and analyzing interactive query
1 7 3 (C) Rearrangement and reordering of operations and
1 9 5 elimination of redundancies
1 11 5 (D) Performance monitoring
5 3 3 13. Which of the following does not belong to database
(A) AB → C and C → B model?
(B) BC → A and B → C (A) Relational Model (B) Distributed Model
(C) BC → A and A → C (C) Hierarchical Model (D) Network Model
(D) AC → B and B → A 14. What is the correct sequence of database design
6. Let E1 and E2 be two entities in an E/R diagram with process?
single-valued attributes, R1 and R2 are two relationships (i) Create conceptual schema
between E1 and E2, R1 is one to many R2 is many-to-one. (ii) Data model mapping
R1 and R2 do not have any attributes of their own. What (iii) Requirement collection and analysis
is the minimum number of tables required to represent (iv) Physical design
this situation in the relation model? (A) iii →i →ii → iv
(A) 2 (B) 3 (B) iii → ii → i → iv
(C) 4 (D) 5 (C) i → ii → iii → iv
7. Which of the following is true about DBMS? (D) i → iii → ii → iv
(i) Low-level DMLs are record-at-a time 15. Consider the following schema definitions
(ii) High-level DMLs are set oriented or set-at-a time Employee {Name, SSN, Address, DNo}
(iii) Query in high-level DML specify which data to Department {DName, DNumber, Manager, SSN}
retrieve rather than how. Which among the following expressions represent the
(iv) When used as standalone, DML is called ‘host query ∏name, address(σDname = ‘Res’ ∧ DNumber = DNo (Department
language’  Employee)?
 Test | 4.97

(A) Retrieve the name and address of employees who (C) π a1 , a2 ... an σ P ( r1 ∪ r2 ∪×…× ∪rm )
work for the project no ‘Dno’
(B) Retrieve the name and address of all employees (D) π a , a ... a σ P ( r1r2 ×…× rm )
1 2 n

who control the ‘Res’ department.

(C) Retrieve the name and address of all employees 20. Let R1­(A, B, C) and R2(D, E) be two relation schemas
who work for the ‘Res’ department. with primary keys A and D and C be a foreign key in
(D) None of these R1 referring to R2. Suppose there is no violation of the
above referential integrity constraint in the instances r1
16. Select from the following which closely resembles the and r2, which of the following relational algebra expres-
concept ‘Degree of a relationship’: sion would necessarily produce an empty relation?
(A) Number of entities participating in a relation (A) pD(r2) - pC(r1)
(B) Number of entity types participating in a relation (B) pC(r1) - pE(r2)
(C) Number of strong entity types in a relation (C) pD(r1  C = D r2) - pB(r1)
(D) Number of weak entity types in a relation (D) pC(r1  C = E r2)
17. Consider the following statements in a database: 21. Let r be an instance for the schema R = (A, B, C, D). Let
(i) No primary key value can be NULL r1 = π A, B , C ( r )r2 = π A, D ( r ) and S = r1  r2. Also given
(ii) A tuple in one relation which refers to another re- that the decomposition of r into r1 and r2 is lossy, which
lation must refer to an existing tuple in that rela- of the following is true?
tion (A) S ⊂ r (B) r ∪ s = r
(iii) The value of x determines the value of y in all (C) r ⊂ s (D) r  s = s
states of a relation, where x and y are two attrib-
utes of the relation Which of the following combi- 22. Which of the following is/are logical database
nations matches the given statements in order? structures?
(A) Referential integrity, functional dependency, en- (A) Network (B) Tree
tity integrity. (C) Chain (D) All of the above
(B) Functional dependency, entity integrity, referential 23. A relational database management system manages
integrity data in more than one file at a time by using which of
(C) Entity integrity, functional dependency, referential the following combinations?
integrity. (A) Tables and tuples
(D)  Entity integrity, referential integrity, functional (B) Relations and tuples
dependency (C) Tables and Relations
18. Consider the following relation schemas: (D) Attributes and tuples
Works (emp_name, comp_name,salary) 24. Let Emp = (Name, ID, ADDRESS, PHONE, SPOUSE,
Livesin (emp_name, street, city) LIVINGAT) be a relation scheme with following FDs,
which one of the following is a key
Location (comp_name, city)
ADDRESS → Phone
Manager (manager_name) SPOUSE → NAME
What is returned by the following relational algebra SPOUSE, ADDRESS → PHONE
expression NAME → ID
π emp _ name (σ comp − name = Time ∧ [Link] _ name = live sin . emp _ name ) (A) ADDRESS, PHONE
(B) SPOUSE, ADDRESS
(Works  Livesin) (C) NAME, SPOUSE
(A) Names of all employees who work for TIME (D) NAME, ADDRESS
(B) Names of all employees of TIME who lives in the
25. Consider the following E-R diagram
same city
(C) Names of people who live in the same city
Sname Quantity Proj_name
(D) None of these
19. Consider the following SQL query:
SUPPLIER SUPPLY PROJECT
Select distinct a1, a2, …, an from r1, r2…rm where P
This query is equivalent to one of the following rela- Part_no
tional algebra expression: PART
(A) π a , a ... a σ P (r1 × r2 × ... × rm )
1 2 n
Select the most appropriate statement from the follow-
(B) π a1 , a2 ... an σ P ( r1r2 ×…× rm )
ing for the above ER diagram:
4.98 | Unit 4 • Databases

(A) Represents a ternary relationship 28. What does the following relational algebra expression
(B) Represents a binary relationship represent?
(C) Represents a ternary relationship with instances of pid ( pid­, mob_no(Employee-Guests))
the form (s, j, p) (A) Id of all employees working with the company
(D) Represents 1 – to – many relationships (B) Id of all permanent employees
26. If two relations R1 and R2 are such that they are of the (C) Id of part time employees
same degree and domain of the corresponding fields (D) None of these
are also the same, then which one of the following is Common data for questions 29 and 30:
true about R1 and R2? 29. Let R1 and R2 be two relations with attributes a1 and a2.
(A) R1 ⊂ R2 P1 and P2 be two predicates.
(B) R1 ∪R2 = R2 ∪ R1  Select the expression from the following which is
(C) R1 and R2 are union compatible wrong:
(D) None of these
(A) σ P1 (σ P1 ( R1 )) → σ P2 (σ P2 ( R1 ))
Common data questions for 27 and 28: Let Employee
(B) σ P1 (π a1 ( R1 )) → π (σ a1 (σ P1 ( R1 )))
and Guests be two relations with attributes (id, mobl_no,
name, address) and (id, mob–no, comps_working, shifts) (C) σ P1 ( R1 ∪ R2 ) → σ P1 ( R1 ) ∪ σ P2 ( R2 )
Relations respectively {id, mob_no} is the key for both. (D) π a2 (σ a1 ( R1 )) → σ P1 (π a2 ( R1 ))
27. Which of the following queries are equivalent? 30. Select from the following corresponding TRC for the
(i) pid (Employee  Guests) wrong expression in the above question:
(ii) pid (Employee)  pid(Guests)
(A) {t/ ∃u, R1(t[P1]) = R2(u[P1])}
(iii) pid{(Employee-Guest) ∩ Guest-Employee)}
(B) {t/ u, R1(t[P1]) = R1(u[P1])}
A
(iv) pid { pid, mob (Employee) ∩ pid, mob (Guest)}
(A) (ii) and (iii) (B) (ii), (iii) and (iv) (C) {t/ ∃u, R1(t[P1]) ≠ R2(u([P1])}
(C) (i), (ii) and (iv) (D) (ii) and (iv) only (D) {t/‫(ד‬t∈R1)}

Answer Keys
1. D 2. D 3. C 4. C 5. B 6. B 7. C 8. B 9. B 10. A
11. B 12. C 13. B 14. A 15. C 16. A 17. D 18. C 19. A 20. A
21. C 22. D 23. C 24. B 25. C 26. C 27. C 28. B 29. A 30. B