Cơ sở dữ liệu nâng cao - Buổi 8

Buổi # 8 
(lớp TH2008-1)
Cơ sở dữ liệu nâng cao
Đồng Thị Bích thủy
26/10/2010
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
2
Nội dung tuần này
III.6 Chuổi kết ñược cài ñặt trên ñồ thị (nhắc 
lại)
III.7 Thuật toán biến ñổi cấu trúc CSDLQH
III.8 Chuyển từ ñồ thị quan hệ sang cấu trúc 
CSDL quan hệ
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
3
III.6 Chuỗi kết ñược cài ñặt trên 
ĐTQH / ñồ thị CĐTX (nhắc lại)

 Khái niệm chu
i kt ñc cài ñt trên ñ
th quan h	 là cơ sở ñể ñánh giá tính hiệu 
quả của cấu trúc lô-gíc khi thực hiện phép 
kết.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
4
Lấy lại Ví dụ 3.1
Cho cấu trúc mức quan niệm: 
NhânViên (Ma_NV, HoTen_NV, Ma_P)
NhânViên_2 (Ma_NV, HoTen_NV)
Thuộc (Ma_NV, Ma_P)
Phòng (Ma_P, Ten_P)
ĐềÁn (Ma_DA, Ten_DA, Ma_P)
ĐềÁn_2 (Ma_DA, Ten_DA)
PhụTrách (Ma_DA, Ma_P)
PhânCông (Ma_NV, Ma_DA), 
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
5

 Tên các ñề án do phòng của nhân viên 
NVA phụ trách:
pi Ten_DA σHoTen_NV = “NVA”
(NhânViên_2 Thuộc Phòng 
PhụTrách ĐềÁn_2)
Chuổi kết thể hiện câu truy vấn
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
6
Đồ thị quan hệ của ví dụ 3.1 
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
7
Đồ thị CĐTX của ví dụ 3.1
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
8
III.7 Thuật toán biến ñổi lược ñồ
CSDLQH

 Vào: Cấu trúc CSDL mức quan niệm :
ρ = {}, mỗi Qi có tập khóa {Ki}

 Ra: Đồ thị quan hệ tương ứng với ρ
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
9
III.7 Thuật toán (2)

 Bước 1 - Biến ρ thành một phân rã ñồng nhất:
1.1. ∀ (Qi, Qj):
nếu Ki ↔Kj, với Ki và Kj lần lượt là một khóa 
của Qi và Qj, 
thì gộp Qi, Qj lại thành một quan hệ.
1.2. ∀(Qi, Qj): 
nếu Qi+ có chứa một khóa Kj của Qj 
thì Qi+ phải chứa tất cả các khoá của Qj 
(khi ñó Qi có thể có thêm khoá)

 Bước 2 - Tạo nút và quan hệ nút:
∀ Qi: tạo một nút Ni với QNi = Qi
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
10
III.7 Thuật toán (3)

 Bước 3 - Tạo nút bản lề và quan hệ nút 
tương ứng:
*** M
c ñích: làm ni bt các thu
c tính chung ca m
i 
cp quan h	 nút ***
3.1. ∀ (Qi, Qj), Qij+ = Qi+ ∩ Qj+
3.2. Chừng nào Qij+ ≠ ∅ :

 Xác ñịnh tất cả các khóa củaQ[Qij+], ký hiệu KQij+ là tập 
thuộc tính khóa của Q[Qij+]

 Nếu ¬∃ Qh ∈ ρ sao cho một khóa của Qh là một khoá của 
Q[Qij+] 
thì Tạo nút bản lề Nbl với quan hệ tương ứng Qbl = Q[KQij+]
Cuối nếu

 Qij+ := Qij+ - KQij+
Cuối Chừng nào
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
11
III.7 Thuật toán (4)

 Bước 4 - Tạo cung 
*** ch to s cung ti thiu t m
t nút ***
4.1. ∀Ni với Qi tương ứng, xác ñịnh:
PTH(Ni) = {Nj với Qj tương ứng sc KQj+ ⊂ Qi+}
PTH_Thừa(Ni) = {Nj ∈PTH(Ni) | 
∃Nh ∈ PTH(Ni) với KQj+⊂ KQh+}
Lồng_Khoá(Ni) = {Nj với Qj tương ứng | KQj+⊂ KQi+}
Lồng_Khoá_Thừa (Ni) = 
{Nj ∈ Lồng_Khoá(Ni) | ∃Nh ∈ Lồng_Khoá(Ni) với Qh 
sao cho KQj+⊂ KQh+}
Cung (Ni) = (PTH(Ni) – PTH_Thừa(Ni) ) ∪
( Lồng_Khoá(Ni) – Lồng_Khoá_Thừa(Ni) )
Cuối ∀
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
12
III.7 Thuật toán (5)

 Bước 4 (tiếp)
4.2. ∀Nj ∈ Cung(Ni) :
Tạo một cung có hướng từ Ni → Nj, 
ký hiệu cij
Cuối ∀
4.3. Qij = Qi[KQi+ ∪ KQj+]
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
13
III.7 Thuật toán (6)

 Bước 5 - Hủy những nút bản lề thừa
 ∀Nk thỏa các ñiều kiện:
 Qk có một khóa duy nhất Kk
 Không có thuộc tính nào khác ngoài khóa
 Chỉ có một cung vào Nk, xuất phát từ nút Ni
Thì ***Vai trò bản lề của Nk không còn cần thiết nữa

 Nhập Nk vào Ni (nhập Qk+ vào Qi+) 

 Hủy cung cik
 Cuối ∀
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
14
III.7 Thuật toán (7)

 Bước 6 - Mịn hóa các quan hệ nút:
 ∀ Ni với Qi tương ứng thì:
∀ Nj ∈ Cung(Ni) với Qj tương ứng thì:
Loại khỏi Qi+ những thuộc tính khóa của 
Qj mà không phải là thuộc tính khóa của Qi
Cuối ∀
 Cuối ∀
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
15
III.7 Thuật toán (8)

 Bước 7 - Tạo cung vô hướng:
∀ Nk thỏa:

 Qk chỉ có toàn thuộc tính khóa (Qk+ = KQk+)

 Chỉ có hai cung ra khỏi Nk (không có cung vào) ñến 
Ni và Nj với Qi và Qj sao cho KQk+ = KQi+ ∪ KQj+
Thì

 Tạo một cung vô hướng nối Ni, Nj với Qij = Qk

 Hủy nút Nk

 Hủy hai cung cki và ckj
Cuối ∀
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
16
Ví dụ 3.5
Cho cấu trúc quan niệm sau:
ĐĐH (Số_ĐĐH, Ngày_ĐH, TrịGiá)
MặtHàng (Mã_MH, Tên_MH, ĐơnGiá)
ChiTiếtĐĐH (Mã_MH, Số_ĐĐH, SL_ĐH)
Giao hàng (Số_GH, Ngày_GH, Số_ĐĐH)
ChiTiếtGH (Số_GH, Mã_MH, SL_GH, Số_ĐĐH)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
17
Ví dụ 3.5 (2)
 Bước 1: không có khóa tương ñương giữa 
các quan hệ
 Bước 2: Tạo nút
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
18
Ví dụ 3.5 (3)
 Bước 3: 
 Các tập thuộc tính chung khác rỗng của các cặp 
quan hệ:

 (1 và 3), (1 và 4), (1 và 5): So_ĐĐH, khoá của 1

 (2 và 3): Ma_MH, khoá của 2

 (2 và 5): Ma_MH, khoá của 2

 (3 và 5): Ma_MH, So_ĐĐH  Khóa = (Ma_MH, So_ĐĐH) 
= khóa của 3

 (4 và 5): So_GH, So_ĐĐH  Khóa = (So_GH) = Khoá của 
4; loại bỏ So_GH; 
khóa của tập còn lại là (So_ĐĐH) = khóa của 1
 Kết luận: Không tạo nút bản lề nào cả
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
19
Ví dụ 3.5 (4)
 Bước 4
2,3,4∅2,41,21,2,3,45.ChiTiếtGH
∅-∅∅14. GiaoHàng
1,2∅1,2∅1,23. 
ChiTiếtĐĐH
∅---∅2.MặtHàng
∅---∅1. ĐĐH
Cung(Qi)LK_Thừa 
(Qi)
Lồng_ 
Khoá(Qi)
PTH_
Thừa(Qi)
PTH(Qi)
Ghi chú “-” : không cần tính
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
20
Ví dụ 3.5 (5)
 Các quan hệ cung:

 Cung 31: CTĐĐH_ĐĐH (Ma_MH, So_ĐĐH)

 Cung 32: CTĐĐH_MH(Ma_MH, So_ĐĐH)

 Cung 41: GH_ĐĐH(So_GH, So_ĐĐH)

 Cung 52: CTGH_MH (So_GH, Ma_MH)

 Cung 53: CTGH_CTĐĐH (So_GH, Ma_H, So_ĐĐH)

 Cung 54: CTGH_GH (So_GH, Ma_MH)
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
21
Ví dụ 3.5 (6)
 Kết quả của bước 1-4
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
22
Ví dụ 3.5 (7)
 Bước 5: Không thực hiện, vì không tạo nút bản 
lề nào
 Bước 6: 

 Trong quan hệ nút GiaoHàng, loại bỏ thuộc tính 
Số_ĐĐH

 Trong quan hệ nút ChiTiếtGH, loại bỏ thuộc tính 
Số_ĐĐH
 Bước 7: không tạo ñược cung vô hướng nào 
cả.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
23
Ví dụ 3.5 (8)
 Kết quả thuật toán:
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
24
III.8 Biến ñổi từ ñồ thị quan hệ 
sang lược ñồ CSDL quan hệ

 Mục ñích: kiểm chứng xem cấu trúc quan hệ biểu 
diễn dưới dạng ñồ thị quan hệ có hoàn toàn tương 
ñương với cấu trúc ban ñầu hay không.

 Thuật toán:
 Gọi ρ-1 là tập quan hệ con có ñược sau khi biến 
ñổi từ ñồ thị quan hệ về cấu trúc CSDL quan hệ:
 ρ-1 = {Qi} ∪ {Qij}, với Qi là quan hệ nút và Qij là
quan hệ cung
 Gộp các quan hệ có cùng khóa trong ρ-1 lại thành 
một.
© Đồng Thị Bích Thủy Bộ môn Hệ Thống Thông Tin
Trường ĐH Khoa Học Tự Nhiên - HCM
25
Câu hỏi?