✅ FD 추론규칙
✅ FD closure
FD 폐포 : 주어진 FD 집합으로부터 유도 가능한 모든 FD를 포함하는 집합
폐포 얻는 알고리즘은 다음과 같다
✅ FD minimal set
함수적 종속성을 나타내는 최소한의 집합
아래 두가지 조건을 충족해야함
1. 완전성 : 원래 집합의 모든 FD를 나타내야함
2. 적절성 : 더이상 제거할 수 있는 FD가 없어야함
FD minimal set은 주어진 FD에서 시작함
구하는 알고리즘을 분해 알고리즘이라 함
분해 알고리즘 중 하나는 암스트롱 공리를 활용하는 것임
이 알고리즘은 세 가지 공리를 기반으로 함
알고리즘은 다음과 같다
1. 원래 FD 집합에서 시작
2. 세가지 공리를 사용해 새로운 FD를 생성함. 생성된 FD는 원래의 FD를충족해야 함
3. 생성된 FD를 모든 가능한 조합을 시도해서 하나씩 추가함. 새로운 FD가 생성되지 않는 최소 FD 집합을 찾음
4. 반복해서 더이상 FD를 생성할 수 없는 최종적인 FD minimal set을 얻음
✅ relational decompositions
관계형 db에서 데이터 중복성, 불필요한 종속성을 제거하기 위해 relation을 분해하는 과정. relation 크기가 작아지고 더 나은 구조를 갖게 됨. 일관성, 효율성을 향상시킴
분해의 속성
1. 손실 없는 분해 : Lossless Decomposition
분해된 relation을 복원하면 원래의 relation을 얻을 수 있어야 함
모든 FD를 보존하는 분해가 손실 없는 분해임
2. 종속성 보존 : Dependency Preservation
분해된 relation에서 원래의 FD를 유지해야함
3. 결합성 : Joinability
분해된 relation을 결합해 원래의 relation을 얻을 수 있는지를 나타냄
분해된 relation join이 가능하면 원래 relation을 복원할 수 있음
