Bài giảng Cơ sở dữ liệu và quản trị cơ sở dữ liệu: Chương 5 - ThS. Nguyễn Vương Thịnh

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:45

Thêm vào BST

Báo xấu

9
lượt xem 6
download

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

Bài giảng Cơ sở dữ liệu và quản trị cơ sở dữ liệu: Chương 5 Lý thuyết về phụ thuộc hàm, được biên soạn gồm các nội dung chính sau: Phụ thuộc hàm và hệ tiên đề armstrong; Bao đóng của tập phụ thuộc hàm; Bao đóng của tập thuộc tính; Phủ tối thiểu của tập phụ thuộc hàm; Khóa của lược đồ quan hệ. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng Cơ sở dữ liệu và quản trị cơ sở dữ liệu: Chương 5 - ThS. Nguyễn Vương Thịnh

TRƯỜNG ĐẠI HỌC HÀNG HẢI VIỆT NAM KHOA CÔNG NGHỆ THÔNG TIN BÀI GIẢNG HỌC PHẦN CƠ SỞ DỮ LIỆU VÀ QUẢN TRỊ CƠ SỞ DỮ LIỆU Chương 5 LÝ THUYẾT VỀ PHỤ THUỘC HÀM Giảng viên: ThS. Nguyễn Vương Thịnh Bộ môn: Hệ thống thông tin Hải Phòng, 2016
Thông tin về giảng viên Họ và tên Nguyễn Vương Thịnh Đơn vị công tác Bộ môn Hệ thống thông tin – Khoa Công nghệ thông tin Học vị Thạc sỹ Chuyên ngành Hệ thống thông tin Cơ sở đào tạo Trường Đại học Công nghệ - Đại học Quốc Gia Hà Nội Năm tốt nghiệp 2012 Điện thoại 0983283791 Email thinhnv@vimaru.edu.vn Website http://scholar.vimaru.edu.vn/thinhnv 2
Thông tin về học phần Tên học phần Cơ sở dữ liệu và quản trị cơ sở dữ liệu Tên tiếng Anh Database and Database Management Mã học phần 17425 Số tín chỉ 04 tín chỉ (LT: 45 tiết, TH: 30 tiết) Bộ môn phụ trách Hệ thống thông tin PHƯƠNG PHÁP HỌC TẬP, NGHIÊN CỨU  Nghe giảng, thảo luận, trao đổi với giảng viên trên lớp.  Tự nghiên cứu tài liệu và làm bài tập ở nhà. PHƯƠNG PHÁP ĐÁNH GIÁ  SV phải tham dự ít nhất 75% thời gian.  Có 02 bài kiểm tra viết giữa học phần (X2 = (L1 + L2)/2), 01 bài kiểm tra thực hành (X3). Điểm quá trình X = (X2 + X3)/2.  Thi kết thúc học phần bằng hình thức trắc nghiệm khách quan 3 trên máy tính (Z = 0.5X + 0.5Y).
Tài liệu tham khảo 1. Elmasri, Navathe, Somayajulu, Gupta, Fundamentals of Database Systems (the 4th Edition), Pearson Education Inc, 2004. 2. Nguyễn Tuệ, Giáo trình Nhập môn Hệ Cơ sở dữ liệu, Nhà xuất bản Giáo dục Việt Nam, 2007. 3. Nguyễn Kim Anh, Nguyên lý của các hệ Cơ sở dữ liệu, Nhà xuất bản Đại học Quốc gia Hà Nội, 2004. 4
Tài liệu tham khảo 5
LÝ THUYẾT VỀ PHỤ THUỘC HÀM 5.1. PHỤ THUỘC HÀM VÀ HỆ TIÊN ĐỀ ARMSTRONG 5.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 5.3. BAO ĐÓNG CỦA TẬP THUỘC TÍNH 5.4. PHỦ TỐI THIỂU CỦA TẬP PHỤ THUỘC HÀM 5.6. KHÓA CỦA LƯỢC ĐỒ QUAN HỆ 6
Giáo sư William Ward Armstrong Đại học Montreal, Canada 7
5.1.1. ĐỊNH NGHĨA PHỤ THUỘC HÀM Ví dụ: Xét quan hệ trên lược đồ quan hệ Đặt Hàng Đơn vị Số Ngày Mã KH Tên KH Số CMND Điện Thoại Mã MH Tên MH Đơn Giá tính Lượng Đặt KH01 An 031275568 0988812322 MH01 USB 32G Chiếc 25$ 30 11/6 KH02 Bình 031254678 0912345678 MH02 Ốp lưng Chiếc 10$ 100 20/7 KH01 An 031275568 0988812322 MH02 Ốp lưng Chiếc 20$ 50 28/7 KH03 Cường 031255566 0987654323 MH01 USB 32G Chiếc 25$ 25 29/7 KH02 Bình 031254678 0912345678 MH03 Thẻ 16G Chiếc 15$ 20 01/8 KH03 Cường 031255566 0987654323 MH03 Thẻ 16G Chiếc 15$ 55 09/10 Mã KH quyết định Tên KH, Số CMND, Điện Thoại Ký hiệu: Mã KH → Tên KH, Số CMND, Điện Thoại Số CMND quyết định Mã KH, Tên KH, Điện Thoại Ký hiệu: Số CMND → Mã KH, Tên KH, Điện Thoại Phụ thuộc hàm Mã MH quyết định Tên MH, Đơn Vị Tính, Đơn Giá Ký hiệu: Mã MH → Tên MH, Đơn Vị Tính, Đơn Giá Mã KH, Mã MH quyết định Số Lượng, Ngày Đặt 8 Ký hiệu: Mã KH, Mã MH → Số Lượng, Ngày Đặt
Cho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y  Ω. Ta nói X quyết định Y hay Y phụ thuộc hàm vào X (ký hiệu: X→Y) khi và chỉ khi với mọi quan hệ r trên R(Ω) và với 02 bộ t1, t2 bất kỳ thuộc r ta luôn có: Nếu t1[X] = t2[X] thì t1[Y] = t2[Y] Lưu ý: + Phụ thuộc hàm X →  đúng với mọi quan hệ r + Phụ thuộc hàm  → Y đúng với quan hệ r có cùng giá trị trên Y X Y A B C Viết X → Y có nghĩa là: a2 b2 c2 Cứ mang giá trị giống a1 b1 c1 nhau trên X thì phải a2 b2 c2 a1 b1 c1 mang giá trị giống nhau a2 b2 c2 trên Y a1 b1 c1 9
5.1.2. HỆ TIÊN ĐỀ ARMSTRONG Cho lược đồ quan hệ R(Ω) và các tập thuộc tính X, Y, Z, W  Ω 5.1.2.1. LUẬT PHẢN XẠ: Nếu Y  X thì X → Y 5.1.2.2. LUẬT TĂNG TRƯỞNG: Nếu X → Y thì XZ → YZ 5.1.2.3. LUẬT BẮC CẦU: Nếu X → Y và Y → Z thì X → Z Được công bố bởi William Ward Armstrong vào năm 1974 10
5.2.1. BAO ĐÓNG LOGIC CỦA TẬP PHỤ THUỘC HÀM 5.2.1.1. Phụ thuộc hàm được suy dẫn logic từ tập phụ thuộc hàm F Phụ thuộc hàm X → Y được gọi là suy dẫn logic từ tập phụ thuộc hàm F nếu như mọi quan hệ r thỏa mãn tất cả các phụ thuộc hàm trong tập phụ thuộc hàm F thì cũng thỏa mãn phụ thuộc hàm X → Y. Ký hiệu: ⊢ → 5.2.1.2. Bao đóng logic của tập phụ thuộc hàm F Tập tất cả các phụ thuộc hàm có thể suy dẫn logic từ tập phụ thuộc hàm F được gọi là bao đóng logic của F. Ký hiệu là F*. ∗ = ⟶ | ⊢ ⟶ 11
5.2.2. BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM 5.2.2.1. Phụ thuộc hàm suy dẫn được từ tập phụ thuộc hàm F nhờ hệ tiên đề Armstrong Phụ thuộc hàm X → Y được gọi là suy dẫn được từ tập phụ thuộc hàm F nhờ hệ tiên đề Amrstrong nếu như ta có thể suy dẫn ra phụ thuộc hàm này từ các phụ thuộc hàm trong F bằng cách áp dụng liên tiếp các luật của hệ tiên đề Armstrong. Ký hiệu: ⊨ → 5.2.2.2. Bao đóng của tập phụ thuộc hàm F Tập tất cả các phụ thuộc hàm có thể suy dẫn ra từ tập phụ thuộc hàm F nhờ áp dụng các luật cùa hệ tiên đề Armstrong được gọi là bao đóng (closure) của F. Ký hiệu là F+. = ⟶ | ⊨ ⟶ 12
5.2.2.3. Tính chất của bao đóng của tập phụ thuộc hàm A. Tính phản xạ: F  F+ B. Tính đơn điệu: Nếu F  G thì F+  G+ C. Tính bao phủ: Nếu F  G+ thì F+  G+ D. Tính lũy đẳng: (F+)+ = F+ 13
5.2.3. HỆ TIÊN ĐỀ ARMSTRONG LÀ ĐÚNG VÀ ĐẦY ĐỦ A. Hệ tiên đề Armstrong là đúng: Từ tập phụ thuộc hàm F ban đầu, hệ tiên đề Armstrong chỉ có thể sinh ra các phụ thuộc hàm nằm trong F* ∗ ⊆ B. Hệ tiên đề Armstrong là đầy đủ: Từ tập phụ thuộc hàm F ban đầu, hệ tiên đề Armstrong có thể sinh ra được tất cả các phụ thuộc hàm của F* ∗ ⊆ Vậy nên: Kể từ giờ trở đi ta không phân biệt F* ∗ ≡ hay F+ nữa mà chỉ dùng một khái niệm 14 bao đóng F+
5.3.1. KHÁI NIỆM 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+ được định ngĩa như sau: =∪ với → ∈ . 5.3.2. THUẬT TOÁN TÌM BAO ĐÓNG CỦA TẬP THUỘC TÍNH Xác định liên tiếp các tập thuộc tính X0, X1, X2,... Bước 1: X0 = X Bước 2: Lần lượt xét các phụ thuộc hàm trong F. Nếu có phụ thuộc hàm Y → Z nào đó có Y  Xi thì Xi+1 = Xi  Z. Sau đó loại phụ thuộc hàm Y → Z ra khỏi tập phụ hàm F. Bước 3: Nếu tại bước 2 không tìm được thêm Xi+1 thì Xi là bao đóng của X. Ngược lại, tiếp tục lặp lại bước 2. 15
Ví dụ: Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và tập phụ thuộc hàm: F = {B → A, DA → CE, D → H, GH → C, AC → D} Tìm bao đóng của X = AC. Giải: Bước 1: Xo = AC Bước 2: Duyệt các phụ thuộc hàm trong F: - Có AC → D nên X1 = Xo  {D} = ACD và loại AC → D khỏi F Lặp lại bước 2: Duyệt các phụ thuộc hàm còn lại trong F: - Có DA → CE nên X2 = X1  {CE} = ACDE và loại DA → CE ra khỏi F - Có D → H nên X3 = X2  {H} = ACDEH và loại D → H ra khỏi F. Lặp lại bước 2: Từ các phụ thuộc hàm còn lại F = {B → A, GH → C} không thể sinh thêm X4 từ X3 Bước 3: Thuật toán kết thúc. Bao đóng là X+ = X3 = ACDEH. 16
5.3.3. TÍNH CHẤT CỦA BAO ĐÓNG CỦA TẬP THUỘC TÍNH A. Tính phản xạ: X  X+ B. Tính đơn điệu: Nếu X  Y thì X+  Y+ C. Tính lũy đẳng: (X+)+ = X+ D. Các tính chất khác: X+Y+  (XY)+ (X+Y)+ = (XY+)+ = (X+ Y+)+ X → Y  Y+  X+ X → X+ và X+ → X X+ = Y+  X → Y và Y → X 17
5.3.4. ĐỊNH LÝ BÀI TOÁN THÀNH VIÊN → ∈ ⟺ ⊆ Chứng minh định lý Chứng minh ⊆ ⟹ → ∈ Với mọi thuộc tính Ai ∈ Y: Vì Y ⊆ X+ nên Ai ∈ X+. Theo định nghĩa bao đóng tập thuộc tính nếu Ai ∈ X+ thì X → Ai ∈ F+. Áp dụng luật hợp thì → ⋃ ∈ hay → ∈ Chứng minh → ∈ ⟹ ⊆ Xét → ∈ : Áp dụng luật phân rã thì với mọi thuộc tính Ai ∈ Y ta luôn có X → Ai ∈ F+. Theo định nghĩa bao đóng tập thuộc tính nếu X → Ai ∈ F+ thì Ai ∈ X+. Mà mọi phần tử Ai ∈ Y đều thuộc X+ nên Y ⊆ X+ 18
Ví dụ 5.1: Cho lược đồ quan hệ R(A,B,C,D,E,G,H) và tập phụ thuộc hàm: F = {B → A, DA → CE, D → H, GH → C, AC → D} Chứng minh rằng phụ thuộc hàm AC → EH có thể suy diễn ra từ các phụ hàm trong F. Giải Cách 1: Chỉ ra một cách suy diễn có thể: → ⇒ → (Luật bắc cầu) → → ⟹ → (Luật tăng trưởng 2 vế - thêm A) → ⇒ → ⟹ → (Luật bắc cầu và luật phân rã) → → ⇒ → (Luật hợp) (đpcm) → Cách 2: Dùng định lý bài toán thành viên: Tính bao đóng vế trái: (AC)+ = ACDEH. Vì vế phải EH ⊆ ACDEH nên phụ thuộc hàm AC → EH ∈ F+ hay có thể suy diễn ra từ F (đpcm). 19
5.3.5. TÌM BAO ĐÓNG CỦA TẬP PHỤ THUỘC HÀM DỰA TRÊN BAO ĐÓNG CỦA TẬP THUỘC TÍNH Cho lược đồ quan hệ R(Ω) và tập phụ thuộc hàm F Thuật toán tìm F+ Bước 1: Tìm tất cả các tập thuộc tính là tập con thực sự của Ω. Bước 2: Tìm bao đóng của từng tập thuộc tính con của Ω tìm được ở bước 1. Bước 3: Dựa vào các bao đóng của các tập thuộc tính con tìm được ở bước 2 để suy ra các phụ thuộc hàm trong F+. 20