후보 키

관계형 데이터베이스의 후보 키 또는 단순한 키는 최소의 슈퍼키다.^[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의 모든 법적 값에 대한 고유성 특성을 가진 속성 집합이며, r1과 r2가 모두 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})이 없기 때문에 그러한 관계에서 특정 집합이 후보 키가 아니라는 결론을 내릴 수 있을 것이다. 고유성 특성을 가진 집합의 적절한 하위 집합의 존재는 일반적으로 상위 집합이 후보 키가 아니라는 증거로 사용될 수 없다는 점에 유의하십시오. 특히 빈 관계의 경우, 머리글의 모든 부분 집합은 빈 집합을 포함하여 고유한 속성을 가지고 있다는 점에 유의하십시오.

후보 키 결정 중

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

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

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

후보 키 계산을 위한 효율적인 알고리즘에는 근본적인 어려움이 있다. 특정 기능 의존성 집합은 기하급수적으로 많은 후보 키로 이어진다. Consider the $2\cdot n$ functional dependencies $\{A_{i}\rightarrow B_{i}:i\in \{1,\dots ,n\}\}\cup \{B_{i}\rightarrow A_{i}:i\in \{1,\dots ,n\}\}$ which yields $2^{n}$ candidate keys: $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ { $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ , $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ × $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ × $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ × $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ $\{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}$ ${\displaystyle \{A_{1},B_{1}\}\times \times \{A_{n},B_{n$ 즉, 후보 키 수와 관련하여 효율적인 알고리즘을 기대할 수 있는 것이 최선이다.

다음 알고리즘은 실제로 후보 키 수와 기능 의존성 수에서 다항식으로 실행된다.^[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 $K_{i}$ and a functional dependency $\alpha \rightarrow \beta$ , the reverse application of the functional dependency yields the set $\alpha \cup (K_{i}\setminus \beta )$ , which is a key, t그러나 이미 알려진 다른 후보 키에 의해 가려질 수 있다. (알고리즘은 '찾은' 변수를 사용하여 이 사례를 확인한다.) 그렇지 않은 경우 새 키를 최소화하면 새 후보 키가 생성된다. 모든 후보 키가 이런 식으로 만들어질 수 있다는 게 핵심 통찰이다.

참고 항목

참조

^ 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.
^ 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.
^ 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.

Date, Christopher (2003). "5: Integrity". An Introduction to Database Systems. Addison-Wesley. pp. 268–276. ISBN 978-0-321-18956-1.

외부 링크

관계형 데이터베이스 관리 시스템 - 데이터베이스 설계 - 참조 조건 - 키: RDBMS(Relative Database Management System)의 다양한 키 유형 개요.

[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.

[1]

[2]

[3]

v t 데이터베이스 관리 시스템
종류들	객체 지향 비교의 관계성 리스트를 작성하다 비교의 키-값 기둥 지향 리스트를 작성하다 문서 지향 와이드 컬럼 스토어 그래프 NoSQL NewSQL 인메모리 리스트를 작성하다 멀티 모델 비교의 구름
개념	데이터베이스 산성 암스트롱의 공리 Codd의 12가지 규칙 CAP 정리 CRUD Null 후보 키 외래키 슈퍼키 대리 키 유니크 키
물건들	관계 테이블 칼럼을 세우다 배를 젓다 보기 거래 트랜잭션 로그 트리거 색인 저장 프로시저 커서 칸막이
구성 요소들	동시성 제어 데이터 사전 JDBC XQJ ODBC 질의어 쿼리 최적화 도구 재쓰기 시스템 쿼리 질의 계획
기능들	관리 쿼리 최적화 복제 샤딩
관련 항목	데이터베이스 모델 데이터베이스 정규화 데이터베이스 저장소 분산 데이터베이스 연합 데이터베이스 시스템 참조 무결성 관계 대수 관계 미적분학 관계형 데이터베이스 관계형 모델 객체 관계 데이터베이스 거래처리
카테고리 개요 위키프로젝트

Search

후보 키

네임스페이스

더

목차

예

후보 키 결정 중

참고 항목

참조

외부 링크