후보 키

Candidate key

관계형 데이터베이스후보또는 단순한 는 최소의 슈퍼키다.[1] 즉, 열을 제거하면 중복 행이 생성될 수 있다는 추가적인 제약조건(최소 슈퍼키)과 함께 각 행에 고유한 값의 조합을 갖는 모든 열 집합이다.

특정 후보 키를 기본 키, 보조 키 또는 대체 키라고도 한다.

후보 키의 열은 prime attributes라고 하며,[2] 어떤 후보 키에서도 발생하지 않는 열을 non-prime attribute라고 한다.

NULL 값이 없는 모든 관계에는 최소한 하나의 후보 키가 있을 것이다: 중복 행이 있을 수 없기 때문에, 모든 열의 집합은 수퍼키이며, 그것이 최소가 아니라면, 그 중 일부 하위 집합은 최소가 될 것이다.

후보 키에서 관계 내의 모든 속성에 대한 기능적 의존성이 있다.

관계의 후보 열쇠는 우리가 열을 식별할 수 있는 모든 가능한 방법이다. 이와 같이 데이터베이스 스키마 설계에 중요한 개념이다.

후보 키의 정의는 다음과 같은 (추상) 예제로 설명할 수 있다. 다음 두 가지 법적r1, r2만 갖는 속성(A, B, C, D)을 갖는 관계 변수(relvar) 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의 경우, 다음 집합은 고유성 특성을 가지고 있다. 즉, 집합에 동일한 속성 값을 가진 인스턴스(instance)에 두 개의 구별되는 튜플이 없다.

{A,B}, {A,C}, {B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,C,D}, {A,B,C,D}, {A,B,C,D}, {A,C,D}, {A,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}, {A,B,C,D}, {A,B,C,D}, {A,C,D}, {A,D}

relvar의 superkeys는 해당 relvar의 모든 법적 값에 대한 고유성 특성을 가진 속성 집합이며, r1r2가 모두 R이 취할 수 있는 법적 값이라고 가정하기 때문에, 우리는 다음 두 목록의 교차점을 취함으로써 R의 superkeys 집합을 결정할 수 있다.

{B,C}, {A,B,C}, {A,B,D}, {A,C,D}, {B,C,D}, {A,B,C,D}, {A,B,C,D}, {A,C,D}

마지막으로 목록에 적절한 하위 집합이 없는 집합을 선택해야 하며, 이 경우 다음과 같다.

{B,C}, {A,B,D}, {A,C,D}

이것들은 정말로 렐바 R의 후보 키들이다.

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

후보 키 결정 중

모든 후보 키 집합은 예를 들어 기능 의존성 집합에서 계산할 수 있다. 이를 위해 속성 집합 에 대한 속성 폐쇄 + 을(를) 정의해야 한다 세트 + 은(는에 의해 기능적으로 함축된 모든 속성을 포함한다

단일 후보 키를 찾는 것은 꽤 간단하다. 먼저 개의 속성으로 시작하여 각 속성을 연속적으로 제거하려고 한다. 속성을 제거한 후에도 속성 폐쇄가 그대로 유지되면 이 속성은 필요하지 않으며 영구적으로 제거할 수 있다. 우리는 결과 () 이라고 부른다. (가) 모든 속성의 집합이라면 minimize}(\

사실 우리는 이 절차로 모든 후보 키를 탐지할 수 있다. 단지 속성 제거의 가능한 모든 순서를 시도함으로써 말이다. 그러나 하위 집합( 보다 속성 순열(! n이 더 많다. 즉, 많은 속성 주문이 동일한 후보 키로 이어질 것이다.

후보 키 계산을 위한 효율적인 알고리즘에는 근본적인 어려움이 있다. 특정 기능 의존성 집합은 기하급수적으로 많은 후보 키로 이어진다. Consider the functional dependencies which yields candidate keys:{ , × × × 즉, 후보 키 수와 관련하여 효율적인 알고리즘을 기대할 수 있는 것이 최선이다.

다음 알고리즘은 실제로 후보 키 수와 기능 의존성 수에서 다항식으로 실행된다.[3]

모든 특성의 기능 find_candidate_keys(A, F)/* 집합 및 기능적 의존성의 F집합/를 K[0]:)minimize(A), n:=1;키의/* 수 알려진 지금까지 나를:=0;는 동안 나는 < /* 현재 키*/가공, n각 α을 하→β ∈ F니 /*을 짓다 새로운 잠재적인 키를 통해 이전의 알려진 키와. 그 current FD */             S := α ∪ (K[i] − β);             /* Search whether the new potential key is part of the already known keys */              found := false;             for j := 0 to n-1 do if K[j] ⊆ S then found := true;             /* If not, add if              if not found then                 K[n] := minimize(S);                 n := n + 1; i := i + 1 리턴 K 

The idea behind the algorithm is that given a candidate key and a functional dependency , the reverse application of the functional dependency yields the set , which is a key, t그러나 이미 알려진 다른 후보 키에 의해 가려질 수 있다. (알고리즘은 '찾은' 변수를 사용하여 이 사례를 확인한다.) 그렇지 않은 경우 새 키를 최소화하면 새 후보 키가 생성된다. 모든 후보 키가 이런 식으로 만들어질 수 있다는 게 핵심 통찰이다.

참고 항목

참조

  1. ^ Date, Christopher (2015). "Codd's First Relational Papers: A Critical Analysis" (PDF). warwick.ac.uk. Retrieved 2020-01-04. Note that the extract allows a “relation” to have any number of primary keys, and moreover that such keys are allowed to be “redundant” (better: reducible). In other words, what the paper calls a primary key is what later (and better) became known as a superkey, and what the paper calls a nonredundant (better: irreducible) primary key is what later became known as a candidate key or (better) just a key.
  2. ^ Saiedian, H. (1996-02-01). "An Efficient Algorithm to Compute the Candidate Keys of a Relational Database Schema". The Computer Journal. 39 (2): 124–132. doi:10.1093/comjnl/39.2.124. ISSN 0010-4620.
  3. ^ L. Lucchesi, Cláudio; Osborn, Sylvia L. (October 1978). "Candidate keys for relations". Journal of Computer and System Sciences. 17 (2): 270–279. doi:10.1016/0022-0000(78)90009-0.

외부 링크