Cách lấy khóa tối thiểu từ các phụ thuộc chức năng?

Question

Tôi cần một số trợ giúp và nguyên tắc.

Tôi có mối quan hệ sau: R = {A, B, C, D, E, F} và tập các phụ thuộc hàm

 
F = { 
    {AB -> C}; 
    {A -> D}; 
    {D -> AE}; 
    {E -> F}; 
} 

khóa chính cho R là gì?

Nếu tôi áp dụng quy tắc suy luận tôi nhận được các phụ thuộc hàm thêm:

D -> A 
D -> E 
D -> F 

D -> AEF 

A -> E 
A -> F 
A -> DEF 

Làm thế nào để tiếp tục không?

Answer 1

Có một thuật toán nổi tiếng để thực hiện việc này. Tôi không nhớ nó, nhưng tập thể dục dường như đủ đơn giản để không sử dụng nó.

Tôi nghĩ rằng đây là tất cả về transitivity:

CurrentKey = {A, B, C, D, E, F} 

Bạn biết D xác định E và E xác định F. Do đó, D xác định F bởi transitivity. Như F không xác định bất cứ điều gì, chúng ta có thể loại bỏ nó và như E có thể được lấy từ D chúng ta có thể loại bỏ nó là tốt:

CurrentKey = {A, B, C, D} 

như AB xác định C và C không xác định bất cứ điều gì chúng ta biết nó có thể' t là một phần của chìa khóa, vì vậy chúng tôi loại bỏ nó:

CurrentKey = {A, B, D} 

cuối cùng chúng ta đã biết một quyết định D vì vậy chúng tôi có thể loại bỏ sau từ khóa:

CurrentKey = {A, B} 

Nếu một khi bạn có chìa khóa có thể này, bạn có thể tạo lại tất cả các phụ thuộc chức năng es nó là chìa khóa có thể.

PS: Nếu bạn tình cờ có thuật toán tiện dụng, xin vui lòng gửi nó như tôi muốn được vui để học lại mà :)

Answer 2

Thuật toán: tính toán chính (gọi với x = ∅)

procedure key(x;A;F) 
foreach ! B 2 F do 
if x and B 2 x and B ̸2 then 
return; /* x not minimal */ 
fi 
od 
if x+ = A then 
print x; /* found a minimal key x */ 
else 
X any element of A x+; 
key(x [ fXg;A;F); 
foreach ! X 2 F do 
key(x [ ;A;F); 
od 
fi