Tính các bao đóng

Chương II: CÁC PHỤ THUỘC DỮ LIỆU TRONG MÔ HÌNH QUAN HỆ

II.11. Tính các bao đóng

Rõ ràng là việc tính F+ cho một tập phụ thuộc F nói chung tốn rất nhiều thời gian, đơn giản là vì tập các phụ thuộc của F+có thể rất lớn dù rằng tập phụ thuộc F nhỏ. Chẳng hạn xét tập phụ thuộc:

F = (AB1,AB2 ….,ABn)

Thế thì F+ bao gồm tất cả các phụ thuộc A  Y, trong đó Y là một tập con của (B1, B2 …., Bn). Bởi vì có có đến 2n tập Y nhưthế, chúng ta không hy vọng liệtkê hết được tập F+ ngay cả với kích thước n vừa phải.

Ngược lại, việc tính X+ cho tập các thuộc tính X thì không khó; chi phí thuật toán này tỷ lệ với chiều dài của tất cả các phụ thuộc trong F. Nhờ Bổ đề II.3 và định lý II.1 về tính đúngđắn vàđầy đủ của hệ tiênđề Armstrong, chúng ta có thể biết được X  Y có thuộc F+ hay không bằng cách tính X+ ứng với F. Cách tính X+ đơn giản nhưsau.

II.11.1. Thuật toán II.1: tính các bao đóng một tập thuộc tínhứng với môt tập phụ thuộc hàm.

NHẬP:

Tập thuộc tính hữu hạn U, tập phụ thuộc hàm F trên U, và tập X U.

XUẤT:

X+, baođóng của X ứng với F.

PHƯƠNG PHÁP:

chúng ta tính chuỗi các tập thuộc tính X(0), X(1), …. bằng các qui tắc:

1. X(0)chính là X.

2. X(i+1) là hợp của X(i)với tập các thuộc tính A sao cho có một phụ thuộc YZ thuộc F, A thuộc Z và Y X(i).

Bởi vì X= X(0) X(1)…. X(i)U, và U là hữu hạn, cuối cùng chúng ta phải đạt đến một trị số i sao cho X(i)

=X(i+1). Bởi vì mỗi X(j+1) chỉ được tính theo X(j), suy ra rằng X(i)=X(i+1)=X(i+2)…Chúng ta không cần phải tính tiếp khi đã phát hiện ra rằngX(i) =X(i+1) , và có thể chứng minh rằng X+ chính là X(i) với trị số i này.

Thí dụ II.3:

Gọi F là tập gồm 8 phụ thuộc sau:

ABC DEG

CA BEC

BCD CGBD

ACDB CEAG

Và cho X= BD. Hãy tính X+

Để áp dụng Thuật toán II.1, khởi đầu chúng ta đặt X(0)= BD.

Muốn tính X(1), chúng ta tìm các phụ thuộc có vế phải là B,D hoặc BD. Chỉ có một phụ thuộc D EG, vì thế chúng ta nối E và G với X(1), kết quả là X(1)= BDEG.

Đối với X(2) chúng ta tìm các vế trái được chứa trong X(1) và tìmđược hai phụ thuộc D EG và BEC. Vì vậy X(2)=BCDEG.

Tiếp tục với X(3), chúng ta tìm các vế trái được chứa trong BCDEG và tìm ra các phụ thuộc mới C A, BC D, CGBD, và CEAG. Vì vậy X(3)= ABCDEG, là tập hợp gồm tất cả mọi thuộc tính đã cho.

Do đó không có gì ngạc nhiên là X(3) = X(4) = … . Do vậy (BD)+= ABCDEG.

Bây giờ chúng ta phải chứng minh tính đúng đắn của Thuật toán II.1. Chúng ta có thể dễ dàng chứng minh được rằng mỗi thuộc tính được đặt vào một tập X(j)đều thuộc X+, nhưng chứng minh rằng mỗi thuộc tính trong X+đều được đặt trong một X(j)nàođó thì khó hơn.

II.11.2.Định lý II.2: Thuật toán II.1 tính đúng X+. Chứng minh:

Trước tiên chúng ta chứng minh bằng qui nạp trên j rằng nếu A được đặt trong X(j ) trong khi “chạy” thuật toán II.1 thì A thuộc X+; nghĩa là nếu A thuộc tập X(j )được trả về bởi thuật toán II.1 thì A thuộc X+.

Bước cơ sở: j = 0. Thế thì A thuộc X, vì vậy do tính phản xạ, X A.

Qui nạp: Với j > 0 và giả sử rằng X(j-1 ) chỉ chứa các thuộc tính X+. Giả sử A được đặt trong X(j )do A thuộc Z, Y

 Z thuộc F, và Y X(j-1 ) . Bởi vì Y X(j-1 ) chúng ta biết rằng Y X+theo giả thiết qui nạp . Vì vậy X Y theo Bổ đề II.3. Nhờ tính chất bắc cầu, X Y và Y Z suy ra XZ.

Nhờ tính chất phản xạ, Z A nên XA lại do tính bắc cầu.

Vì vậy A thuộc X+.

Bây giờ chúng ta chứng minh phần đảo: nếu A thuộc X+ thì A là phần tử của tập được trả về bởi thuật toán II.1.

Giả sử A thuộc X+ nhưng A không thuộc tập X(j ) được trả về bởi Thuật toán II.1. Chú ý rằng X(i )= X(i+1 )bởi vìđó là điều kiện để Thuật toán II.1 kết thúc.

Xét quan hệ r tương tự nhưHình II.3: r có hai bộ giống nhau ở các thuộc tính của X(i ) nhưng khác nhau ở tất cả các thuộc tính khác. Chúng ta khẳng định rằng r thoả F. Thật vậy, gọi U V là một phụ thuộc trong F bị vi phạm bởi r. Thế thì UX(i )và V không thể là một tập con của X(i )nếu xảy ra vi phạm (lập luận tương tự nhưtrong phần chứng minh Định lý II.1). Vì vậy không thể bằng với X(i )như đã giả định.

Do đó, quan hệ r cũng phải thoả X  A. Lý do là A được giả thiết là thuộc X+, và vì thế X Ađược suy ra từ F bởi hệ tiênđề Armstrong. Vì các tiênđề này làđúngđắn nên bất kỳ quan hệ nào thoả F cũng thoả X A. Nhưng cách duy nhất X A có thể đúng trong r là A thuộc X(i ) bởi vì nếu không thì hai bộ của r, chắc chắn rằng giống nhau ở X, sẽ không giống nhau ở A và vì vậy vi phạm X  A. Chúng ta kết luận rằng A thuộc tập X(i )được trả về bởi Thuật toán II.1.