Đề 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ệ

Chia sẻ: Sunflower Sunflower_1 | Ngày: | Loại File: PDF | Số trang:73

Thêm vào BST

Báo xấu

207
lượt xem 62
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề 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ệ

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. Wit h the objective of researching on the expansion of functional dependency and related concepts, my thesis focus on researching about data dependency, fuzz y 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 theore m.
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 Nghĩa đầy đủ TT Từ viết tắt 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 CSD L 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 1 ... 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 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 Te n đề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à X ® Y thì XW ® YW A3) Bắc cầu : Nếu X ® Y , Y ® Z thì X ® Z Chứng minh: A1) Giả sử t1 , t2 Î R và t1[X]=t 2 [X] cần chứng minh t1[Y]=t 2 [Y] Thật vậy do Y Í X suy ra t1[Y]=t 2 [Y] (đúng ) □ A2) Giả sử t1 , t2 Î R và t1[XW]=t 2 [XW] cần chứng minh t1[YW]=t 2 [YW] . Phản chứng: Giả sử t1[YW] ¹ t 2 [YW] . Do t1[W]=t 2 [W] nên để có t1[YW] ¹ t 2 [YW] thì t1[Y] ¹ t 2 [Y] . Nhưng theo giả thiết ta có X→Y nghĩa là t1[X]=t 2 [X] thì t1[Y]=t 2 [Y] Þ mâu thuẫn.Vậy t1[YW]=t 2 [YW] □
15 A3) Theo giả thiết ta có X ® Y , Y ® Z là hai PTH trên quan hệ R Giả sử t1 , t2 Î R và t1[X]=t 2 [X] cần chứng minh t1[Z]=t 2 [Z] Phản chứng : Giả sử t1[Z] ¹ t 2 [Z] . Từ X ® Y suy ra t1[X]=t 2 [X] thì t1[Y]=t 2 [Y] . Mặt khác ta lại có PTH Y ® Z nghĩa là t1[Y]=t 2 [Y] thì t1[Z]=t 2 [Z] nhưng theo giả thiết phản chứng ta có t1[Z] ¹ t 2 [Z] (mâu thuẫn). Vậy t1[Z]=t 2 [Z] □ 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ì XW ® Z 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ó XW ® WY (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ó XW ® Z □ 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ột quan hệ R có thể tồn tại nhiều các phụ thuộc hàm khác nha u 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 + được xác định như sau: F X F = { A| A Ì U , X ® A Î F } + + Ta viết gắn gọn X + là X . + F 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 = A 1 A 2 …A k + Do A 1 Î X ta có X ® A 1 +
17 Tương tự: X ® A 2 ……… X ® A k Theo Luật hợp ta có X ® A 1 A 2 …A k Þ 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 Þ Y Î X + ++ Þ Y Î X + + Þ Y Î X (theo tính chất luỹ đẳng) (1) + Do Y ® X Þ 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: f 1 , F 1 = F È {f 1 } f 2 , F 2 = F 1 È {f 2 } ……………….. f k , F k = F k -1 È {f k } Vậy ta có R(F) Þ R(F 1 ) Þ R(F 2 ) Þ … Þ R(F k ) Þ R(f) hay F = f □
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: A k A n R A 1 A 2 … A k +1 … a k a n u a 1 a 2 … a k +1 … a k b n v a 1 a 2 … b k +1 … Giả sử X = A 1 A 2 …A k + 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.