Chap. 7  Relational DB Design

*Textbook: Chapter 8 (6판), Chapter 7(7판)

RDB의 자료구조

• Table: row/column으로 이루어진 자료구조

• Relation: Stores entities and relationships.

⇒ Normal table. (1NF, Every attribute is ‘single-valued’ for each tuple.)

e.g., p.300

⇒ Problems: Insertion, update and deletion anomalies.

(즉, 이 제약만으로는 문제점들이 발생)

⇒ Normalization이 필요. (점차 다른 제약을 가하면서 문제가 없는(normal) table들로 분해(decompose)해 나감)

Problems in a Bad DB Design

• DBA가 relation을 잘못 design하면 어떤 문제점들이 발생하는가?

⇒ ER diagram의 조악한 설계

ex) 은행:

Lending-schema = (branch-name, branch-city, assets, customer-name, loan-number, amount)

Lending(Lending-schema)  ; Lending relation (1NF)

⇒ 은행 DB: 대출

ex) 학교: p.297 그림 8.2(6판)/p.279 그림 7.2(7판)

Problems?

① The repetition of information.

⇒ Wastes space.

② 'Downtown' 지점이 ‘Newtown' 시로 이사갔을 경우?

⇒ Update problem: 모두 고치지 않으면 inconsistency가 발생.

③ 새로운 지점이 개설되었는데 대출이 없는 경우?

⇒ Insertion problem: Insertion is impossible. (P.K. is a null value.)

④ 'Smith'가 대출금을 갚았을 경우?

⇒ Deletion problem: Loses information on 'Redwood' branch.

How to Solve the Problems?

• We should decompose a relation with 'many' attributes into several relations with 'fewer' attributes.

How?

①	서로 관련 있는 속성들끼리만 한 table에 속하도록.

⇒ Functional dependency preserving decomposition.

② 분해한 table들을 다시 join하였을 때, 원래의 table과 같아지도록.

⇒ Lossless join decomposition.

ex) 방법 #1: join 속성 - ‘branch-name’

Branch-schema = (branch-name, assets, branch-city)

Borrow-schema = (branch-name, loan-number, customer-name, amount)

⇒

Branch(Branch-schema)	; a relation called Branch.

Borrow(Borrow-schema)	; a relation called Borrow.

ex) 방법 #2: join 속성 - ‘customer-name’

p.299 그림 8.3(6판)/p.280 그림 7.3(7판)

Functional Dependency

• 속성들간의 관련성(의존성)을 나타냄.

⇒ A generalization of the notion of "key".

• Superkey

Let R be a relation schema.

A subset K of R is a "superkey" of R,

if, in any legal relation r(R), for all pairs t1 and t2 of tuples in r such that

t1[K] = t2[K], then t1 = t2.

ex) R(A,B,C)  ; a relation schema.

K(A,B)   ; a superkey.   AB→C, AB→ABC

	A	B	C
t1
	t1[K]
t2
	t2[K]

r(R)

⇒ 즉, superkey 값이 같으면, 같은 tuple이어야 한다. (superkey가 tuple을 결정)

- Superkey: (in Chap 2: ER model)

A set of one or more attributes which allow us to identity uniquely an entity (a relationship) in the entity set (a relationship set).

ex)

학생
학번	성명	주민번호	주소	전화번호

{학번}: superkey?	학번 → 성명 주민번호 주소 전화번호

{학번, 성명}: superkey?	학번 성명 → 주민번호 주소 전화번호

{성명, 주소}: superkey?

{주민번호}: superkey?	주민번호 → 학번 성명 주소 전화번호

{성명, 주민번호, 주소}: superkey? 성명 주민번호 주소 → 학번 전화번호

{학번, 성명, 주민번호, 주소, 전화번호}: superkey?

ex)	(super) key 값이 같으면, tuple도 같다.

⇔	K → R

⇔	If t1[K]=t2[K], t1=t2.

(K is a superkey if, whenever t1[K]=t2[K], it is also the case that

t1[R]=t2[R] (that is, t1=t2))

• Functional dependency (속성 간의 종속 관계)

Let R be a relation schema.

Let α⊆ R and β⊆ R.

The FD α→ β holds on R,

if, in any legal relation r(R), for all pairs of tuples t1 and t2 in r such that

t1[α]=t2[α], it is also the case that t1[β]=t2[β].

(즉, α값이 같으면 β값도 같다.	⇔ α값이 β값을 함수적으로 결정한다.

⇔ β is functionally dependent on α.)

Def.) For nonempty sets A, B, a 'function', or mapping, f from A to B, denoted f: A→B, is a relation from A to B in which 'every' element of A appears exactly 'once' as the first component of an ordered pair in the relation.

⇒ We often write f(a)=b when (a,b) is an ordered pair in the function f.

y = f(x)

x: 독립변수

y: 종속변수

f(x) ⇒ x값이 결정되면 y값이 결정됨.

ex) A={1, 2, 3} and B={w, x, y, z},

f={(1,w),(2,x),(3,x)}	; function? relation?

⇒ A값이 결정되면 B값이 결정됨.

R1={(1,w),(2,x)}	; function? relation?

R2={(1,w),(2,w),(2,x),(3,z)}	; function? relation?

A→B? B→A?

Relation

Function

1

2

3

A

w

x

y

z

B

ex) p.303 그림 8-4(6판)/p.284 그림 7-4(7판)

R(A,B,C,D) : schema

r(R)	: relation

A	B	C	D
a1	b1	c1	d1
a1	b2	c1	d2
a2	b2	c2	d2
a2	b3	c2	d3
a3	b3	c2	d4

A → C  ; Satisfied.

f={(a1,c1),(a1,c1),(a2,c2),(a2,c2),(a3,c2)}={(a1,c1),(a2,c2),(a3,c2)} ; function

C → A  ; Not satisfied.	Why?

AB  → D  ; Satisfied. (There is no pair of distinct tuples t1 and t2 such that	t1[AB]=t2[AB]. Therefore, if t1[AB]=t2[AB], it must be that t1=t2, and thus, t1[D]=t2[D].)	Why?

AB  → A  ; Always satisfied. (In general, a FD of the form α→ β is	"trivial", if β⊆ α.

• The closure(폐포) of F:

- From a given set of FDs, F, we need to consider "all" FDs that hold.

ex) R = (A, B, C, G, H, I)

F = { A → B, A → C, CG → H, CG → I, B → H }

A → H ?

- By applying three rules (Armstrong's axioms) repeatedly, we can find F+ given F.

① Reflexivity(재귀) rule   : If α is a set of attrs and β⊆α, then α→ β holds.

② Augmentation(증가) rule: If α→ β holds and γ is a set of attrs,

then γα→ γβ holds.

③ Transitivity(이행) rule  :  If α→ β holds and β→ γ holds, then α→ γ holds.

e.g., p.311(6판)/p.294(7판)

- Procedure for computing F+

To compute the closure of a set of functional dependencies F:

F+ = F

REPEAT

FOR EACH functional dependency f in F+

apply 'reflexivity' and 'augmentation' rules on f

add the resulting functional dependencies to F+

FOR EACH pair of functional dependencies f1and f2 in F+

IF f1 and f2 can be combined using 'transitivity'

THEN add the resulting functional dependency to F+

UNTIL F+ does NOT change any further

- Although Armstrong's axioms are complete, we list some ‘additional’ rules.

④ Union(연합) rule: If α→ β holds and α→ γ holds, then α→ βγ holds.

pf)  αα→ αβ(by ②),  αβ→ βγ(by ②)

αα→ βγ(by ③)

α→ βγ

⑤ Decomposition(분해) rule: If α→ βγ holds, then α→ β holds and α→ γ holds.

pf)	α→ βγ, βγ→ β(by ①), α→ β(by ③)

α→ βγ, βγ→ γ(by ①), α→ γ(by ③)

*연합/분해: nonkey 속성들을 ‘합칠 수 있고/분해할 수 있음’

⑥ Pseudo transitivity(가이행) rule: If α→ β holds and βγ→ δ holds,

then αγ→ δ holds.

pf)	αγ→ βγ(by ②), βγ→ δ

αγ→ δ(by ③)

ex)	F = { A → B, A → C, CG → H, CG → I, B → H }

CG → HI ?	CG → H, CG → I, CG → HI (by ④)

AG → I ?	A → C, AG → CG (by ②)

CG → I, AG → I	(by ③)

https://en.wikipedia.org/wiki/Functional_dependency

Functional Dependency Preserving Decomposition

• When we design a relational DB, we first list those FD's that must always hold.

⇒ Then, we can decompose tables in an appropriate normal form.

⇒ We 'require' that above constraints hold on each relation.

⇒ FD's must be 'preserved'.

ex) 대출-schema = (지점명, 대출번호, 고객명, 액수)

대출이 부부 공동 명의로 허가되는 경우,

대출

지점명	대출번호	고객명	대출액
둔산	111	안중근	100,000
둔산	111	유관순	100,000

대출번호 → 고객명? 대출번호 → 대출액?

⇒ Express "facts" about the enterprise that we are modeling with our DB.

⇒ Relations must satisfy F, a given set of FDs.

Lossless Join Decomposition

• A set of relation-schemas {R1, R2, … , Rn} is a decomposition of R,

if R = R1∪R2∪ … ∪Rn.

• 'Wrong' decomposition ⇒ The 'loss' of information.

ex) Lending-schema = (branch-name, branch-city, assets, customer-name, loan-number, amount)

Lending(Lending-schema)

Decomposition(분해)

Branch-customer(branch-name, branch-city, assets, customer-name)

Customer-loan(customer-name, loan-number, amount)

⇒ ‘lossy’ join decomposition

c.f.) 강의노트 4쪽

Branch-schema = (branch-name, assets, branch-city)

Borrow-schema = (branch-name, loan-number, customer-name, amount)

⇒ ‘lossless’ join decomposition

What happens if we need to 'reconstruct' the Lending relation?

⇒ “join”

e.g., p.299 그림 8.3(6판)/p.280 그림 7.3(7판)

'Jones'가 대출 받은 대출액은?

① πamount σcustomer-name="Jones" (Lending)

② πamount σcustomer-name="Jones" (Branch-customer ∞ Customer-loan)

① = ②?	No.

Why? Join attribute 값들이 '중복'되어 join 되었음.

⇒ We have more tuples in (Branch-customer ∞ Customer-loan)

⇒ We actually have 'less' information.

⇒ A 'lossy-join' decomposition

• A lossless join decomposition

- A good DB design.

- A decomposition {R1, R2, … , Rn} of R is a lossless join decomposition for R,

if, for all relation r on schema R

r =  ΠR1(r) ∞ ΠR2(r) ∞ … ∞ ΠRn(r)

ex)	Decomposition

⇒ Branch-schema = (branch-name, assets, branch-city)

Borrow-schema=(branch-name, loan-number, customer-name, amount)

⇒ Lending = Branch ∞ Borrow

⇒ 'lossless-join' decomposition

• How to obtain lossless join decompositions?

Let R be a relation schema and F a set of FDs on R.

Let R1 and R2 form a decomposition of R.

This decomposition is a lossless join decomposition of R

if at least one of the following FDs are in F+ (the closure of F).

{ R1∩R2 → R1,  R1∩R2 → R2 }

⇒ R1∩R2가 R1의 superkey이거나, R2의 superkey인 경우

⇒ 즉, join attribute 값이 어느 한 table 또는 두 table 모두를 고유하게(uniquely) 결정하면 lossless join decomposition이 성립한다.

⇒ 우연히 중복되는 join은 일어날 수 없다.

ex) Lending-schema = (branch-name, branch-city, assets, customer-name, loan-number, amount)

Decomposition

⇒ Branch-schema = (branch-name, assets, branch-city)

Borrow-schema=(branch-name, loan-number, customer-name, amount)

FDs for Branch-schema

branch-name → assets

branch-name → branch-city

⇒ branch-name → branch-name assets branch-city in F+.

⇒ lossless join decomposition.

Normalization

• Decompose a relation using FDs

⇒ We can define normal forms (1NF, 2NF, 3NF, BCNF) which represent "good" DB designs.

⇒ NO anomalies.

• Purpose

① Try to find a DB design, BCNF which satisfies ‘dependency preserving’ and ‘lossless join’.

⇒  But, NOT every BCNF decomposition is dependency preserving.

Thus, it is NOT always possible to satisfy above three design goals.

② Try to find a DB design, 3NF which satisfies ‘dependency preserving’ and ‘lossless join’.

⇒  It is always possible to satisfy above three goals.

But, the repetition of information happens.

⇒ We normally choose to retain 'dependency preservation' and sacrifice BCNF.

Normal Forms

(1) 1NF

• Every attr is ‘single-valued’ for each tuple.

⇔ The domain of the attrs are "atomic".

ex) CLASS

COURSE#	STUID	STUNAME	FACID	SCHED	ROOM	GRADE
ART103A ART103A ART103A CS102B CS102B HST205H	S1001 S1010 S1006 S1003 S1006 S1001	Smith Burns Lee Jones Lee Smith	F101 F101 F101 F105 F105 F202	MWF9 MWF9 MWF9 TTH10 TTH10 MWF11	H221 H221 H221 M110 M110 H221	A B B A C A

Problems?

① Update anormaly

Suppose: Change the schedule of ART103A to MWF12.

⇒ Possible to update only top 2 records, NOT the third one.

⇒ Inconsistency.

② Insertion anormaly

We can't add info. about a student who has NOT yet registered.

⇒ Can't add a null value for STUID.

③ Deletion anormaly

Student S1001 dropped HST205H.

⇒ All info. about HST205H is lost.

(2) 2NF

• Full functional dependency:

X → Y is a full functional dependency,

if Y is functionally dependent on X, but NOT on any proper subset of X.

ex) If AB → C and B → C,

then AB → C is not a full FD

• A relation is in 2nd normal form (2NF),

iff it is in 1st normal form AND

all the nonkey attrs are fully functionally dependent on the key.

⇒ 1NF에서 partial functional dependency를 제거.

ex) If R is in 1NF and the key consists of a "single" attribute.

⇒ R is in 2NF.

ex) CLASS(COURSE#, STUID, STUNAME, FACID, SCHED, ROOM, GRADE)

F={COURSE# STUID → STUNAME, FACID, SCHED, ROOM, GRADE ;partial FD

COURSE# → FACID, SCHED, ROOM

STUID    → STUNAME

COURSE# STUID → FACID, SCHED, ROOM (by rule ⑤)

COURSE# STUID → STUNAME	(by rule ⑤) }

Is it in 2NF?

No, the nonkey attrs (STUNAME and FACID, SCHED, ROOM) are NOT fully dependent on the key.

• How to transform a 1NF relation into a 2NF one?

① Identify the partial FDs.

ex) COURSE# STUID → STUNAME, FACID, SCHED, ROOM, GRADE

② Remove attr.'s on the right side of the full FDs.

ex) COURSE# STUID → GRADE

③ Make a lossless join decomposition with FDs made by ① & ②, and other full	FDs.

ex)	R1 = (COURSE#, STUID, GRADE) ; from ②

R2 = (COURSE#, FACID, SCHED, ROOM)

; from COURSE# → FACID, SCHED, ROOM

R3 = (STUID, STUNAME)

; from STUID → STUNAME

Is it lossless join decompositions?

R1∩R2 = COURSE#

R1∩R3 = STUID

• Still, there are some problems in 2NF.

ex) STUDENT (STUID, STUNAME, MAJOR, CREDITS, STATUS)

F = { STUID → STUNAME, MAJOR, CREDITS, STATUS  ;(super)key

STUID	STUNAME	MAJOR	CREDITS	STATUS
S1001 S1003 S1006 S1010 S1060	Smith Jones Lee Burns Jones	HISTORY MATH CS ART CS	90 95 25 63 25	Senior Senior Freshman Junior Freshman

CREDITS → STATUS	;수강학점에 따라 학년이 결정.

STUID	→ STATUS }

e.g. CREDITS → STATUS

0 ~ 30: Freshman

31 ~ 60: Sophomore

61 ~ 90: Junior

91 ~	: Senior

Is it in 2NF?

Yes, the key consists of a 'single' attribute.

⇒ All the nonkey attrs are “fully” dependent on the key.

But, STATUS is dependent on STUID directly and 'transitively'.

⇒ transitive dependency.

Problems? Still anomalies happen.

① Update anomaly

25학점 이상은 2학년(Sophomore)으로 변경.

⇒ Fail to update all?

② Insertion anomaly

Can we insert the info. that any student with 31 credits has sophomore status before we actually have such a student?

③ Deletion anomaly

Deletion of S1010 record

⇒ Loss of Junior info.

(3) 3NF

• Transitive dependency occurs when one 'nonkey' attr. is dependent on another 'nonkey' attr.

• A relation is in 3rd normal form (3NF)

iff it is in 2NF AND

NO nonkey attr is transitively dependent on the key. ; nonkey 속성 간의 FD	가 존재하면 안됨

⇒ 2NF에서 transitive dependency를 제거.

ex) STUDENT(STUID, STUNAME, MAJOR, CREDITS, STATUS)

⇒ Lossless join decomposition

R1 = STU(STUID, STUNAME, MAJOR, CREDITS)

FR1 = { STUID → STUNAME, MAJOR, CREDITS }

R2 = STATS(CREDITS, STATUS)

FR2 = { CREDITS → STATUS }

⇒ { STUID → STATUS }가 제거됨.

• Problems in 3NF

ex) LOCATION

BLDG	FLOOR	DEPT
ENG ENG ENG ENG ART ART	1 2 3 4 1 2	CS CS AE AE MU MU

F = { BLDG FLOOR → DEPT ; 하나의 과는 전체 층을 차지.

DEPT → BLDG	; 하나의 과는 다른 빌딩에 흩어져 있지 않음. }

Is it in 3NF?	Yes.

All the nonkey attr.'s are fully functionally dependent on the key.

NO nonkey attr is transitively dependent on the key.

Problems?

① 'Redundancy' is shown.

② If floors are NOT yet assigned to the dept. but building is assigned, we can't store the info., since floor is a part of the key.

Lossless join decomposition

R1 = ( DEPT, BLDG)	FR1 = { DEPT → BLDG }

R1			R2			R2(?)
DEPT	BLDG		DEPT	FLOOR		BLDG	FLOOR
CS AE MU	ENG ENG ART		CS CS AE AE MU MU	1 2 3 4 1 2		ENG ENG ENG ENG ART ART	1 2 3 4 1 2

R2 = ( FLOOR, DEPT)	FR2 = { }

⇒ BLDG FLOOR → DEPT is lost.	BLDG: join attr.

⇒ NOT dependency preserving decomposition.         ⇒ 'lossy' join

(4) BCNF

• A relation is in Boyce-Codd normal form (BCNF)

iff for every FD,  X → Y, X is a superkey, Y⊆X.

⇒ 1NF/2NF/3NF와는 독립적으로 정의

ex) R(C, S, Z)

F = { CS → Z,

Z → C  ; Z is not a superkey }

In 3NF, but NOT in BCNF.

• Any relation has a lossless join decomposition into BCNF, but NOT always dependency preserving.

⇒ Any relation has a lossless join AND dependency preserving decomposition into 3NF.

ex) FACULTY(NAME, DEPT, OFFICE, RANK, DATEHIRED)

Assumptions:

① No two prof.s in ‘one’ dept. have the same name. (key)

② Each prof. has one office.

③ Dept. has several prof.s' office.

④ Prof.'s in the ‘same’ dept. can share offices.

F = { NAME DEPT → OFFICE RANK DATEHIRED,  ;  ① super key

NAME OFFICE → DEPT RANK DATEHIRED,  ;  ①&② super key

OFFICE → DEPT	;  ③&④ }

NAME	DEPT	OFFICE	RANK	DATEHIRED
Smith Jones Lee	CS CS CS	ENG401 ENG402 ENG401	조교수 부교수 정교수

In 3NF, but NOT in BCNF.

To reach relations in BCNF, decompose it into

R1 = FAC1(OFFICE, DEPT)

FR1 = { OFFICE → DEPT }

R2 = FAC2 (NAME, OFFICE, RANK, DATEHIRED)       // lossless join

FR2 = { NAME OFFICE → RANK DATEHIRED }

However, NAME DEPT → OFFICE RANK DATEHIRED is lost.

⇒ Dependency is NOT preserved.

⇒ BCNF is too restricted.

Summary

• Problems: Relation Schema가 “복합”되어 있으면 anomaly들이 발생.

⇒ 각각의 단일한 Schema로 하나의 table이 구성되어야 함.

⇒ FD를 사용하여 하나의 테이블에 복합된 정보가 들어가지 않도록 lossless join 분해

• Normalization:

- 1NF: Key attrs를 check.

Partial FDs가 존재하면?

⇒ key attrs가 복합되어 있음.

⇒ key attrs가 단일하도록 lossless join decomposition을 수행하여 full FDs로 만듬.

- 2NF: Nonkey attrs를 check.

Transitive FDs가 존재하면?

⇒ nonkey attrs끼리 종속관계가 존재함.

⇒ nonkey attr들이 key attr에만 종속되도록 lossless join decomposition을 수행하여 transitive FDs를 제거.

- 3NF: Partial FDs와 Transitive FDs를 제거한 table.

⇒ nonkey attr들이 순수한 key attr에만 종속되지 않는 FDs가 존재할 수 있음.

⇒ the repetition of information happens, but it's O.K.

- BCNF: nonkey attr들이 순수한 key attr에만 종속되는 table.

⇒ the repetition of information을 제거.

⇒ FDs를 잃어버리는 경우가 발생.

• Denormalization:

- 정규화된 스키마를 가지고 정규화가 아니게 하는 과정.

⇒ '중복'을 허용함.

- 시간이 중요한(time-critical) 연산을 지원하는 시스템의 '성능을 향상'시킬 목적.