후보 키

1. 개요

후보 키는 관계형 데이터베이스에서 릴레이션의 각 튜플을 고유하게 식별하는 데 사용되는 속성 또는 속성 집합이다. 슈퍼키의 진부분 집합으로, 진부분 집합이 고유성을 유지하지 못하는 속성 집합이다. 후보 키는 함수 종속성을 이용하여 계산할 수 있으며, 효율적인 후보 키 계산 알고리즘이 존재한다.

2. 후보 키의 정의

관계 변수 R의 속성 집합이 있을 때, 이 속성 집합이 튜플을 고유하게 식별할 수 있고, 그 부분 집합은 고유하게 식별할 수 없을 때 (최소성) 후보 키라고 한다.

다음은 후보키를 설명하기 위한 예시이다. 속성(A, B, C, D)을 가진 관계 변수 R이 있고, 두개의 유효한 값 r1과 r2만 있다고 가정한다. 여기서 r2는 마지막 튜플의 A와 D 값에서만 r1과 다르다.

r1의 경우, {A,B}, {A,C}, {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D} 집합은 고유성 속성을 갖는다. 즉, 인스턴스 내에 집합 내의 동일한 속성 값을 가진 두 개의 서로 다른 튜플이 없다. r2의 경우, {B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D} 집합에 대해 고유성 속성이 유지된다.

관계 변수의 슈퍼키는 해당 관계 변수의 모든 유효 값에 대해 고유성 속성을 갖는 속성의 집합이므로, r1과 r2가 R이 가질 수 있는 모든 유효 값이라고 가정하면, 두 목록의 교집합({B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D})을 통해 R의 슈퍼키 집합을 결정할 수 있다.

마지막으로, 목록에 진부분 집합이 없는 집합({B,C}, {A,B,D}, {A,C,D})을 선택해야 하는데, 이것들이 실제로 관계 변수 R의 후보 키이다.

특정 속성 집합이 후보 키인지 여부를 결정하려면 관계 변수에 할당될 수 있는 모든 관계를 고려해야 한다. 예를 들어, r1만 고려했다면 {A,B}가 후보 키라고 결론을 내렸을 텐데, 이는 잘못된 것이다. 그러나 그러한 관계에서 특정 집합이 후보 키가 아님을 결론지을 수 있는데, 그 이유는 해당 집합이 고유성 속성을 갖지 않기 때문이다(예: r1의 {A,D}). 고유성 속성을 갖는 집합의 진부분 집합이 존재한다고 해서 일반적으로 상위 집합이 후보 키가 아니라는 증거로 사용될 수 없음에 유의해야 한다. 특히, 빈 관계의 경우, 머리글의 모든 부분 집합은 빈 집합을 포함하여 고유성 속성을 갖는다.

2.1. 예시

속성 (A, B, C, D)을 가진 관계 변수 R의 후보 키를 구하는 예시는 다음과 같다. r1과 r2는 R의 유효한 값이라고 가정한다.

r2는 마지막 튜플의 A와 D 값에서만 r1과 다르다.

r1에서 고유성 속성을 갖는 집합은 {A,B}, {A,C}, {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}이다. 즉, 인스턴스 내에 해당 집합의 속성 값을 동일하게 가진 튜플이 없다.

r2에서 고유성 속성이 유지되는 집합은 {B,C}, {B,D}, {C,D}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}이다.

관계 변수의 슈퍼키는 해당 관계 변수의 모든 유효 값에 대해 고유성 속성을 갖는 속성의 집합이다. 따라서 r1과 r2가 R이 가질 수 있는 모든 유효 값이라고 가정하면, 두 목록의 교집합을 통해 R의 슈퍼키 집합을 결정할 수 있다.
: {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}

마지막으로, 목록에서 진부분 집합이 없는 집합을 선택한다.
: {B,C}, {A,B,D}, {A,C,D}

위 집합들이 관계 변수 R의 후보 키이다.

특정 속성 집합이 후보 키인지 여부를 결정하려면 관계 변수에 할당될 수 있는 모든 관계를 고려해야 한다. 예를 들어, r1만 고려했다면 {A,B}가 후보 키라고 결론 내렸겠지만, 이는 잘못된 것이다. 그러나 특정 집합이 후보 키가 아님을 확인하는 것은 가능하다. 왜냐하면 해당 집합이 고유성 속성을 갖지 않기 때문이다(예: r1의 {A,D}). 고유성 속성을 갖는 집합의 진부분 집합이 존재한다고 해서 상위 집합이 후보 키가 아니라는 증거로 사용될 수 없다. 특히, 빈 관계의 경우, 머리글의 모든 부분 집합은 빈 집합을 포함하여 고유성 속성을 갖는다.

3. 후보 키 결정

함수 종속성 집합으로부터 모든 후보 키 집합을 계산할 수 있다. 이를 위해 속성 집합 $\backslash alpha$에 대한 속성 폐포 $\backslash alpha^+$를 정의해야 한다. $\backslash alpha^+$는 $\backslash alpha$에 의해 함수적으로 함축되는 모든 속성을 포함한다.

단일 후보 키는 속성 집합 $\backslash alpha$에서 시작하여 각 속성을 차례로 제거하는 방식으로 찾을 수 있다. 속성을 제거한 후에도 속성 폐포가 동일하게 유지되면, 그 속성은 불필요하므로 영구적으로 제거할 수 있다. 이 결과를 $\backslash text\{minimize\}(\backslash alpha)$라고 부른다. 만약 $\backslash alpha$가 모든 속성의 집합이라면, $\backslash text\{minimize\}(\backslash alpha)$는 후보 키가 된다.

모든 후보 키를 찾기 위해서는 속성을 제거하는 모든 가능한 순서를 시도해야 한다. 그러나 속성의 순열($n!$)은 부분 집합($2^n$)보다 훨씬 많으므로, 많은 속성 순서가 동일한 후보 키로 이어질 수 있다.

특정 집합의 함수 종속성은 지수적으로 많은 후보 키를 생성할 수 있기 때문에, 후보 키 계산을 위한 효율적인 알고리즘은 근본적인 어려움을 가진다.

3.1. 후보 키 계산 알고리즘

함수 종속성 집합으로부터 모든 후보 키 집합을 계산할 수 있다. 이를 위해 속성 집합 $\backslash alpha$에 대한 속성 폐포 $\backslash alpha^+$를 정의해야 하는데, 집합 $\backslash alpha^+$는 $\backslash alpha$에 의해 함수적으로 함축되는 모든 속성을 포함한다.

단일 후보 키를 찾는 것은 매우 간단하다. 속성 집합 $\backslash alpha$로 시작하여 각 속성을 차례로 제거하며, 속성을 제거한 후에도 속성 폐포가 동일하게 유지되면 이 속성은 불필요하므로 영구적으로 제거할 수 있다. 결과를 $\backslash text\{minimize\}(\backslash alpha)$라고 부르며, 만약 $\backslash alpha$가 모든 속성의 집합이라면, $\backslash text\{minimize\}(\backslash alpha)$는 후보 키이다.

이 절차를 통해 모든 후보 키를 찾기 위해서는 속성을 제거하는 모든 가능한 순서를 시도해 보아야 한다. 그러나 속성의 순열($n!$)은 부분 집합($2^n$)보다 훨씬 많다. 즉, 많은 속성 순서가 동일한 후보 키로 이어진다.

후보 키 계산을 위한 효율적인 알고리즘에는 근본적인 어려움이 있는데, 특정 집합의 함수 종속성은 지수적으로 많은 후보 키로 이어질 수 있다는 점이다. 예를 들어 $2\backslash cdot\; n$개의 함수 종속성 $\backslash \{A\_i\; \backslash rightarrow\; B\_i\; :\; i\backslash in\backslash \{1,\backslash dots,n\backslash \}\backslash \}\; \backslash cup\; \backslash \{B\_i\; \backslash rightarrow\; A\_i\; :\; i\backslash in\backslash \{1,\backslash dots,n\backslash \}\backslash \}$는 $2^n$개의 후보 키 $\backslash \{A\_1,\; B\_1\backslash \}\; \backslash times\; \backslash dots\; \backslash times\; \backslash \{A\_n,\; B\_n\backslash \}$를 생성한다. 즉, 기대할 수 있는 최선은 후보 키의 수에 따라 효율적인 알고리즘이다.

다음은 후보 키와 함수 종속성의 수에 대해 다항 시간 내에 실행되는 알고리즘이다:

```
function find_candidate_keys(A, F)
/* A는 모든 속성의 집합이고 F는 함수 종속성의 집합이다. */
K[0] := minimize(A);
n := 1; /* 지금까지 알려진 키의 수 */
i := 0; /* 현재 처리된 키 */
while i < n do
for each α → β ∈ F do
/* 이전 알려진 키와 현재 FD로부터 새로운 잠재적 키를 생성한다. */
S := α ∪ (K[i] − β);
/* 새로운 잠재적 키가 이미 알려진 키의 일부인지 검색한다. */
found := false;
for j := 0 to n-1 do
if K[j] ⊆ S then found := true;
/* 그렇지 않으면 추가한다. */
if not found then
K[n] := minimize(S);
n := n + 1;
i := i + 1
return K
```

이 알고리즘의 핵심 아이디어는 후보 키 $K\_i$와 함수 종속성 $\backslash alpha\; \backslash rightarrow\; \backslash beta$가 주어지면, 함수 종속성의 역을 적용하여 집합 $\backslash alpha\; \backslash cup\; (K\_i\; \backslash setminus\; \backslash beta)$를 생성하는 것이다. 이 집합은 키이지만, 이미 알려진 다른 후보 키에 의해 포함될 수 있다. (알고리즘은 'found' 변수를 사용하여 이 경우를 확인한다.) 그렇지 않은 경우, 새로운 키를 최소화하면 새로운 후보 키가 생성된다. 핵심적인 통찰력은 모든 후보 키가 이런 방식으로 생성될 수 있다는 것이다.

4. 한국 데이터베이스 환경에서의 후보 키

한국의 기업 및 공공기관에서 데이터베이스를 설계하고 운영할 때, 후보 키는 데이터 무결성을 보장하고 효율적인 데이터 관리를 위한 핵심 요소이다. 특히, 개인정보보호법 등 관련 법규 준수를 위해 후보 키를 신중하게 선정하고 관리해야 한다.