Bài giảng Cơ sở dũ liệu (database) - Chương 4 Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu quan hệ

CHƯƠNG 4: Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu quan hệ Nội dung  Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF) Nội dung  Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF) Một số khái niệm  Phụ thuộc hàm  Luật của phụ thuộc hàm  Bao đóng của tập phụ thuộc hàm  Các loại khóa  Thuộc tính thuộc khóa Phụ thuộc hàm  Phụ thuộc hàm (functional dependency) được sử dụng như 1 độ đo để đánh giá chất lượng của tập sơ đồ quan hệ được thiết kế  Các phụ thuộc hàm và các khóa được dùng để xác định các chuẩn của quan hệ  Phụ thuộc hàm là các ràng buộc được xác định từ ngữ nghĩa và mối quan hệ bên trong của các thuộc tính Phụ thuộc hàm  Một tập thuộc tính X xác định tập thuộc tính Y nếu giá trị trong X cho phép xác định một giá trị duy nhất trong Y  Y phụ thuộc hàm vào X  X Y là đúng nếu bất cứ hai bộ nào có cùng giá trị X thì phải có cùng giá trị Y Nếu t1[X]=t2[X], thì t1[Y]=t2[Y] với mọi bộ r(R)  X  Y trong R xác định một ràng buộc cho tất cả các thể hiện r(R)  Phụ thuộc hàm chính là các ràng buộc trên dữ liệu Ví dụ về phụ thuộc hàm  Mã số bảo hiểm cho phép xác định tên nhân viên SSN  ENAME  Mã dự án cho phép xác định tên dự án và địa điểm dự án PNUMBER  {PNAME, PLOCATION}  Mã số bảo hiểm của nhân viên SSN và mã dự án xác định số giờ mà nhân viên phải làm trong dự án {SSN, PNUMBER}  HOURS Phụ thuộc hàm  Một phụ thuộc hàm là một tính chất của các thuộc tính trong lược đồ quan hệ R  Một ràng buộc phải đúng cho tất cả các thể hiện của lược đồ quan hệ r(R) Các luật cho phụ thuộc hàm  Với một tập phụ thuộc hàm F, ta có thể suy ra các phụ thuộc hàm mới  Luật Armstrong A1. (Phản xạ - Reflexive) Nếu Y là tập con của X thì X  Y A2. (Tăng trưởng - Augmentation) Nếu X  Y, thì XZ  YZ (Chú ý: XZ có nghĩa là X U Z) A3. (Bắc cầu - Transitive) Nếu X  Y và Y  Z, thì X  Z  A1, A2, A3 tạo một tập các luật đúng và đầy đủ Các luật cho phụ thuộc hàm  Luật tách - Decomposition  If X  YZ, then X  Y and X  Z  Luật hợp  If X  Y and X  Z, then X  YZ  Luật tựa bắc cầu - Psuedotransitivity  If X  Y and WY  Z, then WX  Z  Bao đóng của F cho tập phụ thuộc hàm là tập F+ của các phụ thuộc hàm suy diễn từ F Phụ thuộc hàm đầy đủ  Phụ thuộc hàm đầy đủ (Full functional dependency): Y  Z là phụ thuộc hàm đầy đủ nếu bỏ đi bất cứ một thuộc tính nào trong Y thì phụ thuộc hàm này không còn đúng  {SSN, PNUMBER}  HOURS là một phụ thuộc hàm đầy đủ bởi vì SSN  HOURS hoặc PNUMBER  HOURS không còn đúng  {SSN, PNUMBER}  ENAME không phải là phụ thuộc hàm đầy đủ (gọi là phụ thuộc hàm bộ phận) bởi vì SSN  ENAME Một số khái niệm khác  Phụ thuộc hàm tầm thường (Trivial functional dependency)  {Employee ID, Employee Address} → {Employee Address} là phụ thuộc hàm tầm thường vì {Employee Address} → {Employee Address}. Khóa • Siêu khóa (Superkey) K  R • Khóa (Candidate Key) K  R Không tồn tại K’  K, sao cho K’  R (tối thiểu) • Khóa chính (Primary Key) • Thuộc tính thuộc khóa (Prime attribute) là 1 thuộc tính trong khóa chính K Siêu khóa Khóa Khóa chính Khóa - ví dụ  Bảng employee (employeeID, name, job, và departmentID)  Siêu khóa: {employeeID }, {employeeID, Name}, {employeeID, Name, job}, và {employeeID, Name, job, departmentID}.  employeeID là một khóa Bao đóng của tập thuộc tính Algorithm: •X(0) := X •Repeat X(i+1) := X(i)  Z, where Z is the set of attributes such that there exists YZ in F, and Y  X(i) •Until X(i+1) := X(i) •Return X(i+1) Định nghĩa: X, Y là các thuộc tính của R: X  Y nằm trong F+  Y  X+ R = (A, B, C, D, E) F = {ABC, CDE, BD, EA} Tính A+ và B+: A+ := {A} := {A, B, C} ABC và {A}  A+ := {A, B, C, D} BD và {B}  A+ := {A, B, C, D, E}CDE và {C, D}  A+ không thay đổi Bao đóng của tập thuộc tính B+ := {B} := {B, D} BD và {B}  B+ dừng giải thuật vì B+ không thay đổi nữa Bao đóng của tập thuộc tính Bao đóng của tập thuộc tính  A+ là bao đóng của tập thuộc tính  Nếu A+ = R, thì A là một siêu khóa của quan hệ R R = (A, B, C, D, E) F = {ABC, CDE, BD, EA} Liệt kê tất cả các khóa của R • A+ = {A, B, C, D, E}do đó AABCDE, thì A là khóa của quan hệ R. • Vì EA, nên EABCDE. (bắc cầu) • Vì CDE, nên CDABCDE. (bắc cầu) • Vì BD, nên BCCD, BCABCDE. (tăng trưởng, bắc cầu) Tính khóa dựa trên bao đóng tập thuộc tính Thuộc tính khóa - Ví dụ  Cho lược đồ quan hệ R trên tập thuộc tính U={A, B, C, D} với các phụ thuộc hàm AB->C và B->D và BC->A.  Xác định thuộc tính khóa và thuộc tính không khóa Nội dung  Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF) Các quy tắc cho thiết kế cơ sở dữ liệu quan hệ  Thiết kế cơ sở dữ liệu quan hệ: cách nhóm các thuộc tính đề tạo thành các lược đồ quan hệ  Các chuẩn 1NF 2NF 3NF BCNF Dư thừa dữ liệu và các dị thường khi cập nhật  Dư thừa dữ liệu  Các dị thường:  Dị thường khi thêm bộ  Dị thường khi xóa bộ  Dị thường khi thay đổi Ví dụ về các dị thường Ví dụ quan hệ: EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)  Dị thường khi cập nhật  Chuyển tên của dự án từ P1 từ “Billing” thành “Customer- Accounting” phải cập nhật nhiều lần do 100 nhân viên đang làm trong dự án P1  Dị thường khi thêm bộ  Không thể thêm một dự án không có nhân viên.  Không thể thêm một nhân viên nếu nhân viên đó chưa được chỉ định vào 1 dự án cụ thể. Ví dụ về các dị thường  Dị thường xóa bộ  Khi xóa 1 dự án thì toàn bộ nhân viên làm cho dự án bị xóa  Khi xóa một nhân viên của dự án chi bao gồm 1 nhân viên thì kết quả là dự án bị xóa theo  Dư thừa dữ liệu  Không nhất quán  Đảm bảo cơ sở dữ liệu thiết kế không chứa các dị thường thêm, xóa và cập nhật Giá trị Null trong các bộ  Các quan hệ phải được thiết kế sao cho các bộ của nó có giá trị NULL ít nhất có thể  Các thuộc tính thường có giá trị NULL có thể được đặt trong 1 quan hệ riêng  Giá trị NULL xảy ra do:  thuộc tính không hợp lệ  giá trị của thuộc tính không biết (có thể tồn tại)  giá trị của thuộc tính tồn tại nhưng không chưa xác định được Bộ giả  Thiết kế không tốt có thể sinh ra lỗi khi thực hiện các thao tác kết nối  Các quan hệ phải được thiết kế để đảm bảo không có bộ giả nào được sinh ra khi thực hiện kết nối tự nhiên Nội dung  Một số khái niệm  Các vấn đề trong thiết kế sơ đồ quan hệ  Chuẩn hóa  1NF  2NF  3NF  Boyce Codd (BCNF) Chuẩn hóa  Chuẩn hóa: Là một quá trình chia nhỏ quan hệ thiết kế không tốt thành tập các quan hệ nhỏ hơn  Các chuẩn: dùng khóa và các phụ thuộc hàm để xác định dạng chuẩn của quan hệ  Chuẩn 2, chuẩn 3, chuẩn Boyce-Codd dựa vào khóa và các phụ thuộc hàm  Chuẩn 4 dựa vào khóa và các ràng buộc đa trị Chuẩn 1  Không cho phép các thuộc tính đa trị, thuộc tính không nguyên tố Bài tập: xác định quan hệ nào là 1NF Chuẩn 2  Một quan hệ R ở dạng chuẩn 2 nếu tất cả thuộc tính không khóa A trong R là phụ thuộc đầy đủ vào khóa chính  R có thể chia thành các quan hệ ở dạng chuẩn 2 thông qua quá trình chuẩn hóa dạng chuẩn 2 Chuẩn 2: Ví dụ  FIRST (supplier_no, status, city, part_no, quantity)  Phụ thuộc hàm:  (supplier_no, part_no) -> quantity  (supplier_no) -> status  (supplier_no) -> city  city -> status Chuẩn 2  Hai thuộc tính city và status chỉ phụ thuộc một phần vào khóa chính (supplier_no và part_no)  INSERT: Không thể thêm một nhà cung cấp (supplier) ở một thành phố nào đó nếu nhà cung cấp đó chưa tham gia cung cấp.  DELETE: Nếu xóa hàng cuối cùng của một nhà cung cấp thì thông tin về địa chỉ của nhà cung cấp bị xóa.  UPDATE: Thông tin về thành phố (city) xuất hiện nhiều lần cho cùng một nhà cung cấp->không đồng nhất khi thay đổi thông tin.  Phân rã quan hệ thành 2 quan hệ dạng chuẩn 2NF:  SECOND (supplier_no, status, city)  SUPPLIER_PART (supplier_no, part_no, quantity) Chuẩn 3  Định nghĩa  Phụ thuộc hàm bắc cầu (Transitive functional dependency): Tập thuộc tính Z không phải là khóa và tồn tại X  Y và Y  Z  Ví dụ  SSN  DMGRSSN là một phụ thuộc hàm bắc cầu vì SSN  DNUMBER và DNUMBER  DMGRSSN  SSN  ENAME không phải là phụ thuộc hàm bắc cầu vì không tồn tại tập thuộc tính X sao cho SSN  X và X  ENAME Chuẩn 3  Một quan hệ R ở dạng chuẩn 3 nếu nó :  ở dạng chuẩn 2 và  không có thuộc tính không khóa A trong R phụ thuộc bắc cầu vào khóa chính Chuân 3NF  SECOND (supplier_no, status, city)  supplier_no -> status  supplier_no ->city  city -> status  SUPPLIER_CITY (supplier_no, city)  CITY_STATUS (city, status) Chuẩn Boyce-Codd (Boyce-Codd Normal Form)  Một quan hệ R là ở dạng chuẩn Boyce-Codd nếu có một phụ thuộc hàm X  A trong R thì X là một khóa của R  Chuẩn sau luôn luôn mạnh hơn chuẩn trước:  Tất cả các quan hệ ở dạng chuẩn 2 đều ở dạng chuẩn 1  Tất cả các quan hệ ở dạng chuẩn 3 đều ở dạng chuẩn 2  Tất cả các quan hệ ở dạng chuẩn Boyce-Codd đều ở dạng chuẩn 3  Tuy nhiên có một số quan hệ ở dạng chuẩn 3 nhưng không ở dạng chuẩn Boyce-Codd.  Mục đích là chuẩn hóa để quan hệ ở dạng chuẩn 3 hoặc dạng chuẩn Boyce-Codd Ví dụ title year length filmType studioNam e starName Star Wars 1977 124 color Fox Fisher Star Wars 1977 124 color Fox Hamill Star Wars 1977 124 color Fox Ford Mighty Ducks 1991 104 color Disney Esteves Wayne’s World 1992 95 color Paramount Carvey Wayne’s World 1992 95 color Paramount Meyers Ví dụ  {title, year, starName} là candidate key  title, year  length, filmType, studioName Ví dụ  Chia quan hệ Movies thành 2 quan hệ  Quan hệ chứa tất cả các thuộc tính xuất hiện trong phụ thuộc hàm {title, year, length, filmType, studioName}  Quan hệ chứa khóa và thuộc tính ở phía bên trái của phụ thuộc hàm {title, year, starName} Bài tập  Customer-schema = (cname, street, ccity) cname ->street, ccity  Branch-schema = (bname, assets, bcity) bname ->assets, bcity  Loan-info-schema = (bname, cname, loan#, amount) loan# ->amount, bname Bài tập  Cho quan hệ Book(Book_title, Authorname, Book_type, Listprice, Author_affil, Publisher) Và các ràng buộc Book_title  Publisher, Book_type Book_type  Listprice Authorname Author_affil Xác định quan hệ ở dạng chuẩn nào? Bài tập: Xác định dạng chuẩn của quan hệ R=(A, B, C, D, E, F) FD = {AB, BCD, CE, BF} • Xác định dạng chuẩn của quan hệ