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.
Giới thiệu về tinh chỉnh lược đồ
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.
Phân rã một lược đồ quan hệ
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.
Các vấn đề liên quan đến việc phân rã
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
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á.
Những tranh luận về phụ thuộc hàm
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.)
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.
Tính chất của sự phân rã
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.
Chuẩn hoá
Để 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ể thay thế chúng bằng một phụ thuộc hàm tương đương là X → Ai...An. Vì thế, chúng ta có được một lược đồ quan hệ XAi ...An, thay vì có một số lược đồ quan hệ XA1,… XAn.
Xem xét lược đồ quan hệ Contracts có các thuộc tính CSJDPQV và các phụ thuộc hàm JP → C, SD → P, và J → S. Nếu chúng ta tách CSJDPQV thành SDP và CSJDQV, thì SDP ở BCNF, nhưng CSJDQV không thậm chí ở 3NF. Vì thế chúng ta chia nó tiếp tục thành JS và CJDQV. Lược đồ quan hệ SDP, JS, và CJDQV ở 3NF (thực tế là ở BCNF), và sự phân rã này là không mất kết nối. Tuy nhiên, phụ thuộc hàm JP → C không được bảo toàn. Vấn đề này có thể được giải quyết bằng cách thêm một lược đồ quan hệ CJP vào phân rã này.
Tổng hợp thành 3NF
Chúng ta giả sử rằng quá trình thiết kế được khởi đầu từ một lược đồ ER, và các phụ thuộc hàm được sử dụng để hướng dẫn việc phân rã. Thuật toán thực hiện việc phân rã không mất kết nối và bảo toàn phụ thuộc hàm được trình bày trong phần trước (phân rã không mất kết nối thành 3NF) rất rõ ràng, và thuật toán này giải quyết việc bảo toàn phụ thuộc hàm bằng cách thêm vào các lược đồ quan hệ.
Một cách tiếp cận khác, gọi là tổng hợp, cách này đưa tất cả các thuộc tính vào một quan hệ R và xác định phủ tối thiểu của các phụ thuộc hàm F trên R và thêm một lược đồ quan hệ XA tới phân rã của R ứng với mỗi phụ thuộc hàm X→A trong F.
Tập kết quả chứa các lược đồ quan hệ đều ở 3NF và bảo toàn tất cả các phụ thuộc hàm.
Nếu nó không phải là phân rã không mất kết nối, chúng ta có thể giải quyết bằng việc thêm một lược đồ quan hệ chứa những thuộc tính xuất hiện trong một vài khoá.
Thuật toán này cung cấp cho chúng ta một phân rã thành các quan hệ 3NF mà bảo toàn phụ thuộc hàm và không mất kết nối và có độ phức tạp đa thức- để tính phủ tối thiểu có thể dùng các thuật toán có độ phức tạp đa thức, và một khoá có thể được tìm bằng thời gian là đa thức (mặc dù việc tìm tất cả các khoá được biết là bài toán NP-đầy đủ). Sự tồn tại của một thuật toán đa thức để thực hiện phân rã một lược đồ quan hệ thành các lược đồ con ở 3NF thật đáng kinh ngạc vì chúng ta biết rằng việc kiểm tra một lược đồ nào đó có ở dạng 3NF hay không là một bài toán NP-đầy đủ.
Ví dụ, xem xét lược đồ quan hệ ABC với các phụ thuộc hàm F={A → B, C → B}. Qua bước thực hiện đầu tiên ta thu được các lược đồ quan hệ AB và BC. Đây không phải là một phân rã không mất kết nối của ABC; AB Ç BC là B, và cả B→A và B→C đều không nằm trong F+. Nếu chúng ta thêm một lược đồ AC, chúng ta có được một phép phân rã không mất kết nối. Tập các quan hệ AB, BC và AC là kết quả của phép phân rã không mất kết nối và bảo toàn phụ thuộc hàm được thực hiện bằng cách sử dụng phép tổng hợp tốt hơn là tiến hành phân rã lặp. Chúng ta ghi nhớ rằng sự phân rã thực hiện theo cách tiếp cận tổng hợp phụ thuộc nhiều vào phủ tối thiểu sử dụng.
Ví dụ khác của cách tiếp cận tổng hợp, xem xét quan hệ Contracts có các thuộc tính CSJDPQV và các phụ thuộc hàm sau:
C → CSJDPQV, JP → C, SD → P, và J → S.
Tập phụ thuộc hàm này không phải là một phủ tối thiểu vì thế chúng ta cần tìm được một tập phủ tối thiểu nào đó. Đầu tiên, chúng ta thay thế C→ CSJDPQV bằng tập phụ thuộc hàm:
C → S, C → J, C → D, C → P, C → Q, và C→ V.
Phụ thuộc hàm C → P được suy diễn từ C → S, C → D, và SD → P; vì thế chúng ta có thể bỏ nó. Phụ thuộc hàm C → S được suy diễn từ C → J và J → S; vì thế chúng ta có thể xoá nó. Từ đó, chúng ta có phủ tối thiểu là:
C → J, C → D, C → Q, C → V, JS → C, SD → P, và J → S.
Sử dụng thuật toán này đảm bảo sự bảo toàn phụ thuộc hàm, chúng ta thu được các lược đồ quan hệ CJ, CD, CQ, CV, CJP, SDP, và JS. Chúng ta có thể cải tiến lược đồ này bằng cách kết hợp các quan hệ có C là khoá thành lược đồ CDJPQ V. Thêm nữa, chúng ta có SDP và JS trong phân rã của chúng ta.
So sánh phân rã này với phân rã đã thực hiện trong phần trước, chúng ta thấy chúng thực sự tương tự, chỉ có sự khác nhau là CDJPQV được thay bằng CJP và CJDQV. Nói chung, chúng không có sự khác biệt đáng kể.
Tinh chỉnh lược đồ trong thiết kế cơ sở dữ liệu
Chúng ta đã biết việc chuẩn hoá có thể giảm dư thừa như thế nào và cũng đã bàn đến một vài cách tiếp cận để chuẩn hoá một quan hệ. Bây giờ chúng ta đề cập đến cách áp dụng các ý tưởng này trong thực tế.
Người thiết kế cơ sở dữ liệu sử dụng một phương pháp thiết kế khái niệm, ví dụ như thiết kế ER để có được thiết kế cơ sở dữ liệu ban đầu. Từ đây, cách tiếp cận là phân rã lặp đi lặp lại được sử dụng để giảm dư thừa là cách tiếp cận tự nhiên nhất sử dụng các phụ thuộc hàm và các công nghệ chuẩn hoá.
Trong phần này, chúng ta tiến hành tinh chỉnh lược đồ sau khi thiết kế ER. Một câu hỏi ở đây là chúng ta có thể có được các quan hệ phân rã bằng cách chuyển từ lược đồ ER. Một thiết kế lược đồ ER tốt có thể ánh xạ ra một tập các quan hệ không có dư thừa không? Không may là thiết kế ER là một công việc phức tạp, nó có tính chủ quan và nhiều ràng buộc không biểu diễn được. Những ví dụ trong phần này được dùng để minh hoạ vì sao phân rã quan hệ sử dụng thiết kế ER có lẽ cần thiết.
Các ràng buộc trên một thực thể
Xem xét lại quan hệ Hourly_Emps. Ràng buộc chỉ ra thuộc tính ssn là một khoá có thể được biểu diễn như một phụ thuộc hàm:
{ssn} → {ssn, name, lot, rating, hourly_wages, hours_worked)
Để ngắn gọn, chúng ta viết như sau S→ SNLRWH, sử dụng một ký tự duy nhất ứng với mỗi thuộc tính và bỏ đi những ký tự cách. Thêm nữa, quan hệ này còn có ràng buộc từ thuộc tính hourly_wages có thể xác định được giá trị của thuộc tính rating: R→W.
Như chúng ta nhìn thấy trong Phần 1.1, phụ thuộc hàm này dẫn đến dư thừa trong lưu trữ. Nó không thể được biểu diễn bằng các khái niệm của mô hình ER. Chỉ những phụ thuộc hàm xác định tất cả các thuộc tính trong một quan hệ mới có thể biểu diễn được trong mô hình ER. Vì thế, chúng ta không thể nhận ra nó khi chúng ta xem xét Hourly_Emps trong quá trình xây dựng mô hình ER.
Chúng ta có thể đồng ý rằng vấn đề này có thể tránh được bằng cách thêm vào một tập thực thể gọi là Wage_Table (có các thuộc tính rating và hourly_wages) và một kiểu liên kết Has_Wages giữa hai bảng Hourly_Emps và Wage_Table. Tuy nhiên, không phải dễ dàng đạt được thiết kế tốt do quá trình mô hình hoá này bị ảnh hưởng nhiều bởi ý kiến chủ quan của người thiết kế. Việc có các công nghệ chuẩn để giải quyết vấn đề này và chỉ dẫn chúng ta tới một thiết kế tốt hơn là rất cần thiết. Giá trị của những công nghệ này không thể được đánh giá thấp khi thiết kế những lược đồ lớn có tới hàng trăm bảng.
Các ràng buộc trên một kiểu liên kết
Ví dụ trước minh hoạ như thế nào các phụ thuộc hàm có thể hỗ trợ tinh chỉnh những quyết định chủ quan đã thực hiện trong suốt quá trình thiết kế ER, nhưng chúng ta cũng đồng ý rằng một lược đồ ER tốt có thể cho chúng ta cùng một tập các quan hệ (giống với chúng ta tiếp cận bằng các công nghệ đã trình bày). Ví dụ tiếp theo chỉ ra rằng nhờ vào thông tin về phụ thuộc hàm, một thực thể có thể dẫn tới một tập các quan hệ chứ không chỉ là một quan hệ như là cách sử dụng thiết kế ER.
Chúng ta xem lại ví dụ trong Chương 2. Giả sử rằng chúng ta có kiểu thực thể Parts, Suppliers, và Departments, và kiểu liên kết Contracts giữa chúng. Lược đồ Contracts có các thuộc tính CQPSD. Một hợp đồng C (Contract) có contract idxác định rằng một nhà cung cấp S (supplier)sẽ cung cấp một số lượng Q của một mặt hàng P (part) cho đơn vị D (Departments). (Chúng ta thêm một trường contract id so với phiên bản của quan hệ Contracts đã trình bày trong Chapter 2.)
Chúng ta có một quy tắc là một đơn vị chỉ mua một loại sản phẩm ở một nhà cung cấp. Vì thế, nếu có một vài hợp đồng có cùng nhà cung cấp và đơn vị thì chúng phải có cùng giá trị của loại sản phẩm. Ràng buộc này là DS→ P.
Chúng ta lại gặp dư thừa và những vấn đề tồn tại do dư thừa sinh ra. Chúng ta có thể giải quyết tình trạng này bằng cách phân rã Contracts thành hai quan hệ có các thuộc tính CQSD và SDP. Quan hệ SDP ghi lại loại sản phẩm mà một nhà cung cấp bán cho một đơn vị, và quan hệ CQSD ghi lại những thông tin bổ sung của một hợp đồng. Nó không giống kết quả nhận được khi sử dụng mô hình ER, vì sử dụng cách này chúng ta chỉ thu được một quan hệ.
Xác định các thuộc tính của thực thể
Ví dụ này chỉ ra việc kiểm tra cẩn thận các phụ thuộc hàm có thể dẫn tới những hiểu biết tốt hơn về các thực thể và các kiểu liên kết giữa chúng; cụ thể nó chỉ ra rằng các thuộc tính có thể dễ dàng được gắn vào những thực thể ‘sai’ trong quá trình thiết kế ER. Lược đồ ER trong Hình 11 chỉ ra một kiểu liên kết gọi là Work_In tương tự với kiểu liên lết Work_In trong Chương 2 nhưng nó được thêm một ràng buộc khoá chỉ ra rằng một nhân viên có thể làm việc chỉ ở nhiều nhất một phòng. (Quan sát mũi tên kết nối từ Employees tới Works_In.)
Hình 11 Kiểu liên kết Works_In
Sử dụng ràng buộc khoá này, chúng ta có thể chuyển lược đồ ER này thành hai quan hệ:
Workers( ssn , name, lot, did, since)
Departments( did , dname, budget)
Kiểu thực thể Employees và kiểu liên kết Works_In được ánh xạ thành một quan hệ đơn Workers. Việc ánh xạ này dựa trên cách tiếp cận thứ hai trình bày trong Phần 2.4.1.
Bây giờ, giả sử rằng các nhân viên được chỉ định bãi để xe dựa vào phòng họ làm việc, và tất cả các nhân viên trong một phòng được chỉ định tới cùng một bãi đỗ xe. Ràng buộc này không được biểu diễn trong lược đổ của Hình 11. Đây là một ví dụ khác của một phụ thuộc hàm: did→lot. Dư thừa trong thiết kế này có thể được loại bỏ bằng việc phân rã quan hệ Workers thành hai quan hệ:
Workers2(sid, name, did, since)
Dept_Lots(did, lot)
Trong thiết kế mới này có nhiều lưu ý. Nó có thể thay đổi được chỗ để xe liên quan đến một phòng bằng cách cập nhật duy nhất một bộ giá trị trong quan hệ thứ hai. (tức là, không có dị thường khi cập nhật). Chúng ta có thể có một chỗ để xe ứng với một phòng ngay cả khi phòng đó hiện tại không có nhân viên nào mà không sử dụng các giá trị rỗng (tức là, không có dị thường khi xoá). Chúng ta có thể thêm một nhân viên vào một phòng nào đó bằng việc thêm một bộ giá trị vào quan hệ đầu tiên ngay cả khi nhân viên này chưa thuộc phòng nào (tức là, không có dị thường khi thêm bộ).
Việc kiểm tra hai quan hệ Departments và Dept_Lots, hai quan hệ này có cùng khoá, chúng ta thấy rõ rằng một bộ Departments và một bộ Dept_Lots có cùng giá trị khoá biểu diễn cùng một thực thể. Quan sát này được phản ánh trong lược đồ ER của hình 12.
Chuyển luợc đồ này thành mô hình quan hệ ta có:
Workers2(ssn, name, did, since)
Departments(did, dname, budget, lot)
Quan sát ta thấy chỗ để xe liên quan tới các nhân viên, mặt khác, các ràng buộc toàn vẹn cho thấy rằng trong ví dụ này chỗ để xe liên quan thực sự đến các phòng. Xử lý trong mô hình ER có thể bỏ xót điểm này. Thực hiện chuẩn hoá nghiêm khắc thì không.
Xác định kiểu thực thể
Xem xét một biến thể của lược đồ Reserves được sử dụng trong các chương trước. Giả sử Reserves chứa các thuộc tính S, B và D như trước, trong đó thuỷ thủ S có phục vụ trên tàu B vào ngày D. Thêm nữa, giả sử có một thuộc tính C ghi lại thẻ tín dụng để thanh toán tiền phục vụ cho thuỷ thủ. Chúng ta sử dụng ví dụ này để minh hoạ thông tin về phụ thuộc hàm có thể được sử dụng để tinh chỉnh thiết kế lược đồ ER như thế nào. Cụ thể, chúng tôi minh hoạ thông tin về phụ thuộc hàm được sử dụng để quyết định xem một khái niệm nào đó có thể được mô hình hoá như một thực thể hay là một thuộc tính.
Giả sử tất cả các 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. Ràng buộc này được biểu diễn bằng một phụ thuộc hàm S→C. Ràng buộc này chỉ ra rằng trong quan hệ Reserves chúng ta lưu lại mã số của thẻ tín dụng trong mỗi lần thuỷ thủ đó phục vụ, và chúng ta có sự dư thừa và những dị thường khi cập nhật. Để giải quyết vấn đề này chúng ta phân rã quan hệ Reserves thành hai quan hệ có các thuộc tính SBD và SC. Như vậy, một quan hệ lưu thông tin về sự phục vụ của thủy thủ, và một lưu thông tin về các thẻ tín dụng.
Chúng ta có thể nghĩ rằng thiết kế ER sẽ dẫn đến những quan hệ này. Một cách tiếp cận là giới thiệu một tập thực thể gọi là Credit_Card có một thuộc tính đơn là cardno, và một kiểu liên kết là Has_Card giữa hai quan hệ Sailors và Credit_Card. Với ghi nhớ là mỗi thẻ tín dụng do một thuỷ thủ sở hữu, chúng ta có thể ánh xạ Has_Card và Credit-Cards thành một quan hệ đơn có các thuộc tính SC. Chúng ta có lẽ không mô hình hoá những mã số thẻ tín dụng như các thực thể nếu mục đích chính của chúng ta đối với các mã số thẻ là để ghi lại thẻ tín dụng nào được sử dụng trong mỗi lần trả tiền phục vụ; trong trường hợp này ta chỉ cần sử dụng một thuộc tính để mô hình hóa nó.
Cách tiếp cận thứ hai là xem cardno là một thuộc tính của Sailors. Nhưng cách này rất không tự nhiên- một thuỷ thủ có lẽ có nhiều thẻ, và chúng ta không quan tâm đến tất cả các thẻ của họ. Chúng ta chỉ quan tâm đến một thẻ được sử dụng để trả tiền cho họ, như vậy tốt nhất trong trường hợp này là chúng ta mô hình hoá nó như một thuộc tính của kiểu liên kết Reserves.
Khi nghĩ về những vấn đề thiết kế của ví dụ này, cách hữu ích là đầu tiên chúng ta xem cardno là một thuộc tính của Reserves sau đó tinh chỉnh các bảng kết quả bằng cách sử dụng thông tin về phụ thuộc hàm. (Chúng ta có thể tinh chỉnh thiết kế này bằng cách thêm cardno vào bảng thu được từ Sailors hoặc bằng việc tạo một bảng mới có các thuộc tính SC).
Những kiểu khác của phụ thuộc hàm
Phụ thuộc hàm có lẽ là kiểu ràng buộc quan trọng và phổ dụng nhất đứng trên quan điểm của thiết kế cơ sở dữ liệu. Tuy nhiên, có một số kiểu phụ thuộc hàm. Cụ thể, có một lý thuyết đã được xây dựng tốt cho thiết kế cơ sở dữ liệu là các phụ thuộc hàm đa trị(MVD) và các phụ thuộc hàm liên kết. Bằng việc sử dụng những loại phụ thuộc hàm này, chúng ta có thể xác định được các vấn đề có thể dẫn đến dư thừa mà không phát hiện được khi chỉ sử dụng các phụ thuộc hàm đơn.
Phần này minh hoạ những loại dư thừa có thể phát hiện được bằng cách sử dụng MVD. Chúng ta cũng đề cập đến vai trò của phụ thuộc hàm inclusion trong thiết kế cơ sở dữ liệu.
Phụ thuộc hàm đa trị
Giả sử rằng chúng ta có một quan hệ gồm các thuộc tính course, teacher, và book, và được ký hiệu là CTB. Trong đó giáo viên T có thể dạy khoá học C, và quyển sách B là tài liệu của khoá học này. Ở đây không có phụ thuộc hàm nào; khoá của quan hệ là CTB. Tuy nhiên, tài liệu của khoá học phụ thuộc vào giáo viên dạy. Minh hoạ trong Hình 13 chỉ ra tình trạng này.
Lưu ý ba điểm ở đây:
- Lược đồ quan hệ CTB ở BCNF; vì thế chúng ta sẽ không nghĩ đến việc phân rã nó thêm nữa nếu chúng ta chỉ nhìn vào những phụ thuộc hàm của quan hệ này.
- Có sự dư thừa ở đây. Thực tế là giáo viên Green có thể dạy Physics101 được ghi lại một lần ứng với mỗi tài liệu của khoá học. Tương tự, Optics là tài liệu của môn học Physics101 được ghi lại một lần ứng với một giáo viên dạy.
- Sự dư thừa có thể được loại bỏ bằng cách phân rã CTB thành CT và CB.
Sự dư thừa trong ví dụ này là do có một ràng buộc là các tài liệu cho một khoá học phụ thuộc vào giáo viên dạy, điều này không thể biểu diễn được bằng khái niệm của các phụ thuộc hàm. Ràng buộc này là một ví dụ về MVD. Chúng ta sẽ mô hình hoá tình trạng này sử dụng hai kiểu liên kết nhị phân. Giáo viên (T) sẽ có các thuộc tính CT và Tài liệu(B) có các thuộc tính CB. Vì ở đây có hai mối liên kết độc lập, việc mô hình hoá chúng bằng một kiểu liên kết bậc ba cùng với các thuộc tính CTB là không phù hợp. (Xem phần 2.5.3 đã trình bày về sự khác nhau giữa mối liên kết bậc ba và mối liên kết bậc hai).Tuy nhiên nếu tiếp cận theo hướng thiết kế ER chúng ta sẽ tạo ra một kiểu liên kết bậc ba. Sau đó, phân tích cẩn thận thông tin về MVD sẽ phát hiện ra vấn đề này.
Giả sử R là một lược đồ quan hệ và giả sử X và Y là tập con của R. X→→Y được gọi là MVD trên R nếu, trên tất cả minh hoạ hợp lý r của R, mỗi giá trị X có một tập giá trị tương ứng trên Y và tập này độc lập với các giá trị trong các thuộc tính khác.
Chính thức, nếu có MVD X→→Y trên R và Z= R-XY, điều kiện sau phải đúng trên mọi minh hoạ hợp lý r của R:
Nếu t1 ∈ r, t2 ∈ r và t1.X=t2.X thì tồn tại một vài t3 ∈ r sao cho t3.XY = t1.XY và t2.Z=t3.Z.
Hình 14 minh hoạ định nghĩa này. Nếu chúng ta có hai bộ giá trị đầu tiên và nói rằng có MVD X→→Y trên quan hệ này, chúng ta có thể suy diễn rằng minh hoạ quan hệ này cũng phải chứa bộ thứ ba. Thực tế, bằng việc hoán đổi vai trò của hai bộ giá trị đầu tiên- xem bộ đầu tiên là bộ thứ hai và bộ thứ hai là bộ thứ nhất- chúng ta có thể suy ra rằng bộ giá trị thứ 4 cũng phải ở trong minh hoạ quan hệ này.
Bảng sau đề xuất một cách khác để nghĩ về MVD: Nếu có X→→Y trên R, thì π YZ(σ X=x(R)) = πY(σX=x(R)) ×πZ(σX=x(R)) trong tất cả các minh hoạ hợp pháp của R, với bất kỳ giá trị x nào xuất hiện trong cột X của R. Diễn đạt cách khác, xem xét các nhóm của các bộ giá trị trong R có cùng giá trị của X. Trong mỗi nhóm, xem xét phép chiếu trên các thuộc tính YZ. Phép chiếu này phải bằng với phép nhân chéo giữa các phép chiếu trên Y và Z. Tức là, giá trị X, các giá trị Y và các giá trị là độc lập. (Từ định nghĩa này ta có thể dễ dàng nhận ra rằng X→→Y tồn tại bất cứ khi nào X→Y tồn tại). Nếu tồn tại phụ thuộc hàm X→Y, thì có chính xác một giá trị Y ứng với một giá trị X nào đó và các điều kiện trong định nghĩa MVD đều thoả mãn. Không có điều ngược lại, như minh hoạ trong Hình 14).
Quay trở lại ví dụ CTB của chúng ta, ràng buộc về tài liệu của khoá học độc lập với giáo viên dạy có thể được biểu diễn bằng C→→T. Sử dụng các khái niệm của MVD, ràng buộc này có thể được đọc như sau:
Nếu (có một bộ giá trị nào đó chỉ ra rằng) C được dạy bằng giáo viên T,
và (có một bộ giá trị nào đó chỉ ra rằng) C có tài liệu là B,
thì (có một bộ giá trị nào đó chỉ ra rằng) C được dạy bởi T và tài liệu là B.
Cho một tập phụ thuộc hàm và các MVD, chúng ta có thể suy diễn ra một số các phụ thuộc hàm và MVD khác nhờ vào ba luật trong hệ tiên đề Armstrong và năm luật bổ sung. Ba luật bổ sung sau chỉ áp dụng cho các MVD:
- Luật bù cho MVD: Nếu X→→Y thì X→→R – XY.
- Luật tăng trưởng cho MVD: Nếu X→→Y và W ⊇ Z thì WX→→YZ.
- Luật bắc cầu cho MVD: Nếu X→→Y và X→→Z, thì X →→(Z –Y).
Xem một ví dụ sử dụng những luật này, vì chúng ta có C→→T trên quan hệ CTB. Luật bù của MVD cho phép chúng ta suy diễn ra C→→CTB – CT, tức là C→→B. Hai luật còn lại phối hợp giữa phụ thuộc hàm và MVDs:
- Tái tạo: Nếu X→Y thì X→→Y.
- Kết hợp: Nếu X→→Y và có một W mà WÇ Y rỗng, W→Z, và Y ⊇ Z thì X → Z.
Dạng chuẩn bốn
Dạng chuẩn bốn là dạng tổng quát trực tiếp của BCNF. Giả sử P là một lược đồ quan hệ, A và Y là các tập con không rỗng của P, và F là một tập phụ thuộc hàm có cả MVDs. P được gọi là dạng chuẩn bốn (4NF) nếu tất cả các MVD X→→Y trên R đều thoả mãn yêu cầu sau:
- Y ⊆ X hoặc XY = R, hoặc
- X là một siêu khoá.
Trong định nghĩa này, một điểm quan trọng phải lưu ý là định nghĩa của một khoá không thay đổi – khoá này phải xác định duy nhất tất cả các thuộc tính thông qua các phụ thuộc hàm. X→→Y là một trivial MVD nếu Y ⊆ X ⊆ R hoặc XY = R trivial.
Quan hệ CTB không ở dạng 4NF vì C→→ T là một nontrivial MVD và C không phải là khoá. Chúng ta có thể loại bỏ dư thừa bằng cách phân rã CTB thành CT và CB; mỗi quan hệ con này đều ở dạng 4NF.
Để sử dụng thông tin MVD đầy đủ, chúng ta phải hiểu về lý thuyết của MVDs. Nhiều khi chỉ sử dụng thông tin về FD cũng đủ để phát hiện được sự dư thừa mà không cần sử dụng đến thông tin về MVD. Vì thế, đôi khi chúng ta không cần xác định tất cả các MVDs.
Nếu một lược đồ quan hệ ở BCNF, và có ít nhất một trong các khoá của nó chứa một thuộc tính đơn, thì nó cũng ở 4NF.
Xem xét một lược đồ quan hệ ABCD và giả sử rằng nó có các FD: A→ BCD và MVD: B→→C. Xem xét chỉ những phụ thuộc hàm này, lược đồ quan hệ này như là phản ví dụ với kết quả. Quan hệ có một khoá, nó là BCNF và không phải là 4NF vì B→→C gây ra vi phạm chuẩn này. Hãy cùng chúng tôi xem xét nó kỹ càng hơn.
Hình 15 chỉ ra ba bộ giá trị trong minh hoạ ABCD thoả mãn MVD B→→C. Từ định nghĩa về MVD, nếu có hai bộ t1 và t2, thì bộ t3 cũng nằm trong minh hoạ này. Xem xét bộ t2 và t3. Từ phụ thuộc hàm A→ BCD và thực tế là hai bộ này có cùng giá trị của A, chúng ta có thể suy ra rằng c1=c2. Vì thế, chúng ta thấy rằng FD B→C cũng phải có trên ABCD bất cứ khi nào có FD A→ BCD và MVD B→→C. Nếu có B→→C, quan hệ ABCD sẽ không ở BCNF (trừ khi bổ sung phụ thuộc hàm để B là một khoá)!
Vì thế, phản ví dụ này lại không thực sự là phản ví dụ - mà nó minh hoạ sự quan trọng của việc xác định tất cả các FDs trên một quan hệ một cách đúng đắn. Trong ví dụ này, không chỉ có A→BCD là FD; mà còn có FD B→C nhưng nó không được xác định từ đầu. Với một tập FDs và MVDs cho trước, các luật suy diễn có thể được sử dụng để suy ra các FDs (MVDs) khác.
Phụ thuộc liên kết (Join Dependency)
Phụ thuộc liên kết là sự tổng quát hoá của MVDs. Một phụ thuộc liên kết (JD) 
{R1, …, Rn} được nói là có trên quan hệ R nếu R1, …, Rn là một phân rã không mất kết nối của R.
Một MVD X→→Y trên một quan hệ R có thể được biểu diễn như một JD 
{XY, X(R-Y)}. Ví dụ, trong quan hệ CTB, MVD C→→T có thể được biểu diễn như một JD 
{CT, CB}.
Không như FDs và MVDs, JDs không có các luật suy diễn đúng đắn và đầy đủ.
Dạng chuẩn năm
Một lược đồ quan hệ R được nói là ở dạng chuẩn năm(5NF) nếu với tất cả các phụ thuộc liên kết 
{R1, …, Rn} trên R, một trong những điều kiện sau đây đúng:
- Ri = R với một số i, hoặc
- JD được ngụ ý là một tập các FDs trên R mà phía trái của chúng là một khoá của R.
Điều kiện thứ hai xứng đáng có một vài giải thích, vì chúng ta không trình bày các luật suy diễn cho các FDs và JDs cùng nhau. Chúng ta phải có thể chỉ ra rằng việc phân rã R thành {R1, …, Rn} là không mất kết nối bất cứ khi nào có phụ thuộc khoá (FDs mà phía trái của nó là khoá của R). JD 
{R1, …, Rn} là một trivial JD nếu Ri=R với một số i.
Nếu một lược đồ quan hệ ở 3NF và mỗi khoá của nó chứa một thuộc tính đơn thì nó cũng ở 5NF.
Nhận xét trên rất hữu ích trong thực tế vì nó cho phép chúng ta kết luận được một quan hệ nào đó ở 5NF mà không cần xác định các MVDs và JDs trên quan hệ đó.
Các phụ thuộc bao gồm (Inclusion Dependencies)
MVDs và JDs có thể được sử dụng để hướng dẫn thiết kế cơ sở dữ liệu, mặc dù chúng ít phổ biến hơn là FDs và khó hơn để nhận và suy luận ra nó. Ngược lại, phụ thuộc bao gồm (IDs) rất phổ biến và dễ nhận ra. Tuy nhiên, chúng lại ít ảnh hưởng đến việc thiết kế cơ sở dữ liệu (dựa trên thiết kế ER).
Một ID có dạng là một vài cột của một quan hệ nằm trong những cột khác (thường là quan hệ thứ hai). Ràng buộc khoá là một ví dụ của một ID; (các) cột tham chiếu trong một quan hệ phải nằm trong (các) cột khoá chính của quan hệ được tham chiếu. Ví dụ, nếu R và S là hai quan hệ đạt được bằng việc ánh xạ hai kiểu thực thể mà tất cả thực thể R cũng là thực thể của S; chúng ta sẽ có một ID; phép chiếu lấy ra các thuộc tính khoá trên R cũng bằng với trên S.
Một điểm cần phải nhớ là chúng ta không nên chia tách các nhóm thuộc tính tham gia trong một ID. Ví dụ, chúng ta có một phụ thuộc bao gồm AB⊆ CD, nếu phân rã lược đồ quan hệ chứa AB, chúng ta nên chắc chắn rằng có ít nhất một lược đồ kết quả chứa cả A và B. Nếu không thì chúng ta không thể kiểm tra được phụ thuộc bao gồm AB ⊆ CD mà không xây dựng lại quan hệ chứa AB.
Trong thực tế hầu hết các ID đều dựa trên khoá, tức là chỉ bao gồm các khoá. Các ràng buộc khoá ngoại là một ví dụ của ID dựa trên khoá. Một lược đồ ER chứa các phân cấp ISA (xem Phần 2.4.4) cũng dẫn đến các ID dựa trên khoá. Nếu tất cả các ID đều dựa trên khoá thì hiếm khi chúng ta phải lo lắng về việc phân chia nhóm thuộc tính tham gia trong IDs, vì việc phân rã thường không phân tách khoá chính. Tuy nhiên, nhớ là việc chuyển từ 3NF thành BCNF luôn phải phân tách một số khoá (không phải là khoá chính là tốt nhất!).
Trường hợp nghiên cứu: CỬA HÀNG INTERNET
Nhớ lại trong Phần 3.8 DBDudes đã chấp nhận lược đồ sau:
Books(isbn: CHAR(10),title: CHAR(8), author: CHAR(80), qty_in_stock: INTEGER, price: REAL, year_published: INTEGER)
Customers(cid: INTEGER, cname: CHAR(80), address: CHAR(200))
Orders( ordernum: INTEGER, isbn: CHAR(10),cid: INTEGER,
cardnum: CHAR(16), qty: INTEGER, order_date: DATE, ship_date: DATE)
DBDudes phân tích tập các quan hệ xem có sự dư thừa không. Quan hệ Book chỉ có một khoá là (isbn), và không có phụ thuộc hàm nào. Vì thế Books ở dạng BCNF. Quan hệ Customers cũng chỉ có một khoá là (cid) và không có phụ thuộc hàm nào. Vì thế, Customers cũng ở BCNF.
DBDudes cũng xác định cặp á ordernum, isbn ñ là khoá của bảng Orders. Thêm nữa, vì mỗi hoá đơn (order) được một khách hàng đặt vào một ngày xác định cùng với mã tài khoản xác định, nên quan hệ này có ba phụ thuộc hàm sau:
ordernum → cid, ordernum → order_date, và ordernum → cardnum
Các chuyên gia ơ DBDudes kết luận rằng quan hệ Orders thậm chí không ở 3NF. (Bạn có thể nhìn thấy vì sao?). Họ quyết định phân rã Orders thành hai quan hệ:
Orders(ordernum, cid, order_date, cardnum), và
Orderlists(ordernum,isbn, qty, ship_date)
Kết quả là cả hai quan hệ này đều ở BCNF, và việc phân rã này không mất kết nối vì ordernum là một khoá của Orders (mới). Người đọc nên kiểm tra lại xem phân rã này có bảo toàn phụ thuộc hàm không.
Cuối cùng, chúng tôi cung cấp SQL DDL của quan hệ Orders và Orderlists như sau:
CREATE TABLE Orders ( ordernum INTEGER,
cid INTEGER,
order_date DATE,
cardnum CHAR(16),
PRIMARY KEY (ordernum),
FOREIGN KEY (cid) REFERENCES Customers)
CREATE TABLE Orderlists(ordernum INTEGER,
isbn CHAR(10),
qty INTEGER,
ship_date DATE,
PRIMARY KEY (ordernum, isbn),
FOREIGN KEY (isbn) REFERENCES Books)
Câu hỏi ôn tập
Trả lời những câu hỏi sau, phần gợi ý được chỉ ra bên cạnh.
- Giải thích về sự dư thừa và những vấn đề nó có thể gây ra. Cung cấp những ví dụ về dị thường khi thêm, xoá, và cập nhật. Các giá trị rỗng có thể giúp giải quyết những vấn đề này? Chúng có phải là những giải pháp đầy đủ? (Phần 1.1)
- Phân rã là gì và nó giải quyết vấn đề dư thừa như thế nào? Những vấn đề gì có thể xảy ra khi sư dụng phân rã? (Phần 1.1 và 1.3)
- Định nghĩa các phụ thuộc hàm (FDs). Khoá chính liên quan đến FDs như thế nào? (Phần 2)
- Khi nào một phụ thuộc hàm f được suy diễn từ một tập F các FDs? Định nghĩa Tiên đề Amstrong’s, và giải thích câu sau: “Chúng là một tập các luật đầy đủ và đúng đắn để suy diễn phụ thuộc hàm” (Phần 3)
- Bao đóng F+ của một tập F các FDs là gì? Bao đóng X+ của một tập các thuộc tính X trên tập các phụ thuộc hàm F là gì? (Phần 3)
- Định nghĩa 1NF, 2NF, 3NF và BCNF. Động cơ để đưa một quan hệ về BCNF là gì? Động cơ để đưa một quan hệ về 3NF là gì? (Phần 4)
- Khi nào một phân rã của một lược đồ quan hệ P thành hai lược đồ quan hệ X và Y được nói là một phân rã không mất kết nối? Vì sao tính chất này lại rất quan trọng? Cung cấp điều kiện cần và đủ để kiểm tra một phân rã là không mất kết nối. (Phần 5.1)
- Khi nào một phân rã được gọi là bảo toàn phụ thuộc? Vì sao tính chất này thực sự hữu ích? (Phần 5.2)
- Chúng ta có thể thu được một phân rã không mất kết nối từ một quan hệ thành các quan hệ con ở BCNF như thế nào? Cung cấp một ví dụ để chỉ ra rằng có thể có phân rã về BCNF không bảo toàn phụ thuộc. Một quan hệ có thể được phân rã theo các cách khác nhau để đạt được các kết quả phân rã khác nhau. (Phần 6.1)
- Phủ tối thiểu của một tập FDs là gì? Trình bày một thuật toán để tính toán phủ tối thiểu của một tập FDs và minh hoạ nó bằng một ví dụ. (Phần 6.2)
- Trình bày như thế nào thuật toán phân rã thành BCNF không mất kết nối lại có thể tương thích để có được phân rã thành 3NF không mất kết nối và bảo toàn phụ thuộc. Trình bày phép tổng hợp để thu được một phân rã thành 3NF như vậy. Minh hoạ cả hai cách tiếp cận bằng một ví dụ. (Phần 6.2)
- Trình bày cách thức tinh chỉnh lược đồ thông qua phân tích phụ thuộc và chuẩn hoá có thể cải thiện được lược đồ thu được từ thiết kế ER. (Phần 7)
- Định nghĩa phụ thuộc đa trị, phụ thuộc liên kết, và phụ thuộc bao gồm. Trình bày việc sử dụng những phụ thuộc này trong thiết kế cơ sở dữ liệu. Định nghĩa 4NF và 5NF, và giải thích vì sao chúng tránh được những loại dư thừa mà BCNF không loại trừ được. Trình bày cách thức kiểm tra một quan hệ ở 4NF và 5NF mà chỉ sử dụng FDs. (Phần 8)
Bài tập
Trả lời tóm tắt những câu hỏi sau:
- Định nghĩa khái niệm phụ thuộc hàm.
- Vì sao có một số phụ thuộc hàm gọi là trivial?
- Đưa ra một tập phụ thuộc hàm trên lược đồ R(A,B,C,D) trong đó AB là khoá chính để R ở 1NF nhưng không ở 2NF.
- Đưa ra một tập phụ thuộc hàm trên lược đồ R(A,B,C,D) trong đó AB là khoá chính để R ở 2NF nhưng không ở 3NF.
- Xem xét lược đồ quan hệ R(A,B,C) có FD B→C. Nếu A là một khoá dự tuyển của R thì R có thể ở BCNF không? Nếu có thì phải có những điều kiện gì? Nếu không, giải thích vì sao.
- Giả sử chúng ta có một lược đồ quan hệ R(A,B,C) biểu diễn mối liên kết giữa hai kiểu thực thể có khoá A và B, giả sử R có các phụ thuộc hàm A→B và B→A. Giải thích ý nghĩa của cặp phụ thuộc hàm này.
1. Giả sử R là một lược đồ quan hệ và giả sử X, Y là hai tập con của tập các thuộc tính của R. Chúng ta nói Y là phụ thuộc hàm trên X, viết là X→Y, nếu như các giá trị của Y được xác định bằng các giá trị của X. Nói cách khác, với bất kỳ hai bộ giá trị r1 và r2 trong (bất kỳ minh họa của) R:
π X(r1) = πX (r2) ⇒ πY (r1) = πY(r2)
2. Một số phụ thuộc hàm được coi là trivial (không có giá trị) vì chúng chứa các thuộc tính không cần thiết – những thuộc tính không cần được liệt kê. Xem xét phụ thuộc hàm: A→ AB. Vì A luôn suy ra A, nên thuộc tính A bên phía phải là không cần thiết và có thể xóa đi được. Dạng chính xác không có phụ thuộc hàm trivial là: A→B.
3. Xem xét tập các phụ thuộc hàm: AB → CD và B → C. ABhiển nhiên là khóa của quan hệ này vì AB→CD nên AB→ABCD. Nó là một khóa chính vì ở đây không có tập nào nhỏ hơn tập này có thể làm khóa trên R(A, B, C, D). Phụ thuộc hàm: B→C vi phạm 2NF vì:
- C Є B là sai; tức là nó không phải là một trivial FD.
- B không phải là siêu khóa.
- C không phải là một phần của một khóa nào đó trên R.
- B là tập con của khóa AB.
4. Xem xét tập phụ thuộc hàm: AB → CD và C → D. AB rõ ràng là khóa của quan hệ này vì AB → CD nên suy ra AB → ABCD. Nó là một khóa chính vì không có tập con nào của nó có thể làm khóa trên R (A, B, C, D). Phụ thuộc hàm: C → D vi phạm 3NF nhưng không vi phạm 2NF vì:
- D Є C là sai; tức là, nó không phải là một trivial FD.
- C không phải là một siêu khóa
- D không phải là một phần của một khóa nào đó trên R.
5. Cách duy nhất để R ở dạng BCNF là B chứa một khóa nào đó, tức là B là một khóa của R.
6. Nó có nghĩa là mối quan hệ này là một-một. Tức là một thực thể A tương ứng với duy nhất một thực thể B và ngược lại.
Xem xét quan hệ R với 5 thuộc tính ABCDE. Bạn được cho các phụ thuộc hàm sau: A → B, BC → E, và ED → A.
1. Liệt kê các khóa của R.
2. R ở dạng 3NF không?
3. R ở dạng BCNF không?
Dành cho độc giả.
Xem xét quan hệ trong Hình 1.
1. Liệt kê danh sách các phụ thuộc hàm thỏa mãn minh họa quan hệ này.
2. Giả sử rằng giá trị của thuộc tính Z ở bản ghi cuối cùng trong quan hệ này được thay đổi từ z3 thành z2. Bây giờ liệt kê tất cả các phụ thuộc hàm mà minh họa quan hệ này thỏa mãn.
1. Danh sách các hàm phụ thuộc trên R:
Z → Y, X → Y, và XZ → Y
2. Tương tự phần 1. Tập phụ thuộc hàm không thay đổi.
Giả sử bạn được cung cấp một quan hệ với các thuộc tính ABCD.
1. Giả sử rằng không có bản ghi nào có các giá trị rỗng. Viết một truy vấn SQL kiểm tra xem có tồn tại phụ thuộc hàm A→B.
2. Một lần nữa giả sử rằng không có bản ghi nào có giá trị rỗng. Viết một câu lệnh SQL để thiết đặt ràng buộc A→B cho quan hệ này.
3. Giả sử rằng các bản ghi này có thể có các giá trị rỗng. Thực hiện hai câu hỏi trên với giả thiết này.
Dành cho độc giả
Xem xét tập các quan hệ và các phụ thuộc hàm sau đây. Giả sử mỗi quan hệ có được thông qua việc phân rã quan hệ gồm các thuộc tính ABCDEFGHI và tất cả các phụ thuộc hàm trên quan hệ ABCDEFGHI được liệt kê trong mỗi câu hỏi. (Các câu hỏi này là độc lập với nhau). Đối với mỗi quan hệ (con): (a) Dạng chuẩn lớn nhất của quan hệ này là dạng nào? (b)Nếu không ở dạng BCNF, thì hãy phân rã nó thành một tập các quan hệ ở dạng BCNF?
1. R1(A,C,B,D,E), A → B, C → D
2. R2(A,B,F), AC → E, B → F
3. R3(A,D), D → G, G → H
4. R4(D,C,H,G), A → I, I → A
5. R5(A,I,C,E)
1. 1NF. Phân rã BCNF: AB, CD, ACE.
2. 1NF. Phân rã BCNF: AB, BF
3. BCNF.
4. BCNF.
5. BCNF.
Giả sử chúng ta có ba bộ giá trị sau trong một minh họa đúng của lược đồ quan hệ S cùng với ba thuộc tính ABC (được liệt kê theo thứ tự): (1,2,3), (4,2,3) và (5,3,3)
1. Phụ thuộc hàm nào sau đây không nằm trên lược đồ S?
(a) A → B, (b) BC → A, (c) B → C
2. Bạn có thể chỉ ra phụ thuộc nào có trên lược đồ S?
Dành cho độc giả
Giả sử bạn được cung cấp một quan hệ R với 4 thuộc tính ABCD. Với mỗi tập phụ thuộc hàm sau, thực hiện các yêu cầu: (a) Chỉ ra các khóa dự tuyển của R. (b) Xác định dạng chuẩn cao nhất mà R thỏa mãn (1NF, 2NF, 3NF, BCNF). (c) Nếu R không ở dạng BCNF, hãy phân rã nó về các quan hệ ở dạng BCNF mà vẫn bảo toàn phụ thuộc hàm:
1. C → D, C → A, B → C
2. B → C, D → A
3. ABC → D, D → A
4. A → B, BC → D, A → C
5. AB → C, AB → D, C → A, D → B
1. (a) Khóa dự tuyển là: B.
(b) R ở dạng 2NF nhưng không phải là 3NF.
(c) C → D và C → A, cả hai đều vi phạm BCNF. Có một cách phân rã mà vẫn duy trì được phụ thuộc hàm là phân tích R thành AC, BC và CD.
2. (a) Khóa dự tuyển là BD.
(b) R ở dạng 1NF nhưng không ở dạng 2NF.
(c) B → C và D → A, cả hai đều vi phạm BCNF. Phân rã thành: AC, BC và BD (nhận được từ phân rã đầu tiên thành AD và BCD) ở dạng BCNF mà vẫn bảo toàn dữ liệu và liên kết.
3. (a) Khóa chính là ABC, BCD
(b) R ở dạng 3NF nhưng không ở dạng BCNF.
(c) ABCD không ở dạng BCNF vì D → A và D không phải là khóa. Tuy nhiên nếu chúng ta phân rã R thành AD, BCD thì chúng ta không thể bảo toàn được phụ thuộc hàm ABC → D. Như vậy ở đây không thể phân rã thành BCNF.
4. (a) Khóa dự tuyển là: A.
(b) R ở dạng 2NF nhưng không ở dạng 3NF (vì có phụ thuộc hàm BC → D).
(c) BC → D vi phạm BCNF vì BC không chứa khóa. Vì thế, chúng ta phân rã R thành: BCD, ABC.
5. (a) Khóa dự tuyển là: AB, BC, CD, AD
(b) R ở dạng 3NF nhưng không là BCNF vì có phụ thuộc hàm : C → A.
c) C → A và D → B, cả hai đều dẫn đến vi phạm. Vì thế phân rã thành: AC, BCD nhưng việc này không bảo toàn được phụ thuộc hàm AB → C và AB → D, và BCD vẫn không ở dạng BCNF vì phụ thuộc hàm D → B. Vì vậy chúng ta cần phân rã tiếp: AC, BD, CD. Tuy nhiên khi chúng ta cố gắng không để mất các phụ thuộc hàm bằng cách thêm vào ABC và ABD, thì những quan hệ này không còn ở dạng BCNF. Vì vậy quan hệ này không thể được phân rã thành BCNF.
Xem xét tập thuộc tính R= ABCDEGH và các phụ thuộc hàm: F = {AB →C, AC → B, AD → E, B → D, BC → A, E → G}.
1. Với mỗi tập thuộc tính, thực hiện các công việc sau: (i) Tính toán tập các phụ thuộc hàm trên tập thuộc tính này và viết ra một tập tối thiểu. ii) Tên dạng chuẩn cao nhất không bị vi phạm bởi quan hệ chứa những thuộc tính này. (iii) Phân rã quan hệ này thành tập các quan hệ ở BCNF nếu nó không ở BCNF.
(a) ABC, (b) ABCD, (c) ABCEG, (d) DCEGH, (e) ACEH
2. Khi phân rã R = ABCDEG thành các quan hệ con sau, vẫn với tập các phụ thuộc hàm F như trên, các quan hệ này có: (a) bảo toàn phụ thuộc hàm? b) không mất mát liên kết?
(a) {AB, BC, ABDE, EG}
(b) {ABC, ACDE, ADG}
Dành cho độc giả.
Giả sử R được phân rã thành R1, R2,..., Rn. Giả sử F là tập các phụ thuộc hàm trên R.
1. F được bảo toàn trong tập các quan hệ được phân rã có nghĩa là gì?
2. Trình bày thuật toán thời gian đa thức để kiểm tra sự bảo toàn phụ thuộc hàm.
3. Chúng ta thường được yêu cầu để tính toán bao đóng của tập phụ thuộc hàm FDs. Cho một ví dụ trong đó việc xem xét bao đóng là cần thiết trong khi kiểm tra sự bảo toàn phụ thuộc hàm.
- Giả sử Fi là ký hiệu phép chiếu của F trên Ri. F được bảo toàn nếu bao đóng của Fi bằng với F.
- Chúng ta sẽ biểu diễn thuật toán kiểm tra bảo toàn phụ thuộc hàm trong đó lực lượng của F là đa thức. Với mỗi phụ thuộc hàm X → Y Є F kiểm tra xem nó có ở trong F không như sau: bắt đầu từ tập S (của các thuộc tính trong) X. Với mỗi quan hệ Ri, tính bao đóng của S ∩ Ri liên quan đến F và chiếu bao đóng này tới tập các thuộc tính của Ri. Nếu kết quả này nằm trong các thuộc tính bổ sung, thì thêm chúng vào S. Lặp lại cho đến khi không có sự thay đổi nào trong S.
- Có một ví dụ trong mục 5.2 của giáo trình.
Giả sử bạn được cho một quan hệ R(A,B,C,D). Với mỗi tập phụ thuộc hàm, thực hiện những yêu cầu sau: (a) Xác định khóa dự tuyển của R. (b) Chỉ ra có hoặc không một phép phân rã tốt của R.
1. B → C, D → A; phân rã thành BC và AD.
2. AB → C, C → A, C → D; phân rã thành ACD và BC.
3. A → BC, C → AD; phân rã thành ABC và AD.
4. A → B, B → C, C → D; phân rã thành AB và ACD.
5. A → B, B → C, C → D; phân rã thành AB, AD và CD.
Dành cho độc giả
Xem xét một quan hệ R có ba thuộc tính ABC. Nó được phân rã thành các quan hệ con là R1 có các thuộc tính AB và R2 có các thuộc tính BC.
- Chỉ ra định nghĩa của phép phân rã không mất mát kết nối cùng với một ví dụ. Trả lời câu hỏi này bằng việc viết ra một biểu thức đại số quan hệ chứa R, R1 và R2.
- Giả sử rằng có B→C. Việc phân rã R thành R1 và R2 có mất kết nối không? Xem xét câu trả lời của bạn cùng với quan sát rằng không có các phụ thuộc hàm R1 ∩ R2 → R1 và cũng không có phụ thuộc hàm R1 ∩ R2 → R2, cân nhắc những kiểm tra đơn giản khi đưa ra điều kiện cần và đủ cho việc phân rã không mất mát kết nối trong Phần 15.6.1.
- Nếu bạn được cung cấp các minh họa của R1 và R2, bạn có thể nói gì về minh họa của R? Trả lời câu hỏi này bằng cách liệt kê các bộ giá trị được định nghĩa trong R và các bộ giá trị có khả năng trong R.
Minh họa của R1 = {(5,1), (6,1)}
Minh họa của R2 = {(1,8), (1,9)}
Bạn có thể chắc chắn rằng thuộc tính B là hoặc không là một khóa của R?
1. Phân rã R thành R1 và R2 là không mất mát nếu và chỉ nếu:
R1 R1.B=R2.B R2=R
Ghi nhớ rằng đây là lược đồ quan hệ, không có minh họa dữ liệu nào trên chúng.
2. Dành cho độc giả
- Chúng ta có thể nói rằng minh họa R từ những minh họa đã cho R1 và R2 phải là một tập con của tập các bộ giá trị ABC: {(5,1,8), (5,1,9), (6,1,8), (6,1,9)}, {(5,1,8), (6,1,9)}, {(5,1,9), (6,1,8)}. Cụ thể, R chứa ít nhất hai bộ giá trị nhưng không nhiều hơn 4. Điều này cũng suy ra rằng thuộc tính B không phải là một khóa của R (vì R có ít nhất hai bộ giá trị phân biệt có cùng giá trị B).
Giả sử rằng chúng ta có bốn bộ giá trị trong quan hệ S có ba thuộc tính ABC: (1,2,3), (4,2,3), (5,3,3), (5,3,4). Những phụ thuộc hàm (→), phụ thuộc hàm đa trị (→→) nào sau đây có thể suy ra là không nằm trên S?
1. A→B
2. A→→B
3. BC→A
4. BC→→A
5. B→C
6. B→→C
Dành cho độc giả
Cho quan hệ R có năm thuộc tính ABCDE.
1. Với mỗi minh họa sau của R, chỉ ra rằng nó có vi phạm (a) phụ thuộc hàm: BC→ D và (b) phụ thuộc hàm đa trị BC →→ D:
(a) { } (tức là, quan hệ rỗng)
(b) {(a,2,3,4,5), (2,a,3,5,5)}
(c) {(a,2,3,4,5), (2,a,3,5,5), (a,2,3,4,6)}
(d) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5)}
(e) {(a,2,3,4,5), (2,a,3,7,5), (a,2,3,4,6)}
(f ) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5), (a,2,3,6,6)}
(g) {(a,2,3,4,5), (a,2,3,6,5), (a,2,3,6,6), (a,2,3,4,6)}
2. Nếu mỗi minh họa của R được liệt kê ở trên là đúng, bạn có thể nói gì về phụ thuộc hàm A →B?
1. Chú ý: Câu trả lời phụ thuộc vào giá trị a. Trừ khi được nói rõ ràng rằng câu trả lời áp dụng cho mọi giá trị của a.
(a) { }(quan hệ rỗng) không vi phạm phụ thuộc hàm nào
(b) {(a,2,3,4,5), (2,a,3,5,5)}:
Nếu a=2 thì BC→D là vi phạm (còn lại thì không).
BC→→D không vi phạm (với mọi giá trị của a).
(c) {(a,2,3,4,5), (2,a,3,5,5), (a,2,3,4,6)}:
BC→D bị vi phạm nếu a=2 (còn lại thì không)
Nếu a=2 thì BC→→D vi phạm (xem xét các bộ giá trị (2,a,3,5,5) và (a,2,3,4,6); nếu a =2 cũng phải có (2,a,3,5,6)).
(d) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5)}:
BC → D bị vi phạm (xem xét bộ giá trị thứ nhất (a,2,3,4,5) và thứ ba (a,2,3,6,5))
BC →→ D không bị vi phạm.
(e) {(a,2,3,4,5), (2,a,3,7,5), (a,2,3,4,6)}:
Nếu a=2 thì BC→D bị vi phạm (còn lại thì không)
Nếu a=2 thì BC →→ D bị vi phạm (còn lại thì không).
(f) {(a,2,3,4,5), (2,a,3,4,5), (a,2,3,6,5), (a,2,3,6,6)}:
BC→D không có. (Xem xét bộ giá trị thứ nhất và thứ ba).
BC →→ C bị vi phạm. Xem xét bộ giá trị thứ nhất và thứ 4. Để có phụ thuộc hàm này, ở đây phải có bộ giá trị (a,2,3,4,6).
(g) {(a,2,3,4,5), (a,2,3,6,5), (a,2,3,6,6), (a,2,3,4,6)}:
BC → D không có. (Xem xét bộ giá trị đầu tiên và thứ ba).
BC →→ C không bị vi phạm.
2. Chúng ta không thể nói bất cứ điều gì về hàm phụ thuộc A→B.
JDs được thúc đẩy bằng một thực tế rằng đôi khi một quan hệ không thể được phân rã thành hai quan hệ nhỏ hơn mà bảo toàn được liên kết, nhưng có thể được phân rã thành ba hoặc nhiều hơn các quan hệ con. Ví dụ, một quan hệ có các thuộc tính supplier, part, và project, ký hiệu là SPJ, không có phụ thuộc hàm và phụ thuộc hàm đa trị. Có JD{SP, PJ, JS}.
Từ JD này, tập các lược đồ quan hệ SP, PJ, và JS là phân rã bảo toàn liên kết của SPJ. Xây dựng một minh họa của SJD để cho thấy rằng không có hai trong số những lược đồ này đáp ứng được yêu cầu.
Trả lời mỗi câu hỏi như sau:
1. Chứng minh rằng thuật toán cho trong Hình 4 là đúng trong việc tính toán bao đóng của một tập thuộc tính X.
2. Trình bày một thuật toán có thời gian tuyến tính để tìm ra bao đóng của một tập thuộc tính. Chứng minh rằng thuật toán của bạn là đúng.
Câu trả lời với mỗi câu hỏi như sau:
1. Dành cho độc giả
2. Nhớ lại rằng bao đóng của tập thuộc tính X liên quan tới tập các thuộc tính A mà Σ thỏa mãn X → A.
// Initialize
X+ := X;
FdSet := Σ;
do
{
for each FD Y → Z in FdSet such that X+ ⊇ Y
{
X+ := X+ union Z;
Remove Y → Z from FdSet;
}
} until ( X+ does not change) ;
Giả sử n= | Σ | là ký hiệu lực lượng của Σ. Thì vòng lặp thực hiện nhiều nhất n lần vì với mỗi con chạy chúng ta hoặc là loại bỏ vĩnh viễn một phụ thuộc hàm nào đó từ tập Σ, hoặc là dừng tất cả cùng nhau. Bằng cách lựa chọn cấu trúc dữ liệu đúng, thuật toán này sẽ có kích thước tuyến tính là Σ.
Giả sử có FD X → Ylà phụ thuộc hàm đơn, trong đó Y là một thuộc tính đơn.
1. Thay thế FD AB→CD bằng tập các phụ thuộc hàm đơn nhỏ nhất.
2. Chứng minh rằng FD X→Y trong tập các phụ thuộc hàm F có thể được thay bằng tập các phụ thuộc hàm đơn để F+ bằng với bao đóng của tập các phụ thuộc hàm mới.
Dành cho độc giả
Chứng minh rằng tiên đề Amstrong là đúng đắn và đầy đủ cho các FD được suy diễn. Tức là, thực hiện lặp đi lặp lại các tiền đề này trên tập F của các FDs sẽ đưa ra chính xác các phụ thuộc hàm trong F+.
Insert Solution Text Here
Xem xét quan hệ R có các thuộc tính ABCDE. Giả sử có các phụ thuộc hàm sau đây: A → BC, BC → E, và E → DA. Tương tự, giả sử S là một quan hệ có các thuộc tính ABCDEvà giả sử có các phụ thuộc hàm sau: A → BC, B → E, và E → DA. Bạn không biết được có hay không có những phụ thuộc hàm khác đang tồn tại.
1. R là BCNF?
2. R là 4NF?
3. R là 5NF?
4. S là BCNF?
5. S là 4NF?
6. S là 5NF?
Dành cho độc giả
Giả sử R là một lược đồ quan hệ với F là tập các phụ thuộc hàm. Chứng minh rằng phân rã của R thành R1 và R2 là không mất mát kết nối nếu và chỉ nếu F+ chứa R1 ∩R2 →R1 hoặc R1 ∩ R2 → R2.
Với cả hai chiều (nếu và chỉ nếu) chúng ta sử dụng ký hiệu:
C = R1∩R2, X = R1−C, Y = R2−C, vì thế R1 = XC, R2 = CY , và R = XCY .
(⇐): Với chiều này, giả sử chúng ta được cung cấp phụ thuộc hàm C → X. (Trường hợp X→ C tương tự.)
Giả sử r là một minh họa của lược đồ R và giả sử (x1, c, y1) và (x2, c, y2) là hai bộ giá trị trong r. Phụ thuộc hàm C→X dẫn đến x1=x2. Vì thế, (x1, c, y2) tương tự như (x2, c, y2) và (x2,c,y1) tương tự như (x1, c, y1), vì thế cả hai bộ này (x1, c, y2) và (x2, c, y1) đều nằm trong r. Vì thế r thỏa mãn JD: R = R1 R2. Vì r là một minh họa dữ liệu tùy ý nên chúng ta đã chứng minh được rằng phân rã này là không mất mát.
(⇒): Với chiều này, giả sử rằng không có C→ X cũng như C→Y. Chúng ta sẽ chứng minh rằng phép nối này là mất mát bằng cách chỉ ra một minh họa quan hệ nào đó vi phạm JD: R1 R2. Giả sử chúng ta được cho một số tập của các phụ thuộc hàm Σ, để R có một phép nối không mất mát với Σ. Điều này có nghĩa là bất kỳ minh họa r nào thảo mãn Σ, chúng ta có
r = r1r2 trong đó r1 = πR1(r), r2 = πR2 (r).
Sau đó chứng minh rằng
{C → X, C → Y} ∩ Σ+ = ∅.
Chứng minh điều này bằng phản chứng. Giả sử rằng phép hợp {C → X,C → Y } ∩ Σ+ là rỗng. Giả sử r1 là một minh họa của lược đồ này và không thỏa mãn phụ thuộc hàm C→X và r2 là một minh họa không thỏa mãn phụ thuộc hàm C→Y. Chọn c để các bộ giá trị (x1, c, y1), (x2, c, y2) ∈ r1 trong đó x1 ≠ x2 và c’ để (x’1, c’, y’1), (x’2, c’, y’2) ∈ r2 trong đó y’1 ≠ y’2.
Sử dụng phép chọn để thay thế r1 bằng π R.C=c(r1) và r2 bằng π R.C=c’ (r2). Vì r1 và r2 là hữu hạn và các tập hợp miền là vô hạn, chúng ta có thể giả sử mà không mất tính tổng quát (bằng cách thay đổi một số các giá trị của các bộ trong r1 và r2 nếu cần thiết) để
c=c’
π A(r1) Ç π A (r2) = ∅ với mỗi thuộc tính A ∈ X
π B(r1) Ç π B (r2) = ∅ với mỗi thuộc tính B ∈ Y
Bây giờ xem xét quan hệ r1 È r2. Đây là một minh họa của lược đồ R thỏa mãn Σ. Tuy nhiên, (x1, c, y’1) ∉ r1 È r2, vì thế minh họa r1 È r2 không thỏa mãn JD: R1 R2.
Xem xét lược đồ R với các phụ thuộc hàm F được phân rã thành các lược đồ cùng với các thuộc tính X và Y. Chỉ ra rằng phép phân rã này bảo toàn phụ thuộc hàm nếu F ⊆ (FXÈFY )+.
Dành cho độc giả.
Chứng minh rằng thuật toán phân rã một quan hệ thành các quan hệ con ở dạng 3NF bảo toàn phụ thuộc hàm và không mất mát kết nối (Phần 6.2) là đúng.
Dành cho độc giả
Chứng minh rằng việc tổng hợp thành 3NF đưa ra được một phép phân rã không mất kết nối và vẫn giữ được tất cả các thuộc tính ban đầu.
Dành cho độc giả
Chứng minh rằng MVD X →→ Y trên quan hệ R có thể được biểu diễn bằng
{XY, X(R − Y )}.
Viết Z = R − Y. Vì, R = YXZ. X →→ Y nói rằng nếu (y1, x, z1), (y2, x, z2) ∈ R thì (y1, x, z2), (y2, x, z1) cũng ∈ R. Nhưng đây là chính xác nếu nói rằng R={XY, X(R−Y)}.
Chứng minh rằng, nếu R chỉ có một khóa thì R ở BCNF nếu và chỉ nếu nó ở 3NF.
Dành cho độc giả
Chứng minh rằng, nếu R ở 3NF và tất cả các khóa là thuộc tính đơn, thì R ở BCNF.
Vì tất cả các khóa là thuộc tính đơn, nên chúng ta biết rằng với bất kỳ phụ thuộc hàm thỏa mãn X→A, trong đó A là một khóa. Thông qua định nghĩa của phụ thuộc hàm, nếu biết X thì cũng biết A. Điều này có nghĩa là nếu biết X, chúng ta biết một khóa nào đó của quan hệ này, vì thế X phải là một siêu khóa. Điều này thỏa mãn tất cả các tính chất của BCNF.
Chứng minh những phát biểu sau:
1. Nếu một lược đồ quan hệ nào đó ở BCNF và ít nhất một khóa của nó chứa một thuộc tính đơn thì nó cũng ở 4NF.
2. Nếu một lược đồ quan hệ ở 3NF và mỗi khóa có một thuộc thíh đơn thì nó cũng ở 5NF.
Dành cho độc giả
Trình bày một thuật toán để kiểm tra xem một quan hệ nào đó có ở BCNF không. Thuật toán này nên là đa thức theo kích thước của tập phụ thuộc hàm được cho. (Kích thước là tổng trên tất cả các phụ thuộc hàm của số lượng các thuộc tính xuất hiện trong phụ thuộc hàm.) Có thuật toán đa thức để kiểm tra xem lược đồ quan hệ này có ở dạng 3NF không?
Giả sử |F| là ký hiệu của kích thước của sự biểu diễn lược đồ, tức là tập của tất cả các phụ thuộc hàm của lược đồ này. Cũng như vậy, giả sử |f| là số lượng các phụ thuộc hàm trên lược đồ này. Trong Bài 15 chúng ta biết rằng với mỗi thuộc tính trong lược đồ này, chúng ta có thể tính được bao đóng của các thuộc tính phía trái với thời gian O(|F|).
Thuật toán này để kiểm tra xem R ở BCNF bao gồm việc tính toán bao đóng của tập thuộc tính bên phía trái của từng phụ thuộc hàm. Nếu một trong số chúng không bằng U trong đó U là tập của tất cả các thuộc tính, thì R không ở BCNF. Ngược lại kết luận rằng R ở BCNF.
Rõ ràng độ phức tạp trong trường hợp xấu nhất của thuật toán này là O(|f|•|F|). Vì |f| được giới hạn bởi |F| nên độ phức tạp thời gian là |F|.
Mặt khác, không có một thuật toán nào kiểm tra một quan hệ có ở 3NF hay không với độ phức tạp thời gian là đa thức. Vì để kiểm tra một phụ thuộc hàm đã cho nào đó có vi phạm 3NF hay không chúng ta cần kiểm tra xem phía tay phải là nguyên tố không, tức là, là một tập con của một vài khóa của lược đồ này. Nhưng việc xác định (tất cả) các khóa của lược đồ này bao gồm việc kiểm tra tất cả các tập con của U. Cuối cùng là bài toán thuộc tính nguyên tố được biết là bài toán NP-đầy đủ và vấn đề 3NF rõ ràng là cũng khó như vậy, vì thế nó cũng là NP-đầy đủ.
Trình bày một thuật toán để kiểm tra xem một quan hệ nào đó có ở BCNF không. Thuật toán này nên là đa thức theo kích thước của tập phụ thuộc hàm được cho. (Kích thước là tổng trên tất cả các phụ thuộc hàm của số lượng các thuộc tính xuất hiện trong phụ thuộc hàm.) Có thuật toán đa thức để kiểm tra xem lược đồ quan hệ này có ở dạng 3NF không?
Dành cho độc giả
Chứng minh rằng thuật toán phân rã một quan hệ thành các quan hệ con ở dạng BCNF trong Phần 6.1 (tức là, nó đưa ra một tập các quan hệ ở BCNF và không mất mát kết nối) là đúng và sẽ dừng lại.
1. Giả sử X ⊂ R , A là một thuộc tính đơn của R và X→A là một phụ thuộc hàm gây ra sự vi phạm BCNF. Phân rã thành R − A và XA.
2. Nếu R − A hoặc XA không ở BCNF, tiếp tục phân rã chúng một cách đệ quy áp dụng thuật toán này.
Chứng minh sự đúng đắn của thuật toán được chia thành 3 phần:
Chứng minh rằng tất cả các phân rã là không mất mát:
Với mỗi phân rã R thành R − A và XA , nó là không mất mát theo định lý 3 của chương này. Đầu tiên, chúng ta nói rằng (R − A) Ç (XA) = X vì: X ⊂ R, và A không nằm trong X. Có phụ thuộc hàm X→A thì suy ra X→ XA bởi Luật hợp, vì thế (R − A) Ç (XA) → XA và theo Định lý 3, phân rã này là không mất mát. Tuy nhiên, phân rã này có thể không bảo tồn phụ thuộc hàm.
Chứng minh rằng thuật toán sẽ dừng lại
Các phân rã của quan hệ R sẽ đưa ra các quan hệ R − A và XA. R−A sẽ có ít thuộc tính hơn R vì A không rỗng, và vì phụ thuộc hàm này vi phạm BCNF nên A phải nằm trong R. Thêm nữa, XA có ít thuộc tính hơn R nên X ⊂ R và XA ≠ R. Điều này là rõ ràng vì nếu chúng ta giả sử rằng XA=R thì chúng ta có thể kết luận rằng X là siêu khóa vì XA→ R và X→A nên X→R do tính bắc cầu. Điều này là trái với giả thiết rằng phụ thuộc hàm này vi phạm BCNF nên chúng ta kết luận rằng XA ≠ R.
Nếu chúng ta giả sử rằng n là số các thuộc tính trong quan hệ ban đầu R, thì có nhiều nhất (2n-1) phân rã thuật toán sẽ thực hiện trước khi nó dừng lại. Khi một quan hệ nào đó chỉ chứa thuộc tính đơn, nó là BCNF và không thể được phân rã tiếp vì ở đây không có các phụ thuộc hàm chúng ta có thể áp dụng để nó vi phạm BCNF.
Chứng minh rằng tất cả quan hệ trong tập cuối cùng đều ở BCNF
Như đã trình bày trong phần trước về vấn đề này, trong trường hợp xấu nhất phân rã R thành một tập của n quan hệ gồm các thuộc tính đơn với n là số lượng các thuộc tính của quan hệ ban đầu R. Như đã trình bày ở trên, mỗi quan hệ rõ ràng là ở BCNF. Quá trình phân rã có thể, và trong trường hợp xấu nhất, dừng trước khi chúng ta phân rã thành các quan hệ chỉ có các thuộc tính đơn, thuật toán sẽ chỉ dừng khi tất cả các tập con của R đều ở BCNF.
Tài liệu tham khảo
Tài liệu trình bày về lý thuyết phụ thuộc hàm và cách sử dụng nó trong thiết kế cơ sở dữ liệu [3, 45, 501, 509, 747]. Những bài báo hay về chủ đề này gồm [755, 41, 5].
FDs được giới thiệu trong [187], cùng với khái niệm về 3NF, và các tiên đề để suy diễn phụ thuộc hàm được trình bày trong [38]. BCNF được giới thiệu trong [188]. Khái niệm về một minh họa quan hệ được nghiên cứu trong [328]. FDs được tổng quát hoá thành các mô hình dữ liệu mức ngữ nghĩa trong [768].
Việc tìm một khoá là bài toán NP-đầy đủ được trình bày trong [497]. Phân rã không mất kết nối được trình bày trong [28, 502, 627]. Phân rã bảo toàn phụ thuộc hàm được trình bày trong [74]. [81] giới thiệu về phủ tối thiểu. Phân rã một quan hệ thành các quan hệ con ở 3NF được trình bày trong [81, 98] và thành BCNF được trình bày trong [742]. [412] chỉ ra rằng việc kiểm tra một quan hệ có ở 3NF không là bài toán NP-đầy đủ. [253] giới thiệu về 4NF và trình bày về việc phân rã thành 4NF. Fagin giới thiệu những dạng chuẩn khác trong [254] (dạng chuẩn project-join) và [255] (dạng chuẩn domain-key). Ngược lại với những nghiên cứu rộng lớn về phân rã theo chiều dọc, hiện nay đã có một số nghiên cứu về cách phân rã theo chiều ngang. [209] nghiên cứu về phân rã này.
MVDs được nghiên cứu đầu tiên bởi Delobel [211], Fagin [253], và Zaniolo [789]. Tiên đề cho FDs và MVDs được trình bày trong [73]. [593] chỉ ra rằng không có tiên đề cho JDs, mặc dù [662] cung cấp một tiên đề cho một lớp phổ biến của các phụ thuộc hàm. Những điều kiện đầy đủ cho 4NF và 5NF dưới dạng FDs được trình bày trong Phần 8 là bắt nguồn từ [205]. Các tiếp cận để thiết kế cơ sở dữ liệu sử dụng thông tin phụ thuộc hàm để xây dựng các minh hoạ quan hệ dữ liệu được trình bày trong [508, 509].