Database Management System - DSM 206

**This material is only for MSDSM 2022 (joint program by IIM Indore and IIT Indore) students.
The material should not be shared with others.
08/08/2022 Indian Institute of Technology Indore
 Course Roadmap

. Chapter 1 Introduction to Databases

Chapter 2 Integrity Constraints and ER Model

Chapter 3 Relational Databases and Schema Refinement

Chapter 4
Query Language

Chapter 5 Transaction and Concurrency Control

Chapter 6 Indexing

Chapter 7 Object-based Database

 Example of Relation

attributes
(or columns)

tuples
(or rows)

Table: Faculty

Database Management System 1.3

 Relation
 Columns are attributes
 Rows are tuples or records
 The set of allowed values for each attribute is called the domain of
the attribute
 Attribute values are (normally) required to be atomic; that is,
indivisible

Database Management System 1.4

 Candidate Key
 Key
 Attribute of a relation/table
 Candidate Key
 Attribute that uniquely identify any two tuples in a table
 E.g., In Faculty table, Candidate Key (CK): {ID}
 To identify if two faculties are same or different
 In a Table, there can be more than one CKs
 Question: In a Student Table, what can be possible CK?
 roll_no, registration_no, email_id

 Study (sid, cid)

Database Management System 1.5

 Candidate Key
 In Student table, CK: {roll no, registration no, email id}
 To identify if two students are same or different

Database Management System 1.6

 Candidate Key
 Question?
 Can we use DOB as CK?

Database Management System 1.7

 Candidate Key
 Question
 Can we use name as CK?

Database Management System 1.8

 Primary Key
 Primary Key
 One of the candidate keys that is not Null: Unique + Not Null
 A Table can have only one Primary Key
 Examples
 In Student table, Primary Key can be either Roll No. or Registration No.
 In Aadhaar Card Database, Primary Key can be Aadhaar No.

Database Management System 1.9

 Primary Key
 Question?
 In Student Table, Aadhaar card can be one of the possible
Primary Keys?

Database Management System 1.10

 Primary and Alternate Keys
 SQL query to create Primary Key:

 CREATE TABLE Student (

RollNo int NOT NULL,
LastName varchar(255) NOT NULL,
FirstName varchar(255),
Age int,
PRIMARY KEY (RollNo) );

 Primary Key is usually assigned by the organization

 Alternate Key
 Set of candidate keys that are not primary key

Database Management System 1.11

 Super Key
 Combination of all possible attributes which can uniquely identify two
tuples in a table
 Super set of a candidate is a super key
 Minimal super key is a candidate key
 For Example
 Consider a relation/table student(id, name), where id is a
candidate key
 Possible super keys = {id}, {id name}

 Student(id,name,rollNo)

 SK = {id rollNo}, {id name}, , {id }, {id name rollNo}

Database Management System 1.12

 Class Activity
 How many possible super keys
 A set of n attributes with two attribute (combined) as candidate key

 R(a) = 1 = 2 ^(1-1)

 R(a,b) = 2 = 2 ^(2-1)

 R(a,b,c) = 4 = 2^(3-1)

 R(a,b,c,d) = {a,ab,ac,ad,abc,acd,abd,abcd} = 8 = 2 ^(4-1)

Database Management System 1.13

 Class Activity
 How many possible super keys
 A set of n attributes with two combined attribute as candidate key
(composite key as candidate key)

Database Management System 1.14

 Class Activity
 How many possible super keys
 A set of n attributes with two attributes as candidate keys

 (abcd)

Database Management System 1.15

 Class Activity
 Minimum and maximum super keys in a relation of n attributes?

 1
 (a) = 1

 (a, b) = 3

 (a, b, c) = a, b,c, ab,ac,cb, abc = 7 = 2^n -1

Database Management System 1.16

 Super Key
 Example: R(A1, A2, A3, A4), Candidate keys (CK) = {A1, A2A3}
 No of super keys (SK) = ?

Set of SK

Set of CK

Database Management System 1.17

 Class Activity
 Consider a relation R(A1, A2, A3, A4), where candidate keys are {A1A2,
A2A3}
 How many possible super keys?

Database Management System 1.18

 Super Key

Question: Can you tell if A2A3 is a super key?

Database Management System 1.19

 Super Key

Database Management System 1.20

 Foreign Key
 Foreign Key
 Attribute or set of attributes that references to primary key of
same table or another table
 Used to relate one table with other table
 Maintains referential integrity
 In a Table, there can be more than one foreign key
 Integrity
 Maintain same value in database
 Foreign key integrity
 Maintains referential integrity while inserting deleting and updating
in the database

Database Management System 1.21

 Foreign Key: Example
Updation in referencing table:
Will not cause problem
May cause problem
Will cause problem

Roll_no (pk) Name Address Course_id Course_name Roll_no (fk)

2 Subham Indore C1 Database Null

3 Shyam Delhi C2 Data Mining 5

5 Bharat Bangalore C3 CN Null

4 dshj Indore C4 C 3

Base Table/Referenced Table: Student

Referencing Table: Course

 To relate two tables, one attribute should be common in two tables

In the above tables, Roll_no is common and that is also acting as a Foreign Key
What is the meaning of Roll_no in Course table is taking reference from Roll_no in Student table?
Database Management System 1.22
 Foreign Key
 How to create Foreign Key
 CREATE TABLE Course (
Course_id Varchar(10),
Course_name Varchar(20),
Roll_no int,
PRIMARY KEY (Course_id),
FOREIGN KEY (Roll_no) REFERENCES Student(Roll_no)
);

Database Management System 1.23

 Foreign Key: Class Activity
 Insertion in referenced table:
 Will not cause problem
 May cause problem
 Will cause problem

Database Management System 1.24

 Foreign Key: Class Activity
 Deletion in referenced table:
 Will not cause problem
 May cause problem
 Will cause problem

Database Management System 1.25

 Foreign Key: Class Activity
 Updation in referenced table:
 Will not cause problem
 May cause problem
 Will cause problem

Database Management System 1.26

 Foreign Key: Class Activity
 Insertion in referencing table:
 Will not cause problem
 May cause problem
 Will cause problem

Database Management System 1.27

 Foreign Key: Class Activity
 Deletion in referencing table:
 Will not cause problem
 May cause problem
 Will cause problem

Database Management System 1.28

 Foreign Key: Class Activity
 Updation in referencing table:
 Will not cause problem
 May cause problem
 Will cause problem

 ReferencinG (GUI)
 ReferenceD (DDU)

Database Management System 1.29

 Referential Integrity
 Insertion in Referenced Table or Base Table
 No violation
 Deletion or updation in Referenced Table or Base Table
 May create problem
 Insertion and updation in Referencing Table
 May create problem
 Deletion in Referencing Table
 No violation
Roll_no (pk) Name Address Course_id Course_name Roll_no (fk)

1 Ram Delhi C1 Database 1

2 Subham Indore C2 Data Mining 2

3 Shyam Delhi c3 CN 3

4 Rohan Mumbai c4 C 3

5 Bharat Bangalore c5 OS 5

Referenced Table: Student Referencing Table: Course

Database Management System 1.30

 Maintain Referential Integrity
 Deletion in Referenced Table
 On Delete Cascade
 If referential integrity violation occurs, delete corresponding
record from both the tables
 On Delete No Action
 Referenced attribute value deletion is restricted, if this attribute
is referred by foreign key of referencing table
– If it is essential to delete, delete in referencing table then in
referenced table
 On Delete Set Null
 If referential integrity violation occurs, place NULL in the
corresponding foreign key attribute

Database Management System 1.31

 Class Activity
 Can you always apply On Delete Set Null?

Database Management System 1.32

 Maintain Referential Integrity
 Updation in Referenced Table
 On Update Cascade
 On Update No Action
 On Update set Null
 Insertion and Updation in Referencing Table
 If any violation, restrict operations

Database Management System 1.33

 Foreign Key
 How I will remember!!
 GUI
 DDU

Database Management System 1.34

 ER Model
 ER Model
 Logical representation of database
 Used for high level database design
 Has an associated diagrammatic representation, the ER diagram,
which can express the overall logical structure of a database graphically
 Creates a blueprint of database
 Main components in ER Model
 Attribute, Entity, Relationship

Database Management System 1.35

 ER Model
 Entity
 An object in real world
 Example: Student, course, faculty
 Attribute
 Characteristics of an entity
 Example: {roll no, age, address} can be attribute of Student
entity
 Relationship
 Connection or association between entities

Database Management System 1.36

 Entity Sets
 An entity is an object that exists and is distinguishable from other objects
 Example: specific person, company, event, plant
 An entity set is a set of entities of the same type that share the same
properties
 Example: set of all persons, companies, trees, holidays
 An entity is represented by a set of attributes; i.e., descriptive properties
possessed by all members of an entity set
 Example:
instructor = (ID, name, salary )
course= (course_id, title, credits)
 A subset of the attributes form a primary key of the entity set

Database Management System 1.37

 Entity Sets -- instructor and student

Database Management System 1.38

 Representing Entity sets in ER Diagram
 Rectangles represent entity sets
 Attributes listed inside entity rectangle
 Or eclipse represent attribute
 Underline indicates primary key attributes

 Alternate representation

ID name salary ID name tot_cred

instructor student

Database Management System 1.39

 Relationship Sets
 A relationship is an association among several entities
Example:
44553 (Peltier) advisor 22222 (Einstein)
student entity relationship set instructor entity
 A relationship set is a mathematical relation among n  2 entities, each
taken from entity sets
 Pictorially, we draw a line between related entities.

Database Management System 1.40

 Representing Relationship Sets via ER Diagrams

 Diamonds represent relationship sets.

Database Management System 1.41

 Relationship Sets (Cont.)
 An attribute can also be associated with a relationship set.
 For instance, the advisor relationship set between entity sets instructor
and student may have the attribute date which tracks when the
student started being associated with the advisor

76766 Crick 98988 Tanaka

45565 Katz 3 May 2008 12345 Shankar
10 June 2007
10101 Srinivasan 00128 Zhang
12 June 2006

98345 Kim 6 June 2009 76543 Brown

76543 Singh 30 June 2007
76653 Aoi
31 May 2007
22222 Einstein 23121 Chavez
4 May 2006

instructor 44553 Peltier

student

Database Management System 1.42

 Relationship Sets with Attributes

Database Management System 1.43

 Degree of a Relationship Set
 Binary relationship
 Involve two entity sets (or degree two)
 Most relationship sets in a database system are binary
 Relationships between more than two entity sets are rare. Most
relationships are binary
 Example: students work on research projects under the guidance of
an instructor.
 Relationship proj_guide is a ternary relationship between instructor,
student, and project

Database Management System 1.44

 Non-binary Relationship Sets
 Most relationship sets are binary
 There are occasions when it is more convenient to represent
relationships as non-binary
 E-R Diagram with a Ternary Relationship

Database Management System 1.45

 Attributes
 Attribute types:
 Simple and composite attributes
 Simple Attribute cannot be divided further
 Example: student age
 Composite attribute can be divide further
 Example: student name (first name, middle name, last
name), student address
 Single-valued and Multi-valued attributes
 Single-valued attribute has only one value
 Example: Student registration_number
 Multi-valued attribute has more than one vlaue
 Example: Student phone_numbers, address
 Complex attributes
 Composite + Multi-valued
 Example: Two address of a student
Database Management System 1.46
 Class Activity
 Can you tell few examples of single valued attributes?

Database Management System 1.47

 Class Activity
 Can you tell few examples of multi valued attributes?

Database Management System 1.48

 Attributes
 Attribute types
 Stored attributes
 Cannot be derived
 Example: date_of_birth
 Derived attributes
 Can be computed from other attributes
 Example: age given date_of_birth
 Key and non-key attributes
 Key is an unique attribute
 Example: registration number is a key attribute in student entity
 Domain – the set of permitted values for each attribute
 Representation of different types of attributes
 Derived: represented in dotted eclipse
 Multivalued: represented in double eclipse
 Key Attribute: underlined in eclipse
Database Management System 1.49
 Composite Attributes
 Composite attributes allow us to divided attributes into subparts (other
attributes).

composite name address

attributes

first_name middle_initial last_name street city state postal_code

component
attributes
street_number street_name apartment_number

Database Management System 1.50

 Mapping Cardinality Constraints
 Express the number of entities to which another entity can be associated
via a relationship set
 Most useful in describing binary relationship sets
 How two entities are associated with each other
 For a binary relationship set the mapping cardinality must be one of the
following types:
 One to one
 One to many
 Many to one
 Many to many

Database Management System 1.51

 Mapping Cardinalities

One to one One to many

Note: Some elements in A and B may not be mapped to any

elements in the other set

Database Management System 1.52

 Mapping Cardinalities

Many to one Many to many

Database Management System 1.53

 Representing Cardinality Constraints in ER Diagram

 We express cardinality constraints by drawing either a directed line

(), signifying “one”, or an undirected line (—), signifying “many”,
between the relationship set and the entity set.
 One-to-one relationship between an instructor and a student :
 A student is associated with at most one instructor via the relationship
advisor
 Similarly, an instructor is associated with at most one student with the
same relationship

 Example: HOD manages Department

Database Management System 1.54

 One-to-One Relationship
 Can you draw an ER diagram for HOD Manage Department?

Database Management System 1.55

 One-to-Many Relationship
 One-to-many relationship between an instructor and a student
 A student is associated with at most one instructor via advisor
 An instructor is associated with several (including 0) students via
advisor

Database Management System 1.56

 One-to-Many Relationship
 Can you draw an ER diagram for Customer Give Order?

Database Management System 1.57

 Many-to-One Relationships
 In a many-to-one relationship between an instructor and a student,
 A student is associated with several (including 0) instructors via
advisor
 An instructor is associated with at most one student via advisor,

Database Management System 1.58

 Many-to-Many Relationship
 An instructor is associated with several students via advisor
 A student is associated with several instructors via advisor

Database Management System 1.59

 Total and Partial Participation
 Total participation (indicated by double line): every entity in the entity
set participates in at least one relationship in the relationship set

 Participation of student in advisor relation is total

 Every student must have an associated instructor
 Partial participation: Some entities may not participate in any
relationship in the relationship set
 Example: participation of instructor in advisor is partial

Database Management System 1.60

 Total and Partial Participation

Database Management System 1.61

 Weak Entity Sets and Self Referential Relationship

 Weak entity set

 Entity set with no key
 Attributes of weak entity set may not be able to differentiate the
records
 Weak entity set is allowed in design of ER diagram
 RDBMS does not allow weak entity set
 Combine relationship with entity

Database Management System 1.62

 ER Diagram Minimization
 ER Diagram Minimization
 Convert ER Diagram into minimal such that minimum number of
RDBMS tables would be formed
 To reduce the number of overhead and complexity
 One to one minimization
 One to many minimization
 Many to one minimization
 Many to many minimization

Database Management System 1.63

 ER Diagram Minimization
One to one minimization
Since
Eid Ename Did Dname

Emp Manages Dept

1 1

Did Dname
Eid Ename
D1 CS
E1 A
D2 IT
E2 A
D3 ME
E3 B
D4 EE

What will be attributes in relationship table, Manages?

What will be Primary Key (PK) in relationship table, Manages?

Database Management System 1.64

 ER Diagram Minimization
One to one minimization
Since
Eid Ename Did Dname

Emp Manages Dept

1 1

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E2 D2 2012
D3 ME
E3 B E3 D3 2016
D4 EE

 Can you tell if Manages Table is correct?

Database Management System 1.65

 ER Diagram Minimization
One to one minimization
Since
Eid Ename Did Dname
What will be
attributes?
Emp Manages Dept
1 1 What will
be Primary
Key (PK)?
Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E2 D2 2012
D3 ME
E3 B E3 D3 2016
D4 EE

Can we merge?
What will be PK?

Database Management System 1.66

 ER Diagram Minimization
One to one minimization
Since
Eid Ename Did Dname
What will be
attributes?
Emp Manages Dept
1 1 What will
be Primary
Key (PK)?
Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E2 D2 2012
D3 ME
E3 B E3 D3 2016
D4 EE
Can we
merge? Eid Ename Did Dname Eid Since
What will Can we
be PK? E1 A D1 CS E1 2009 merge?
E2 A D2 IT E2 2012 What
will be
E3 B D3 ME E3 2016 PK?

Database Management System

D4 EE
1.67
NULL NULL
 ER Diagram Minimization
One to many minimization
Since
Eid Ename Did Dname

Emp Manages Dept

1 N

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2002
D2 IT
E2 A E1 D2 2003
D3 ME
E3 B E2 D3 2004
D4 EE

What will be Primary Key in Relationship Table, Manages (PK)?

Database Management System 1.68

 ER Diagram Minimization
One to many minimization
Since
Eid Ename Did Dname

Emp Manages Dept

1 N

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E1 D2 2012
D3 ME
E3 B E2 D3 2016
D4 EE

What will be Primary Key in Relationship Table, Manages (PK)?

How I will remember? Easy way?

Database Management System 1.69

 ER Diagram Minimization
One to many minimization
Since
Eid Ename Did Dname

Emp Manages Dept What will

1 N be Primary
Key (PK)?

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E1 D2 2012
D3 ME
E3 B E2 D3 2016
D4 EE
Can we
merge?

Database Management System 1.70

 ER Diagram Minimization
One to many minimization
Since
Eid Ename Did Dname

Emp Manages Dept What will

1 N be Primary
Key (PK)?

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E1 D2 2012
D3 ME
E3 B E2 D3 2016
D4 EE
Can we
merge? Did Dname Eid Since
Eid Ename
E1 A D1 CS E1 2009 Can we
D2 IT E1 2012 merge?
E2 A
E3 B D3 ME E2 2016

Database Management System

D4 EE
1.71
NULL NULL
 ER Diagram Minimization
Many to Many minimization
Since
Eid Ename Did Dname
What will be
attributes?
Emp Manages Dept
M N What will
be Primary
Key (PK)?
Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E1 D2 2012
D3 ME
E3 B E3 D2 2016
D4 EE
Can we
merge?
What will
be PK? Can we
merge?
What will
be PK?

Database Management System 1.72

 ER Diagram Minimization
One to one minimization with total participation
Since
Eid Ename Did Dname

Emp Manages Dept What will

1 1 be Primary
Key (PK)?

Did Dname
Eid Ename Eid Did Since
D1 CS
E1 A E1 D1 2009
D2 IT
E2 A E2 D2 2012
D3 ME
E3 B E3 D3 2016
D4 EE
Can we
merge? Did Dname Eid Since
Eid Ename Can we
E1 A D1 CS E1 2009 merge?
E2 A D2 IT E2 2012
+
E3 B D3 ME E3 2016

Database Management System

D4 EE
1.73
NULL NULL
 References
 Silberschatz, Abraham, Henry F. Korth, and Shashank
Sudarshan. Database system concepts. Vol. 6. New York: McGraw-
Hill, 1997.
 Ramez Elmasri, Shamkant B. Navathe. Fundamentals of Database
Systems. Edition 6. Pearson, 2010.

Database Management System 1.74