Transcript PPT - NYU Stern School of Business

C20.0046: Database
Management Systems
Lecture #4
Matthew P. Johnson
Stern School of Business, NYU
Spring, 2005
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
1
Admin

Textbooks?
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
2
Agenda







Last time: (nearly) finished E/R models per se
Announcement: may have occasional pop quizzes
 at start of class
 On reading
 Counting toward participation/attendance grade
This time:
Weak Entity Sets
Intro to relational model
Converting E/Rs to relations
Functional dependencies
 Keys and superkeys in terms of FDs
 Finding keys for relations
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
3
Weak entity sets


Example: Hierarchy – species & genus
Idea: species name unique per genus only
Species
Belongs-to

name
Genus
name
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
4
Weak entity sets

Video store connecting entity sets e.g. was a
weak entity set
MovieOf
 Product
MID
StoreOf

SID
Rental
date
BuyerOf

Store
Customer
CID
Key: date, MID,SID, CID
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
5
E/R design summary

Subject/design choices:




Should a concept be modeled as an ES or an att?
Should a concept be modeled as an ES or a
relship?
Identifying relationships: binary or multiway?
Constraints in the ER Model:



Important in determining the best design.
Much data semantics can (and should) be
captured
Normalization improves further – later
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
6
Review: E/R example

Exercise: email addresses & logins





address = username @ host
mjohnson @ stern.nyu.edu
Password table stores just username
Draw E/R diagram with weak entity set Username
supported by entity set Host
Could we design this differently?

Why/why not?
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
7
Next topic: the Relational Data Model
Database
Model
(E/R, other)
Relational
Schema
Physical
storage
Complex file
Diagrams (E/R) Tables:
organization
column names: attributes and index
rows: tuples
structures.
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
8
Relations as tables
Attribute
names
Product table/relation
Name
Price
gizmo
Power gizmo
SingleTouch
MultiTouch
$19.99
$29.99
$149.99
$203.99
Category
Manufacturer
gadgets
GizmoWorks
gadgets
GizmoWorks
photography Canon
household
Hitachi
tuples/rows/records/entities
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
9
Relational terminology


Relation is composed of tuples
Tuples composed of attribute values


Attribute has atomic types
Relation schema:
relation name + attribute names + attribute types

Relation instance: set of tuples



order doesn’t matter
Database schema: set of relation schemas
Database instance: relation instance for every
relation in the schema
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
10
Relations as sets

Remember: math relation is a subset of the crossproduct of the attribute value sets



R subset-of S x T
Product subset-of Name x Price x Cat x Mft
One member of Product relation:

(gizmo, $19.99, gadgets, GizmoWorks) in Product

DB Relation instance = math relation

Q: If relations are sets, why call “instances”?
A: R is a member of the powerset P(SxT)


powerset = set of all subsets
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
11
More on tuples

Formally, can also be a mapping

from attribute names to (correctly typed) values:






name

price

category

manufacturer 
gizmo
$19.99
gadgets
GizmoWorks
NB: ordered tuple is equiv to mapping
Sometimes we refer to a tuple by itself (note
order of attributes)


(gizmo, $19.99, gadgets, GizmoWorks) or
Product(gizmo, $19.99, gadgets, GizmoWorks).
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
12
Updates/modifications


The database maintains a current database state
Modifications of data:





DB Relation instance = math relation
Idea: we saw partic. Product DB instance





add a tuple
delete a tuple
update an attribute value in a tuple
add, delete rows  different DB rel. instances
technically, different math relations
to DBMS, still the same relation/table
Modifications to the data are frequent
Updates to the schema are rare, painful (Why?)
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
13
E/R models to relations
Recall justification:

design is easier in E/R
implementation is easier/faster in R


Parallel to program compilation:

design is easier in C/Java/whatever
implemen. is easier/faster in machine/byte code


Strategy

apply semi-mechanical conversion rules
improve by combining some relations
improve by normalization
1.
2.
3.

involves finding functional dependencies
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
14
E/R conversion rules

Relationship  relation



Entity set  … relation



attributes: attributes of entity set
key: key of ES
NB: mapping of types is not one-one


attributes: keys of entity-sets/roles
key: depends on multiplicity
We’ll see: mapping one tokens is not one-one
Special treatment:


Weak entity sets
Isa relations & subclasses
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
15
Entity Sets

Entity set Students
ssn
Students
name
address
Rel: Students
SSN
Name
Address
111-222-3333
Howard
Park Avenue
444-555-6666
John
South Carolina
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
16
Entity Sets
CourseID
Course
CourseName
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
17
Binary many-to-many relationships

Key: keys of both entities
S_addr
Students
Enrolls
Course-Name
Course
S_Name
ssn

CourseID
Relation: Enrolls
ssn
CourseID
111-222-3333
C20.0046
111-222-3333
C20.0056
444-555-6666
C30.0046
Why we learned to recognize keys
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
18
Many-to-one relationships
CopyrightNo
Title
MovieID
Name
StudioID
Year
Movies
owns
Movies
Address
Studios
Studios
MovieID Title
Year
StudioID
Name
Address
M101
Mr. Ripley.
1999
S35
Miramax
NYC
M202
Sylia
2003
S73
Disney
Orlando

Key: keys of
many entitiy
Owns MovieID
StudioID CopyrightNo
M101
S73
CN11111
M202
S35
CN22222
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
19
Improving on many-one

Note rules applied:




Movies Rel.: all atts from Movies ES
Studios Rel: all atts from Studios ES
Owns Rel: att key atts from Movies & Studios ESs
But: Owns:MoviesStudios is many-one


for each row in Movies, there’s a(/no) row in Owns
 just add the Owns data to Movies
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
20
Many-to-one: a better design
Movies
Owns
MovieID Title
Year
MovieID
StudioID CopyrightNo
M101
Mr. Ripley.
1999
M101
S73
CN11111
M202
Sylia
2003
M202
S35
CN22222
Movies’

MovieID
Title
Year
StudioID CopyrightNo
M101
Talent Mr.
Ripley
1999
S73
CN11111
M202
Sylia
2003
S35
CN22222
Q: What if a movie’s Owns row were missing?
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
21
Many-to-many relationships again

Won’t work for many-many relationships
Movies
Movies
acts
Stars
MovieID Title
Year
M101
Mr. Ripley
1999
Acts
M202
Sylia
2003
MovieID
StarID
M303
P.D. Love
2002
M101
T400
M202
T400
Stars
StarID
Name
Address
M101
T401
T400
Gwyneth P.
Bev.Hills
M101
T402
T401
P.S. Hoffman
Hollywood
M303
T401
T402
Jude Law
Palm Springs
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
22
Many-to-many relationships again
And here’s why:
MovieID
Title
Year
StarID
M101
Talented Mr. Ripley
1999
T400
M101
Talented Mr. Ripley
1999
T401
M101
Talented Mr. Ripley
1999
T402
M202
Sylia
2003
T400
M303
Punch Drunk Love
2003
T401
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
23
Multiway relationships & roles
SSN
CourseID
enrolls
Students
Name
tutors
Courses
graders
Name
TAs
TA_SSN


Name
Different roles treated as different entity sets
Key: keys of the many entities
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
24
Multiway relationships & roles
Students
TAs
Courses
SSN
Name
TA_SSN
Name
111-11-1111
George
333-33-3333
Wesley
444-44-4444
Howard
555-55-5555
John
222-22-2222
Dick
CourseID
Name
C20.0046
Databases
C20.0056
Software
Enrolls(S_SSN, Course_ID, Tutor_SSN, Grader_SSN)
S_SSN
CourseID
Tutor_SSN
Grader_SSN
111-11-1111
C20.0046
333-33-3333
444-44-4444
222-22-2222
C20.0046
444-44-4444
555-55-5555
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
25
Converting weak ESs – differences
StudioName
Crew_ID
Crew

Atts of Crew Rel are:



Unit-of
attributes of Crew
key attributes of
supporting ESs
address
Studio
Crew
StudioName Crew_ID
Miramax
C1
Miramax
C2
Disney
C1
Supporting relships may be omitted (why?)
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
26
For next week

Tuesday’s reading is online

Proj1 is due Thursday, start of class
M.P. Johnson, DBMS, Stern/NYU, Spring 2005
27