DBMS 中可能的超級鍵數量

---

在資料庫管理系統 (DBMS) 中，超級鍵是用於識別表中唯一記錄的重要概念。超級鍵是一組一個或多個屬性，可以唯一地識別表中的一條記錄。

在本文中，我們將探討資料庫中可能的超級鍵數量及其意義。

什麼是超級鍵？

超級鍵是表中的一組屬性，可以唯一地識別該表中的每一行。它與主鍵和候選鍵不同，因為只有最小的可能的超級鍵才能被選為主鍵或候選鍵。因此，主鍵或候選鍵是沒有不必要屬性的超級鍵。所有主鍵或候選鍵都是超級鍵，但並非所有超級鍵都是主鍵或候選鍵。表的定義規定所有行都是唯一的，因此所有屬性的集合本身就是一個超級鍵。

例如，如果我們有一個包含以下列的學生表：學生 ID、姓名和電子郵件。這裡，學生 ID 和姓名的組合可以形成一個超級鍵。此外，學生 ID、姓名和電子郵件也可以形成一個超級鍵。

我們將在這裡使用包含-排除的各種屬性。

計算 DBMS 中可能的超級鍵數量

示例-1

假設我們有一個具有屬性 {a1, a2, a3} 的關係 R，並且 a1 是候選鍵。那麼，a1 的任何超集都是超級鍵。因此，我們可以有四個可能的超級鍵：{a1, a1 a2, a1 a3, a1 a2 a3}。一般來說，如果我們有 'N' 個屬性和一個候選鍵，則可能的超級鍵數量為 2^(N – 1)。

示例-2

假設我們有一個具有屬性 {a1, a2, a3,…,an} 的關係 R。超級鍵的最大數量為 2^(n) – 1。要成為超級鍵，必須至少存在一個屬性；空集或沒有屬性的集合不能是超級鍵。

示例-3

假設我們有一個具有屬性 {a1, a2, a3,…, an} 的關係 R，並且候選鍵為“a1 a2 a3”。根據之前的公式，我們有三個屬性而不是一個。因此，這裡可能的超級鍵數量為 2^(N-3)。

示例-4

假設我們有一個具有屬性 {a1, a2, a3,…, an} 的關係 R，並且候選鍵為“a1”，“a2”。在這種情況下，我們有兩個不同的候選鍵，而不僅僅是一個。我們可以使用以下公式

可能的超級鍵

= (使用候選鍵 A1 可能的超級鍵) + (使用候選鍵 A2 可能的超級鍵) – (來自 A1 和 A2 的公共超級鍵)。

= = 2^(n-1) + 2^(n-1) - 2^(n-2)

示例-5

假設我們有一個具有屬性 {a1, a2, a3,…, an} 的關係 R，並且候選鍵為“a1”，“a2 a3”。我們可以使用以下公式

= (a1) 的超級鍵 + (a2 a3) 的超級鍵 – (a1 a2 a3) 的超級鍵。

= 2^(n - 1) + 2^(n - 2) - 2^(n - 3)

示例-6

假設我們有一個具有屬性 {a1, a2, a3,…, an} 的關係 R，並且候選鍵為“a1 a2”，“a3 a4”。我們可以使用以下公式

= (a1 a2) 的超級鍵 + (a3 a4) 的超級鍵 – (a1 a2 a3 a4) 的超級鍵。

= 2^(n - 2) + 2^(n - 2) - 2^(n - 4)

示例-7

假設我們有一個具有屬性 {a1, a2, a3,…, an} 的關係 R，並且候選鍵為“a1 a2”，“a1 a3”。我們可以使用以下公式

= (a1 a2) 的超級鍵 + (a1 a3) 的超級鍵 – (a1 a2 a3) 的超級鍵。

= 2^(n - 2) + 2^(n - 2) - 2^(n - 3)

示例-8

假設有一個具有屬性 {a1, a2, a3,…,an} 的關係 R。如果候選鍵為“a1”，“a2”和“a3”，則可能的超級鍵有多少個？

要找出超級鍵的數量，我們可以使用下圖所示的公式。我們只需要將關係中的屬性數量 (n) 和我們擁有的候選鍵數量代入即可。

公式為

|A1 ∪ A2 ∪ A3| = |A1| + |A2| + |A3| – |A1 ∩ A2| – |A1 ∩ A3| – |A2 ∩ A3| + |A1 ∩ A2 ∩ A3|

= (使用候選鍵 A1 可能的超級鍵) + (使用候選鍵 A2 可能的超級鍵) + (使用候選鍵 A3 可能的超級鍵) – (來自 A1 和 A2 的公共超級鍵) – (來自 A1 和 A3 的公共超級鍵) – (來自 A2 和 A3 的公共超級鍵) + (來自 A1、A2 和 A3 的公共超級鍵)

= 2^(n-1) + 2^(n-1) + 2^(n-1) – 2^(n-2) – 2^(n-2) – 2^(n-2) + 2^(n-3)

示例-9

假設有一個關係 R (A, B, C, D, E, F, G, H)，並且函式依賴集為 CH → G、A → BC、B → CFH 和 E → A、F → EG。存在多少個可能的超級鍵？

首先，我們需要找出候選鍵，它們是 AD、BD、ED 和 FD。然後我們需要找到由於單個候選鍵、兩個候選鍵的組合、三個候選鍵和所有候選鍵而產生的可能的超級鍵。應用包含-排除原理後，我們可以找到超級鍵的數量，即 120。

示例-10

假設有一個具有屬性 {a1, a2, a3…an} 的關係 R，並且 {a1a2a3…ak} 作為候選鍵，其中 k<=n。可能的超級鍵有多少個？

可能的超級鍵數量為 2^(n-k)。

示例-11

假設有一個具有屬性 {a1, a2, a3…an} 的關係 R，使得任何 k 個屬性一次確定所有其他屬性。我們需要找到 k 的值，使得關係中的候選鍵數量最大。

任何 k 個屬性一次構成一個候選鍵。這些 k 個屬性是從 n 個屬性中隨機選擇的。因此，對於某個 k，可能的候選鍵數量為 nCk，即 n!/(n-k)!k!。為了使候選鍵的數量最大化，k 必須為 ⌊n/2⌋，以便 nCk 為該值的最大值。