Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế
cơ sở dữ liệu thì và một trong những lớp phụ thuộc dữ liệu đầu tiên là lớp phụ
thuộc hàm. Ngày nay, việc mở rộng lớp phụ thuộc hàm này (mờ hoá) đang được
nghiên cứu và tiếp cận theo nhiều hướng khác nhau. Với mục tiêu nghiên cứu về
việc mở rộng này cũng như các khái niệm liên quan, trong đề tài nghiên cứu đã
tìm hiểu sâu về phụ thuộc dữ liệu và trình bày các nội dung liên quan đến lớp
phụ thuộc hàm mờ (fuzzy functional dependency), bao đóng tập thuộc tính và
thuật toán tìm bao đóng tập thuộc tính mờ (fuzzy transitive closure), khoá mờ
(fuzzy key) và thuật toán tìm khoá mờ, các dạng chuẩn mờ trong CSDL quan hệ.
Bên cạnh đó đề tài cũng đã nghiên cứu về việc mở rộng một trong những định lý
quan trọng nhất của việc nghiên cứu CSDL đó là định lý tương đương.
73 trang |
Chia sẻ: lvbuiluyen | Lượt xem: 2597 | Lượt tải: 4
Bạn đang xem trước 20 trang tài liệu Đề tài Nghiên cứu một số vấn đề về phụ thuộc dữ liệu và khai phá dữ liệu trong cơ sở dữ liệu quan hệ, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
TRƯỜNG ………………….
KHOA……………………….
----------
Báo cáo tốt nghiệp
Đề tài:
NGHIÊN CỨU MỘT SỐ VẤN ĐỀ VỀ PHỤ THUỘC DỮ LiỆU VÀ KHAI PHÁ DỮ
LiỆU TRONG CƠ SỞ DỮ LiỆU QUAN HỆ
1
LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn “Nghiên cứu một số vấn đề về Phụ thuộc
dữ liệu và Khai phá dữ liệu trong Cơ sở dữ liệu quan hệ” là công trình
nghiên cứu riêng của tôi
Các kết quả nghiên cứu trong luận văn là trung thực. Nếu sai tôi xin hoàn
toàn chịu trách nhiệm.
Hà Nội, ngày 15 tháng 11 năm 2009
Học viên
Trần Thành Trung
2
LỜI CẢM ƠN
Tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS Vũ Ngọc Loãn, người
đã hướng dẫn, truyền đạt những kinh nghiệm quý báu và tận tình giúp đỡ tác
giả hoàn thành luận văn này.
Tác giả xin cảm ơn sự quan tâm giúp đỡ của các thầy, cô trong khoa Công
nghệ thông tin đã tận tình giảng dạy cũng như giúp đỡ trong quá trình học tập và
nghiên cứu tại Khoa; đồng thời xin cảm ơn sự ủng hộ của các anh chị học viên
lớp K13HTTT đã động viên và giúp đỡ tác giả trong quá trình thực hiện đề tài
này.
Hà Nội, ngày 15 tháng 11 năm 2009
Học viên
Trần Thành Trung
3
TÓM TẮT
Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế
cơ sở dữ liệu thì và một trong những lớp phụ thuộc dữ liệu đầu tiên là lớp phụ
thuộc hàm. Ngày nay, việc mở rộng lớp phụ thuộc hàm này (mờ hoá) đang được
nghiên cứu và tiếp cận theo nhiều hướng khác nhau. Với mục tiêu nghiên cứu về
việc mở rộng này cũng như các khái niệm liên quan, trong đề tài nghiên cứu đã
tìm hiểu sâu về phụ thuộc dữ liệu và trình bày các nội dung liên quan đến lớp
phụ thuộc hàm mờ (fuzzy functional dependency), bao đóng tập thuộc tính và
thuật toán tìm bao đóng tập thuộc tính mờ (fuzzy transitive closure), khoá mờ
(fuzzy key) và thuật toán tìm khoá mờ, các dạng chuẩn mờ trong CSDL quan hệ.
Bên cạnh đó đề tài cũng đã nghiên cứu về việc mở rộng một trong những định lý
quan trọng nhất của việc nghiên cứu CSDL đó là định lý tương đương.
4
ABSTRACT
Data dependency plays a very important role in the process of designing
the database and one of the first data dependency class is the functional
dependency. Today, the expansion of the functional dependency (fuzzy
functional dependency) are being studied and approached in several ways. With
the objective of researching on the expansion of functional dependency and
related concepts, my thesis focus on researching about data dependency, fuzzy
functional dependency, fuzzy transitive closure and the algorithm for finding
fuzzy transitive closure of attributes , fuzzy key and the algorithm of finding
fuzzy keys in relational database. Besides, my thesis also focuses on researching
about the expansion of one of the most important theorems of rational database
– the equivalence theorem.
5
MỤC LỤC
LỜI CAM ĐOAN .............................................................................................. 1
LỜI CẢM ƠN .................................................................................................... 2
TÓM TẮT.......................................................................................................... 3
ABSTRACT....................................................................................................... 4
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT ...................................... 7
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ ............................................................. 8
DANH MỤC CÁC BẢNG BIỂU....................................................................... 9
MỞ ĐẦU ..........................................................................................................10
I. Mục tiêu nghiên cứu của đề tài ..............................................................10
II. Một số kết quả đạt được.........................................................................10
III. Bố cục của Luận văn .............................................................................11
CHƯƠNG 1. TỔNG QUAN .............................................................................12
1.1 Cơ sở dữ liệu ...........................................................................................12
1.1.1 Các khái niệm chung ........................................................................12
1.1.2 Định nghĩa ........................................................................................12
1.2 Phụ thuộc hàm.........................................................................................13
1.2.1 Định nghĩa ........................................................................................13
1.2.2 Tính chất của Phụ thuộc hàm (Hệ tiên đề Amstrong)........................14
1.2.3 Bao đóng tập thuộc tính ....................................................................15
1.2.4 Định lý tương đương.........................................................................18
1.3 Khoá........................................................................................................19
CHƯƠNG 2. LỚP PHỤ THUỘC HÀM MỜ TRONG CƠ SỞ DỮ LIỆU QUAN
HỆ.....................................................................................................................21
2.1 Dữ liệu mờ ..............................................................................................21
2.1.1 Tập rõ ...............................................................................................21
2.1.2 Tập mờ .............................................................................................21
2.1.3 Các phép toán cơ bản trên tập mờ .....................................................22
2.2 Phụ thuộc hàm mờ...................................................................................23
2.2.1 Định nghĩa ........................................................................................23
2.2.2 Tính chất...........................................................................................27
2.3 Xây dựng hệ tiên đề cho lớp Phụ thuộc hàm mờ ( Hệ tiên đề Amstrong
mở rộng)........................................................................................................29
CHƯƠNG 3. KHOÁ MỜ TRONG CƠ SỞ DỮ LIỆU QUAN HỆ ....................31
3.1 Khoá mờ.................................................................................................31
3.2 Bao đóng tập thuộc tính..........................................................................31
3.2.1. Tính chất của bao đóng tập thuộc tính (X + ) .....................................32
3.2.2 Bài toán thành viên ..........................................................................33
3.2.3 Thuật toán tìm bao đóng ...................................................................34
3.2.4 Tính đúng của thuật toán tìm bao đóng .............................................37
3.3 Định lý tương đương cho tập mờ ............................................................41
3.3.1 Định nghĩa ........................................................................................42
6
3.3.2 Định nghĩa ........................................................................................42
3.3.3 Định lý.............................................................................................42
3.4 Thuật toán tìm khoá mờ..........................................................................44
3.5 Các dạng chuẩn mờ ................................................................................45
3.5.1 Dạng chuẩn mờ F1NF.......................................................................45
3.5.2 Dạng chuẩn mờ F2NF.......................................................................46
3.5.2.1 Xác định dạng chuẩn mờ F2NF .....................................................47
3.5.2.2 Đưa quan hệ về dạng chuẩn mờ F2NF ...........................................48
3.5.3 Dạng chuẩn mờ F3NF.......................................................................50
3.5.4 Dạng chuẩn mờ Boyce Codd (FBCNF) ............................................51
KẾT LUẬN.......................................................................................................53
4.1 Ý nghĩa khoa học và thực tiễn của đề tài.................................................53
4.2 Kết luận và kiến nghị..............................................................................53
4.2.1 Kết luận ...........................................................................................53
4.2.2 Hướng phát triển đề tài ....................................................................54
TÀI LIỆU THAM KHẢO.................................................................................55
PHỤ LỤC .........................................................................................................57
7
DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT
TT Từ viết tắt Nghĩa đầy đủ
1 CNTT Công nghệ thông tin
2 CSDL Cơ sở dữ liệu
3 HTTT Hệ thống thông tin
4 HĐH Hệ điều hành
5 FTH Phụ thuộc hàm
6 FFD Fuzzy Functional Dependency Phụ thuộc hàm
mờ
7 FK Fuzzy Key – khoá mờ
8
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1: Hệ thống thông tin ............................................................................... 12
Hình 2: Hệ thống Cơ sở dữ liệu........................................................................ 13
Hình 3: Tập mờ và tập rõ.................................................................................. 22
Hình 4: Tập Input ............................................................................................. 71
Hình 5: Giao diện cài đặt thuật toán ................................................................. 71
Hình 6: Giao diện chạy thuật toán (Nhập tập thuộc tính cần tính bao đóng X + ) 72
Hình 7: Kết quả bao đóng của tập thuộc tính {A,B,C} ..................................... 72
9
DANH MỤC CÁC BẢNG BIỂU
Bảng 1: Bảng quan hệ Học sinh ....................................................................... 14
Bảng 2: Bảng các mở rộng của Phụ thuộc hàm................................................. 26
Bảng 3: Bảng các khả năng kết hợp giữa các tập thuộc tính ............................. 27
Bảng 4: Bảng các khả năng kết hợp giữa các tập thuộc tính ............................. 28
Bảng 5: Bảng quan hệ Nhân viên ..................................................................... 46
10
MỞ ĐẦU
I. Mục tiêu nghiên cứu của đề tài
Trong những năm gần đây, việc ứng dụng công nghệ thông tin trở nên
rộng rãi và vai trò của công nghệ thông tin ngày càng được khẳng định trong
nhiều lĩnh vực khác nhau như là: học tập, khoa học kỹ thuật, kinh doanh, quản
lý, ... dưới nhiều quy mô khác nhau. Cơ sở dữ liệu là một trong những lĩnh vực
nghiên cứu đóng vai trò nền tảng trong sự phát triển của công nghệ thông tin.
Tuy nhiên sự phát triển của cơ sở dữ liệu cũng chỉ mới bắt đầu trong thời gian
gần đây, đặc biệt từ khi E.F.Codd giới thiệu mô hình Cơ sở dữ liệu quan hệ
(Relational Database Model). Ngày nay có rất nhiều hệ quản trị Cơ sở dữ liệu
được xây dựng và phát triển dựa trên mô hình này như là : MS Access, SQL
Server, Oracle,…
Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế
cơ sở dữ liệu thì và một trong những lớp phụ thuộc dữ liệu đầu tiên là lớp phụ
thuộc hàm. Việc khai phá lớp phụ thuộc hàm có yếu tố quyết định trong việc
thiết kế Lược đồ khái niệm, bước đầu của quá trình xây dựng Cơ sở dữ liệu. Một
trong những đặc điểm quan trọng của phụ thuộc dữ liệu là việc nghiên cứu về
Khoá một khái niệm quan trọng trong việc xác định quan hệ phụ thuộc dữ liệu.
Việc phát triển nghiên cứu về dữ liệu mờ (fuzzy data) đòi hỏi việc nghiên cứu về
khái niệm Khoá mờ (fuzzy key) trong CSDL quan hệ. Đây cũng là sự mở rộng
hết sức tự nhiên của quá trình phát triển Cơ sở dữ liệu.
Với mong muốn được đóng góp một phần công sức nhỏ bé của mình vào
việc nghiên cứu về lớp phụ thuộc dữ liệu và khai phá dữ liệu trong CSDL quan
hệ mục tiêu nghiên cứu của đề tài này chủ yếu chú trọng vào việc nghiên cứu về
sự phụ thuộc dữ liệu, lớp phụ thuộc hàm mờ, bao đóng và thuật toán tìm bao
đóng, khoá mờ và thuật toán tìm khoá mờ.
II. Một số kết quả đạt được
Với mong muốn nghiên cứu sâu về lĩnh vực CSDL và các ứng dụng mở rộng
CSDL đề tài nghiên cứu của tác giả đã đạt được một số kết quả nhất định như
sau:
· Tổng hợp lại khái niệm trong CSDL quan hệ truyền thống
· Nghiên cứu về lớp Phụ thuộc hàm mờ:
o Hệ tiên đề cho lớp Phụ thuộc hàm mờ
o Khái niệm và thuật toán tìm bao đóng trong ngữ cảnh mờ
o Khoá mờ (fuzzy key) và thuật toán tìm khoá
o Định lý tương đương trong lớp phụ thuộc hàm mờ
· Tìm hiểu mở rộng khái niệm các dạng chuẩn thành dạng chuẩn mờ
( fuzzy normal form) F1NF, F2NF, F3NF, FBCNF.
11
III. Bố cục của Luận văn
Bố cục của luận văn được chia làm 3 chương chính theo trình tự nghiên
cứu từ CSDL quan hệ truyền thống đến việc mở rộng các khái niệm trong
CSDL này. Cụ thể luận văn bao gồm các vấn đề được trình bày theo thứ tự như
sau:
Chương 1: Tổng quan
Chương 1 trình bày lại những khái niệm cơ bản như là: dữ liệu, thông tin,
cơ sở dữ liệu, hệ quản trị cơ sở dữ liệu, khái niệm về Phụ thuộc hàm, Bao đóng
tập thuộc tính và Khóa. Bên cạnh đó trong chương này cũng trình bày về một
trong những định lý quan trọng nhất của Cơ sở dữ liệu quan hệ định lý tương
đương.
Chương 2: Lớp phụ thuộc hàm mờ trong Cơ sở dữ liệu quan hệ
Chương 2 trình bày các khái niệm cơ bản về tập mờ, các phép toán trên
tập mờ, phụ thuộc hàm mờ trong cơ sở dữ liệu quan hệ và một số mở rộng của
hệ tiên đề Amstrong trong ngữ cảnh mờ.
Chương 3: Khoá mờ trong Cơ sở dữ liệu quan hệ
Chương 3 trình bày các khái niệm cơ bản về khoá, khóa mờ, định nghĩa
về khoá mờ (fuzzy key), thuật toán tìm khóa mờ trong CSDL quan hệ; trình bày
khái niệm về bao đóng của tập thuộc tính đối với lớp phụ thuộc hàm mờ, thuật
toán tìm bao đóng; nêu và chứng minh định lý tương đương đối với hai kiểu suy
dẫn trong lớp phụ thuộc hàm mờ . Bên cạnh đó chương này cũng trình bày một
cách cơ bản về các dạng chuẩn mờ F1NF, F2NF, F3NF và FBCNF.
Trong quá trình thực hiện luận văn, mặc dù đã có nhiều cố gắng nhưng do
thời gian và kinh nghiệm nghiên cứu còn hạn chế nên những vấn đề trình bày
trong luận văn, những kết quả đạt được vẫn còn những điều cần phải khắc phục
và bổ sung thêm. Tác giả rất mong nhận được những lời góp ý của các thầy cũng
như các anh, các chị quan tâm đến chủ đề này.
12
CHƯƠNG 1. TỔNG QUAN
1.1 Cơ sở dữ liệu
1.1.1 Các khái niệm chung
Dữ liệu:Dữ liệu là các sự kiện, văn bản, đồ họa, hình ảnh và đoạn phim video có
ý nghĩa trong môi trường người dùng.
Thông tin:Thông tin (information) là dữ liệu được xử lý để tăng hiểu biết của
người dùng về dữ liệu này
Hệ thống thông tin: Hệ thống thông tin bao gồm bộ phận xử lý thông tin, các
thông tin vào ra (I/O information); bộ phận xử lý thông tin được đặt trong môi
trường của hệ thống [2].
Hình 1: Hệ thống thông tin
1.1.2 Định nghĩa
Cơ sở dữ liệu (CSDL) là một hệ thống thông tin có cấu trúc được lưu trữ
trên các thiết bị lưu trữ thông tin thư cấp (như băng từ, đĩa từ…) để có thể thoả
mãn yêu cầu khai thác thông tin đồng thời của nhiều người sử dụng hay nhiều
chương trình ứng dụng với nhiều mục đích khác nhau.
13
Hình 2: Hệ thống Cơ sở dữ liệu
Việc tổ chức dữ liệu tốt sẽ cho ta một hệ thống CSDL tốt, giúp cho người
quản trị hệ thống dễ dàng trong việc làm chủ hệ thống này. Một số hệ quản trị
CSDL phổ biến hiện nay như là: Oracle, SQL Server, DB2, My SQL, …
1.2 Phụ thuộc hàm
Khi xét đến mối quan hệ giữa dữ liệu trong CSDL quan hệ [2] một trong
những yếu tố quan trọng nhất được xét đến là sự phụ thuộc giữa các thuộc tính
này với thuộc tính khác. Từ đó có thể xây dựng những ràng buộc cũng như loại
bỏ đi những dư thừa dữ liệu trong một CSDL.
Phụ thuộc hàm [3] là những mối quan hệ giữa các thuộc tính trong CSDL
quan hệ. Khái niệm về phụ thuộc hàm có một vai trò rất quan trọng trong việc
thiết kế mô hình dữ liệu. Một trạng thái phụ thuộc hàm chỉ ra rằng giá trị của
một thuộc tính được quyết định một cách duy nhất bởi giá trị của thuộc tính
khác. Ở đây sẽ trình bày khái niệm một cách hình thức.
1.2.1 Định nghĩa
Định nghĩa : Cho tập thuộc tính U = {A n A ... 1 }, R là một quan hệ trên U. Gọi
X,Y là hai tập con của U. Khi đó: X→Y (đọc là X xác định hàm Y hay Y phụ
thuộc hàm vào X ) sao cho với hai bộ bất kỳ t1,t2 R Î mà t1[X] = t2[X] thì
t1[Y] = t2[Y]
14
Phụ thuộc hàm ký hiệu là FD.
Ví dụ: Cho quan hệ R = HS :
HS STT Ten Namsinh Diachi DT Email
1 Trung 1983 Việt Trì 0989313797 Trungtt
2 Kiên 1987 Phú Thọ 045596045 kientt
3 Nam 1984 Hà Nội 045769823 namlt
Bảng 1: Bảng quan hệ Học sinh
Theo bảng trên ta thấy mỗi một trong số các thuộc tính Namsinh, Diachi,
DT, Email đều phụ thuộc hàm (PTH) vào thuộc tính Ten. Mỗi giá trị của Ten
đều tồn tại đúng một giá trị tương ứng đối với từng thuộc tính còn lại. Khi đó có
thể viết: Ten → Nam sinh, Ten → Diachi, …
1.2.2 Tính chất của Phụ thuộc hàm (Hệ tiên đề Amstrong)
Lớp phụ thuộc dữ liệu đóng vai trò rất quan trọng trong quá trình thiết kế
cơ sở dữ liệu thì và một trong những lớp phụ thuộc dữ liệu đầu tiên là lớp phụ
thuộc hàm. Khi nghiên cứu về lớp phụ thuộc hàm trong CSDL quan hệ
Amstrong đã đưa ra một số tính chất như sau:
1.2.2.1 Hệ tiên đề
Gọi R là quan hệ trên tập thuộc tính U. Khi đó với các thuộc tính
, , ,W X Y Z U Í ta có hệ tiên đề Amstrong [3] như sau :
A1) Phản xạ : Nếu Y X Í thì X Y ®
A2) Tăng trưởng: Nếu W U Í và X Y ® thì W YW X ®
A3) Bắc cầu : Nếu , X Y Y Z ® ® thì X Z ®
Chứng minh:
A1) Giả sử 1 2 , t t R Î và 1 2 [X]=t [X] t cần chứng minh 1 2 [Y]=t [Y] t
Thật vậy do Y X Í suy ra 1 2 [Y]=t [Y] t (đúng ) □
A2) Giả sử 1 2 , t t R Î và 1 2 [XW]=t [XW] t cần chứng minh 1 2 [YW]=t [YW] t .
Phản chứng: Giả sử 1 2 [YW] t [YW] t ¹ . Do 1 2 [W]=t [W] t nên để có
1 2 [YW] t [YW] t ¹ thì 1 2 [Y] t [Y] t ¹ . Nhưng theo giả thiết ta có X→Y nghĩa là
1 2 [X]=t [X] t thì 1 2 [Y]=t [Y] t Þmâu thuẫn.Vậy 1 2 [YW]=t [YW] t □
15
A3) Theo giả thiết ta có , X Y Y Z ® ® là hai PTH trên quan hệ R
Giả sử 1 2 , t t R Î và 1 2 [X]=t [X] t cần chứng minh 1 2 [Z]=t [Z] t
Phản chứng : Giả sử 1 2 [Z] t [Z] t ¹ . Từ X Y ® suy ra 1 2 [X]=t [X] t thì
1 2 [Y]=t [Y] t . Mặt khác ta lại có PTH Y Z ® nghĩa là 1 2 [Y]=t [Y] t thì 1 2 [Z]=t [Z] t
nhưng theo giả thiết phản chứng ta có 1 2 [Z] t [Z] t ¹ (mâu thuẫn). Vậy
1 2 [Z]=t [Z] t □
Ví dụ : , BC A A C ® ®
Cần chứng minh AB ABC ®
Thật vậy từ:
1. A C ® (g/t)
2. AB BC ® (luật tăng trưởng của (1) thêm thuộc tính C )
3. BC A ® (g/t)
4. BC ABC ® (luật tăng trưởng của (3) thêm BC )
5. AB ABC ® (bắc cầu từ (2) và (4)) □
1.2.2.2 Hệ quả
Từ các tính chất trên chúng ta có các hệ quả sau đây:
1) Luật hợp : Nếu X Y ® và X Z ® thì X YZ ®
2) Luật tựa bắc cầu : Nếu X Y ® và WY Z ® thì W Z X ®
3) Luật tách : Nếu X Y ® và Z Y Í thì X Z ®
Chứng minh:
1) Từ X Y ® dùng luật tăng trưởng thêm X có X XY ® (1). Từ X Z ®
dùng luật tăng trưởng thêm Y có XY YZ ® (2)
Vậy từ (1) và (2) áp dụng luật bắc cầu suy ra X YZ ® □
2) Từ X Y ® dùng luật tăng trưởng, thêm W có W WY X ® (3). Mặt khác
theo giả thiết ta có WY Z ® (4)
Vậy từ (3) và (4) áp dụng luật bắc cầu ta có W Z X ® □
3) Do Z Y Í suy ra Y Z ® (theo luật phản xạ). Áp dụng luật bắc cầu cho
X Y ® và Y Z ® suy ra X Z ® □
1.2.3 Bao đóng tập thuộc tính
Trong m