Luận án Tiến sỹ Toán học: Phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu

Chia sẻ: Lê Thị Hồng Nhung | Ngày: | Loại File: PDF | Số trang:132

Thêm vào BST

Báo xấu

47
lượt xem 5
download

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

Mục tiêu của luận án là nghiên cứu một số vấn đề như đã phân tích ở trên trong phạm vi cơ sở dữ liệu quan hệ. Trình bày tổng quan về mô hình dữ liệu quan hệ, các khái niệm FD, bao đóng của một tập thuộc tính, khóa của lược đồ quan hệ,…Đồng thời tập trung trình bày về RFD và khát quát các phương pháp đã được sử dụng để phát hiện FD và RFD.

Chủ đề:

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

Lưu

Nội dung Text: Luận án Tiến sỹ Toán học: Phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- VŨ QUỐC TUẤN PHÁT HIỆN PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG CƠ SỞ DỮ LIỆU LUẬN ÁN TIẾN SỸ TOÁN HỌC HÀ NỘI – 2019
BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM HỌC VIỆN KHOA HỌC VÀ CÔNG NGHỆ ----------------------------- VŨ QUỐC TUẤN PHÁT HIỆN PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG CƠ SỞ DỮ LIỆU LUẬN ÁN TIẾN SỸ TOÁN HỌC Chuyên ngành: Cơ sở Toán học cho Tin học Mã số: 9 46 01 10 Người hướng dẫn khoa học: 1. PGS. TS. Hồ Thuần 2. PGS. TS. Nguyễn Thanh Tùng Hà Nội – 2019
LỜI CAM ĐOAN Tác giả xin cam đoan đây là công trình nghiên cứu do chính tác giả thực hiện dưới sự hướng dẫn khoa học của PGS. TS. Hồ Thuần và PGS. TS. Nguyễn Thanh Tùng tại Học viện Khoa học và Công nghệ - Viện Hàn lâm Khoa học và Công nghệ Việt Nam. Tất cả các kết quả trình bày trong luận án là trung thực, không sao chép từ bất kỳ công trình nào khác. Nếu có điều gì không trung thực, tác giả xin chịu hoàn toàn trách nhiệm. Tác giả Vũ Quốc Tuấn i
LỜI CẢM ƠN Luận án này được thực hiện tại Học viện Khoa học và Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam dưới sự hướng dẫn khoa học của PGS. TS. Hồ Thuần và PGS. TS. Nguyễn Thanh Tùng. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới các Thầy đã tận tình chỉ bảo, động viên, hướng dẫn và tạo mọi điều kiện thuận lợi để tác giả hoàn thành luận án. Tác giả xin trân trọng cảm ơn tập thể các Thầy Cô trong Viện Công nghệ Thông tin đã có nhiều ý kiến đóng góp và phản biện trong suốt quá trình tác giả nghiên cứu và hoàn chỉnh luận án. Tác giả xin chân thành cảm ơn các nhà khoa học, các tác giả của các công trình đã được tham khảo và trích dẫn trong luận án. Tác giả xin trân trọng cảm ơn Lãnh đạo Viện Công nghệ Thông tin, Học Viện Khoa học và Công nghệ đã tạo những điều kiện tốt nhất để tác giả có được môi trường nghiên cứu và hoàn thành chương trình nghiên cứu sinh của mình. Xin chân thành cảm ơn các Phòng ban của Viện Công nghệ Thông tin đã giúp đỡ, tạo điều kiện cho tác giả trong suốt quá trình thực hiện luận án. Tác giả xin cảm ơn Ban giám hiệu Trường Cao đẳng Hải Dương, Khoa Tự Nhiên và Khoa Điện-Cơ-Tin đã tạo điều kiện thuận lợi cho tác giả thực hiện luận án. Xin cảm ơn tất cả các bạn đồng nghiệp đã luôn chia sẻ, động viên tác giả trong những lúc khó khăn. Cuối cùng, tác giả xin bày tỏ lòng biết ơn đối với những người thân trong gia đình, đặc biệt là mẹ và vợ, đã luôn ủng hộ và động viên cho tác giả trong suốt thời gian hoàn thành luận án. ii
MỤC LỤC Danh sách hình vẽ v Danh sách bảng v Danh sách chữ viết tắt vi MỞ ĐẦU 1 Chương 1. PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG MÔ HÌNH DỮ LIỆU QUAN HỆ 6 1.1. Nhắc lại một số khái niệm cơ bản ................................................................. 6 1.1.1. Miền ...................................................................................................... 6 1.1.2. Quan hệ ................................................................................................. 6 1.1.3. Các tính chất đặc trưng của một quan hệ ............................................... 7 1.1.4. Lược đồ quan hệ .................................................................................... 7 1.2. Phụ thuộc hàm .............................................................................................. 8 1.2.1. Khái niệm phụ thuộc hàm ...................................................................... 8 1.2.2. Hệ quy tắc suy diễn Armstrong ............................................................. 9 1.2.3. Bao đóng của một tập thuộc tính ........................................................... 9 1.2.4. Khóa của lược đồ quan hệ ..................................................................... 9 1.3. Phụ thuộc hàm suy rộng ............................................................................. 10 1.3.1. Phụ thuộc hàm xấp xỉ .......................................................................... 11 1.3.2. Phụ thuộc hàm mêtric .......................................................................... 13 1.3.3. Phụ thuộc hàm điều kiện ..................................................................... 14 1.3.4. Phụ thuộc hàm mờ ............................................................................... 16 1.3.5. Phụ thuộc sai phân............................................................................... 17 1.3.6. Các loại phụ thuộc hàm suy rộng khác ................................................ 18 1.4. Phát hiện phụ thuộc hàm............................................................................. 18 1.4.1. Phương pháp top-down ....................................................................... 19 1.4.2. Phương pháp bottom-up ...................................................................... 28 1.4.3. Một số chủ đề liên quan đến phát hiện phụ thuộc hàm ......................... 32 1.5. Phát hiện phụ thuộc hàm suy rộng .............................................................. 34 1.5.1. Phát hiện phụ thuộc hàm xấp xỉ ........................................................... 34 1.5.2. Phát hiện phụ thuộc hàm điều kiện ...................................................... 36 1.6. Tổng kết chương 1...................................................................................... 39 iii
Chương 2. PHỤ THUỘC HÀM XẤP XỈ VÀ PHỤ THUỘC HÀM ĐIỀU KIỆN 41 2.1. Về một số kết quả liên quan đến FD và AFD .............................................. 41 2.1.1. Phân hoạch .......................................................................................... 41 2.1.2. Một số kết quả ..................................................................................... 42 2.2. Phát hiện FD và AFD ................................................................................. 45 2.2.1. Ma trận tương đương ........................................................................... 45 2.2.2. Một số tính chất của ma trận thuộc tính ............................................... 48 2.2.3. Sử dụng ma trận để kiểm tra phụ thuộc hàm ........................................ 49 2.2.4. Sử dụng ma trận để tính một số độ đo xấp xỉ ....................................... 50 2.3. Phụ thuộc hàm điều kiện............................................................................. 54 2.3.1. Sự cần thiết phải mở rộng FD thành CFD ............................................ 54 2.3.2. Cú pháp và ngữ nghĩa của CFD ........................................................... 54 2.3.3. Một số kết quả quan trọng đã biết về CFD ........................................... 57 2.4. Về một thứ tự phân cấp giữa các FD, CFD và AR ...................................... 62 2.5. Kết luận chương 2 ...................................................................................... 72 Chương 3. THUẬT TOÁN TÍNH BAO ĐÓNG VÀ VẤN ĐỀ RÚT GỌN BÀI TOÁN TÌM KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 73 3.1. Thuật toán tính bao đóng ............................................................................ 73 3.1.1. Khái niệm bao đóng ............................................................................ 73 3.1.2. Một số thuật toán tính bao đóng .......................................................... 74 3.2. Vấn đề rút gọn bài toán xác định khóa của lược đồ quan hệ........................ 87 3.2.1. Một số kết quả đã biết ......................................................................... 87 3.2.2. Một dạng cải tiến cho điều kiện cần đã được công bố năm 1985.......... 89 3.2.3. So sánh các điều kiện cần .................................................................... 91 3.2.4. Một bài toán quyết định....................................................................... 95 3.3. Kết luận chương 3 ...................................................................................... 96 Chương 4. VỀ MỘT PHÉP BIẾN ĐỔI TIỀN XỬ LÝ HIỆU QUẢ CÁC TẬP PHỤ THUỘC HÀM 97 4.1. Giới thiệu ................................................................................................... 97 4.2. Sự dư thừa trong tập phụ thuộc hàm ......................................................... 100 4.3. Một phép biến đổi tiền xử lý hiệu quả các tập FD ..................................... 101 4.3.1. Logic Paredaens ................................................................................ 102 4.3.2. Một chứng minh mới cho định lý 4.1................................................. 107 4.4. Tổng kết chương 4.................................................................................... 113 KẾT LUẬN 114 DANH MỤC CÔNG TRÌNH CỦA TÁC GIẢ 116 TÀI LIỆU THAM KHẢO 117 iv
DANH SÁCH HÌNH VẼ Hình 1.1. Minh họa dàn thuộc tính........................................................... 20 Hình 2.1. Các luật suy diễn đối với CFD ................................................. 60 DANH SÁCH BẢNG BIỂU Bảng 1.1. Quan hệ Nhân viên ................................................................... 11 Bảng 1.2. Quan hệ Phim .......................................................................... 13 Bảng 1.3. Quan hệ Qh1............................................................................. 14 Bảng 1.4. Quan hệ Cust ........................................................................... 15 Bảng 1.5. Quan hệ Qh2............................................................................. 17 Bảng 1.6. Quan hệ Qh3............................................................................. 19 Bảng 1.7. Minh họa phụ thuộc hàm điều kiện .......................................... 38 Bảng 2.1. Một quan hệ minh họa ............................................................. 47 Bảng 2 .2. Quan hệ r ................................................................................ 67 Bảng 2.3. Quan hệ r1 ................................................................................ 68 Bảng 2.4. Quan hệ r2 ................................................................................ 68 Bảng 2.5. Quan hệ r3 ................................................................................ 68 Bảng 2.6. Quan hệ r4 ................................................................................ 68 Bảng 3.1. Minh họa cho ví dụ 3.3 ............................................................ 80 Bảng 3.2. Kết quả thử nghiệm .................................................................. 82 Bảng 3.3. Minh họa thuật toán 3.7 ........................................................... 84 Bảng 4.1. Quan hệ phân công .................................................................. 98 Bảng 4.2. Minh họa cho ví dụ 4.6 .......................................................... 111 Bảng 4.3. Minh họa cho ví dụ 4.7 .......................................................... 112 v
DANH SÁCH CHỮ VIẾT TẮT Từ Tiếng Anh Tiếng Việt viết tắt FD Functional dependency Phụ thuộc hàm RFD Relaxed functional dependencies Phụ thuộc hàm suy rộng AFD Approximate functional dependency Phụ thuộc hàm xấp xỉ MFD Metric functional dependency Phụ thuộc hàm mêtric FFD Fuzzy functional dependency Phụ thuộc hàm mờ DD Differential dependencies Phụ thuộc sai phân CFD Conditional Functional dependency Phụ thuộc hàm điều kiện AR Association Rule Luật kết hợp Extended Conditional Functional Phụ thuộc hàm điều kiện eCFD dependency mở rộng Phụ thuộc bao hàm điều CIND Conditional Inclusion Dependency kiện vi
MỞ ĐẦU Các phụ thuộc dữ liệu có vai trò quan trọng trong thiết kế cơ sở dữ liệu, quản lý chất lượng dữ liệu và biểu diễn tri thức. Việc sử dụng các phụ thuộc trong thiết kế cơ sở dữ liệu và quản lý chất lượng dữ liệu được giới thiệu trong phần lớn các sách về cơ sở dữ liệu. Các phụ thuộc trong trường hợp này được trích xuất từ các yêu cầu về ứng dụng, được sử dụng trong việc chuẩn hóa cơ sở dữ liệu và được cài đặt trong cơ sở dữ liệu đã được thiết kế để đảm bảo chất lượng dữ liệu. Ngược lại, các phụ thuộc trong phát hiện tri thức được trích xuất từ dữ liệu hiện có của cơ sở dữ liệu. Quá trình trích xuất này được gọi là phát hiện phụ thuộc với mục đích tìm tất cả các phụ thuộc được thỏa mãn (đúng) trên dữ liệu hiện có. Mục đích của việc phát hiện phụ thuộc là tìm các phụ thuộc quan trọng đúng (thỏa mãn) trên dữ liệu của cơ sở dữ liệu. Các phụ thuộc (được phát hiện) biểu diễn tri thức (thuộc lĩnh vực hoạt động nào đó) và có thể được sử dụng để kiểm tra thiết kế cơ sở dữ liệu cũng như đánh giá chất lượng dữ liệu. Ví dụ. Bằng việc kiểm tra dữ liệu của một cơ sở dữ liệu y học có hai thuộc tính Bệnh và Triệu chứng, nếu viêm phổi là một giá trị của Bệnh và sốt là một giá trị của Triệu chứng, đồng thời nếu mỗi bệnh nhân viêm phổi đều bị sốt thì sốt được cho là có liên quan đến viêm phổi. Nếu điều này xảy ra (đúng) đối với mọi cặp giá trị Triệu chứng và Bệnh thì Bệnh xác định hàm Triệu chứng và đây là một phụ thuộc hàm. Nếu phụ thuộc hàm này là một tri thức mới, nó sẽ giúp cho việc chẩn đoán bệnh hiệu quả hơn. Trong lĩnh vực khoa học sức khỏe hiện đại, việc tìm các mối liên hệ và các phụ thuộc như vậy (giữa các đoạn DNA và Bệnh) trở nên rất quan trọng đối với sự phát triển của y học. Bên cạnh việc phát hiện tri thức, các phụ thuộc được phát hiện từ dữ liệu có thể được sử dụng để kiểm tra xem các phụ thuộc đã được định nghĩa trước đây trên cơ sở dữ liệu có đúng (thỏa mãn) và đầy đủ hay không, đồng thời có thể dùng để kiểm tra ngữ nghĩa của dữ liệu trong cơ sở dữ liệu. 1
Một ứng dụng nữa của các phụ thuộc (được phát hiện) là để đánh giá chất lượng của dữ liệu. Vai trò chính của việc cài đặt các phụ thuộc trong một cơ sở dữ liệu là để đảm bảo chất lượng dữ liệu của cơ sở dữ liệu. Do đó, trên cơ sở phân tích các phụ thuộc được phát hiện và các phụ thuộc phải có giữa các thuộc tính của dữ liệu, ta có thể tìm và xác định được sự không nhất quán giữa các thuộc tính và các lỗi sai trên dữ liệu; từ đó, đánh giá được chất lượng dữ liệu. Từ những năm đầu thập kỷ 80 của thế kỷ 20, bài toán phát hiện phụ thuộc đã thu hút được sự quan tâm của đông đảo các nhà khoa học thuộc nhiều lĩnh vực nghiên cứu khác nhau như thiết kế cơ sở dữ liệu, học máy và phát hiện tri thức ([3], [10], [12], [18], [21], [26], [32], [33], [34], [37], [42], [45], [57], [65], [72], [75],...). Và cho đến thời điểm hiện tại, vấn đề phát hiện phụ thuộc từ các tập dữ liệu lớn (big data) càng trở nên quan trọng vì trong các tập dữ liệu lớn này chứa rất nhiều tri thức quý giá. Hiện nay, với sự phát triển của toàn xã hội và các thiết bị số, đặc biệt là các ứng dụng mạng xã hội và điện thoại thông minh (smartphone), lượng dữ liệu trong các ứng dụng tăng rất nhanh làm nảy sinh vấn đề lưu trữ, quản lý dữ liệu và đặc biệt là vấn đề phát hiện tri thức từ các tập dữ liệu lớn đó. Bài toán phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu là một trong những vấn đề quan trọng của phát hiện tri thức (dưới dạng các phụ thuộc). Ba loại phụ thuộc điển hình được chú ý phát hiện là phụ thuộc hàm (FD: Functional Dependency), phụ thuộc hàm xấp xỉ (AFD: Approximate Functional Dependency) và phụ thuộc hàm điều kiện (CFD: Conditional Functional Dependency). AFD là sự mở rộng của FD, tính chất xấp xỉ dựa trên độ thỏa hoặc độ đo lỗi; CFD là sự mở rộng của FD, nhằm nắm bắt những yếu tố không nhất quán trong dữ liệu. Các hướng nghiên cứu giải quyết bài toán phát hiện FD suy rộng trong cơ sở dữ liệu, trước hết tập trung vào vấn đề phát hiện FD do loại phụ thuộc này là trường hợp riêng của tất cả các loại FD suy rộng, các kết quả về phát hiện FD có thể được thích nghi để phát hiện các loại phụ thuộc khác (chẳng 2
hạn AFD). Mô hình chung của bài toán phát hiện FD là xây dựng không gian tìm kiếm các FD, kiểm tra sự thỏa mãn của từng FD, tỉa không gian tìm kiếm, xuất ra tập FD đã phát hiện được và làm gọn tập FD này (giảm bớt sự dư thừa). Trong bài toán phát hiện FD, phát hiện khóa là trường hợp đặc biệt và cũng là bài toán rất đáng quan tâm do khóa đóng vai trò quan trọng trong chuẩn hóa cơ sở dữ liệu quan hệ. Độ phức tạp thời gian tổng quát của bài toán phát hiện FD là đa thức theo số bản ghi trong cơ sở dữ liệu nhưng là hàm mũ theo số thuộc tính của cơ sở dữ liệu đó. Do đó, để giảm thời gian xử lý, cần xây dựng các luật tỉa hiệu quả. Trong số các luật tỉa đã được đề xuất, tỉa khóa là rất quan trọng, khi phát hiện được khóa thì có thể tỉa (xóa) mọi nút chứa khóa trong không gian tìm kiếm. Tuy nhiên, các luật tỉa khóa hiện có vẫn còn nhược điểm là tìm khóa trên toàn bộ tập thuộc tính  của cơ sở dữ liệu (đây thực sự là vấn đề rất khó vì độ phức tạp thời gian có thể là hàm mũ theo số thuộc tính của ), vậy có cách nào phát hiện được khóa trong một tập con thực sự của  hay không? Câu hỏi trên chính là một trong những động lực cơ bản của luận án này. Sau khi đã phát hiện được tập các phụ thuộc, tập này có thể rất lớn và gây khó khăn cho việc sử dụng vì chứa những dư thừa không cần thiết. Vấn đề quan trọng đặt ra là làm thế nào để loại bỏ được (càng nhiều càng tốt) sự dư thừa trong tập phụ thuộc đã được phát hiện. Đây cũng là bài toán được quan tâm trong luận án. Một hướng nghiên cứu nữa trong luận án là tập trung nghiên cứu, phát hiện hai loại FD suy rộng điển hình, đó là AFD và CFD. Cả AFD và CFD đều có nhiều ứng dụng và xuất hiện nhiều trong các cơ sở dữ liệu quan hệ, đặc biệt CFD còn là công cụ mạnh trong giải quyết bài toán làm sạch dữ liệu ([12]). Với AFD, vấn đề quan trọng nhất là cải tiến và phát triển các kỹ thuật tính toán các độ thỏa hoặc độ đo lỗi ([34], [72]); với CFD, ngoài việc phát hiện, thì việc tìm hiểu về một thứ tự phân cấp giữa CFD và một số loại phụ thuộc khác cũng là vấn đề rất đáng quan tâm. 3
Trong những năm gần đây, các hướng nghiên cứu về cải tiến thuật toán tính bao đóng của một tập thuộc tính đối với một tập FD, vấn đề rút gọn cho bài toán xác định khóa của lược đồ quan hệ, vấn đề về các phép biến đổi tiền xử lý hiệu quả các tập FD cho trước đã được xới lại, làm mới với hàng loạt các công trình của các tác giả nước ngoài ([22], [23], [24], [25], [52], [53], [54], [55]), trong khi ở trong nước, có nhiều công trình được công bố liên quan tới các phương pháp và thuật toán xác định các tập rút gọn (reduct) của một bảng quyết định theo nhiều tiếp cận khác nhau. Mục tiêu của luận án là nghiên cứu nhằm thu được một số kết quả giúp giải quyết có hiệu quả một số vấn đề như đã phân tích ở trên trong phạm vi cơ sở dữ liệu quan hệ. Để thực hiện các mục tiêu trên, chúng tôi tập trung vào các nội dung sau: 1) Nghiên cứu tổng quan về các loại FD suy rộng, các phương pháp phát hiện FD và FD suy rộng trong cơ sở dữ liệu quan hệ. 2) Nghiên cứu về AFD và CFD: kỹ thuật tính độ thỏa hoặc độ đo lỗi trong AFD, về một thứ tự phân cấp giữa CFD và một số loại phụ thuộc khác. 3) Nghiên cứu các thuật toán tính bao đóng của tập thuộc tính đối với một tập FD. Cải tiến được các thuật toán này sẽ làm tăng hiệu năng phát hiện khóa của lược đồ quan hệ. Nghiên cứu vấn đề rút gọn cho bài toán xác định khóa của lược đồ quan hệ, đây là vấn đề quan trọng, là cơ sở cho các luật tỉa khóa nhằm thu hẹp không gian tìm kiếm khi phát hiện các FD. 4) Nghiên cứu về một phép biến đổi tiền xử lý các tập FD nhằm thu được một tập FD tương đương nhưng đơn giản hơn tập FD ban đầu. Với các nội dung nghiên cứu trên, luận án được cấu trúc gồm phần mở đầu, bốn chương nội dung và phần kết luận. Chương 1. Trình bày tổng quan về mô hình dữ liệu quan hệ, các khái niệm FD, bao đóng của một tập thuộc tính, khóa của lược đồ quan hệ,…Trong đó tập trung trình bày về FD suy rộng và khát quát các phương pháp đã được sử dụng để phát hiện các FD và FD suy rộng. 4
Chương 2. Trình bày về AFD và CFD (hai loại FD suy rộng điển hình) và một số kết quả có liên quan. Chương 3. Trình bày các thuật toán tính bao đóng của một tập thuộc tính đối với một tập FD, vấn đề rút gọn cho bài toán xác định khóa của lược đồ quan hệ và một số kết quả có liên quan. Chương 4. Trình bày một phép biến đổi tiền xử lý hiệu quả các tập FD (nhằm hạn chế sự dư thừa trong một tập FD cho trước) và một số kết quả liên quan. Kết luận. Tổng kết các kết quả đã đạt được, những điểm còn tồn tại và hướng nghiên cứu tiếp theo. 5
Chương 1. PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM SUY RỘNG TRONG MÔ HÌNH DỮ LIỆU QUAN HỆ Chương này nhắc lại các khái niệm cơ bản của mô hình dữ liệu quan hệ, tập trung vào các khái niệm phụ thuộc hàm, phụ thuộc hàm suy rộng và khái quát các phương pháp đã được sử dụng để phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng. 1.1. Nhắc lại một số khái niệm cơ bản Mô hình dữ liệu quan hệ được E.F.Codd đề xuất năm 1970 và ngay lập tức mô hình này đã gây được sự chú ý vì có tính đơn giản và cơ sở toán học vững chắc. Mô hình dữ liệu quan hệ biểu thị dữ liệu trong một cơ sở dữ liệu như một tập các quan hệ. Về mặt trực quan, ta có thể hình dung một quan hệ như là một bảng giá trị gồm các hàng và các cột. Mỗi hàng trong bảng là một tập các giá trị có liên quan đến nhau, các giá trị này biểu thị một sự kiện tương ứng với một thực thể hay một mối quan hệ trong thế giới thực. Trong lý thuyết mô hình dữ liệu quan hệ, các thuật ngữ quan hệ, thuộc tính, miền và bộ tương ứng được dùng để chỉ bảng, cột, kiểu dữ liệu của một cột và một hàng trong bảng. 1.1.1. Miền Một miền D là một tập các giá trị nguyên tố, hiểu theo nghĩa mỗi giá trị trong miền là không thể phân chia được thành các thành phần nhỏ hơn trong phạm vi mô hình quan hệ. Mỗi miền được đặc tả thông qua một tên miền và một kiểu dữ liệu. Tương ứng với mỗi thuộc tính có một miền, các thuộc tính khác nhau không nhất thiết phải có các miền khác nhau. 1.1.2. Quan hệ Một quan hệ trên (hay xác định trên) tập thuộc tính Ω = {A1, A2,…,An} là một tập con của tích Descartes Dom(A1)  Dom(A2)  …  Dom(An), trong đó Dom(Ai) là miền trị của thuộc tính Ai, i = 1, 2,…, n. 6
Cho quan hệ r xác định trên tập thuộc tính Ω = {A1, A2,…,An}. Theo định nghĩa, ta có thể viết r dưới dạng sau: r  {(a1, a2,…,an) | ai  Dom(Ai), i = 1, 2,…, n} 1.1.3. Các tính chất đặc trưng của một quan hệ Để làm rõ hơn khái niệm quan hệ trong mô hình dữ liệu quan hệ, ta xem xét các tính chất đặc trưng sau đây của quan hệ:  Mỗi quan hệ có một tên phân biệt.  Mỗi ô trong bảng (quan hệ) chứa một giá trị nguyên tố.  Mỗi thuộc tính có một tên phân biệt.  Các giá trị của một thuộc tính thuộc cùng một miền.  Thứ tự của các thuộc tính là không quan trọng.  Không có hai bộ trùng nhau trong một quan hệ.  Thứ tự của các bộ là không quan trọng. Mỗi giá trị trong một bộ phải là một giá trị nguyên tố. Mô hình dữ liệu quan hệ không cho phép có các thuộc tính phức hợp hoặc các thuộc tính đa trị. Đặc trưng này đòi hỏi mỗi thuộc tính đa trị phải được biểu diễn bằng một quan hệ và mỗi thuộc tính phức hợp phải được biểu diễn bằng các thành phần đơn của nó. Trường hợp một số ô trong bảng (quan hệ) có thể là chưa biết được giá trị của chúng vào thời điểm đang xét hoặc không có giá trị nào thích hợp đặt cho một ô (thuộc tính) của một bộ nào đó thì một giá trị đặc biệt, gọi là giá trị null, được sử dụng cho các ô kiểu này. Thứ tự của các thuộc tính trong một quan hệ là không quan trọng khi đảm bảo được sự tương ứng giữa các thuộc tính với các giá trị. Vì các phần tử trong một tập hợp là không có thứ tự nên các bộ không có một thứ tự bắt buộc trong một quan hệ. Định nghĩa quan hệ cũng cho thấy rằng hai quan hệ được xem là đồng nhất nếu chúng có cùng các bộ cho dù thứ tự các bộ trong chúng khác nhau. 1.1.4. Lược đồ quan hệ Một lược đồ quan hệ S là một cặp có thứ tự S = , trong đó Ω là 7
tập hữu hạn các thuộc tính của quan hệ, F là tập các ràng buộc giữa các thuộc tính. Một ràng buộc trên tập thuộc tính {A1, A2,…,An} là một tính chất trên tập tất cả các quan hệ xác định trên tập thuộc tính này. Mỗi ràng buộc còn được gọi là một phụ thuộc dữ liệu. Một lược đồ quan hệ được sử dụng để mô tả về cấu trúc và các ràng buộc của một quan hệ. Một quan hệ có thể liên tục thay đổi theo thời gian nhưng cấu trúc và các ràng buộc của nó có thể ổn định trong một khoảng thời gian nhất định. Cho lược đồ quan hệ S = với Ω = {A1, A2,…,An}. Nếu không quan tâm đến tập các ràng buộc F thì ta sẽ dùng ký hiệu S(A1, A2,…,An) hoặc S(Ω) thay cho S = . Ta dùng ký hiệu r(S) để chỉ một quan hệ r (hay một thể hiện r) của lược đồ quan hệ S. Với một bộ t của r(S) và X  Ω, ta ký hiệu t[X] là bộ chỉ chứa các giá trị của bộ t tại các thuộc tính trong X. Một lược đồ cơ sở dữ liệu quan hệ là một tập các lược đồ quan hệ S’ = {S1, S2,…,Sp}. Một thể hiện của một lược đồ cơ sở dữ liệu quan hệ S’ là một tập các thể hiện DB = {r1(S1), r2(S2),…, rp(Sp)}. Một cơ sở dữ liệu quan hệ là một thể hiện của một lược đồ cơ sở dữ liệu quan hệ. Một cơ sở dữ liệu quan hệ cỡ lớn là một cơ sở dữ liệu quan hệ chứa một lượng lớn dữ liệu (cỡ vài chục thuộc tính, hàng trăm nghìn bản ghi). 1.2. Phụ thuộc hàm Phụ thuộc hàm là một loại phụ thuộc dữ liệu giữa hai nhóm thuộc tính của một lược đồ quan hệ và nó thể hiện tính chất ngữ nghĩa của các thuộc tính. 1.2.1. Khái niệm phụ thuộc hàm Phụ thuộc hàm. Cho  là tập thuộc tính và S() là một lược đồ quan hệ trên . Giả sử X, Y  . Khi đó Y được gọi là phụ thuộc hàm vào X trên lược đồ S(), ký hiệu là X  Y, nếu với mọi quan hệ r trên lược đồ S(), với hai bộ bất kỳ t1, t2  r mà t1[X] = t2[X] thì t1[Y] = t2[Y]. 8
Nếu Y phụ thuộc hàm vào X thì ta cũng nói "X xác định hàm Y". Với mỗi quan hệ r trên lược đồ S(), ta nói r thỏa mãn (hay thỏa) phụ thuộc hàm X  Y (hay phụ thuộc hàm X  Y đúng trên r) nếu và chỉ nếu với mọi bộ t1, t2  r, t1[X] = t2[X] kéo theo t1[Y] = t2[Y] . Trong luận án này, ta hạn chế F của lược đồ S = chỉ gồm các phụ thuộc hàm. 1.2.2. Hệ quy tắc suy diễn Armstrong Với lược đồ quan hệ S = và X, Y  , ta ký hiệu XY thay cho X  Y. Với mọi X, Y, Z  , hệ quy tắc suy diễn Armstrong đối với các phụ thuộc hàm gồm ba quy tắc sau đây: Q1. (Phản xạ): Nếu Y  X thì X  Y. Q2. (Gia tăng): Nếu X  Y thì XZ  YZ. Q3. (Bắc cầu): Nếu X  Y và Y  Z thì X  Z. Ký hiệu F+ là tập tất cả các phụ thuộc hàm được suy diễn từ F bằng cách áp dụng một số hữu hạn lần các quy tắc của hệ quy tắc suy diễn Armstrong. 1.2.3. Bao đóng của một tập thuộc tính Cho tập phụ thuộc hàm F xác định trên tập thuộc tính  (phụ thuộc hàm Y  Z xác định trên tập thuộc tính  nếu Y, Z  ) và X  . Ta gọi bao đóng của tập thuộc tính X đối với tập phụ thuộc hàm F, ký hiệu là X F , là tập tất cả các thuộc tính A của  sao cho X  A được suy diễn từ F nhờ hệ quy tắc suy diễn Armstrong. X F = {A    (X  A)  F+} 1.2.4. Khóa của lược đồ quan hệ Một quan hệ là một tập hợp các bộ. Các phần tử trong một tập hợp là phân biệt nên không thể có hai bộ trùng nhau trong một quan hệ. Như vậy, với mỗi lược đồ quan hệ S = , tồn tại một tập thuộc tính SK  Ω có tính chất: với mỗi thể hiện r(S) thì t1[SK] ≠ t2[SK], với t1, t2 là hai bộ khác nhau bất kỳ trong r. 9
Siêu khóa của một lược đồ quan hệ S là một tập gồm một hay nhiều thuộc tính của lược đồ S có tính chất xác định duy nhất một bộ trong mỗi thể hiện của S. Cho lược đồ quan hệ S = . Nếu SK là siêu khóa của S thì mọi tập con của Ω mà chứa SK cũng là siêu khóa của S. Một siêu khóa "nhỏ nhất" được gọi là một khóa. Khóa của một lược đồ quan hệ S là một siêu khóa của S sao cho mọi tập con thực sự của siêu khóa này đều không phải là siêu khóa của S. Mỗi lược đồ quan hệ luôn có ít nhất một khóa và có thể có nhiều khóa. Một thuộc tính xuất hiện trong một khóa nào đó được gọi là thuộc tính khóa. Ngược lại, một thuộc tính không xuất hiện trong bất kỳ khóa nào được gọi là thuộc tính không khóa. Sử dụng khái niệm phụ thuộc hàm, khái niệm khóa và siêu khóa của lược đồ quan hệ được định nghĩa lại như sau: Cho lược đồ quan hệ S = và K  . Ta nói K là một khóa của S nếu hai điều kiện sau đây đồng thời được thỏa mãn: (i). (K  )  F+ (ii). Nếu K'  K thì (K'  )  F+ Nếu K   thỏa mãn điền kiện (i) thì K được gọi là một siêu khóa của S. Như vậy, mọi khóa của S đồng thời cũng là siêu khóa của S. 1.3. Phụ thuộc hàm suy rộng Cho r là một quan hệ xác định trên tập thuộc tính Ω = {A1, A2,…,An} và X, Y  . Từ định nghĩa phụ thuộc hàm ở trên, ta nhận thấy: nếu tồn tại t1, t2  r sao cho t1[X] = t2[X] và t1[Y]  t2[Y] thì ta kết luận được rằng r không thỏa phụ thuộc hàm X  Y (hay phụ thuộc hàm X  Y không đúng trên r). Điều này tỏ ra quá chặt chẽ và cứng nhắc khi ta hình dung quan hệ r có hàng nghìn bộ, trong đó chỉ có một vài bộ vi phạm phụ thuộc hàm X  Y do có một số dữ liệu bị sai lệch hoặc một số ngoại lệ. Do đó, việc mở rộng khái niệm phụ thuộc hàm thành phụ thuộc hàm suy rộng theo một cách thức, một nghĩa nào 10
đó là nhu cầu tất yếu và tự nhiên. Tùy theo cách thức và ý nghĩa của sự mở rộng, các phụ thuộc hàm suy rộng có thể được đặt tên khác nhau như phụ thuộc hàm xấp xỉ, phụ thuộc hàm điều kiện, phụ thuộc hàm metric,... 1.3.1. Phụ thuộc hàm xấp xỉ Phụ thuộc hàm xấp xỉ [41] là các phụ thuộc hàm được thỏa mãn với phần lớn các bộ trong quan hệ. Để định nghĩa thuật ngữ "xấp xỉ" một cách chính xác hơn, một độ đo được sử dụng để đo mức độ thỏa mãn (độ thỏa) hay mức độ vi phạm (độ đo lỗi) của mỗi phụ thuộc hàm. Để xác định mức độ vi phạm của X  Y trên quan hệ r, một độ đo lỗi nào đó, ký hiệu là e( X  Y , r ) , sẽ được sử dụng. Cho trước một ngưỡng lỗi , 0    1. Ta nói X  Y là phụ thuộc hàm xấp xỉ nếu và chỉ nếu e( X  Y , r )   . Một độ đo lỗi được sử dụng phổ biến là g3 [41], dựa trên số bộ tối thiểu cần phải loại bỏ khỏi r để X  Y đúng. min| r1 |: r1  r , X  Y ®óng trªn r \ r1 g3 ( X  Y , r )  |r| Ví dụ 1.1. Với quan hệ cho trong bảng 1.1, ta thấy Tên xác định xấp xỉ Giới tính, để phụ thuộc hàm Tên  Giới tính đúng ta chỉ cần loại bỏ một bộ có mã số 003. Ta có: g3(Tên  Giới tính, Nhân viên) = 1/8 = 0.125 Mã số Họ đệm Tên Giới tính Chức vụ t1 001 Vũ Văn Tuấn Nam Trưởng phòng t2 002 Nguyễn Thị Mai Nữ Phó trưởng phòng t3 003 Phạm Thị Hải Nữ Nhân viên t4 004 Trần Văn Hải Nam Nhân viên t5 005 Nguyễn Minh Tuấn Nam Nhân viên t6 006 Vũ Thị Linh Nữ Nhân viên t7 007 Lê Văn Hải Nam Nhân viên t8 008 Nguyễn Văn Thắng Nam Nhân viên Bảng 1.1. Quan hệ Nhân viên 11
Có nhiều phương pháp đã được đề xuất để tính độ thỏa hoặc độ đo lỗi. Các phương pháp này được tóm tắt và so sánh trong [34]. Chẳng hạn, trong [72], độ thỏa của X  Y trên quan hệ r được xác định như sau: tti ,tt j R TRUTH ( t i , t j ) ( X  Y ) TRUTHr(X  Y ) = i j NTP trong đó, nếu ti[X] = tj[X] và ti[Y]  tj[Y] thì TRUTH ( ti ,t j ) ( X  Y )  0 , ngược lại TRUTH (ti ,t j ) ( X  Y )  1 ; NTP là tổng số cặp bộ trong r và bằng |r|(|r| - 1)/2. Ví dụ 1.2. Với quan hệ cho trong bảng 1.1, ta có độ thỏa của phụ thuộc hàm Tên Giới tính là TRUTHNhân viên(Tên Giới tính) = 26/28  93% Một cách khác để tính độ thỏa của X  Y trên quan hệ r được giới thiệu trong [56, 57], cụ thể: xây dựng quan hệ tương đương E(X) trên r như sau: (t1, t2)  E(X)  t1[X] = t2[X],  t1, t2  r Quan hệ E(X) phân hoạch r thành các lớp tương đương. Mỗi lớp tương đương là một tập con của r chứa các bộ giống nhau trên X. Ký hiệu phân hoạch đó là  X . Với u   X , nếu t1[X] = t2[X]  t1[Y] = t2[Y],  t1, t2  u, thì ta nói rằng u thỏa X  Y. Ngược lại, u không thỏa X  Y. Thực hiện đoạn chương trình dưới đây để nhận được quan hệ r1. r1 : = ; For each u   X do if (u thỏa X  Y) then r1 : = r1  u; Đặt k = |r1| / |r|. Khi đó, ta nói r thỏa X  Y với độ phụ thuộc k, 0  k  1. Ví dụ 1.3. Xét phụ thuộc hàm Tên  Giới tính trên quan hệ cho trong bảng 1.1, ta có  Tên = {{t1, t5}, {t2}, {t3, t4, t7}, {t6}, {t8}}, r1 = {{t1, t5}  {t2}  {t6}  {t8} = {t1, t5, t2, t6, t8}, k = |r1| / |r| = 5/8 = 0.625. Như vậy, r thỏa phụ thuộc hàm Tên  Giới tính với độ phụ thuộc 0.625. 12