함수 종속

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

함수 종속은 릴레이션 R에서 애트리뷰트 집합 X의 값이 Y의 값을 유일하게 결정할 때 X → Y로 표기하며, X가 Y를 함수적으로 결정한다고 정의한다. 이는 데이터베이스 설계, 정규화 및 비정규화 과정에서 중요한 개념으로, 후보 키를 결정하고 데이터 중복을 방지하는 데 활용된다. 암스트롱의 공리를 통해 함수 종속성의 성질을 파악하고, 이를 바탕으로 함수 종속성 집합의 폐포, 애트리뷰트 집합의 폐포, 커버, 동등성, 그리고 축약 불가능한 함수 종속 집합을 정의할 수 있다. 또한, 히스의 정리를 통해 함수 종속성을 이용한 무손실 조인 분해를 수행하고, 데이터베이스 정규형을 설계하는 데 활용된다.

더 읽어볼만한 페이지

데이터 모델링 - 빌딩 정보 모델링
빌딩 정보 모델링(BIM)은 건축물의 전 생애주기 동안 발생하는 정보를 디지털 모델로 통합 관리하는 프로세스이다.
데이터 모델링 - 저장 프로시저
저장 프로시저는 데이터베이스 관리 시스템에서 SQL 문들을 미리 컴파일하여 저장하고, 모듈화, 보안성, 성능 향상, 유지보수 용이성과 같은 특징을 가지며, 데이터베이스 시스템마다 구현 방식과 지원하는 언어가 다를 수 있는 코드 묶음이다.

함수 종속
개념
정의	관계형 데이터베이스 이론에서, 함수 종속성은 관계 내의 속성 간의 제약 조건이다.
설명	속성 X의 값이 속성 Y의 값을 고유하게 결정하는 경우, 속성 Y는 속성 X에 함수적으로 종속된다.
표기법	X → Y (X가 Y를 함수적으로 결정한다)
예시	주어진 테이블에서 학생 ID는 학생 이름을 고유하게 결정한다. 학생 ID → 학생 이름
형식적 정의
관계형 스키마	R(A1, A2, ..., An)
속성 집합	X ⊆ {A1, A2, ..., An} 및 Y ⊆ {A1, A2, ..., An}
함수 종속성	X → Y
조건	R의 모든 인스턴스 r에 대해, r에서 동일한 X 값을 가진 튜플은 동일한 Y 값을 가져야 한다.
추론 규칙 (암스트롱 공리)
반사성	만약 Y ⊆ X이면, X → Y이다.
증가성	만약 X → Y이면, XZ → YZ이다.
이행성	만약 X → Y이고 Y → Z이면, X → Z이다.
추가 규칙 (암스트롱 공리에서 파생)
합집합	만약 X → Y이고 X → Z이면, X → YZ이다.
분해	만약 X → YZ이면, X → Y이고 X → Z이다.
유사 이행성	만약 X → Y이고 WY → Z이면, XW → Z이다.
속성 폐쇄
정의	속성 집합 X의 폐쇄 (X+)는 함수 종속성 집합 F에 의해 결정되는 X로부터 함수적으로 결정될 수 있는 모든 속성의 집합이다.
용도	슈퍼키 계산 함수 종속성 유효성 검사
정규화와의 관계
정규화	데이터베이스 정규화는 함수 종속성을 분석하여 데이터베이스 스키마의 중복성을 줄이고 데이터 무결성을 개선하는 과정이다.
정규형	함수 종속성은 제1정규형 (1NF), 제2정규형 (2NF), 제3정규형 (3NF), 보이시-코드 정규형 (BCNF)과 같은 다양한 정규형의 정의에 사용된다.
키워드
결정자 집합 (Determinant set)	함수 종속성의 좌변에 나타나는 속성 집합.
종속 속성 (Dependent attribute)	함수 종속성의 우변에 나타나는 속성.

2. 함수 종속성의 정의

릴레이션 R의 애트리뷰트 집합 X와 Y가 있다고 할 때, X의 값이 주어지면 Y의 값을 유일하게 결정할 수 있는 경우, 이를 X → Y 와 같이 표기하며, "X가 Y를 함수적으로 결정한다"고 말한다. 이는 특정 튜플에서 X 애트리뷰트의 값을 알면 Y 애트리뷰트의 값을 유일하게 식별할 수 있다는 의미이다. 여기서 "함수"는 식별 함수를 의미한다.

함수 종속성을 찾아내는 것은 관계형 모델 기반의 데이터베이스를 설계하거나, 데이터베이스 정규화 및 데이터베이스 비정규화를 수행할 때 매우 중요한 과정이다. 함수 종속은 데이터에 대한 제약을 정의하여, 애트리뷰트 도메인과 함께 유효하지 않은 데이터를 최대한 제거하는 데 도움을 준다.

예를 들어, 차량과 엔진 배기량을 관리하는 시스템을 설계한다고 가정해 보자. 각 차량에는 고유한 차량 식별 번호(VIN)가 부여된다. 차량 한 대는 하나의 엔진 배기량만을 가지므로(차량에 엔진이 하나만 있다고 가정), "VIN → 배기량"이라는 함수 종속 관계가 성립한다. 즉, VIN을 알면 해당 차량의 배기량을 유일하게 알 수 있다. 반대로, 동일한 배기량을 가진 차량이 여러 대 존재할 수 있기 때문에 "배기량 → VIN"이라는 함수 종속은 성립하지 않는다.

함수 종속 관계 중에는 추이적(transitive)인 경우도 존재한다. 예를 들어, "VIN → 차량모델"이고 "차량모델 → 배기량"이라는 두 함수 종속이 성립한다면, 추이 규칙에 따라 "VIN → 배기량"이라는 함수 종속도 성립하게 된다.^[11] 이러한 추이적 함수 종속은 데이터베이스 정규화 과정에서 고려되어야 할 중요한 요소이다.

함수 종속성에는 몇 가지 중요한 성질이 있으며, 이는 암스트롱 공리로 알려져 있고 데이터베이스 정규화 이론의 기초가 된다. 릴레이션 R의 애트리뷰트 집합 X, Y, Z에 대해 다음과 같은 기본 규칙들이 성립한다.

부분 집합의 특성 (반사 규칙): Y가 X의 부분 집합이라면, X → Y이다. (이는 자명한 함수 종속성에 해당한다.)
증가 (증가 규칙): X → Y이면, 임의의 애트리뷰트 집합 Z에 대해 XZ → YZ이다.
추이성 (추이 규칙): X → Y이고 Y → Z이면, X → Z이다.

이러한 암스트롱 공리로부터 다음과 같은 부가적인 규칙들을 유도할 수 있다.

결합 규칙: X → Y이고 X → Z이면, X → YZ이다.
분해 규칙: X → YZ이면, X → Y이고 X → Z이다.
유사 추이성 규칙: X → Y이고 YZ → W이면, XZ → W이다.

2. 1. 후보 키

후보 키는 릴레이션 내의 모든 애트리뷰트를 함수적으로 결정하는 최소한의 애트리뷰트 집합이다.

예를 들어, 차량과 엔진 배기량을 관리하는 시스템에서 각 차량은 고유한 차량 식별 번호(VIN)를 가진다. 이때 VIN은 후보 키가 될 수 있다. "VIN → 배기량"이라는 함수 종속 관계는, VIN을 알면 해당 차량의 배기량을 유일하게 결정할 수 있다는 의미이다. 이는 애트리뷰트 '배기량'이 후보 키 'VIN'과 함께 하나의 릴레이션 안에 포함될 수 있음을 보여준다. 그러나 "배기량 → VIN" 관계는 성립하지 않는데, 동일한 배기량을 가진 여러 차량이 존재할 수 있기 때문이다. 즉, 배기량만으로는 특정 차량(VIN)을 고유하게 식별할 수 없으므로 배기량은 후보 키가 될 수 없다.

2. 2. 자명한 함수 종속성

만약 애트리뷰트 집합 Y가 애트리뷰트 집합 X의 부분 집합이라면, 함수 종속 X → Y는 자명하다(trivial)고 한다. 이는 X의 값이 주어졌을 때 Y의 값은 이미 X 안에 포함되어 있으므로 항상 결정될 수 있다는 의미이다.

3. 함수 종속성의 예시

함수 종속성을 찾아내는 것은 관계형 모델 하의 데이터베이스를 설계하거나, 데이터베이스 정규화, 데이터베이스 비정규화를 수행할 때 매우 중요한 과정 중 하나이다. 함수 종속은 사용자 도메인에 맞지 않는 데이터를 가능한 한 많이 제거하기 위한 제약을 생성하기 위해 속성 도메인과 함께 선택된다.

실생활의 다양한 상황을 모델링하며 함수 종속성의 개념을 구체적으로 이해할 수 있다. 예를 들어, 차량과 엔진 배기량을 관리하는 시스템, 대학생의 수강 정보 시스템, 혹은 회사의 직원과 부서 정보 관리 시스템 등에서 함수 종속 관계를 찾아볼 수 있다. 이러한 예시들은 데이터 간의 논리적 관계를 파악하고 효율적인 데이터베이스 구조를 설계하는 데 도움을 주며, 각 예시에 대한 자세한 내용은 하위 섹션에서 살펴볼 수 있다.

3. 1. 차량

차량과 엔진 배기량을 추적 관리하는 시스템을 설계한다고 가정해 보자. 각 차량에는 고유한 차량 식별 번호(VIN)가 부여된다. 차량 한 대는 하나의 엔진 배기량만을 가지므로 (이 예제에서는 차량에 엔진이 하나만 있다고 가정한다), "VIN → 배기량"이라는 함수 종속 관계를 설정할 수 있다. 즉, VIN을 알면 해당 차량의 배기량을 유일하게 결정할 수 있다.

하지만 그 반대인 "배기량 → VIN"은 성립하지 않는다. 동일한 배기량을 가진 여러 차량이 존재할 수 있기 때문이다.

이러한 함수 종속 관계는 '배기량'이라는 속성(애트리뷰트)을 후보 키인 'VIN'과 함께 하나의 릴레이션(표)에 포함시킬 수 있음을 시사한다. 그러나 이것이 항상 최선의 설계 방법은 아니다. 예를 들어, 함수 종속 관계가 다음과 같은 이행적 함수 종속의 결과일 수도 있다.

VIN → 차량모델
차량모델 → 배기량

이 경우, VIN을 통해 차량모델을 알 수 있고, 차량모델을 통해 배기량을 알 수 있으므로 결과적으로 VIN → 배기량 관계가 성립하지만, 이는 이행적 함수 종속에 해당한다.^[11] 이러한 구조는 데이터베이스 설계 시 정규화 원칙에 따라 분리하는 것이 일반적이다.

3. 2. 강의

다음은 함수 종속 개념을 설명하기 위한 예시이다. 이 예시는 대학생들이 각기 다른 조교(TA)가 배정된 하나 이상의 강의를 수강하는 상황을 가정한다. 모든 학생은 특정 학기에 속하며, 고유한 정수 ID로 식별된다.

학생 ID	학기	강의	조교
1234	6	수치 해석	존
1221	4	수치 해석	스미스
1234	6	시각 컴퓨팅	밥
1201	2	수치 해석	피터
1201	2	물리학 II	사이먼

위 표를 보면, 두 행의 '학생 ID'가 같을 경우, 해당 행들의 '학기' 값 역시 필연적으로 같다는 것을 알 수 있다. 이 기본적인 사실은 다음과 같은 함수 종속성으로 표현할 수 있다.

학생 ID → 학기

만약 어떤 학생이 다른 학기에 속하는 행이 추가된다면, 위 함수 종속성은 더 이상 유효하지 않게 된다. 이는 함수 종속성이 데이터를 통해 암시되며, 데이터 값에 따라 유효성이 달라질 수 있음을 보여준다.

다른 비자명적 함수 종속성도 식별할 수 있다. 예를 들면 다음과 같다.

{학생 ID, 강의} → 조교
{학생 ID, 강의} → {조교, 학기}

마지막 함수 종속성은 집합 {학생 ID, 강의}가 이 관계(표)의 슈퍼키임을 나타낸다.

3. 3. 직원 부서

함수 종속의 전형적인 예는 직원 부서 모델이다.

직원 ID	직원 이름	부서 ID	부서 이름
0001	존 도	1	인사부
0002	제인 도	2	마케팅
0003	존 스미스	1	인사부
0004	제인 구달	3	영업

이 사례는 단일 데이터 표현에 여러 함수 종속성이 포함된 예시를 나타낸다. 직원은 하나의 부서에만 소속될 수 있으므로 해당 직원의 고유 ID가 부서를 결정한다는 점에 유의해야 한다.

직원 ID → 직원 이름
직원 ID → 부서 ID

이 관계 외에도 테이블은 비-키 속성을 통해 함수 종속성을 갖는다.

부서 ID → 부서 이름

이 예시는 FD 직원 ID → 부서 ID가 존재하더라도 직원 ID가 부서 이름을 결정하는 논리적인 키가 아니라는 것을 보여준다. 데이터 정규화 프로세스는 모든 FD를 인식하고, 설계자가 데이터를 기반으로 더 논리적인 테이블과 관계를 구축할 수 있도록 한다.

4. 함수 종속성의 성질

릴레이션 R의 애트리뷰트(속성) 집합 X, Y, Z가 주어졌을 때, 함수 종속성은 여러 중요한 성질을 가진다. 이러한 성질들은 데이터베이스 정규화 과정에서 핵심적인 역할을 수행한다.^[3]

가장 대표적인 성질은 암스트롱의 공리(Armstrong's axioms)로 알려져 있으며, 이는 다음과 같은 기본 규칙들로 구성된다.^[3]^[4]

'''반사율''' (Reflexivity)
'''증대''' (Augmentation)
'''전이성''' (Transitivity)

이 세 가지 기본 공리는 함수 종속성에 대한 추론의 기초를 이루며, 정당하고(sound) 완전한(complete) 것으로 알려져 있다.^[5]

또한, 암스트롱의 공리로부터 다음과 같은 부가적인 규칙들이 유도될 수 있다.^[3]^[7]

'''합집합''' (Union) 또는 '''결합''' (Composition)
'''분해''' (Decomposition)
'''유사 이행성''' (Pseudotransitivity)
'''합성''' (Composition)^[6]

이러한 함수 종속성의 성질들은 관계형 데이터베이스 설계 시 제약 조건을 정의하고 데이터 무결성을 유지하는 데 필수적으로 사용된다.

4. 1. 암스트롱 공리

관계 R의 속성(attribute) 집합 X, Y, Z가 주어졌을 때, 함수 종속성의 여러 성질을 유도할 수 있다. 그중 중요한 성질은 암스트롱의 공리(Armstrong's axioms)이며, 이는 데이터베이스 정규화에 사용된다.^[3]

암스트롱의 공리는 다음과 같은 세 가지 주요 규칙으로 구성된다:^[3]

'''반사율''' (Reflexivity) 또는 '''부분집합의 성질''' (Subset Property): 만약 ''Y''가 ''X''의 부분 집합이면, ''X'' → ''Y''이다.
'''증대''' (Augmentation) 또는 '''확대의 공리''' (Augmentation Rule): 만약 ''X'' → ''Y''이면, ''XZ'' → ''YZ''이다.
'''전이성''' (Transitivity) 또는 '''이행의 공리''' (Transitivity Rule): 만약 ''X'' → ''Y''이고 ''Y'' → ''Z''이면, ''X'' → ''Z''이다.

이 세 가지 규칙은 함수 종속성에 대해 정당하고(sound) 완전하다(complete). 즉, 주어진 함수 종속(FD)들의 집합 F로부터 반드시 F의 폐포(closure), F+에 속하는 FD들만 생성할 수 있으므로 정당하며, 이 세 규칙을 반복해서 적용하면 F+에 속하는 모든 FD들을 생성할 수 있으므로 완전하다. 이 공리화는 추론 규칙의 수가 유한하다는 점에서 유한하다고 묘사되기도 한다.^[5]

암스트롱의 공리로부터 다음과 같은 부가적인 규칙들을 유도할 수 있다.

'''합집합''' (Union) 또는 '''결합''' (Additive Rule): 만약 ''X'' → ''Y''이고 ''X'' → ''Z''이면, ''X'' → ''YZ''이다.
'''분해''' (Decomposition) 또는 '''투영''' (Projectivity Rule): 만약 ''X'' → ''YZ''이면, ''X'' → ''Y''이고 ''X'' → ''Z''이다.
결합과 분해 규칙은 ''X'' → ''Y''이고 ''X'' → ''Z''인 것과 ''X'' → ''YZ''인 것이 필요충분조건임을 의미한다.^[3]^[7]
'''유사 이행성''' (Pseudotransitivity): 만약 ''X'' → ''Y''이고 ''YW'' → ''Z''이면, ''XW'' → ''Z''이다.^[3] (또는 만약 ''X'' → ''Y''이고 ''YZ'' → ''W''이면, ''XZ'' → ''W''이다.)
'''합성''' (Composition): 만약 ''X'' → ''Y''이고 ''Z'' → ''W''이면, ''XZ'' → ''YW''이다.^[6]

4. 2. 추가 규칙 (보조 규칙)

암스트롱의 공리로부터 다음과 같은 부수적인 함수 종속 규칙들을 유도할 수 있다. 이 규칙들은 데이터베이스 정규화 과정 등에서 활용된다.^[3]^[7] 릴레이션 R에 대해 X, Y, Z, W는 임의의 애트리뷰트(속성) 집합을 나타낸다.

'''합집합'''(Union) / '''결합'''(Composition): ''X'' → ''Y''이고 ''X'' → ''Z''이면, ''X'' → ''YZ''이다.
'''분해'''(Decomposition): ''X'' → ''YZ''이면, ''X'' → ''Y''이고 ''X'' → ''Z''이다.
합집합/결합 규칙과 분해 규칙은 ''X'' → ''YZ'' 와 (''X'' → ''Y'' 이고 ''X'' → ''Z'') 가 서로 동치임을 보여준다.^[3]^[7]
'''유사 이행성'''(Pseudotransitivity) / '''가전이성'''(Pseudotransitivity): ''X'' → ''Y''이고 ''YW'' → ''Z''이면, ''XW'' → ''Z''이다.^[3] (다른 표현: ''X'' → ''Y''이고 ''YZ'' → ''W''이면, ''XZ'' → ''W''이다.)
'''합성'''(Composition): ''X'' → ''Y''이고 ''Z'' → ''W''이면, ''XZ'' → ''YW''이다.^[6]

5. 함수 종속성의 폐포

관계 ''R''의 애트리뷰트 집합 ''X'', ''Y'', ''Z''에 대해, 함수 종속성의 여러 속성을 유도할 수 있다. 이 중 가장 중요한 것들은 일반적으로 암스트롱의 공리라고 불리며, 다음과 같다.^[3]

'''반사율'''(Reflexivity^eng): ''Y''가 ''X''의 부분 집합이면, ''X'' → ''Y''
'''증대'''(Augmentation^eng): ''X'' → ''Y''이면, ''XZ'' → ''YZ''
'''전이성'''(Transitivity^eng): ''X'' → ''Y''이고 ''Y'' → ''Z''이면, ''X'' → ''Z''

이 세 가지 규칙은 함수 종속성으로부터 다른 함수 종속성을 논리적으로 추론하는 데 사용되는 기본적인 추론 규칙이다. 특히 증대와 전이성은 새로운 함수 종속성을 유도하는 핵심 공리 역할을 한다.^[4] 반사율은 모든 애트리뷰트 집합이 자신의 부분집합을 함수적으로 결정한다는 자명한 사실을 나타낸다.

\vdash X \rightarrow \varnothing

X \rightarrow Y \vdash XZ \rightarrow YZ

X \rightarrow Y, Y \rightarrow Z \vdash X \rightarrow Z

.

이 규칙들은 함수 종속성에 대한 타당하고 완전한 공리화를 제공하며, 유한한 수의 규칙으로 이루어져 있다.^[5]^[4]

암스트롱의 공리를 바탕으로 다음과 같은 추가 규칙들을 유도할 수 있다.

'''가전이성'''(Pseudotransitivity^eng): ''X'' → ''Y''이고 ''YW'' → ''Z''이면, ''XW'' → ''Z''^[3]
'''합성'''(Composition^eng): ''X'' → ''Y''이고 ''Z'' → ''W''이면, ''XZ'' → ''YW''^[6]
'''결합'''(Union^eng) 및 '''분해'''(Decomposition^eng): ''X'' → ''Y''이고 ''X'' → ''Z''인 것은 ''X'' → ''YZ''인 것과 필요충분조건이다.^[3]^[7]

이러한 공리와 규칙들은 주어진 함수 종속성 집합으로부터 모든 논리적 결과를 추론하는, 즉 함수 종속성 집합의 폐포(

F

⁺)를 구하는 이론적 기초를 제공한다. 더 나아가, 특정 애트리뷰트 집합이 결정하는 모든 애트리뷰트 집합, 즉 애트리뷰트 집합의 폐포(

X

⁺)를 계산하는 데에도 핵심적으로 사용된다. 이 폐포 개념은 데이터베이스 정규화 과정에서 필수적이다.

5. 1. 함수 종속성 집합의 폐포

관계

R

과

R

에 적용되는 함수 종속성(FD) 집합

F

가 주어졌을 때,

F

로부터 논리적으로 추론될 수 있는 모든 함수 종속성들의 집합을

F

의 폐포(closure)라고 하며,

F

⁺로 표기한다.^[8] 즉,

F

⁺는

F

에 속한 함수 종속성들과 이들로부터 암스트롱의 공리 (반사율, 증대, 전이성 등)와 같은 추론 규칙들을 통해 유도될 수 있는 모든 함수 종속성들을 포함하는 가장 작은 집합이다.^[3]^[4]^[5] 폐포를 구하는 것은 데이터베이스 정규화 과정 등에서 중요한 역할을 한다.

5. 2. 애트리뷰트 집합의 폐포

주어진 관계 ''R''과 ''R''에 적용되는 함수 종속(FD)의 집합 ''F''가 있을 때, ''F''로부터 논리적으로 유도될 수 있는 모든 함수 종속의 집합을 ''F''의 폐포(closure)라 하며 ''F''⁺로 표기한다.^[8]

특정 애트리뷰트 집합 ''X''에 대해, ''F''⁺를 사용하여 ''X''에 의해 함수적으로 결정되는 모든 애트리뷰트의 집합을 ''X''의 폐포라 하며 ''X''⁺로 표기한다. 즉, ''X''⁺는 ''X''로부터 함수 종속 관계에 있는 모든 애트리뷰트들의 집합이다. 애트리뷰트 집합의 폐포는 암스트롱의 공리(반사율, 증대, 전이성)를 반복적으로 적용하여 계산할 수 있다.

예를 들어, 어떤 관계에서 다음과 같은 함수 종속(FD)들이 성립한다고 가정해보자.

1. ''A'' → ''B''

2. ''B'' → ''C''

3. ''AB'' → ''D''

이때 애트리뷰트 A의 폐포 A⁺를 계산하는 과정은 다음과 같다.

1. 초기 상태: A⁺ = {A} (암스트롱의 공리의 반사율에 의해 모든 애트리뷰트는 자기 자신을 함수적으로 결정한다).

2. FD 1 적용: ''A'' → ''B'' 이고 A가 A⁺에 있으므로, B를 A⁺에 추가한다. A⁺ = {A, B}.

3. FD 2 적용: ''B'' → ''C'' 이고 B가 A⁺에 있으므로, C를 A⁺에 추가한다. (암스트롱의 공리의 전이성에 의해 A → C가 성립). A⁺ = {A, B, C}.

4. FD 3 적용: ''AB'' → ''D'' 이고 A와 B가 모두 A⁺에 있으므로, D를 A⁺에 추가한다. (A → AB가 성립하므로, 전이성에 의해 A → D가 성립). A⁺ = {A, B, C, D}.

모든 함수 종속을 고려한 후 더 이상 새로운 애트리뷰트가 A⁺에 추가되지 않으면 계산이 완료된다. 따라서 최종적으로 A⁺ = {A, B, C, D}이다. 이 경우 A⁺가 관계의 모든 애트리뷰트(A, B, C, D)를 포함하므로, 애트리뷰트 A는 이 관계의 슈퍼키가 된다.

6. 커버와 동등성

관계 $R$ 에 적용되는 함수 종속성(FD) 집합 $F$ 가 주어졌을 때, $F$ 로부터 논리적으로 추론될 수 있는 모든 함수 종속성의 집합을 $F$ 의 클로저( $F$ ⁺로 표시)라고 한다.^[8] 이 클로저는 주어진 함수 종속성 집합이 어떤 정보를 함의하는지를 나타낸다.

함수 종속성 집합의 클로저는 암스트롱의 공리와 같은 추론 규칙들을 통해 체계적으로 구할 수 있다.^[3]^[4] 암스트롱의 공리는 함수 종속성이 가지는 기본적인 성질을 나타내는 세 가지 규칙, 즉 반사율, 증대, 전이성으로 구성된다.^[3] 이러한 규칙들을 이용하면 주어진 함수 종속성 집합으로부터 새로운 함수 종속성을 유도하여 클로저를 결정할 수 있다.

함수 종속성 집합의 클로저 개념은 두 함수 종속성 집합이 실질적으로 같은 의미를 가지는지(동등성)를 판단하거나, 한 집합이 다른 집합의 정보를 완전히 포함하는지(커버)를 정의하는 데 중요한 기초가 된다.

6. 1. 커버

정의: 함수 종속성 집합

F

가

G

의 모든 함수 종속성을

F

로부터 추론할 수 있다면,

F

는

G

를 덮는다고 한다. 즉,

G

⁺ ⊆

F

⁺이면

F

는

G

를 덮는다.

모든 함수 종속성 집합은 정규 덮개를 가진다.

6. 2. 동등성

스키마 ''R''에 대한 두 개의 함수 종속 집합 ''F''와 ''G''가 있을 때, 두 집합의 클로저가 서로 같다면, 즉 ''F''⁺ = ''G''⁺ 이면, 이 두 집합은 동등하다고 한다. 이는 ''F'' ≡ ''G''와 같이 표기한다.

만약 ''F''와 ''G''가 동등하다면 (''F'' ≡ ''G''), ''F''는 ''G''의 커버(cover)가 되고, 반대로 ''G'' 역시 ''F''의 커버가 된다. 따라서 동등한 함수 종속 집합들은 서로를 커버한다고 말할 수 있다.

6. 3. 중복되지 않는 커버

FD(함수 종속) 집합

F

가 중복되지 않는다는 것은

F

의 어떤 진부분집합

F'

도

F

와 동등(

F' \equiv F

)하지 않다는 것을 의미한다. 만약 이러한

F'

이 존재한다면,

F

는 중복된다고 한다.

어떤 함수 종속성 집합

F

가 다른 집합

G

의 중복되지 않는 커버가 되려면, 다음 두 조건을 만족해야 한다.

$F$ 는 $G$ 의 커버이다. 즉, $F$ 와 $G$ 는 동등하다 ( $F \equiv G$ ).
$F$ 는 중복되지 않는다.

중복되지 않음을 나타내는 또 다른 특징은 다음과 같다.

F

에 속하는 어떤 FD ''X'' → ''Y''에 대해서도,

F

에서 해당 FD를 제외한 집합

F

- {''X'' → ''Y''}이 ''X'' → ''Y''를 논리적으로 함의하지 않는 경우(

F

- {''X'' → ''Y''}

\not\models

''X'' → ''Y''),

F

는 중복되지 않는다. 반대로, 만약

F

에 속하는 어떤 FD ''X'' → ''Y''에 대해

F

- {''X'' → ''Y''}

\models

''X'' → ''Y''가 성립한다면, 해당 FD ''X'' → ''Y''는

F

내에서 중복된다고 한다.

7. 축약 불가의 함수 종속 집합

어떤 함수 종속 집합 S가 다음 세 가지 조건을 만족하면 축약 불가(irreducible) 또는 기약 집합(canonical cover)이라고 한다.^[10] 이는 함수 종속 집합을 더 이상 간단하게 표현할 수 없는 최소한의 형태로 나타내는 것을 의미한다.

# S에 속한 각 함수 종속의 오른쪽 부분(종속항)은 반드시 단 하나의 애트리뷰트만을 포함해야 한다.

# S에 속한 각 함수 종속의 왼쪽 부분(결정항)은 더 이상 축약될 수 없어야 한다. 즉, 왼쪽 부분의 애트리뷰트 집합에서 어느 하나의 애트리뷰트라도 제거하면 원래의 함수 종속 집합 S가 가진 정보가 손실된다.

# S에 속한 함수 종속 중에서 어느 하나라도 제거하면 원래의 함수 종속 집합 S가 가진 정보가 손실된다.

이러한 세 가지 조건을 만족하는 함수 종속 집합 S를 '표준(canonical)' 또는 '최소(minimal)' 집합이라고도 부른다.

주어진 함수 종속 집합 S'와 논리적으로 동등하면서 축약 불가 조건을 만족하는 함수 종속 집합 S를 찾는 과정을 최소 커버(minimal cover)를 찾는다고 한다. 최소 커버를 찾는 문제는 다항 시간 내에 해결할 수 있는 문제이다.^[10]

8. 정규화에의 응용

함수 종속성을 찾아내는 것은 관계형 모델 기반의 데이터베이스를 설계하거나, 데이터베이스 정규화 또는 데이터베이스 비정규화를 수행할 때 매우 중요한 과정 중 하나이다. 함수 종속성은 애트리뷰트의 도메인과 함께, 사용자 요구사항에 맞지 않는 데이터를 가능한 한 많이 제거하기 위한 제약을 만드는 데 활용된다.

예를 들어, 차량과 엔진 배기량을 관리하는 시스템을 설계한다고 가정해보자. 각 차량에는 고유한 차량 식별 번호(VIN)가 부여된다. 이때 "VIN → 배기량"이라는 함수 종속 관계가 성립한다고 표현할 수 있다. 왜냐하면 특정 차량(VIN)에는 하나의 엔진 배기량만 연결되는 것이 일반적이기 때문이다. (이 예제에서는 차량에 엔진이 하나만 있다고 가정한다.) 반대로, "배기량 → VIN"이라고 적는 것은 일반적으로 올바르지 않다. 같은 배기량을 가진 여러 차량이 존재할 수 있기 때문이다.

이처럼 함수 종속성은 특정 애트리뷰트(예: 배기량)가 후보 키(예: VIN)와 함께 하나의 릴레이션 안에 포함될 수 있는지 판단하는 근거를 제공한다. 그러나 이러한 배치가 항상 적절한 것은 아니다. 예를 들어, 함수 종속성이 이행적 종속성의 결과로 나타날 수도 있다.

VIN → 차량모델

차량모델 → 차량배기량

위와 같은 경우, VIN은 차량모델을 함수적으로 결정하고, 차량모델은 다시 차량배기량을 함수적으로 결정한다. 이러한 이행적 종속성은 정규화된 관계 설계를 방해할 수 있다.^[11] 따라서 함수 종속성을 정확히 파악하고 분석하는 것은 올바른 데이터베이스 구조를 설계하고 정규화를 진행하는 데 필수적이다.

8. 1. 히스의 정리 (Heath's theorem)

함수 종속성은 데이터베이스 이론에서 중요한 속성을 가지는데, 이는 '히스의 정리(Heath's theorem)'라고 불리는 초기 결과 중 하나로 설명될 수 있다.^[9] 이 정리는 속성 집합 ''U''를 가진 관계 ''R''이 있고, 이 관계 ''R''이 함수 종속성 ''X'' → ''Y''를 만족할 때 적용된다.

히스 정리에 따르면, 이러한 관계 ''R''은 두 개의 작은 관계로 무손실 분해될 수 있다. 즉,

R=\Pi_{XY}(R)\bowtie\Pi_{XZ}(R)

가 성립하며, 여기서 ''Z''는 ''U''에서 ''X''와 ''Y''를 제외한 나머지 속성들(''Z'' = ''U'' − ''XY'')을 의미한다. 직관적으로 설명하면, 함수 종속성 ''X'' → ''Y''가 성립하면, 관계 ''R''을 속성 ''X''를 기준으로 두 개의 관계, 즉 ''X''와 ''Y'' 속성만 가진 테이블(

\Pi_{XY}(R)

)과 ''X''와 나머지 속성 ''Z''를 가진 테이블(

\Pi_{XZ}(R)

)로 안전하게 나눌 수 있다. 이 두 테이블을 다시 조인하면 원래의 데이터 손실 없이 복원할 수 있다는 것이 보장된다.

이 분해 방식은 실용적인 이점을 가진다. 원래의 큰 관계 ''R''에서는 특정 ''X'' 값에 대해 ''Y'' 값이 여러 번 반복될 수 있지만, 분해된 테이블

\Pi_{XY}(R)

에서는 ''X'' 값이 키 역할을 하므로 ''Y'' 값이 중복되지 않는다. 이는 마치 ''X''를 키로 사용하는 ''Y'' 값에 대한 조회 테이블처럼 작동한다. 따라서 데이터를 업데이트할 때, 각 ''X'' 값에 해당하는 ''Y'' 값을 단 한 곳에서만 수정하면 되므로 업데이트 이상을 방지하고 데이터 일관성을 유지하기 쉽다. 특히 데이터 변경이 잦은 OLTP(온라인 트랜잭션 처리) 환경에서는 이러한 데이터 중복 제거가 매우 유리하다. 반면, 주로 조회 위주인 OLAP(온라인 분석 처리) 환경에서는 그 중요성이 상대적으로 덜할 수 있다.

또한, 히스 정리에 따른 분해 결과, 테이블

\Pi_{XZ}(R)

에서 속성 ''X''는 테이블

\Pi_{XY}(R)

을 참조하는 외래 키 역할을 하게 된다.

그러나 함수 종속성을 포함 종속성과 혼동해서는 안 된다. 포함 종속성은 주로 외래 키 제약을 정의하는 데 사용되며, 두 개 이상의 관계 스키마 간의 제약을 나타낸다. 반면, 함수 종속성은 단일 관계 내의 속성들 간의 제약을 나타낸다. 또한, 함수 종속성은 동등성 생성 종속성이고 포함 종속성은 튜플 생성 종속성으로, 종속성의 분류에서도 서로 다른 범주에 속한다. 관계 스키마를 정규화(분해)한 후 테이블 간의 참조 무결성을 보장하기 위해서는 포함 종속성이라는 별도의 개념이 필요하다. 히스 정리에 따른 분해만으로는

\Pi_{XZ}(R)

테이블에

\Pi_{XY}(R)

테이블에 존재하지 않는 ''X'' 값을 가진 튜플이 삽입되는 것을 막지 못한다.

8. 2. 정규형

정규형은 테이블의 "우수성"을 결정하는 데이터베이스 정규화 수준이다. 일반적으로 제3 정규형은 관계형 데이터베이스의 "좋은" 표준으로 간주된다.

정규화는 데이터베이스를 갱신, 삽입, 삭제 시 발생할 수 있는 이상 현상으로부터 자유롭게 하는 것을 목표로 한다. 또한, 새로운 값이 관계에 추가될 때 데이터베이스에 미치는 영향을 최소화하여, 데이터베이스를 사용하는 애플리케이션에 미치는 영향도 최소화하는 데 목적이 있다.

참조

_[1] 서적 Information Modeling and Relational Databases https://books.google[...] Morgan Kaufmann
_[2] 서적 Database Design and Relational Theory: Normal Forms and All That Jazz https://books.google[...] O'Reilly Media, Inc.
_[3] 서적 Database System Concepts McGraw-Hill
_[4] 간행물 Fundamentals of dependency theory http://www.cs.rice.e[...] Computer Science Press, Rockville, MD
_[5] 서적 Foundations of Databases https://archive.org/[...] Addison-Wesley
_[6] 서적 Database Systems: Concepts, Design & Applications https://books.google[...] Pearson Education India
_[7] 서적 Database systems: the complete book Pearson Prentice Hall
_[8] 학술지 An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema https://academic.oup[...] 1996-02-01
_[9] 서적 Proceedings of the 1971 ACM SIGFIDET (now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '71
_[10] 학술지 Minimum covers in the relational database model
_[11] 서적 데이터베이스 시스템 정익사 2005-08-15

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com