함수종속성
태그 :
- 개념
- 함수적 종속성(Functional Dependency)의 정의 1) 데이터들이 어떤 기준값에 의해 항상 종속되는 현상 2) 어떤 릴레이션 R에서, 애트리뷰트 X의 값 각각에 대해 애트리뷰트 Y의 값이 하나만 연관 3) ‘Y는 X에 함수적으로 종속된다’라고 정의하고 X→Y 로 표기 4) X : 결정자(determinant), Y : 종속자(dependent) 5) X와 Y를 임의의 애트리뷰트들의 집합이라고 할 때, X의 값이 Y의 값을 유일하게(unique) 결정한다면 “X는 Y를 함수적으로 결정한다(functionally determines)”라고 함 6) X → Y로 표기하고, “Y는 X에 함수적으로 종속된다” 라고 함 7) 함수적 종속성은 모든 릴레이션 인스턴스 r(R)에 대하여 성립해야 함
1. 정규화의 기본이론, 함수적 종속성의 개요
가. 함수적 종속성의 검사 방법
-릴레이션 인스턴스 r(R)에 속하는 어떠한 임의의 두 투플에 대해서도 속성들의 집합 X에 대해 동일한 값을 가질 때마다 Y에 대해서도 동일한 값을 가진다면 X → Y라는 함수적 종속성이 성립한다.
-즉, r(R)에서의 임의의 두 투플 t1과 t2에 대해 t1[X] = t2[X]이면, t1[Y] = t2[Y]이다.
나. 함수적 종속성의 중요성
-각 데이터를 종속된 테이블에 배치하여 데이터의 반복 차단
-이상현상을 제거 시 데이터의 정합성 유지
-정규화 작업 시 가장 중요한 작업으로 제2정규형에서 BCNF까지 적용 됨
다.함수종속다이어그램 (FDD: Functional Dependency Diagram)
-애트리뷰트들 간의 함수 종속관계를 도식으로 표현
릴레이션R (A,B) → C, D, E B → C C → D |
2. 함수적 종속성의 유형과 추론규칙
가. 함수적 종속성 유형
종속성구분 |
주요개념 |
완전 함수 종속 |
full functional dependency X’⊂X 이고 X’→Y 를 만족하는 애트리뷰트 X'이 존재하지 않음 |
부분 함수 종속(2FN) |
partial functional dependency X’⊂X 이고 X’→Y 를 만족하는 애트리뷰트 X'이 존재함 |
이행함수적 종속성(3FN) |
transitive dependence 릴레이션 R에서 속성 A→X이고 X→Y이면 A→Y임 |
결정자함수적종속성(BCNF) |
boyce-code normalization 함수적 종속이 되는 결정자가 후보키가 아닌 경우 즉, X→Y에서 X가 후보키가 아님 |
다중값 종속성(4NF) |
MVD: Multi-Valued Dependency 한관계에 둘이상의 독립적 다중값속성이 존재하는 경우 X, Y, Z 세개의 속성을 가진 릴레이션 R에서 속성쌍[X,Z]값에 대응하는 Y값의 집합이 X값에만 종속되고 Z값에는 독립이면 Y는 X에 다중값 종속된다고 하고 X->>Y로 표기 |
조인종속성(5NF) |
Adjoin Dependency 관계 중에서 둘로 나눌 때는 원래의 관계로 회복할 수 없으나, 셋 또는 그 이상으로 분리시킬 때 원래의 관계를 복원할 수 있는 특수한 경우임 |
나.함수적 종속성의 주요추론 규칙
구분 |
추론 |
내용 |
비고 |
기본 |
재귀 |
Y가 X의 부분집합이면 X→Y이다 |
Reflective |
증가 |
X→Y이면, XZ→YZ이다 |
Augmentation |
|
이행 |
X→Y이고, Y→Z이면, X→Z이다. |
Transitivity |
|
부가 |
연합 |
X→Y이고, Y→Z이면, X→YZ이다 |
Union |
분해 |
X→YZ이면, X→Y이고, X→Z이다. |
Decomposition |
|
가이행 |
X→Y이고, YW→Z이면, XW→Z이다 |
Pseudo-Transitivity |
3. 함수적 종속성의 예제
주민등록번호는 사원의 이름을 결정한다.
SSN → ENAME
프로젝트 번호는 프로젝트 이름과 위치를 결정한다.
PNUMBER → {PNAME, PLOCATION}
사원의 주민등록번호와 프로젝트 번호는 그 사원이 일주일동안 그 프로젝트을 위해서 일하는 시간을 결정한다.
{SSN, PNUMBER} → HOURS
4. FD의 집합 F의 폐포(closure) : F+
가. 정의 : F로부터 추론할 수 있는 모든 가능한 함수적 종속성들의 집합
나.내용
-함수적 종속성 집합 F를 사용하여 X에 의해 함수적으로 결정되는 모든 애트리뷰트들의 집합
F = SSN→ENAME,
PNUMBER→PNAME, PLOCATION,
SSN, PNUMBER→HOURS
알고리즘을 사용하여 F하에서 다음과 같은 폐포 집합들을 구할 수 있다.
SSN+=SSN, ENAME
PNUMBER+ = PNUMBER, PNAME, PLOCATION
SSN, PNUMBER+ = SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS
5.FD의 집합 F의 동등성 : Cover
가. 정의: cover
G의 모든 FD가 F로부터 추론될 수 있다면(즉, G+ Í F+) “F가 G를 덮는다(cover)” 라고 말한다.
나. 두 FD 집합의 동등성
FD의 집합 F와 G에 대하여, F의 모든 FD가 G로부터 추론될 수 있고, G의 모든 FD가 F로 부터 추론될 수 있으면 “F와 G는 동등하다(equivalent)” 라고 한다
F와 G가 다르더라도 F+ = G+이면 F와 G는 동등하다.
F가 G를 덮고 G가 F를 덮으면 F와 G는 동등하다.
다. FD 집합의 동등성을 검사하는 알고리즘이 존재함
6.함수적 종속성들의 집합 F의 최소(minimal)
가. 다음 세 조건을 만족하는 FD 집합을 최소라고 함
1) F의 모든 함수적 종속성들의 오른쪽편 애트리뷰트가 하나이다.
2) F로부터 어떤 함수적 종속성을 제거했을 때, F와 동등한 함수적 종속성들의 집합이 될 수 없다.
3). F에서 X→A를 X의 진부분집합 Y에 대하여 Y→A로 교체했을 때, F와 동등한 함수적 종속성들의 집합이 될 수 없다.
나. 함수적 종속성들의 집합 F의 최소 덮개(minimal cover)는 F와 동등한 함수적 종속성들의 최소 집합 Fmin을 의미함
함수적 종속성들의 최소 덮개는 여러 개 존재할 수 있다.
또한, 임의의 함수적 종속성들의 집합 F에 대해 알고리즘을 사용하여 적어도 하나의 최소 덮개를 구할 수 있다