후보 키

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

1. 개요
2. 후보 키의 정의
- 2.1. 예시
3. 후보 키 결정
- 3.1. 후보 키 계산 알고리즘
4. 한국 데이터베이스 환경에서의 후보 키
참조

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''의 유효한 값이라고 가정한다.

''r1''
A	B	C	D
a1	b1	c1	d1
a1	b2	c2	d1
a2	b1	c2	d1

''r2''
A	B	C	D
a1	b1	c1	d1
a1	b2	c2	d1
a1	b1	c2	d2

''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. 후보 키 결정

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

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

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

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

3. 1. 후보 키 계산 알고리즘

함수 종속성 집합으로부터 모든 후보 키 집합을 계산할 수 있다. 이를 위해 속성 집합

\alpha

에 대한 속성 폐포

\alpha^+

를 정의해야 하는데, 집합

\alpha^+

는

\alpha

에 의해 함수적으로 함축되는 모든 속성을 포함한다.

단일 후보 키를 찾는 것은 매우 간단하다. 속성 집합

\alpha

로 시작하여 각 속성을 차례로 제거하며, 속성을 제거한 후에도 속성 폐포가 동일하게 유지되면 이 속성은 불필요하므로 영구적으로 제거할 수 있다. 결과를

\text{minimize}(\alpha)

라고 부르며, 만약

\alpha

가 모든 속성의 집합이라면,

\text{minimize}(\alpha)

는 후보 키이다.

이 절차를 통해 모든 후보 키를 찾기 위해서는 속성을 제거하는 모든 가능한 순서를 시도해 보아야 한다. 그러나 속성의 순열(

n!

)은 부분 집합(

2^n

)보다 훨씬 많다. 즉, 많은 속성 순서가 동일한 후보 키로 이어진다.

후보 키 계산을 위한 효율적인 알고리즘에는 근본적인 어려움이 있는데, 특정 집합의 함수 종속성은 지수적으로 많은 후보 키로 이어질 수 있다는 점이다. 예를 들어

2\cdot n

개의 함수 종속성

\{A_i \rightarrow B_i : i\in\{1,\dots,n\}\} \cup \{B_i \rightarrow A_i : i\in\{1,\dots,n\}\}

는

2^n

개의 후보 키

\{A_1, B_1\} \times \dots \times \{A_n, B_n\}

를 생성한다. 즉, 기대할 수 있는 최선은 후보 키의 수에 따라 효율적인 알고리즘이다.

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

```

'''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

와 함수 종속성

\alpha \rightarrow \beta

가 주어지면, 함수 종속성의 역을 적용하여 집합

\alpha \cup (K_i \setminus \beta)

를 생성하는 것이다. 이 집합은 키이지만, 이미 알려진 다른 후보 키에 의해 포함될 수 있다. (알고리즘은 'found' 변수를 사용하여 이 경우를 확인한다.) 그렇지 않은 경우, 새로운 키를 최소화하면 새로운 후보 키가 생성된다. 핵심적인 통찰력은 모든 후보 키가 이런 방식으로 생성될 수 있다는 것이다.

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

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

참조

_[1] 웹사이트 Codd's First Relational Papers: A Critical Analysis https://www.dcs.warw[...] 2015
_[2] 웹사이트 database - Can a relation have Candidate Keys with different lengths? https://stackoverflo[...] 2023-03-23
_[3] 학술지 An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema https://academic.oup[...] 1996-02-01
_[4] 학술지 Candidate keys for relations 1978-October

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

문의하기 : help@durumis.com