Bài tập lý thuyết Cơ sở dữ liệu
Cho lược đồ quan hệ R=(U, F). Bao đóng của tập thuộc tính X (X ⊆ U), ký hiệu X + là tập tất hợp cả các thuộc tính mà có thể suy diễn logic từ X. Nhận xét: Bao đóng của tập thuộc tính X thực chất là tập tất cả các thuộc tính mà ...
Cho lược đồ quan hệ R=(U, F). Bao đóng của tập thuộc tính X (X ⊆ U), ký hiệu X+ là tập tất hợp cả các thuộc tính mà có thể suy diễn logic từ X.
- Nhận xét: Bao đóng của tập thuộc tính X thực chất là tập tất cả các thuộc tính mà ta có thể “với tới” (hay suy ra) nó từ tập thuộc tính X ban đầu.
- Việc tính toán bao đóng là cơ sở cho việc tìm khoá, tìm tập khoá, kiểm tra một phụ thuộc hàm nào đó có tồn tại trong quan hệ hay không...
- Đầu vào: Tập thuộc tính X cần tính bao đóng trên lược đồ quan hệ R=(U,F).
- Đầu ra: Tập thuộc tính X +
Phương pháp
Kiểm tra lần lượt từng phụ thuộc hàm fi=α→β size 12{ ital "fi"=α rightarrow β} {}, nếu α⊆X+ size 12{α subseteq X rSup { size 8{+{}} } } {} thì kết nạp vế phải (tức β size 12{β} {}) vào vào X+: X+=X+∪β size 12{X rSup { size 8{+{}} } =X rSup { size 8{+{}} } union β} {}
Lặp lại cho đến khi nào X+ = Const.
Thuật toán 1:
CònThayĐổi := True;
X+ := X;
While Còn_Thay_Đổi Do
Begin
Còn_Thay_Đổi := False;
For mỗi fi=α→β Do
Begin
If α⊆X+ Then
Begin
X+=X+∪β ;
Còn_Thay_Đổi := True;
End;
End;
End;
Cho lược đồ quan hệ R = (U, F) với U= {A,B,C,D,E,G,H} và F= {AB→C, D→EG, ACD→B, C→A, BE→C, CE→AG, BC→D, CG→BD, G→ H}
- Tính (D)+
- Tính (DE)+
- Tính (BE)+
- Tính (CG)+
a) Tính (D) +
X0 = D
1) X1 = DEG (áp dụng D→EG)
2) X2 = DEGH (áp dụng G→H) (= Constant)
Vậy (D)+ = DEGH
b) Tính (DE) +
X0 = DE
1) X1 = DEG (áp dụng D→EG)
2) X2 = DEGH (áp dụng G→H) (= Constant)
Vậy (DE)+ = DEGH
c) Tính (BE) +
X0 = BE
1) X1 = BEC (áp dụng BE→C)
2) X2 = BECAG (áp dụng CE→AG)
3) X3 = BECAGD (áp dụng BC→D)
4) X4 = BECAGDH (áp dụng G→H) (= Constant)
Vậy (BE)+ = ABCDEGH
d) Tính (CG) +
X0 = CG
1) X1 = CGA (áp dụng C→A)
2) X2 = CGABD (áp dụng CG→BD)
3) X3 = CGABDH (áp dụng G→H)
4) X4 = CGABDHE (áp dụng D→EG) (= Constant)
Vậy (CG)+ = ABCDEGH
Cho lược đồ quan hệ R = (U, F) với U = {A,B,C,D,E,G} và F = {C→G, BG → CD, AEG → BC, CG → AE, B → CG }
- Tính C+
- Tính (B)+
- Tính (AEG)+
a) Tính C +
X0 = C
1) X1 = CG (áp dụng C→G)
2) X2 = CGAE (áp dụng CG→AE)
3) X3 = CGAEB (áp dụng AEG→BC)
4) X4 = CGAEBD (áp dụng BG→CD) (= Constant)
Vậy (C)+ = ABCDEG
b) Tính (B)+
X0 = B
1) X1 = BCG (áp dụng B→CG)
2) X2 = BCGD (áp dụng BG→CD)
3) X3 = BCGDAE (áp dụng CG→AE) (= Constant)
Vậy (B)+ = ABCDEG
c) Tính (AEG)+
X0 = AEG
1) X1 = AEGBC (áp dụng AEG→BC)
2) X2 = AEGBCD (áp dụng BG→CD) (= Constant)
Vậy (AEG)+ = ABCDEG
Một ví dụ về tính bao đóng của tập phụ thuộc hàm.
Tính (BG → CD)+ với R cho ở bài tập 2.
X0 = BG → CD
X1 = (BG→C, BG → D) (Theo luật tách trong hệ tiên đề Amstrong)
X2 = (BG → C, BG → D, BG → B, BG → G) (Theo luật phản xạ)
X3 = (BG → B, BG → G, BG → C, BG → D, BG → CG) (Luật hợp)
X4 = (BG → B, BG → G, BG → C, BG → D, BG → CG, CG → AE) …..
