ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CNTT & TRUYỀN THÔNG NGUYỄN LÊ HOÀN
LOẠI BỎ CÁC MẪU TIN NHÂN BẢN THỪA
TRONG CƠ SỞ DỮ LIỆU QUAN HỆ
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
ii
MỤC LỤC
Trang
MỞ ĐẦU 1
CHƯƠNG 1: CƠ SỞ LÍ THUYẾT 2
1.1. Tổng quan CSDL quan hệ 2
1.1.1. Định nghĩa quan hệ 2
1.1.2. Phụ thuộc hàm 2
1.1.3. Khóa 4
1.1.3. Các loại chuẩn 7
1.2. Hệ chuyên gia 14
1.2.1. Thể hiện dấu hiệu không chắc chắn 16
1.2.2. Thể hiện các luật không chắc chắn 19
1.2.3. Lan truyền chắc chắn đối với các luật có nhiều giả thiết 22
CHƯƠNG 2: LOẠI BỎ CÁC MẪU TIN NHÂN BẢN THỪA 25
2.1. Các dạng lệnh SQL 25
2.2. Các loại mảnh và cách phân mảnh quan hệ 32
2.2.1. Các lý do phân mảnh 40
Kí hiệu không thuộc
Kí hiệu thuộc
+ Phép cộng
- Phép trừ
X Tích đề các
Phép nối
Phép chiếu
Tê ta
> Phép so sánh lớn hơn
< Phép so sánh nhỏ hơn
Phép so sánh lớn hơn hoăc bằng
Phép so sánh nhỏ hơn hoăc bằng
\ Phép chia
* Phép nhân
v
AND Phép và
OR Phép hoặc
LCS Local Conception Schema (lược đồ khái niệm địa phương)
LTM Long Term Memory (bộ nhớ vĩnh cửu)
MB Measure of Belief (Độ chắn chắn)
MD Measure of Disbelief (Độ không chắn chắn)
SQL Structured Query Langguage (Ngôn ngữ truy vấn có cấu trúc)
STM Short Term Memory (bộ nhớ tạm thời)
vii
DANH MỤC CÁC BẢNG BIỂU
Trang
Bảng 1.1. HS 3
Bảng 1.2. HangHoa 5
Bảng 1.3. Khoa 6
Bảng 1.4.Luong 7
Bảng 1.5. TienLuong 8
Bảng 1.6.XeMay 8
Bảng 1.7. XeMay1 9
Bảng 1.8. XeMay2 9
Bảng 1.9. SV 10
Bảng 1.10. Xe 12
Bảng 1.11. R1 13
Bảng 1.12. R2 13
Bảng 1.13. R3 13
Bảng 1.14. Miêu tả các giá trị CF 23
Bảng 2.1. So sánh các lựa chọn nhân bản 39
Bảng 2.2. Truong 42
Bảng 2.3. Hocsinh 42
Bảng 2.4. Monhoc 42
Bảng 2.5.Diemthi 43
Bảng 3.15. Mảnh ngang 2 60
Bảng 3.16. Mảnh ngang 3 61
Bảng 3.17. Mảnh ngang 4 61
Bảng 3.18. Mảnh ngang 5 61
Bảng 3.19. Mảnh ngang 6 61
Bảng 3.20. Mảnh ngang 7 62
Bảng 3.21. Mảnh HV1 62
Bảng 3.22. Mảnh HV2 62
Bảng 3.23. Mảnh HV3 63
Bảng 3.24. Mảnh HV4 63
Bảng 3.25. Mảnh HV5 63
Bảng 3.26. Mảnh HV6 63
ix
Bảng 3.27. Mảnh HV7 63
Bảng 3.28. Mảnh R1 64
Bảng 3.30. Mảnh ngang tR21 65
Bảng 3.31. Mảnh ngang tR22 65
Bảng 3.32. Mảnh ngang tR23 65
Bảng 3.33. Mảnh ngang tR24 65
Bảng 3.34. Mảnh ngang R2a 65
Bảng 3.35. Mảnh HV8 66
Bảng 3.37. Mảnh R22 66
Bảng 3.38. Mảnh ngang tR22 66
x
DANH MỤC CÁC HÌNH
Trang
Hình 1.1. Giải quyết vấn đề của chuyên gia 17
,…} là tập các thuộc tính không khoá.
Tập siêu khoá được dùng để xác định tính duy nhất của các bộ giá trị t(K,A).
Một số bộ giá trị t(A) có thể trùng nhau trên toàn bộ hoặc ở một số thuộc
tính không khoá nhưng vẫn không vi phạm tính duy nhất của bộ giá trị cũng
như tính chất phụ thuộc hàm bởi chúng luôn luôn có bộ giá trị khoá t(K) khác
nhau. Nghĩa là có thể do một sai sót nào đó mà hai bộ t
s
(K), t
x
(K) khác nhau
và t
s
(A), t
x
(A) có thể khác hoặc giống nhau nhưng t
s
(K, A), t
x
(K, A) trong thực
tế chỉ mô tả một đối tượng, khi đó ta nói t
s
(K, A), t
x
(K, A) là nhân bản thừa
của nhau. Điều này đặc biệt hay xảy ra trong CSDL phân tán khi vô hình nhân
bản và vô hình phân tán. Điều gì xẩy ra, nếu một người được nhận "danh hiệu
khen thưởng tại một số nơi", một nhân viên của tổng công ty có thể nhận
"lương tại một số công ty con" ở các nút mạng khi vô hình nhân bản và phân
tán.…Vì vậy cần phải loại bỏ tất cả các bộ được nhân bản thừa trong CSDL
quan hệ. Để làm việc này chúng ta có thể dựa vào phương pháp heuristics.
(i = 1, 2, …, n). Khi đó r gồm
một tập các bộ {h
1
, h
2
, …, h
m
} được gọi là một quan hệ trên R, với h
j
(j
= 1, 2,
…, m) là một hàm:
:
i
j A
i
h R D
A R
sao cho: h
j
(A
i
)
Ai
D
j
) thì chiếu Y(t
i
) = chiếu Y(t
j
)
Ví dụ:
Xét quan hệ HS(Sbd, HoTen, DiaChi, Truong, KhuVuc) cho bởi bảng 1.1:
Sbd HoTen DiaChi Truong KhuVuc
CD101 Lê Thị Bình Định Hóa TN
Định Hóa 1
ED123 Vũ Ngọc Nam TP.TN Chuyên 3
QE112 Trần Thu Lệ Đồng Hỷ TN Đồng Hỷ 2
Bảng 1.1. HS
Trong quan hệ HS dựa vào định nghĩa phụ thuộc hàm của quan hệ ta có:
{Truong}
{KhuVuc}
* Hệ tiên đề Armstrong:
Giả sử R = {A
1
, A
2
, …, A
n
} là tập các thuộc tính.
X, Y, Z
Z
* Sơ đồ quan hệ:
Giả sử R = (A
1
, A
2
, …, A
n
) là tập các thuộc tính. F là tập các phụ thuộc
hàm trên R. Khi đó sơ đồ quan hệ s là cặp R, F như trên và ký hiệu
là
s = < R, F >.
4
* Bao đóng của sơ đồ quan hệ:
Giả sử một sơ đồ quan hệ s = (R, F), trong đó R là tập các thuộc tính, F là
tập các phụ thuộc hàm trên R. Kí hiệu F
+
là tập tất cả các phụ thuộc hàm được
dẫn xuất từ F bằng việc áp dụng hệ tiên đề Armstrong:
Đặt A
+
= {a: A
{a}
F
+
}. Khi đó A
tại một thuộc tính A
K sao cho t
i
(A)
t
j
(A) (
i j
). Nói cách khác, không
tồn tại hai bộ mà có giá trị bằng nhau trên mọi thuộc tính của K, điều kiện này có
thể viết t
i
(K)
t
j
(K). Do vậy mỗi giá trị của K là xác định duy nhất.
Trong một lược đồ quan hệ có thể có rất nhiều khóa. Việc tìm tất cả các
khóa của lược đồ quan hệ là rất khó khăn. Để có thể định nghĩa khóa ta lưu ý,
nếu K
’
là khóa của quan hệ r(A
1
, …, A
n
) thì K
R sao cho bất kì hai bộ khác nhau t
i
, t
j
r luôn thỏa mãn t
i
(K)
t
j
(K) bất kì
tập con thực sự K
’
K nào, K’ đều không có tính chất đó. Thì K được định
nghĩa là khóa.
Ví dụ 1:
Cho quan hệ hàng hóa HangHoa(MSMH, TenHang, SoLuong) cho dữ
liệu bởi bảng 1.2 như sau:
5
MSHH TenHang SoLuong
1011 Bàn phím 505
1012 Chuột quang 500
1013 Màn hình 600
i
j
m}, ở đây E
ij
= {a
R: h
i
(a) = h
j
(a)}
Vào: r ={h
1
,…, h
m
} là một quan hệ trên tập thuộc tính R ={A
1
, …,A
n
}
Ra: K là một khóa tối tiểu của r
+ Bước 1: Tính E
r
= {A
1
, …, A
n
} trong đó E
} nếu không tồn tại A
M
r
sao cho K
i-1
– {A
i
}
A hoặc
K
i
= K
i-1
trong trường hợp ngược lại
+ Bước 4: Đặt K = K
n
, khi đó K là khóa tối tiểu.
Nếu ta thay đổi thứ tự các thuộc tính của R, thì bằng thuật toán này
chúng ta tìm được một khóa tối tiểu khác.
6
Ví dụ 2: Cho quan hệ Khoa = {A, B, C, D, E} cùng dữ liệu ở bảng 1.3.
A B C D E
1 1 0 3 0
0 1 0 1 1
0 0 1 1 0
2 0 2 0 1
– {A} = {A, B, C, D, E} - {A} = {B, C, D, E}
K
2
= K
1
– {B} = {B, C, D, E} - {B} = {C, D, E}
K
3
= K
2
– {C} = {D, E}
K
4
= K
3
K
5
= K
4
Do vậy theo thuật toán tập thuộc tính {D, E} là khóa tối tiểu của r
Nếu ta thay đổi thứ tự R= {E, D, C, B, A} thì ta có:
K
1
= {D, C, B, A}
K
2
= {C, B, A}
K
Dạng chuẩn thứ nhất (Fisrt Normal Form, viết tắt 1NF)
Dạng chuẩn thứ hai (Second Normal Form, viết tắt 2NF)
Dạng chuẩn thứ ba (Third Normal Form, viết tắt 3NF)
Dạng chuẩn BCNF (Boye Codd Normal Form)
Dạng chuẩn thứ bốn (Fourth Normal Form, viết tắt 4NF)
Dạng chuẩn thứ năm (Fifth Normal Form, viết tắt 5NF)
* Dạng chưa chuẩn:
Ví dụ 1:
Cho quan hệ Luong có cấu trúc như bảng 1.4:
Tien
HoTen
Luong Thuong
Bảng 1.4.Luong 8
* Các dạng chuẩn:
Cho sơ đồ quan hệ s = (R, F), trong đó R là tập các thuộc tính, F là tập
các phụ thuộc hàm trên R, K là một khóa của s.
+ Định nghĩa 1.(Dạng chuẩn 1 – 1NF)
Sơ đồ quan hệ s = (R, F) được gọi là ở dạng chuẩn 1NF nếu toàn bộ các
miền giá trị có mặt trong R đều chỉ chứa các giá trị nguyên tố (giá trị nguyên
tố là giá trị không thể phân chia nhỏ được nữa).
Ví dụ 2:
Quan hệ TienLuong có cấu trúc cho bởi bảng 1.5:
HoTen Luong Thuong Tien
Bảng 1.5. TienLuong
+ Định nghĩa 2.(Dạng chuẩn 2 – 2NF)
Sơ đồ quan hệ s = (R, F) được gọi là ở dạng chuẩn 2NF nếu mọi thuộc
R và a là thuộc tinh thứ cấp. Có nghĩa là cấm thuộc tính thứ cấp phụ
thuộc vào mọi tập có bao đóng khác R.
Ví dụ 4:
Cho quan hệ XeMay1(MaXe, NamSx) cho bởi bảng dữ liệu 1.7:
MaXe NamSx
S1 2010
S2 2011
S3 2012
Bảng 1.7. XeMay1
+ Định nghĩa 4.(Dạng chuẩn Boye- Codd – BCNF)
Sơ đồ quan hệ s = (R, F) được gọi là ở dạng chuẩn BCNF nếu trong s
không tồn tại phụ thuộc hàm dạng A
{a} với {a}
A và A
+
R. Có nghĩa
là cấm tất cả các thuộc tính không phụ thuộc vào tập các bao đóng khác R.
Ví dụ 5: Cho quan hệ XeMay2(MaXe,Ten,NamSx,Mau) cho bởi bảng 1.8:
MaXe Ten NamSx Mau
năm 1977, Delobel năm 1978 và Zanodo năm 1981.
+ Định nghĩa 5. Phụ thuộc đa trị (Multivalued dependancy)
Giả sử R(A
1
, A
2
, …, A
n
) là một lược đồ quan hệ X,Y
{A
i
}, ta nói rằng
X ->>Y (X xác đa trị Y hay Y phụ thuộc đa trị vào X) nếu cho những giá trị
11
X, có một tập giá trị Y liên quan và tập này độc lập với các thuộc tính
Z = R - X - Y. Điều này tức là:
(X ->>Y)
{(xyz),(x’y’z’)
R
(xy’z),(x’yz’)
R } x
X,y
12
Ví dụ 7:
Cho quan hệ Xe(Ten, Mau, Mac) và dữ liệu cho ở bảng 1.7 về người
dùng xe có màu và mác xe. Bảng 1.7 dữ liệu cho thấy quan hệ này vẫn dư
thừa dữ liệu và vấn đề cần phải nghiên cứu và phân rã chúng như bảng 1.10:
Ten Mau Mac
Nam Xanh YAMAHA
Nam Xanh HONDA
Nam Đỏ HONDA
Mai Xanh HONDA
Bảng 1.10. Xe
Quan hệ Xe thuộc dạng chuẩn 4NF vì bài toán không xác định phụ thuộc
đa trị nào. Kiểm tra các phụ thuộc đa trị ta thấy:
+ Không thể Ten
Mau vì không có bộ (Nam, Đỏ, YAMAHA)
+ Không thể Mau
Mac vì không có bộ (Mai, Đỏ, YAMAHA)
+ Không thể Mac
Ten vì không có bộ (Mai, Đỏ, HONDA)
Để giải quyết vấn đề này người ta phải phân rã thành nhiều quan hệ. Tài
liệu này được Aho hay Nicolas đề cập năm 1979.
Quan hệ Xe nói trên có thể phân rã thành các quan hệ R
1
, …, A
n
) là lược đồ quan hệ và X
1
, X
2
, …, X
m
là các tập
con của {A
i
}. Ta nói rằng có phụ thuộc kết nối
*
{ X
1
, X
2
, …, X
n
} nếu R là
kết nối của chiếu của nó trên X
1
, X
2
, …, X
m
, tức là:
R = chiếu
x1
(R) chiếu
+ Quan hệ nhiều – nhiều (many - to - many): mỗi thể hiện của thực thể A
được liên kết với không, một hay nhiều thể hiện của B và ngược lại, mỗi thể
hiện của thực thể B được liên kết với không, một hay nhiều thể hiện của A.
1.2. Hệ chuyên gia
+ Máy thông minh
Khi tri thức con người ngày càng rộng và cao, thì họ đòi hỏi thiết bị càng có
khả năng xử lý các vấn đề ngày càng phức tạp. Thậm chí yêu cầu máy xử lý các
tình huống càng giống con người. Máy phải “thu thập các sự kiện, suy nghĩ, dẫn
luận và đưa ra các kết luận”. Nhiều tổ chức đã dùng các thiết bị - cùng với các
phần mềm hỗ trợ để ra các quyết định hoặc thu thập tri thức của các chuyên gia
các lĩnh vực mà họ cần có các máy móc đó gọi là máy thông minh.
Định nghĩa 1.2-1. Chuyên gia về lĩnh vực nào đó là một người có kiến
thức sâu sắc về lĩnh vực đó và có thể dùng kiến thức đó để giải quyết các vấn
đề tương tự trong lĩnh vực đó.
Trải qua các kinh nghiệm, chuyên gia phát triển kĩ năng giúp họ giải
quyết vấn đề một cách có hiệu quả. Còn hệ chuyên gia là hệ thống bắt chước
được các kĩ năng của chuyên gia.
Định nghĩa 1.2-2. Hệ chuyên gia là một hệ thống dựa trên tri thức, cho
phép mô hình hóa các tri thức của chuyên gia có chất lượng, hay chuyên gia
Copyright: Tài liệu đại học ©