Chương II: CÁC PHỤ THUỘC DỮ LIỆU TRONG MÔ HÌNH QUAN HỆ
III. PHỤ THUỘC ĐA TRỊ
III.5. Bao đóng của phụ thuộc hàm và phụ thuộc đa trị
Chúng ta có thể tính D+bằng cách khởi đầu với D và áp dụng các tiên đề A1-A8 đến khi không còn suy ra được một phụ thuộc mới nào nữa. Tuy nhiên quá trình này có chi phí thời gian là hàm mũtheo kích thước của D.
Thông thường chúng ta chỉ muốn biết xem một phụ thuộc hàm XY hoặc phụ thuộc đa trị X Y nào đó có suy rađược từ D hay không.
III.5.1. Cơsở phụ thuộc
Như đã trình bày khi nói về phụ thuộc hàm, để kiểm tra một phụ thuộc hàm XY có thuộc D+hay không, ta tính X+ là bao đóng của tập thuộc tính X đối với tập các phụ thuộc hàm trong D, sau đó xem Y có phải là tập con của X+ hay không, nghĩa là Y = A1A2…Ak,với Ailà thuộc tính thuộc X+
Tương tự, để kiểm tra xem một phụ thuộc đa trị XY có đúng hay không (thuộc D+ hay không), chúng ta chỉ cần xác định cơsở phụ thuộccủa X và xem Y –X có phải là hợp của một số tập trong cơsở đó hay không.
Nhận xét:
- Baođóngcủa X = A1A2…Ak,với Ailàthuộc tính - Cơsở phụ thuộccủa X = Y1Y2…Yk,với Yilàtập các thuộc tính
Với qui tắc phân rã của phụ thuộc đa trị, cùng với quy tắc hợp, dẫn đến khẳng định sau đây về các tập Y sao cho XY đúng với một tập X đã cho.
III.5.2.Định lý II.4 :
Nếu U là tập chứa tất cả các thuộc tính thì chúng ta có thể phân hoạch U-X thành các tập thuộc tính Y1,...,Yksao cho nếu Z U-X thì XZ đúng nếu và chỉ nếu Z là hợp của một số Yi.
Nhận xét:
- Mỗi Yilà không rỗng, với i=1, 2, …, k
- Mỗi cặp các Yi, Yj là phân biệt (có giao là rỗng), với i,j=1, 2, …, k
-U-X là hợp của các tập Y1, Y2,...,Yk
- Z là con của U-X
Chứng minh:
Khởi đầu phân hoạch toàn bộ U-X thành một khối (W1=U-X).
Ta có thể phân họach nhưtrên bởi vì do tiênđề A1 (tính phản xạ của phụ thuộc hàm) ta có phụ thuộc hàm hiển nhiên XX, hơn nữa do tiênđề A7 (liên hệ giữa phụ thuộc hàm và phụ thuộc đa trị) ta có X X đúng. Áp dụng tiên đề A4 (tính bù của phụ thuộc đa trị) ta có X(U-X-X) tức là X(U-X)đúng.
Giả sử rằng tại một điểm nào đó chúng ta có các phân hoạch W1,……,Wnvà XWi với i = 1,2,….n.
Nếu XZ đúng và Z không phải là hợp của một số Wi, hãy thay mỗi Wi có Wi Z và Wi - Z đều không trống bởi WiZ và Wi- Z .
Áp dụng qui tắc phân rã cho XWi và X Z, ta có X(WiZ) và X(Wi- Z)đúng.
Bởi vì chúng ta không thể phân hoạch vô hạn một tập các thuộc tính hữu hạn, cuối cùng chúng ta thấy rằng mỗi Z có XZ đúngđều là hợp của một số phân hoạch.
Nhờ qui tắc hợp, X đa xác định hợp của một tập phân hoạch bất kỳ.
Chúng ta gọi tập Y1……..Yk được xây dựng cho X từ tập các phụ thuộc hàm và đa trị D là cơ sở phụ thuộc (dependency basis) của X (ứng với D).
Thí dụ II.7.:
Trong Thí dụ II.6 chúngta đã nhận xét rằng CHR.
Vì thế theo qui tắc bù, C TSG. Chúng ta cũng biết rằng C T. Vì thế nhờ tiênđề A7, C T. Theo quy tắc phân rã, C SG. Cũng có thể kiểm chứng rằng không có một thuộc tính đơn nào trừ T hoặc C được xác định đa trị bởi C.
Vì thế cơ sở phụ thuộc cho C là {T, HR, SG}. Về trực quan chúng ta thấy rằng, đi kèm với mỗi khoá học là các tập giảng viên (chỉ có duy nhất một tập), các cặp giờ học – phòng cho biết thời gian và địa điểm khoá học, và các cặp sinh viên - điểm, là danh sách sinh viên của khoá học.
Nhận xét:
Trong trường hợp tổng quát với X Z mà ZU-X, tức là Z X không rỗng. Áp dụng qui tắc phân rã cho XZ và X X ta có các phụ thuộc đa trị X(Z-X) và X(ZX) cũngđúng.
Với X(Z - X), vì (Z - X) (U - X) nên dođịnh lý trên (U - X) là hợp của một số các Yi là cơsở phụ thuộc của X.
Với X (ZX), vì (ZX) X nên do tiên đề A1 và tiênđề A7 ta có XAi với (ZX) = A1A2… Am
III.5.3. Thuật toán II.2: Tính Cơsở phụ thuộc
Để tính cơsở phụ thuộc của X đối với D ta chỉ cần tính cơ sở phụ thuộc của X đối với tập các phụ thuộc đa trị M trong D làđủ.
Khiđóđòi hỏi M phải bao gồm:
1. Tất cả các phụ thuộc đa trị thuộc D và
2. Với mỗi phụ thuộc hàm XY thuộc D thì thay bằng tập các phụ thuộc đa trị XA1, X A2, … X An, trong đó Y= A1A2…An, tức là Ai thuộc Y và mỗi Ai là một thuộc tính đơn.
Một định lý khác của Beeri [1980] cho chúng ta cách lấy ra những phụ thuộc hàm không tầm thường từ cơ sở phụ thuộc được tính ứng với tập các phụ thuộc đa trị M. Beeri đã chứng minh được rằng nếu X không chứa A thì X Ađúng nếu và chỉ nếu:
1.A là tập độc nhất trong cơsở phụ thuộc cho X ứng với tập phụ thuộc đa trị M, và
2. Có một tập thuộc tính Y không chứa A, sao cho Y Z là một trong những phụ thuộc của D và A thuộc Z.
Ta có thuật tóan tính cơsở phụ thuộc sau:
NHẬP:
Tập phụ thuộc đa trị Mtrên tập các thuộc tính Uvà tâpX
U.
XUẤT:
Cơsở phụ thuộc choXứng với M.