CS代考 Relational Model

Relational Model

Relational Data Structures
Chapter 5 – part I

Copyright By PowCoder代写 加微信 powcoder

Collect requirements (users, views, constraints, tasks)
Model requirements and validate (ERD and EERD)
Map ERD to relational model
Verify model with relational algebra
Build model using DBMS (SQL)
Optimize model (Normalization and Indexing)
Build transactions and other user tools
Intro. To DBMS

Relational Model Concepts
The concept of a Relation
The strength of the relational approach to data management comes from the formal foundation provided by the theory of relations
A Relation is a mathematical concept based on the ideas of sets

How is a Relational DB different from a File?
File Table Relational DB
File Table Relation
Record Row Tuple
Field Column Attribute
Records may be different types.
Field order matters
Record order may matter
No primary key or unique identifier field

Informal Definitions
A relation looks like a table of values.
Tuple – one row of a relation
Attribute – one column of a relation
Relation – the whole table
Domain of an Attribute – all the values that attribute can have

All the possible values an attribute can take
Remember your mathematics?
A set of Atomic Values
Indivisible
Atomic Values have name, type, format
“USA_phone_numbers”
the set of U.S. valid 10 digit phone numbers
(ddd)ddd-dddd, where each d is a decimal digit.

Domain types
Simple Domain is a set of atomic values
Composite Domains
Cartesian product of simple domains
Ex., Date = Month x Day x Year
where Month = {1, 2, …, 12}
Day = {1, 2, … 31}
Year = { 1900, 1901, …}
E.g., 10 9 1999

Informal Definitions
Key of a Relation:
Each row has a value of a data item (or set of items) that uniquely identifies that row in the table
Called the key
Sometimes row-ids or sequential numbers are assigned as keys to identify the rows in a table
Called artificial key or surrogate key

Relational Database Schema
Informally, the table definition
COMPANY relational db schema

Relation Schema
Relation schema: R or R(A1, A2, …, An)
Fixed set of attributes A1, A2, …, An
Each attribute Aj corresponds to exactly one of the underlying domains Dj (j = 1, 2, …, n),
Not necessarily distinct Dj = domain( Aj)
EMP( EMPNO, NAME, DNO, JOB, MGR, SAL, COMMISSION)
Note: EMPNO and MGR take values from the same domain, the set of valid employee numbers
n = The number of attributes in the relation schema (degree of the relation)
Degree 1 Unary
Degree 2 Binary
Degree 3 Ternary
Degree n n-ary

Example – A relation STUDENT
Same state, but with different tuple ordering

An “ordered” set of attributes
Values derived from an appropriate domain
Tuple in the EMPLOYEE relation
<"John”, “X”,“Smith", “000-99-9999”>
A relation is an unordered set of such tuples
Concrete realization, i.e. printed table does have an order.
Abstract construct does not.
Much easier to understand effects of operations if no ordering is specified.

Relation Instance
An ordered list of attributes
R(A1, A2, …, An)
With a set of values
Each tuple consists of attribute-value pairs (aj, vj), where j = 1, 2, …, n
vj is a value from the unique domain Dj that is associated with that attribute.
Mapped to a domain
r = {t1, t2, …, tm}
Each tuple t is a mapping from R → D
where, R = R(A1, A2, …, An) and
D = domain(A1)  domain(A2)  …  domain(An)

Informal  Formal Translation
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

Properties of Relations
Ordering of tuples
Relation is a set
Sets have no order
Relation is not sensitive to ordering of tuples
Uniqueness of tuples
No duplicate tuples in a relation!
Unknown values
NULL value – used when value can’t be known or does not exist
Interpretation
Relation is an assertion of facts
Each tuple can be thought of as a fact about the world
Or as a predicate in first order logic
Relations may not contain repeating groups.
Such a relation is said to be normalized or in 1st normal form.

Normalization of Repeating Groups
Before: S# (PQ)*
3 “records”
After: S# P# QTY

6 “records”

A subset of the relation attributes where all tuple values must be distinct.
SK is a set of attributes
t1 and t2 are tuples
Then, t1 [SK]  t2 [SK]

SuperKey Example
EMP( EMPNO, NAME, DNO, JOB, MGR, SAL, COMMISSION)
What are the SuperKey(s) of this relation?

EMPNO, NAME
EMPNO, NAME, DNO, JOB
EMPNO, NAME, SAL, COMMISSION
EMPNO, NAME, DNO, JOB, MGR, SAL, COMMISSION

Key – formal definition
A SuperKey where no proper subset of the attributes is a SuperKey.
A SuperKey K such that removal of any attribute(s) from K results in a set of attributes that is not a SuperKey …
i.e., does not possess the SuperKey uniqueness property

Key Example
EMP( EMPNO, NAME, DNO, JOB, MGR, SAL, COMMISSION)
What are the Key(s) of this relation?

Why isn’t EMPNO, NAME a Key?

A Key is a minimal SuperKey.

Candidate and Primary Key
A Key is a minimal SuperKey.
A relation may have more than one Key, called Candidate Keys
A Primary Key is an arbitrarily chosen Candidate Key
Generally the smallest of the candidate keys (in terms of size)

Two Candidate keys:
{EngSerialNo} akin to a VIN
{LicenseNo} contains State and Reg #
What would you choose for the Primary Key?

Any Key is a SuperKey (but not vice versa)
Any set of attributes that includes a key is a SuperKey
A minimal SuperKey is also a Key

Is every relation required to have a Primary Key?

Chapter 9 Outline
Relational Database Design Using ER-to-Relational Mapping
Mapping EER Model Constructs to Relations

Relational Database
Design by ER- and EER-to-Relational Mapping
Design a relational database schema
Based on a conceptual schema design
Algorithm to convert the basic ER model constructs into relations
Additional steps for EER model

Relational Database Design Using ER-to-Relational Mapping

E-R to Relational Mapping
Regular entity type
Weak entity type
Binary M:1 relationship
Binary 1:1 relationship
Binary M:N relationship
Multi-valued attributes
ER to Relational Mapping

ER to Relational Mapping
An ERD Example
DEPARTMENT
PROJ_MANAGE

Regular entity?
Composite attribute?
Derived attribute?
Multi-valued attribute?
Weak entity?
M:1 relationship?
1:1 relationship?
M:N relationship?

ER-to-Relational Mapping Algorithm
Step 1: Mapping of Regular Entity Types
For each regular entity type, create a relation R that includes all the simple attributes of E
Called entity relations
Each tuple represents an entity instance

ER to Relational Mapping
Step 1: Regular Entities
Map each regular entity type into a relation.
Each simple attribute of the entity type maps to an attribute of the relation.
Each composite attribute will be broken into many simple attributes.
We’ll treat Multi-valued attributes later.
Derived attributes, by definition, can be derived, and therefore are not necessary to be represented.
The primary key of the entity type maps to the primary key of the relation.

ER to Relational Mapping
An ERD Example – Step 1
DEPARTMENT
PROJ_MANAGE

Primary keys are underlined.
Department (Dept#, Dname, City)
Employee (Emp#, First, MI, Last, Salary)
Project (J#, Jname, City)

What happened to Name?
How about Phone, and Totqty?

ER-to-Relational Mapping Algorithm
Step 2: Mapping of Weak Entity Types
For each weak entity type, create a relation R and include all simple attributes of the entity type as attributes of R
Include primary key attribute of owner as foreign key attributes of R

ER to Relational Mapping
Step 2: Weak Entities
The identifying relationship of a weak entity is a Many-to-One relationship,
The weak entity type must “fully” participate in its identifying relationship.
Each weak entity type maps into a relation.
Attributes are treated as usual.
Introduce a foreign key that references the primary key of its identifying relation.
The primary key is the primary key of its identifying relation plus its own partial key.

ER to Relational Mapping
An ERD Example – Step 2
DEPARTMENT
PROJ_MANAGE

Dependent (Emp#, Dname#, Gender)

Foreign key Emp# References Employee

Foreign Key
a field (or collection of fields) in one relation that uniquely identifies a tuple of another relation
equal to the candidate key in some tuple of the PK relation, or else NULL
Multiple tuples in the FK relation may refer to the same tuple in the PK relation
Same data type and domain as PK
May have different name

ER-to-Relational Mapping Algorithm
Step 3: Mapping of Binary 1:N Relationship Types
For each regular binary 1:N relationship type
Identify relation that represents participating entity type at N-side of relationship type
Include primary key of other entity type as foreign key in S
Include simple attributes of 1:N relationship type as attributes of S

ER to Relational Mapping
Step 3: M:1 Relationships
Foreign Key approach
Each regular Many-to-One relationship type,
Add key attribute from “1” side as a foreign key to the relation on the “many” side
Do not need to introduce a separate relation.

ER to Relational Mapping
An ERD Example – Step 3
DEPARTMENT
PROJ_MANAGE

Employee (Emp#, First, MI, Last, Salary, Dept#)
Foreign key Dept# references Department

Project (J#, Jname, City, Manager#)
Foreign key Manager# references Employee

Foreign keys don’t have to have the same name as their PK

ER-to-Relational Mapping Algorithm
Step 4: 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

ER to Relational Mapping
Step 4: 1:1 Relationships
Foreign Key approach
Similarly to Many-to-One relationship.
Partial participation side is like Many side of relationship
Key attribute from partial participation side is added as foreign key to full participation side.
Merged approach
Combine into one relation / table
Relationship relation (cross reference)
Create a new table of foreign keys to relate the two tables

ER to Relational Mapping
An ERD Example – Step 4
DEPARTMENT
PROJ_MANAGE

Department (Dept#, Dname, City, Manager#)

Foreign key Manager# references Employee
Foreign Key approach

ER to Relational Mapping
An ERD Example – Step 4
DEPARTMENT
PROJ_MANAGE

Department (Dept#, Dname, City, Mgr#, First, MI, Last, Salary)

All Manager information is now a part of Department
Merged approach
Is this a desirable solution?

ER to Relational Mapping
An ERD Example – Step 4
DEPARTMENT
PROJ_MANAGE

DeptMgr (Dept#, Manager#)

New relation has a compound key that refers (FK) to both relations.
Cross Reference approach

ER-to-Relational Mapping Algorithm
Step 5: Mapping of Binary M:N Relationship Types
For each binary M:N relationship type
Create a new relation S
Include primary key of participating entity types as foreign key attributes in S
Include any simple attributes of M:N relationship type

ER to Relational Mapping
An ERD Example – Step 5
DEPARTMENT
PROJ_MANAGE

Proj_Work (Emp#, J#)

Foreign key Emp# References Employee
Foreign key J# References Project
Attributes of Proj_Work would also be added, if any

ER-to-Relational Mapping Algorithm
Step 6: Mapping of Multivalued Attributes
For each multivalued attribute
Create a new relation
If the multivalued attribute is composite, include its simple components
Create foreign key to relationship or entity it belongs to
The primary key is the combination of all the attributes.

ER to Relational Mapping
An ERD Example – Step 6
DEPARTMENT
PROJ_MANAGE

Emp_Phone (Phone, Emp#)
Foreign key Emp# References Employee

ER to Relational Mapping
Step 6: Another example
Compound Multivalued Attribute

Customer (Cust#, name)
Credit_Cards (Cust#, Card#, Expiration)
Foreign key Cust# References Customer

CREDIT_CARDS
EXPIRATION

ER to Relational Mapping
An ERD Example – Summary
DEPARTMENT
PROJ_MANAGE

Employee (Emp#, First, MI, Last, Salary, Dept# (FK))
Project (J#, Jname, City, Manager# (FK))
Department (Dept#, Dname, City, Manager#(FK))
Dependent (Emp#(FK), Dname#, Gender)
Proj_Work (Emp# (FK), J# (FK))
Emp_Phone (Phone, Emp# (FK), )

ER to Relational Mapping
An ERD Example – Summary
DEPARTMENT
PROJ_MANAGE

Employee (Emp#, First, MI, Last, Salary, Dept# (FK))
Project (J#, Jname, City, Manager# (FK))
Department (Dept#, Dname, City, Manager#(FK))
Dependent (Emp#(FK), Dname#, Gender)
Proj_Work (Emp# (FK), J# (FK))
Emp_Phone (Phone, Emp# (FK), )
Quick Check
1 table / entity
+1 table / n:m relationship
+1 table / multivalued attribute
All attributes mapped (except derived attribute)
All tables have PKs
Weak entity, M:N relationships and multivalued attribute tables have compound PKs

ER to Relational Mapping
Step 7: n-ary relationships
Each n-ary (n>2) relationship type maps into a relation.

The primary key of this relation is the combination of the primary keys of the participating entity types.

These are also foreign keys.

Attributes of the relationship type maps to attributes of the relation, similar to those of regular entity types.

ER to Relational Mapping
An ERD Example
SPJ (S#, P#, J#, QTY)

Foreign key S# References Supplier
Foreign key P# References Part
Foreign key J# References Project

Summary of Mapping for ERD

E-R to Relational Mapping
Regular entity type – map to a relation
One key of the entity type chosen as primary key for the relation

Weak entity type
Include the attribute(s) of the owner relation
Primary key is combination of owner key attributes and partial key of week entity type.

Binary M:1 relationship – map to foreign key in relation at M-side referring to a relation at 1-side

Binary 1:1 relationship – map to a foreign key from one relation referring to the other relation

ER to Relational Mapping

E-R to Relational Mapping
Binary M:N relationship – maps to a relation whose primary key includes the keys of both participating relations

Multi-valued attributes – map to a relation R that includes the key of the owner relation

Each n-ary relationship – maps to a relation that includes the keys of all participating relations

ER to Relational Mapping

ER-to-Relational Mapping Algorithm
COMPANY database example
Mapping will create tables with simple single-valued attributes

Where are the
Regular entities?
Weak entities?
Multivalued Attributes?

Where are the
Strong entities?
Weak entities?
Multivalued Attributes?

ER-to-Relational Mapping Algorithm
Step 1: Mapping of Regular Entity Types
For each regular entity type, create a relation R that includes all the simple attributes of E
Called entity relations
Each tuple represents an entity instance

ER-to-Relational Mapping Algorithm
Step 2: Mapping of Weak Entity Types
For each weak entity type, create a relation R and include all simple attributes of the entity type as attributes of R
Include primary key attribute of owner as foreign key attributes of R

ER-to-Relational Mapping Algorithm (cont’d.)
Step 3: Mapping of Binary 1:N Relationship Types
For each regular binary 1:N relationship type
Primary key from 1-side becomes foreign key in N-side

ER-to-Relational Mapping Algorithm (cont’d.)
Step 4: 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

ER-to-Relational Mapping Algorithm
Step 5: Mapping of Binary M:N Relationship Types
For each binary M:N relationship type

Create a new relation S

Include primary key of participating entity types as foreign key attributes in S

Include any simple attributes of M:N relationship type

ER-to-Relational Mapping Algorithm (cont’d.)
Step 6: Mapping of Multivalued Attributes
For each multivalued attribute
Create a new relation
Primary key of R is the combination of A and K
If the multivalued attribute is composite, include its simple components

Result of Mapping (steps 1-6)

Mapping EER Model Constructs to Relations
Extending ER-to-relational mapping algorithm

Mapping Specialization/ Generalization
Option 8a – Any specialization
Create multiple relations for all super/sub classes
Option 8b – subclasses that are total & disjoint
Create multiple relations for all subclasses
Option 8c – subclasses are disjoint, with a single special attribute
Create a single relation with a type attribute
Option 8d – subclasses are overlapping, with multiple attributes
Create a single relation with multiple type attributes

EER Mapping Example

Option 8a – Any specialization
Create multiple relations for all super/sub classes

EER Mapping Example

Option 8b – subclasses that are total & disjoint
Create multiple relations for all subclasses

EER Mapping Example
Option 8c – subclasses are disjoint, with a single special attribute
Create a single relation with a type attribute

EER Mapping Example
Option 8d – subclasses are overlapping, with multiple attributes
Create a single relation with multiple type attributes

Mapping of Categories (Union Types)
Step 9: Mapping of Union Types (Categories)
Defining superclasses have different keys
Specify a new key attribute
Surrogate key

Mapping Union types

Map conceptual schema design in the ER model to a relational database schema
Algorithm for ER-to-relational mapping
Illustrated by examples from the COMPANY database
Include additional steps in the algorithm for mapp

程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com