Bài tập về đại số quan hệ

1. BµI TËP VÒ ĐẠI SỐ QUAN HỆ MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC Phân biệt các phép toán trên quan hệ, các tính chất của đại số quan hệ. Kết hợp các phép toán để giải quyết các yêu cầu cụ thể. A/ NHẮC LẠI LÝ THUYẾT I. CÁC CÔNG THỨC QUAN TRỌNG Phép hợp: Cho hai quan hệ R và S có cùng tập thuộc tính là U, Khi đó hợp của hai quan hệ R và S, kí hiệu là R+S, đó cũng là một quan hệ có tập thuộc tính là U, và được xác định như sau: R+S={ t | t Î R hoặc tÎ S} Phép giao: Cho 2 quan hệ R và S, có cùng tập thuộc tính U, giao của 2 quan hệ R và S, kí hiệu là R.S, là một quan hệ trên tập thuộc tính U và chỉ gồm tất cả các bộ t vừa thuộc R vừa thuộc S, tức là: R.S={ t | tÎ R và t Î S } Phép hiệu: Cho R và S là 2 quan hệ trên tập thuộc tính U, hiệu hai quan hệ R và S, kí hiệu là R\S, là một quan hệ trên tập thuộc tính U, và được xác định như sau: R-S= { t | tÎ R và t Ï S} Phép chọn: Cho quan hệ R trên tập thuộc tính U và E là biểu thức chọn trên tập thuộc tính U, phép chọn quan hệ R theo biểu thức chọn E đựơc kí hiệu là R(E), đó là một quan hệ trên tập thuộc tính U, và được xác định như sau: R(E)= { t | t Î R và t(E) } Phép chiếu: Cho quan hệ R trên tập thuộc tính U, f¹XÍU là một tập con các thuộc tính của U, phép chiếu của quan hệ R lên tập thuộc tính X, được kí hiệu là R[X], đó là một quan hệ trên tập thuộc tính X, và được xác định như sau: R[X] = { t.X | t Î R} Phép chia: Cho lược đồ quan hệ R={A1, A2,…, An}. Cho quan hệ R(U), và S(V), với Æ ¹ V Í U, đặt X = U\V. Phép chia quan hệ R cho quan hệ S, ký hiệu là R ¸ S là một quan hệ trên tập thuộc tính X và được xác định: R ÷ S ={ t.X\ t Î và " V Î S và Î R} Trong định nghĩa trên chú ý rằng ký hiệu là sự ghép vào đúng vị trí của hai xâu t và u. Phép kết nối q - Sau đây ta sẽ xét phép kết nối theo toán tử q, với q là một toán tử so sánh số học 2 ngôi (=, , ≤, ≥, ≠). - Cho A Í U, B Í V là các thuộc tính, t1, t2 lần lượt là 2 bộ trên U và V. Khi đó, t1, t2 có thể kết nối với nhau nếu t1.A q t2.B, ký hiệu là t= là kết quả kết nối của t1, t2. Định nghĩa: Cho 2 quan hệ R(U) và S(V) l tương ứng trên các lược đồ rời nhau R và S tức R Ç S = Æ. q là phép so sánh, A Î U, B Î S . Phép kết nối quan hệ R và S theo điều kiện A q B được ký hiệu là: R = A q B = { t\ $ t1 Î R, t2 Î S, t =, sao cho t1.A q t2.B } */ Phép kết nối tự nhiên Định nghĩa: Cho 2 quan hệ R(U), S(V), đặt X= U Ç V, phép kết nối tự nhiên của quan hệ R và S, ký hiệu là R* S, được xác định như sau: R*S = { t\ $ t1 Î R, t2 Î S để t1.X = t2.X} */ Phép kết nối một nửa Với giả tihết như trên với R(U), S(V). Ta có phép kết nối nửa sau: R S = { t\ t Î (R S) [U]} II. CÁC VÍ DỤ Ví dụ 1: Đây là phép chiếu trên quan hệ R R A B C D R[AC] A C a1 b3 c1 d1 a1 c1 a2 b2 c1 d3 a2 c1 a1 b1 c1 d2 a3 c2 a3 b1 c2 d5 a1 b3 c1 d6 Ví dụ 2: Đây là phép kết nối trên 2 quan hệ Giả sử r và s là các quan hệ như sau: r A B C s D E 1 2 3 3 1 4 5 6 6 2 7 8 9 Khi đó, ta có r 2<1 s A B C D E 1 2 3 3 1 1 2 3 6 2 4 5 6 6 2 Ví dụ 3: Đây là phép kết nối trên 2 quan hệ Cho hai quan hệ R và S như sau: R A B C S C D a1 1 c1 c1 4 a2 2 c1 c1 3 a1 3 c1 c2 2 a3 4 c2 c2 1 Phép so sánh là B > D khi đó R S A B C C D a2 2 c1 c2 1 a1 3 c1 c2 2 a1 3 c1 c2 1 a3 4 c2 c1 3 a3 4 c2 c2 2 a3 4 c2 c2 1 Ví dụ 4: Đây là phép kết nối nửa trên 2 quan hệ r A B C s C D a b c b c d d b c b c e b b f a d b c a d Khi đó ta có: r s A B C a b c d b c c a d III. MỘT SỐ LƯU Ý Khi bài toán cần sử dụng nhiều phép toán cần phải kết hợp các phép toán sao cho hạn chế dung lượng nhớ cho các kết quả trung gian. Khi bài toán có sử dụng các phép toán chiếu, chọn, kết nối nên thực hiện phép toán chiếu, chọn xuống dưới nhất (Gốc của cây đại số quan hệ) có thể được. B/ BÀI TẬP MẪU Bài số 1: Ví dụ về phép chọn trên quan hệ SV. Xét hồ sơ kết quả thi của sinh viên. Quan hệ này gọi là SV. Giả sử ta có quan hệ SV như sau: TT Hoten namsinh CSDL FOX 1 Tuấn Anh 1983 7 5 2 Huy Công 1982 8 3 3 Thanh Hương 1984 8 9 4 Bình Minh 1986 2 3 Giả sử, điều kiện E là sinh viên có ít nhất một điểm kém. Vậy SV(E), E = ( CSDL < 5 v Fox < 5). Khi đó kết quả SV(CSDL < 5 v Fox < 5): TT Hoten namsinh CSDL FOX 2 Huy Công 1982 8 3 4 Bình Minh 1986 2 3 Bài số 2: Cho CSDL gồm có ba quan hệ như sau: NCC(MaNCC, TenNCC, DCNCC, DT) SP(MaSP, TenSP, Loai) SP_NCC(MaNCC, MaSP, SL) Giải thích một số từ viết tắt: MaNCC là mã số nhà cung cấp TenNCC là tên nhà cung cấp có mã số tương ứng DCNCC là địa chỉ của nhà cung cấp DT là điện thoại nhà cung cấp MaSP là mã số sản phẩm TenSP là tên của sản phẩm Loại là chủng loại của mặt hàng SL là số lượng đã cung cấp Quan hệ NCC ( nhà cung cấp ) dùng để lưu trữ một số thông tin về các nhà cung cấp Quan hệ SP ( sản phẩm ) dùng để lưu trữ một số thông tin của các mặt hàng Quan hệ SP_NCC dùng để lưu trữ một số thông tin về việc cung ứng sản phẩm của NCC Hãy viết biểu thức đại số quan hệ cho biết Cho biết tên của nhà cung cấp có địa chỉ là Hà Nôi Cho biết tên của các sản phẩm đã cung ứng bởi nhà cung cấp có mã số là HP. Hướng dẫn : - Với câu a) Ta cần chiếu để lấy tên nhà cung cấp kết hợp với phép chọn với điều kiện chọn là 'Hà nội', các thông tin này lấy trong quan hệ NCC, ta thực hiện như sau: NCC(DCNCC='Hà nội')[TenNCC] - Với câu b) Các thông tin lấy trong 2 quan hệ là SP và SP_NCC, với yêu cầu này cần thực hiện 3 phép toán là kết nối, chọn, chiếu. Có thể 2 cách để thực hiện yêu cầu này: +/ C1: Thực hiện phép toán kết nối 2 quan hệ SP, SP_NCC, phép chọn, phép chiếu. (SP * SP_NCC) (MaNCC = ‘HP’)[TenSP] +/ C2: Thực hiện phép chọn trên quan hệ SP_NCC, sau đó thực hiện phép kết nối giữa 2 quan hệ kết quả trên với quan hệ trung gian, cuối cùng là chiếu lấy tên các sản phẩm thoả mãn trên quan hệ cừa thu được. (SP - NCC(MaNCC=’HP’) * SP)[TenSP] C/ BÀI TẬP TỰ GIẢI Bài số 1: Cho 2 quan R và S như sau: R S A B C D A B C D 1 0 0 0 2 1 1 1 1 1 0 0 2 2 1 1 1 1 1 0 1 1 1 0 1 1 1 1 x y z v a. Tính R-S và S-S b. Tính R+S c. Tính R*S d. Giả sử X = {A, B, C}, Y={A, C, D}. tính các quan hệ chiếu r.X, r.Y và s.Y, (r+s).X, (r+s).(XUY) e. Chứng minh rằng với mọi quan hệ R, S, Q thì ta luôn có: R*S=S*R và R+S = S+R (Tính giao hoán) R*(Q+S) = (R*Q)+ (R*S) (Tính kết hợp) (R+S).X = R.X + S.X (R*S).X = R.X*S.X Bài số 2: Cho 2 quan hệ R và S như sau: R S A B C D A B C D 0 0 0 0 a b c d 0 0 1 1 x y z v 0 1 1 1 Tính R*S Bài số 3 Cho 2 quan hệ R và S như sau: R S A B C D E A B 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 Tính (R S) q ( 0>1) Bài số 4 Cho 2 quan r và s như sau: r s TT Tên NS GT Quê NH Điểm vào 1 Linh 77 Nữ HN Anh 18 2 Quyên 76 Nữ HF Hoá 20 3 Nam 75 Nam SG Toán 22 4 Tuấn 74 Nam VF Tin học 22 Hãy dùng các thủ thuật nhỏ và sử dụng các phép toán quan hệ để có kết quả DS như sau: DS TT Tên NS GT Quê NH Điểm vào 1 Linh 77 Nữ HN Anh 18 2 Quyên 76 Nữ HF Hoá 20 3 Nam 75 Nam SG Toán 22 4 Tuấn 74 Nam VF Tin học 22 Bài số 5 Cho cơ sở dữ liệu gồm 3 quan hệ SV(MSV, HT, NS, QUE) ĐT(MĐT, TĐT, GV, KP) TT(MSV, MĐT, NTT, KQ) Trong đó : MSV : Mã sinh viên HT : Họ tên sinh viên NS : Năm sinh QUE : Quê quán MĐT : Mã đề tài TĐT : Tên đề tài GV : Giáo viên KP : Kinh phí NTT : Nơi thực tập KQ : Kết quả Hãy trả lời các câu hỏi sau dưới dạng biểu thức quan hệ : a. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Hà nội và có kết quả thực tập khá ( KQ ( 7) b. Cho biết tên của các sinh viên có kết quả thực tập khá và thực tập tại quê hoặc thực tập tại Quảng ninh. c. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Hà nội và thực tập đề tài có kinh phí lơn hơn 5 triệu d. Cho biết tên của các sinh viên có kết quả thực tập khá và thực tập đề tài có kinh phí lớn hơn 4 triệu. e. Danh sach sinh viên thực tập tại quê nhà f. Thông tin về các đề tài có sinh viên thực tập g. Cho biết mã của các đề tài không có sinh viên nào tham gia h. Cho biết mã của các đề tài có kinh phí nằm trong khoảng 1.5 đến 2 triệu i. Cho biết mã của sinh viên có tuổi nhỏ hơn 20 và kết qủa thực tập là khá ( KQ>7)