CHƯƠNG I:
1.1. Quan hệ và bộ [2]
Cho tập hữu hạn U = {A 1, A 2, …, A n} khác trống (n ≥ 1). Các phần tử của U được gọi là thuộc tính, ứng với mỗi thuộc tính A i ⊆ U, i = 1, 2, …, n có một tập không rỗng dom(A i) được gọi là miền trị của thuộc tính A i (thập chí được giả thiết là chứa hơn 1 giá trị).
Đặt D=Ui=1ndom(Ai) size 12{D= {U} cSub { size 8{i=1} } cSup { size 8{n} } ital “dom” ( { size 24{A} } rSub { size 8{i} } ) } {}
Một quan hệ R với các thuộc tính U = {A 1, A 2, …, A n}, ký hiệu là R(U), là một tập các ánh xạ t: U ↑ D sao cho với mỗi A i ⊆ U ta có t(A i) ⊆ dom(A i). Mỗi ánh xạ được gọi là một bộ của quan hệ R.
Mỗi quan hệ R(U) có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính, mỗi dòng là một bộ.
Ta ký hiệu t(X) hoặc t.X là một bộ trên tập thuộc tính X.
Một quan hệ rỗng, ký hiệu ⊕, là quan hệ không chứa bộ nào.
Chú ý: Mỗi quan hệ là một tập các bộ nên trong quan hệ không có hai bộ trùng lặp.
1.2. Phụ thuộc hàm, hệ tiên đề Armstrong, lược đồ quan hệ.
1.2.1. Phụ thuộc hàm [2]
ζ Định nghĩa phụ thuộc hàm
Cho tập thuộc tính U. Giả sử X, Y ⊂ U. Một phụ thuộc hàm (PTH) trên U là biểu thức dạng f: X ↑ Y.
Nếu f: X ↑ Y là một PTH trên U thì ta nói tập thuộc tính Y phụ thuộc hàm vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc tính Y.
Cho quan hệ R(U) và một PTH f: X ↑ Y trên U. Ta nói quan hệ R thỏa PTH f (hay PTH f đúng trong quan hệ R), ký hiệu R(f), nếu hai bộ tùy ý trong R giống nhau trên X thì cũng giống nhau trên Y, tức là:
R(X ↑ Y) ⇔ u,v ⊆ R: u.X = v.X ⇒ u.Y = v.Y
1.2.2. Hệ tiên đề Armstrong [2, 3]
Cho quan hệ R(U). Giả sử X, Y, Z, W ⊂ U.
F1. Tính phản xạ:
Nếu X ⊃ Y thì X ↑ Y
F2. Tính gia tăng:
Nếu X ↑ Y thì XZ ↑ YZ
F3. Tính bắc cầu:
Nếu X ↑ Y và Y ↑ Z thì X ↑ Z
Chú ý: Các PTH có vế trái chứa vế phải như mô tả trong F1 được gọi là tầm thường. Các PTH tầm thường thoả trong mọi quan hệ.
1.2.3 Lược đồ quan hệ [2]
Lược đồ quan hệ (LĐQH) là một cặp p = (U, F) trong đó U là tập hữu hạn các thuộc tính, F là tập các PTH trên U.
Quy ước: Trong trường hợp không chỉ rõ tập PTH F, ta xem LĐQH chỉ là một tập hữu hạn các thuộc tính U.
1.3. Bao đóng của tập thuộc tính [2]
– Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Bao đóng của tập thuộc tính X, ký hiệu X+, là tập tất cả các thuộc tính A ⊆ U mà PTH X↑A có thể được suy diễn logic từ F nhờ hệ tiên đề Armstrong:
Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong U. Để xác định bao đóng của tập thuộc tính X , ký hiệu X + xuất phát từ tập X và bổ sung dần cho X các thuộc tính thuộc vế phải của các PTH L↑R size 12{ in } {} F thoả điều kiện L size 12{ subseteq } {} X. Thuật toán sẽ dừng khi không thể bổ sung thêm thuộc tính nào cho X.
Algorithm Closure
Input: – Tập thuộc tính X ⊂ U
– Tập PTH F
Method
Y: = X ;
Repeat
Z: = Y ;
For each FD L↑R in F do
If L ⊂ Y then Y: = Y∩R ;
Enddif ;
Endfor ;
Until Y: = Z;
Return Y;
End Closure.
Giả sử n là số lượng các thuộc tính trong U, m là số lượng các PTH trong F thì thuật toán trên có độ phức tạp đa thức bậc hai theo chiều dài dữ liệu O(mn2).
1.4. Phủ của tập phụ thuộc hàm [2, 3]
Cho hai tập PTH F và G trên cùng một tập thuộc tính U. Ta nói F suy dẫn được ra G, ký hiệu F╞ G nếu g⊆G: F╞ g.
Ta nói F tương đương với G, ký hiệu F ≠ G, nếu F╞ G và G╞ F.
Nếu F ≠ G ta nói G là một phủ của F.
Ký hiệu: F !╞ G: F không suy dẫn ra được G
F !≠ G có nghĩa là F và G không tương đương.
Cho tập PTH F trên tập thuộc tính U và X là tập con của U, ta dùng ký hiệu X F+ trong trường hợp cần chỉ rõ bao đóng của tập thuộc tính X lấy theo tập PTH F.
ζ Phủ thu gọn tự nhiên
Cho hai tập PTH F và G trên cùng một thuộc tính U. G là phủ thu gọn tự nhiên của F nếu:
G là phủ của F, và
G có dạng thu gọn tự nhiên theo nghĩa sau:
a. Hai vế trái và phải của mọi PTH trong G rời nhau (không giao nhau)
f ⊆ G: LS(f)⊘RS(f) = ⊕
b. Các vế trái của mọi PTH trong G khác nhau đôi một.
f,g ⊆ G: f ≃ g ⇔ LS(f) ≃ LS(g)
Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F
Algorithm Natural_Reduced
Function: Tính phủ thu gọn tự nhiên của tập PTH
Format: Natural_Reduced (F)
Input: Tập PTH F
Output: Một phủ thu gọn tự nhiên G của F
i) G ≠ F
ii) L↑R ⊆ G: L⊘R = ⊕
Method
G := ⊕;
For each FD L↑R in F do
Z := R L;
If Z ≃ ⊕ then
If there is an FD L↑Y in G then
Replace L↑Y in G by L↑YZ
Else Add L↑Z to G;
Endif
Endif
Endfor
Return G;
End Natural_Reduced.
Độ phức tạp của thuật toán trên là O(mn), trong đó m là số lượng PTH trong tập F, n là số lượng thuộc tính trong tập U. Để ý rằng mn là chiều dài dữ liệu vào của thuật toán.
1.5. Cơ sở của lược đồ quan hệ. [2, 3]
(ii) A⊆B: (B{A})+ ≃ U
Hai điều kiện trên tương đương với
(i) B → size 12{ rightarrow } {} U
(ii) A⊆B: (B{A}) ! → size 12{ rightarrow } {} U
Nếu B thỏa mãn điều kiện (i) thì B được gọi là một siêu cơ sở.
Thuộc tính A ⊆ U được gọi là thuộc tính cơ sở (nguyên thủy hoặc cơ sở) nếu A có mặt trong một cơ sở nào đấy. A được gọi là thuộc tính không cơ sở (phi nguyên thủy hoặc thứ cấp) nếu A không có mặt trong bất kỳ cơ sở nào. Ký hiệu U B là tập các thuộc tính cơ sở của LĐQH p và U 0 là tập các thuộc tính không cơ sở của p.
Chú ý: Trong một số tài liệu, thuật ngữ cơ sở được dùng theo nghĩa siêu cơ sở và thuật ngữ cơ sở tối tiểu được dùng theo nghĩa cơ sở .
Thuật toán tìm một cơ sở của LĐQH
Tư tưởng: Xuất phát từ một siêu cơ sở B tuỳ ý của LĐQH, duyệt lần lượt các thuộc tính A của B, nếu bất biến (B{A})+ = U được bảo toàn thì A loại khỏi B. Có thể thay kiểm tra (B{A})+ = U bằng kiểm tra A ⊆ (B{A})+
Algorithm Base
Function: Tìm một cơ sở của LĐQH
Input: – Tập thuộc tính U
– Tập PTH F
Output: Cơ sở B ⊂ U thoả
ii) A⊆B : (B{A})+ ≃ U
Method
B := U;
For each attribute A in U do
If A ⊆ (B{A})+ then
B := B {A}
Endif;
Endfor;
Return B;
End Base.
Độ phức tạp tính toán: Thuật toán duyệt n thuộc tính, với mỗi thuộc tính thực hiện phép lấy bao đóng với độ phức tạp n 2m. Tổng hợp lại, độ phức tạp tính toán của thuật toán là O(n 3 m).
1.6. Cách tính giao các cơ sở [2]
Những phần tử không xuất hiện ở vế phải thì nó có mặt ở mọi cơ sở, đó chính là giao các cơ sở.
Vậy giao các cơ sở chính là những thuộc tính không xuất hiện ở vế phải.
Gọi M là giao các cơ sở khi và chỉ khi: M+ = U.
Cho LĐQH p = (U,F) với n thuộc tính trong U và m PTH trong F. Gọi M là giao các cơ sở của p. Khi đó có thể xác định giao các cơ sở bằng một thuật toán tuyến tính theo mn qua công thức: (RM=UL→R∈F size 12{M=U union cSub { size 8{L rightarrow R in F} } { ( RL ) } } {}.
Thuật toán xác định giao các cơ sở trong LĐQH
Algorithm BaseIntersec
Input:- Tập thuộc tính U
– Tập PTH F
Output: Giao các cơ sở (RM=UL→R∈F size 12{M=U union cSub { size 8{L rightarrow R in F} } { ( RL ) } } {}
Method
M:=U;
For each FD L↑R in F do
M:=M(RL);
Endfor;
Return M;
End BaseIntersec.
1.7. Thuật toán tìm 2 cơ sở của LĐQH [2]
Bước 1: Tính giao các cơ sở
Bước 2: Tính M +. Nếu M + = U ⇒ size 12{ drarrow } {} Lược đồ có 1 cơ sở M là duy nhất
Gọi thuật toán Base 1 – Tìm cơ sở 1
Gọi thuật toán Base 2 – Tìm cơ sở 2
Thuật toán tìm cơ sở thứ hai của LĐQH
Tư tưởng: Xuất phát từ tập thuộc tính M = U, trước hết duyệt các thuộc tính A của B, nếu bất biến (M{A})+ = U được bảo toàn thì loại A khỏi M. Sau đó duyệt tương tự với các thuộc tính trong UB.
Algorithm Base 2
Function: Tìm một cơ sở thứ 2 của LĐQH
Input: – Tập thuộc tính U
– Tập PTH F
– Cơ sở B size 12{ subseteq } {} U
Output: Cơ sở thứ hai, nếu có, M ⊂ U thoả
ii) A⊆M : (M{A})+ ≃ U
Nếu không có cơ sở thứ 2: {} ⊕
Method
M := U;
For each attribute A in K do
If A ⊆ (M{A})+ then
M := M {A}
Endif;
Endfor;
For each attribute A in U B do
If A ⊆ (M{A})+ then
M := M {A}
Endif;
Endfor;
If M = K then return ⊕
Else return M;
Endif
End Base 2.