Klíč kandidáta - Candidate key

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Klíč kandidáta“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Červen 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V relační model z databáze, a klíč kandidáta a vztah je minimální superklíč pro tento vztah; to je, a soubor atributů, které:

1. vztah nemá dva odlišné n-tice (tj. řádky nebo záznamy v běžném jazyce databáze) se stejnými hodnotami pro tyto atributy (což znamená, že sada atributů je superklíč)
2. tady není žádný správná podmnožina z těchto atributů, pro které platí (1) (což znamená, že množina je minimální).

Kandidátské klíče se také různě označují jako primární klíče, sekundární klíče nebo alternativní klíče.

Atributy složky se nazývají hlavní atributy. Naopak atribut, který se nevyskytuje v ŽÁDNÉM kandidátském klíči, se nazývá a atribut non-prime.

Vzhledem k tomu, že relace neobsahuje žádné duplicitní n-tice, je sada všech jejích atributů superklíč, pokud nejsou použity hodnoty NULL. Z toho vyplývá, že každá relace bude mít alespoň jeden kandidátský klíč.

Kandidátské klíče relace nám říkají všechny možné způsoby, jak můžeme identifikovat její n-tice. Jako takové jsou důležitým konceptem pro návrh databázové schéma.

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ě právní hodnoty R1 a r2:

Tady r2 se liší od R1 pouze v A a D hodnoty poslední n-tice.

Pro R1 následující sady mají vlastnost jedinečnosti, tj. v instanci nejsou žádné dvě rozdílné 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 vlastnost jedinečnosti platí pro následující sady;

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

Protože superklíče relvar jsou ty sady atributů, které mají vlastnost jedinečnosti Všechno legální hodnoty tohoto relvaru a protože to předpokládáme R1 a r2 jsou všechny legální hodnoty, které R můžeme vzít, můžeme určit sadu superklíčů R průnikem 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é neexistuje správná podmnožina v seznamu, což jsou v tomto případě:

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

Jedná se skutečně o kandidátské klíče relvar R.

Musíme zvážit Všechno vztahy, které lze přiřadit k relvar k určení, zda je určitá sada atributů kandidátským klíčem. Například kdybychom uvažovali pouze R1 pak bychom dospěli k závěru, že {A, B} je kandidátský klíč, což je nesprávné. My však mohl být schopen z takového vztahu usoudit, že určitá množina je ne kandidátský klíč, protože tato sada nemá vlastnost jedinečnosti (příklad {A, D} pro R1). Všimněte si, že existence správné podmnožiny sady, která má vlastnost jedinečnosti nemůže obecně se používá jako důkaz, že nadmnožina není kandidátským klíčem. Zejména si všimněte, že v případě prázdné relace má každá podmnožina nadpisu vlastnost jedinečnosti, včetně prázdné sady.

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

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

Najít jeden klíč kandidáta je docela jednoduché. Začneme sadou ${ displaystyle alpha}$ atributů a pokusit se postupně odstranit každý atribut. pokud po odstranění atributu zůstane uzávěr atributu stejný, pak tento atribut není nutný a můžeme jej trvale odstranit. ${ displaystyle { text {minimalizovat}} ( alpha)}$.Li ${ displaystyle alpha}$ je tedy soubor všech atributů ${ displaystyle { text {minimalizovat}} ( alpha)}$ je kandidátský klíč.

Ve skutečnosti můžeme tímto postupem detekovat každý klíč kandidáta jednoduše vyzkoušením všech možných pořadí odstraňování atributů. Je jich však mnohem více obměny atributů (${ displaystyle n!}$)než podmnožiny (${ displaystyle 2 ^ {n}}$To znamená, že mnoho objednávek atributů povede ke stejnému klíči kandidáta.

Efektivní algoritmy pro výpočet kandidátských klíčů mají zásadní problém: Některé sady funkčních závislostí vedou k exponenciálně mnoha kandidátským klíčům. ${ displaystyle 2 cdot n}$ funkční závislosti${ displaystyle {A_ {i} rightarrow B_ {i}: i in {1, dots, n } } cup {B_ {i} rightarrow A_ {i}: i in {1, tečky, n } }}$který přináší ${ displaystyle 2 ^ {n}}$ kandidátské klíče:${ displaystyle {A_ {1}, B_ {1} } krát tečky časy {A_ {n}, B_ {n} }}$To znamená, že to nejlepší, co můžeme očekávat, je algoritmus, který je efektivní s ohledem na počet kandidátských klíčů.

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í:^[1]

 funkce find_candidate_keys (A, F) / * A je množina všech atributů a F je množina funkčních závislostí * / K [0]: = minimalizovat (A); n: = 1; / * Počet dosud známých klíčů * / i: = 0; / * Aktuálně zpracovaný klíč * / while i 
Myšlenkou algoritmu je myšlenka, že byl dán kandidátský klíč ${ displaystyle K_ {i}}$a funkční závislost ${ displaystyle  alpha  rightarrow  beta}$, reverzní aplikace funkční závislosti poskytuje sadu ${ displaystyle  alpha  cup (K_ {i}  setminus  beta)}$, což je také klíč. Může to však být pokryto jinými již známými kandidátskými klíči. (Algoritmus tento případ zkontroluje pomocí proměnné „found“.) Pokud ne, pak minimalizací nového klíče získá nový kandidátský klíč. vhled je, že všechny klíče kandidátů lze vytvořit tímto způsobem.
Viz také
Alternativní klíč
Složený klíč
Normalizace databáze
Primární klíč
Relační databáze
Superklíč
Prime implicitně je odpovídající pojem kandidátského klíče v logická logika
Reference
^ L. Lucchesi, Cláudio; Osborn, Sylvia L. (říjen 1978). "Klíče kandidáta na vztahy". Journal of Computer and System Sciences. 17 (2): 270–279. doi:10.1016/0022-0000(78)90009-0.
Rande, Christophere (2003). „5: Integrita“. Úvod do databázových systémů. Addison-Wesley. 268–276. ISBN  978-0-321-18956-1.
externí odkazy
Relační systémy pro správu databází - Návrh databáze - Zadání - Klíče: Přehled různých typů klíčů v RDBMS (Relational Database Management System).