KAIST/Database

[3] Design Theory : Functional Dependency, Rules about functional dependencies

나비스 2024. 4. 3. 15:07

3. Design Theory for Relational Databases

  • 관계형 데이터베이스 스키마를 설계하는 여러 가지 방법이 있다.
    • ex) E/R diagram
  • 초기의 스키마를 발전시킬 수 있다.(중복제거)
    • 여기서 문제는, 하나의 릴레이션에 너무 많은 것을 합칠 때 발생한다.
  • "GOOD 스키마 설계" 방법이 발전했다.
    • 함수적 종속성, 정규화, 다치 종속성
    • 데이터베이스가 강력하고 다양하게 쓰이는 이유 중 하나
  • Ideas →  High-Level Design → Relational Database Schema → Relational DBMS

3.1 Functional Dependencies FD 함수적 종속성

3.1.1 Definition of functional dependency 함수적 종속성의 정의

  • 키의 아이디어를 일반화하는 릴레이션 제약
  • 정의 : 만약 R 튜플이 $$A_1, A_2, ..., A_n$$ 애트리뷰트를 만족할 때, $$B_1, B_2, ..., B_n$$을 만족하면,
    B는 A에 함수적으로 의존하고 A는 B를 함수적으로 결정한다.  즉, 일부 애트리뷰트의 값이 다른 애트리뷰트의 값을 유일하게 결정한다는 의미이다. 
  • 표기 : $$A_1, A_2, ..., A_n \rightarrow B_1, B_2, ..., B_n $$

출처 : The database system : the complete book by Ullman. Figure 3.2. An instance of the relation Movies1

Movies1 릴레이션에서 title과 year가 결정되면 length, genre, studioName을 결정한다. 하지만 starName은 결정하지 않는다. 

  • FD는 릴레이션의 모든 가능한 인스턴스에 대한 것이다.
  • FD는 릴레이션을 분해하고 중복을 제거하는 데 사용할 수 있다.
  • FD는 함수의 종속성의 오른쪽 부분은 애트리뷰트 하나인 경우가 일반적이다.

$$ A1A2...An → B1$$

$$A1A2...An → B2 $$

$$…$$

$$ A1A2...An → Bm $$

 

3.1.2 Key 키

  • 함수적으로 다른 모든 애트리뷰트를 결정하는 애트리뷰트 집합
  • 같은 역할을 하는 적절한 부분 집합은 없고 키는 최소한의 집합을 의미
  • 여러 개의 키 가능 (기본키의 특별한 역할 X)
  • ex) Movies1 릴레이션의 키 : {title, year, starName}

3.1.3 Super Key 슈퍼키

  • 키를 포함하는 애트리뷰트 집합
  • 최소한 일 필요 X
  • ex) Movies1 릴레이션의 슈퍼키 : {title, year, starName}, {title, year, length, starName}

3.2 Rules about functional dependencies

3.2.1 Reasoning about functional dependencies

  • 다른 주어진 FD로부터 FD를 추론하는 것은 GOOD 스키마 설계에 중요
  • FD의 S, T 두 집합이 주어지면, 
    • 만족하는 릴레이션 집합이 동일하면 S와 T가 동등함
    • 모든 릴레이션 인스턴스가 T의 FD를 S의 FD도 만족하는 경우 S는 T를 따름

3.2.2 Splitting / Combining rule

 $$A_1, A_2, ..., A_n \rightarrow B_1, B_2, ..., B_n $$

$$ \uparrow \; \downarrow$$

$$ A1A2...An → B1$$

$$A1A2...An → B2 $$

$$…$$

$$ A1A2...An → Bm $$

위로 가는 방향은 Combining rule, 아래로 가는 방향은  Splitting rule

 

Movies1 릴레이션을 예로 들면,

title year → length gerne studioName

=

title year → length

title year → gerne

title year → studioName

 

title year → length

not!

title → length

year → length

 

즉, 왼쪽 부분을 split할 수 없고 오로지 오른쪽 부분을 split할 수있다.

3.2.3 Trivial Functional Dependencies

  • 무의미 함수적 종속성 : 제약 조건이 모든 릴레이션 인스턴스에 대해 성립하는 경우
  • A trivial FD A1A2 … An → B1 B2 … Bm : {B1, B2, … Bm} ⊆ {A1,A2, … ,An} 인 경우
    • title year → title 인경우 Trivial FD임
  • 무의미 함수적 종속성 규칙 : C는 A의 것이 아닌 B의 것일 때, A →B와 A →C는 동등함
    • title year → title length과 title year → length는 동등함.

3.2.4 Closure of attributes

  • 함수적 종속성 폐포의 정의: 주어진 함수 종속성 집합으로부터 유추할 수 있는 모든 함수적 종속성을 가진 집합
  • 함수적 종속성 폐포 표기 : {A}+

폐포 알고리즘

입력 : {A1, A2, …, An}, S의 FD 집합
출력 : 폐포 {A1, A2, …, An}+

1. 필요한 경우, S의 FD를 분할하여 각 FD가 오른쪽에 단일 속성을 가지도록 합니다.
2. X = {A1, A2, …, An} 초기화
3. B1B2 … Bm → C와 같은 FD를 반복적으로 검색합니다
    여기서 B는 X에 있지만, C는 없으면, C를 X에 추가합니다
4. X 반환

 

유추 방법 :

  • A → B
  • B → C
  • A → C 임을 유추할 수 있다

Closures and Keys

A1, A2, …, An이 모든 속성의 집합인 {A1, A2, …, An}+이면 슈퍼키

 

Armstrong's axioms

 

클로저 알고리즘이 작동하는 동안, 이러한 공리를 사용하여 어떤 FD든 파생 가능 : 추론 규칙

 

1. 재귀성 Reflexivity : 무의미한 함수적 종속성 생성

만약 {B1 ,B2 ,…, Bm} ⊆ {A1, A2, …, An} 그러면 A1 A2 … An  → B1 B2 … Bm

2. 부가성 Augmentation : 왼쪽과 오른쪽에 동일한 애트리뷰트를 양쪽에 동시에 추가
만약 A1 A2 … An → B1 B2 … Bm 그러면 A1 A2 … An C1 C2 … Ck → B1 B2 … Bm C1 C2 … Ck
 

3. 이행성 Transivity : 추론

만약 A1 A2 … An → B1 B2 … Bm 그리고 B1 B2 … Bm → C1 C2 … Ck 그러면  A1 A2 … An → C1 C2 … Ck

 

3.2.7 Closing Sets of Functional Dependencies

  • 어떤 FD들이 전체 FD 집합을 대표하는지 선택하고 싶을 때 (키를 계산하고 싶을 때)
  • FD 집합 S가 주어지면, S와 동일한 FD 집합은 S의 Basis 기초
  • S의 Minimal basis 최소 기초는 다음과 같은 기초 M이다.
    • M 안의 모든 FD들은 오른쪽이 단일항이다
    • 어떤 FD를 제거하면 M은 더 이상 기초가 아니다
    • M의 어떤 FD에서 왼쪽의 하나 이상의 속성을 제거하면, M은 더 이상 기초가 아니다
  • S = {A → AB, AB → C}라고 가정하면 그럼 최소 기초는 {A → B, A → C}이다.
    일반적으로, 여러 최소 기초가 존재할 수 있다
     
    최소 기초 생성
    입력: S = {A → AB, AB → C}
     
    FD들을 분리해서 오른쪽이 단일항이 되게 합니다.
    M = {A → B, A → A, AB → C}
     
    무의미한 FD를 제거합니다.
    M = {A → B, AB → C}
     
    각 FD의 왼쪽을 최소화합니다.
    M = {A → B, A → C}
     
    중복 FD를 제거합니다.
    M = {A → B, A → C}
     

3.2.8 Projection of Functional Dependencies FD의 투영

  • 스키마를 설계할 때, R 릴레이션의 S라는 FD가 주어지면, R1 = πL(R)에 대해 어떤 FD가 유지될까?
  • S를 만족하고 R1의 애트리뷰트만 포함하는 모든 FD를 계산
  • 일반적으로, 이 계산은 R1 애트리뷰트 수에 지수적이다.
    • R1의 모든 부분집합에 대해 클로저를 계산하고 무의미한 FD을 추가
    • 다른 FD에서 따르는 FD를 제거
    • 모든 FD의 왼쪽면 최소화
  • ex) R(A, B, C, D)가 FD’s A → B, B → C, C → D를 가정한다면
    그런 다음 R1(A, C, D)의 FD들은 A → C(추론 A → B, B → C), C → D입니다.

예제

 

  • Given R(A, B, C, D) and FD’s AB → C, C → D, D → A
    • What are all the nontrivial FD’s that follow from the above FD’s? : AB → B 처럼 subset이 되지 않는 것들만!
      • AB → D
      • C → A
      • BD → C
      • BC → D
      • AC → D
      • ABD → C
      • ABC → D
      • CD → A
      • BC → A
      • BCD → A
      • BD → A
    • What are all the keys of R?
      • AB, BD, BC
저작자표시 비영리 변경금지