DB Chapter 3

Ch.3: Design Theory for Relational Databases

Terminology

• Redundancy: 여분
• Decompose:분해하다
• Decomposition
• Instance: Student = Class, 김용주 = instance

1. Functional Dependencies(FD)

design theory how to improve our designs by the process of “decomposition”

left side와 right side를 나누고 그 관계를 정의할 수 있으면 functional dependency. left에 있는 것들이 정해지면 right에 있는 것은 항상 같을 경우 FD임.

EX) students(SID, name, Dongari, DongBang)

• Movies1의 instance들. 여기서 FD는 어떤것이 있는가?(Figure 6)

  

  • (title, year) → (length, genre, studioName)

    title, year가 같으면 오른쪽에 있는 것들은 항상 같음.

  • starName은 해당이 안된다. 그래서 이를 normalization.(분리해서 중복되는 tuple은 지움)

    

    title, year가 3개를 정의하므로 b에 해당하는 table을 만들어 더 간단하게 하고 title, year가 starName은 정의하지 못하니까 이를 기반으로 또 table Movies3을 만듬.

Keys of Relation

key는 uniqueness와 minimality를 만족함. 만약 key가 uniqueness만 만족하면 super key.

위의 그림을 예시로 들자면 key는 {title, year, starName}. 이 셋 attribute의 data가 정해지면 relation의 모든 component가 정해짐. super key는 {title, year, starName, length, genre} 같이 minimality는 만족하지 못함. 물론 key역시 super key에 포함됨.

• {T, Y} → {SN}이 {T, Y} → {SN, T, Y} 가능

  Many to one에서는 Many에 해당하는 key가 key. Many에 있는 key의 값이 결정되면 one에 있는 것은 자동으로 결정되기 때문.

  Many to many relationship의 경우 relationship에 있는 attribute 모두가 key. 애초에 many to many에서 가져온 attribute 자체가 모두 key임.

  One to one relationship의 경우 아무거나 해도 됨. 둘 중 하나가 나머지 하나를 정의해주기 때문.

2.Rules About FD

FD를 통해 알 수 있는 것

1. FD인 S와 T의 instance가 모두 같으면 equivalent
2. S의 instance가 T의 instance에 모두 포함되면 follow

Trivial FD

FD의 집합은 FD의 부분집합도 정의가 가능하다.

• {T, Y, SN} → {T} or {T, Y} or {T, Y, SN} 등등이 가능

Computing the Closure of Attributes

Closure: FD에 의해 포함되는 attribute들의 집합. 표기는 아래와 같다. $S^+$

주어진 FD가 A → B, BC → D라고 하자. 그러면 closure들은 이렇게 정의가 가능하다.

Algorithm 7 : Closure of a Set of Attributes

S는 FD의 집합이고, X는 처음 주어지는 closure라고 하자.

• figure 6을 이용해 Algo7을 확인해보자.
  1. {title, year} -> {length, genre, studioName}
  2. {title, year} -> {StarName} 은 포함 안댐. 즉, closure of {title, year}에 포함이 안댐(element가 아님).
  3. X = {title, year, length, genre, studioName}

Why the Closure Algorithm Works

• proof by induction

  1. {title, year} -> title, {title, year} -> year : trivial FD에 의해 basis condition 증명

  2. 그리고 set {title, year} -> {length}, {length} -> {genre}가 주어졌다고 했다고 가정

  3. {title,year} -> {length}고 {length} -> {genre}니까 {title,year} -> {genre}가 가능!(근데 이게 증명이 되남 암튼 이렇게 알아들엇읍니다)

• proof by contradiction

  R:	title	year	length	genre	studioName	starName
  t:	111	11	111	1111	11111	0000
  s:	111	11	111	1111	11111	1111

  S: title, year -> length, genre, studioName

  가정: title, year -> starName 이지만 closure에 포함되지 않음.

  instance인 t, s에 나타나 있는 starName의 값은 다르지만 가정에 의해 {title,year}의 closure에 들어가게 된다. 여기 어렵다… 모르겠어요ㅠ

Transitive Rule

FD는 transitivity를 가짐. A -> B, B -> C면 A -> C.

Closing Sets of FD

Minimal basis는 아래 3개를 만족하는 relation(B)

1. FD에서 우측에 있는 모든 값은 하나만 있어야 한다(singleton). ex) ABC -> D
2. B에서 FD 하나 지우면 얘는 더이상 basis가 아님.
3. XY -> Z가 basis라 해도 X -> Z, Y -> Z는 basis가 아님.

Minimal basis를 구하는 방법

1. Relation R에 의해 나올 수 있는 FD를 모두 구한다
2. transitive를 통해 나올 수 있는 애들은 다 제거해서 크기를 줄인다.
3. 더이상 제거할 수 없을 때 = minimal basis

Projecting FD

implied FD: 주어진 FD를 통해 새롭게 찾아낸 FD들

Alogorithm 12: Projecting a Set of FD

Relation R, 주어진 FD`s set인 S, R에 projection을 적용한 relation인 R1이 주어졌을 때, S를 통해 새롭게 구한 FD들을 포함한 모든 FD는 R1에도 똑같이 적용된다. 그리고 R1에 적용된 FD들은 basis지만 minimal basis는 아니다. 그래서 아래의 2가지 행동을 반복하면서 minimal basis를 찾는다.

1. transtive
2. AC -> B, A -> B일 경우 A -> B를 뽑는다.

• Example 13

하나 더 예시를 봅시다ㅏㅏ

3. Design of Relational DB schemas

BCNF: FD가 A1A2…An -> B1B2..Bn일 때 왼쪽에 있는게 superkey면 BCNF를 만족. 만약 nontrivial FD가 있으면 nontrivial FD만 적용, 없으면 BCNF 만족

FD: title, year -> length, genre, studioname

여기서 title, year가 superkey인가? superkey면 BCNF를 만족하고 아니면 BCNF를 만족하지 않음. 여기서 key는 title, year, starName이므로 superkey가 아님. 그래서 이 table을 decomposition하는게 좋음. 어떻게 나눌것인가? 이렇게~

(b)의 경우 title, year -> length, genre, studioName이라는 FD가 있는데 이는 BCNF를 만족

(c)의 경우 모든 attribute가 key임. 그래서 FD는 trivial한거밖에 없음. 이거도 BCNF를 만족

X+와 X(R-Y) 2개로 나뉨. 예를 들자면 Title, year이 X, length, genre, stdname이 Y면 X+는 저거 5개임. 근데 starname은 저기에 포함이 안됨!! X+기준으로 relation하나 만들고 안들어온애 기준으로 하나 또 만들고~ 이걸 더 이상 안쪼개질때까지 반복

Decomposition

1. Elimination of Anomalies
2. Recoverability of Information
3. Preservation of Dependencies

Lossless join

abc를 ab, bc로 나눈다음 다시 join면 abc가 되는데 이를 lossless join이라고 함. 근데 이는 너무 이상적.

General case로는 t(a,b,c), v(d,b,e)처럼 b의 값이 중복될 경우 AB, BC로 projection을 하고 다시 join을 하면 t, v말고 x(a,b,e)랑 y(d,b,c)같이 이전에 없던 친구들이 튀어나옴. 이런 친구들을 bogus tuple이라고 부름.

근데 FD B -> C가 있다면? B가 정해지면 C의 값도 정해지게 되므로 t(a,b,c)와 x(a,b,e)를 볼 때 c=e가 된다. 그래서 FD를 기준으로 나눠야 한다 이말이야.

Chase test

그러면 Relation을 나눴을 때, lossless join이 생기는지 안생기는지 어떻게 알 것인가? 그 방법이 chase test. 방법은 예시를 통해서~

R(ABCD)가 있고, S1(AD), S2(AC), S3(BCD) 3개로 나눌 것. FD는 A->B, B->C, CD->A가 주어짐. 그래서 tableau는 아래와 같음.(S1, S2, S3를 기준으로 각각 tuple 전개)

여기서 FD A->B를 적용할 수 있는 친구를 찾아보니 첫번째, 두번째 tuple의 A에 해당하는 값이 같음을 볼 수 있음. 그래서 b1=b2가 됨.

그 다음에 다시 살펴보면 B->C를 1,2번째 tuple에 적용 가능해서 적용하면 c1 = c가 됨.

이 다음에 CD->A를 적용할 수 있나 찾아보니 1,3번째 tuple에 적용 가능. 그래서 a = a3가 됨

맨 마지막 tuple이 a,b,c,d가 되었다는 것은 이 decomposition of relation이 lossless join을 갖고 있음을 의미. test 종료! Since there is an unsubscripted row, the decomposition for R has a losslsss join.

근데 만약 lossless join이 없다면? 마지막 tableau를 기준으로 S1, S2, S3, … Sn을 기준으로 Relation을 새롭게 만든 다음 서로 join시키면서 합쳐나감. 그럼 원래 Relation인 R보다 크게 되는데 그 안에 a,b,c,d 로만 이루어진 tuple이 있음.

5. 3NF

BCNF를 적용해서 제대로 나눴는데도 문제가 생길 수 있음. 그래서 거기서 한단계 더 발전한 것이 3NF. BCNF의 조건인 leftside가 superkey여야 한다를 만족하거나 rightside가 member of key(prime)이면 나눌 수 있다.

그러면 3NF로는 어떻게 나눌 것인가? 일단 FD를 모두 minimal basis FD로 바꾼다. 그 다음은 FD를 기준으로 나눈다.(synthesis of 3NF - algorithm 26) 마지막으로 key만 갖고 있는 relation을 하나 더 추가하면 끝~ 예시를 봅시당

R(ABCDE), FD: AB -> C, C -> B, A -> D

3NF의 경우 FD가 다 relation schema임 그래서 S1(ABC), S2(BC), S3(AD) 3개로 나눔.

Key:ABE, ACE 이므로 이 중 하나를 선택해서 S4를 만듦. 난 ABE선택

S2는 S1의 subset이니 지워도 댐. 그래서 R은 최종적으로 S1(ABC), S3(AD), S4(ABE)로 나눌 수 있음.

3NF 말고 1NF 2NF 등등도 있다!

1NF: 모든 data의 값은 1개씩만 갖고 있어야 한다

2NF: AB가 key고 A -> C면 FD의 왼쪽이 key가 아니니까 나눠야 함 AB, AC로

4NF: 곧 다룰 예정

6.MVD

MVD는 X ->-> Y처럼 2개의 화살표로 나타내는데 2개의 tuple을 스까서 새로운 2개를 만든다라고 이해하면 된다. 뭐든 예시가 직빵이므로 교수님께서 쓰신 예시를 가져와 보겠다.

여기서 주어진 MVD는 name ->-> street, city다.

tuple t하고 u를 보면 A에 해당하는 attribute의 값은 모두 같고 B와 Others에 해당하는 tuple은 다르다. 그러면 B와 Others에 해당하는 애들을 둘이 섞어서 w와 v라는 tuple을 만들 수가 있는데, 이 tuple들이 이미 전체 relation R에 있다는 것이 MVD가 의미하는 것이다.

MVD Rules

1. Every FD is an MVD
2. Complementation: 만약 X->->Y고 Z가 X나 Y의 attribute에 포함이 안되있다면 X->->Z다.

4NF

그러면 이 MVD가 왜 필요한가? 고거슨 4NF에서 사용하기 때문. 4NF는 MVD를 FD처럼 다뤄서 decomposition에 사용한다. X->->Y가 nontrivial MVD일 경우, X가 superkey가 아니라면 XY로 하나 만들고 X(R-Y)로 하나 만들고. 즉, MVD를 기준으로 BCNF를 한다고 보면 된다.

위의 그림을 예시로 들면 name ->-> street, city는 nontrivial MVD인데 X가 superkey가 아니다. 그래서 S1{name, street, city}과 S2{name, title, year}로 나눈다. 그 다음 또 검사하는데 S1에 MVD를 적용하면 name ->-> street, city의 경우 others가 없으므로 trivial MVD가 된다. S2의 경우에도 nontrivial MVD가 없으므로 이렇게 2개로 나누고 끝~

Chase for 4NF

4NF에도 chase test가 있다는 사실!(두둥) 근데 이거 설명하기 어려우니까 그냥 넘어갈께용~

만약 설명이 필요하시다면 연락주세요 한번 올려볼게유…