Tinh chỉnh lược đồ và các dạng chuẩn hoá
Thiết kế cơ sở dữ liệu mức khái niệm cung cấp cho chúng ta một tập các lược đồ quan hệ và các ràng buộc toàn vẹn, đây có thể được coi là điểm bắt đầu tốt để đến được kết quả thiết kế cơ sở dữ liệu cuối cùng. Những thiết kế ban đầu này phải được tinh chỉnh ...
Thiết kế cơ sở dữ liệu mức khái niệm cung cấp cho chúng ta một tập các lược đồ quan hệ và các ràng buộc toàn vẹn, đây có thể được coi là điểm bắt đầu tốt để đến được kết quả thiết kế cơ sở dữ liệu cuối cùng. Những thiết kế ban đầu này phải được tinh chỉnh bằng việc đưa các ràng buộc toàn vẹn vào thiết kế chi tiết chứ không đơn thuần là các cấu trúc của mô hình ER, điều kiện thực hiện và các luồng thực hiện đặc trưng. Trong chương này, chúng ta bàn về việc sử dụng các ràng buộc toàn vẹn để tinh chỉnh lược đồ khái niệm đạt được do chuyển từ một thiết kế mô hình ER thành một tập các quan hệ. Luồng thực hiện và những vấn đề khác được trình bày trong Chương sau.
Chúng ta tập trung vào một phần quan trọng của các ràng buộc gọi là các phụ thuộc hàm. Những loại khác của các ràng buộc toàn vẹn, ví dụ các phụ thuộc đa trị và các phụ thuộc liên kết cũng cung cấp những thông tin hữu ích. Đôi khi chúng có thể phát hiện ra các dư thừa mà các phụ thuộc hàm không tự mình phát hiện được. Chúng ta trình bày những phụ thuộc hàm này một cách tóm tắt.
Chương này được tổ chức như sau. Phần 1 là tổng quan về cách tiếp cận tinh chỉnh lược đồ đã trình bày trong chương này. Chúng tôi giới thiệu các phụ thuộc hàm trong Phần 2. Phần 3 chỉ ra những lý do để có được các phụ thuộc hàm bổ sung từ một tập phụ thuộc hàm cho trước. Phần 4 giới thiệu về các dạng chuẩn của quan hệ; một dạng chuẩn của một quan hệ được dùng làm thước đo về sự dư thừa trong quan hệ đó. Một quan hệ có dư thừa có thể được tách ra thành các quan hệ nhỏ hơn vẫn chứa những thông tin đó nhưng không còn dư thừa nữa. Chúng ta bàn về việc tách quan hệ và đặc điểm của nó trong Phần 5, và các quan hệ có thể tách thành các quan hệ nhỏ hơn ở dạng chuẩn mong muốn trong Phần 6.
Phần 7 trình bày một số ví dụ minh hoạ việc chuyển một thiết kế mô hình ER thành các lược đồ quan hệ, tuy nhiên các lược đồ này có thể vẫn còn sự dư thừa, và chúng ta bàn về cách thức tinh chỉnh những lược đồ này để loại bỏ dư thừa. Phần 8 trình bày về những loại phụ thuộc khác trong thiết kế cơ sở dữ liệu. Chúng tôi tổng kết những trình bày về chuẩn hoá dữ liệu bằng việc nghiên cứu ví dụ Cửa hàng Internet trong Phần 9.
Bây giờ, chúng tôi trình bày tổng quan về các vần đề mà tinh chỉnh lược đồ có thể giải quyết được và một cách tiếp cận tinh chỉnh dựa trên phân rã quan hệ. Mặc dù phân rã có thể tránh được dư thừa, nhưng nó có thể dẫn tới các vấn đề khác của bản thân nó nên chúng ta phải thận trọng khi sử dụng.
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.
Các giá trị rỗng
Việc sử dụng các giá trị rỗng có thể giải quyết được một số vấn đề trên. Như chúng ta nhìn thấy trong ví dụ, các giá trị rỗng không thể cung cấp một giải pháp trọn vẹn, nhưng chúng có thể cung cấp một số hỗ trợ.
Xem xét ví dụ quan hệ Hourly_Emps. Rõ ràng, các giá trị rỗng không thể giúp chúng ta loại bỏ được lưu trữ dư thừa hoặc là dị thường khi cập nhật. Nhưng dường như nó lại giải quyết được vấn đề dị thường khi thêm bộ và dị thường khi xoá bộ. Trong minh hoạ này, để đối phó với ví dụ dị thường khi thêm bộ, chúng ta có thể thêm một bộ giá trị của nhân viên (employee) với giá trị rỗng trong trường hourly_wages. Tuy nhiên, những giá trị rỗng này không giải quyết được tất cả các dị thường khi thêm bộ. Ví dụ, chúng ta không thể thêm vào một giá trị hourly_wage nào đó ứng với một rating trừ khi đã có một nhân viên có rating này, bởi vì chúng ta không thể lưu một giá trị rỗng trong trường ssn vì đây là khoá chính. Tương tự, để đối phó với ví dụ dị thường khi xoá bộ, chúng ta có thể nghĩ đến việc lưu một bộ giá trị với các giá trị rỗng trong tất cả các trường trừ trường rating và hourly_wages. Tuy nhiên, giải pháp này không thể thực hiện được vì trường khoá chính là ssn không thể nhận giá trị rỗng. Vì thế, các giá trị rỗng không phải là một giải pháp có thể giải quyết được vấn đề dư thừa, mặc dù chúng có thể được sử dụng để hỗ trợ trong một số trường hợp.
Sự dư thừa tăng lên khi các thuộc tính trong quan hệ có nhiều ràng buộc với nhau. Các phụ thuộc hàm (trong trường hợp này là các ràng buộc toàn vẹn) có thể được sử dụng để định nghĩa tình trạng này và được sử dụng để tinh chỉnh lược đồ. Rất nhiều vấn đề sinh ra do dư thừa có thể được hoá giải bằng việc phân rã lược đồ quan hệ lớn thành những lược đồ quan hệ ‘nhỏ hơn’.
Việc phân rã một lược đồ quan hệ R bao gồm việc thay thế một lược đồ quan hệ bằng hai (hay nhiều) lược đồ quan hệ nhỏ hơn chứa các thuộc tính của R và khi kết hợp các thuộc tính trong các lược đồ quan hệ nhỏ hơn này lại thì ta sẽ được lược đồ quan hệ R ban đầu. Trong phần này chúng ta xem xét việc phân rã thông qua vài ví dụ sau.
Chúng ta có thể phân rã quan hệ Hourly_Emps thành hai quan hệ nhỏ hơn:
Hourly-Emps2(ssn, name, lot, rating, hours_worked)
Wages(rating, hourly_wages)
Những minh hoạ dữ liệu của các quan hệ này tương ứng với minh hoạ dữ liệu của quan hệ Hourly_Emps trong Hình 1 được chỉ ra trong Hình 2.

Bằng cách lưu trữ như thế này chúng ta có thể dễ dàng ghi lại giá trị của hourly_wages ứng với bất kỳ giá trị nào của rating bằng việc bổ sung một bộ giá trị vào Wages dù cho là không có nhân viên nào có giá trị rating này trong minh hoạ hiện tại của quan hệ Hourly_Emps. Việc thay đổi lương (wage) tương ứng với xếp hạng (rating) của nhân viên được thực hiện chỉ đơn giản bằng việc cập nhật duy nhất một bộ giá trị của Wages. Cách làm này hiệu quả hơn rất nhiều so với phải cập nhật nhiều bộ giá trị như trong thiết kế ban đầu, và nó loại bỏ những vấn đề tiềm tàng nảy sinh do sự không nhất quán dữ liệu.
Trừ khi chúng ta rất cẩn thận, việc phân rã một lược đồ quan hệ có thể tạo ra nhiều khó khăn hơn là mang lại lợi ích. Hai câu hỏi quan trọng sau đây phải thường xuyên được lặp đi lặp lại:
- Quan hệ này có cần phải phân rã không?
- Những vấn đề nảy sinh do phân rã mang đến là gì?
Để trả lời câu hỏi thứ nhất, một số dạng chuẩn đã được đề xuất đối với quan hệ. Nếu một lược đồ quan hệ nằm trong số một trong những dạng chuẩn này, chúng ta sẽ biết được có những vấn đề nào không thể nảy sinh. Việc xem xét dạng chuẩn của một lược đồ quan hệ có thể giúp chúng ta đi đến quyết định có hoặc không phân rã nó. Nếu chúng ta quyết định một lược đồ quan hệ nào đó phải được phân rã, thì chúng ta phải chọn một phân rã cụ thể nào đó (ví dụ, một tập các quan hệ nhỏ hơn sẽ được thay thế cho một quan hệ ban đầu).
Đối với câu hỏi thứ hai, hai tính chất của việc phân rã phải được xem xét. Tính chất kết nối không mất thông tin sẽ giúp chúng ta khôi phục lại được bất kỳ minh hoạ dữ liệu của quan hệ ban đầu nào từ các minh hoạ dữ liệu của các quan hệ nhỏ hơn. Tính chất bảo toàn phụ thuộc hàm có thể giúp chúng ta áp đặt bất kỳ ràng buộc nào lên quan hệ ban đầu bằng việc áp đặt một số ràng buộc lên trên các quan hệ nhỏ hơn. Tức là, chúng ta không cần thực hiện việc nối các quan hệ nhỏ hơn lại để kiểm tra xem một ràng buộc nào đó trên quan hệ ban đầu có bị vi phạm không.
Trên quan điểm của việc thực hiện, các truy vấn trên quan hệ gốc có thể yêu cầu chúng ta phải kết nối các quan hệ nhỏ hơn đã được tách ra. Nếu những truy vấn này thường xuyên được yêu cầu, thì phân tách quan hệ có thể không được chấp nhận. Trong trường hợp này, chúng ta nên lựa chọn giải pháp là sống chung với vấn đề dư thừa và không nên phân rã quan hệ. Một điểm quan trọng là bạn phải ý thức được các vấn đề tiềm tàng nảy sinh do lưu trữ dư thừa và bạn phải làm một số việc để tránh chúng (ví dụ, bạn có thể thêm một số kiểm tra trong khi lập trình). Trong một số trường hợp, việc phân ra có thể cải thiện được việc thực hiện. Điều này xảy ra trong trường hợp, ví dụ, hầu hết các truy vấn và các kiểm tra cập nhật chỉ trên một quan hệ con nào đó. Chúng ta không bàn đến những ảnh hưởng của việc phân rã đối với thực thi truy vấn trong chương này; vấn đề này sẽ được tìm hiểu trong Phần 20.8.
Mục đích của chúng ta trong chương này là giải thích một số khái niệm quan trọng và các hướng dẫn khi thiết kế dựa trên lý thuyết của phụ thuộc hàm. Một người thiết kế cơ sở dữ liệu tốt nên hiểu rõ ràng về các dạng chuẩn, kỹ thuật phân rã quan hệ và các vấn đề tiềm tàng khi thực hiện phân rã. Ví dụ, người thiết kế thường đặt ra các câu hỏi như: Quan hệ đang ở dạng chuẩn nào? Phân tách có bảo toàn được phụ thuộc hàm không? Mục đích của chúng ta là giải thích khi nào cần nhấn mạnh những câu hỏi này và ý nghĩa của các câu trả lời.
Phụ thuộc hàm là một kiểu ràng buộc toàn vẹn cung cấp khái niệm của khoá. Giả sử R là một lược đồ quan hệ và X và Y là hai tập con không rỗng của các thuộc tính trong R. Chúng ta nói rằng một minh hoạ r của R thoả mãn phụ thuộc hàm X→Y nếu hai bộ bất kỳ t1 và t2 trong r thoả mãn:
Nếu t1.X =t2.X thì t1.Y=t2.Y.
Chúng ta sử dụng ký hiệu t1.X cho phép chiếu của bộ giá trị t1 trên các thuộc tính trong X. Một Phụ thuộc hàm X → Y nói rằng nếu hai bộ giá trị có cùng giá trị của X thì nó sẽ có cùng giá trị của Y.
Hình 3 minh hoạ ý nghĩa của phụ thuộc hàm AB → C bằng việc chỉ ra một trường hợp thoả mãn phụ thuộc hàm này. Hai bộ giá trị đầu tiên chỉ ra rằng một phụ thuộc hàm không giống như một ràng buộc khoá: Mặc dù phụ thuộc hàm này không bị vi phạm, AB rõ ràng không phải là khoá của quan hệ này. Các bộ giá trị thứ ba và bốn minh hoạ rằng nếu hai bộ giá trị khác nhau trong trường A hoặc trường B thì chúng có thể khác nhau trong trường C mà không vi phạm ràng buộc này. Tuy nhiên, nếu chúng ta thêm một bộ á a1, b1, c2, d2 ñ vào minh hoạ dữ liệu này thì kết quả sau khi thêm sẽ vi phạm ràng buộc này; để nhìn thấy vi phạm này, bạn hãy so sánh bộ giá trị đầu tiên trong hình minh hoạ với bộ giá trị mới thêm.

Nhớ lại rằng minh hoạ của một quan hệ chỉ đúng khi nó thoả mãn tất cả các ràng buộc toàn vẹn, bao gồm tất cả các phụ thuộc hàm. Như ghi nhớ trong Phần 3.2, các ràng buộc toàn vẹn được xác định dựa trên các nguyên tắc quản lý của bài toán. Khi xem một minh hoạ của một quan hệ, chúng ta có thể phát hiện ra được nó vi phạm một phụ thuộc hàm nào đó. Tuy nhiên, chúng ta không thể suy luận ra được có một phụ thuộc hàm tồn tại trong một quan hệ khi nhìn vào nhiều minh hoạ của nó, bởi vì một phụ thuộc hàm giống như ràng buộc toàn vẹn, nó phải được thoả mãn trên mọi minh hoạ dữ liệu của quan hệ.
Ràng buộc khoá chính là một trường hợp đặc biệt của phụ thuộc hàm. Các thuộc tính trong khoá đóng vai trò của X, và tập tất cả các thuộc tính trong quan hệ đóng vai trò của Y. Tuy nhiên, trong định nghĩa phụ thuộc hàm không yêu cầu X là tập tối thiểu; trong khi đó ràng buộc khoá chính thì yêu cầu X là tập tối thiểu. Nếu X → Y, trong đó Y là tập tất cả các thuộc tính, và có một số tập con V của X trong đó V→ Y thì X gọi là một siêu khoá.
Trong phần còn lại của chương này, chúng ta có một số ví dụ về các phụ thuộc hàm không phải là các ràng buộc khoá.
Cho một tập các phụ thuộc hàm trên một lược đồ quan hệ R, trong một số trường hợp có thể có các phụ thuộc hàm phát sinh trên R. Xem xét ví dụ:
Workers(ssn, name, lot, did, since)
Chúng ta biết rằng ssn→ did, vì ssn là khoá, và có phụ thuộc hàm did→lot trên Workers. Do đó, trong bất kỳ minh hoạ đúng của Workers, nếu hai bộ giá trị có cùng giá trị ssn, chúng phải có cùng giá cùng giá trị did (do phụ thuộc hàm đầu tiên), và bởi vì chúng có cùng giá trị của did, chúng phải có cùng giá trị của lot (do phụ thuộc hàm thứ hai). Vì thế, phụ thuộc hàm ssn → lot cũng phải có trên Workers.
Chúng ta giả sử rằng f là một phụ thuộc hàm được suy diễn từ tập phụ thuộc hàm F nếu tất cả các minh hoạ của f thoả mãn tất cả các phụ thuộc hàm trong F; tức là, f có tất cả các phụ thuộc hàm mà F nắm giữ. Ghi nhớ rằng tất cả các minh hoạ dữ liệu của f phải thoả mãn tất cả các phụ thuộc hàm trong F.
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.
Các dạng chuẩn
Cho một lược đồ quan hệ, chúng ta cần khẳng định xem đó có phải là một thiết kế tốt hay là chúng ta cần phải phân rã nó thành nhiều quan hệ nhỏ hơn. Khẳng định này phải được dẫn dắt dựa trên hiểu biết về những vấn đề gì sẽ xảy ra với lược đồ hiện tại. Để cung cấp dẫn dắt này, có một vài dạng chuẩn được đưa ra. Nếu một lược đồ quan hệ là một trong những dạng chuẩn này, chúng ta biết rằng có những vấn đề với dữ liệu sẽ không bao giờ xuất hiện.
Các dạng chuẩn đưa ra dựa trên tập các phụ thuộc hàm bao gồm dạng chuẩn 1 (1NF), dạng chuẩn 2 (2NF), dạng chuẩn 3 (3NF) và dạng chuẩn Boyce-Codd (BCNF).
Các dạng chuẩn này được sắp xếp theo thự tự tăng dần của các yêu cầu hạn chế dữ liệu: Tất cả các quan hệ ở dạng BCNF thì cũng đã ở dạng 3NF, tất cả các quan hệ ở dạng 3NF thì cũng đã ở dạng 2NF, tất cả các quan hệ ở dạng 2, 3NF thì cũng đã ở dạng 1NF. Một quan hệ ở dạng chuẩn 1 nếu tất cả các trường chứa những giá trị nguyên tử. Mặc dù một số hệ thống cơ sở dữ liệu mới đang làm suy yếu đi yêu cầu này, nhưng trong chương này chúng ta giả sử rằng yêu cầu này là bắt buộc. 2NF là chuẩn được quan tâm chủ yếu trong quá khứ. Trên quan điểm thiết kế cơ sở dữ liệu, 3NF và BCNF là hai chuẩn quan trọng.
Trong khi nghiên cứu về các dạng chuẩn, tập các phụ thuộc hàm đóng vai trò hết sức quan trọng. Xem xét một lược đồ quan hệ R có các thuộc tính ABC và có phụ thuộc hàm A→B. Như vậy, nếu có một vài bản ghi có cùng giá trị của A thì cũng phải có cùng giá trị của B. Khả năng dư thừa có thể dự đoán được bằng cách sử dụng thông tin về phụ thuộc hàm.
Chúng ta bàn về cách phát hiện dư thừa bằng sử dụng thông tin phụ thuộc hàm. Trong Phần 8, chúng ta trình bày về các ràng buộc toàn vẹn phức tạp hơn gọi là MVD, các phụ thuộc hàm liên kết và các dạng chuẩn dựa trên chúng.
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.

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.


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ã là một công cụ cho phép chúng ta loại bỏ dư thừa. Như ghi nhớ trong Phần 1.3, tuy nhiên, vấn đề quan trọng là phải kiểm tra để phân rã này không phát sinh những vấn đề mới. Cụ thể, chúng ta nên kiểm tra xem việc phân rã này có thể cho phép chúng ta khôi phục lại được quan hệ gốc không, và nó có cho phép chúng ta kiểm tra lại các ràng buộc toàn vẹn một cách hiệu quả không. Chúng ta sẽ bàn đến những tính chất này trong phần tiếp theo.
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ị (s1, p1, d3) và (s3, p1, d1) 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à R1 và R2 không mất thông tin nếu và chỉ nếu F+ chứa phụ thuộc hàm R1 Ç R2 →R1 hoặc phụ thuộc hàm R1Ç R2 → R2.
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à FX. 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 (FXÈFY)+=F+. Tức là, nếu chúng ta lấy các phụ thuộc hàm trong FX 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 FX và FY; tất cả các phụ thuộc hàm trong F+ chắc chắn sẽ thoả mãn. Để thực thi FX, 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 FY, 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 FAB và B→C ở trong FBC. 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à, FAB cũng chứa B→A và FBC chứa C→B. Vì thế, FAB È FBC chứa A→B, B → C, B → A, và C → B. Bao đóng của tập phụ thuộc hàm trong FAB và FBC 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.
Để hiểu được các khái niệm này cần phải hiểu được vai trò của các dạng chuẩn hoá và việc phân rã nó trong thiết kế cơ sở dữ liệu, chúng ta xem xét các thuật toán được sử dụng để chuyển một quan hệ thành các quan hệ con ở BCNF hoặc 3NF. Nếu một lược đồ quan hệ không ở BCNF, nó có thể được chuyển thành tập các lược đồ quan hệ BCNF bằng phép phân rã không mất kết nối. Nhưng đáng tiếc, phép phân rã này có thể không bảo toàn phụ thuộc hàm. Tuy nhiên, phép phân rã một lược đồ quan hệ thành các lược đồ quan hệ con ở dạng 3NF luôn bảo toàn được phụ thuộc hàm và không mất kết nối.
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:
- 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.
- 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.

Dư thừa trong BCNF
Phân rã CSJDQV thành SDP, JS, và CJDQV không bảo toàn phụ thuộc hàm. Phụ thuộc hàm JP→C không thể được bảo toàn mà không có kết nối. Một cách để giải quyết tình trạng này là thêm một quan hệ có các thuộc tính CJP. Nhưng hậu quả của giải pháp này là lưu trữ dư thừa thông tin.
Một điểm tinh tế: Mỗi lược đồ CJP, SDP, JS, và CJDQV đều ở BCNF, không có dư thừa nào có thể dự đoán được mà chỉ sử dụng thông tin phụ thuộc hàm. Cụ thể, nếu chúng ta nối các minh hoạ quan hệ của SDP và CJDQV và thực hiện phép chiếu lấy ra các thuộc tính CJP, chúng ta phải có chính xác minh hoạ quan hệ này trên lược đồ CJP. Chúng ta nhìn trong Phần 4.1 ở đây không có dư thừa trong một quan hệ BCNF đơn. Ví dụ này chỉ ra rằng dư thừa có thể vẫn xảy ra trên các quan hệ chéo mặc dù không có dư thừa trong từng quan hệ.
Những lựa chọn trong việc phân rã thành BCNF
Giả sử có một vài phụ thuộc hàm vi phạm BCNF. Tuỳ thuộc vào các phụ thuộc hàm này chúng ta có thể lựa chọn bước phân rã tiếp theo, chúng ta có thể thu được tập các quan hệ BCNF khác nhau tuỳ theo cách chúng ta lưa chọn thứ tự thực hiện các phụ thuộc hàm. Xem xét Contracts. Chúng ta vừa phân rã nó thành SDP, JS, và CJDQV. Giả sử chúng ta lựa chọn cách phân rã quan hệ ban đầu CSJDPQV thành JS và CJDPQV, dựa vào phụ thuộc hàm J → S. Chỉ còn hai phụ thuộc hàm trên CJDPQV là JP → C và phụ thuộc hàm khoá là C→CJDPQV. Vì JP là một khoá nên CJDPQV ở BCNF. Vì thế, lược đồ JS và CJDPQV là kết quả của phép phân rã không mất kết nối của quan hệ Contracts thành các quan hệ BCNF.
Những bài học ở đây là lý thuyết của phụ thuộc hàm, nó nói cho chúng ta khi nào có sự dư thừa và cung cấp cho chúng ta những manh mối về các phân rã có thể được sử dụng để giải quyết vấn đề này, nhưng nó không thể phân biệt được sự khác nhau giữa những khả năng phân rã. Người thiết kế phải xem xét những khả năng này và lựa chọn một trong số đó dựa vào ngữ cảnh của ứng dụng.
BCNF và Sự bảo toàn phụ thuộc hàm
Đôi khi, sự phân rã thành các quan hệ BCNF không bảo tồn được các phụ thuộc hàm. Ví dụ, xem xét một lược đồ quan hệ SBD, trong đó S (Sailor) là thuỷ thủ đã phục vụ trên tàu B (Boat) vào ngày D (Date). Nếu chúng ta có một phụ thuộc hàm SB→D (một thuỷ thủ phục vụ trên một tàu suốt cả ngày) và D→B, SBD không ở BCNF vì D không phải là khoá. Nếu chúng ta có gắng phân rã nó thì chúng ta không thể bảo tồn được phụ thuộc hàm SB→D.
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:
- 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.
- Bao đóng F+ bằng bao đóng G+.
- 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:
- Đư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.
- 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+.
- 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ệ R1, R¬2, …, Rn và phân rã này không mất kết nối. Với 1≤ i ≤ n, giả sử rằng Ri ở 3NF và giả sử rằng Fi 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 Fis.
- 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 Ris đã 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ể
- 1 Nội dung quản lý vốn đầu tư xây dựng cơ bản
- 2 Font chữ trong lập trình c trên windows
- 3 Mắm cáy
- 4 Mô hình hóa hệ thống phần mềm
- 5 Các hệ thống kiểm soát bay
- 6 Năng suất lao động và sự cần thiết phải nâng cao năng suất lao động
- 7 Mục đích, khái niệm, vai trò và ý nghĩa của bảng cân đối kế toán
- 8 Một số vấn đề lý luận về tiêu thụ sản phẩm ở các doanh nghiệp trong nền kinh tế thị trường
- 9 Phân tích môi trường marketing
- 10 Tổ chức là một khâu quyết định đối với việc thực hiện thắng lợi đường lối, chính sách của Đảng