Introduction of ER Model

ER Model is used to model the logical view of the system from data perspective which consists of these
components:

Entity, Entity Type, Entity Set –

An Entity may be an object with a physical existence – a particular person, car, house, or employee – or it may be an
object with a conceptual existence – a company, a job, or a university course.

An Entity is an object of Entity Type and set of all entities is called as entity set. e.g.; E1 is an entity having Entity
Type Student and set of all students is called Entity Set. In ER diagram, Entity type is represented as:

Attribute(s):
Attributes are the properties which define the entity type. For example, Roll_No, Name, DOB, Age, Address,
Mobile_No are the attributes which defines entity type Student. In ER diagram, attribute is represented by an oval.

1. Key Attribute –
The attribute which uniquely identifies each entity in the entity set is called key attribute.For example,
Roll_No will be unique for each student. In ER diagram, key attribute is represented by an oval with underlying

lines.
1. Composite Attribute –
An attribute composed of many other attribute is called as composite attribute. For example, Address
attribute of student Entity type consists of Street, City, State, and Country. In ER diagram, composite attribute
is represented by an oval comprising of ovals.

2. Multivalued Attribute –
An attribute consisting more than one value for a given entity. For example, Phone_No (can be more than one
for a given student). In ER diagram, multivalued attribute is represented by double oval.
3. Derived Attribute –
An attribute which can be derived from other attributes of the entity type is known as derived attribute. e.g.;
Age (can be derived from DOB). In ER diagram, derived attribute is represented by dashed oval.

The complete entity type Student with its attributes can be represented as:

Relationship Type and Relationship Set:

A relationship type represents the association between entity types. For example,‘Enrolled in’ is a relationship type
that exists between entity type Student and Course. In ER diagram, relationship type is represented by a diamond
and connecting the entities with lines.

A set of relationships of same type is known as relationship set. The following relationship set depicts S1 is enrolled
in C2, S2 is enrolled in C1 and S3 is enrolled in C3.
Degree of a relationship set:
The number of different entity sets participating in a relationship set is called as degree of a relationship set.
1. Unary Relationship –
When there is only ONE entity set participating in a relation, the relationship is called as unary relationship.
For example, one person is married to only one person.

2. Binary Relationship –
When there are TWO entities set participating in a relation, the relationship is called as binary
relationship.For example, Student is enrolled in Course.

3. n-ary Relationship –
When there are n entities set participating in a relation, the relationship is called as n-ary relationship.
Cardinality:
The number of times an entity of an entity set participates in a relationship set is known as cardinality.
Cardinality can be of different types:
1. One to one – When each entity in each entity set can take part only once in the relationship, the cardinality is
one to one. Let us assume that a male can marry to one female and a female can marry to one male. So the
relationship will be one to one.

Using Sets, it can be represented as:

2. Many to one – When entities in one entity set can take part only once in the relationship set and entities in
other entity set can take part more than once in the relationship set, cardinality is many to one. Let us
assume that a student can take only one course but one course can be taken by many students. So the cardinality
will be n to 1. It means that for one course there can be n students but for one student, there will be only one
course.

Using
Sets, it can be represented as:

In this case, each student is taking only 1 course but 1 course has been taken by many students.
3. Many to many – When entities in all entity sets can take part more than once in the relationship cardinality
is many to many. Let us assume that a student can take more than one course and one course can be taken by
many students. So the relationship will be many to many.

Using sets, it can be represented as:

1. In this example, student S1 is enrolled in C1 and C3 and Course C3 is enrolled by S1, S3 and S4. So it is many
to many relationships.
Participation Constraint:
Participation Constraint is applied on the entity participating in the relationship set.
1. Total Participation – Each entity in the entity set must participate in the relationship. If each student must
enroll in a course, the participation of student will be total. Total participation is shown by double line in ER
diagram.
2. Partial Participation – The entity in the entity set may or may NOT participate in the relationship. If some
courses are not enrolled by any of the student, the participation of course will be partial.
The diagram depicts the ‘Enrolled in’ relationship set with Student Entity set having total participation and
Course Entity set having partial participation.

Using set, it can be represented as,

Every student in Student Entity set is participating in relationship but there exists a course C4 which is not
taking part in the relationship.
Weak Entity Type and Identifying Relationship:
As discussed before, an entity type has a key attribute which uniquely identifies each entity in the entity set. But
there exists some entity type for which key attribute can’t be defined. These are called Weak Entity type.
For example, A company may store the information of dependants (Parents, Children, Spouse) of an Employee. But
the dependents don’t have existence without the employee. So Dependent will be weak entity type and Employee
will be Identifying Entity type for Dependant.
A weak entity type is represented by a double rectangle. The participation of weak entity type is always total. The
relationship between weak entity type and its identifying strong entity type is called identifying relationship and it is
represented by double diamond.

Enhanced ER Model
Prerequisite – Introduction of ER Model
Todays time the complexity of the data is increasing so it becomes more and more difficult to use the traditional ER
model for database modeling. To reduce this complexity of modeling we have to make improvements or
enhancements were made to the existing ER model to make it able to handle the complex application in a better
way.
Enhanced entity-relationship diagrams are advanced database diagrams very similar to regular ER diagrams which
represents requirements and complexities of complex databases.
It is a diagrammatic technique for displaying the Sub Class and Super Class; Specialization and Generalization;
Union or Category; Aggregation etc.
Generalization and Specialization –
These are very common relationship found in real entities. However this kind of relationships was added later as
enhanced extension to classical ER model. Specialized class are often called as subclass while generalized
class are called superclass, probably inspired by object oriented programming. A sub-class is best understood
by “IS-A analysis”. Following statements hopefully makes some sense to your mind “Technician IS-A Employee”,
“Laptop IS-A Computer”.
An entity is specialized type/class of other entity. For example, Technician is special Employee in a university
system Faculty is special class of Employee. We call this phenomenon as generalization/specialization. In the
example here Employee is generalized entity class while Technician and Faculty are specialized class of Employee.
Example – This example instance of “sub-class” relationships. Here we have four sets employee: Secretary,
Technician, and Engineer. Employee is super-class of rest three set of individual sub-class is subset of Employee set.
 An entity belonging to a sub-class is related with some super-class entity. For instance emp no 1001 is a
secretary, and his typing speed is 68. Emp no 1009 is engineer (sub-class) and her trade is “Electrical”, so forth.
 Sub-class entity “inherits” all attributes of super-class; for example employee 1001 will have attributes eno,
name, salary, and typing speed.
Enhanced ER model of above example –

Constraints – There are two types of constraints on “Sub-class” relationship.

1. Total or Partial – A sub-classing relationship is total if every super-class entity is to be associated with some
sub-class entity, otherwise partial. Sub-class “job type based employee category” is partial sub-classing – not
necessary every employee is one of (secretary, engineer, and technician), i.e. union of these three types is
proper subset of all employees. Whereas other sub-classing “Salaried Employee AND Hourly Employee” is
total; union of entities from sub-classes is equal to total employee set, i.e. every employee necessarily has to be
one of them.
2. Overlapped or Disjoint – If an entity from super-set can be related (can occur) in multiple sub-class sets, then
it is overlapped sub-classing, otherwise disjoint. Both the examples: job-type based and salaries/hourly
employee sub-classing are disjoint.
Note – These constraints are independent of each other: can be “overlapped and total or partial” or “disjoint and
total or partial”. Also sub-classing has transitive property.
Multiple Inheritance (sub-class of multiple super classes) –
An entity can be sub-class of multiple entity types; such entities are sub-class of multiple entities and have multiple
super-classes; Teaching Assistant can subclass of Employee and Student both. A faculty in a university system can
be sub-class of Employee and Alumnus both. In multiple inheritance, attributes of sub-class is union of attributes of
all super-classes.
Union –
 Set of Libray Members is UNION of Faculty, Student, and Staff. A union relationship indicates either of type;
for example: a library member is either Faculty or Staff or Student.
 Below are two examples shows how UNION can be depicted in ERD – Vehicle Owner is UNION of PERSON
and Company, and RTO Registered Vehicle is UNION of Car and Truck.
You might see some confusion in Sub-class and UNION; consider example in above figure Vehicle is super-class of
CAR and Truck; this is very much the correct example of subclass as well but here use it different we are saying
RTO Registered vehicle is UNION of Car and Vehicle, they do not inherit any attribute of Vehicle, attributes of car
and truck are altogether independent set, where is in sub-classing situation car and truck would be inheriting the
attribute of vehicle class. Below is Vehicle as modeled as class of Car and Truck.
Minimization of ER Diagrams
Entity Relationship (ER) Diagram is diagrammatic representation of data in databases, it shows how data is related.
Note: This article for those who already know what is ER diagram and how to draw ER diagram.
1) When there is One to Many cardinality in ER diagram.
For example, a student can be enrolled only in one course, but a course can be enrolled by many students

For Student(SID, Name), SID is the primary key. For Course ( CID, C_name ), CID is the primary key
Student Course
(SID Name) ( CID C_name )
-------------- -----------------
1 A c1 Z
2 B c2 Y
3 C c3 X
4 D
 Enroll
(SID CID)
----------
1 C1
2 C1
3 c3
4 C2
Now the question is, what should be the primary key for Enroll SID or CID or combined. We can’t have CID as
primary key as you can see in enroll for the same CID we have multiples SID. (SID , CID) can distinguish table
uniquely, but it is not minimum. So SID is the primary key for the relation enroll.
For above ER diagram, we considered three tables in database
Student
Enroll
Course
But we can combine Student and Enroll table renamed as Student_enroll.
Student_Enroll
( SID Name CID )
---------------------
1 A c1
2 B c1
3 C c3
4 D c2
Student and enroll tables are merged now .
So require minimum two DBMS tables for Student_enroll and Course.
Note: In One to Many relationship we can have minimum two tables.
2. When there is Many to Many cardinality in ER Diagram.
Let us consider above example with the change that now student can also enroll more than 1 course.

Student Course
( SID Name) ( CID C_name )
-------------- -----------------
1 A c1 Z
2 B c2 Y
3 C c3 X
4 D

Enroll
( SID CID )
----------
1 C1
1 C2
2 C1
2 C2
3 c3
4 C2
Now, same question what is the primary key of Enroll relation, if we carefully analyse the Enroll primary key for
Enroll
table is ( SID , CID ).
But in this case we can’t merge Enroll table with any one of Student and Course. If we try to merge Enroll with any
one of the Student and Course it will create redundant data.
Note: Minimum three tables are required in Many to Many relationship.

3. One to One Relationship

There are two possibilities
A) If we have One to One relationship and we have total participation at at-least one end.
For example, consider the below ER diagram.

A1 and B1 are primary keys of E1 and E2 respectively.

In the above Diagram we have total participation at E1 end.

 Only a single table is required in this case having primary key of E2 as its primary key.

The primary key of E1, which is in total participation should not be allowed as the primary key of the reduced
table, since if the primary key of E1 is used, it might have null values for many of its entries in the reduced
table for some E2 entities.

B) One to One relationship with no total participation.

A1 and B1 are primary keys of E1 and E2 respectively.

Primary key of R can be A1 or B1, but we can’t still combine all the three table into one. if we do, so some entries in
combined table may have NULL entries. So idea of merging all three table into one is not good.
But we can merge R into E1 or E2. So minimum 2 tables are required.

Generalization, Specialization and Aggregation in ER Model

Prerequisite – Introduction of ER Model
Generalization, Specialization and Aggregation in ER model are used for data abstraction in which abstraction mechanism is
used to hide details of a set of objects.
Generalization –
Generalization is the process of extracting common properties from a set of entities and create a generalized entity from it. It
is a bottom-up approach in which two or more entities can be generalized to a higher level entity if they have some attributes
in common. For Example, STUDENT and FACULTY can be generalized to a higher level entity called PERSON as shown in
Figure 1. In this case, common attributes like P_NAME, P_ADD become part of higher entity (PERSON) and specialized
attributes like S_FEE become part of specialized entity (STUDENT).

Specialization –
In specialization, an entity is divided into sub-entities based on their characteristics. It is a top-down approach where higher
level entity is specialized into two or more lower level entities. For Example, EMPLOYEE entity in an Employee
management system can be specialized into DEVELOPER, TESTER etc. as shown in Figure 2. In this case, common
attributes like E_NAME, E_SAL etc. become part of higher entity (EMPLOYEE) and specialized attributes like TES_TYPE
become part of specialized entity (TESTER).

Aggregation –
An ER diagram is not capable of representing relationship between an entity and a relationship which may be required in
some scenarios. In those cases, a relationship with its corresponding entities is aggregated into a higher level entity. For
Example, Employee working for a project may require some machinery. So, REQUIRE relationship is needed between
relationship WORKS_FOR and entity MACHINERY. Using aggregation, WORKS_FOR relationship with its entities
EMPLOYEE and PROJECT is aggregated into single entity and relationship REQUIRE is created between aggregated entity
and MACHINERY.
Recursive Relationships in ER diagrams
Prerequisite – ER Model

A relationship between two entities of similar entity type is called a recursive relationship. Here the same entity
type participates more than once in a relationship type with a different role for each instance. In other words, a
relationship has always been between occurrences in two different entities. However, it is possible for the same
entity to participate in the relationship. This is termed a recursive relationship.

Example –
Let us suppose that we have an employee table. A manager supervises a subordinate. Every employee can have
a supervisor except the CEO and there can be at most one boss for each employee. One employee may be the
boss of more than one employee. Let’s suppose that REPORTS_TO is a recursive relationship on the Employee
entity type where each Employee plays two roles

Supervisor
Subordinate

Supervisor and Subordinate are called “Role Names”. Here the degree of the REPORTS_TO relationship is 1
i.e. a unary relationship.
The minimum cardinality of Supervisor entity is ZERO since the lowest level employee may not be a manager
for anyone.
The maximum cardinality of Supervisor entity is N since an employee can manage many employees.
Similarly the Subordinate entity has a minimum cardinality of ZERO to account for the case where CEO can
never be a subordinate.
It maximum cardinality is ONE since a subordinate employee can have at most one supervisor.

Note – Here none of the participants have a total participation since both minimum cardinalities are Zero.
Hence, the relationships are connected by a single line instead of a double line in the ER diagram.

To implement a recursive relationship, a foreign key of the employee’s manager number would be held in each
employee record. A Sample table would look something like this:-

Emp_entity( Emp_no,Emp_Fname, Emp_Lname, Emp_DOB, Emp_NI_Number, Manager_no);

Manager no - (this is the employee no of the employee's manager).

Impedance Mismatch in DBMS

Impedance mismatch is the term used to refer to the problems that occurs due to differences between the
database model and the programming language model. The practical relational model has 3 components these
are:

Attributes and their data types

Tuples
Tables
Problems:
Following problems may occur due to the impedance mismatch:

The first problem that may occur is that is data type mismatch means the programming language attribute data
type may differ from the attribute data type in the data model.

Hence it is quite necessary to have a binding for each host programming language that specifies for each
attribute type the compatible programming language types. It is necessary to have different data types, for
example, we have different data types available in different programming languages such as data types in C are
different from Java and both differ from SQL data types.

The second problem that may occur is because the results of most queries are sets or multisets of tuples and
each tuple is formed of a sequence of attribute values. In the program, it is necessary to access the individual
data values within individual tuples for printing or processing.

Hence there is a need for binding to map the query result data structure which is a table to an appropriate data
structure in the programming language. A mechanism is needed to loop over the tuples in a query result in
order to access a single tuple at a time and to extract individual values from the tuple.
The extracted values are typically copied to appropriate program variables for further processing by the
program.
A cursor or iterator is a variable which is used for looping over the tuples in a query result. Individual values
within each tuple are extracted into different or unique program variables of the appropriate datatype.

Impedance mismatch is less of a problem when a special database programming language is designed that uses
the same data model and data type as a database model for example Oracles’sPL/SQL.
Introduction of Relational Model and Codd Rules in DBMS
Terminology

Relational Model: Relational model represents data in the form of relations or tables.

Relational Schema: Schema represents structure of a relation. e.g.; Relational Schema of STUDENT relation
can be represented as:
STUDENT (STUD_NO, STUD_NAME, STUD_PHONE, STUD_STATE, STUD_COUNTRY, STUD_AGE)

Relational Instance: The set of values present in a relation at a particular instance of time is known as relational
instance as shown in Table 1 and Table 2.

Attribute: Each relation is defined in terms of some properties, each of which is known as attribute. For
Example, STUD_NO, STUD_NAME etc. are attributes of relation STUDENT.

Domain of an attribute: The possible values an attribute can take in a relation is called its domain. For Example,
domain of STUD_AGE can be from 18 to 40.
Tuple: Each row of a relation is known as tuple. e.g.; STUDENT relation given below has 4 tuples.

NULL values: Values of some attribute for some tuples may be unknown, missing or undefined which are
represented by NULL. Two NULL values in a relation are considered different from each other.
Table 1 and Table 2 represent relational model having two relations STUDENT and STUDENT_COURSE.

Codd rules were proposed by E.F. Codd which should be satisfied by relational model.

Foundation Rule: For any system that is advertised as, or claimed to be, a relational data base management
system, that system must be able to manage data bases entirely through its relational capabilities.
Information Rule: Data stored in Relational model must be a value of some cell of a table.
Guaranteed Access Rule: Every data element must be accessible by table name, its primary key and name of
attribute whose value is to be determined.
Systematic Treatment of NULL values: NULL value in database must only correspond to missing, unknown or
not applicable values.
Active Online Catalog: Structure of database must be stored in an online catalog which can be queried by
authorized users.
Comprehensive Data Sub-language Rule: A database should be accessible by a language supported for
definition, manipulation and transaction management operation.
View Updating Rule: Different views created for various purposes should be automatically updatable by the
system.
High level insert, update and delete rule: Relational Model should support insert, delete, update etc. operations
at each level of relations. Also, set operations like Union, Intersection and minus should be supported.
Physical data independence: Any modification in the physical location of a table should not enforce
modification at application level.
Logical data independence: Any modification in logical or conceptual schema of a table should not enforce
modification at application level. For example, merging of two tables into one should not affect application
accessing it which is difficult to achieve.
Integrity Independence: Integrity constraints modified at database level should not enforce modification at
application level.
Distribution Independence: Distribution of data over various locations should not be visible to end-users.
Non-Subversion Rule: Low level access to data should not be able to bypass integrity rule to change data.

Relational Model in DBMS

Relational Model was proposed by E.F. Codd to model data in the form of relations or tables. After designing
the conceptual model of Database using ER diagram, we need to convert the conceptual model in the relational
model which can be implemented using any RDMBS languages like Oracle SQL, MySQL etc. So we will see
what Relational Model is.

What is Relational Model?

Relational Model represents how data is stored in Relational Databases. A relational database stores data in the
form of relations (tables). Consider a relation STUDENT with attributes ROLL_NO, NAME, ADDRESS,
PHONE and AGE shown in Table 1.

STUDENT

ROLL_NO NAME ADDRESS PHONE AGE

1 RAM DELHI 9455123451 18
2 RAMESH GURGAON 9652431543 18
3 SUJIT ROHTAK 9156253131 20
4 SURESH DELHI 18

IMPORTANT TERMINOLOGIES

Attribute: Attributes are the properties that define a relation. e.g.; ROLL_NO, NAME
Relation Schema: A relation schema represents name of the relation with its attributes. e.g.; STUDENT
(ROLL_NO, NAME, ADDRESS, PHONE and AGE) is relation schema for STUDENT. If a schema has more
than 1 relation, it is called Relational Schema.
Tuple: Each row in the relation is known as tuple. The above relation contains 4 tuples, one of which is shown
as:
1 RAM DELHI 9455123451 18
Relation Instance: The set of tuples of a relation at a particular instance of time is called as relation instance.
Table 1 shows the relation instance of STUDENT at a particular time. It can change whenever there is
insertion, deletion or updation in the database.
Degree: The number of attributes in the relation is known as degree of the relation. The STUDENT relation
defined above has degree 5.
Cardinality: The number of tuples in a relation is known as cardinality. The STUDENT relation defined above
has cardinality 4.
Column: Column represents the set of values for a particular attribute. The column ROLL_NO is extracted
from relation STUDENT.
 ROLL_NO
1
2
3
4
NULL Values: The value which is not known or unavailable is called NULL value. It is represented by blank
space. e.g.; PHONE of STUDENT having ROLL_NO 4 is NULL.
Constraints in Relational Model

While designing Relational Model, we define some conditions which must hold for data present in database are
called Constraints. These constraints are checked before performing any operation (insertion, deletion and
updation) in database. If there is a violation in any of constrains, operation will fail.

Domain Constraints: These are attribute level constraints. An attribute can only take values which lie inside the
domain range. e.g,; If a constrains AGE>0 is applied on STUDENT relation, inserting negative value of AGE
will result in failure.

Key Integrity: Every relation in the database should have atleast one set of attributes which defines a tuple
uniquely. Those set of attributes is called key. e.g.; ROLL_NO in STUDENT is a key. No two students can
have same roll number. So a key has two properties:

It should be unique for all tuples.

It can’t have NULL values.
Referential Integrity: When one attribute of a relation can only take values from other attribute of same relation
or any other relation, it is called referential integrity. Let us suppose we have 2 relations

STUDENT

ROLL_NO NAME ADDRESS PHONE AGE BRANCH_CODE

1 RAM DELHI 9455123451 18 CS
2 RAMESH GURGAON 9652431543 18 CS
3 SUJIT ROHTAK 9156253131 20 ECE
4 SURESH DELHI 18 IT
BRANCH

BRANCH_CODE BRANCH_NAME
CS COMPUTER SCIENCE
IT INFORMATION TECHNOLOGY
ECE ELECTRONICS AND COMMUNICATION ENGINEERING
CV CIVIL ENGINEERING

BRANCH_CODE of STUDENT can only take the values which are present in BRANCH_CODE of BRANCH
which is called referential integrity constraint. The relation which is referencing to other relation is called
REFERENCING RELATION (STUDENT in this case) and the relation to which other relations refer is called
REFERENCED RELATION (BRANCH in this case).

Types of Keys in Relational Model (Candidate, Super, Primary, Alternate and

Foreign)
Candidate Key: The minimal set of attribute which can uniquely identify a tuple is known as candidate key. For
Example, STUD_NO in STUDENT relation.

The value of Candidate Key is unique and non-null for every tuple.
There can be more than one candidate key in a relation. For Example, STUD_NO as well as STUD_PHONE
both are candidate keys for relation STUDENT.
The candidate key can be simple (having only one attribute) or composite as well. For Example, {STUD_NO,
COURSE_NO} is a composite candidate key for relation STUDENT_COURSE.
Note – In Sql Server a unique constraint that has a nullable column, allows the value ‘null‘ in that column only
once. That’s why STUD_PHONE attribute as candidate here, but can not be ‘null’ values in primary key
attribute.

Super Key: The set of attributes which can uniquely identify a tuple is known as Super Key. For Example,
STUD_NO, (STUD_NO, STUD_NAME) etc.

Adding zero or more attributes to candidate key generates super key.

A candidate key is a super key but vice versa is not true.
Primary Key: There can be more than one candidate key in a relation out of which one can be chosen as
primary key. For Example, STUD_NO as well as STUD_PHONE both are candidate keys for relation
STUDENT but STUD_NO can be chosen as primary key (only one out of many candidate keys).

Alternate Key: The candidate key other than primary key is called as alternate key. For Example, STUD_NO as
well as STUD_PHONE both are candidate keys for relation STUDENT but STUD_PHONE will be alternate
key (only one out of many candidate keys).

Foreign Key: If an attribute can only take the values which are present as values of some other attribute, it will
be foreign key to the attribute to which it refers. The relation which is being referenced is called referenced
relation and corresponding attribute is called referenced attribute and the relation which refers to referenced
relation is called referencing relation and corresponding attribute is called referencing attribute. Referenced
attribute of referenced relation should be primary key for it. For Example, STUD_NO in STUDENT_COURSE
is a foreign key to STUD_NO in STUDENT relation.

It may be worth noting that unlike, Primary Key of any given relation, Foreign Key can be NULL as well as
may contain duplicate tuples i.e. it need not follow uniqueness constraint.
 For Example, STUD_NO in STUDENT_COURSE relation is not unique. It has been repeated for the first and
third tuple. However, the STUD_NO in STUDENT relation is a primary key and it needs to be always unique
and it cannot be null.

Please write comments if you find anything incorrect, or you want to share more information about the topic
discussed above

Number of possible Superkeys in DBMS

Any subset of attributes of a table that can uniquely identify all the tuples of that table is known as a Super key.
Its different from the primary and candidate keys in the sense that only the minimal superkeys are the
candidate/primary keys.

This means that from a super key when we remove all the attributes that are unnecessary for its uniqueness,
only then it becomes a primary/candidate key. So, in essence, all primary/candidate keys are super keys but not
all superkeys are primary/candidate keys. By the formal definition of a Relation(Table), we know that the
tuples of a relation are all unique. So the set of all attributes itself is a super key.

Counting the possible number of superkeys for a table is a common question for GATE. The examples below will
demonstrate all possible types of questions on this topic.
 Example-1 : Let a Relation R have attributes {a1,a2,a3} & a1 is the candidate key. Then how many super keys are
possible?
Here, any superset of a1 is the super key.
Super keys are = {a1, a1 a2, a1 a3, a1 a2 a3}
Thus we see that 4 Super keys are possible in this case.
In general, if we have ‘N’ attributes with one candidate key then the number of possible superkeys are 2 (N – 1).
 Example-2 : Let a Relation R have attributes {a1, a2, a3,…,an}. Find Super key of R.
Maximum Super keys = 2n – 1.
If each attribute of relation is candidate key.
 Example-3 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate key is “a1 a2 a3” then the possible
number of super keys?
Following the previous formula, we have 3 attributes instead of one. So, here the number of possible superkeys are 2 (N-
3)
.
 Example-4 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate keys are “a1”, “a2” then the possible
number of super keys?
This problem now is slightly different since we now have two different candidate keys instead of only one. Tackling
problems like these is shown in the diagram below:

|A1 ∪ A2| = |A1| + |A2| – |A ∩ A2|

= (superkeys possible with candidate key A1) + (superkeys possible with candidate key A2)
– (common superkeys from both A1 and A2)

= 2(n-1) + 2(n-1) – 2(n-2)

Example-5 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate keys are “a1”, “a2 a3” then
the possible number of super keys?
Super keys of(a1) + Super keys of(a2 a3) – Super keys of(a1 a2 a3)
⇒ 2(n – 1) + 2(n – 2) – 2(n – 3)

Example-6 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate keys are “a1 a2”, “a3 a4”
then the possible number of super keys?
Super keys of(a1 a2) + Super keys of(a3 a4) – Super keys of(a1 a2 a3 a4)
⇒ 2(n – 2) + 2(n – 2) – 2(n – 4)
Example-7 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate keys are “a1 a2”, “a1 a3”
then the possible number of super keys?
Super keys of(a1 a2) + Super keys of(a1 a3) – Super keys of(a1 a2 a3)
⇒ 2(n – 2) + 2(n – 2) – 2(n – 3)

Example-8 : Let a Relation R have attributes {a1, a2, a3,…,an} and the candidate keys are “a1”, “a2”, “a3” then
the possible number of super keys?
In this question, we have 3 different candidate keys. Tackling problems like these are shown in the diagram
below.

→ |A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| – |A1 ∩ A2| – |A1 ∩ A3| – |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|

= (superkeys possible with candidate key A1) + (superkeys possible with candidate key A2) + (superkeys
possible with candidate key A3) – (common superkeys from both A1 and A2) – (common superkeys from both
A1 and A3) – (common superkeys from both A2 and A3) + (common superkeys from both A1, A2 and A3)

= 2(n-1) + 2(n-1) + 2(n-1) – 2(n-2) – 2(n-2) – 2(n-2) + 2(n-3)

Example-9 : A relation R(A, B, C, D, E, F, G, H)and set of functional dependencies are

CH → G,
A → BC,
B → CFH,
E → A,
F → EG
Then how many possible super keys are present ?

Step 1:- First of all, we have to find what the candidate keys are:-
as we can see in given functional dependency D is missing but in relation, D is given so D must be a prime
attribute of the Candidate key.

A+ = E+ = B+ = F+ = all attributes of a relation except D

So, Ck’s are = AD, BD, ED, FD
 Step 2:-Find superkeys due to single candidate key
there is a two possibility of attribute either we select or not hence there will be 2 chances so,
A_ _D_ _ _ _ = _ B_ D_ _ _ _ = _ _ _ DE _ _ _ = _ _ _ D_F_ _ = 26

Step 3:-Find superkeys due to combination of two CK’s

so,
n(AD ∩ BD) = n(AD ∩ ED) = n(AD ∩ FD) = n(BD ∩ ED) = n(BD ∩ FD) = n(ED ∩ FD) = 25

Step 4:-Find supekeys due to combination of three CK’s

so,
n(AD ∩ BD ∩ ED) = n(AD ∩ ED ∩ FD) = n(ED ∩ BD ∩ FD) = n(BD ∩ FD ∩ AD) = 24

Step 5:-Find superkeys due to all so,

n(AD ∩ BD ∩ ED ∩ FD) = AB_DEF_ _ = 23

so according to inclusion- exclusion principle :-

|W ∪ X ∪ Y ∪ Z| = |W| + |X| + |Y| + |Z| – |W ∩ X| – |W ∩ Y| – |W ∩ Z| – |X ∩Y| – |X ∩ Z| – |Y ∩ Z| + |W ∩ X
∩ Y| + |W ∩ X ∩ Z| + |W ∩ Y ? Z| + |X ∩ Y ∩ Z| – |W ∩ X ∩ Y ∩ Z|

#Supekeys = 4 * 26 – 6 * 25 + 4 * 24 – 23 = 120

So the number of superkeys are 120.

Anomalies in Relational Model