Cơ sở dữ liệu nâng cao - Buổi 7 - Chương 3: Giai đoạn thiết kế lô-gic

a Học Tự Nhiên - HCM
3
Nhắc lại bối cảnh thiết kế CSDL (tt)
Thiết kế quan niệm
Thiết kế lô-gíc
Thiết kế vật lý
Lược ñồ CSDL vật lý
Yêu cầu về
thông tin/dữ
liệu
Yêu cầu 
khai thác/ 
xử lý
Đặc trưng 
của hệ
QTCSDL
Đặc trưng của 
phần cứng 
và HĐH
CHƯƠNG III: 
Giai ñoạn thiết kế lô-gí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
5
Nội dung tuần này
III.1 Mục tiêu của giai ñoạn thiết kế lô-gíc
III.2 Nhắc lại một số khái niệm của lý thuyêt 
ñồ thị
III.3 Đồ thị các con ñường truy xuất
III.4 Đồ thị quan hệ
III.5 Chuyển ñổi ĐTQH 
 ĐT CĐTX và 
ngược lại
III.6 Chuổi kết ñược cài ñặt trên ñồ thị
© Đồ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
III.1 Mục tiêu của giai ñoạn
 Giai ñoạn thiết kế logic là bước trung gian 
ñể giai ñoạn thiết vật lý ñược thực hiện dễ
dàng.
 Biểu diễn lại mô hình CSDL mức quan niệm 
thành mô hình dữ liệu phù hợp với hệ quản trị
sẽ dùng ñể cài ñặt sau này.
 Độc lập với các ñặc trưng khác của hệ quản trị.
 Chọn một biểu diễn ở dạng ñồ thị phù hợp, 
làm cơ sở cho việc lựa chọn chỉ mục ở giai 
ñoạn thiết kế vật lý.
© Đồ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
III.1 Mục tiêu của giai ñoạn (tt)
 Kết quả của gñ phải hoàn toàn “trung 
thực” với cấu trúc quan niệm:
 Bảo toàn nội dung CSDL
 Bảo toàn sự truy xuất trực tiếp ñến các quan 
hệ của cấu trúc quan niệm.
 Khi một quan hệ con Qi tồn tại trong cấu trúc quan 
niệm C, một bộ của Qi có thể ñược truy xuất trực 
tiếp (không cần thông qua một quan hệ nào 
khác). Cấu trúc logic phải bảo toàn khả năng này.
 Bảo toàn tính hiệu quả trong việc kiểm tra ràng 
buộc toàn 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
8
III.1 Mục tiêu của giai ñoạn (tt)
 Ví dụ 3.1
Cho cấu trúc mức quan niệm: 
NhânViên (Ma_NV, HoTen_NV, Ma_P )
Phòng (Ma_P, Ten_P)
ĐềÁn (Ma_DA, Ten_DA, Ma_P)
PhânCông (Ma_NV, Ma_DA), 
ràng bu
c: M
t nhân viên ñc phân công vào 
tt c các ñ án do phòng ban mà nhân viên ñó
trc thu
c ph trách )
© Đồ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
Ví dụ 3.1 (tt)
Xét cấu trúc logic sau:
NhânViên (Ma_NV, HoTen_NV, Ma_P )
Phòng (Ma_P, Ten_P)
ĐềÁn_1 (Ma_DA, Ten_DA)
PhụTrách (Ma_DA, Ma_P)
Không có quan hệ PhânCông: có bảo toàn nội 
dung không?
Có bảo toàn sự truy xuất trực tiếp ñến quan hệ
PhânCông không?
© Đồ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.2 Lý thuyết ñồ thị - một số khái 
niệm
 Đồ thị G(N,C) ñược ñịnh nghĩa trên một 
tập nút N={n1,n2,…nn} và một tập cung 
C={c1, c2,…cm}
 Đồ thị có hướng nếu tồn tại một cung có 
hướng (khi ñó các nút trong ñồ thị gọi là nút 
ñi hoặc nút ñến), ngược lại ñồ thị vô hướng 
(các nút gọi là nút xuất phát).
 Đng ñi (ñối với ñồ thị vô hướng) và mch 
ñi (ñối với ñồ thị có hướng)
 Khuyên & Chu trì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
11
III.2 Lý thuyết ñồ thị - một số
khái niệm (tt)
 Dòng có gốc n1 là một tập cung D = (c1, c2, 
…,cp) sao cho:
 Một cung trong tập D có nút xuất phát (hoặc nút 
ñi) là n1
 ∀ ni là nút xuất phát (hoặc nút ñi/ ñến) của ci ∈ D, 
tồn tại một ñường ñi hoặc mạch ñi từ gốc n1 ñến 
ni qua các cung của D.
© Đồ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.2 Lý thuyết ñồ thị - Ví dụ 3.2
(c1, c2) là một dòng có gốc n1
(c1, c2) không là một dòng có gốc n2
(c1, c2) là một mạch ñi
(c1, c2) là một dòng có gốc n2
(c1, c2) không là một mạch ñi
(c1, c2) không là dòng của gốc nào cả
(c1, c2) là dòng của gốc n1, n2 hoặc n3
© Đồ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.3 Đồ thị con ñường truy xuất
 Định nghĩa:
 Đồ thị con ñường truy xuất là một ñồ thị có 
hướng với:
 N: Tập các nút của ñồ thị
 C ⊆ (N x N): Tập các cung (có hướng)
 Q: tập các quan hệ Qi.
 Cñ: Tập các con ñường truy xuấ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
14
III.3 Đồ thị CĐTX – Định nghĩa (tt)
 Mỗi cung trên ñồ thị tương ứng với một con 
ñường truy xuất ñến 1 hoặc n bộ của quan hệ
nút ñến.
 Một quan hệ Qi∈ Q có thể là quan hệ nút (nếu 
nó tương ứng với một nút trên ñồ thị) hoặc 
quan hệ cung (nếu nó ứng với một cung trên 
ñồ thị).
 Mỗi quan hệ cung có thể tương ứng với tối ña 
hai cung ngược chiều nhau trên ñồ thị CĐTX, 
nút ñến của cung này là nút ñi của cung kia và 
ngược lạ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.3 Đồ thị CĐTX – Định nghĩa (tt)
 Ni Nj: Từ một bộ của quan hệ nút QNi có
thể truy xuất từ 1 ñến n bộ của quan hệ nút 
QNj thông qua con ñường truy xuất tương ứng 
với cij. 
 Ni Nj: Từ một bộ của quan hệ nút QNi có
thể truy xuất ñến 1 bộ của quan hệ nút QNj 
thông qua con ñường truy xuất tương ứng với 
cij.
 Trên mỗi con ñường truy xuất có gắn một bản 
số (n1, n2, n3) thể hiện số bộ tối thiểu, trung 
bình và tối ña có thể ñược truy xuất 
cij
cij
© Đồ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
III.3 Đồ thị CĐTX – Ví dụ 3.3
Ngõ vào 
CSDL
Ngõ vào 
CSDL
© Đồ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.3 (tt)
 Diễn giải:
 Có hai ngõ vào CSDL: NhânViên_2 và ĐềÁn_2, nghĩa là cung 
cấp một giá trị Ma_NV (Ma_DA), ta có thể truy xuất ngay một 
bộ tương ứng trong quan hệ NhânViên_2 (ĐềÁn_2).
 Từ một bộ NhânViên_2, ta có thể truy xuất trực tiếp một bộ
của Phòng_2 mà nhân viên trực thuộc, thông qua con ñường 
truy xuất NhânViên_2 → Phòng_2.
 Từ một bộ của Phòng_2, ta có thể truy xuất trực tiếp danh 
sách các nhân viên của phòng thông qua con ñường truy 
xuất Phòng_2 → NhânViên_2.
 Từ một bộ của NhânViên, ta không thể truy xuất trực tiếp
danh sách các ñề án mà nhân viên ñược phân công, do 
không có con ñường truy xuất NhânViên_2 → ĐềÁn_2.
© Đồ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
Đồ thị con ñường truy xuất thô
 Là ñồ thị con ñường truy xuất ñặc biệt, 
trong ñó, nếu giữa hai nút của ñồ thị có
một cung thì bao giờ cũng tồn tại một 
cung theo chiều ngược lạ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
19
III.4 Đồ thị quan hệ
 Đồ thị quan hệ là một dạng ñồ thị con 
ñường truy xuất ñược ñơn giản hoá
 Giúp người thiết kế dễ dàng hơn trong việc 
ñánh giá chất lượng của biểu diễn cấu trúc 
CSDL ở dạng ñồ thị.
 Đồ thị quan hệ là một ñồ thị có hướng, với:
 NQ: Tập nút
 CQ ∈ NQ x NQ: tập cung có hướng/vô hướng
 QQ : tập quan hệ 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
20
III.4 Đồ thị quan hệ (tt)
 Diễn giải: 
 Ni Nj: 
 Qi, Qj là các quan hệ lần lượt ứng với hai nút Ni 
và Nj 
 có một phụ thuộc hàm KQi → KQj, với KQi và
KQj lần lượt là một khóa của Qi và Qj
 Quan hệ cung Qij ñược hình thành từ tất cả các 
thuộc tính khóa của Qi, Qj: Qji+ = KQi+ ∪ KQj+
Qij
© Đồ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
III.4 Đồ thị quan hệ của ví dụ 3.3 (tt)
© Đồ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
III.5 a.Biến ñổi từ ñồ thị CĐTX thô 
sang ĐTQH
 NQ = N
 QQ = Q
 ∀c,c’ ∈ C có chiều ngược nhau và cùng ứng với 
một quan hệ cung Qc, ∃ cQ ∈ CQ sao cho cQ 
cũng ứng với quan hệ Qc trong QQ.
 Cung cQ là cung vô hướng nếu bản số của c và c’ 
ñều có giá trị tối ña (max(c), max(c’)) lớn hơn 1 
 Ngược lại cQ là cung có hướng
© Đồ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
III.5 b.Chuyển từ ĐTQH sang ñồ
thị CĐTX thô
 N =NQ 
 Q= QQ
 ∀cQ = (n1, n2) ∈ CQ, (cQ ứng với một quan hệ
Qc ∈ QQ), ∃ c,c’ ∈ C có chiều ngược nhau và
cùng ứng với một quan hệ cung Qc ∈ Q. 
 Nếu cQ là cung vô hướng: max(c) >1 và max(c’)>1 
 Ngược lại max(c) =<1 hoặc max(c’) <= 1
 Các nút trong N ñều là nút và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
24
III.6 Chuỗi kết ñược cài ñặt trên 
ĐTQH / ñồ thị CĐTX
 Khái niệm chui 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
25
III.6 a. Chuỗi kết ñược cài ñặt 
trên ñồ thị CĐTX
 Một chuỗi kết p = Q1 Q2… Qm ñược 
cài ñặt trên ñồ thị CĐTX (N,C,Q,Cñ ) nếu và
chỉ nếu:
 ∀ Qi, i=1..m, Qi ∈ Q
 ∃ một dòng D = (c1, c2,… ,cp) trên ñồ thị CĐTX sao 
cho :
 ∀ cung ci của D, ci ứng với một quan hệ Qj, trong 
chuỗi kết
 ∀ Qi trong chuỗi kết : ∃ một cung c của D ứng với Qi
Hoặc ∃ một nút n trên D ứng với 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
26
III.6 b. Chuỗi kết ñược cài ñặt 
trên ĐTQH
 Một chuỗi kết p = Q1 Q2… Qm ñược 
cài ñặt trên ĐTQH (NQ,CQ,QQ) nếu và chỉ
nếu:
 ∀ Qi, i=1..m, Qi ∈ QQ
 ∃ một dòng D = (c1, c2,… ,cp) trên ñồ thị quan hệ
sao cho :
 ∀ cung ci của D, ci ứng với một quan hệ Qj, trong 
chuỗi kết
 ∀ Qi trong chuỗi kết: ∃ một cung c của D ứng với Qi
Hoặc ∃ một nút n trên D ứng với 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
27
Chuỗi kết trên ñồ thị - Ví dụ 3.4
Chuỗi kết (AX) (AB) (BY) (BC) (CZ) ñược cài 
ñặt trên (a), (b), (d) nhưng không ñược cài ñặt trên (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
28
Chuỗi kết trên ñồ thị - Diễn giải
 Nếu chuỗi kết ρ ñược cài ñặt trên ñồ thị, 
tồn tại một dòng D có gốc là ng. 
 Từ quan hệ Qg ứng với ng ta có thể truy xuất 
nhanh ñến những bộ của Qi trong ρ thông 
qua các ñường ñi hoặc mạch ñi xuất phát từ
ng
© Đồ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
29
Câu hỏi?