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ệ
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
2
3
4
5
6
CNTT
Công nghệ thông tin
Cơ sở dữ liệu
Hệ thống thông tin
Hệ điều hành
Phụ thuộc hàm
Fuzzy Functional Dependency - Phụ thuộc hàm
CSDL
HTTT
HĐH
FTH
FFD
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 = {A1...An }, 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 :
STT
Ten
Namsinh
Diachi
DT
Email
HS
1
Trung
1983
Việt Trì 0989313797 Trungtt
2
3
Kiên
Nam
1987
1984
Phú Thọ 045596045
Hà Nội 045769823
kientt
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
X ,Y, Z, W ⊆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à
thì
XW → YW
X → Y
A3) Bắc cầu : Nếu X → Y,Y → Z thì
X → Z
Chứng minh:
t [X]=t [X]
t [Y]=t [Y]
A1) Giả sử t1,t2 ∈ R và
cần chứng minh
1
2
1
2
t [Y]=t [Y]
Thật vậy do Y ⊆ X suy ra
(đúng )
□
1
2
t [XW]=t [XW]
t [YW]=t [YW]
A2) Giả sử t1,t2 ∈ R và
cần chứng minh
.
1
2
1
2
t [YW] ≠ t [YW]
t1[W]=t2[W]
nên để có
Phản chứng: Giả sử
t1[YW] ≠ t2[YW]
. Do
1
2
t [Y] ≠ t [Y]
thì
. Nhưng theo giả thiết ta có X→Y nghĩa là
1
2
t [X]=t [X]
t [Y]=t [Y]
t [YW]=t [YW]
mâu thuẫn.Vậy
thì
□
⇒
1
2
1
2
1
2
15
A3) Theo giả thiết ta có X → Y,Y → Z là hai PTH trên quan hệ R
t [X]=t [X]
t [Z]=t [Z]
Giả sử t1,t2 ∈ R và
cần chứng minh
1
2
1
2
t [Z] ≠ t [Z]
t1[X]=t2[X]
Phản chứng : Giả sử
t [Y]=t [Y]
. Từ
suy ra
thì
t [Y]=t [Y] t1[Z]=t2[Z]
thì
X → Y
1
2
. Mặt khác ta lại có PTH
nghĩa là
Y → Z
1
2
1
2
t [Z] ≠ t [Z]
nhưng theo giả thiết phản chứng ta có
(mâu thuẫn). Vậy
□
1
2
t1[Z]=t2[Z]
Ví dụ : BC → A, A → C
Cần chứng minh
Thật vậy từ:
AB → ABC
1.
2.
3.
4.
5.
(g/t)
A → C
(luật tăng trưởng của (1) thêm thuộc tính C )
(g/t)
AB → BC
BC → A
(luật tăng trưởng của (3) thêm BC )
(bắc cầu từ (2) và (4))
BC → ABC
AB → ABC
□
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
và
thì
X → YZ
X → Y
X → Z
2) Luật tựa bắc cầu : Nếu
và
thì
WY → Z
X → Y
XW → Z
X → XY
3) Luật tách : Nếu
và Z ⊆ Y thì
X → Z
X → Y
Chứng minh:
1) Từ
dùng luật tăng trưởng thêm Y có
dùng luật tăng trưởng thêm X có
(1). Từ
X → Y
X → Z
(2)
XY → YZ
Vậy từ (1) và (2) áp dụng luật bắc cầu suy ra
□
X → YZ
2) Từ
dùng luật tăng trưởng, thêm W có
(3). Mặt khác
X → Y
XW → WY
theo giả thiết ta có
(4)
WY → Z
Vậy từ (3) và (4) áp dụng luật bắc cầu ta có
□
XW → Z
3) Do Z ⊆ Y suy ra
(theo luật phản xạ). Áp dụng luật bắc cầu cho
□
Y → Z
suy ra
X → Z
và
X → Y
Y → Z
1.2.3 Bao đóng tập thuộc tính
Trong một quan hệ R có thể tồn tại nhiều các phụ thuộc hàm khác nhau
giữa các thuộc tính (có thể nhiều thuộc tính phụ thuộc vào một thuộc tính hoặc
cũng có thể một thuộc tính phụ thuộc và nhiều thuộc tính khác nhau). Để tổng
16
quát hoá các phụ thuộc hàm này người ta đưa ra khái niệm Bao đóng tập thuộc
tính [3].
Gọi F là tập tất cả các phụ thuộc hàm đối với quan hệ R trên tập thuộc
tính U và X→Y là một phụ thuộc hàm ( X, Y⊆U). Ta nói rằng X→Y được suy
diễn ra từ F nếu quan hệ r trên R(U) đều thoả mãn phụ thuộc hàm F thì cũng
thoả mãn X→Y. Chẳng hạn như F = { A→C, C→D} thì A→D được suy ra từ
F. Gọi F+ là bao đóng (transitive closure) của F tức là tập tất cả các phụ thuộc
hàm được suy diễn logic từ F. Nếu F=F+ thì F là họ đầy đủ của các phụ thuộc
hàm.
1.2.3.1 Định nghĩa
Cho tập thuộc tính U, X⊂U và F là tập các phụ thuộc hàm nào đó trên U.
Khi đó ta định nghĩa Bao đóng của tập thuộc tính X theo phụ thuộc hàm F được
ký hiệu là X +F được xác định như sau:
X+F = { A| A⊂U , X→A ∈F+ }
Ta viết gắn gọn X +F là X+.
Nhận xét: Khái niệm Bao đóng tập thuộc tính có ý nghĩa hết sức quan trọng
trong việc nghiên cứu về lớp phụ thuộc dữ liệu. Có thể nói đây là một trong
những khái niệm quan trọng nhất vì tất cả các kết quả quan trọng nhất trong lớp
phụ thuộc hàm đều liên quan đến khái niệm này.
1.2.3.2 Tính chất của Bao đóng
Dựa vào các tính chất của phụ thuộc hàm ta có các tính chất của Bao đóng
tập thuộc tính như sau:
1) Tính phản xạ: X⊆X+
2) Tính đơn điệu: Nếu X⊆Y thì X+ ⊆Y+.
3) X→ X +
4) Tính luỹ đẳng: X++= X+.
5) X+Y+ ⊆(XY)+.
6) (X+Y)+ = (XY+) = (XY)+.
7) X→Y Y⊆X+.
⇔
8) X→Y và Y→X X+=Y+.
⇔
Chứng minh:
1) Lấy bất kỳ A∈X, ta cần chứng minh A∈X+.
Ta có A∈X
{A}⊆X. Vậy theo Luật phản xạ suy ra X→A A∈X+.
□
□
⇔
⇒
2) Lấy A∈X+ , ta cần chứng minh A∈Y+.
Ta có A∈X+ X→A (1)
⇒
Mà X⊆Y Y→X (2) ( theo Luật phản xạ )
⇒
Vậy từ (1) và (2) và Luật bắc cầu ta có Y →A A∈Y+
⇒
3) Giả sử X+= A1 A2 …Ak
Do A1 ∈X+ ta có X→A1
17
Tương tự:
X→A2
………
X→Ak
Theo Luật hợp ta có X→A1 A2 …Ak
X→ X +
⇒
4) Ta có X+ ⊆X++ ( tính chất 1). Ta cần chứng minh X++ ⊆X+
Lấy A ∈X++ , ta cần chứng minh A∈X+.
Do A ∈X++
X+ →A (1)
⇒
Mặt khác theo tính chất 3 ta có : X→ X + (2)
Từ (1) và (2) ta có X→A ( tính chất bắc cầu) A∈X+
□
□
⇒
5) Ta có X ⊆XY
Theo tính chất 2 ( tính đơn điệu ) ta có : X+ ⊆(XY)+ (1)
Tương tự ta cũng có: Y+ ⊆(XY)+ (2)
Từ (1) và (2) suy ra X+Y+ ⊆(XY)+.
6) Theo những phần trên ta có:
X⊆X+Y (1)
X+ ⊆(XY)+ (2)
Y⊆(XY)+ (3)
Từ (1), (2) và (3) ta có X+Y⊆(XY)+
(X+Y)+ ⊆(XY)++ = (XY)+ ( theo tính luỹ
⇒
đẳng )
Vậy ta có (X+Y)+ ⊆ (XY)+ (4)
⇒
Mặt khác ta cũng có :
X⊆X+
( tính chất 1)
XY⊆ X+Y
⇒
⇒
(XY)+ ⊆ (X+Y)+ (5)
( tính đơn điệu)
Từ (4) và (5) suy ra (X+Y)+ = (XY)+
□
7) Để chứng minh X→Y Y⊆X+ ta có:
⇔
a) Giả sử có X→Y ta cần chứng minh Y⊆X+
Lấy bất kỳ A∈Y, ta cần chứng minh A∈X+
Ta có: A∈Y
Y→A (1)
⇒
Theo giả thiết ta lại có: X→Y (2)
Từ (1) và (2) và luật bắc cầu ta có X→A
A∈X+
⇒
b) Giả sử có Y⊆X+ ta cần chứng minh X→Y
Do Y⊆X+ X+ →Y ( luật phản xạ )
⇒
Mặt khác: X→ X + ( theo tính chất 3)
Suy ra: X→Y ( luật bắc cầu)
8) Để chứng minh X→Y và Y→X X+=Y+ ta có:
⇔
a) Giả sử có X→Y và Y→X ta cần chứng minh X+=Y+
Do X→Y
Do Y→X
Y∈X+
⇒
⇒
⇒
⇒
⇒
Y+∈X++
Y+∈X+ (theo tính chất luỹ đẳng) (1)
X∈Y+
X+∈Y++
18
X+∈Y+ (theo tính chất luỹ đẳng) (2)
⇒
Từ (1) và (2) ta có X+=Y+
b) Giả sử có X+=Y+ ta cần chứng minh X→Y và Y→X
Do X+=Y+ nên ta có
□
Y+ ⊆X+ (1’)
X+ ⊆Y+ (2’)
Theo tính chất 1 ta có Y⊆Y+ mà Y+ ⊆X+
Y⊆X+
X→Y ( theo tính chất 7)
⇒
⇒
Nhận xét: Trong các tính chất trên thì tính chất 7 là quan trọng nhất. Thực tế ta
cần biết với một phụ thuộc hàm X→Y thì hỏi rằng phụ thuộc hàm đó có được
suy dẫn logic từ tập phụ thuộc hàm F hay không?
Khi đó đặt ra 2 vấn đề:
- Nếu biết Y⊆X+ thì X→Y ∈F+
- Nếu Y X+ thì X→Y F+
⊄
∉
Khi đó nếu ta xây dựng được một thuật toán tìm X+ một cách dễ dàng như vậy
thì ta cũng có thể trả lời câu hỏi X→Y một cách dễ dàng.
1.2.4 Định lý tương đương
Định nghĩa: Cho tập phụ thuộc hàm F trên tập thuộc tính U và f là một phụ
thuộc hàm trên U. Ta nói PTH f được suy dẫn theo quan hệ từ tập phụ thuộc
hàm F và viết F =f nếu mọi quan hệ R(U) thoả F thì R cũng thoả f.
Định nghĩa: Cho tập phụ thuộc hàm F trên tập thuộc tính U và f là một phụ
thuộc hàm trên U. Ta nói phụ thuộc hàm f được suy dẫn theo tiên đề ( hoặc suy
dẫn logic) từ tập PTH F và viết F├ f nếu f∈F+. Nói cách khác f được suy dẫn
theo các tiên đề từ tập PTH F nếu như áp dụng các luật A1, A2, A3 đối các PTH
trong F thì sau hữu hạn lần ta sẽ thu được f.
Định lý: Với mọi tập FPT F và PTH f trên tập thuộc tính U ta có F├ f khi và
chỉ khi F =f . Hay, suy dẫn theo tiên đề và suy dần theo quan hệ là một.
Ký hiệu: F├ f F =f .
⇔
Chứng minh:
a) Giả sử ta có F├ f ta cần chứng F =f.
Giả sử sau k bước ứng dụng các luật của hệ tiên đề ta nhận được các phụ thuộc
hàm:
f1 , F1 = F∪ {f1 }
f2 , F2 = F1 ∪ {f2 }
………………..
fk , Fk = Fk−1 ∪ {fk }
Vậy ta có R(F)
R(F )
R(F ) … R(F )
R(f) hay F =f
□
⇒
⇒
⇒
⇒
⇒
1
2
k
19
b) Giả sử ta có F =f ta cần chứng minh F├ f .
Để chứng minh F =f
F├ f ta sẽ chứng minh F├ f thì F =f
⇒
Thật vậy, đặt f = X→Y. Khi đó có F, X ta sẽ tính được X+
Xây dựng quan hệ R như sau:
R
u
A1
a1
A2
a2
…
…
…
Ak
ak
Ak +1
ak +1
bk +1
…
…
…
An
an
v
a1
a2
ak
bn
Giả sử X+= A1 A2 …Ak
Như vậy quan hệ R chỉ gồm 2 bộ u và v. Hai bộ này giống nhau trên tập X+ và
với mọi thuộc tính B≠ X+ thì u.B≠ v.B tức là a j ≠ b j ( j = k+1,..n).
Ta sẽ chứng minh f vừa dẫn xuất được theo quan hệ R và f vừa không dẫn xuất
được theo quan hệ R.
Hay là ta chứng minh R(f) và ┐R(f)
1) Ta chứng minh R thoả mãn mọi phụ thuộc hàm trong F+ hay R(f).
Giả sử có PTH Z→W ∈F+ và u.Z = v.Z. Ta cần chứng minh u.W = v.W.
Ta có: u.Z = v.Z
Z⊆X+
X+ →Z ( theo tính phản xạ )
⇒
⇒
Mà ta lại có X→X+ (theo tính chất 3)
Áp dụng tính chất bắc cầu cho các phụ thuộc hàm X→X+, X+ →Z và Z→W ta
có X→W
Suy ra W⊆X+ ( theo tính chất 7)
Vậy u.W = v.W
□
2) Ta chứng minh R không thoả mãn PTH X→Y hay ta cần chứng minh có
u.X = v.X nhưng u.Y ≠ v.Y .
Từ là X→Y F
Y X+ (theo tính chất 7)
∉
⇔
⊄
Suy ra: u.Y ≠ v.Y (1)
Mặt khác theo tính chất 1 ta có X⊆X+ u.X = v.X (2)
⇒
Từ (1) và (2) suy ra R không thoả mãn PTH X→Y hay ┐R(f)
□
1.3 Khoá
Trong một quan hệ có những thuộc tính đóng vai trò “chủ chốt” và từ các
thuộc tính này có thể suy ra được các thuộc tính khác thông qua các phụ thuộc
dữ liệu. Khái niệm về khoá cũng là một trong những khái niệm quan trọng nhất
trong việc nghiên cứu và xây dựng CSDL.
20
Nói đến khoá (key) [3] trong quan hệ R là nói đến một tập nhỏ nhất các
thuộc tính nhằm phân biệt các đối tượng. Việc xác định khoá cũng xác định
được tính toàn vẹn dữ liệu trong CSDL quan hệ. Do đó việc tìm khoá trong 1
lược đồ mang ý nghĩa hết sức quan trọng.
Định nghĩa: Cho lược đồ quan hệ α = (U,F), trong đó F là tập các phụ thuộc
hàm trên quan hệ R
Tập K⊆U. Khi đó K được gọi là một siêu khoá nếu K+=U
R được gọi là quan hệ của α nếu như ta có R(F).
Nhận xét:
- Nếu K là siệu khoá của lược đồ α thì hai bộ t1, t2 bất kỳ không thể giống
nhau trên K.
- Trong lược đồ quan hệ α có thể có một hoặc nhiều siêu khoá
- Hợp của một siêu khoá là một siêu khoá
- Giao của các hoá nói chung không là một siêu khoá.
Định nghĩa: Cho lược đồ quan hệ α = (U,F), trong đó F là tập các phụ thuộc
hàm trên quan hệ R
Tập K⊆U
Khi đó K được gọi là khoá của lược đồ nếu K thoả mãn hai điều kiện sau:
1. K là 1 siêu khoá
2. ∀ K1⊆ K thì K1 không là siêu khoá.
Tức là:
K+ =U
∀K1⊆K:K1 ≠U
+
{
Nhận xét:
- Trong lược đồ quan hệ α có thể có một hoặc nhiều khoá
- Hợp của các khoá khác nhau không phải là một khoá.
21
CHƯƠNG 2. LỚP PHỤ THUỘC HÀM MỜ TRONG
CƠ SỞ DỮ LIỆU QUAN HỆ
2.1 Dữ liệu mờ
Cơ sở dữ liệu [2] là biểu hiện của thế giới thực, hầu hết các giá trị của nó
là rõ ràng nhưng đôi khi cũng không xác định, không rõ ràng hay còn gọi là mờ
(fuzzy). Việc thiết kế Cơ sở dữ liệu với các giá trị ra sao là do nhà thiết kế lựa
chọn và tuỳ vào mục đích sử dụng nhưng hầu hết các Cơ sở dữ liệu hiện nay đều
rõ. Tuy nhiên để nắm bắt những giá trị chưa rõ ràng của thế giới thực đặc biệt là
với những ứng dụng trong các ngành sinh học và gen, hệ thống thông tin địa lý,
hệ thống dự báo kinh tế và thời tiết,… người ta nghĩ đến việc mờ hoá dữ liệu và
xây dựng mô hình Cơ sở dữ liệu mờ.Việc xây dựng cũng như phát triển các mô
hình cơ sở dữ liệu mờ cũng như lớp phụ thuộc hàm mờ (FFDs) có thể theo nhiều
hướng khác nhau nhưng đều dựa trên các khái niệm cơ bản sau:
2.1.1 Tập rõ
Khái niệm tập rõ là khái niệm được sử dụng trong CSDL truyền thống.
Khi đó các thuộc tính được xét đến coi như thoả mãn các yêu cầu một cách tuyệt
đối. Ta có thể định nghĩa về tập rõ như sau:
Cho U là tập các đối tượng, A là tập con của U. A được gọi là tập rõ (crisp
set) [4] nếu A được định nghĩa bởi hàm đặc trưng của nó sao cho:
1
0
nếu x thuộc A
(x) =
λ
nếu x không thuộc A
2.1.2 Tập mờ
Cho U là tập các đối tượng x∈ U. A là tập con của U, A được gọi là tập
mờ (fuzzy set ) [4] nếu các phần tử x chỉ thuộc A với ngưỡng nào đó được xác
định bởi ánh xạ µ : U → [ 0,1] (0 ≤ µA ≤1), µ (x) là mức thoả của phần tử x
A
A
thuộc A, nếu µ (x) = 0 thì
còn nếu µ (x) = 1 thì x hoàn toàn thuộc vào
x ∉ A
A
A
A. Tập rõ là một trường hợp đặc biệt của tập mờ khi µ (x) = 1.
A
Ký hiệu: A = {x, µA(x) x ∈ U} với x∈ U và µ (x) là mức thỏa của x trong
A
tập mờ A.
22
Hình 3: Tập mờ và tập rõ
Như vậy ta có:
µ(x) ≥ 0∀x∈U
sup[µ A (x)]=1
x∈u
Ví dụ : Cho các phần tử A,B,C thuộc vào tập X với các mức 0.4, 0.7, 0.8.
Khi đó tập mờ X sẽ được biểu diễn như sau:
X = {(A,0.4) , (B, 0.7), (C, 0.8)}
2.1.3 Các phép toán cơ bản trên tập mờ
Trong tập mờ có một số phép toán cơ bản sau:
§ Phép lấy phần bù
C = ~ A(u) = 1 – A(u)
§ Phép hợp
C = ( A ∪ B )(u) = max [A (u), B(u)]
§ Phép giao
C = (A∩ B)(u) = min [ A(u), B(u) ]
Ví dụ: Cho 2 tập mờ :
X = { (A,0.9), (B,0.8), (D,0.6)}
Y = { (A,0.7), (B,0.65), (G,0.6)}
Khi đó ta có:
Phép lấy phần bù: Z= ~ X(u) = 1–X(u) = {(A,0.1),(B,0.2),(D,0.4)}.
23
Phép giao: Z = (X∩ Y)(u) = min [ A(u), B(u) ] = {(A,0.7),
(B,0.65), (D,0.6),(G,0.6)}.
Phép hợp: Z=(X∪ Y)(u) = max [ A(u), B(u) ] = {(A,0.9), (B,0.8),
(D,0.6),(G,0.6)}.
2.2 Phụ thuộc hàm mờ
Trong quá trình xác định những ràng buộc dữ liệu, đặc biệt là việc xác
định lớp các thụ thuộc hàm đã cho thấy vẫn còn những vấn đề cần được giải
quyết. như là trong cơ sở dữ liệu lớn, các dữ liệu nhiễu thì những xung đột dữ
liệu và lỗi đều có thể xảy ra, cụ thể như sự thiếu chính xác trong việc nhập, thay
đổi cũng như cập nhật dữ liệu. Nói chung khó có thể tìm được phụ thuộc hàm
nếu ràng buộc giữa các thuộc tính chưa rõ ràng, chưa xác định hoặc mờ. Vì vậy
việc mở rộng phụ thuộc hàm mờ (fuzzy functional dependency) [12] sẽ giúp cho
việc thiết kế mô hình dữ liệu để xử lý được những vấn đề về phụ thuộc dữ liệu
với độ tin cậy α (0<α <1) . Chúng ta sẽ xét đến phụ thuộc hàm (X → Y)α nghĩa
là Y phụ thuộc hàm vào X với mức α nào đó.
2.2.1 Định nghĩa
Định nghĩa: Cho một tập U ={ A1 , A2 , …, An } với mỗi phần tử Ai∈U là một
thuộc tính, ứng với mỗi thuộc tính Ai ; i =1,2,…,n sẽ có miền giá trị là Di .Ký
hiệu Dom(Ai ) = Di . Ta chỉ xét Di ≥ 2. Khi đó:
Với R là một quan hệ trên U; X→Y là phụ thuộc hàm trên quan hệ R
Cặp bộ bất kỳ ti , tj ∈ R được gọi là thoả mãn phụ thuộc hàm X→Y nếu
ti (X) = tj(X) thì ti (Y) = tj(Y).
Đặt :
0 nếu ti (X) = tj(X) nhưng ti (Y) ≠ tj(Y)
T(
(X→Y)
=
ti , t j )
1 nếu ngược lại
(X→ Y) = 1 ta nói rằng 2 cặp bộ ti , t j thỏa mãn phụ thuộc
Nếu T(
ti , t j )
hàm X→Y.
Quan hệ R được gọi là thoả mãn phụ thuộc hàm X→Y với hai bộ bất kỳ
ti , tj ∈ R nếu T( (X→ Y) = 1.
ti , t j )
Nhận xét: Nếu quan hệ R được gọi là thoả mãn phụ thuộc hàm X→Y thì
T R (X→ Y) = 1
24
Định nghĩa: Cho tập thuộc tính U ={ A1 , A2 , …, An } và R là một quan hệ trên
U; X , Y⊆ U . Đặt
T( t
) ( X → Y )
∑
,
t
i
j
∀ ti
,
t
∈
R
j
ti
≠
t
j
TR (X→Y) =
trong đó: n là số bộ trong R: N = C2n = n(n–1)/2.
Nhận xét: Ta thấy 0<T R (X→Y)≤1.
N
- Nếu T R (X→ Y) = 1 thì chính là định nghĩa phụ thuộc hàm trong CSDL
truyền thống.
- Nếu 0<T R (X→Y)≤1. Xét hệ số α nào đó (0<α ≤ 1). Khi đó quan hệ R
có T R (X→Y) ≥ α thì ta nói quan hệ R thoả mãn phụ thuộc hàm X→Y
với mức thoả α (0<α ≤ 1).
- Khi giá trị T R (X→Y) càng gần giá trị 1 thì quan hệ R thoả mãn phụ
thuộc hàm X→Y càng có ý nghĩa và chặt chẽ. Nếu T R (X→Y) càng gần
giá trị 0 thì quan hệ R thoả mãn mãn phụ thuộc hàm X→Y lỏng lẻo và
gần như không có ý nghĩa khi ta xét đến các ràng buộc dữ liệu trong quan
hệ R.
Ví dụ: Cho quan hệ R :
R
STT
X
Y
1
2
3
4
5
6
7
A
A
A
B
B
C
C
E
E
G
H
K
D
D
Khi đó theo định nghĩa trên ta có T R (X→Y) = 85,7 % . Vậy R thỏa mãn
phụ thuộc hàm X→Y với mức thoả α ≥ 0.875.
Định nghĩa: Cho tập thuộc tính U ={ A1 , A2 , …, An } và R là một quan hệ trên
U; X, Y là hai tập con của U.
25
Khi đó với giá trị α (0<α ≤ 1) cho trước nếu T R (X→Y) ≥ α thì X → Y
được gọi là phụ thuộc hàm trong R với mức thoả α hay nói cách khác là R thỏa
mãn phụ thuộc hàm X → Y với mức thoả α .
Một số mở rộng định nghĩa Phụ thuộc hàm:
Theo định nghĩa trên mới xét đến phụ thuộc hàm mờ với mức thoả α
(0<α ≤ 1) còn dữ liệu là rõ (các thuộc tính X, Y). Do đó đôi khi trong một CSDL
có thể gây ra “lãng phí” dữ liệu. Chẳng hạn như xét một quan hệ HS sau đây:
HS STT
Toán
Lý
6,8
Văn
Trung bình
1
2
8
9
7.93
8.0
8.3
7
8.7
Theo định nghĩa thì 2 bộ t1 , t2 ∈ R được gọi là phụ thuộc hàm X→Y nếu
t1 (X) = t2(X) thì t1 (Y) = t2(Y). Trong trường hợp “xấp xỉ” nhau thì cũng coi
như khác biệt và không có sự phụ thuộc hàm gì ở đây. Chính điều này gây ra
“lãng phí” dữ liệu và không thấy được sự phụ thuộc dữ liệu gì ở đây.
Theo một cách khác nếu xét ở chừng mực nào đó ta có thể đánh giá 2 bộ
vẫn phụ thuộc hàm vào nhau, chẳng hạn như ví dụ trên HS 1 có điểm các môn
gần như “tương đương” với HS 2. Theo định nghĩa trên thì sẽ không tồn tại phụ
thuộc hàm giữa 2 bộ này. Tuy nhiên nếu đặt ra “tỷ lệ” khác biệt nào đó thì ta
λ
có thể coi 2 bộ này “giống nhau” và sẽ có phụ thuộc hàm:
{Toán, Lý, Hoá }→Trung bình
Chẳng hạn ta xét “tỷ lệ” khác biệt giữa 2 bộ 1 và 2 ở các thuộc tính lần lượt như
sau:
+ Thuộc tính Toán: ta có λ = 0.96
1
+ Thuộc tính Lý: ta có λ2 = 0.97
+ Thuộc tính Văn: ta có λ3 = 0.96
+ Thuộc tính Trung bình: ta có λ4 = 0.99
Ta có thể coi “tỷ lệ” khác biệt giữa giữa hai bộ thuộc tính mức độ phụ
thuộc dữ liệu giữa hai bộ thuộc tính này.
Lấy min{λi } với I = 1,4, ta có min{λi } = min {0.96, 0.97, 0.96, 0.99} =
0.96
Ta có thể nói : ({Toán, Lý, Hoá }→Trung bình )0.96
26
Như vậy xét theo một khía cạnh nào đó ta có thể mở rộng thêm định nghĩa
về Phụ thuộc hàm mờ như sau:
Định nghĩa 1: Cho tập thuộc tính U ={ (A1 ,λ ), (A2 ,λ2 ),…, (An ,λn )} và R là
1
một quan hệ trên U; X, Y là hai tập con của U.
Đặt = min{λ } với i =1, n và (0< ≤ 1)
λ
λ
i
Khi đó với nói rằng 2 bộ t1 , t2 là thoả mãn PTH X → Y mức
nếu
λ
λ
λ
t1 (X) = t2(X) thì t1 (Y) = t2(Y) .
Định nghĩa 2: Cho tập thuộc tính U ={ (A1 ,λ ), (A2 ,λ2 ),…, (An ,λn )} và R là
1
một quan hệ trên U; X, Y là hai tập con của U.
Đặt = min{λ } với i =1, n và (0< ≤ 1)
λ
λ
i
Khi đó R được gọi là thoả mãn PTH X → Y với mức thoả
nếu T R
λ
(X→Y) ≥
.
λ
Nhận xét:
- Từ việc nghiên cứu về lớp phụ thuộc hàm trong CSDL quan hệ truyền thống ta
thấy rằng việc mở rộng các khái niệm (mờ hoá) sẽ càng ngày càng giúp cho việc
xây dựng các hệ thống dữ liệu sát với thực tế hơn. Đặc biệt việc mở rộng này có
ý nghĩa vô cùng quan trọng trong các hệ thống dự báo như là hệ thống về dự báo
thời tiết, dự báo tăng trưởng kinh tế,….
- Dưới đây là một số hướng mở rộng về phụ thuộc hàm trong CSDL quan hệ.
Dữ liệu
Độ bằng
Độ phụ thuộc
Kết quả
R
R
R
Quan niệm truyền
thống
R
R
Mở rộng 1
(X → Y)α
(X → Y)α
R
M
M
Mở rộng 2
Mở rộng 3
(X → Y)α
M
Ghi chú: R: Rõ; M: Mờ
Bảng 2: Bảng các mở rộng của Phụ thuộc hàm
- Các định nghĩa mở rộng về phụ thuộc hàm mờ chỉ coi như là một mở rộng khi
xét đến các phụ thuộc dữ và đánh giá độ tin cậy của dữ liệu chứ không nên sử
dụng trong việc tìm Khoá của lược đồ quan hệ.
27
2.2.2 Tính chất
Cũng tương tự như trong khái niệm phụ thuộc hàm truyền thống, đối với
lớp phụ thuộc hàm mờ cũng có một số tính chất [12] như sau:
Tính chất 1( Tính phản xạ ): Cho R là một quan hệ trên tập thuộc tính U, X và
Y là các tập con của U. Khi đó nếu Y⊆ X thì TR (X →Y) = 1.
Chứng minh:
Vì Y⊆ X nên với mỗi cặp (ti , t j ) thuộc R ta có:
§ Nếu ti (X) = t j (X) thì t j (Y) = t j (Y), theo định nghĩa 1 ta có
T(t , t ) (X→Y) = 1
(1)
i
j
§ Nếu ti (X) ≠ t j (X) thì trong cả hai trường hợp t j (Y) = t j (Y) hoặc t j (Y)
≠ t j (Y) ta đều có T(t , t ) (X→Y) = 1 (2)
i
j
Vậy từ (1) và (2) ta có T R (X →Y) = 1
□
Tính chất 2 (Tính tăng trưởng): Cho R là một quan hệ trên tập thuộc tính U.
Với X, Y và Z là các tập con của U. Khi đó:
Nếu TR (X →Y) ≥ α thì T R (XZ →YZ) ≥ α ( 0≤
1) [12]
α ≤
Chứng minh:
Với 3 tập thuộc tính X, Y, Z ta có thể liệt kê tất cả các khả năng kết hợp
giữa các tập thuộc thuộc tính. Do đó ta có bảng sau:
ti (X) = t j (X) ti (Y) = t j (Y) ti (Z)= t j (Z) T(t , t ) (X→Y) T(t , t ) (XZ→YZ)
i
j
i
j
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
Bảng 3: Bảng các khả năng kết hợp giữa các tập thuộc tính
Trong đó : 1 biểu diễn ti (X) = t j (X)
0 biểu diễn ti (X) ≠ t j (X)
28
Vậy theo bảng trên ta thấy với mỗi cặp bộ (ti ,t j ) thì
T(t , t ) (XZ→YZ)≥ T(t , t ) (X→Y).
i
j
i
j
Theo giả thiết
T R (X →Y) ≥ α ta có:
(T(t , t ) (X → Y))/N = T (X →Y).
T R (XZ →YZ) =
(T(t , t ) (XZ → YZ))/N ≥
∑
∑
R
i
j
i
j
Vậy T R (XZ →YZ) ≥ α
□
Tính chất 3 (Tính tựa bắc cầu): Cho R là một quan hệ trên tập thuộc tính U.
Với X, Y và Z là các tập con của U. Khi đó:
Nếu T R (X →Y) =α , TR (Y →Z) = β thì T R (X →Z) =γ với γ =
min(α, β ).
Chứng minh:
Ta có bảng sau:
ti (X) = t j (X) ti (Y) = t j (Y) ti (Z)= t j (Z) T(t , t ) (X→Y) T(t , t ) (XZ→YZ)
i
j
i
j
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
1
1
1
1
0
0
1
1
1
1
1
1
1
0
1
1
Bảng 4: Bảng các khả năng kết hợp giữa các tập thuộc tính
Trong đó : 1 biểu diễn ti (X) = t j (X)
0 biểu diễn ti (X) ≠ t j (X)
Coi n là số bộ của quan hệ R . N = C2n = n(n-1)/2.
Dựa vào bảng ta thấy T(t , t ) (X→Z) = 0 tại vị trí thứ 5 và thứ 7
i
j
T(t , t ) (X → Z)
∑
i
j
∀ti , t j∈ R
ti t j
≠
[
]
n(n −1) − 4
Vậy định nghĩa ta có TR (X→Z) = γ =
=
N
2N
29
[
]
[
]
n(n −1) − 4
n(n −1) − 4
Tương tự α =
;
β =
2N
2N
Suy ra γ = min(α, β)
□
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)
Để đơn giản ta ký hiệu phụ thuộc hàm X → Y với mức thỏa T R (X →
Y)≥ α là (X → Y)α . Đây cũng là sự mở rộng rất tự nhiên của hệ tiên đề
Amstrong. Việc mở rộng này sẽ là cơ sở nền tảng cho phép xem xét các vấn đề
liên quan đến phụ thuộc hàm, bao đóng và khoá trong ngữ cảnh mờ.
Định lý( Hệ tiên đề Amstrong mở rộng[12] ): Cho R là một quan hệ trên tập
thuộc tính U và X, Y, Z là 3 tập thuộc tính của U. Khi đó:
A1': Nếu Y⊆ X thì (X → Y)α với (0
).
≤ α ≤1
A2': Nếu (X → Y)α thì (X Z→ YZ)α
A3': Nếu (X → Y)α , (Y→ Z)β thì (X → Z)φ với φ = min(α,β) .
A4': Nếu (X → Y)α thì (X→ Y) β với mọi β ≤ α
Chứng minh: Với A1' , A2' , A3' dễ dàng chứng minh dựa vào định nghĩa Phụ
thuộc hàm mờ nêu trên và các tính chất 1,2 và 3.
Với A4' ta có (X→ Y)α tức là T R (X → Y) = α ≥ β suy ra (X→ Y) β
□
Từ hệ tiên đề trên ta cũng có các hệ quả sau:
Hệ quả:
D1: Nếu (X→Y)α và (X→Z)β thì (X→ YZ)γ với γ = min(α, β) .
D2: Nếu (X→Y)α và (WY→Z)β thì (WX→Z)γ γ = min(α, β)
D3: Nếu (X→Y)α và Z⊆ Y thì (X→Z)α .
D4: (X→Y1 Y2 … Yk )α khi và chỉ khi (X→ Yi )α với i = 1,2,…,k.
Chứng minh:
D1: Từ (X→Y)α theo A2' ; thêm X ta có (X→XY)α
Từ (X→Z)β cũng theo A2' ; thêm Y ta có (XY→YZ)β . Và cuối cùng
theo A3' ta có (X→ YZ)γ với γ = min(α, β) .
D2: Từ (X→Y)α theo A2' ; thêm W ta có (WX→WY)α . Khi từ giả thiết
theo A3' ta có (WX→Z)γ với γ = min(α, β) .
D3: Vì Z⊆ Y nên (Y→Z) với (0
) ( theo A1' )
≤ α ≤1
α
Tải về để xem bản đầy đủ
73 trang
05/06/2025
50
Bạn đang xem 30 trang mẫu của tài liệu "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ệ", để 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_nghien_cuu_mot_so_van_de_ve_phu_thuoc_du_lieu_va_kh.pdf
