Các nguyên tắc thiết kế lược đồ quan hệ và phụ thuộc hàm

Ngữ nghĩa của các thuộc tính quan hệ

Khi chúng ta nhóm các thuộc tính để tạo nên một lược đồ quan hệ, ta giả thiết rằng có một ý nghĩa nào đó gắn với các thuộc tính. Ý nghĩa này, còn gọi là ngữ nghĩa, chỉ ra việc hiểu các giá trị thuộc tính lưu giữ trong các bộ của một quan hệ như thế nào. Nói cách khác, các giá trị thuộc tính trong một bộ liên hệ với nhau như thế nào. Nếu việc thiết kế khái niệm được làm một cách cẩn thận, sau đó là một chuyển đổi sang các quan hệ thì hầu hết ngữ nghĩa đã được giải thích và thiết kế kết quả có một ý nghĩa rõ ràng. Nói chung, việc giải thích ngữ nghĩa của quan hệ càng dễ dàng thì việc thiết kế lược đồ quan hệ càng tốt. Một ví dụ về thiết kế lược đồ quan hệ tốt là lược đồ cơ sở dữ liệu “CÔNG TY”. Trong lược đồ đó, các thuộc tính đều có ý nghĩa rõ ràng, không có tính mập mờ. Nguyên tắc sau sẽ hỗ trợ cho việc thiết kế lược đồ quan hệ.

Nguyên tắc 1: Thiết kế một lược đồ quan hệ sao cho dễ giải thích ý nghĩa của nó. Đừng tổ hợp các thuộc tính từ nhiều kiểu thực thể và kiểu liên kết vào một quan hệ đơn. Một cách trực quan, nếu một lược đồ quan hệ tương ứng với một kiểu thực thể hoặc một kiểu liên kết thì ý nghĩa trở nên rõ ràng. Ngược lại, một quan hệ tương ứng với một hỗn hợp các thực thể và liên kết thì ý nghĩa trở nên không rõ ràng.

Thông tin dư thừa trong các bộ và sự dị thường cập nhật

Một mục tiêu của thiết kế lược đồ là làm tối thiểu không gian lưu trữ các quan hệ cơ sở. Các thuộc tính được nhóm vào trong các lược đồ quan hệ có một ảnh hưởng đáng kể đến không gian lưu trữ. Nếu cùng một thông tin được lưu giữ nhiều lần trong cơ sở dữ liệu thì ta gọi đó là dư thừa thông tin và điều đó sẽ làm lãng phí không gian nhớ. Ví dụ, giả sử ta có bảng cơ sở sau đây:

Bảng NHÂNVIÊN_ĐƠNVỊ

Ở đây có sự dư thừa thông tin. Nếu một đơn vị có nhiều nhân viên làm việc thì thông tin về đơn vị (Mã số, Tên đơn vị, Mã số người quản lý) được lưu giữ nhiều lần trong bảng. So với việc dùng hai bảng NHÂNVIÊN và ĐƠNVỊ riêng rẽ như trong lược đồ “CÔNG TY”, việc sử dụng bảng này làm lãng phí không gian nhớ.

Ngoài việc lãng phí không gian nhớ nó còn dẫn đến một vấn đề nghiêm trọng là sự dị thường cập nhật. Dị thường cập nhật bao gồm: Dị thường Chèn, dị thường Xoá, dị thường Sửa đổi. Những dị thường cập nhật này sẽ đưa vào cơ sở dữ liệu những thông tin “lạ” và làm cho cơ sở dữ liệu mất tính đúng đắn.

Dị thường Chèn: Gây ra khó khăn khi chèn các bộ giá trị vào bảng hoặc dẫn đến vi phạm ràng buộc. Ví dụ:

Để chèn một bộ giá trị cho một nhân viên mới vào bảng NHÂNVIÊN_ĐƠNVỊ ngoài các thông tin về nhân viên, ta phải đưa vào các thông tin về đơn vị mà anh ta làm việc hoặc các giá trị null (nếu nhân viên không làm việc cho đơn vị nào cả). Các thông tin về đơn vị phải được đưa vào một cách đúng đắn, phù hợp với các thông tin của đơn vị đó trong các bộ khác. Trong lúc đó, với lược đồ cơ sở dữ liệu “CÔNGTY” chúng ta không phải lo lắng gì, vì các thông tin về một đơn vị chỉ được lưu trữ một lần.

Rất khó chèn một đơn vị mới vào quan hệ NHÂNVIÊN_ĐƠNVỊ nếu đơn vị đó không có nhân viên nào làm việc. Cách giải quyết duy nhất là điền các giá trị null vào các thuộc tính của nhân viên. Điều đó làm nảy sinh vấn đề về ràng buộc bởi vì MãsốNV là khóa chính của quan hệ.

Dị thường Xóa: Gây ra việc mất thông tin khi xóa. Ví dụ khi ta xóa một bộ giá trị trong bảng NHÂNVIÊN_ĐƠNVỊ. Nếu nhân viên tương ứng với bộ giá trị đó là người cuối cùng làm việc cho đơn vị thì phép xóa sẽ kéo theo việc làm mất thông tin về đơn vị.

Dị thường Sửa đổi: Gây ra việc sửa đổi hàng loạt khi ta muốn sửa đổi một giá trị trong một bộ nào đó. Ví dụ, ta muốn sửa giá trị của thuộc tính MãsốNQL của đơn vị 5. Điều đó kéo theo ta phải sửa giá trị của thuộc tính này trong tất cả các bộ ứng với đơn vị 5. Dựa trên các dị thường ở trên, chúng ta có thể phát biểu nguyên tắc sau:

Nguyên tắc 2: Thiết kế các lược đồ quan hệ cơ sở sao cho không sinh ra những dị thường cập nhật trong các quan hệ. Nếu có xuất hiện những dị thường cập nhật thì phải ghi chép lại một cách rõ ràng và phải đảm bảo rằng các chương trình cập nhật dữ liệu sẽ thực hiện một cách đúng đắn.

Các giá trị không xác định trong các bộ

Trong một số thiết kế lược đồ, chúng ta có thể nhóm nhiều thuộc tính với nhau vào một quan hệ “béo”. Nếu nhiều thuộc tính không thích hợp cho mọi bộ trong một quan hệ, chúng ta sẽ kết thúc với nhiều giá trị null trong các bộ đó. Điều đó có thể làm tăng không gian ở mức lưu trữ và có thể dẫn đến vấn đề về hiểu ý nghĩa của các thuộc tính. Việc chỉ ra các phép nối ở mức lôgic cũng sẽ gặp khó khăn. Một vấn đề nữa với các giá trị null là các hàm nhóm như COUNT, SUM không đếm được đối với chúng. Hơn nữa, các giá trị null có thể nhiều cách giải thích, chẳng hạn như thuộc tính không áp dụng được cho bộ này, giá trị của thuộc tính cho bộ này là không có hoặc giá trị cho thuộc tính là có nhưng vắng mặt. Tóm lại, các giá trị null có nhiều ý nghĩa khác nhau .

Nguyên tắc 3: Tránh càng xa càng tốt việc đặt vào trong các quan hệ cơ sở những thuộc tính mà các giá trị của chúng thường xuyên là null. Nếu không thể tránh được các giá trị null thì phải đảm bảo rằng chúng chỉ áp dụng trong các trường hợp đặc biệt và không áp dụng cho một số lớn các bộ trong quan hệ.

Sinh ra các bộ giả

Nhiều khi chúng ta đưa vào cơ sở dữ liệu những quan hệ không đúng, việc áp dụng các phép toán (nhất là các phép nối) sẽ sinh ra các bộ giá trị không đúng, gọi là các bộ “giả”. Ví dụ, xét hai lược đồ quan hệ:

NV_ĐĐ (Tên, ĐịađiểmDA)

NV_DA1(Mã sốNV, Mã sốDA, Sốgiờ, TênDA, ĐịađiểmDA)

Bảng NV_ĐĐ

Bảng NV_DA1

Bây giờ ta nối tự nhiên hai quan hệ trên với nhau, ta có quan hệ

Kết quả của phép nối tự nhiên hai quan hệ NV_ĐĐ và NV_DA1

Ta thấy các dòng đánh dấu * là các bộ “giả”. Đấy là các bộ giá trị không có trên thực tế.

Nguyên tắc 4: Thiết kế các lược đồ quan hệ sao cho chúng có thể được nối với điều kiện bằng trên các thuộc tính là khoá chính hoặc khoá ngoài theo cách đảm bảo không sinh ra các bộ “giả”. Đừng có các quan hệ chứa các thuộc tính nối khác với các tổ hợp khoá chính-khoá ngoài. Nếu không tránh được những quan hệ như vậy thì đừng nối chúng trên các thuộc tính đó, bởi vì các phép nối có thể sinh ra các bộ “giả”.

Định nghĩa phụ thuộc hàm

Một phụ thuộc hàm là một ràng buộc giữa hai nhóm thuộc tính của một cơ sở dữ liệu. Giả sử rằng lược đồ cơ sở dữ liệu của ta có n thuộc tính A₁,A₂,…,A_n và ta hãy nghĩ rằng toàn bộ cơ sở dữ liệu được mô tả bằng một lược đồ quan hệ chung R={A₁, A₂,…., A_n}. Đừng nên nghĩ rằng cơ sở dữ liệu của chúng ta sẽ được lưu trữ trong một bảng chung, chúng ta chỉ sử dụng khái niệm này để phát triển lý thuyết hình thức về sự phụ thuộc dữ liệu. Giả sử X và Y là hai tập con của R.

Một phụ thuộc hàm, ký hiệu là X→ Y, giữa hai tập thuộc tính X và Y chỉ ra một ràng buộc trên các bộ có thể có tạo nên một trạng thái quan hệ r của R. Ràng buộc đó là: với hai bộ bất kỳ t₁ và t₂ trong r , nếu có t₁[X] = t₂[X] thì cũng phải có t₁[Y] = t₂[Y]. Điều đó có nghĩa là các giá trị của thành phần Y của một bộ trong R phụ thuộc vào, hoặc được xác định bởi, các giá trị của thành phần X. Nói cách khác, các giá trị của thành phần X của một bộ xác định một cách duy nhất các giá trị của thành phần Y. Chúng ta cũng nói rằng có một phụ thuộc hàm từ X vào Y hoặc Y phụ thuộc hàm vào X. Phụ thuộc hàm được viết tắt là FD (functional dependency). Tập thuộc tính X được gọi là vế trái của FD, tập thuộc tính Y được gọi là vế phải của FD.

Như vậy, X xác định hàm Y trong lược đồ quan hệ R khi và chỉ khi nếu hai bộ của r(R) bằng nhau trên các giá trị của X thì chúng nhất thiết phải bằng nhau trên các giá trị của Y. Ta có các nhận xét sau:

• Nếu có một ràng buộc trên các trạng thái của R là chỉ có một bộ giá trị duy nhất của X trong mọi thể hiện quan hệ r(R) thì điều đó kéo theo X → Y với mọi tập con các thuộc tính Y của R.
• Nếu X → Y thì không thể nói gì về Y → X.

Một phụ thuộc hàm là một tính chất ngữ nghĩa của các thuộc tính. Những người thiết kế cơ sở dữ liệu sẽ dùng hiểu biết của họ về ý nghĩa của các thuộc tính của R để chỉ ra các phụ thuộc hàm có thể có trên mọi trạng thái quan hệ của r(R) của R. Khi ngữ nghĩa của hai tập thuộc tính trong R chỉ ra rằng có thể có một phụ thuộc hàm, chúng ta sẽ đặc tả phụ thuộc hàm như một ràng buộc. Các trạng thái quan hệ r(R) thoả mãn các ràng buộc phụ thuộc hàm được gọi là các trạng thái hợp pháp của R, bởi vì chúng tuân theo các ràng buộc phụ thuộc hàm. Như vậy, việc sử dụng chủ yếu của các phụ thuộc hàm là dùng để mô tả một lược đồ quan hệ R bằng việc chỉ ra các ràng buộc trên các thuộc tính phải thoả mãn ở mọi thời điểm.

Một phụ thuộc hàm là một tính chất của lược đồ quan hệ R chứ không phải là tính chất của một trạng thái hợp pháp r của R. Vì vậy, một phụ thuộc hàm không thể được phát hiện một cách tự động từ một trạng thái r mà phải do một người hiểu biết ngữ nghĩa của các thuộc tính xác định một cách rõ ràng. Ví dụ, ta có quan hệ sau

Bảng DẠY

Mới nhìn qua, chúng ta có thể nói có một phụ thuộc hàm Tàiliệu → Mônhọc, tuy nhiên chúng ta không thể khẳng định được vì điều đó chỉ đúng với trạng thái quan hệ này, biết đâu trong trạng thái quan hệ khác có thể có hai môn học khác nhau sử dụng cùng một tài liệu tham khảo. Với một trạng thái cụ thể, chúng ta chỉ có thể khẳng định là không có một phụ thuộc hàm giữa nhóm thuộc tính này và nhóm thuộc tính khác. Để làm điều đó chúng ta chỉ cần đưa ra một phản ví dụ. Chẳng hạn, ở trong quan hệ trên chúng ta có thể khẳng định rằng không có phụ thuộc hàm giữa Giáoviên và Mônhọc bằng cách chỉ ra ví dụ là AA dạy hai môn học “ Mônhọc1” và “Mônhọc2” vậy Giáo viên không thể xác định duy nhất Môn học.

Để biểu diễn các phụ thuộc hàm trong một lược đồ quan hệ, chúng ta sử dụng khái niệm sơ đồ phụ thuộc hàm. Mỗi FD được biểu diễn bằng một đường nằm ngang. Các thuộc tính ở vế trái của FD được nối với đường biểu diễn FD bằng các đường thẳng đứng, các thuộc tính ở vế phải của FD được nối với đường biểu diễn FD bằng mũi tên chỉ đến các thuộc tính.

Ví dụ: Ta có lược đồ quan hệ

MƯỢN(Sốthẻ, Mãsốsách, Tênngườimượn, Tênsách, Ngàymượn)

Với các phụ thuộc hàm:

Sốthẻ → Tênngườimượn

Mãsốsách → Tênsách

Sốthẻ, Mãsốsách → Ngàymượn

Có sơ đồ phụ thuộc hàm như sau:

Sơ đồ phụ thuộc của quan hệ MƯỢN

Các quy tắc suy diễn đối với các phụ thuộc hàm

Chúng ta ký hiệu F là tập các phụ thuộc hàm được xác định trên một lược đồ quan hệ R. Một phụ thuộc hàm X → Y được gọi là suy diễn được từ một tập các phụ thuộc hàm F được xác định trên R nếu X → Y đúng trong mỗi trạng thái quan hệ r là mở rộng hợp pháp của R, nghĩa là mỗi khi r làm thoả mãn mọi phụ thuộc hàm trong F, X→ Y cũng đúng trong r. Tập hợp tất cả các phụ thuộc hàm suy diễn được từ F được gọi là bao đóng của F và được ký hiệu là F⁺. Để xác định một cách suy diễn các phụ thuộc hàm có hệ thống, chúng ta phải phát hiện một tập hợp các quy tắc suy diễn. Tập quy tắc này sẽ được sử dụng để suy diễn các phụ thuộc hàm mới từ một tập các phụ thuộc hàm cho trước. Ta sử dụng ký hiệu F |= X→ Y để ký hiệu phụ thuộc hàm X→ Y được suy diễn từ tập các phụ thuộc hàm F. Để cho tiện, ta viết tắt phụ thuộc hàm có dạng {X,Y}→ Z thành XY → Z ( nghĩa là ta nối các biến và bỏ dấu ngoặc nhọn đi). Có 6 quy tắc suy diễn đối với các phụ thuộc hàm:

QT1 (quy tắc phản xạ) : Nếu X  Y thì X → Y

QT2 (quy tắc tăng) : { X→ Y } |= XZ →YZ

QT3 (quy tắc bắc cầu) : { X→ Y, Y→ Z } |= X→ Y

QT4 (quy tắc chiếu) : { X→ YZ } |= X→ Y và X→ Z

QT5 (quy tắc hợp) : { X→ Y , X→ Z } |= X→ YZ

QT6 (quy tắc tựa bắc cầu) : { X→ Y, WY→ Z } |= WX→ Z

Quy tắc phản xạ phát biểu rằng một tập hợp các thuộc tính luôn luôn xác định chính nó hoặc một tập con bất kỳ của nó. Vì QT1 tạo ra các phụ thuộc luôn luôn đúng, những phụ thuộc như vậy được gọi là tầm thường. Một cách hình thức, một phụ thuộc hàm X → Y là tầm thường nếu X Y, ngược lại, nó được gọi là không tầm thường. Quy tắc tăng nói rằng việc thêm cùng một tập thuộc tính vào cả hai vế của một phụ thuộc hàm sẽ tạo ra một phụ thuộc hàm đúng đắn. Theo quy tắc 3, các phụ thuộc hàm là bắc cầu. Quy tắc chiếu (QT4) nói rằng chúng ta có thể bỏ bớt các thuộc tính ra khỏi vế phải của phụ thuộc hàm. Việc áp dụng nhiều lần quy tắc này có thể tách phụ thuộc hàm X → {A₁, A₂,…, A_n} thành một tập hợp phụ thuộc hàm { X→ A₁, X→ A₂, ..., X→ A_n}. Quy tắc hợp cho phép chúng ta làm ngược lại, ta có thể gộp các phụ thuộc hàm { X→ A₁, X→A₂, ..., X→ A_n} thành một phụ thuộc hàm đơn X→ {A₁, A₂, ..., A_n}.

Có thể chứng minh các quy tắc suy diễn ở trên một cách trực tiếp hoặc bằng phản chứng dựa trên định nghĩa của phụ thuộc hàm. Để chúng minh phản chứng, ta giả thiết một quy tắc là không đúng và chỉ ra rằng điều đó là không thể. Sau đây là chứng minh các quy tắc.

Quy tắc 1:

Giả sử rằng X  Y và hai bộ t₁ và t₂ trong một thể hiện quan hệ r của R sao cho t₁[X] = t₂[X]. Khi đó t₁[Y] = t₂[Y] bởi vì X  Y, như vậy X→ Y phải xẩy ra trong r.

Quy tắc 2: (chứng minh phản chứng)

Giả sử rằng X→Y đúng trong một thể hiện quan hệ r của R nhưng XZ→ YZ không đúng. Khi đó phải có hai bộ t₁ và t₂ trong r sao cho:

1. t₁[X] = t₂[X],
2. t₁[Y] = t₂[Y],
3. t₁[XZ] = t₂[XZ] và
4. t₁[YZ] ≠ t₂[YZ]. Điều đó là không thể bởi vì từ (1) và (3) chúng ta suy ra
5. t₁[Z] = t₂[Z], và từ (2) và (5) ta suy ra t₁[YZ] = t₂[YZ], mâu thuẫn với (4).

Quy tắc 3: Giả sử rằng

(1) X→ Y và (2) Y→ Z cả hai đúng trong một quan hệ r. Khi đó với mọi bộ t₁ và t₂ trong r sao cho t₁[X] = t₂[X] ta phải có (3) t₁[Y] = t₂[Y] theo giả thiết (1). Như vậy chúng ta cũng phải có (4) t₁[Z] = t₂[Z] theo (3) và giả thiết (2). Vậy X→ Z phải đúng trong r.

Chúng ta có thể chứng minh các quy tắc từ quy tắc 4 đến quy tắc 6 theo phương pháp trên. Tuy nhiên ta có thể lợi dụng các quy tắc đã được chứng minh là đúng để chứng minh chúng. Sau đây ta chứng minh theo cách đó.

Quy tắc 4:

1. X→ YZ (cho trước)

2. YZ → Y (sử dụng QT1 và YZ  Y)

3. X→ Y (sử dụng QT3 trên 1. và 2.)

Quy tắc 5:

1. X→ Y (cho trước)

2. X→ Z (cho trước)

3. X→ YX (sử dụng QT2 trên 1. bằng cách thêm vào cả hai vế X, và XX=X)

4. YX→ YZ (sử dụng QT2 trên 2. bằng cách thêm vào cả hai vế Y)

5. X→YZ (sử dụng QT3 trên 3. và 4.)

Quy tắc 6:

1. X→Y (cho trước )

2. WY→Z (cho trước)

3. WX→WY (sử dụng QT2 trên 1. bằng cách thêm vào cả hai vế W)

4. WX→ Y (sử dụng QT3 trên 3. và 2.)

Amstrong đã chứng minh rằng các quy tắc suy diễn từ QT1 đến QT3 là đúng và đầy đủ. Đúng có nghĩa là cho trước một tập các phụ thuộc hàm F trên một lược đồ quan hệ R , bất kỳ một phụ thuộc hàm nào suy diễn được bằng cách áp dụng các quy tắc từ QT1 đến QT3 cũng đúng trong mỗi trạng thái quan hệ r của R thoả mãn các phụ thuộc hàm trong F. Đầy đủ có nghĩa là việc sử dụng các quy tắc từ QT1 đến QT3 lặp lại nhiều lần để suy diễn các phụ thuộc hàm cho đến khi không còn suy diễn được nữa sẽ cho kết quả là một tập hợp đầy đủ các phụ thuộc hàm có thể được suy diễn từ F. Nói cách khác, tập hợp các phụ thuộc hàm F⁺ (bao đóng của F) có thể xác định được từ F bằng cách áp dụng các quy tắc suy diễn từ QT1 đến QT3. Các quy tắc từ QT1 đến QT3 được gọi là các quy tắc suy diễn Amstrong.

Thông thường, những người thiết kế cơ sở dữ liệu đầu tiên chỉ ra một tập các phụ thuộc hàm dễ xác định được nhờ ngữ nghĩa của các thuộc tính của R. Sau đó, sử dụng các quy tắc Amstrong để suy diễn các phụ thuộc hàm bổ sung. Một cách có hệ thống, để xác định tất cả các phụ thuộc hàm bổ sung là đầu tiên hãy xác định mỗi tập thuộc tính X xuất hiện ở vế trái của một phụ thuộc hàm nào đấy trong F và sau đó xác định tập hợp tất cả các thuộc tính phụ thuộc vào X. Như vậy, với mỗi tập thuộc tính X, chúng ta xác định tập X⁺ các thuộc tính phụ thuộc hàm vào X dựa trên F. X⁺ được gọi là bao đóng của X dưới F. Thuật toán xác định X⁺ như sau:

Thuật toán 7.1: ( xác định X⁺, bao đóng của X dưới F)

X⁺ = X;

Repeat

Old X⁺ = X⁺ ;

với mỗi phụ thuộc hàm Y → Z trong F thực hiện

nếu X⁺  Y thì X⁺ = X⁺  Z;

until ( X⁺ = Old X⁺ );

Ví dụ: Xét lược đồ quan hệ

R = {MãsốNV, HọtênNV, MãsốDA, TênDA, ĐịađiểmDA, Sốgiờ}

và tập phụ thuộc hàm F = {MãsốNV → HọtênNV,

MãsốDA → TênDA, ĐịađiểmDA,

{MãsốNV, MãsốDA} → Số giờ}

Áp dụng thuật toán 7.1 ta có:

{MãsốNV}⁺ = { MãsốNV, HọtênNV}

{MãsốDA }⁺ = { MãsốDA, TênDA, ĐịađiểmDA}

{MãsốNV, MãsốDA}⁺ = {MãsốNV, HọtênNV, MãsốDA, TênDA, Sốgiờ}

Bao đóng và khóa: Để ý rằng nếu X⁺ là là tập tất cả các thuộc tính của quan hệ thì có nghĩa là X xác định hàm các thuộc tính còn lại, hay nói cách khác X là một siêu khóa. Chúng ta có thể kiểm tra xem một tập thuộc tính X có phải là khóa của một quan hệ bằng cách trước tiên xem X⁺ có chứa tất cả các thuộc tính của quan hệ hay không sau đó kiểm tra không có một tập con S nào được lập từ X bằng cách loại bỏ một thuộc tính của X thỏa mãn S⁺chứa tất cả các thuộc tính của quan hệ (nghĩa là X là siêu khóa tối thiểu). Ví dụ:

Xét lược đồ quan hệ R( A,B,C,D,E,F) và tập phụ thuộc hàm

F ={ A,B → F ; A→ C,D; B → E }

Ta có {A,B}⁺ = {A,B,C,D,E,F}, A⁺ = {A,C,D}, B⁺ = {B,E} , vậy AB là khóa của quan hệ.

Sự tương đương của các tập phụ thuộc hàm

Trong phần này chúng ta thảo luận về sự tương đương của hai tập phụ thuộc hàm. Một tập hợp các phụ thuộc hàm E được phủ bởi một tập các phụ thuộc hàm F - hoặc F phủ E - nếu mỗi một phụ thuộc hàm trong E đều ở trong F⁺ ,điều đó có nghĩa là mỗi phụ thuộc hàm trong E có thể suy diễn được từ F. Hai tập phụ thuộc hàm E và F là tương đương nếu E⁺ = F⁺. Như vậy tương đương có nghĩa là mỗi phụ thuộc hàm trong E có thể suy diễn được từ F và mỗi phụ thuộc hàm trong F có thể suy diễn được từ E.

Chúng ta có thể xác định xem F có phủ E hay không bằng cách tính X⁺ đối với F đối với mỗi thuộc hàm X→Y trong E và sau đó kiểm tra xem X⁺ này có các thuộc tính trong Y hay không (nghĩa là X⁺  Y). Nếu điều đó xẩy ra với mỗi phụ thuộc hàm trong E, thì F phủ E. Chúng ta xác định xem E và F có tương đương hay không bằng cách kiểm tra E phủ F và F phủ E.

Ví dụ : Xét hai tập phụ thuộc hàm

F = {A →C, AC → D, E→AD, E →H }

E = { A →CD, E → AH }

Ta chứng minh F phủ E:

Tìm bao đóng của các vế trái của các phụ thuộc hàm trong E theo F. Áp dụng thuật toán 7.1 ở trên, ta có:

{A}⁺ = { A, C, D };

{E}⁺ = {E, A,D, H}

ta thấy các bao đóng này chứa các vế phải tương ứng. Từ đó suy ra F phủ E.

Ta chứng minh E phủ F:

Tìm bao đóng của các vế trái của các phụ thuộc hàm trong F theo E. Ta có

{A}⁺ ={A,C,D},

{AC}+ = { A,C,D},

{E}+ = {E,A,H}, ta thấy các bao đóng này chứa các vế phải tương ứng. Từ đó suy ra E phủ F.

Tóm lại E tương đương với F.

Các tập phụ thuộc hàm tối thiểu

Một tập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các điều kiện sau đây:

1. Vế phải của các phụ thuộc hàm trong F chỉ có một thuộc tính.

2. Chúng ta không thể thay thế bất kỳ một phụ thuộc hàm X →A trong F bằng phụ thuộc hàm Y→A, trong đó Y là tập con đúng của X mà vẫn còn là một tập phụ thuộc hàm tương đương với F.

3. Chúng ta không thể bỏ đi bất kỳ phụ thuộc hàm nào ra khỏi F mà vẫn có một tập phụ thuộc hàm tương đương với F.

Chúng ta có thể nghĩ về tập tối thiểu các phụ thuộc hàm như là một tập hợp ở dạng chuẩn không có sự dư thừa. Điều kiện 1 đảm bảo rằng mỗi phụ thuộc hàm là ở dạng chính tắc với một thuộc tính ở vế phải. Điều kiện 2 và 3 đảm bảo rằng không có sự dư thừa trong các phụ thuộc hoặc do có các thuộc tính dư thừa ở vế trái của phụ thuộc, hoặc do có một phụ thuộc có thể được suy diễn từ các phụ thuộc khác ở trong F.

Một phủ tối thiểu của một tập phụ thuộc hàm F là một tập tối thiểu các phụ thuộc hàm F_min tương đương với F. Thường có rất nhiều các phủ tối thiểu cho một tập các phụ thuộc hàm. Chúng ta luôn luôn có thể tìm được ít nhất là một phủ tối thiểu G cho một tập các phụ thuộc hàm F bất kỳ theo thuật toán 4.2 sau đây:

Thuật toán 7.2: ( Tìm phủ tối thiểu G cho F)

1. Đặt G := F;

2. Thay thế mỗi phụ thuộc hàm X → {A₁, A₂, ..., A_n} trong G bằng n phụ thuộc hàm X → A₁, X → A₂, … , X → A_n.

3. Với mỗi phụ thuộc hàm X → A trong G,

với mỗi thuộc tính B là một phần tử của X

nếu ((G – (X → A)  ((X － {B}) → A) là tương đương với G

thì thay thế X→A bằng (X – {B})→A ở trong G

4. Với mỗi phụ thuộc hàm X→A còn lại trong G

nếu (G － {X → A}) là tương đương với G

thì loại bỏ X → A ra khỏi G

Ví dụ áp dụng : Tìm phủ tối thiểu cho tập phụ thuộc hàm:

{A → B, A → C, B → A, B → C, C → A, C → B}

Áp dụng thuật 7.2, chúng ta có thể tìm được các phủ tối thiểu sau:

1. Do A→B và B→C nên A→C là thừa. Do C→B và B→A nên C→A là thừa. Bỏ những phụ thuộc hàm thừa đi, ta có {A→B, B→A, B→C, C→B} là một phủ tối thiểu.
2. Do A→B và B→C nên A→C là thừa. Do có B→C và C→A nên B→A là thừa. Do có C→A và A→B nên C→B là thừa. Bỏ những phụ thuộc hàm thừa đi, ta nhận được một phủ tối thiểu khác là {A→B, B→C, C→A}