Computer Science/데이터베이스

데이터베이스 함수적 종속성(FD ,Functional Dependency)

콩순이냉장고 2021. 12. 27. 12:47

함수적 종속성

함수적 종속성(FD ,Functional Dependency) : 애트리뷰트들 간에 존재하는 제약조건을 표현한것 , 기본키에 해당하는 애트리뷰트(들)을 결정자, 나머지 애트리뷰트들을 종속자라고 생각하면, 기본키에 값에 따라 나머지 애트리뷰드을이 결정된다

 

X → Y

X에서 Y로 함수적 종속성이 있다.

 

X는 결정자(Determinant), Y는 종속자(Dependent)라고 부른다. X에서 Y로 함수적 종속성이 존재한다고 말하거나 Y가 X에 함수적으로 종속된다고 말한다.

 

 

다음과 같이 학생 테이블을 가정한다면

 

학생테이블

학번 이름 생년월일 주소 학과
20200301 홍길동 2000/07/01 서울 국문
20200302 박봉팔 2000/07/02 부산 컴공
20200303 콩순이 2000/07/03 광주 영문
20200304 철수 2000/07/04 서울 경영

학번은 기본키이고 , {학번 →  이름} , {학번 →  생년월일}, {학번 →  주소}, {학번 →  학과} 함수적 종속성의 결정자가 된다.

 

  •  X가 관계형 스키마 R의 기본키 또는 후보키이면 해당 튜플의 어떤 부분집합 Y에 대해서도 X → Y가 성립
  • 관계형 스키마 R에 X → Y가 성립하더라도 Y → X가 성립되는것은 아님

 

함수적 종속성의 의미

 

정확하게 

임의의 관계형 스키마 R에서 임의의 두 튜플 t1,t2를 선택했을때 t1[X] = t2[X] 이면 반드시 t1[Y] = t2[Y] 이다. 여기서 X,Y는 R의 애트리뷰트 또는 복합 애트리뷰트이다.

 

 

 

추론규칙 

이러한 테이블이 존재할때

 

학생

학번 이름 생년월일 주소 학과명
20211234 영구 2001/07/01 서울 컴공
20211235 땡칠이 2001/07/02 서울 컴공
20211236 짱구 2001/0703 인천 컴공

 

학과

학과명 사무실위치 전화번호
컴공 T동 10층 02-1234-5678
경영 R동 9층 02-1234-5679

 

 

다음과 같이 학과와 학생 테이블에는 함수적 종속성이 명백하게 존재하고 이런 모든 함수적 종속성의 집합을 F라고 부른다.

 

다이어그램으로 표현하면

 

 

F={학번 → {이름,생년월일, 주소, 학과명}, 학과명  → {사무실위치, 전화번호}}

이므로

 

다음과같은 함수적 종속성을 추론할 수 있다.

 

학번  → {사무실위치, 전화번호}

 

  •  FD : Function Dependency의 약자로 함수적 종속성을 의미, f.d로도 표기
  •  F : 임의의 관계형 스키마 R에 명시된 함수적 종속성의 집합
  •  F+ : 폐포(Closure)는 F에 있는 함수적 종속성으로 부터 추론 가능한 모든 함수적 종속성 (FD)와 F를 포함한 집합을 의미

 

암스트롱의 추론 규칙(Armstrong's Inference Rule)을 사용하면 함수적 종속성이 같은것인지를 알수있음

앞으로 {X,Z} → {Y,Z}는 XZ → YZ로 표기 ({}와 ,를제거해서 표시)

 

  • 규칙 1(재귀성(Relexive)규칙)  Y⊆ X 이면  X → Y이다.
  • 규칙 2(부가성(Augmentation)규칙) X  → Y 이면 XZ → YZ이다.
  • 규칙 3(이행성(Transitive) 규칙) X → Y 이고, Y → Z 이면 X → Z이다.
  • 규칙 4(분해 (Decomposition)규칙) X → YZ 이면 X →Y and X →Z 이다.
  • 규칙 5(합집합(Union)규칙) X → Y 이고 X → Z 이면 X → YZ
  • 규칙 6(의사 이행성(Psudo-transitive)규칙) X →Y 이고 WY → Z이면 WX → Z이다.

 

규칙1~3까지는 잘알려진 규칙입니다.

 

규칙 4의 증명

(1) X →YZ(주어진 함수적 종속성)

(2) Y ⊆ YZ 이므로  규칙1(재귀성규칙)에 의하여 YZ → Y

(3) (1),(2)에 규칙 3(이행성규칙)을 적용하면 X → Y이다.

(4) (2)(3)을 Y를 Z로 바꾸면 똑같음

 

규칙 5의 증명

(1) X → Y

(2) X → Z

(3) (1)에 규칙 2를(부가성 규칙)적용 ,양쪽에 X를 부가 X →XY(XX=X임)

(4) (2)에 규칙 2를(부가성 규칙)적용, 양쪽에 Y를 부가 XY → YZ

(5) (3)과 (4)에 규칙 3(이행성규칙)을 적용하면 X → YZ

 

규칙 6의 증명

(1) X → Y

(2) WX → Z

(3) (1)에 규칙 2(부가성 규칙)적용 , 양쪽에 W를 부가 WX →WY

(4) (3),(2)에 규칙3(이행성 규칙)을 적용하면 WX → Z

 

폐포구하는 방법

 

임의의 관계형 스키마 R의 집합 X가 있다면 X의 폐포 X+를 앞의 추론 규칙들을 이용하여 구할수 있다.

 

학생

학번 이름 생년월일 주소 학과명
20211234 영구 2001/07/01 서울 컴공
20211235 땡칠이 2001/07/02 서울 컴공
20211236 짱구 2001/0703 인천 컴공

 

학과

학과명 사무실위치 전화번호
컴공 T동 10층 02-1234-5678
경영 R동 9층 02-1234-5679

 

{학번}+= {학번,이름,생년월일,주소,학과명,사무실위치,전화번호}

{학과명} += {학과명,사무실위치 ,전화번호}

 

 

Example

다음과 같은 스키마에서 학번은 기본키이고 학번  → {이름,학년,학과명} 인 함수적종속성이 존재할때

학년의 도메인은 {1,2,3,4} 이고 학과명의 도메인은 {전자공학,컴퓨터공학} 일때 

(1),(2),(3)은 어떤값이 들어갈지 추론할수있다.

 

현재 2021-12-27 기준

학번 이름 학년 학과명
20211234 유재석 1 (1) : ?
20211235 아이유 2 컴퓨터공학
20181236 박보영 (2) : ? 전자공학
20211237 공유 (3) : ? 컴퓨터공학

(1) 전자공학 or 컴퓨터공학

(2) 1,2,3,4

(3) 1