Tài liệu học tập Cơ sở dữ liệu: Phần 2 - Trường ĐH Kinh tế kỹ thuật công nghiệp

Nội dung của tài liệu bao gồm 4 chương, trình bày cụ thể như sau: Cơ sở dữ liệu quan hệ; Ngôn ngữ truy vấn dữ liệu; Lý thuyết thiết kế cơ sở dữ liệu; Bảo mật và toàn vẹn dữ liệu. Mời các bạn cùng tham khảo nội dung tài liệu phần 2 dưới đây.
Nội dung trích xuất từ tài liệu:
Tài liệu học tập Cơ sở dữ liệu: Phần 2 - Trường ĐH Kinh tế kỹ thuật công nghiệp 121 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU CHƯƠNG 3 LÝ THUYẾT THIẾT KẾ CƠ SỞ DỮ LIỆU Mục tiêu: Chương này sẽ trình bày những khái niệm cơ bản nhất về lý thuyết cơ sở dữ liệu quan hệ do E.F Codd đề xuất, đó là các khái niệm về quan hệ, về khóa của lược đồ quan hệ. Những khái niệm này có vai trò quan trọng trong việc thiết kế và cài đặt các hệ cơ sở dữ liệu quan hệ và các hệ quản trị cơ sở dữ liệu. Nội dung của chương bao gồm các phần: Phụ thuộc hàm Bao đóng Phủ tối thiểu Khóa của lược đồ quan hệ Phép tách – kết nối Các dạng chuẩn của lược đồ quan hệ Các phương pháp chuẩn hóa lược đồ quan hệ 3.1. Phụ thuộc hàm 3.1.1 Định nghĩa phụ thuộc hàm Cho một quan hệ R xác định trên tập thuộc tính U, kí hiệu là R(U). X, Y là các tập con của U, ta nói rằng X xác định Y hay Y phụ thuộc hàm vào X, kí hiệu X  Y nếu trên quan hệ R ta có mọi bộ giá trị t1, t2 bất kỳ mà giá trị của tập thuộc tính X trên bộ t1 (kí hiệu t1[X]) bằng giá trị của tập thuộc tính X trên bộ t2 (kí hiệu là t2[X]) thì t1[Y]) = t2[Y]). Phụ thuộc hàm ký hiệu là FD. Cần chú ý rằng chỉ xét các phụ thuộc hàm thỏa mãn cho mọi quan hệ trên lược đồ tương ứng của nó. Không thể xem xét một phụ thuộc hàm thỏa mãn một quan hệ r đặc biệt ( ví dụ quan hệ rỗng) của lược đồ R rồi sau đó qui nạp rằng phụ thuộc hàm đó là thỏa trên R. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 122 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU S (S# STATUS CITY) P (P# PNAME COLOR WEIGHT CITY) SP (S# P# QTY) Trong quan hệ S của hàng cung ứng, mỗi một trong số các thuộc tính SNAME, STATUS, CITY đều phụ thuộc hàm vào thuộc tính S#. Mỗi giá trị S# tồn tại vừa đúng một giá trị tương ứng đối với từng thuộc tính SNAME, STATUS, CITY. Khi đó có thể viết: S# → SNAME, S# → STATUS và S# → CITY. 3.1.2 Phụ thuộc hàm đầy đủ và không đầy đủ  Phụ thuộc hàm (FD) đầy đủ: Một FD X Y là một phụ thuộc hàm đầy đủ nếu loại bỏ bất kỳ thuộc tính A nào ra khỏi X thì FD không còn đúng nữa  Phụ thuộc hàm không đ  ầy đủ (FD bộ phận): Một FD X Y là phụ thuộc hàm bộ phận nếu có thể bỏ đi 1 thuộc tính A  X ra khỏi X mà FD vẫn còn đúng. 3.1.3 Hệ tiên đề Amstrong Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ R(U) và X→Y là một phụ thuộc hàm, X,Y⊆ U. Nói rằng X→Y được suy diễn logic từ F nếu mối quán hệ r trên R(U) đều thỏa các phụ thuộc hàm của F thì cũng thỏa X→Y. Chẳng hạn F= {A→B,B→C} thì A→C suy ra từ F. Gọi F+ là bao đóng (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 đủ( full family) của các phụ thuộc hàm. Để có thể xác định khóa của một lược đồ quan hệ và các suy diễn logic giữa các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có các hệ tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, thường được gọi là hệ tiên đề Armstrong. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 123 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU Gọi R(U) là lược đồ quan hệ với U= {A1, ….., An} là tập các thuộc tính. X,Y, Z, W ⊆ U. Hệ tiên đề Armstrong bao gồm :  A1(phản xạ): nếu Y⊆X thì X→Y  A2(tăng trưởng):nếu Z⊆U và X→Y thì XZ→YZ trong đó ký hiệu XZ là tập hợp của 2 tập X và Z thay cho ký hiệu X∪Z.  A3(bắc cầu): nếu X→Y và Y→Z thì X→Z Ví dụ : AB→C, C→A Cần chứng minh rằng BC→ABC Thật vậy từ : 1. C→A ( giả thiết) 2. BC→AB ( luật tăng trưởng (1) thêm B) 3. AB→C ( giả thiết) 4. AB→ABC ( tăng trưởng (3) thêm AB) 5. BC→ABC ( bắc cầu từ (2) và (4)) Định lý : Hệ tiên đề Armstrong là đúng. Có nghĩa là F là tập các phụ thuộc hàm đúng trên quan hệ r. nếu X→Y là một phụ thuộc hàm được suy diễn từ F nhờ hệ tiên đề Armstrong thì X→Y là đúng trên quan hệ r. Chứng minh : Lần lượt kiểm tra tính đúng đắn của ba tiên đề A1, A2, A3 A1 : Tiên đề A1 rõ ràng là đúng vì không thể có hai bộ bằng nhau trên X mà lại không bằng nhau trên tập con của nó. A2 : Giả sử rằng quan hệ r thỏa mãn X→Y. Tồn tại hai bột, u ∈r sao cho t[XZ] = u[ZX] mà t[YZ] ≠ u[YZ]. Vì rằng t[Z] = u[Z] nên để có t[YZ] ≠ u[YZ] thì t[Y] ≠ u[Y]. Nhưng vì t[X] = u[X] nên t[Y] ≠ u[Y] là trái với giả thiết X→Y. Vì vậy A2 đúng. KHOA CNTT – TRƯỜNG ĐẠI HỌC KINH TẾ KỸ THUẬT CÔNG NGHIỆP 124 TÀI LIỆU HỌC TẬP CƠ SỞ DỮ LIỆU A3 : Cho X→Y và Y→Z đúng trên quan hệ r. Giả sử tồn tại hai bộ t, u∈r sao cho t[Y] = u[Y]. Nhưng lại có t[Y] = u[Y] và t[Z] ≠ u[Z] là trái với giả thiết Y→Z. Do vậy t[Z] = u[Z]. Suy ra X→Z đúng trên quan hệ r. Từ hệ tiên đề Armstrong suy ra một số luật sau đây : Định lý : a. Luật hợp: nếu X→Y và X→Z thì X→YZ b. Luật tựa bắc cầu: nếu X→Y và WY→X thì XW→Z c. Luật tách: nếu X→Y và Z⊆Y thì X→Z Chứng minh: a. Từ X→Y dùng luật tăng trưởng thêm X có X→XY, dùng luật bắc cầu ta có điều phải chứng minh. b. Từ X→Y, dùng luật tăng trưởng, thêm W có WX→WY. Dùng luật bắc cầu cho WX→WY và Wy→Z suy ra WX→Z. ...