Kandidátský klíč - Candidate key

Kandidát klíč , nebo jednoduše klíč , z relační databáze je minimální superkey . Jinými slovy, je to jakákoli sada sloupců, která má jedinečnou kombinaci hodnot v každém řádku (což z něj dělá superklíč), s dodatečným omezením, že odebrání jakéhokoli sloupce by pravděpodobně vytvořilo duplicitní řádky (což z něj činí minimální superklíč).

Specifické kandidátské klíče se někdy nazývají primární klíče, sekundární klíče nebo alternativní klíče.

Sloupce v kandidátském klíči se nazývají primární atributy a sloupec, který se nevyskytuje v ŽÁDNÉM kandidátském klíči, se nazývá atribut , který není primární .

Každý vztah bez hodnot NULL bude mít alespoň jeden kandidátský klíč: Protože nemohou existovat duplicitní řádky, sada všech sloupců je superklíč, a pokud to není minimální, bude nějaká jeho podmnožina minimální.

Od kandidátského klíče existuje funkční závislost na všech atributech ve vztahu.

Kandidátské klíče relace všemi možnými způsoby, jak můžeme identifikovat řádek. Jako takové jsou důležitým konceptem pro návrh schématu databáze .

Příklad

Definici kandidátských klíčů lze ilustrovat na následujícím (abstraktním) příkladu. Zvažte relační proměnnou ( relvar ) R s atributy ( A , B , C , D ), která má pouze následující dvě zákonné hodnoty r1 a r2 :

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

Zde se r2 liší od r1 pouze v hodnotách A a D poslední n -tice.

Pro r1 mají následující sady vlastnost jedinečnosti, tj. V instanci neexistují dvě odlišné n -tice se stejnými hodnotami atributů v sadě:

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

Pro r2 platí vlastnost unikátnosti pro následující sady;

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

Vzhledem k tomu, že superklíče relvaru jsou ty sady atributů, které mají vlastnost jedinečnosti pro všechny zákonné hodnoty tohoto relvaru, a protože předpokládáme, že r1 a r2 jsou všechny zákonné hodnoty, které R může nabývat, můžeme určit množinu superklíčů R podle přičemž průsečík těchto dvou seznamů:

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

Nakonec musíme vybrat ty sady, pro které v seznamu neexistuje žádná správná podmnožina , což jsou v tomto případě:

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

Jsou to opravdu kandidátské klíče relvar R .

Musíme zvážit všechny vztahy, které by mohly být přiřazeny k relvar, abychom zjistili, zda je určitá sada atributů kandidátským klíčem. Pokud bychom například uvažovali pouze r1, pak bychom dospěli k závěru, že {A, B} je kandidátský klíč, což je nesprávné. Nicméně jsme může být schopen uzavřít z tohoto vztahu, že určitá sada je nejsou kandidáta na klíč, protože sada není jednoznačná (příklad {A, D} pro r1 ). Všimněte si toho, že existenci řádné podmnožiny množiny, která má vlastnost jedinečnosti, nelze obecně použít jako důkaz, že nadmnožina není kandidátským klíčem. Zejména si všimněte, že v případě prázdného vztahu má každá podmnožina nadpisu vlastnost jedinečnosti, včetně prázdné množiny.

Určení kandidátských klíčů

Množinu všech kandidátských klíčů lze vypočítat např. Ze sady funkčních závislostí . Za tímto účelem musíme definovat uzavření atributu pro sadu atributů . Sada obsahuje všechny atributy, které jsou funkčně implikovány . ${\ displaystyle \ alpha +}$ ${\ displaystyle \ alpha}$ ${\ displaystyle \ alpha ^{+}}$ ${\ displaystyle \ alpha}$

Najít jediný kandidátský klíč je celkem jednoduché. Začneme sadou atributů a pokusíme se postupně každý atribut odebrat. Pokud po odebrání atributu zůstane uzavření atributu stejné, pak tento atribut není nutný a můžeme jej trvale odstranit. Říkáme výsledku . Pokud je sada všech atributů, pak je kandidátský klíč. ${\ displaystyle \ alpha}$ ${\ displaystyle {\ text {minimal}} (\ alpha)}$ ${\ displaystyle \ alpha}$ ${\ displaystyle {\ text {minimal}} (\ alpha)}$

Ve skutečnosti můžeme pomocí tohoto postupu detekovat každý kandidátský klíč jednoduchým vyzkoušením každého možného pořadí odstraňování atributů. Existuje však mnohem více permutací atributů ( ) než podmnožin ( ). To znamená, že mnoho atributových objednávek povede ke stejnému kandidátskému klíči. ${\ displaystyle n!}$ ${\ displaystyle 2^{n}}$

Efektivní algoritmy pro výpočet kandidátských klíčů mají zásadní potíže: Některé sady funkčních závislostí vedou k exponenciálně mnoha kandidátským klíčům. Vezměme si funkční závislostí , která poskytuje kandidátní klíče: . To znamená, že to nejlepší, co můžeme očekávat, je algoritmus, který je účinný s ohledem na počet kandidátních klíčů. ${\ Displaystyle 2 \ cdot n}$ ${\ Displaystyle \ {A_ {i} \ rightarrow B_ {i}: i \ in \ {1, \ dots, n \} \} \ cup \ {B_ {i} \ rightarrow A_ {i}: i \ in \ {1, \ tečky, n \} \}}$ ${\ displaystyle 2^{n}}$ ${\ displaystyle \ {A_ {1}, B_ {1} \} \ times \ dots \ times \ {A_ {n}, B_ {n} \}}$

Následující algoritmus ve skutečnosti běží v polynomiálním čase v počtu kandidátských klíčů a funkčních závislostí:

function find_candidate_keys(A, F)
    /* A is the set of all attributes and F is the set of functional dependencies */
    K[0] := minimize(A);
    n := 1; /* Number of Keys known so far */
    i := 0; /* Currently processed key */
    while i < n do
        for each α → β ∈ F do
            /* Build a new potential key from the previous known key and the 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
    return K

Myšlenkou algoritmu je, že vzhledem k kandidátskému klíči a funkční závislosti získá zpětná aplikace funkční závislosti množinu , která je také klíčem. Může však být pokryto jinými již známými kandidátskými klíči. (Algoritmus tento případ kontroluje pomocí proměnné „nalezeno“.) Pokud ne, minimalizací nového klíče se získá nový kandidátský klíč. Klíčovým poznatkem je, že tímto způsobem lze vytvořit všechny kandidátské klíče. ${\ displaystyle K_ {i}}$ ${\ displaystyle \ alpha \ rightarrow \ beta}$ ${\ Displaystyle \ alpha \ cup (K_ {i} \ setminus \ beta)}$

Viz také

Alternativní klíč
Složený klíč
Normalizace databáze
Primární klíč
Relační databáze
Super klíč
Prime implicant je v booleovské logice odpovídající pojem kandidátského klíče

Reference

Datum, Christopher (2003). „5: Integrita“. Úvod do databázových systémů . Addison-Wesley. s. 268–276. ISBN 978-0-321-18956-1.

externí odkazy

Relational Database Management Systems - Database Design - Reference - Keys : Přehled různých typů klíčů v RDBMS (Relational Database Management System).

Languages

In other projects