Tài liệu Các dạng biểu diễn của khóa qua phép dịch chuyển lược đồ khối (2018)

TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 VIỆN CÔNG NGHỆ THÔNG TIN BÙI NHƢ NGỌC CÁC DẠNG BIỂU DIỄN CỦA KHÓA QUA PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Sƣ phạm Tin học HÀ NỘI - 2018 TRƢỜNG ĐẠI HỌC SƢ PHẠM HÀ NỘI 2 VIỆN CÔNG NGHỆ THÔNG TIN BÙI NHƢ NGỌC CÁC DẠNG BIỂU DIỄN CỦA KHÓA QUA PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Chuyên ngành: Sƣ phạm Tin học Ngƣời hƣớng dẫn khoa học PGS. TS. Trịnh Đình Thắng HÀ NỘI - 2018 LỜI CAM ĐOAN Tôi xin cam đoan đây là khóa luận tốt nghiệp nghiên cứu độc lập của riêng tôi. Các định nghĩa, trích dẫn đã có nguồn gốc rõ ràng, được công bố đúng theo quy định của pháp luật. Các ví dụ, nghiên cứu trong khóa luận tốt nghiệp do tôi tự tìm hiểu một cách trung thực, khách quan. Nếu có tranh chấp gì, tôi xin được chịu hoàn toàn trách nhiệm. Sinh viên nghiên cứu Bùi Nhƣ Ngọc LỜI CẢM ƠN Trân trọng cảm ơn giảng viên hướng dẫn PGS.TS. Trịnh Đình Thắng, các thầy giáo, cô giáo giảng viên khoa Công nghệ thông tin trường Đại học Sư phạm Hà Nội 2 đã tạo điều kiện tốt nhất để tôi có thể thực hiện khóa luận tốt nghiệp. Sinh viên nghiên cứu Bùi Nhƣ Ngọc MỤC LỤC MỞ ĐẦU CHƢƠNG 1. MÔ HÌNH DỮ LIỆU QUAN HỆ 1.1. Các khái niệm 1.2. Các phép toán trên lược đồ quan hệ 1 3 3 5 1.3. Phụ thuộc hàm 11 1.4. Bao đóng của tập phụ thuộc hàm và tập thuộc tính 1.5. Khóa của lược đồ quan hệ 13 17 1.6. Phép dịch chuyển lược đồ quan hệ 17 1.7. Một số dạng biểu diễn của khóa qua phép dịch chuyển lược đồ quan hệ 19 CHƢƠNG 2. MÔ HÌNH DỮ LIỆU DẠNG KHỐI 2.1. Các khái niệm 22 22 2.2. Các phép toán đại số trên mô hình dữ liệu dạng khối 2.3. Phụ thuộc hàm 26 34 2.4. Bao đóng của tập thuộc tính chỉ số trong lược đồ khối 35 2.5. Khóa của lược đồ khối 37 CHƢƠNG 3. KHÓA QUA PHÉP DỊCH CHUYỂN LƢỢC ĐỒ KHỐI 3.1. Phép dịch chuyển lược đồ khối 39 39 3.2. Biểu diễn khóa qua phép dịch chuyển lược đồ khối. 41 3.3. Một số tính chất mở rộng của khóa qua phép dịch chuyển lược đồ khối 44 KẾT LUẬN 51 TÀI LIỆU THAM KHẢO 52 DANH MỤC KÝ HIỆU VÀ CHỮ CÁI VIẾT TẤT Kí hiệu LĐQH Ý nghĩa Lược đồ quan hệ TC Tính chất ╞ Suy dẫn theo tiên đề theo logic ≠ Khác  Với mọi ∩ Phép giao  Phép hợp \ Phép trừ  Tập con  Nằm trong  Thuộc  Không thuộc X+ Bao đóng của tập thuộc tính X  Tương đương  Rỗng  Tồn tại DANH MỤC CÁC BẢNG Bảng 1.1. Quan hệ r 4 Bảng 1.2. Quan hệ Nhanvien 4 Bảng 1.3. Biểu diễn quan hệ Nhanvienl Nhanvien2 5 Bảng 1.4. Biểu diễn quan hệ Nhanvienl ∩ Nhanvien2 6 Bảng 1.5. Biểu diễn quan hệ Nhanvienl - Nhanvien2 6 Bảng 1.6. Biểu diễn quan hệ r * s 7 Bảng 1.7. Biểu diễn quan hệ ∏ Bảng 1.8. Biểu diễn quan hệ Tienluong>6.000.000(Nhanvien) e 8 9 Bảng 1.9. Biểu diễn phép nối tự nhiên r x s 10 Bảng 1.10. Biểu diễn phép chia 11 Bảng 2.1. Biểu diễn lát cắt r(R2/2018) 24 DANH MỤC CÁC HÌNH VẼ Hình 2.1. Biểu diễn khối BANHANG(R) 23 Hình 2.2. Biểu diễn các khối r, s, r s 27 Hình 2.3. Biểu diễn các khối r, s, r ∩ s 28 Hình 2.4. Biểu diễn các khối r, s, r – s 30 Hình 2.5. Biểu diễn các khối r, r‟=P(r) 32 MỞ ĐẦU 1. Lý do chọn đề tài Trong cuộc sống hiện đại ngày nay, Công nghệ thông tin đang ảnh hưởng tới mọi lĩnh vực. Các ứng dụng của Công nghệ thông tin đã và đang phát triển vượt trội trong các ngành khác nhau từ kinh tế tới giáo dục, từ nông nghiệp tới dịch vụ,... Trong đó, cơ sở dữ liệu là một trong những phần cốt lõi tạo nên sự phát triển của Công nghệ thông tin. Để đáp ứng các nhu cầu sử dụng đa dạng, rất nhiều mô hình dữ liệu đã được ra nghiên cứu và ứng dụng. Một số mô hình đang được sử dụng phổ biến trong hệ thống cơ sở dữ liệu toàn cầu như: mô hình thực thể - liên kết, mô hình mạng, mô hình phân cấp, mô hình quan hệ,... Trong đó, mô hình quan hệ được đánh giá cao hơn do nó được xây dựng trên cơ sở toán học chặt chẽ. Tuy nhiên mô hình này chưa đủ đáp ứng với các ứng dụng phức tạp. Vì vậy, người ta đã nghiên cứu và ứng dụng rộng rãi mô hình dữ liệu dạng khối. Ở mô hình này, các khái niệm cơ bản của khối được mở rộng từ các quan hệ trong mô hình quan hệ, các khối có thể biểu diễn dữ liệu dưới dạng động, có khả năng giải quyết các bài toán phức tạp hơn. Trong mô hình dữ liệu quan hệ cũng như mô hình dữ liệu dạng khối, việc xác định khóa là vô cùng quan trọng. Phép dịch chuyển lược đồ được đề xuất và nghiên cứu nhằm giảm tính phức tạp trong việc tìm ra khóa. Để góp phần hoàn thiện thêm về mô hình dữ liệu dạng khối, em xin chọn đề tài: Các dạng biểu diễn của khóa qua phép dịch chuyển lƣợc đồ khối. 2. Mục đích nghiên cứu Tìm hiểu khái quát về mô hình dữ liệu dạng khối, sau đó đi sâu tìm hiểu và nghiên cứu một số dạng biểu diễn của khóa qua phép dịch chuyển lược đồ khối. 1 3. Nhiệm vụ nghiên cứu - Tìm hiểu về mô hình dữ liệu dạng khối. - Tìm hiểu về các dạng biểu diễn của khóa qua phép dịch chuyển lược đồ khối. - Phát biểu và chứng minh một số dạng biểu diễn mới của khóa qua phép dịch chuyển lược đồ khối. - Minh họa một số ví dụ. 4. Đối tƣợng và phạm vi nghiên cứu Đối tƣợng: Khóa và phép dịch chuyển lược đồ khối. Phạm vi: Mô hình dữ liệu dạng khối. 5. Ý nghĩa khoa học và thực tiễn của đề tài - Biểu diễn của khóa qua phép dịch chuyển lược đồ khối. - Bổ sung thêm một số tính chất về biểu diễn khóa qua phép dịch chuyển lược đồ khối. - Có thể sử dụng các kết quả đã có trong việc xây dựng CSDL thực tế. 6. Phƣơng pháp nghiên cứu Phương pháp tổng hợp, phân tích các vấn đề liên quan đến đề tài. Phương pháp lý luận và chứng minh. 2 CHƢƠNG 1. MÔ HÌNH DỮ LIỆU QUAN HỆ Chương 1 trình bày một số khái niệm cơ bản nhất trong mô hình dữ liệu quan hệ, các phép toán cơ bản , định nghĩa về phụ thuộc hàm, bao đóng của tập phụ thuộc hàm, bao đóng của tập thuộc tính, các tính chất của khóa cùng với thuật toán tìm khoá. Các vấn đề trình bày ở chương 1 được tham khảo trong các tài liệu [5], [6]. 1.1. Các khái niệm 1.1.1. Thuộc tính và miền thuộc tính Định nghĩa 1.1 Thuộc tính là đặc trưng của đối tượng. Tập tất cả các giá trị có thể có của thuộc tính Ai gọi là miền giá trị của thuộc tính đó, ký hiệu: Dom(Ai) hay viết tắt là DAi. Ví dụ 1.1 Đối tượng Nhân viên (NV) có các thuộc tính như: Mã nhân viên (MaNV), Họ tên (Hoten), Ngày sinh (NS), Địa chỉ (DC). Miền giá trị của các thuộc tính của đối tượng NV: Dom(MaNV) = {„NV01‟, „NV02‟, „NV03‟,... }; Dom(Hoten) = {„Nguyễn Thị A‟,„Đỗ Văn B‟,...}; Dom(NS) = {„15/02/88‟, „20/10/92‟,...}; Dom(DC) = {„Hà Nội‟,„Hải Phòng‟,…}. 1.1.2. Quan hệ, lƣợc đồ quan hệ Định nghĩa 1.2 Cho U = {A1, A2,…, An} là một tập hữu hạn không rỗng các thuộc tính. Mỗi thuộc tính Ai (i =̅̅̅̅̅) có miền giá trị là Dom(Ai). Khi đó tập các bộ {h1, h2,..., hm}, kí hiệu r, được gọi là quan hệ trên U với hj (j = ̅̅̅̅̅̅) là một hàm: hj: U → DAi sao cho hj (Ai) DAi (i =̅̅̅̅̅) 3 Ta có thể xem một quan hệ như một bảng, trong đó mỗi hàng (phần tử) là một bộ và mỗi cột tương ứng với một thành phần gọi là thuộc tính. Biểu diễn quan hệ r như sau: Bảng 1.1. Quan hệ r А2 A1 An h1 h1(A1) h1 (A2) h1(An) h2 h2(A1) h2(A2) h2(An) … ... ... ... hm hm(A1) hm(A2) hm(An) Ví dụ 1.2 Bảng 1.2. Quan hệ Nhanvien Nhanvien MaNV Hoten NS DC NV01 Nguyễn Thị A 20/11/88 Hà Nội NV02 Đỗ Văn B 13/06/92 Hải Phòng NV03 Vũ Thị C 3/07/90 Nam Định Trong đó các thuộc tính là: MaNV: mã nhân viên Hoten: họ tên NS: ngày sinh DC: địa chỉ Bộ giá trị: (NV01, Nguyễn Thị A, 20/11/88, Hà Nội) là 1 phần tử của quan hệ Nhanvien. Định nghĩa 1.3 Tập tất cả các thuộc tính trong một quan hệ cùng với mối liên hệ giữa chúng được gọi là lược đồ quan hệ. 4 Lược đồ quan hệ R với tập thuộc tính U = {A1, A2,…, An} được viết là R(U) hoặc R(A1, A2,…, An). 1.2. Các phép toán trên lƣợc đồ quan hệ 1.2.1. Phép hợp Hai quan hệ r và s được gọi là khả hợp nếu như chúng có cùng tập thuộc tính và các thuộc tính cùng tên có cùng miền giá trị. Cho hai quan hệ r và s khả hợp. Hợp của r và s ký hiệu r hệ gồm tất cả các phần tử thuộc r hoặc thuộc s. Ta có: r s = {t | t s là một quan r t s} Ví dụ 1.3 Cho hai quan hệ NV1 và NV2 NV1 NV2 MaNV Hoten NV01 Nguyễn Thị A NV02 Đỗ Văn B MaNV Hoten NV01 Nguyễn Thị A NV03 Vũ Thị C Bảng 1.3. Biểu diễn quan hệ NVl NV1 NV2 NV2 MaNV Hoten NV01 Nguyễn Thị A NV02 Đỗ Văn B NV03 Vũ Thị C 1.2.2. Phép giao Cho hai quan hệ r và s khả hợp. Giao của r và s ký hiệu r ∩ s là một quan hệ gồm tất cả các bộ thuộc r và thuộc s. Ta có: r ∩ s = { t | t 5 r∧t s} Ví dụ 1.4 Cho 2 quan hệ NV1 và NV2 NV1 MaNV Hoten NV01 NV02 NV2 MaNV Hoten Nguyễn Thị A NV01 Nguyễn Thị A Đỗ Văn B NV03 Vũ Thị C Bảng 1.4. Biểu diễn quan hệ NVl ∩ NV2 NV1 ∩ NV2 MaNV Hoten NV01 Nguyễn Thị A 1.2.3. Phép trừ Cho hai quan hệ r và s khả hợp. Hiệu của r và s ký hiệu là r - s là tập tất cả các bộ thuộc r nhưng không thuộc s. Ta có: r – s = {t |t r∧t s} Ví dụ 1.5 Cho 2 quan hệ NV1 và NV2 NV1 MaNV Hoten NV01 NV2 MaNV Hoten Nguyễn Thị A NV01 Nguyễn Thị A NV02 Đỗ Văn B NV03 Vũ Thị C NV03 Vũ Thị C NV04 Phạm Văn D Bảng l.5. Biểu diễn quan hệ NVl - NV2 NV1 NV2 MaNV Hoten NV02 Đỗ Văn B NV04 Phạm Văn D 6 1.2.4. Tích Đề - các Cho hai quan hệ r và s bất kỳ có tập thuộc tính lần lượt là U 1 và U2 với U1 ∩ U2 = Ø . Tích Đề - các của r và s ký hiệu là: r x s là một quan hệ trên U1 U2 gồm tập tất cả các bộ ghép được từ các bộ của r và s. Ta có: r x s = {t = (u, v) | u r, v s} Ví dụ 1.6 Cho 2 quan hệ r và s R S MaNV Hoten Chucvu NV01 Nguyễn Thị A Văn thư NV02 Đỗ Văn B Phó phòng Giolam Tienluong 200 4500000 Bảng l.6. Biểu diễn quan hệ r x s rxs MaNV Hoten Giolam Tienluong NV01 Nguyễn Thị A 200 4500000 NV02 Đỗ Văn B 200 4500000 1.2.5. Phép chiếu Cho quan hệ r xác định trên tập thuộc tính U và X quan hệ r trên tập thuộc tính X, kí hiệu là X, ta có:  X (r) = {t.X | t  X U. Phép chiếu của (r) là tập các bộ của r xác định trên r} Thực chất của phép chiếu là phép toán giữ lại một số thuộc tính của quan hệ và loại bỏ những thuộc tính khác. 7 Ví dụ 1.7 Cho quan hệ Nhanvien, đưa ra giá trị các thuộc tính MaNV, Hoten, Tienluong của quan hệ Nhanvien. Ta sử dụng phép chiếu ∏ Nhanvien e . MaNV Hoten Chucvu Tienluong NV01 Nguyễn Thị A Văn thư 4.500.000 NV02 Đỗ Văn B Phó phòng 6.300.000 NV03 Vũ Thị C Trưởng phòng 7.000.000 NV04 Phạm Văn D Kế toán 5.700.000 Bảng 1.7. Biểu diễn quan hệ ∏ MaNV Hoten Tienluong NV01 Nguyễn Thị A 4.500.000 NV02 Đỗ Văn B 6.300.000 NV03 Vũ Thị C 7.000.000 NV04 Phạm Văn D 5.700.000 1.2.6. Phép chọn Phép chọn là phép toán lọc lấy ra một tập con các phần tử của quan hệ đã cho thoả mãn một điều kiện xác định. Điều kiện đó được gọi là điều kiện chọn hay biểu thức chọn, thường kí hiệu là F. Biểu thức chọn F được định nghĩa là một tổ hợp logic của các toán hạng, mỗi toán hạng là một phép so sánh đơn giản giữa hai biến là hai thuộc tính hoặc giữa một biến là một thuộc tính và một giá trị hằng. Biểu thức chọn F cho giá trị đúng hoặc sai đối với mỗi bộ đã cho của quan hệ khi kiểm tra riêng bộ đó. - Các phép toán so sánh trong biểu thức F: >, <, =, >=, <=, < >. 8 - Các phép toán logic trong biểu thức F: (và), v (hoặc), (phủ định). Cho r là một quan hệ và F là một biểu thức logic trên các thuộc tính của r Phép chọn trên quan hệ r với biểu thức chọn F, kí hiệu là cả các bộ của r thoả mãn F. Ta có: F(r) ={t|t r F(r), là tập tất F(t)}. Ví dụ 1.8 Cho quan hệ Nhanvien, hãy đưa ra đầy đủ thông tin của các nhân viên có lương > 6.000.000. Ta sử dụng phép chọn: Nhanvien Tienluong>6.000.000(Nhanvien) MaNV Hoten Chucvu Tienluong NV01 Nguyễn Thị A Văn thư 4.500.000 NV02 Đỗ Văn B Phó phòng 6.300.000 NV03 Vũ Thị C Trưởng phòng 7.000.000 NV04 Phạm Văn D Kế toán 5.700.000 Bảng 1.8. Biểu diễn quan hệ Tienluong>6.000.000(Nhanvien) MaNV Hoten Chucvu Tienluong NV02 Đỗ Văn B Phó phòng 6.300.000 NV03 Vũ Thị C Trưởng phòng 7.000.000 1.2.7. Phép kết nối Cho quan hệ r(U) và s(V). Đặt M=U ∩V. Phép kết nối tự nhiên hai quan hệ r(U) và s(V), ký hiệu r*s, cho ta quan hệ gồm các bộ được dán từ các bộ u của quan hệ r với mỗi bộ v của quan hệ s sao cho các trị trên miền thuộc tính chung M của hai bộ này giống nhau . r*s = {u*v│u r, v s, u.M=v.M} Nếu M = U ∩V = Ф, r*s sẽ cho ta tích Đề - các, trong đó mỗi bộ của quan hệ r sẽ được ghép với mọi bộ của quan hệ s. 9 Ví dụ 1.9 Cho 2 quan hệ r và s R S MaNV Hoten Xephang NV01 Nguyễn Thị A B NV02 Đỗ Văn B A NV03 Vũ Thị C A NV04 Phạm Văn D B Xephang Tienthuong A 2.000.000 B 1.000.000 Bảng 1.9. Biểu diễn quan hệ r*s r*s MaNV Hoten Xephang Tienthuong NV01 Nguyễn Thị A B 1.000.000 NV02 Đỗ Văn B A 2.000.000 NV03 Vũ Thị C A 2.000.000 NV04 Phạm Văn D B 1.000.000 1.2.8. Phép chia Cho r là một quan hệ xác định trên tập thuộc tính U = {A1,..., An} và s là một quan hệ xác định trên tập thuộc tính V = {A1,..., Am}, với V U, n > m và s , có nghĩa là lực lượng của s là khác 0 hay s có ít nhất một bộ. Phép chia quan hệ r cho quan hệ s, kí hiệu là r  s, là tập tất cả các bộ t trên U\V sao cho với mọi bộ vs thì khi ghép bộ t với bộ v ta được một bộ thuộc r. Ta có: r † s = {t│ v s, (t, v) r} Ví dụ 1.10 Cho bảng r và bảng s như dưới đây 10 Ta có phép chia Ketqua = r ÷ s r MaNV Hoten Tienluong Tienthuong NV01 Nguyễn Thị A 4500000 1000000 NV02 Đỗ Văn B 5000000 2000000 NV03 Vũ Thị C 5000000 2000000 NV04 Phạm Văn D 5700000 1000000 s Tienluong Tienthuong 5000000 2000000 Bảng 1.10. Biểu diễn quan hệ r ÷ s Ketqua MaNV Hoten NV02 ĐỗVăn B NV03 Vũ Thị C 1.3. Phụ thuộc hàm Định nghĩa 1.4 Cho lược đồ quan hệ R xác định trên tập thuộc tính U; X,Y U; r là quan hệ trên U. Ta nói rằng X xác định hàm Y hay Y phụ thuộc hàm vào X và ký hiệu X → Y nếu t1, t 2 r mà t1(X) = t2(X) thì t1(Y) = t2(Y). Ví dụ 1.11 Cho quan hệ Nhanvien MaNV Hoten NV01 Nguyễn Thị A Chucvu Diachi Khuvuc Văn thư Hà Nội 1 NV02 Đỗ Văn B Phó phòng Hải Phòng 1 NV03 Vũ Thị C Trưởng phòng Nam Định 2 NV04 Phạm Văn D Kế toán Vĩnh Phúc 2 11 Trong quan hệ Nhanvien, dựa vào định nghĩa phụ thuộc hàm của quan hệ, ta có quan hệ Nhanvien thỏa mãn 2 phụ thuộc hàm sau: {Diachi} → {Khuvuc} {MaNV} → {Hoten, Chucvu, Diachi, Khuvuc} Các tính chất của phụ thuộc hàm Cho lược đồ quan hệ R xác định trên tập thuộc tính U = {A1, A2,..., An}, cho X, Y, Z, W U thì ta có một số tính chất cơ bản của các phụ thuộc hàm như sau: TC1: Tính phản xạ Nếu Y X thì X → Y TC2: Tính mở rộng hai vế Nếu X → Y thì XW → YW. TC3: Tính chất bắc cầu Nếu X → Y, Y → Z thì X → Z. TC4: Tính tựa bắc cầu Nếu X → Y, YZ → W thì XZ → W. TC5: Tính cộng đầy đủ Nếu X → Y, Z → W thì XZ → YW. TC6: Tính mở rộng vế trái Nếu X → Y thì XZ → Y. TC7: Tính cộng ở vế phải Nếu X → Y, X → Z thì X → YZ. TC8: Tính bộ phận ở vế phải Nếu X → YZ thì X → Y. TC9: Tính lũy đẳng Nếu X → YZ, Z → W thì X → YZW. 12