PHÉP GIẢN LƯỢC CỦA LƯỢC ĐỒ QUAN HỆ

CHƯƠNG 2.

2.1. Phép biến đổi LĐQH [2]

Cho hai LĐQH p = (U,F), q = (V,G) và tập thuộc tính M ⊂ U. Ta nói LĐQH q nhận được từ LĐQH p qua phép thu gọn (dịch chuyển) theo tập thuộc tính M, nếu sau khi loại bỏ mọi xuất hiện của các thuộc tính của M trong lược đồ p thì thu được lược đồ q.

Nếu sau khi thực hiện phép thu gọn theo M cho LĐQH p ta thu được LĐQH q thì ta viết q = pM.

Thao tác loại bỏ M được thực hiện trên lược đồ p = (U,F) để thu được lược đồ q = (V,G) như sau:

1. Tính V = UM có độ phức tạp O(n) với n là số lượng thuộc tính trong U.

2. Mỗi PTH X↑Y trong F ta tạo ra PTH XM↑YM cho G. Thủ tục này ký hiệu là G = FM. Tính FM đòi hỏi độ phức tạp O(mn) với m là số lượng PTH trong F.

2.2. Thuật toán biến đổi LĐQH [2, 3]

Input:

- LĐQH p = (U,F)

- Tập thuộc tính M ⊂U

Output:

LĐQH q = (V,G) = pM, V = UM, G = FM.

Method

V := UM;

G := ⊕

For each FD L↑R in F do

G := G ∩ {LM↑RM};

Endfor;

G := Natural_Reduced(G);

Return (V,G);

End Translation.

Thủ tục Natural_Reduced(G) đưa tập PTH G về dạng thu gọn tự nhiên bằng cách loại khỏi G những PTH tầm thường (có vế trái chứa vế phải), chuyển đổi mỗi PTH có hai vế trái phải rời nhau và gộp các PTH có cùng vế trái.

2.3. Định lý cơ bản của phép biến đổi LĐQH. [2]

Cho LĐQH a=(U, F) và hai tập con rời nhau X và Y trong U. Khi đó (XY)⁺_F = XY⁺_{FX .}

2.4. Dạng biểu diễn thứ nhất của cơ sở [2, 3, 4]

Nếu dịch chuyển LĐQH p = (U,F) theo tập X⊂U để nhận được LĐQH

q = pX thì:

1. Base (p) = Base (q) khi và chỉ khi X⊂U_o
2. Base (p) = X⊗Base (q) khi và chỉ khi X⊂U_I

2.5. Dạng biểu diễn thứ hai của cơ sở [2, 3, 4]

Cho LĐQH p = (U,F). Khi đó mọi cơ sở B của p đều biểu diễn được dưới dạng K = LM trong đó L là vế trái cực tiểu, không chứa tập con khác rỗng (vô sinh) của F và M là cơ sở của LĐQH pL⁺.