các hệ cơ sở dữ liệu nâng cao
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (114.45 KB, 19 trang )
Bài giảng #1
Các hệ cở sở dữ liệu nâng cao
Cao hc KHMT & HTTT
Đồng Thị Bích Thủy
04/2012
Các hệ CSDLNC - Cao học
2
(c) Đồng Thị Bích Thủy
1. Vài ñịnh nghĩa (nhắc lại)
Lược ñồ CSDL: C = <Q,D> hoặc
C
= {<Q
i
,D
i
>}
i=1 n
D, D
i
: tập phụ thuộc ñ/n trên Q, Q
i
, gồm
phụ thuộc hàm, F, F
i
, và những phụ
thuộc dữ liệu khác (ña trị, kết, tồn tại, )
Q
+
, Q
i
+
: tập thuộc tính của Q, Q
i
Các hệ CSDLNC - Cao học
3
(c) Đồng Thị Bích Thủy
1. Vài ñịnh nghĩa (tt)
C = {<Q
i
,F
i
>}
i=1 n
Nếu ∀
∀∀
∀f∈
∈∈
∈F
i
vt(f)=khóa của Q
i
, F
i
là tập pth
ñược
in trong Q
i
(embodied FD)
Nếu ∀
∀∀
∀f∈
∈∈
∈F
i
(vt(f) U vf(f) ) ⊆
⊆⊆
⊆ Q
i
+
, F
i
là tập pth
ñược
bao trong Q
i
(embedded FD)
Tập pth ñược bao trong Q chứa tập pth
ñược in trong Q.
Các hệ CSDLNC - Cao học
4
(c) Đồng Thị Bích Thủy
1. Vài ñịnh nghĩa (tt)
Q(XY) với f:X
A với A∈
∈∈
∈Y : kiểm tra f trong
TQ như thế nào
?
TQ:
Q(ABC) với:
f1: A
B (GV
Lp)
f2: B
C (Lp
Phòng)
f3: A
C (GV
Phòng)
Cần kiểm tra pth nào?
{f1, f2} hay {f1, f3} hay cả 3?
y’3a2x1
y’2a1x2
y’1a1x1
Y’AX
Y
Các hệ CSDLNC - Cao học
5
(c) Đồng Thị Bích Thủy
1. Vài ñịnh nghĩa (tt)
C = <Q,F>
F => bao ñóng (F): F
+
=>Phủ (F) => Phủ tối
thiểu
: PTT(F)
Dùng luật pth (hệ tiên ñề Armstrong) ñể
suy ra bao ñóng, các phủ, các phủ tối
thiểu.
Trong Q: chỉ cần PTT(F) không bị vi phạm
(= ñược thỏa) => toàn bộ F
+
không bị vi
phạm.
Các hệ CSDLNC - Cao học
6
(c) Đồng Thị Bích Thủy
2. Cơ chế kiểm tra pth
Cho C = {<Q
i
,F
i
>}
i=1 n
,
Có 3 tình huống:
F
i
chứa toàn pth ñược in
cơ chế khóa
F
i
có một pth f ñược bao, mà không phải là
pth ñược in
cơ chế ép thỏa nội trong Q
i
Có một pth f ñược bao trong nhiều quan hệ:
bối cảnh của f =
i
Q
i
cơ chế ép thỏa “ngoài” trong
i
Q
i
Các hệ CSDLNC - Cao học
7
(c) Đồng Thị Bích Thủy
2. Cơ chế kiểm tra pth (tt)
Q
0
(ABCD)
F
0
= {
{{
{A →
→→
→ BCD ; B →
→→
→ CD}
}}
}
VD1:
C
1
= {
{{
{ < Q
1
(AD) ; F
1
= {
{{
{ A →
→→
→ D }
}}
} >;
< Q
2
(BC) ; F
2
= {
{{
{ B →
→→
→ C }
}}
} >;
< Q
3
(BD) ; F
3
= {
{{
{ B →
→→
→ D }
}}
}> }
}}
}
Ki
ể
m tra A
B: c
ầ
n thi
ế
t? c
ơ
ch
ế
nào?
Ki
ể
m tra A
C: c
ầ
n thi
ế
t? c
ơ
ch
ế
nào?
Ki
ể
m tra nh
ữ
ng pth khác: c
ơ
ch
ế
nào?
Các hệ CSDLNC - Cao học
8
(c) Đồng Thị Bích Thủy
2. Cơ chế kiểm tra pth (tt)
VD2:
C
2
= {
{{
{ < Q
1
(AB) ; F
1
= {
{{
{ A →
→→
→ B }
}}
} >;
< Q
2
(BCD) ; F
2
= {
{{
{B →
→→
→ CD}
}}
} > }
}}
}
Kiểm tra các pth của F
0
: cơ chế nào?
Các hệ CSDLNC - Cao học
9
(c) Đồng Thị Bích Thủy
3. Vấn ñề trùng lắp thông tin
VD3: F = {GVCT
N, P, G; M
GV
N, P, G
M; M
P }
Xét lược ñồ CSDL C
1
:
CoiThi (GVCT
, N, G, P)
LichThi (N, G, P
, M) ; khóa thứ 2 là (N, G, M)
GiangDay (M
, GV)
Các hệ CSDLNC - Cao học
10
(c) Đồng Thị Bích Thủy
3. Vấn ñề trùng lắp thông tin (tt)
csdlF2028-103
LtCF10110-122
csdlF1018-102
MPGN
csdlF1018-103
LtCF10110-122
csdlF1018-102
MPGN
chỉ dùng cơ chế
khóa ñể kiểm tra pth
(khóa (NGP) hoặc
(NGM) )
M
P bị vi phạm
có dùng thêm cơ
chế ép thỏa nội
M
P ñược thỏa,
nhưng có trùng lắp
thông tin trên (MP)
Cho 2 thể hiện của LICHTHI:
Các hệ CSDLNC - Cao học
11
(c) Đồng Thị Bích Thủy
3. Vấn ñề trùng lắp thông tin (tt)
Lời giải với khái niệm Dạng Chuẩn
DC1
DC2
DC3 pth
DCBC
DC4
pt ña trị
DC5 (DC Chiếu-Kết)
pt kết
Các hệ CSDLNC - Cao học
12
(c) Đồng Thị Bích Thủy
3. Vấn ñề trùng lắp thông tin (tt)
Nguyên tắc của DC:
tối ña trùng lắp thông tin
Pt dữ liệu ñược thỏa bởi một cơ chế hiệu
quả (ñối với pth: cơ chế khóa), hoặc hiển
nhiên ñược thỏa.
VD3b:
LichThi (N, G, P, M) ; khóa thứ 2 là (N, G, M)
LT1 (M, P); LT2 (N, G, M)
Các hệ CSDLNC - Cao học
13
(c) Đồng Thị Bích Thủy
3. Vấn ñề trùng lắp thông tin (tt)
VD3b:
LichThi (N, G, P, M) ; khóa th
ứ
2 là (N, G, M)
LT1 (M, P); LT2 (N, G, M)
DCBC
Cơ chế ép thỏa
ngoài ñ/v N, G, P
M
Không còn trùng lắp
thông tin
DC3
Cơ chế ép thỏa nội
ñ/v M
P
Có trùng lắp thông
tin trên (M, P)
LT1; LT2LichThi
Các hệ CSDLNC - Cao học
14
(c) Đồng Thị Bích Thủy
4. Tính chất bảo toàn thông tin
Khi thay thế một lược ñồ CSDL C
1
bằng
C
2
: cần bảo ñảm C
2
≡
≡≡
≡ C
1
.
VD4: C
1
gồm <CT, F> với
F = {GVCT
N, P, G ; M
GV ;
N, P, G
M ; M
P }
CT(GVCT, N, P, G, M, GV)
ñược thay bằng C
2
gồm hai quan hệ con:
Q1(GVCT
, N, G, M); Q2 (N, G, P, GV)
Các hệ CSDLNC - Cao học
15
(c) Đồng Thị Bích Thủy
4. Tính chất bảo toàn thông tin (tt)
gv3m3p1g2n1gc3
gv2m2p2g1n1gc2
gv1m1p1g1n1gc1
GVMPGNGVCT
m3g2n1gc3
m2g1n1gc2
m1g1n1gc1
MGNGVCT
gv3p1g2n1
gv2p2g1n1
gv1p1g1n1
GVPGN
C2
không tương ñương với C1
Một thể hiện của C1
Một thể hiện của C2
Các hệ CSDLNC - Cao học
16
(c) Đồng Thị Bích Thủy
4. Tính chất bảo toàn thông tin (tt)
Cách kiểm tra tính bttt:
Bằng chính ñịnh lý phân rã
Bằng kỹ thuật tableau
(xem li ni dung môn CSDL nâng cao bc
ñi hc)
Các hệ CSDLNC - Cao học
17
(c) Đồng Thị Bích Thủy
5. Vai trò của phụ thuộc dữ liệu
trong xác ñịnh lược ñồ CSDL
Đ/v pth:
Dùng tập F ñể xác ñịnh lược ñồ CSDL
PTT(F)
cách tiếp cận tổng hợp
Dùng F ñể “mịn hóa” lược ñồ CSDL
cách tiếp cận phân rã
Đ/v ptñt:
Dùng tập ptñt và pth ñể “mịn hóa” lược ñồ
CSDL
cách tiếp cận phân rã
(Xem thêm ni dung môn CSDL nâng cao bc ñi
hc)
Các hệ CSDLNC - Cao học
18
(c) Đồng Thị Bích Thủy
4. Vai trò của phụ thuộc dữ liệu
(tt)
dựa vào ñịnh lý phân
rã
Xñ lược ñồ CSDL ñạt
DCBC (nếu chỉ có pth)
/ DC4 (nếu có thêm
ptñt)
Có khi còn vài f phải
ñược ép thỏa ngoài
dựa vào PTT(F)
Xñ lược ñồ CSDL ñạt
DC3
Hầu hết f∈
∈∈
∈PTT(F)
ñược thỏa bởi cơ chế
khóa
Có khi còn vài f phải
ñược ép thỏa nội
PP phân rãPP Tổng hợp
Các hệ CSDLNC - Cao học
19
(c) Đồng Thị Bích Thủy
Câu hỏi?
