데이터 베이스 [수업 정리] - 11주차 ②

corone_hi·2021년 5월 17일
0

Database

목록 보기
22/31


지난 주 학습 개요


  • Good Design을 위한 Guideline과 Table 분할

    • 정확한 이론에 기반한 Table 분할 방법을 학습하였다.
  • Anomality 현상

    • 데이터를 one table에 모두 모으는 경우 발생하는 현상을 고찰하였다.

    • 갱신 이상 (update anomality)에 대하여 학습하였다.

  • Null Padding Problem

    • 불필요한 정보나 얻을 수 없는 정보는 NULL로 padding 된다.

    • Null은 합리적이지 않을 뿐 아니라, 다양한 문제를 발생시킨다.

  • Table Dividing

    (1) 테이블을 나누는 정확한 이유를 학습하였다.

    (2) 나누는 방법을 학습하였다.

    • Lossless Join, Lossy Join, Lossless Join Decomposition을 배웠다.



Functional Dependency


Good Design이 필요한 이유와 FD 계속


  • 작업: 원 relation을 2개로 projection(decomposition) 했다가 natural
    join으로 확인 했더니 Spurious Tuple이 생겼다.

  • 원인: 원 relation을 근거 없이 잘못 decomposition(분해) 한 것이다.

  • 조치: Spurious Tuple이 안 생기도록 decomposition(분해) 해야 한다. (good
    design 해야함)

  • 방법: 어떻게 하면 good design 할 수 있는가?

    • Functional Dependency라는 성질을 이용하면 된다.



함수 종속성(Functional Dependency)


  • 표현

    • FD: X → Y

    • X가 주어지면, Y가 Unique하게 주어지는 것Functional Dependency 이다.

    • 모든 relational instance에 이런 관계가 항상 만족되어야 한다.

  • FD(Functional Dependency) : X가 정해지면, Y가 Unique하게 결정(determine)된다.

    • 예: x1이 김철수고, x2가 김철수인 동명이인이여도 김철수는 다른 사람이다. 즉 Unique 하다.

    • 속성 집합 X가 속성 집합 Y를 기능적으로 결정한다.

    • X → Y 로 표현한다.

      • 예: SSN이 결정되면, ENAME을 결정한다.

      • SSN → ENAME, 와 같이, SSN이 결정되면, 무엇인가 결정되어야 한다.

      • 또, “학생증 번호가 결정이 되면, 주소가 당연히 (즉시) 결정이 된다.”

        • 번호를 따르는 주소 (according to)
  • 모든 relational instance에 이런 관계가 항상 만족되어야 함

  • 실제 세계에 존재하는 attribute들 간의 semantics로부터 유도되는 것


  • X와 Y를 임의의 attribute들의 집합(set)이라고 할 때,

    • X의 값이 Y의 값을 유일하게(unique) 결정한다면 다음과 같다고 할 수 있다.

      • “X는 Y를 함수적으로 결정한다(functionally determines)”
  • X → Y로 표기하고, “Y는 X에 함수적으로 종속된다” 라고 한다.

    • X에 따라서 Y가 결정되기 때문
  • 함수적 종속성은 모든 릴레이션 인스턴스 r(R)에 대하여 성립해야 한다.



함수 종속성(Functional Dependency)


  • 릴레이션 인스턴스 r(R) (스키마 R을 따르는 인스턴스 집합 r)에 속하는, 어떤 임의의 두 tuple에 대해서라도

    • attribute들의 집합 X에 속하는, 동일한 instance 값을 가질 때마다,

    • attribute들의 집합 Y에 속하는, 동일한 instance 값을 가진다면,

    • X → Y라는 함수적 종속성 ” 이 성립한다.

    • 즉, X를 123을 주었다면 항상 Y도 123에 대해 동일한 결과가 나와야한다.


  • 다른 표현

    • r(R)에서 임의의 tuples(instances), t1과 t2에 대해,

      • t1[X] = t2[X]이면(X value가 같으면),

      • t1[Y] = t2[Y] (Y value가 같다) 이다.

      • X가 A1일 때, Y는 항상 K1이다.

      • But, X와 Z는 functional Dependency가 성립되지 않는다.



함수 종속성(Functional Dependency)의 의미


  • FD는 스키마 R에 있는 애트리뷰트들 간의 특성이다

    • 즉, 스키마 R에 적용되는 특성
  • FD는 같은 스키마 R을 가지는, 모든 릴레이션 인스턴스 r(R)에 대해서 성립해야 하는 성질이다.


  • K가 R의 key이면 K는 R의 모든 애트리뷰트들을 함수적으로 결정한다.

    • t1[K] = t2[K]인 서로 다른 두 개의 투플이 존재하지 않기 때문

    • 즉, 같은 key인 경우에는 같은 정보가 나와야 하고, 다른 key 일 경우에는 다른 정보가 나와야 하기 때문이다.



Rule을 통한 dependency finding 방법


Dependency Finding


  • Dependency는 schema간의 관계성을 말한다.

  • 이것이 찾아낸 것이 10개가 있다고 하자.

    • 찾아낸 것 중에서, 못 찾아낸 dependency를 유도해 낼 수 있다.
  • Dependency를 찾는 Inference rule (추론 규칙)

    • Armstrong’s Inference Rule = Armstrong’s Axiom



Armstrong's Axiom


  • Armstrong's Axiom: FD를 찾아내는 inference rule (추론 규칙)

    • Sound

      • FD set, F가 있을 때, 그 rule을 적용하면 모두 맞다. (맞는 것을 유도한다.)
    • Complete

      • FD set, F가 있을 때, 이 3개의 rule만 가지면 못 찾은 FD를 모두 다 유도할 수 (찾아낼 수) 있다.
    • If and Only If

      • 즉, Armstrong's Axiom, A1, A2, A3는 sound (FD set F가 있을 때, Rule에 의해 유도된 것이 맞다)하고 complete (FD set F가 있을 때, Rule에 의해 빠짐 없이 모두 유도된다) 추론 규칙 집합을 형성한다.


  • 암스트롱의 추론 규칙들

    A1. 재귀성 규칙 : Y ⊆ X이면, X → Y이다.

    • 큰 것에서 작은 것(subset)

    A2. 부가성 규칙 : X → Y이면, XZ → YZ이다. (표기: XZ는 X∪Z를 의미)

    • 같은 것을 붙였을 때도 FD를 유지한다.

    A3. 이행성 규칙 : X → Y이고 Y → Z이면, X → Z이다.


  • 추가된 규칙 (Additional Inference Rules)

    (1) Decomposition (분해 규칙)

    (2) Union (합집합 규칙)

    (3) Pseudo-transitivity (의사(가짜)-이행성 규칙)


  • 추가적으로 유용한 추론 규칙들

    • 분해 규칙: Decomposition rule

      • X → YZ이면, X → Y이고 X → Z이다.
    • 합집합 규칙: Union rule

      • X → Y이고 X → Z이면, X → YZ이다.
    • 의사이행성 규칙: Pseudo-transitivity rule

      • X → Y이고 WY → Z이면, WX → Z이다. (W가 앞으로 이동)

  • 위의 세 규칙 뿐 아니라, 다른 추론 규칙들도 A1, A2, A3으로부터 추론 가능하다 (완전성 특성).



(1) Decomposition rule (Armstrong's Axiom으로 유도 가능)


  • 정의: X → YZ이면, X → Y이고 X → Z이다.

  • (증명)
    **X → YZ **

    • X → YZ (주어짐),

**YZ → Y **

  • by A1. 재귀성 규칙에 의해 Z 추가

그러므로, X → Y

  • by A3. 이행성 규칙에 의해

또, X → YZ

  • X → YZ (주어짐),

**YZ → Z **

  • by A1. 재귀성 규칙에 의해 Y 추가

그러므로, X → Z는 transitive에 의해 성립, 그러므로, 모두 성립함.


  • 즉, 왼쪽 것을 분해할 수 있다.



(2) Union rule


  • 정의: X → Y이고 X → Z이면, X → YZ이다.

  • (증명)

    X → Y (given) : XX → YX

    • by A2. 부가성 규칙에 의해 X 추가

    X → Z (given) : YX → YZ

    • by A2. 부가성 규칙에 의해 Y 추가

    XX → YZ

    • by A3. 이행성 규칙에 의해

    그러므로, X → YZ 성립


  • 즉, 왼쪽 것을 합칠 수 있다.



(3) Pseudo-transitivity rule


  • 정의: X → Y이고 WY → Z이면, WX → Z이다.

  • (증명)

    XWWY이고

    • A2. 부가성 규칙에 의해 W 추가

    WY → Z 이므로,

    • 주어짐, (A3. 이행성 규칙에 의해 WY → Z는 당연히 성립)

    WX → Z 이 성립함.


  • 즉, 뒤쪽 FD에 붙은 속성을 앞으로 당길 수 있다.

    • W를 X → Y쪽으로 가져와서 붙일 수 있다.



결론


  • (Completeness) FD는 Armstrong's Axiom을 가지면, 모두 유도해 낼
    수 있다.

  • (Sound) Armstrong's Axiom으로부터 유도되는 FD는 모두 올바른 FD이다.



FD Closure & Equivalent


Closure (+)


  • FD의 집합 F의 폐포(closure): F+

    • A set of FD

    • F로부터 추론할 수 있는 모든 가능한 함수적 종속성들의 집합

    • 예: 작은 부품으로 로봇을 만들어낼 수 있다. 그 로봇이 closure이다.

      • 즉 작은 요소들이 Armstrong's Axiom(연산)으로 추론되고, 추론되어서 점점 커진 결과
  • F 하에서 속성 집합 X의 폐포 (closure of X under F): X+

    • 함수적 종속성 집합 F를 사용하여 X에 의해 함수적으로 결정되는 모든 애트리뷰트들의 집합



Closure란 무엇인가


  • Algebraic System이 있으면 그 안에 집합(Set)과 연산(Operator)이 있는데,

    이 때, A라는 집합(set)에서 요소(element)에 대해 operation을 가해서, 나온 결과도 A라는 집합(set) 안에 있어야 한다는 것이다.

      • A의 subset A'를 가지고 있는데, op를 가하면,

        A set of FD, F에 연산(Armstrong's Axion)을 적용해서 나온 모든 결과를 합한 것을 **Armstrong's Axiom에 대한 closure, F+**라 한다.

      • 즉, Armstrong's Axiom으로부터 유도될 수 있는 모든 FD의 집합을 Closure라 한다.

        • 예: 자연수에 자연수를 더하고 곱해도 자연수이다.

  • 또 다른 정의

    • X → A, X → B 등, X로부터 유도되는 모든 속성들의 집합이 있다.

      X로 부터 Fuctionally Determine되는 모든 속성들의 집합을 X의 Closure라고 한다.

    • A set of X += X → {....}

    • Armstrong's Axiom 3개를 가지고, X가 왼쪽에 오는 FD에 대해 다 적용해서, 오른쪽에 오는 것을 다 찾아내면 되는 것이다.

  • X → {....}, X로 부터 determine되는 모든 속성들의 집합X의 closure라고 한다.

  • X가 왼쪽에 오는 것을 다 찾으면 된다.

  • 반복적으로 적용해서 구한다.



FD의 집합이 F와 G가 있다. 동등한가(Equivalent)?


  • FD 집합, **F = {X → Y, X → Z}**와 **G = {X → YZ}**가 있다.

    • F의 원소 개수 2개와 G의 원소 개수 1개로 전혀 다르다.

    • FD도 모두 다르다. 그런데 F와 G가 같다고 할 수 있는가?

    • G가 F+ (F Closure)의 subset이다.

      • 이때는 "F가 G를 Cover하고 있다"고 말한다.
  • "같다"는 것의 정의가 다른 것이다. (의미로 볼 때 같다고 볼 수 있다)

    • "Equivalent" 정의

      • G 안에서 유도될 수 있는 모든 FD가, F로부터 유도될 수 있다면, F는 G를 Cover한다고 한다.

      • G가 F+의 subset이면, 당연히 G에서 유도될 수 있는 것은 F에서 유도될 수 있다.

        • F가 더 크기 때문에
  • F가 G를 Cover하고, G가 F를 Cover하면, F와 G는 "Equivalent" 하다.

    • 서로가 서로를 Cover한다는 것은 같다는 것을 의미한다.

  • F+가 G+를 Cover한다는 표현의 의미

    • G에서 유도될 수 있는 (G+)는, F에서도 역시 유도될 수 있는 (F+)가 존재한다면, F+가 G+를 Cover한다고 한다.

    • 반대로, F에서 유도될 수 있는 것(F+)은 G에서도 모두 유도될 수 있으면(G+), G+가 F+를 Cover한다고 한다.

  • Closure가 같아도 Equivalent 하다고 한다. (F+ = G+)

    • 이를 확인하기 위한 polynomial time algorithm은 없다.



FD Minimality


Minimal Functional Dependencies 개념


  • 이제, A set of FD가 minimal 하다는 것을 정의한다.

  • 각 F에 있는 FD가 오른쪽에는 하나의 속성만 있어야 한다.

    • 즉 X → YZ 와 같은 것은 없다.
  • 또, a set of FD로부터 FD를 하나 빼냈다. 그러면 빼내지 않은 것도 동일하지 않다. (Not Equivalent)

    • 이런 것이 Minimality의 조건이 된다.

    • 빼내도 minimal한 것은 minimal한 것이 아니다.


  • X → A가 있을 때, 왼쪽 Xsubset X' 에 대한 dependency도 있으면 안된다는 것이다.

    (1) 왼쪽(X)에서도 minimal 해야 되고

    (2) 오른쪽(A)에서도 minimal해야 하고

    (3) Rule의 개수도 minimal해야 한다는 것이다.

    • 세가지를 모두 만족하는 것을 "a Minimal Set of Fuctional Dependencies"라고 부른다.



Minimality의 추가 설명


  • Minimal FD만 가지고 Closure를 찾을 수 있으므로, FD 중 최소한의 FD만 남기고 나머지는 지운다.

  • Minimality는 왜 찾아 사용하는가?

    • FD와 Equivalent한 Minimum dependency의 집합을 찾을 수 있다.

    • 이것으로 theory를 증명하면 도움이 많이 되므로, minimality부터 우선 찾는다.


  • FD의 최소 집합

    (1) 우측에는 하나의 속성만 있어야 한다.

    (2) 우측에서 하나도 빼내면 안 된다.

    (3) 좌측 X의 subset에 대해서 dependency가 있어서는 안 된다.


  • FD의 모든 set은 minimal set으로부터 유도된 closure 안에 있으므로 Equivalent 하다.



Minimal Functional Dependencies


  • 어떠한 FD가 존재하던 간에 이것에 Equivalent한 a minimal set of FD가 반드시 하나씩 존재한다는 것이다.

    • a set of FD를 가지면, 이것과 Equivalent한 a minimal set of FD를 반드시 찾을 수 있다는 것이다.

    • 여러 개 있을 수 있고, 1개 이상은 반드시 있다는 것이다.

  • 이것은 우리가 Relational design algorithm을 증명할 때, 여러가지 theorem을 증명할 때, 일반적인 형태의 FD를 가지고 증명하는 것보다, minimal set을 가지고 증명하는 것이 좋을 때가 많기 때문에 배운다.

  • 아직 이것을 찾는 polymial time algorithm은 발견하지 못했다.



정규화 (Normalization)


  • Normal Form을 만드는 것: Normalization

  • Normalization(정규화)

    • Normal form (정규적인 형태) 을 만드는 과정이다.

    • 즉, 나쁜 relation을 쪼개서, 여러 개의 table로 표현하므로, 좋은 relation으로 만드는 과정(절차)이다.


  • Normal Form이란?

    • 어떤 relation schema에서 "key들(attribute들)과 FD들이 만족해야 하는 조건 정도"이다. 1NF, 2NF, 3NF, BCNF 조건 등이 있다.

    • 어떤 schema가 특정한 FD만 가지고 있어야 한다는 것이다. 다른 것을 가지고 있어서는 안 된다.

    • 4NF는 multi-valued dependency를 가지고 정의를 한다.

    • 5NF는 join dependency를 가지고 정의를 한다.

profile
Studying Computer Science

관심 있을 만한 포스트

0개의 댓글