시험일자가 다가올 수록 초조해진다.

뭔가 계속 부족한듯하고 외우고 익힌 것은 돌아서면 잊어버린다.


지금의 가장 좋은 방법은 문제를 풀어보는 것이다.

2016년 공무원 7급 기출 문제에 재미난 것이 출제가 되었다.


릴레이션 R(A, B, C, D, E)에 대한 

종속성의 집합 F = {A→C, AC→D, D→C, D→E}가 주어졌을 때, 

종속성 집합 F의 최소 집합(minimal set)으로 옳은 것은?


① {A→C, A→D, D→C, D→E}

② {A→C, C→D, D→E}

③ {A→D, D→C, D→E}

④ {A→C, A→D} 


함수적 종속성에서 나왔던 문제는 크게 3 종류였다.

1. 후보키 찾기

2. 주어진 릴레이션의 문제를 찾기. (부분함수 종속, 이행함수 종속, 결정자 함수 종속)

3. 주어진 릴레이션의 정규화하여 정규형 구하기.


이 문제는 "종속성 집합 F의 최소 집합"을 찾는 새로운 유형의 문제이다.


먼저 개념부터 생소하여 정의를 찾아보았다.

종속성 집합 F의 최소 집합

 1. F내의 모든 종속성이 오른쪽에 하나의 속성만을 갖고 있어야 한다.

 2. F와의 동등성을 유지하기 위해서는 F로부터 어떤 함수적 종속성도 제거될 수 없다.

 3. F에서 X→A를 X의 진부분집합 Y에 대하여 Y→A로 교체했을 때, F와 동등한 함수적 종속성들의 집합이 될 수 없다.


이것은 "minimal cover"로도 정의되어 있다.

"minimal cover"를 찾는 방법은 아래와 같다.

minimal cover를 찾는 방법

 Union 규칙에 의한 FD 단순화.

 X, Y 및 Z를 속성 집합이라 한다. X -> Y와 X -> Z 이면 , X -> YZ


 왼쪽면을 단순화하여 FD 단순화

 X와 Y를 속성 집합으로, B를 X에 없는 단일 속성으로 놓는다.


 F를 다음과 같이 정의한다.

 XB -> Y


 그리고 H는

 X -> Y


 만약 F:: X -> Y 이면,  F를 H로 교환 할 수 있다. 

 즉, if Y ⊆ Xf+, 그러면 F를 H로 대체 할 수 있다.

 오른쪽을 단순화하여 FD 단순화
 X 와 Y는 속성 세트이고, C는 Y에 없는 단일 속성이다.
 F를 다음과 같이 둔다.
 X -> YC


 그리고 H는

  X -> Y


 만약 H:: X -> YC 이면, F를 H로 대체 할 수 있다. 

 즉, YC ⊆ Xh+ 이면, F를 H로 바꿀 수 있다.


위 문제를 풀어보자.

 { A→C, AC→D }를 { A→C, A→D }로 대체한다.

 F = {A→C, AC→D, D→C, D→E}가 {A→C, A→D, D→C, D→E}로 바뀌게 된다.

 A -> D 이고 D -> C 이므로 A -> C. 

 즉, A -> C는 중복이므로 제거 가능.

 F = {A→C, A→D, D→C, D→E}이 {A→D, D→C, D→E}만 남는다.


저작자 표시 비영리 변경 금지
신고

+ Recent posts

티스토리 툴바