Luận văn Các thuật toán xử lý phụ thuộc hàm nới lỏng
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
NGUYỄN THỊ LINH
CÁC THUẬT TOÁN XỬ LÝ
PHỤ THUỘC HÀM NỚI LỎNG
Chuyên ngành: Khoa học Máy tính
Mã số: 8 48 01 01
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
NGƯỜI HƯỚNG DẪN KHOA HỌC
PGS.TSKH NGUYỄN XUÂN HUY
Thái Nguyên năm 2020
1
LỜI CAM ĐOAN
Tên tôi là: Nguyễn Thị Linh
Sinh ngày: 18/08/1989
Học viên lớp Cao học CK17A - Trường Đại học Công nghệ Thông tin và
Truyền thông - Thái Nguyên.
Tôi xin cam đoan toàn bộ nội dung liên quan tới đề tài được trình bày
trong luận văn là do bản thân tôi tìm hiểu và nghiên cứu, dưới sự hướng dẫn
khoa học của Thầy giáo PGS. TSKH. Nguyễn Xuân Huy.
Các nội dung trong luận văn đúng như nội dung trong đề cương và yêu
cầu của thầy giáo hướng dẫn. Tất cả tài liệu tham khảo đều có nguồn gốc, xuất
xứ rõ ràng. Nếu sai tôi hoàn toàn chịu trách nhiệm trước hội đồng khoa học và
trước pháp luật.
Tác giả luận văn
Nguyễn Thị Linh
2
LỜI CẢM ƠN
Lời đầu tiên, em xin bày tỏ lòng cảm ơn và kính trọng sâu sắc đối với Thầy
PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em trong suốt quá
trình làm luận văn này. Thầy giúp em hiểu và tiếp cận những vấn đề khoa học
rất lý thú, hướng em vào nghiên cứu các lĩnh vực rất thiết thực và bổ ích. Em
đã học hỏi được rất nhiều ở Thầy cũng như phong cách làm việc, phương pháp
tiếp cận tri thức. Em luôn được Thầy chỉ bảo tận tình trong suốt quá trình làm
luận văn.
Em cũng xin thể hiện sự kính trọng và biết ơn đến Quý Thầy Cô trong
Trường ĐH CNTT&TT, trang bị cho chúng em đầy đủ về cơ sở vật chất cũng
như tri thức để em hoàn thành khóa học.
Cuối cùng em xin cảm ơn các bạn học viên trong lớp Cao học, những
người luôn bên cạnh và cung cấp những thông tin quý báu trong suốt quá trình
học tập, nghiên cứu để hoàn thành luận văn này.
Thái Nguyên, ngày 26 tháng 8 năm 2020
Học viên
Nguyễn Thị Linh
3
MỤC LỤC
LỜI CAM ĐOAN ..................................................................................................... 2
LỜI CẢM ƠN ........................................................................................................... 3
DANH MỤC CÁC BẢNG........................................................................................ 9
DANH MỤC CÁC HÌNH ...................................................................................... 10
LỜI NÓI ĐẦU......................................................................................................... 11
1.1. Giới thiệu chung................................................................................... 16
1.3. Bao đóng của tập thuộc tính.................................................................. 17
1.4. Các kí hiệu và một số quy ước .............................................................. 18
1.6. Các phép toán quan hệ .......................................................................... 21
1.6.7. Phép chia (Division)...................................................................... 22
1.6.9. Một số hàm tiện ích....................................................................... 23
4
1.6.10. Một số ví dụ ................................................................................ 23
1.7. Phụ thuộc hàm........................................................................................ 25
1.7.3. Phủ................................................................................................. 28
1.8. Chuẩn hóa............................................................................................... 30
2.1. Thuật toán tập hợp................................................................................. 32
2.4. Thuật toán tìm phủ tối tiểu ................................................................... 36
bảng................................................................................................................. 37
3.1. Lớp tập hợp Set ...................................................................................... 41
3.1.1. Cấu tử Set...................................................................................... 42
3.1.2. Hàm Reset..................................................................................... 42
3.1.6. Toán tử gán tập hợp ...................................................................... 43
5
3.1.11. Toán tử so sánh ........................................................................... 44
3.2. Lớp phụ thuộc hàm FD.......................................................................... 45
3.3. Lớp lược đồ quan hệ RSC .................................................................... 47
6
3.4. Minh họa chương trình.......................................................................... 54
KẾT LUẬN ............................................................................................................. 63
TÀI LIỆU THAM KHẢO...................................................................................... 63
7
DANH MỤC CÁC HÌNH
Hình 3.1. Thử nghiệp với lớp Set ............................................................................ 56
Hình 3.2. Thử nghiệm với lớp FD ........................................................................... 57
Hình 3.3. Thử nghiệm với lớp RSC......................................................................... 58
10
LỜI NÓI ĐẦU
1. Đặt vấn đề
Năm 1970 Codd đề xuất khái niệm phụ thuôc hàm như một cơ chế quản
lý ngữ nghĩa dữ liệu trong cơ sở dữ liệu quan hệ [8], [9], [10].
Cho tập thuộc tính U. Một phụ thuộc hàm (PTH) trên U là công thức dạng
f: X Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của PTH f.
Cho quan hệ R(U) và một PTH f: X Y trên U. Ta nói quan hệ R thoả
PTH f, hoặc PTH f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R
giống nhau trên X thì chúng cũng giống nhau trên Y,
R(XY) (u, vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: X Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ
thuộc hàm vào tập thuộc tính X, hoặc tập thuộc tính X xác định hàm tập thuộc
tính Y.
Nếu Y không phụ thuộc hàm vào X thì ta viết X ! Y hoặc (XY).
Cho tập PTH F trên tập thuộc tính U. Ta nói quan hệ R(U) thoả tập PTH
F, và viết R(F), nếu R thoả mọi PTH trong F: R(F) ( f F): R(f)
Cho trước tập thuộc tính U, ký hiệu SAT(F) là tập toàn thể các quan hệ
trên U thoả tập PTH F.
Cho tập các quan hệ trên U, ký hiệu FD() là tập các PTH trên U đúng
trong mọi quan hệ của .
Cho tập PTH F trên tập thuộc tính U. Bao đóng của F, ký hiệu F + là tập
nhỏ nhất các PTH trên U chứa F và thoả các tính chất F1 - F3 của hệ tiên đề
Armstrong Ao sau đây [1], [2], [3]:
X, Y, Z U:
F1. Tính phản xạ: Nếu X Y thì X Y F +
F2. Tính gia tăng: Nếu XY F + thì XZYZ F +
F3. Tính bắc cầu: Nếu X Y F + và Y Z F + thì X Z F +
11
Sau đó hàng loạt công trình nghiên cứu đề xuất các loại phụ thuộc dữ liệu
khác được xuất hiện trong lý thuyết cơ sở dữ liệu [4],[5],[10].
Các phụ thuộc dữ liệu đảm bảo cho dữ liệu trong các cơ sở dữ liệu phản
ánh sát với thế giới thực, phi mâu thuẫn có tính nhất quán và trợ giúp tối ưu hóa
trong tìm kiếm dữ liệu [6], [7].
Trong số các biến thể của phụ thuộc hàm thì các phụ thuộc nới lỏng
(Relaxed Functional Dependencies) được nghiên cứu và ứng dụng với tần xuất
cao vì các lý do sau đây. Thứ nhất, các điều kiện bổ sung cho phụ thuộc hàm
để tạo ra các phụ thuộc nới lỏng thường khá gần với các yêu cầu trong đời
thường. Thứ hai, các phụ thuộc nới lỏng có thể được dùng làm cơ sở để đặc tả
các loại phụ thuộc khác [6], [7].
Cho tập thuộc tính U. Một phụ thuộc hàm nới lỏng trên U là công thức
dạng
f: (γ)X (δ)Y; X, Y U
trong đó ta gọi X là vế trái và Y là vế phải của phụ thuộc hàm nới lỏng f.
Cho quan hệ R(U) và một phụ thuộc hàm nới lỏng f: (γ)X (δ)Y trên U.
Ta nói quan hệ R thoả phụ thuộc hàm nới lỏng f, hoặc phụ thuộc hàm nới lỏng
f đúng trong quan hệ R và viết R(f), nếu hai bộ tuỳ ý trong R thỏa điều kiện γ
và giống nhau trên X thì chúng cũng giống nhau trên miền Y thỏa điều kiện δ,
R(XY) (γ)X, (δ)Y, (u,vR): (u.X = v.X) (u.Y = v.Y)
Nếu f: (γ)X (δ)Y là một phụ thuộc hàm nới lỏng trên U thì ta nói tập
thuộc tính Y phụ thuộc (hàm) nới lỏng vào tập thuộc tính X, hoặc tập thuộc tính
X xác định hàm nới lỏng tập thuộc tính Y.
Dưới đây xin trích dẫn một số thí dụ về các phụ thuộc hàm nới lỏng.
Trong bảng tuần hoàn các nguyên tố hóa học Mendelev, hai chất có cùng
số electron tại lớp ngoài cùng thì có cùng ái lực, tức là chúng có cùng xu thế
nhận thêm cho đủ số electron từ nguyên tố khác.
12
Phụ thuộc hàm nới lỏng f: (E = s)E (true)A
Ý nghĩa của phụ thuộc hàm nới lỏng trong trường hợp này là:
Chỉ xét trên các bộ thỏa điều kiện số điện tử tại lớp ngoài cùng bằng s, E
= s, thì hai nguyên tố có cùng lượng E sẽ có cùng ái lực.
Một dạng khác của phụ thuộc hàm nới lỏng là phân loại học sinh. Hai học
sinh có thể có điểm khác nhau nhưng vẫn được xếp vào cùng loại.
g: (a ĐTB b)ĐTB (true)Loại
Phụ thuộc hàm nới lỏng g cho biết hai học sinh có điểm trung bình (ĐTB)
trong cùng một đoạn [a; b] thì có cùng loại đánh giá.
13
Trong công trình của nhóm nghiên cứu Loredana Caruccio, Vincenzo
Deufemia, và Giuseppe Polese [7] đã phân loại hầu hết các phụ thuộc hàm nới
lỏng từ năm 1970 đến 2016.
Trong khuôn khổ khóa luận thạc sĩ này, học viên chọn đề tài: “Các thuật
toán xử lý phụ thuộc hàm nới lỏng”.
2. Đối tượng và phạm vi nghiên cứu
Luận văn tập trung khảo sát các đối tượng liên quan đến các lược đồ cơ
sở dữ liệu quan hệ sau đây:
- Lý thuyết phụ thuộc hàm và phụ thuộc hàm nới lỏng.
- Các thuật toán cơ bản xử lý các đối tượng trong phụ thuộc hàm nới
lỏng.
3. Hướng nghiên cứu của đề tài
- Nghiên cứu lý thuyết liên quan đến đề tài: Cơ sở dữ liệu quan hệ, phụ
thuộc hàm, phụ thuộc hàm nới lỏng, các thuật toán tính bao đóng,
khóa.
- Cài đặt các lớp đối tượng quản lý tập hợp, thuộc tính, phụ thuộc hàm,
phụ thuộc hàm nới lỏng, khóa.
- Thử nghiệm các lược đồ quan hệ trang bị phụ thuộc hàm nới lỏng.
4. Cấu trúc của luận văn và những nội dung nghiên cứu chính
Cấu trúc của luận văn gồm:
- Phần mở đầu.
- Chương 1, 2 và 3.
- Phần kết luận và đề nghị.
- Tài liệu tham khảo.
Nội dung chính của luận văn:
- Chương 1 giới thiệu các kiến thức cơ bản về CSDL, các định nghĩa
về quan hệ, thuộc tính, bộ. Phụ thuộc hàm cũng như thuật toán tính
bao đóng của các tập thuộc tính, tìm khóa của LĐQH, các chuẩn 1NF,
2NF, 3NF, BCNF, chuẩn hóa 3NF và bảo toàn thuốc tính PTH, PTH
nới lỏng.
14
- Chương 2 trình bày một số thuật toán về: quản lý tập hợp, quản lý
tập thuộc tính, quản lý tập phụ thuộc hàm nới lỏng, tính bao đóng,
khóa.
- Chương 3 là cài đặt chương trình mô phỏng “Thuật toán xử lý phụ
thuộc hàm nới lỏng” và ứng dụng.
5. Phương pháp nghiên cứu
Trong luận văn học viên sử dụng các phương pháp nghiên cứu chính sau:
- Nghiên cứu lý thuyết: Tổng hợp tài liệu, hệ thống lại các kiến thức,
tìm hiểu các khái niệm, thuật toán sử dụng trong đề tài.
- Lập trình thử nghiệm.
- Lấy ý kiến chuyên gia.
6. Ý nghĩa khoa học của đề tài
Việc nghiên cứu đề tài có thể đóng góp thêm một vài chức năng quản lý
ngữ nghĩa dữ liệu thông qua các phụ thuộc hàm nới lỏng. Loại phụ thuộc hàm
này cho phép xử lý dữ liệu mịn hơn và linh hoạt hơn.
Luận văn thiết kế và cài đặt một hệ thống với các chức năng nhập xuất,
lưu trữ, tính bao đóng và khóa của các lược đồ quan hệ có trang bị các phụ
thuộc hàm nới lỏng. Hệ thống có thể được sử dụng để khảo sát và kiểm định
một số tính chất của các lược đồ quan hệ với phụ thuộc hàm nới lỏng.
15
CÁC KIẾN THỨC CƠ SỞ
Chương này trình bày một số khái niệm cơ bản về tập hợp, về phụ thuộc
hàm và về lược đồ quan hệ. Nội dung chương sẽ là cơ sở để nghiên cứu những
vấn đề trong các chương sau.
1.1. Giới thiệu chung
Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được tập trung nghiên
cứu và phát triển của công nghệ thông tin. Trong quản lý các cơ sở dữ liệu
(CSDL), phụ thuộc dữ liệu được hiểu là những mệnh đề mô tả các ràng buộc
mà dữ liệu phải đáp ứng trong thực tế. Nhờ có những mô tả phụ thuộc này mà
hệ quản trị cơ sở dữ liệu có thể quản lý tốt được chất lượng dữ liệu. Lý thuyết
về các phụ thuộc dữ liệu đóng vai trò quan trọng trong việc mô tả thế giới
thực, phản ánh ngữ nghĩa dữ liệu trong cơ sở dữ liệu. Phụ thuộc dữ liệu được
Codd, tác giả của mô hình dữ liệu quan hệ đặt nền móng từ những năm 70 với
khái niệm phụ thuộc hàm. Một cách giải thích rất trực quan cho bài toán quản
lý được tổ chức theo hàng và cột, trong đó cột được biểu thị thuộc tính thông
tin cần quản lý của một đối tượng, thuộc tính này được gọi là tiêu đề của cột
và các giá trị trong cột đó có cùng một kiểu. Tập hợp tất cả các giá trị thuộc
tính trên một hàng (gọi là bộ) là dữ liệu về đối tượng đang quản lý.
1.2. Định nghĩa về quan hệ, bộ, thuộc tính
Cho tập hữu hạn U = {A , A ,...,A } khác rỗng (n> = 1). Các phần tử của U
1
2
n
được gọi là thuộc tính. Ứng với mỗi thuộc tính A U (i = 1,2,....,n) có một tập
i
chứa ít nhất 2 phần tử dom(A ) được gọi là miền giá trị của A . Gọi D là tập hợp
i
i
các dom(A ) (i = 1,2,....,n). Một quan hệ R với các thuộc tính U, kí hiệu R(U) là
i
16
một ánh xạ t: U D sao cho với mỗi A U ta có t(A ) dom(A ). Mỗi ánh xạ
i
i
i
được gọi là một bộ của quan hệ R.
Mỗi quan hệ R có hình ảnh là một bảng, mỗi cột ứng với một thuộc tính,
mỗi dòng là một bộ.
Ta kí hiệu t(U) là một bộ trên tập thuộc tính.
Một quan hệ rỗng là một quan hệ không chứa bộ nào. Vì mỗi quan hệ là
một tập các bộ, nên trong quan hệ không có 2 bộ trùng lặp.
1.3. Bao đóng của tập thuộc tính
Cho tập PTH F trên tập thuộc tính U và một tập con các thuộc tính X trong
U. Bao đóng của tập thuộc tính X, ký hiệu X+ là tập thuộc tính
X+ = {A U | X A F+}
Suy dẫn theo quan hệ
Cho tập PTH F trên tập thuộc tính U và f là một PTH trên U. Ta nói PTH
f được suy dẫn theo quan hệ từ tập PTH F và viết F ├ f, nếu mọi quan hệ R(U)
thoả F thì R cũng thoả f: F ├ f SAT(F) SAT(f).
Cho tập thuộc tính U và tập PTH F trên U, ta định nghĩa F* là tập toàn bộ
các PTH f được suy dẫn theo quan hệ từ tập PTH F
F* = {f: X Y | X, Y U, F ├ f}
Ta viết F !├ f hoặc F ├ f để biểu thị tập PTH F không dẫn theo quan
hệ ra được PTH f .
Định lý (Tính đủ và chặt của hệ tiên đề Armstrong)
F+ = F*
Nói cách khác, suy dẫn theo quan hệ và suy dẫn theo tiên đề là một, tức là F ╞
f F ├ f.
17
Quy ước giản lược: Ta thường viết X Y thay vì viết X Y F+ hoặc F ╞ X
Y.
1.4. Các kí hiệu và một số quy ước
Theo truyền thống của lý thuyết cơ sở dữ liệu chúng ta chấp nhận các
quy định sau đây:
Các thuộc tính được kí hiệu bằng các chữ LATINH HOA đầu bảng chữ A,
B, C, D...
Tập thuộc tính được kí hiệu bằng các chữ LATINH HOA cuối bảng chữ
X, Y, Z,...
Các phần tử trong một tập thường được liệt kê như một xâu kí tự, không
có các ký hiệu biểu diễn tập, chẳng hạn ta viết X = ABC thay vì viết X = {A, B,
C}. XY biểu diễn hợp của hai tập X và Y, X Y. Phép trừ hai tập X và Y được
kí hiệu là X\Y, hoặc X-Y.
Một phân hoạch của tập M (thành các tập con rời nhau và có hợp là M),
X , X
X được kí hiệu là M = X | X | |X với ý nghĩa M = X X
...
1
2,..., m
1
2, ... m
1
2
X và X X = Ø , 1 ≤ i, j ≤ m, i j.
m
i
j
Các bộ được biểu diễn bằng các chữ Latin thường có thể kèm chỉ số, thí
dụ t, u, v, i ...
1
Với mỗi bộ t trong quan hệ R(U) và mỗi tập con các thuộc tính X U ta
kí hiệu t[X] hoặc t.X là hạn chế của bộ (ánh xạ) t trên tập thuộc tính X. Ta chấp
nhận quy ước tự nhiên là miền giá trị của mọi thuộc tính chứa ít nhất hai phần
tử.
Trong trường hợp một miền trị của thuộc tính chỉ chứa một giá trị duy
nhất thì ta có thể loại bỏ cột tương ứng của thuộc tính đó trong quan hệ.
Ta chấp nhận quy ước sau đây: Mọi cặp bộ t và v trong mọi quan hệ giống
nhau trên miền rỗng các thuộc tính
18
t.Ø = v.Ø
Hàm Artr(R) cho tập thuộc tính của quan hệ R
Hàm Card(R) cho lực lượng (số bội) của quan hệ R
Trong trường hợp tập thuộc tính U đã cho trước ta có thể viết đơn giản R
thay cho R(U).
Hai quan hệ R và S được gọi là tương thích nếu chúng có cùng một tập
thuộc tính, tức là nếu Artr(U) = Artr(S).
Với mỗi bộ u trong quan hệ R(U) và mỗi bộ v trong quan hệ S(V) ta ký
hiệu uv là phép dán bộ. uv cho ta bộ t trên tập thuộc tính UV thoả điều kiện
t.U = u và t.V = v.
Với mỗi bộ u trong quan hệ R(U) và với mỗi quan hệ S(V) ta ký hiệu uS
là phép dán bộ u với quan hệ S. uS cho ta quan hệ
P(UV) = {uv | v S}
Để thể hiện các phép toán quan hệ ta sẽ dùng các ký pháp tựa như ký pháp
của hệ ISBL (Information System Base Language).
1.5. Lược đồ quan hệ và khóa của lược đồ quan hệ
1.5.1. Định nghĩa lược đồ quan hệ
Lược đồ quan hệ (LĐQH) là một cặp p = (U, F), trong đó U là tập hữu
hạn các thuộc tính, F là tập các phụ thuộc hàm trên U.
Quy ước: Trong trường hợp không chỉ rõ tập PTH F, ta xem LĐQH chỉ là
một tập hữu hạn các thuộc tính U.
1.5.2. Khóa của lược đồ quan hệ
Cho LĐQH p = (U,F). Tập thuộc tính K U được gọi là khoá của LĐQH
p nếu
(i) K+ = U
19
(ii) A K: (K {A})+ U
Hai điều kiện trên tương đương với
(i') K U
(ii') A K: (K {A}) ! U
Nếu K thoả điều kiện (i) thì K được gọi là một siêu khoá.
Thuộc tính A U được gọi là thuộc tính khoá (nguyên thuỷ hoặc cơ sở)
nếu A có trong một khoá nào đấy. A được gọi là thuộc tính không khoá (phi
nguyên thuỷ hoặc thứ cấp) nếu A không có trong bất kỳ khoá nào. Cho LĐQH
(U,F), ta kí hiệu UK là tập các thuộc tính khóa và UO là tập các thuộc tính không
khóa.
Ví dụ: Cho U = {A,B,C,D,E} và F = {ABC, ACB, BCDE}, hãy
tìm một khóa của lược đồ quan hệ r xác định trên U và F.
Bước 1: K = U tức là K = ABCDE
Bước 2: Tính bao đóng của (K\A)+ nghĩa là tính (BCDE)+ = BCDE ta thấy
kết quả tính bao đóng không bằng U+ nên K = ABCDE
Bước 3: Tính bao đóng của (K\B)+ nghĩa là tính (ACDE)+ = ABCDE ta
thấy kết quả tính bao đóng bằng U+ nên loại B ra tập K ban đầu K = ACDE.
Bước 4: Tính bao đóng của (K\C)+ nghĩa là tính (ADE)+ = ADE ta thấy
kết quả tính bao đóng không bằng U+ nên không bỏ C ra tập K ta có K = ACDE.
Bước 5: Tính bao đóng của (K\D)+ nghĩa là tính (ACE)+ = ACEBD ta thấy
kết quả tính bao đóng bằng U+ nên bỏ D ra tập K ta có K = ACE.
Bước 6: Tính bao đóng của (K\E)+ nghĩa là tính (AC)+ = ACBDE ta thấy
kết quả tính bao đóng bằng U+ nên bỏ E ra tập K ta có K = AC.
Kết quả: Khóa là K = AC.
20
Tải về để xem bản đầy đủ
64 trang
17080
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận văn Các thuật toán xử lý phụ thuộc hàm nới lỏng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_cac_thuat_toan_xu_ly_phu_thuoc_ham_noi_long.pdf
