zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Cơ sở dữ liệu

ÔN TẬP CƠ SỞ DỮ LIỆU

Chia sẻ: Hoang Viet Anh | Ngày: | Loại File: DOC | Số trang:11

Báo xấu

318
lượt xem 92
download

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

= I. TÁCH LƯỢC ĐỒ QUAN HỆ VỀ DẠNG 3NF. Trước khi tách phải kiểm tra xem lược đồ đã cho ở dạng phủ tối thiểu hay chưa? BƯỚC 1:Thuật toán tìm phủ tối thiểu là: Phụ thuộc hàm tương đương: Cho hai tập phụ thuộc hàm F và G, F và G gọi là hai tập phụ thuộc hàm tương đương...

Chủ đề:

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

Lưu

Nội dung Text: ÔN TẬP CƠ SỞ DỮ LIỆU

Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ ÔN TẬP CƠ SỞ DỮ LIỆU I. TÁCH LƯỢC ĐỒ QUAN HỆ VỀ DẠNG 3NF. Trước khi tách phải kiểm tra xem lược đồ đã cho ở dạng phủ tối thiểu hay chưa? BƯỚC 1:Thuật toán tìm phủ tối thiểu là: Phụ thuộc hàm tương đương: Cho hai tập phụ thuộc hàm F và G, F và G gọi là hai tập phụ thuộc hàm tương đương hay F phủ G (G phủ F), nếu mọi phụ thuộc hàm của F đều thuộc G+ và mọi phụ thuộc hàm của G đều thuộc F+. Phủ tối thiểu: Cho tập phụ thuộc hàm F của quan hệ R. Phủ tối thiểu của F sẽ đồng thời thỏa mãn 2 điều kiện sau: 1.Vế phải của F chỉ chứa 1 thuộc tính. 2. Không chứa thuộc tính dư thừa ở vế trái. 3. Không chứa phụ thuộc hàm dư thừa. Thuật toán tìm phủ tối thiểu là: Bước 1: tách các phụ thuộc hàm dựa vào luật Tách sao cho Vế phải của các phụ thuộc hàm chỉ chứa 1 thuộc tính. Bước 2: Loại bỏ các thuộc tính dư thừa ở vế trái của các phụ thuộc hàm. Ở bước này ta chỉ xét các phụ thuộc hàm mà vế trái chứa từ hai thuộc tính trở lên(ví dụ:ab-->c). giả sử f:X-->Y thuộc vào tập phụ thuộc hàm F. B là tập con của X và B-->Y thuộc vào F+. Khi đó X:=B. Bước 3::Loại bỏ các phụ thuộc hàm dư thừa. giả sử f thuộc vào F, và G=F-f Mà G+=F+ thì f là 1 phụ thuộc hàm dư thừa và khi đó, ta loại bỏ f đi bằng cách gán F:=G. BƯỚC 2: loại bỏ tất cả các thuộc tính không liên quan đến bất kỳ phụ thuộc hàm nào của F BƯỚC 3: Nếu có một phụ thuộc hàm nào của F mà liên quan đến tất cả các thuộc tính của R thì kết quả chính là R BƯỚC 4: Phép tách các phụ thuộc hàm có dạng X-->A thành lược đồ con Ri(XA). Nếu X-->A1, X-->A2,....,X->An thuộc vào F thì thay XA=XA1A2A3....An. Chủ yếu là sử dụng bước đầu tiên, quan trọng nhất. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ Sau đây là 1 ví dụ: Bài 9: Tìm phủ tối thiểu của F. F={ MSCD-->CD CD-->MSCD; CD,MSSV-->HG; MSCD,HG--> MSSV; CD,HG--> MSSV; MSCD, MSSV-->HG; } ÁP DỤNG : BƯỚC 1: Tách tất cả các phụ thuộc hàm về dạng vế phải chỉ chứa 1 thuộc tính, theo bài ra thì bước này không cần làm nữa. BƯỚC 2: Loại bỏ các thuộc tính dư thừa ở vế phải các phụ thuộc hàm. - Ta chỉ xét các phụ thuộc hàm 3,4,5,6. - Xét phụ thuộc hàm CD,MSSV--> HG. + giả sử loại bỏ thuộc tính CD . tính MSSV+=MSSV không chứa HG nên thuộc tính CD là không dư thừa. + giả sử loại bỏ thuộc tính MSSV. tính CD+=CD,MSCD không chứa HG nên thuộc tính này cũng không dư thừa. - Xét phụ thuộc hàm MSCD,HG-->MSSV. + giả sử loại bỏ thuộc tính MSCD. tính HG+= HG ko chứa thuộc tính MSSV nên tt MSCD ko dư thừa. + giả sử loại bỏ thuộc tính HG. tính MSCD+=CD,MSCD ko chứa MSSV nên thuộc tính này ko dư thừa. - Xét tương tự cho các phụ thuộc hàm 5,6: ko có thuộc tính dư thừa. Vậy sau bước này, tập phụ thuộc hàm F vẫn giữ nguyên. BƯỚC 3: Loại bỏ các phụ thuộc hàm dư thừa. Ta phải xét từng phụ thuộc hàm. - Xét CD-->MSCD: Loại bỏ pth này ra khỏi F để tính CD+. CD+=CD khác U nên pth này ko dư thừa. -tương tự thì pth MSCD-->CD cũng ko dư thừa. - Xét pth CD,MSSV-->HG. Loại bỏ phụ thuộc hàm này ra khỏi F để tính (CD, MSSV)+ (CD, MSSV)+=CD,MSCD,MSSV,HG=U . Mặt khác ta có: ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ CD-->MSCD CD,MSSV-->MSCD,MSSV (Tăng trưởng) (giả thiết) MSCD,MSSV-->HG (Bắc cầu). CD,MSSV-->HG Vì vậy phụ thuộc hàm này dư thừa nên bị loại bỏ ra khỏi F. Khi đó: F={ MSCD-->CD CD-->MSCD; MSCD,HG--> MSSV; CD,HG--> MSSV; MSCD, MSSV-->HG; } -XÉT tương tự ta tìm được thêm 1 phụ thuộc hàm dư thừa là: MSCD,HG-->MSSV. Vậy phủ tối thiểu của F là: MSCD-->CD CD-->MSCD; CD,HG--> MSSV; MSCD, MSSV-->HG; II. CHUẨN HÓA LƯỢC ĐỒ QUAN HỆ VỀ DẠNG BCNF 1.Định nghĩa - Lược đồ quan hệ R(U) đạt dạng chuẩn BCNF nếu phụ thuộc hàm XA thỏa mãn A ko thuộc X và X là khóa. 2. Thuật toán -B1: Ban đầu phép tách chỉ có R. -B2: Cho lược đồ quan hệ R(U) với tập phụ thuộc hàm F. Nếu tồn tại 1 phụ thuộc hàm f:XA không là BCNF thì tách lược đồ quan hệ thành hai lược đồ con là: R1=XA và R2=U- {A}. Lúc này R1 đạt BCNF với khóa là X. Lặp lại b2 với lược đồ R2. Ở mỗi bước kiểm tra xem các lược đồ con đã đạt BCNF chưa. III. THUẬT TOÁN TÌM 1 KHÓA. Định nghĩa khóa: Cho lược đồ quan hệ R(U), với U là tập thuộc tính. K là tập con của U, K gọi là khóa nếu thỏa mãn hai điều kiện: KU thuộc vào F+ ( nếu K+=U thì K gọi là siêu khóa). và Không tồn tại K1 là con của K mà K1+=U. Cho lược đồ quan hệ R(U), với tập phụ thuộc hàm F. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ Bước 1: Gán K=U; Bước 2: Gán K=K-A nếu (K-A)+=U, A thuộc U. Bước 3: Lặp lại bước 3 cho đến khi không thể loại thêm được 1 phần tử nào nữa. Kết luận: K chính là khóa cần tìm. Chú ý: Thay đổi thứ tự loại các thuộc tính sẽ dẫn đến việc tìm được một khóa khác của lược đồ quan hệ. Chú ý: 1. Các thuộc tính chỉ nằm bên trái phụ thuộc hàm chắc chắn tham gia vào khóa. 2. Các thuộc tính chỉ nằm bên phải phụ thuộc hàm chắc chắn không tham gia vào khóa. 3. Các thuộc tính nằm ở hai bên phụ thuộc hàm có thể tham gia vào khóa hoặc không. Ví dụ: Bài 8: cho lược đồ quan hệ R(ABCD) F={ABC, DB, CABD } Bài làm: Bước 1: Gán K=ABCD; Bước 2: Gán K=ABCD- A=BCD Tính K+= (BCD)+= ABCD Do đó có thể loại được thuộc tính A. Bước 3: Gán K=BCD-B= CD Tính K+=(CD)+= ABCD Do đó có thể loại được thuộc tính B. Bước 4: Gán K=CD – C=D Tính K+=D+=DB #ABCD Do đó không thể loại được thuộc tính C. Bước 5: Gán K=CD-D=C. Tính K+=C+=ABCD. Do dó có thể loại được thuộc tính D. Vậy 1 khóa cả R(U) vừa tìm được là: C IV.THUẬT TOÁN TÌM NHIỀU KHÓA Cho lược đồ quan hệ R(U), với tập phụ thuộc hàm F. Bước 1: tìm tất cả các tập con của tập thuộc tính U khác tập rỗng. Giả sử U={A1A2A3..An} thì có 2^n -1 tập con của U khác rỗng. Đó là: X={X1,X2,X3,.., Xn} Bước 2: Tính Xi+. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ Bước 3: Nếu Xi+=U thì Xi gọi là siêu khóa. Giả sử tập các siêu khóa là S={S1,S2,…, Sk}. Bước 4: Từ tập các siêu khóa ta tìm tập các khóa như sau: Với mọi Si, Sj thuộc tập siêu khóa , i # j, i ,j=1,k. Nếu như Si là tập con của Sj thì loại Sj. Tập còn lại là tập các khóa. Ví dụ: Bài 13: Cho lược đồ quan hệ Q(ABCD) F={AD, DA, ABC} Tìm tất cả các khóa của Q. Bài làm: Xi Xi+ Siêu khóa Khóa A AD B B C C D AD AB ABCD AB AB AD AD AC ADC BD ABCD BD BD BC BC CD ACD ABC ABCD ABC ABD ABCD ABD ACD ACD BCD ABCD BCD ABC ABCD ABCD D Vậy khóa của lược đồ quan hệ Q là AB và BD. V.THUẬT TOÁN TÌM KHÓA CẢI TIẾN. 1.Định nghĩa Tập nguồn(TN): là tập tất cả các thuộc tính chỉ nằm ở bên trái phụ thuộc hàm hoặc không tham gia vào bất cứ phụ thuộc hàm nào. Tập trung gian(TG): là tập tất cả các thuộc tính nằm ở cả hai bên phụ thuộc hàm. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ Tập đích(TĐ): là tập tất cả các thuộc tính chỉ nằm bên phải phụ thuộc hàm. 2.Thuật toán Bước 1: Tìm tập trung gian. Bước 2: Nếu tập trung gian= Rỗng thì Khóa= tập nguồn. Nếu tập trung gian khác rỗng thì tìm tất cả các tập con của tập trung gian. Giả sử các tập con đó là: X1,X2,.. Xn. Bước 3: tính (Xi U TN). Tìm (Xi U TN)+? Bước 4: Nếu (Xi U TN)+= U thì Xi U TN là siêu khóa. Bước 5: Từ tập các siêu khóa ta tìm được tập các khóa như thuật toán trên. Ví dụ: bài 8 tìm khóa của Q(ABCD) F={AB C, D B, C ABD} TẬP NGUỒN: RỖNG TẬP TRUNG GIAN= ABCD Xi Xi U TN (Xi U TN)+ Siêu khóa Khóa O O O A A A B B B C C ABCD C C D D BD AB AB ABCD AB AB AC AC ABCD AC AD AD ABCD AD AD BC BC ABCD BC BD BD BD CD CD ABCD CD ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ ABC ABC ABCD ABC ABD ABD ABCD ABD ACD ACD ABCD ACD BCD BCD ABCD BCD ABC ABCD ABCD ABCD D Vậy Q có 3 khóa là: C, AB, AD. VI. THUẬT TOÁN TÌM BAO ĐÓNG CỦA TẬP THUỘC TÍNH. 1.Định nghĩa Bao đóng của tập phụ thuộc hàm: cho lược đồ quan hệ R(U) và tập phụ thuộc hàm F, bao đóng của tập phụ thuộc hàm F, ký hiệu F+, là tập tất cả các phụ thuộc hàm được suy rộng từ F theo hệ tiên đề Amstrong. Bao đóng của tập thuộc tính: cho X là tập con của tập thuộc tính U. Bao đóng của X, ký hiệu là X+, là tập tất cả các thuộc tính A sao cho phụ thuộc hàm XA có thể được suy diễn logic từ F nhờ hệ tiên đề Amstrong. X+={A|XA thuộc F+}. Bài toán thành viên: Cho R(U), tập phụ thuộc hàm F, xác định xem f: X Y có thuộc F+ hay không? BG: X Y thuộc F+ khi và chỉ khi Y thuộc X+. 2. Thuật toán tìm bao đóng của tập thuộc tính Input: R(U), F,X là tập con của U. Output: X+? Bước 1: gán X0=X; Bước 2: gán Xi+1=Xi U A nếu tồn tại tập thuộc tính Y là con của Xi mà YZ thuộc vào F+, A thuộc Z. Bước 3: Ta xây dựng được 1 dãy các tập thuộc tính Xn chứa Xi+1 chứa Xi.. chứa X1 chứa X0. Thuật toán dừng khi Xi=Xi+1. Ví dụ: bài 6a:cho R(ABCD), F={A D, D A, AB C} TÍNH AC+? ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ BG: Bước 1: X0=X=AC vì ACAC Bước 2: X1=X0 U D =ACD vì AD Bước 3: X2=X1 U A=ACD vì DA Do Xi+1=Xi nên dừng. Kết luận : AC+= ACD. *Các khái niệm cơ bản và hệ tiên đề Amstrong cho tập phụ thuộc hàm 1.Phụ thuộc hàm: Cho lược đồ quan hệ R(U), X,Y là tập con của U. Ta nói X xác định Y hay XY nếu r là một quan hệ của R và với mọii bộ t1, t2 bất kỳ sao cho t1[X]=t2[X] thì t1[Y]= t2[Y]. Hay: Không tồn tại các bộ giống nhau tại các thuộc tính của X mà khác nhau 1 hay nhiều thuộc tính của Y. 2. Hệ tiên đề Amstrong a- Phản xạ: nếu Y là tập con của X thì XY. b- Tăng trưởng: Nếu XY, Z là tập con của U thì XZYZ. c- Bắc cầu: Nếu XY, YZ thì XZ. 3.Bổ đề: a- Luật tách: XY và Z là tập con của Y thì XZ. b- Luật hợp: Nếu X Y và X Z thì X YZ. c- Luật tựa bắc cầu: Nếu XY và WY Z thì WXZ . VI. CÁC DẠNG CHUẨN CỦA LƯỢC ĐỒ QUAN HỆ. 1. DẠNG CHUẨN 1NF. Lược đồ quan hệ R(U) đạt 1NF nếu và chỉ nếu toàn bộ các miền có mặt trong lược đồ quan hệ chỉ chứa các giá trị nguyên tố. Chú ý: nếu không nói gì thêm thì lược đồ đã cho đạt chuẩn 1NF. 2. DẠNG CHUẨN 2NF. Lược đồ quan hệ R(U) đạt 2NF nếu và chỉ nếu R đạt 1NF và mọi thuộc tính không khóa phụ thuộc hàm đầy đủ vào khóa chính. Tức là: mọi thuộc tính không khóa không phụ thuộc vào tập con của khóa chính. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ Chú ý: -Tập thuộc tính không khóa = rỗng 2NF. - Khóa chỉ có 1 thuộc tính 2NF. Phụ thuộc hàm đầy đủ: Cho lược đồ quan hệ R(U), tập phụ thuộc hàm F,X,Y là tập con của U. Ta nói Yphụ thuộc hàm đầy đủ vào X hay XY là 1 phụ thuộc hàm đầy đủ nếu Y phụ thuộc vào X Và Y không phụ thuộc vào tập con của X. 3.DẠNG CHUẨN 3NF. R(U) đạt dạng chuẩn 3NF nếu R đạt 2NF và mọi thuộc tính không khóa không phụ thuộc hàm bắc cầu vào khóa chính. Chú ý:- tập thuộc tính không khóa = rỗng 3NF. BCNF 3NF. Phụ thuộc hàm bắc cầu: X là tập con của U, A là 1 thuộc tính của U. Ta nói A phụ thuộc hàm bắc cầu vào X nếu tồn tại 1 tập con Y của tập thuộc tính U, sao cho XY và YA, đồng thời Y!  X. 4.DẠNG CHUẨN BCNF R(U) đạt BCNF nếu XA thỏa trên R,nếu A không thuộc X và X là khóa của R. Chú ý: BCNF 3NF. 5. Tách lược đồ quan hệ. Cho lược đồ quan hệ R(U), R được tách thành các lược đồ Ri, i=1k; R=R1 U R2 U..U Rk. Các Ri không nhất thiết phải giống nhau. Bài tập: kiểm tra phép tách có kết nối không mất mát thông tin. Input: R(U), Ri, i=1,k Output: kiểm tra phép tách có kết nối không mất mát thông tin. Bước 1: Lập bảng hai chiều gồm n cột và k dòng tương ứng với n thuộc tính và k lược đồ con. Điền các giá trị của bảng như sau: Nếu Aj thuộc vào Ri thì điền aj, ngược lại điền bij vào dòng i, cột j. Bước 2:Áp dụng các phụ thuộc hàm lên bảng. Nếu XY thuộc vào F+ , bằng nhau tại X thì làm bằng nó tại Y. Nếu 1 trong các giá trị tại Y là aj thì ưu tiên làm bằng aj, ngược lại làm bằng 1 trong các bij. Áp dụng cho lần lượt các phụ thuộc hàm, kể cả các phụ thuộc hàm đã áp dụng rồi. Bước 3: nếu xuất hiện một bộ chứa đầy đủ các a1,a2, ..an thì kết luận phép tách có kết nối không mất mát thông tin. ________________________________________________________________________
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ 6. Tìm kiếm sử dụng ngôn ngữ SQL a. Tạo bảng CREATE_TABLE(danh_sách_thuộc_tính kiểu_dữ_liệu, ….) Xóa bảng DROP_TABLE Tên bảng Thêm dữ liệu INSERT INTO Tên bảng VALUE () b. Tìm kiếm Cấu trúc chung của 1 khối lệnh tìm kiếm là: SELECT[*/distinct] ds_thuộc_tính/ biểu thức. FROM ds_bảng. WHERE biểu _thức_điều_kiện GROUP BY ds_thuộc_tính HAVING biểu_thức_điều_kiện. ORDER BY thuộc_tính ASC/DESC. Trong đó: SELECT: xác định nội dung cần đưa ra kết quả. *: chọn tất cả các cột . Distinct: loại bớt các dòng dữ liệu trùng nhau. Biểu thức là sự kết hợp của các thuộc tính, toán tử, hàm gom nhóm như Min, Max, Avg, Count… FROM: Xác định các bảng cần lấy ra thông tin. WHERE: xác định điều kiện của việc truy xuất dữ liệu. Sau mệnh đề where là 1 biểu thức điều kiện, chỉ những bộ nào thỏa mãn điều kiện thì mới xuất hiện trong bảng kết quả. Trong mệnh đề Where thường sử dụng: - Toán tử so sánh: >,=,
Hoàng Hà-TINK6 TOLIVEISTOFIGHT! ________________________________________________________________________ HAVING: mệnh đề Having là mệnh đề đặt điều kiện lên các nhóm dữ liệu, Điểm khác biệt của Where và having là mệnh đề where ko cho phép sử dụng hàm nhóm thì mệnh đề Having lại cho phép dùng hàm nhóm trong các điều kiện của mình. Các hàm nhóm thường dùng là: SUM(biểu thức ): tính tổng các giá trị. AVG(biểu thức): tính trung bình cộng các giá trị. COUNT(biểu thức): đếm số các giá trị trong biểu thức. COUNT(*): đếm số các bộ được chọn. MAX(biểu thức): tính giá trị lớn nhất. MIN(biểu thức): tính giá trị nhỏ nhất. Chú ý: - Các hàm sum, avg chỉ làm việc với các biểu thức số. - hàm count(*) không bỏ qua giá trị null khi tính toán. ORDER BY : sắp xếp kết quả truy vấn theo 1 trường nào đó tăng dần hoặc giảm dần. Sau order by là danh sách các cột cần sắp xếp, tăng dùng ASC, giảm dùng DESC.Mặc định là sắp xếp theo chiều tăng. ________________________________________________________________________

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.