CS3402 Database Systems:
ER , Relational Data Model
CS3402
ER Model Concepts Revisited
Entity: an object represented in the database For example, an employee ‘John Smith’
Attribute: properties used to describe an entity/relationship
For example, an EMPLOYEE entity may have Name, ID, Address,
EMPLOYEE
Sex, BirthDate
ID Sex Name
BirthDate
Relationship: an association among several entities
For example, EMPLOYEE John Smith works on the PROJECT ‘X’
EMPLOYEE
EMPLOYEE
WORK S_ON
PROJECT
CS3402
ER Model Concepts Revisited -Constraints of Relationship
Cardinality ratio (of a binary relationship): 1:1, 1:N, N:1, or M:N
Specify the maximum no. of relationship instances that each entity can participate in
A
B
AB AB
1:1
1:N M:N
CS3402
ER Model Concepts Revisited -Constraints of Relationship
Two ways to indicate Cardinality ratio in ER Diagram 1 Place appropriate number on the link.
11m
1n 2 Place arrow on the 1 side
n
CS3402
ER Model Concepts Revisited -Constraits of Relationship
Participation constraint (on each participating entity type):
Specify the minimum no. of relationship instances that each entity can participate in
Total (existence dependency) or partial
Total shown by double line, partial by single line
E.g., double line: Department to Employee; single line: Employee to Department (not all employees manage department)
MANAGE
EMPLOYEE
DEPARTMENT
CS3402
(Alternative (min, max) notation for relationship structural constraints:
Specified on each participation of an entity type E in a relationship type R
Specifies that each entity e in E participates in at least min and at most max relationship instances in R
Default (no constraint): min=0, max=n
Must have minmax, min0, max 1
CS3402
Alternative (min, max) notation for
relationship structural constraints:
Examples:
A department has exactly one manager and an employee can
manage at most one department
Specify (0,1) for participation of EMPLOYEE in MANAGES
Specify (1,1) for participation of DEPARTMENT in MANAGES
An employee can work for exactly one department but a department can have any number (>1) of employees
Specify (1,1) for participation of EMPLOYEE in WORKS_FOR
Specify (1,n) for participation of DEPARTMENT in WORKS_FOR
CS3402
The (min,max) notation for relationship constraints
One Employee may manage one Dept at most, zero Dept at least
One Dept is managed by exactly one Employee
CS3402
The (min,max) notation for relationship constraints
One Employee works for just one Dept
One Dept is worked by many employees, no Dept without Employee
CS3402
COMPANY ER Schema Diagram using Cardinality ratio notation
CS3402
COMPANY ER Schema Diagram using (min, max) notation
CS3402
ER Model Concepts Revisited -Constraints of Relationship
The degree of a relationship type is the number of participating entity sets.
Both MANAGES and WORKS_ON are binary relationships.
• More than one relationship type can exist with the same participating entity types
For examples, MANAGES and WORKS_FOR are distinct relationships between EMPLOYEE and DEPARTMENT.
CS3402
Relationships of Higher Degree
Relationship types of degree 2 are called binary
Relationship types of degree 3 are called ternary and of
degree n are called n-ary
Supplier A supplies part B for project C
In general, an n-ary relationship is not equivalent to n binary relationships
Constraints are harder to specify for higher-degree relationships (n > 2) than for binary relationships
CS3402
Ternary Relationship: Instance Diagram
SUPPLIER s1
s2
SUPPLY
r1 j1
j2 j3
PROJECT
r2 r3 r4 r5 r6
PART
p1
p2
p3 r7
CS3402
Why not on Higher Order Relationship Types
1
m
What does it mean to put 1:n:m on the three arms of the relationship?
n
CS3402
The (min,max) Notation for
Higher Order Relationship Type Constraints
(1,2)
(1,3)
(1,5)
A Teacher can offer 1 to 2 Offerings
A Course may have 1 to 3 Offerings
A Student may enroll in 1 to 5 Offerings
CS3402
An n-ary relationship is not equivalent to n binary relationships
(S1, P1, Pj1)
(S1, P1) (S1, Pj1) (P1, Pj1)
(S1, Sp1) (Sp1, Pj1) (Sp1, P1)
CS3402
Summary of ER-Diagram Notation
Symbol
Meaning
ENTITY TYPE
WEAK ENTITY TYPE
RELATIONSHIP TYPE
IDENTIFYING RELATIONSHIP TYPE ATTRIBUTE
KEY ATTRIBUTE
MULTIVALUED ATTRIBUTE
COMPOSITE ATTRIBUTE
DERIVED ATTRIBUTE
TOTAL PARTICIPATION OF E2 IN R CARDINALITY RATIO 1:N FOR E1:E2 IN R
STRUCTURAL CONSTRAINT (min, max) ON PARTICIPATION OF E IN R
E1
R
R N
E2
E1
E2
R
(min,max)
E
CS3402
Database Modelling and Implementation
Ideas/requirements E/R Relational Relational design schema database
CS3402
Relational Model
Although the E/R approach is a simple and an appropriate way to describe the structure of data, many database implementations are always based on another approach called the relational model
E/R diagram -> relation model
The relational model was first proposed by Dr. E.F. Codd of IBM
Research in 1970 in the following paper:
”A Relational Model for Large Shared Data Banks,” Communications of the ACM, June 1970
The above paper caused a major revolution in the field of database management and earned Dr. Codd the coveted ACM Turing Award
CS3402
Informal Description
The relational model consists of a set of connected relations.
A relation looks like a table (rows x columns) of values
A relation contains a set of rows (tuples) and each column (attribute) has a column header that gives an indication of the meaning of the data items in that column
Associated with each attribute of a relation is a set of values (domain)
Movies(title:string, year:integer, length:integer)
The data elements in each row (tuple) represent certain facts that correspond to a real-world entity or relationship
CS3402
Example of a Relation
STUDENT(Name:string, Ssn: integer, Home_phone: integer, Address:string, …)
CS3402
Populated Relation State
Each relation has many records/tuples in its current relation state/instance
Whenever the database is changed, a new state arises
Basic operations for changing the database: INSERT a new tuple in a relation DELETE an existing tuple from a relation MODIFY an attribute of an existing tuple
CS3402
Populated database state for COMPANY
CS3402
Definition Summary
Informal Terms
Formal Terms
Table
Relation
Column Header
Attribute
All possible Column Values
Domain
Row
Tuple
Table Definition
Schema of a Relation
Populated Table
State of the Relation
CS3402
Characteristics Of Relations
Ordering of tuples in a relation:
The tuples are not considered to be ordered, even though they appear to be in a tabular form (may have different presentation orders)
Ordering of attributes in a relation schema R (and of values within each tuple):
We consider the attributes in R(A1, A2, …, An) and the values in t=
CS3402
Same state with different order of tuples
CS3402
Characteristics Of Relations
Values in a tuple:
All values are considered atomic (indivisible)
Basic unit for manipulation (add or change) Each value must be from the domain (set of values)
of the attribute for that column
A special null value is used to represent values that are unknown or not available or inapplicable in certain tuples
We refer to the attribute values of a tuple t by: t[Ai] or t.Ai: the value vi of attribute Ai for tuple t
CS3402
From E/R Diagrams to Relations
Converting an E/R design to a relational schema (an approximation approach):
Turn each entity set into a relation with the same set of attributes
Replace a relationship by a relation or attributes of the connected entity set.
CS3402
Example: ER of Company
CS3402
CS3402
ER-to-Relational Mapping Algorithm
COMPANY database example
Assume that the mapping will create tables with
simple single-valued attributes
Step 1: Mapping of Regular (strong) Entity Types
For each regular entity type E, create a relation E that includes all the simple attributes and all simple component of a composite attribute of E
Choose one of the key attributes E as the primary key for E
Called entity relations
• Each tuple represents an entity instance
CS3402
ER to Relations (Entity Sets)
Mapping ER Diagrams into tables (relations) Representation of (Strong) Entity Sets
E
a1
a2
…
ak
xx
yy
…
zz
a1 a2 ak
…
e1 e2
:
tuples (entities)
E
{e1, e2, …, ej}
CS3402
ER-to-Relational Mapping Algorithm
After Step1:
CS3402
ER-to-Relational Mapping Algorithm
Step 2: Mapping of Weak Entity Types
For each weak entity type E, create a relation E and include all simple attributes and simple component of the entity type as attributes of the relation.
Include primary key attribute of owner as foreign key attributes of E
The primary key of E is the combination of the foreign key and the partial key of the weak entity type
E.g., Essn and Dependent_Name
CS3402
ER to Relations (Weak Entity Set)
Representation of Weak Entity Sets Primary key
s1 … sn 1RN
w1 … wm
ES
ES
EW
s1
sr
…
sn
w1
…
EW
wm
s1
CS3402
… sr
ER-to-Relational Mapping Algorithm
After Step2:
CS3402
ER-to-Relational Mapping Algorithm
Step 3: Mapping of Binary 1:1 Relationship Types For each binary 1:1 relationship type
• Identify relations that correspond to entity types participating in R
Possible approaches:
• Foreign key approach
• Merged relationship approach
• Cross reference or relationship relation approach
CS3402
ER-to-Relational Mapping Algorithm
Foreign key approach (S –>T)
Choose one of the relations S and include the
primary key of T as a foreign key in S
Include all the simple attributes of relationship in S
It is better to choose an entity type with total participation in the role of S. (Avoid Null value)
CS3402
ER-to-Relational Mapping Algorithm
Merged relationship approach
To merge the two entity types and the relationship
into a single relation
This is possible when both participations are total.
Cross reference approach
Set up a third relation R for the purpose of cross- referencing the primary keys of the two relations S and T representing the entity types
The relation R will include the primary key attributes of S and T as foreign keys to S and T
The primary key of R will be one of the two foreign
keys
CS3402
ER-to-Relational Mapping Algorithm
After Step3:
CS3402
ER-to-Relational Mapping Algorithm
Step 4: Mapping of Binary 1:N Relationship Types Foreign key approach (S –>T)
• Identify relation that represents participating entity type at N-side of relationship type T
• Include primary key of other entity type as foreign key in T
• Include simple attributes of 1:N relationship type as attributes of T
Cross-reference approach
• as in the third option for binary 1:1 relationships
CS3402
ER-to-Relational Mapping Algorithm
After Step4:
CS3402
ER-to-Relational Mapping Algorithm
Step 5: Mapping of Binary M:N Relationship Types Cross-reference approach:
• Create a new relation R
• Include as primary key of participating entity types
as foreign key attributes in R
• Their combination forms the primary keys of the
relations
• Include any simple attributes of M:N relationship type
CS3402
ER to Relations (Many-to-Many)
Representation of Many to Many Relationship Sets
Primary key
s1 … sn A
Primary key
w1 … wm
M R
N R
Ea
Eb
s1
w1
A
CS3402
ER-to-Relational Mapping Algorithm
After Step5:
CS3402
ER-to-Relational Mapping Algorithm
Step 6: Mapping of N-ary Relationship Types For each n-ary relationship
• Create a new relation R
• Include primary keys of participating entity types
as foreign keys
• Include any simple attributes of the relationship as
attributes of R
• The primary key is a combination of all foreign keys that reference the relations representing the participating entity types
CS3402
ER-to-Relational Mapping Algorithm
Step 7: Mapping of Multivalued Attributes For each multivalued attribute A
• Create a new relation R
• Include an attribute corresponding to A, plus the primary key attribute K—as a foreign key in R—of the relation that represents the entity type or relationship type that has A as a multivalued attribute.
• Primary key of R is the combination of A and K
• If the multivalued attribute is composite, include its simple components
CS3402
ER-to-Relational Mapping Algorithm
After Step7:
CS3402
Discussion and Summary of Mapping for ER Model Constructs
CS3402
References
6e
Ch. 3 p.55 – 75 Ch. 8, p.270 – 278
CS3402