Tinh chỉnh lược đồ và các dạng chuẩn hoá

Các vấn đề tồn tại khi có sự dư thừa

Lưu trữ dư thừa thông tin, tức là một thông tin được lưu nhiều lần trong cơ sở dữ liệu có thể dẫn tới một số vấn đề sau:

• Lưu trữ dư thừa: Một số thông tin được lưu trữ lặp đi lặp lại.
• Dị thường khi cập nhật: Nếu một bản sao của dữ liệu lặp này được cập nhật, thì cơ sở dữ liệu có thể xảy ra hiện tượng không nhất quán, trừ khi tất cả các bản sao này được cập nhật tương tự.
• Dị thường khi thêm dữ liệu: Bạn có thể gặp phải trường hợp không thể thêm được thông tin vào vì muốn thêm những thông tin này lại cần phải thêm những thông tin khác không liên quan đến nó.
• Dị thường khi xoá dữ liệu: Khi bạn xoá một bộ dữ liệu, bạn có thể làm mất những dữ liệu khác lẽ ra không được xóa.

Xem xét một quan hệ được chuyển từ thực thể Hourly_Emps trong Chương 2:

Hourly-Emps(ssn, name, lot, rating, hourly_wages, hours_worked)

Trong chương này, để ngắn gọn chúng ta bỏ qua thông tin về kiểu thuộc tính, vì chúng ta chỉ tập trung vào các thuộc tính nào có trong quan hệ. Chúng ta cũng gọi tắt tên các thuộc tính bằng ký tự đầu tiên của mỗi thuộc tính. Ví dụ, chúng ta gọi lược đồ quan hệ của Hourly_Emps là SNLRWH (trong đó WH là viết tắt của thuộc tính hourly_wages).

Khoá của Hourly_Emps là ssn. Thêm nữa, giả sử rằng thuộc tính hourly_wages được xác định bởi thuộc tính rating. Tức là, nếu chúng ta biết giá trị của rating thì chúng ta cũng sẽ suy ra được giá trị của hourly_wages. Ràng buộc toàn vẹn này là một ví dụ về một phụ thuộc hàm. Nó dẫn đến khả năng có sự dư thừa trong quan hệ Hourly_Emps, như minh hoạ trong Hình 1.

Nếu một giá trị xuất hiện trong cột rating của hai bộ giá trị, thì ràng buộc toàn vẹn nói với chúng ta rằng cùng một giá trị phải xuất hiện trong cột hourly_wages ứng với bộ giá trị đó. Sự dư thừa này dẫn đến một số vấn đề như đã trình bày phía trên:

• Lưu trữ dư thừa: Giá trị rating bằng 8 thì hourly_wages sẽ bằng 10 và cặp giá trị này lặp lại ba lần.
• Dị thường khi cập nhật: Giá trị hourly_wages trong bộ đầu tiên có thể được cập nhật trong khi các hai bộ giá trị khác không được cập nhật tương ứng.
• Dị thường khi thêm: Chúng ta không thể thêm một bộ giá trị của một nhân viên trừ khi chúng ta biết được hourly_wages tương ứng với rating của nhân viên đó.
• Dị thường khi xoá: Nếu chúng ta xoá tất cả các bộ giá trị ứng với một giá trị rating nào đó (ví dụ, chúng ta xóa các bộ giá trị Smethurst và Guldu), chúng ta sẽ làm mất cặp giá trị rating và hourly_wages tương ứng của nó.

Lý tưởng mà nói chúng ta muốn một lược đồ không có sự dư thừa, nhưng đôi khi chúng ta vẫn chấp nhận một lược đồ có sự dư thừa do những ưu điểm về mặt thực thi của nó. Chúng ta sẽ quyết định điều này một cách sáng suốt.

Bao đóng của một tập phụ thuộc hàm

Một tập của tất cả các phụ thuộc hàm được suy diễn từ một tập F đã cho của các phụ thuộc hàm được gọi là bao đóng của F, ký hiệu là F+. Một câu hỏi quan trọng là làm thế nào chúng ta có thể suy diễn, hoặc là tính toán ra được bao đóng này.Câu trả lời ở đây rất đơn giản, rõ ràng. Có ba quy tắc sau, họi là hệ tiên đề Armstrong, có thể được áp dụng lặp đi lặp lại để có thể đưa ra được tất cả các phụ thuộc hàm có thể suy diễn từ F. Chúng ta sử dụng X, Y và Z là tập các thuộc tính trên lược đồ quan hệ R.

• Phản xạ: Nếu X ⊇ Y, thì X→ Y
• Tăng trưởng: Nếu X→Y, thì XZ→ YZ với bất kỳ tập Z nào.
• Bắc cầu: Nếu X→Y và Y→ Z, thì X→Z.

Định lý 1: Hệ tiên đề Armstrong là đúng, vì nó suy diễn ra chỉ một tập F+ khi áp dụng trên một tập F của các phụ thuộc hàm. Chúng cũng là đầy đủ, vì áp dụng lặp đi lặp lại các quy tắc này sẽ suy diễn ra tất cả các phụ thuộc hàm trong tập bao đóng F+.

Tính đúng đắn của hệ tiên đề Armstrong có thể được chứng minh dễ dàng. Tính đầy đủ khó chứng minh hơn, xem bài tập 17.

Sử dụng một số quy tắc bổ sung có thể giúp ta tính được tập F+ dễ dàng hơn.

• Luật hợp: Nếu X→Y và X→Z thì X→YZ.
• Luật phân rã: Nếu X→ YZ thì X→Y và X→Z.

Những luật bổ sung này không phải là cốt lõi; tính đúng đắn của chúng có thể được chứng minh sử dụng hệ tiên đề Armstrong.

Để minh hoạ việc sử dụng những luật này của phụ thuộc hàm, xem xét một lược đồ quan hệ có các phụ thuộc hàm A→B và B→C. Trong một phụ thuộc hàm trival, phía phải chỉ chứa các thuộc tính xuất hiện bên phía trái; những phụ thuộc hàm này luôn chứa tính phản xạ. Sử dụng tính phản xạ chúng ta có thể đưa ra tất cả các phụ thuộc hàm trivial có dạng:

X→Y trong đó Y ⊆ X, X ⊆ ABC, và Y ⊆ ABC.

Do tính bắc cầu ta có A→C. Do áp dụng các luật mở rộng chúng ta có các phụ thuộc hàm nontrivial:

AC→ BC, AB→ AC, AB→ CB

Xem xét ví dụ tiếp theo về quan hệ Contracts:

Contracts ( contractid , supplierid, projectid, deptid, partid, qty, value)

Chúng ta gọi tắt lược đồ này là CSJDPQV tương ứng với các thuộc tính.

Lược đồ này có các ràng buộc toàn vẹn sau:

• C là khoá: C→ CSJDPQV.
• JP→ C.
• SD→P.

Một số phụ thuộc hàm nằm trong bao đóng của tập phụ thuộc hàm này là:

Từ JP→ C, C→ CSJDPQV và luật bắc cầu, ta có thể suy ra JP→ CSJDPQV.

Từ SD→P và các luật tăng trưởng, ta có thể suy ra SDJ→ JP.

Từ SDJ→ JP, JP → CSJDPQV, và luật bắc cầu, ta có SDJ→ CSJDPQV (Lưu ý, ở đây ta không rút gọn được J ở hai phía. Phụ thuộc hàm không giống như phép tính số học!)

Chúng ta có thể suy diễn ra một số phụ thuộc hàm trong tập bao đóng bằng cách sư dụng luật tăng trưởng và phân rã. Ví dụ, từ C→ CSJDPQV sử dụng phân rã chúng ta có thể suy ra:

C→ C, C→S, C→ J, C→ D, …

Cuối cùng, chúng ta có một các phụ thuộc hàm trivial từ luật phản xạ.

Bao đóng của thuộc tính

Nếu chúng ta chỉ muốn kiểm tra một phụ thuộc hàm nào đó, giả sử X→Y có nằm trong bao đóng F của các phụ thuộc hàm, chúng ta có thể làm điều này rất hiệu quả mà không cần tính bao đóng F. Đầu tiên chúng ta tính bao đóng của thuộc tính X+ trên tập phụ thuộc hàm F, đó là một tập của các thuộc tính A trong đó X→ A có thể được suy diễn sư dụng hệ tiên đề Armstrong. Thuật toán trong Hình 4 đưa ra bao đóng của một tập X các thuộc tính.

Định lý 2 Thuật toán chỉ ra trong Hình 4 tính được tập thuộc tính là bao đóng X+ của tập thuộc tính X trên tập phụ thuộc hàm F.

Chứng minh định lý này được đề cập trong Bài 15. Thuật toán này có thể được thay đổi để tìm ra các khoá bằng cách bắt đầu từ tập X chỉ chứa một thuộc tính đơn và dừng ngay khi bao đóng chứa tất cả các thuộc tính trong lược đồ quan hệ. Bằng việc thay đổi thuộc tính khởi đầu và thứ tự các phụ thuộc hàm mà thuật toán xem xét chúng ta sẽ nhận được tất cả các khoá dự tuyển.

Dạng chuẩn Boyce-Codd

Giả sử R là một lược đồ quan hệ, F là một tập phụ thuộc hàm trên R, X là tập thuộc tính của R, và A là một thuộc tính nào đó của R. R ở dạng chuẩn Boyce Codd nếu, với tất cả các phụ thuộc hàm X→A trong F, một trong những câu sau là đúng:

• A∈ X; có nghĩa là đó là một phụ thuộc hàm trivial, hoặc
• X là một siêu khoá.

Trong một quan hệ BCNF, mỗi một bộ giá trị có thể được nghĩ như một thực thể hoặc một mối quan hệ, xác định bằng một khoá và các thuộc tính còn lại. Nếu chúng ta sử dụng hình oval để biểu diễn một thuộc tính hoặc một tập các thuộc tính và vẽ các cung để xác định các phụ thuộc hàm thì một quan hệ ở dạng BCNF có cấu trúc như Hình 5, để đơn giản minh hoạ này giả sử rằng chỉ có một khoá. (Nếu có một vài khoá dự tuyển, mỗi khoá dự tuyển đóng vai trò của KHOÁ, các thuộc tính khác không có một thuộc tính nào nằm trong khoá dự tuyển.)

Các phụ thuộc hàm trong quan hệ BCNF

BCNF đảm bảo rằng không có dư thừa nào được phát hiện mà chỉ sử dụng thông tin về phụ thuộc hàm. Vì thế nó là dạng chuẩn tốt nhất (đứng trên quan điểm dư thừa dữ liệu) nếu chúng ta chỉ đưa vào thông tin về phụ thuộc hàm. Nhận xét này được minh hoạ trong Hình 6.

Minh hoạ quan hệ ở dạng BCNF

Hình này chỉ ra (hai bộ giá trị trong) minh hoạ của một quan hệ có ba thuộc tính X, Y và A. Có hai bộ có cùng giá trị trong cột X. Bây giờ giả sử rằng chúng ta biết rằng minh hoạ này thoả mãn một phụ thuộc hàm là X→A. Chúng ta có thể nhìn thấy rằng một trong số các bộ giá trị có một giá trị a trong cột A. Chúng ta có thể suy diễn ra giá trị trong cột A của bộ giá trị thứ hai? Sử dụng phụ thuộc hàm này, chúng ta có thể kết luận rằng bộ giá trị thứ hai sẽ có giá trị là a trong cột này.

Nhưng trạng thái này không phải là một ví dụ của sự dư thừa? Chúng ta thấy giá trị a được lưu trữ hai lần. Điều này có được xảy ra trong một quan hệ ở dạng BCNF? Câu trả lời là KHÔNG! Nếu quan hệ này ở dạng BCNF, vì A được suy ra từ X nên X phải là một khoá. (Ngược lại, phụ thuộc hàm X→ A sẽ vi phạm BCNF). Nếu X là một khoá, thì y1=y2, có nghĩa la hai bộ giá trị này phải giống hệt nhau. Vì một quan hệ được định nghĩa là một tập các bộ giá trị, chúng ta không thể có hai bản ghi giống hệt nhau và tình trạng chỉ ra trong Hình 6 không thể xuất hiện.

Vì thế, nếu một quan hệ ở dạng BCNF, tất cả các trường của tất cả các bộ giá trị ghi lại một phần của thông tin, nó không thể được suy diễn (sử dụng chỉ các phụ thuộc hàm) từ các giá trị trong tất cả các trường khác trong (tất cả các bộ của) minh hoạ quan hệ đó.

Dạng chuẩn ba

Giả sử R là một lược đồ quan hệ, F là một tập các phụ thuộc hàm trên R, X là tập con các thuộc tính của R, và A là một thuộc tính nào đó của R. R ở dạng chuẩn ba nếu, với tất cả các phụ thuộc hàm X→ A trong F, một trong những điều kiện sau là đúng:

• A∈ X; có nghĩa là đó là một phụ thuộc hàm trivial, hoặc
• X là một siêu khoá, hoặc
• A là một phần của một khoá nào đó của R.

Định nghĩa của 3NF tương tự với định nghĩa của BCNF, chỉ khác nhau ở điều kiện thứ ba. Tất cả các quan hệ ở BCNF thì cũng ở 3NF. Để hiểu được điều kiện thứ ba, nhớ lại rằng khoá của một quan hệ là một tập tối thiểu các thuộc tính có thể xác định được tất cả các thuộc tính của quan hệ. A phải là một phần của khoá (bất kỳ khoá nào nếu quan hệ này có nhiều khoá). Việc tìm ra tất cả các khoá của một lược đồ quan hệ là một bài toán NP-đầy đủ, vì thế khó có thể xác định được một lược đồ quan hệ có ở dạng 3NF không.

Giả sử rằng có một phụ thuộc hàm X→A dẫn đến quan hệ vi phạm 3NF. Có hai trường hợp:

• X là một tập con hoàn toàn của một khoá K nào đó. Phụ thuộc hàm như thế này đôi khi được gọi là phụ thuộc hàm bộ phận. Trong trường hợp này, chúng ta lưu cặp (X,A) là dư thừa. Ví dụ, xem xét quan hệ Reserves có các thuộc tính SBDC như trong Phần 7.4. Khoá duy nhất là SBD, va chúng ta có phụ thuộc hàm S→ C. Chúng ta lưu lại mã số thẻ tín dụng của một thủy thủ nhiều lần bằng với số lần phục vụ của thuỷ thủ đó.
• X không phải là tập con hoàn toàn của bất kỳ khoá nào. Phụ thuộc hàm như thế này đôi khi được gọi là phụ thuộc hàm bắc cầu, vì nó có nghĩa là chúng ta có một chuỗi các phụ thuộc hàm K→X→A. Ví dụ, xem xét quan hệ Hourly_Emps với các thuộc tính SNLRWH trong phần 7.1. Khoá chỉ là S, nhưng có một phụ thuộc hàm R→W, như vậy chúng ta có chuỗi phụ thuộc hàm S→ R→W. Hậu qủa là chúng ta không thể lưu được một bản ghi về nhân viên S có rating R mà không biết lương tính theo giờ (hourly wage) ứng với rating này. Điều này dẫn đến các dị thường khi thêm, xóa và sửa dữ liệu.

Các phụ thuộc hàm bộ phận được minh hoạ trong Hình 7, và phụ thuộc hàm bắc cầu được minh hoạ trong Hình 8.

Phụ thuộc hàm bộ phận Phụ thuộc hàm bắc cầu

Tất cả các lược đồ quan hệ có thể được phân rã thành một tập các quan hệ ở dạng 3NF. Điều này không đúng với các quan hệ ở BCNF. Có lẽ vì thế mà chúng ta thoả hiệp là khi thiết kế các quan hệ nên đưa về dạng chuẩn 3. Như trong Chương 20, chúng ta đôi khi chấp nhận cả những quan hệ chưa phải là chuẩn 3 vì những lý do liên quan đến thực thi hệ thống.

Không giống BCNF, sự dư thừa có thể xảy ra với 3NF. Những vấn đề liên quan đến sự tồn tại của các phụ thuộc hàm bộ phận và bắc cầu, nếu có một phụ thuộc hàm nontrivial X→ A và X không là một siêu khoá, lúc này quan hệ này ở 3NF vì A là một phần của một khoá nào đó. Để hiểu được điều này, chúng ta cùng tìm hiểu quan hệ Reserves có các thuộc tính SBDC và một phụ thuộc hàm S→C minh hoạ ràng buộc một thuỷ thủ sử dụng một thẻ tín dụng duy nhất để nhận tiền phục vụ của mình. S không phải là một khoá, và C không phải là một phần của một khoá nào đó. (Thực tế, chỉ có một khoá là SBD). Do đó, quan hệ này không ở 3NF; cặp (S,C) lưu trữ dư thừa. Tuy nhiên, nếu chúng ta biết rằng thẻ tín dụng sẽ xác định duy nhất một chủ nhân, chúng ta sẽ có phụ thuộc hàm C→S, có nghĩa là CBD cũng là một khoá của Reserves. Vì thế, phụ thuộc hàm S→ C không vi phạm 3NF, và Reserves ở dạng 3NF. Tuy nhiên, trong tất cả các bộ giá trị chứa cùng giá trị S, cặp (S,C) bị lưu trữ dư thừa.

Chúng ta nhận thấy rằng định nghĩa của dạng chuẩn 2 về cơ bản không cho phép tồn tại các phụ thuộc hàm bộ phận. Vì thế, nếu một quan hệ ở dạng chuẩn ba (chuẩn không cho phép tồn tại cả phụ thuộc hàm bộ phận và phụ thuộc hàm bắc cầu) thì nó cũng ở dạng chuẩn hai.

Phân rã không mất kết nối

Giả sử R là một lược đồ quan hệ và F là tập các phụ thuộc hàm trên R. Một phân rã R thành hai lược đồ có các tập thuộc tính X và Y được gọi là một phân rã không mất kết nối trên tập F nếu, với tất cả các minh hoạ r của R thoả mãn các phụ thuộc hàm trong F, thì π _X(r) π _Y(r) = r. Nói các khác, chúng ta có thể khôi phục lại quan hệ ban đầu từ những quan hệ đã phân rã.

Bằng việc thay thế minh hoạ r trong Hình 9 bằng các minh hoạ π_SP(r) và π_PD(r), chúng ta thấy mất một số thông tin. Chúng ta có thể thấy rằng các bộ giá trị (s₁, p₁, d₃) và (s₃, p₁, d₁) không được quản lý. Vì thế, sự phân rã của lược đồ SPD thành SP và PD là có mất mát nếu như minh hoạ r trong hình này là đúng. (Quan sát ví dụ tương tự của quan hệ Contracts trong Phần 2.5.3).

Tất cả phân rã loại bỏ dư thừa phải là các phân rã không mất thông tin. Kiểm tra đơn giản sau đây rất hữu ích:

Định lý 3 Giả sử R là một quan hệ và F là tập các phụ thuộc hàm trên R. Sự phân rã R thành các quan hệ con với tập thuộc tính tương ứng là R₁ và R₂ không mất thông tin nếu và chỉ nếu F+ chứa phụ thuộc hàm R₁ Ç R₂ →R₁ hoặc phụ thuộc hàm R₁Ç R₂ → R₂.

Xem xét quan hệ Hourly_Emps một lần nữa. Nó có các thuộc tính SNLRWH, va phụ thuộc hàm R→W làm quan hệ vi phạm 3NF. Chúng ta loại bỏ vi phạm này bằng cách phân rã quan hệ thành hai quan hệ nhỏ hơn SNLRH và RW. Vì R là thuộc tính chung của cả hai quan hệ được phân rã và có phụ thuộc hàm R→W nên phân rã này là phân rã không mất kết nối.

Ví dụ này minh hoạ một quan sát phổ biến đi kèm với Định lý 3:

Nếu R có phụ thuộc hàm X→Y và X Ç Y là rỗng, thì phân rã R thành R-Y và XY là phân rã không mất mát.

X xuất hiện trong cả R-Y (vì X Ç Y bằng rỗng) và XY, và nó là một khoá của XY.

Một quan sát quan trọng khác, chúng ta phát biểu mà không chứng minh, phải làm với các phân rã lặp đi lặp lại. Giả sử rằng một quan hệ R được phân rã thành R1 và R2 thông qua phép phân rã không mất kết nối, và R1 được phân rã thành R11 và R12 thông qua một phép phân rã không mất mát khác. Vì thế, phép phân rã R thành R11, R12 và R2 là phép phân rã không mất kết nối; bằng việc nối R11 và R12 chúng ta khôi phục lại được R, và sau đó nối R1 với R2 ta khôi phục lại được R.

Phân rã bảo toàn phụ thuộc hàm

Xem xét quan hệ Contracts có các thuộc tính CSJDPQV trong Phần 3.1. Các phụ thuộc hàm của quan hệ này là: C→ CSJDPQV, JS→ C, và SD → P. Vì SD không phải là một khoá nên phụ thuộc hàm SD→P là nguyên nhân làm cho quan hệ này vi phạm BCNF.

Chúng ta có thể phân rã Contracts thành hai lược đồ quan hệ nhỏ hơn là CSJDQV và SDP để giải quyết vi phạm này; phân rã này không mất kết nối. Tuy nhiên có một vấn đề ở đây. Chúng ta có thể thực thi ràng buộc toàn vẹn JP → C dễ dàng khi một bộ giá trị được thêm vào quan hệ Contracts thì đảm bảo rằng không tồn tại bộ giá trị nào có cùng giá tri JP nhưng lại khác giá trị C. Khi chúng ta phân rã Contracts thành CSJDQV và SDP, việc thực thi ràng buộc này yêu cầu một phép kết nối đắt của hai quan hệ khi có bất kỳ một bộ giá trị nào được thêm vào CSJDQV. Chúng ta nói rằng phân rã này là không bảo toàn phụ thuộc hàm.

Để định nghĩa phân rã bảo toàn phụ thuộc hàm một cách chính xác, chúng tôi giới thiệu khái niệm về phép chiếu của các phụ thuộc hàm.

Giả sử R là một lược đồ quan hệ được phân rã thành hai lược đồ có tập thuộc tính là X và Y tương ứng, F là tập các phụ thuộc hàm trên R. Phép chiếu của F trên X là một tập các phụ thuộc hàm trong bao đóng F+ (không chỉ là F) mà chỉ gồm các thuộc tính trong X. Chúng ta ký hiệu phép chiếu của F trên tập thuộc tính X là F_X. Ghi nhớ rằng một phụ thuộc hàm U→ V nằm trong F+ chỉ khi tất cả các thuộc tính của U và V nằm trong X.

Phép phân rã của lược đồ quan hệ R (với các phụ thuộc hàm F) thành các lược đồ với các tập thuộc tính X và Y là phép phân rã bảo toàn phụ thuộc hàm nếu (F_XÈF_Y)+=F+. Tức là, nếu chúng ta lấy các phụ thuộc hàm trong F_X và F¬¬_Y và tính bao đóng của phép hợp giữa chúng, chúng ta sẽ được tất cả các phụ thuộc hàm trong bao đóng của F. Vì thế, chúng ta cần thực thi chỉ những ràng buộc trong F_X và F_Y; tất cả các phụ thuộc hàm trong F+ chắc chắn sẽ thoả mãn. Để thực thi F_X, chúng ta chỉ cần kiểm tra những quan hệ X (khi thêm bản ghi vào quan hệ này). Để thực thi F_Y, chúng ta chỉ cần kiểm tra quan hệ Y.

Để đánh giá đúng sự cần thiết phải xem xét bao đóng F+ trong khi tính phép chiếu của F, giả sử rằng một quan hệ R có các thuộc tính ABC được phân rã thành hai quan hệ AB và BC. Tập phụ thuộc hàm F trên R bao gồm A→B, B→C và C→A. Ở đây A→B ở trong F_AB và B→C ở trong F_BC. Nhưng phép phân rã này có bảo toàn phụ thuộc hàm không? Điều gì xảy ra đối với C→A?

Bao đóng của F chứa tất cả các phụ thuộc hàm trong F cộng với A→C, B →A và C→B. Kết quả là, F_AB cũng chứa B→A và F_BC chứa C→B. Vì thế, F_AB È F_BC chứa A→B, B → C, B → A, và C → B. Bao đóng của tập phụ thuộc hàm trong F_AB và F_BC bây giờ bao gồm C → A (được suy ra từ C → B, B → A, và luật bắc cầu). Vì thế, phép phân rã này bảo toàn được phụ thuộc hàm C → A.

Định nghĩa này cung cấp cho chúng ta thuật toán dễ hiểu để kiểm tra một phép phân rã nào đó có bảo tồn phụ thuộc hàm không. (Thuật toán này có độ phức tạp là hàm mũ của kích thước tập phụ thuộc hàm. Thuật toán có độ phức tạp đa thức được xem xét trong Bài tập 9.)

Chúng ta bắt đầu phần này bằng một ví dụ của phép phân rã không mất kết nối nhưng không bảo toàn phụ thuộc hàm. Các phép phân rã khác bảo toàn phụ thuộc hàm nhưng lại mất kết nối. Ví dụ đơn giản là quan hệ có các thuộc tính ABC và phụ thuộc hàm A→B và quan hệ này được phân rã thành AB và BC.

Phép phân rã thành BCNF

Bây giờ chúng ta trình bày một thuật toán để phân rã một lược đồ quan hệ R với tập phụ thuộc hàm F thành một tập các lược đồ quan hệ ở dạng BCNF:

1. Giả sử rằg R không ở BCNF. Giả sử X ⊂ R, A là một thuộc tính đơn trong R, và X→A là một phụ thuộc hàm gây ra sự vi phạm BCNF. Phân rã R thành R-A và XA.
2. Nếu R-A hoặc XA không ở BCNF, thì phân rã chúng tiếp tục bằng cách thực hiện đệ quy thuật toán này.

R-A là ký hiệu của tập các thuộc tính của R trừ thuộc tính A, và XA là ký hiệu của hai thuộc tính X và A. Vì X→A vi phạm BCNF, nó không phải là phụ thuộc hàm trivial; thêm nữa, A là một thuộc tính đơn. Vì thế, A không nằm trong X; tức là XÇA bằng rỗng. Vì thế, mỗi phân rã trong Bước 1 là phép phân rã không mất kết nối.

Tập các phụ thuộc hàm liên quan đến R-A và XA là phép chiếu của F trên các thuộc tính của chúng. Nếu một trong số các quan hệ mới không phải BCNF, chúng ta tiếp tục phân rã chúng trong Bước 2. Phép phép phân rã này cuối cùng cũng tạo ra được một tập các lược đồ quan hệ ở BCNF. Thêm nữa, phép nối các quan hệ thông qua thuật toán này sẽ cho ta được quan hệ ban đầu. (tức là, phép phân rã này không mất mát kết nối.)

Xem xét quan hệ Contracts có các thuộc tính CSJDPQV và khoáC. Chúng ta được cung cấp các phụ thuộc hàm JP → C và SD → P. Bằng việc sử dụng phụ thuộc hàm SD → P để thực hiện phân rã, chúng ta có hai lược đồ SDP và CSJDQV. SDP ở dạng BCNF. Giả sử rằng chúng ta cũng có ràng buộc là từ một dự án ta suy ra được đơn vị tài trợ: J → S. Như vậy, lược đồ CSJDQV không ởBCNF. Vì thế, chúng ta tiếp tục phân rã nó thành JS và CJDQV. Tất cả các lược đồ quan hệ SDP, JS, và CJDQV ởBCNF, và tập các lược đồ này là kết quả của phép phân rã không mất kết nối của CSJDQV.

Các bước của quá trình phân rã này có thể được biểu diễn dưới dạng một cây như Hình 10. Gốc của cây là quan hệ ban đầu CSJDPQV, và các lá là các quan hệ ở BCNF- kết quả của thuật toán phân rã: SDP, JS, và CSDQV. Như quan sát trên hình, mỗi nút trung gian là các con của nó sinh ra do phụ thuộc hàm được chỉ ra phía dưới nút.

Phân rã thành 3NF

Rõ ràng, cách tiếp cận chúng ta đã trình bày về phân rã không mất kết nối thành các quan hệ BCNF cũng sẽ áp dụng được để phân rã thành 3NF mà không mất kết nối. (Chúng ta có thể dừng lại dễ dàng hơn nếu chúng ta chấp nhận phân rã một quan hệ thành các quan hệ con chỉ ở 3NF). Nhưng cách tiếp cận này không đảm bảo sẽ bảo toàn được phụ thuộc hàm.

Một thay đổi đơn giản nhưng có thể thu được một phân rã thành các quan hệ 3NF mà thoả mãn cả hai điều kiện: bảo tồn phụ thuộc hàm và không mất kết nối. Trước khi chúng ta trình bày về thay đổi đơn giản này, chúng tôi cần giới thiệu khái niệm về phủ tối thiểu của một tập phụ thuộc hàm.

Phủ tối thiểu của một tập phụ thuộc hàm

Một phủ tối thiểu của một tập phụ thuộc hàm F là một tập G của các phụ thuộc hàm thoả mãn:

1. Tất cả các phụ thuộc hàm trong F đều ở dạng X→A, trong đó A là một thuộc tính đơn.
2. Bao đóng F+ bằng bao đóng G+.
3. Nếu chúng ta nhận được tập H của các phụ thuộc hàm từ tập G bằng việc xoá một hoặc nhiều phụ thuộc hàm hoặc xoá các thuộc tính từ một phụ thuộc hàm trong G thì F+ ≠ H+.

Phủ tối thiểu của một tập phụ thuộc hàm F là một tập phụ thuộc hàm tương đương và tối thiểu theo hai khía cạnh: (1) Tất cả các phụ thuộc hàm là nhỏ nhất có thể; có nghĩa là mỗi thuộc tính ở phía trái là thực sự cần đến và phía phải chỉ có một thuộc tính đơn. (2) Bao đóng của tất cả các phụ thuộc hàm ở trong đó bằng với F+.

Ví dụ, giả sử F là một tập các phụ thuộc hàm:

A→B, ABCD → E, EF → G, EF → H, và ACDF → EG.

Đầu tiên, chúng ta viết lại phụ thuộc hàm ACDF → EG để có được các phụ thuộc hàm mà bên phải chỉ là các thuộc tính đơn:

ACDF → E và ACDF → G.

Tiếp theo, xem xét phụ thuộc hàm ACDF→G. Phụ thuộc hàm có thể được suy diễn từ các phụ thuộc hàm sau:

A→ B, ABCD → E và EF → G.

Vì thế, chúng ta có thể xoá nó. Tương tự, chúng ta có thể xoá ACDF→ E. Xem xét tiếp ABCD→ E. Vì có A→B, chúng ta có thể thay nó bằng ACD→E. Vì thế, phủ tối thiểu của F là tập:

A→ B, ACD → E, EF → G, và EF → H.

Ví dụ trước cung cấp một thuật toán để tính được phủ tối thiểu của một tập phụ thuộc hàm F:

1. Đưa các phụ thuộc hàm về dạng chuẩn tắc: Tập phụ thuộc hàm G chỉ chứa các phụ thuộc hàm mà bên phải chỉ có một thuộc tính đơn.
2. Tối thiểu hoá phía trái của từng phụ thuộc hàm: Với mỗi phụ thuộc hàm trong G, kiểm tra mỗi thuộc tính ở phía trái để xem có thể xoá được nó mà vẫn bảo toàn sự tương đương với F+.
3. Xoá các phụ thuộc hàm dư thừa: Kiểm tra mỗi phụ thuộc hàm còn lại trong G để xem có thể xoá được nó mà vẫn bảo toàn được sự tương đương với F+.

Ghi nhớ rằng thứ tự áp dụng các phụ thuộc hàm có thể mang đến các phủ tối thiểu khác nhau; có thể có một vài phủ tối thiểu của một tập phụ thuộc hàm.

Một điểm quan trọng, chúng ta cần phải tối thiểu hoá phía bên trái của các phụ thuộc hàm trước khi kiểm tra các phụ thuộc hàm dư thừa. Nếu hai bước này bị đảo ngược, tập phụ thuộc hàm cuối cùng có thể vẫn chứa một số phụ thuộc hàm dư thừa (tức là, nó chưa phải là phủ tối thiểu), như minh hoạ ví dụ sau. Giả sử F là một tập các phụ thuộc hàm, mỗi phụ thuộc hàm đều đã ở dạng chuẩn tắc:

ABCD → E, E → D, A → B, và AC → D.

Quan sát thấy rằng ở đây không có phụ thuộc hàm nào dư thừa; nếu chúng ta kiểm tra phụ thuộc hàm dư thừa trước, chúng ta sẽ có phủ tối thiểu vẫn chính là tập này. Phía trái của phụ thuộc hàm ABCD→E có thể được thay thế bằng AC mà vẫn đảm bảo tương đương với F+, và chúng ta sẽ dừng lại ở đây nếu chúng ta kiểm tra phụ thuộc hàm dư thừa trước khi tối thiểu hoá phía trái. Tuy nhiên, tập phụ thuộc hàm này không phải là phủ tối thiểu.

AC→E, E→D, A→B, và AC→D.

Hai phụ thuộc hàm đầu tiên có thể suy ra được phụ thuộc hàm cuối cùng do luật bắc cầu, vì thế ta có thể xoá được nó mà vẫn bảo toàn được sự tương đương với F+. AC→D chỉ trở nên dư thừa sau khi chúng ta thay thế ABCD→E bằng AC→E. Nếu chúng ta tối thiểu phía trái trước sau đó mới kiểm tra các phụ thuộc hàm nào dư thừa thì chúng ta sẽ nhận được một tập gồm ba phụ thuộc hàm đầu tiên trong danh sách phía trên, đây mới là phủ tối thiểu thực sự.

Phân rã về 3NF bảo toàn phụ thuộc hàm

Trở lại vấn đề phân rã một quan hệ thành các quan hệ ở dạng 3NF bảo toàn phụ thuộc hàm và không mất kết nối, giả sử R là một quan hệ có tập phụ thuộc hàm F là một phủ tối thiểu, và giả sử R được phân rã thành các quan hệ R₁, R¬₂, …, R_n và phân rã này không mất kết nối. Với 1≤ i ≤ n, giả sử rằng R_i ở 3NF và giả sử rằng F_i là phép chiếu của F trên các thuộc tính của Ri. Thực hiện những công việc sau:

• Xác định tập N của các phụ thuộc hàm trong F mà không được bảo toàn, tức là nó không nằm trong bao đóng của phép hợp của F_is.
• Với mỗi phụ thuộc hàm X→A, tạo ra một lược đồ quan hệ XA và thêm nó vào phân rã của R.

Theo như ta đã biết, tất cả phụ thuộc hàm trong F được bảo tồn nếu chúng ta thay thế R bằng các Ri cộng với lược đồ có dạng XA ở bước trên. Các R_is đã cung cấp đều ở dạng 3NF. Chúng ta có thể thấy rằng mỗi lược đồ XA đều ở dạng 3NF: Vì X→A nằm trong phủ tối thiểu F, không tồn tại phụ thuộc hàm Y→A nào mà Y là tập con của X. Vì thế, X là khoá của XA. Thêm nữa, nếu có bất kỳ phụ thuộc hàm nào khác tồn tại trong XA, phía phải có thể bao gồm chỉ các thuộc tính trong X vì A là một thuộc tính đơn (vì X→A là một phụ thuộc hàm trong một phủ tối thiểu). Vì X là một khoá của XA nên không có phụ thuộc hàm nào khác có thể là nguyên nhân dẫn đến quan hệ này vi phạm 3NF (mặc dù chúng có thể gây ra vi phạm BCNF).

Để tối ưu hoá, nếu tập N chứa một số phụ thuộc hàm có cùng phía trái, giả sử X→A1, X →A2, ... , X → An. Chúng ta có thể