候補キー

リレーショナル データベースの候補キー、または単にキーとは、各行に一意の値の組み合わせを持つ 列のセットであり、列を削除すると値の組み合わせが重複する可能性があるという追加の制約があります。

候補キーは最小のスーパーキーです^[1]。 つまり、より小さいスーパーキーを含まないスーパーキーです。したがって、リレーションには複数の候補キーがあり、それぞれに異なる数の属性があります^{[2] 。}

特定の候補キーは、主キー、二次キー、代替キーと呼ばれることもあります。候補キーの列はプライム属性^[3]と呼ばれ、どの候補キーにも出現しない列は非プライム属性と呼ばれます。

NULL 値のないすべてのリレーションには、少なくとも 1 つの候補キーがあります。重複する行は存在しないため、すべての列のセットがスーパーキーであり、それが最小でない場合は、そのサブセットが最小になります。

候補キーから関係内のすべての属性への 機能的依存関係があります。

リレーションのスーパーキーは、行を識別できるすべての可能な方法です。候補キーは各スーパーキーの最小のサブセットであり、データベース スキーマの設計にとって重要な概念です。

候補キーの定義は、次の（抽象的な）例で説明できます。属性（A、B、C、D ）を持つ関係変数（ relvar）R を考えます。この属性には、次の 2 つの有効な値r1とr2のみが含まれます。

ここで、r2 は最後のタプルの A値とD値のみがr1と異なります。

r1の場合、次のセットには一意性プロパティがあります。つまり、セット内に同じ属性値を持つインスタンス内に 2 つの異なるタプルは存在しません。

{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}

relvar のスーパーキーは、その relvar のすべての有効な値に対して一意性プロパティを持つ属性のセットであり、 r1とr2 はRが取ることができるすべての有効な値であると想定しているため、 2 つのリストの共通部分を取得することで 、 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}

これらは確かに relvar Rの候補キーです。

ある属性セットが候補キーであるかどうかを判断するには、relvar に割り当てられる可能性のあるすべての関係を考慮する必要があります。たとえば、 r1だけを考慮した場合、{A,B} が候補キーであると結論付けますが、これは誤りです。ただし、そのような関係から、あるセットは一意性プロパティを持たないため、候補キーではないと結論付けることができる場合があります(例: r1の場合、{A,D} )。一意性プロパティを持つセットの適切なサブセットの存在は、一般に、スーパーセットが候補キーではないという証拠として使用できないことに注意してください。特に、空の関係の場合、空のセットを含め、見出しのすべてのサブセットに一意性プロパティがあることに注意してください。

すべての候補キーの集合は、例えば関数従属性の集合から計算できます。このためには、属性集合の属性閉包を定義する必要があります。集合には、関数的に によって暗示されるすべての属性が含まれます。 ${\displaystyle \alpha^{+}}$${\displaystyle \alpha}$${\displaystyle \alpha^{+}}$${\displaystyle \alpha}$

候補キーを 1 つだけ見つけるのは非常に簡単です。属性のセットから始めて、各属性を順に削除していきます。属性を削除した後も属性の閉包が同じままであれば、この属性は不要であり、永久に削除できます。結果を と呼びます。 がすべての属性のセットである場合、 は候補キーです。 ${\displaystyle \alpha}$${\displaystyle {\text{最小化}}(\alpha )}$${\displaystyle \alpha}$${\displaystyle {\text{最小化}}(\alpha )}$

実際には、属性を削除するすべての可能な順序を試すだけで、この手順ですべての候補キーを検出できます。ただし、属性の順列( )はサブセット( ) よりもはるかに多くあります。つまり、多くの属性順序で同じ候補キーが導き出されることになります。 ${\displaystyle n!}$${\displaystyle 2^{n}}$

候補キーの計算のための効率的なアルゴリズムには、根本的な難しさがあります。特定の機能的依存関係のセットは、指数関数的に多くの候補キーにつながります。候補キーを 生成する機能的依存関係 を考えてみましょう。つまり、期待できる最良の方法は、候補キーの数に関して効率的なアルゴリズムです。 ${\displaystyle 2\cdot n}$${\displaystyle \{A_{i}\rightarrow B_{i}:i\in \{1,\dots ,n\}\}\cup \{B_{i}\rightarrow A_{i}:i\in \{1,\dots ,n\}\}}$${\displaystyle 2^{n}}$${\displaystyle \{A_{1},B_{1}\}\times \dots \times \{A_{n},B_{n}\}}$

以下のアルゴリズムは、候補キーの数と関数の依存関係に対して多項式時間で実行されます。^[4]

関数find_candidate_keys(A, F)
    /* A はすべての属性の集合であり、F は機能的依存関係の集合です */
    K[0] := 最小化(A);
    n := 1; /* これまでにわかっているキーの数 */
    i := 0; /* 現在処理されているキー */
    i < nで
        あるとき、各α → β ∈ Fに対して
            /* 以前の既知のキーと現在の FD から新しい潜在的なキーを構築します */
            S := α ∪ (K[i] − β);
            /* 新しい潜在的キーが既知のキーの一部であるかどうかを検索します */
            見つかりました := false;
            j := 0 から n-1の場合、 K[j] ⊆ Sであればfound := true になります
                。
            /* そうでない場合は追加します */
             見つからない場合は
                K[n] := 最小化(S);
                n := n + 1;
        私 := 私 + 1
    Kを
返す

このアルゴリズムの背後にある考え方は、候補キー と関数従属性が与えられた場合、関数従属性を逆に適用すると 、これもキーであるセットが生成されるというものです。ただし、これは他の既知の候補キーによってカバーされる可能性があります。(アルゴリズムは、このケースを 'found' 変数を使用してチェックします。) そうでない場合は、新しいキーを最小化すると、新しい候補キーが生成されます。重要な洞察は、すべての候補キーがこのように作成できるということです。 ${\displaystyle K_{i}}$${\displaystyle \alpha \rightarrow \beta }$${\displaystyle \alpha \cup (K_{i}\setminus \beta )}$

• 代替キー、関係の候補キーの中で主キーとして選択されていないキー
• 複合キー
• データベースの正規化
• 主キー
• リレーショナルデータベース
• スーパーキー
• プライム含意はブール論理における候補キーに対応する概念である。

• Date, Christopher (2003)。「5: 整合性」。データベース システム入門。Addison-Wesley。pp. 268–276。ISBN 978-0-321-18956-1。

• リレーショナル データベース管理システム - データベース設計 - 参照用語 - キー: RDBMS (リレーショナル データベース管理システム) のさまざまな種類のキーの概要。