[데이터베이스] 함수 종속성과 암스트롱의 공리

728x90

데이터베이스에서의 함수 종속성

데이터베이스 설계에서 중요한 개념 중 하나는 데이터베이스 테이블의 속성 간의 관계를 설명하는 함수 종속성이다.

함수 종속성은 데이터베이스에서 데이터 무결성을 보장하고, 데이터 중복을 줄이는 데 중요한 역할을 한다.

이러한 함수 종속성은 데이터베이스 정규화 과정에서 광범위하게 사용된다.

정규화에는 큰 테이블을 함수 종속성의 종류에 따라 서로 관련된 더 작고 관리하기 쉬운 테이블로 나누는 과정이 포함된다.

함수 종속성을 이해하고 이를 활용하여 데이터베이스를 효율적이고 유지보수 관리가 가능하게 할 수 있기 때문에, 데이터베이스 디자이너와 관리자에게 매우 중요하다.

⭐️함수 종속성 (Functional Dependency)

FD를 근거로 쪼개야 spurious tuple이 생기지 않는다.
표현: FD: X → Y
X가 주어지면, Y가 unique하게 주어지는 것이 Functional Dependency이다.
모든 관계형 인스턴스에 이런 관계가 항상 만족되어야 한다.
실제 세계에 존재하는 애트리뷰트들 간의 semantics로부터 유도되는 것
(아무 규정이 없는 상태에서 키로 인해 귀결되는 값들을 우리가 dependency로 semantics를 유도)

<검사 방법>

릴레이션 인스턴스 r(R)에 속하는 어떤 임의의 두 튜플에 대해서라도
t1[X] = t2[X]이면 (X value가 같으면) t1[Y] = t2[Y] (Y value가 같다)이다.

FD는 스키마 R에 있는 애트리뷰트들 간의 특성이다.
모든 릴레이션 인스턴스에 대해 성립해야 한다.
K가 R의 key이면 K는 R의 모든 애트리뷰트들을 함수적으로 결정한다.

Dependency Finding

Dependency는 스키마 간의 관계성을 말한다.
찾으려다 못찾은 것들은 유도해내면 된다. 이 때 dependency를 찾는 inference rule(추론 규칙)이 있다.
- ▶ Armstrong’s Inference Rule = Armstrong’s Axiom
암스트롱의 추론 규칙⭐️
1) 재귀성 규칙: Y가 X에 속해있으면, X에 의해서 Y가 결정된다.
2) 부가성 규칙: X → Y이면, XZ → YZ이다. (임의의 Z를 추가로 낑겨넣어도 FD가 유지된다.)
3) 이행성 규칙: X → Y이고 Y → Z이면, X→Z이다.
- 추가된 규칙:
  - ⭐️분해 규칙(Decomposition): X → YZ이면, X → Y이고, X → Z이다.
    - 증명은 왼쪽 것을 분해하는 방식으로 증명할 수 있다.
  - 합집합 규칙(Union): X→Y이고 X→Z이면, X→YZ이다.
    - 결과 집합이 합집합이 되는 게 특징이다. 결과 집합이었던 Y와 Z의 합집합인 YZ로 합칠 수 있다.
  - 의사이행성 규칙(Pseudo-transitivity rule): X→Y이고 WY→Z이면 WX→Z이다.
    - W가 앞으로 이동한다. 결과 집합에 W attribute를 composite 하고, 중간에 넣은 W가 앞쪽으로 propagation 된다.

F의 폐포 (Closure of F: F+)

: FD 집합 F에 의해 추론될 수 있는 모든 FD들의 집합.
F의 폐포 F+는 암스트롱의 공리라고 하는 3가지 법칙을 반복 적용하여 계산할 수 있다.

암스트롱의 공리(Armstrong’s Axiom : AA)

재귀규칙: X ⊇Y 이면, X →Y
부가규칙: X → Y 이면, XZ →YZ
이행규칙: X → Y 이고 Y → Z 이면, X → Z
(알아두면 편리한 추가 규칙)
결합규칙 : X → Y 이고 X → Z 이면, X → Y Z
분해규칙 : X → Y Z 이면, X → Y 이고 X → Z
가이행 규칙 : X → Y 이고 Y Z → Ω 이면, X Z → Ω
(* X, Y, Z : 릴레이션 스키마 R 에 속한 속성들의 집합, XY : X ∪∪Y)

속성 X의 폐포(X+): X가 함수 종속하는 모든 속성들의 집합

함수 종속 X→Y가 F+에 속하는지를 알아보기 위해, F에 대하여 속성 X의 폐포 X+를 계산하여 판단한다.
후보키 찾기에 활용할 수 있다.

커버(Cover)

: 어떤 함수종속 집합 F와 동등한 최소의 함수 종속 집합을 의미한다.

ex. FD 집합, F = { X → Y, X → Z }와 G = { X → YZ }가 있다.
F의 원소 개수 2개와 G의 원소 개수 1개로 전혀 다르다.

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

G가 F+의 subset이다. 이때는 “F가 G를 Cover하고 있다”고 말한다.
▶ G가 F에서 closure를 만들면 F과 G를 커버하는 것이다.

“Equivalent”하다 = G 안에서 유도될 수 있는 모든 FD가, F로부터 유도될 수 있다면, F는 G를 cover한다고 한다.
G가 F+의 subset이면, 당연히 G에서 유도될 수 있는 것은 F에서도 유도될 수 있다.
F가 G를 cover하고, G가 F를 cover하면, F와 G는 “Equivalent”하다.

<F+가 G+를 cover한다고 하는 표현의 의미>

G에서 유도될 수 있는 (G+)는, F에서도 역시 유도될 수 있는 (F+)가 존재한다면, F+가 G+를 Cover한다고 한다.
반대로, F에서 유도될 수 있는 (F+)는, G에서도 모두 유도될 수 있으면(G+), G+가 F+를 cover한다고 한다.
closure들 간에도 커버 관계가 성립된다면 closure들도 equivalent하다.
closure가 같아도 equivalent하다고 한다. (F+ = G+)

FD의 최소 집합:

1) 우측에는 하나의 attribute만 있어야 한다.
2) 우측에서 하나도 빼내면 안 된다.
3) 좌측 X의 subset에 대해서 dependency가 있어서는 안 된다.
• FD의 모든 set은 minimal set으로부터 유도된 closure 안에 있으므로 equivalent하다.