Database

함수종속

배짱이 2008. 10. 10. 15:39

 

이석호 데이터베이스시스템(2005년판 기준)

 

  • 함수 종속(FD : Functional Dependency)

어떤 릴레이션 R에서 X와 Y를 각각 R의 애트리뷰트 집합의 부분 집합이라 정의.

애트리뷰트 X의 값 각각에 대해 시간에 관계없이 항상 애트리뷰트 Y의 값이 오직 하나만 연관되어 있을 때

Y는 X에 함수 종속이라 하고, X->Y라 표기한다.

ex) 학생 릴레이션.

애트리뷰트 이름, 학년, 학과는 애트리뷰트 학번에 함수 종속.

학번->이름, 학번->학년, 학번->학과, 학번->(이름, 학년, 학과)

 

  • 유의점)

X가 어떤 릴레이션 R의 후보키, 특히 기본 키라면 릴레이션 R의 모든 애트리뷰트 Y는 반드시 X에 함수 종속.

그러나, 애트리뷰트 X가 반드시 R의 후보키가 되어야 하는 것은 아님

 

  • 결정자(determinant), 종속자(dependent)

R의 두 투플에서 애트리뷰트 X의 값이 같으면 이들에 연관된 애트리뷰트 Y의 값도 반드시 같아야 함.

따라서, R에서 애트리뷰트 Y가 애트리뷰트 X에 함수 종속이라는 의미는

애트리뷰트 X가 애트리뷰트 Y의 값을 함수적으로 결정한다는 의미와 동등

: X->Y의 관계를 성립시키는 X를 결정자, Y를 종속자라고도 함

 

ex) 수강릴레이션에서 학번이 같은 모든 수강 투플들은 반드시 학년(year) 애트리뷰트 값이 같아야 함.

학번은 결정자, 학년은 종속자

 

  • 아래와 같은 당연 함수 종속은 일반적으로 제외 제외

학번->학번, {학번, 이름} -> 이름

 

  • 함수종속 다이어그램(FD Diagram)

복잡한 함수 종속 관계를 쉽게 이해하기 위해 도식으로 표현한 것

ex)

ScreenHunter_01_Oct._10_15.19.jpg

DFD에서 도출가능한 종속

{학번, 과목번호} -> 성적, 학번->학년

 

  •  완전함수종속
    릴레이션 R의 어떤 애트리뷰트 Y가 다른 복합 애트리뷰트 X에 함수종속이면서 X의 진부분 집합에는 함수 종속이 아닐 때 Y는 X에 완전 함수 종속이라고 함

진부분집합 : 자기자신 A=B를 제외한 부분 집합

 

  • 부분함수종속

학년은 복합 애트리뷰트{학번, 과목번호}에 부분함수종속

 

  • 암스트롱의 추론 규칙(inference rule)

R1:(반사 규칙) A ⊇ B이면 A->B이다. 또한 A->A이다.

R2:(첨가 규칙) A->B이면 AC->BC이고 AC->B이다.

R3:(이행 규칙) A->B이고 B->C이면 A->C이다

R4:(분해 규칙) A->BC이면 A->B이다.

R5:(결합 규칙) A->B이고 A->C이면 A->BC이다.

 

  • 인터넷 참고 자료

설계자는 주어진(알려진) FD의 집합 F를 가지고, 추가로 성립하는 FD들을  추론할 수 있다.
암스트롱의 추론 규칙들
A1. (재귀성 규칙) Y ⊆ X이면, X → Y이다.
A2. (부가성 규칙) X → Y이면, XZ → YZ이다.  (표기: XZ는 X∪Z를 의미)
A3. (이행성 규칙) X → Y이고 Y → Z이면, X → Z이다.
A1, A2, A3는 Sound하고 Complete 추론 규칙 집합을 형성한다.
건전성 특성: A1, A2, A3로부터 유도된 모든 함수적 종속성은 모든 릴레이션 상태에 대해 성립함.
추가적으로 유용한 추론 규칙들
(분해 규칙) X → YZ이면, X → Y이고 X → Z이다.
(합집합 규칙) X → Y이고 X → Z이면, X → YZ이다.
(의사이행성 규칙) X → Y이고 WY → Z이면, WX → Z이다.
완전성 특성: 위의 세 규칙 뿐 아니라 다른 추론 규칙들도 A1, A2, A3만으로부터 추론 가능하다.

 

FD의 집합 F의 폐포(closure) : F+
F로부터 추론할 수 있는 모든 가능한 함수적 종속성들의 집합
F 하에서 속성 집합 X의 폐포(closure of X under F) : X+
함수적 종속성 집합 F를 사용하여 X에 의해 함수적으로 결정되는 모든 애트리뷰트들의 집합

 

정의: 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는 동등하다.

 

 

 

 

 

 

이 글은 스프링노트에서 작성되었습니다.