Bài giảng Cơ sở dữ liệu - Bài 4: Đại số quan hệ - Vũ Văn Định

Bài 4. Đại số quan hệ I. Đại số quan hệ Đại số quan hệ là cơ sở của một ngôn ngữ bậc cao để thao tác trên các quan hệ. Đại số quan hệ gồm 8 phép toán cơ bản. Bằng các phép toán này, ta có thể trích dữ liệu từ một hay nhiều quan hệ để tạo ra các quan hệ mới. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí II. Các phép toán lý thuyết tập hợp -Gọi r là quan hệ trên tập thuộc tính R={A1, ..,An}. Giả thiết rằng r là tập hữu hạn các bộ. - Khái niệm khả hợp : Hai lược đồ quan hệ R1 và R2 được goị là khả hợp nếu có cùng bậc n và DOM(Ai) = DOM(Bi) (1in) - Cho hai quan hệ R1=(A1,A2,..An) và R2=(B1,B2,..,Bn) là hai quan hệ khả hợp, ta có định nghĩa: TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 1.Phép hợp Hợp của hai quan hệ r và s khả hợp, kí hiệu là r  s là tập các bộ thuộc r hoặc s hoặc thuộc cả hai quan hệ. Biểu diễn hình thức: r  s = { t/ t  r hoặc t  s hoặc t  r và s } Ví dụ : r ( A B C) s ( A B C) r  s = ( A B C) ___________ __________ _________________ a1 b1 c1 a1 b1 c1 a1 b1 c1 a2 b1 c2 a2 b2 c2 a2 b1 c2 a2 b2 c1 a2 b2 c2 a2 b2 c1 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Phép giao Giao của hai quan hệ r và s khả hợp, kí hiệu là r  s là tập các bộ thuộc cả quan hệ r và s . Biểu diễn hình thức : r  s = { t/ t  r và t  s } Ví dụ : Với hai quan hệ ở ví dụ trên, giao của chúng là: r  s = ( A B C ) a1 b1 c1 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3. Phép trừ Hiệu của hai quan hệ r và s khả hợp, kí hiệu là r - s là tập các bộ thuộc r nhưng không thuộc s . Biểu diễn hình thức : r - s = { t/ t  r và t  s } Ví dụ : Cũng với ví dụ trên, hiệu của chúng là: r - s = ( A B C ) a2 b1 c2 a2 b2 c1 Chú ý : phép giao của hai quan hệ có thể biểu diễn qua phép trừ: r  s = r- ( r - s ) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 4. Tích Đề -Các - Gọi r là quan hệ xác định trên tập thuộc tính { A1, A2,..,An} và s là quan hệ xác định trên tập thuộc tính { B1, B2,..,Bm} . Tích Đề - Các r x s của r và s là tập ( n + m ) - bộ với n thành phần đầu có dạng một bộ thuộc r và m thành phần sau có dạng của một bộ thuộc s. - Biểu diễn hình thức : r x s = { t/ t có dạng (a1, a2, .., an, b1, b2,..,bm) trong đó ( a1, ..,an ) r và (b1,.. ,bm)  s } - Ví dụ : r ( A B C) s ( D E F) r x s = ( A B C D E F) a1 b1 c1 d e f a1 b1 c1 d e f a2 b2 c2 d1 e1 f 1 a1 b1 c1 d1 e1 f1 a2 b2 c2 d e f a2 b2 c2 d1 e1 f1 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 5. Phép chiếu Phép chiếu trên một quan hệ thực chất là loại bỏ đi một số thuộc tính và giữ lại những thuộc tính còn lại của quan hệ đó. Dạng tổng quát :  (< tên quan hệ >)   là kí hiệu phép chiếu.  : danh sách các thuộc tính được lấy ra  Nếu chỉ có những thuộc tính không khoá thì phép chiếu sẽ tự bỏ đi những bộ lặp. Phép chiếu không có tính giao hoán. Nếu  thì ( (R)) = (R) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Cho quan hệ SV ( Mã SV, Họ tên, Ngày sinh, điểm) như sau : 10004 7003 9002 8001 ĐiểmMã SV Thì phép chiếu Mã Sv, Điểm (SV) sẽ cho ta một quan hệ mới chỉ gồm hai thuộc tính là Mã SV và Điểm . 1021/6/85Hồng Vân004 725/3/87Xuân Mai003 913/4/85Ngọc Bích002 823/4/86Trần Anh001 ĐiểmNgày sinhHọ tênMã SV DIEM( Mã SV, Điểm ) : TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 6. Phép chọn Phép chọn dùng để trích chọn một tập con trong một quan hệ, các bộ được trích chọn phải thoả mãn điều kiện chọn. ( Phép chọn trích ra các hàng trong quan hệ) Dạng tổng quát :  ()   là kí hiệu phép chọn. Kết quả thu được từ phép chọn là một quan hệ có danh sách thuộc tính được chỉ ra trong Tên quan hệ Điều kiện : là các biểu thức điều kiện cần thoả mãn.. Các biểu thức này được nối với nhau bằng các phép: ( phủ định ),  (giao),  (hợp) Phép chọn có tính giao hoán. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 7. Phép kết nối  Phép kết nối : Dùng để kết hợp hai bộ có liên quan từ hai quan hệ thành một bộ. Trước hết ta làm quen với khái niệm xếp cạnh nhau: Cho bộ d =( d1, d2,..,dm) và bộ e= (e1, e2,.., em). Phép xếp cạnh nhau được định nghĩa qua : d  e = ( d1, d2,.., dm,e1, e2,..,em). TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Gọi  là một trong các phép so sánh . Phép kết nội được định nghĩa: Phép kết nối của quan hệ r đối với thuộc tính A với quan hệ s đối với thuộc tính B được định nghĩa qua. r  s = { (t  u ) | t  r và u  s và t[A]  u[B] } A  B TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Kết quả của phép kết nối là một quan hệ Q có ( n+m) thuộc tính, mỗi bộ trong Q thoả mãn điều kiện kết nối.  Các bộ có giá trị rỗng tại thuộc tính kết nối thì không xuất hiện trong kết quả của phép kết.  Bản chất của phép kết nối là phép lấy tích Đề - Các của hai quan hệ và chọn ra các bộ thoả mãn điều kiện kết. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : r ( A B C ) s( C D E ) r  s = ( A B C C D E) a1 1 1 1 d1 e1 a1 1 1 1 d1 e1 a2 2 1 2 d2 e2 a2 2 1 1 d1 e1 a1 2 2 3 d3 e3 a2 2 1 2 d2 e2 a1 2 2 1 d1 e1 a1 2 2 2 d2 e2 B≥ C TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Nếu điều kiện kết nối chứa phép so sánh (=) bằng thì phép kết nối được gọi là phép kết nối bằng.  Trường hợp kết nối bằng tại thuộc tính cùng tên của hai quan hệ và một trong hai thuộc tính đó bị loại bỏ, thì phép kết nối được gọi là kết nối tự nhiên . Kí hiệu là " * ".  Biểu diễn của phép kết nối tự nhiên : r(ABC) * s(CDE) = { t[ABCDE]/ t[ABC]  r và t[CDE ] s} VD : với hai quan hệ r và s nêu trên thì : r(ABC) * s(CDE) = ( A B C D E) a1 1 1 d1 e1 a2 2 1 d1 e1 a1 2 2 d2 e2 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 8. Phép chia Gọi r là quan hệ n- ngôi và s là quan hệ m ngôi ( n > m, s   ). Phép chia r s là tập tất cả các ( n-m )- bộ t sao cho với mọi bộ u s thì bộ t  u  r. Ví dụ : r ( A B C D ) s ( C D) r s = ( A B) a b c d c d a b a b e f e f e d b c e f e d c d e d e f c a d e TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Cơ sở dữ liệu minh hoạ Cho một cơ sở dữ liệu Thực tập gồm 3 quan hệ sau đây: SV( SV#, HT, NS, QUE, HL) DT(DT#, TDT, CN, KP) SD(SV#, DT#, NTT, KM, KQ) -Quan hệ SV chứa thông tin về các sinh viên trong một lớp của một trường đại học. Trong đó: SV# : mã số sinh viên HT : Họ và tên sinh viên NS : Năm sinh của sinh viên QUE: quê quán HL : Học lực thể hiện qua điểm trung bình TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí - Quan hệ DT chứa thông tin về đề tài nhà trường quản lý . Trong đó : DT# : mã số đề tài TDT : tên đề tài CN : họ và tên chủ nhiệm đề tài KP : Kinh phí cấp cho đề tài ( triệu đồng) - Quan hệ SD chứa thông tin về tình hình thực tập của các sinh viên theo các đề tài. Trong đó : NTT : nơi thực tập KM : khoảng cách từ nơi thực tập đến trường KQ : kết quả thực tập theo đề tài đã chọn . * Giả thiết là mỗi sinh viên có thể tham gia nhiều đề tài, mỗi đề tài sinh viên đó thực tập tại một địa điểm. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí SV# HT NS Que HL 1 Hồng Mai 22/4/1982 Hà Nội 6.8 2 Mạnh Khánh 27/6/1986 Nam Định 8.3 3 Xuân Quỳnh 17/5/1987 Hà Nội 9.5 4 Ngọc Bích 25/4/1979 Nam Định 8.6 5 Minh Tú 19/3/1986 Quảng Ninh 6.2 6 Hồng Vân 19/4/1980 Hải Phòng 9.8 7 Ngọc Anh 27/5/1982 Hà Nội 7.6 8 Mai Lan 16/8/1983 Hải Phòng 8.5 DT# TDT CN KP 1 Phân tích thiết kế CSDL Trần Hùng 1000000 2 Mạng máy tính Nguyễn Anh 500000 3 Kiến trúc máy tính Hồng Hạnh 1400000 4 Phần mềm A Mạnh Hùng 2300000 5 Giáo trình ABC Hoàng Hà 900000 6 Mạng Internet Ngọc Lan 1800000 SV DT TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí SV# DT# NTT KM KQ 1 4 Hà Tây 56 6.8 1 6 Hải Phòng 120 8.7 3 5 Quảng Ninh 300 9 3 4 Hà Đông 30 9.7 2 3 Hà Nội 40 9.8 1 5 Nam Định 80 9.4 7 3 Hà Nội 38 8.7 5 5 Hải Phòng 150 8.2 7 3 Thanh Hoá 240 7.9 SD TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Yêu cầu : - Hãy viết các biểu thức đại số quan hệ biểu diễn các yêu cầu sau : 1. Cho thông tin về những sinh viên sinh trước năm 1985 có quê ở Hà Nội. 2. Cho biết các địa điểm thực tập xa trường (KM >100) của đề tài số 5. 3. Cho thông tin về các đề tài có sinh viên thực tập. 4. Cho biết mã của các đề tài không có sinh viên nào tham gia. 5. Cho danh sách các tỉnh có sinh viên đến thực tập. 6. Cho thông tin về việc thực tập tại Hải Phòng của sinh viên. 7. Cho biết mã của những đề tài có kinh phí lớn hơn 1 triệu và nhỏ hơn 2 triệu 8. Cho biết mã của sinh viên dưới 20 tuổi, thực tập khá ( có điểm kết quả thực tập >=6.5) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí III. Các phép toán quan hệ bổ sung  Các hàm kết tập: Có nhiều truy vấn mà đại số quan hệ không thể thực hiện được như: đưa ra tổng lương, tìm lương lớn nhất ,v.v..  Ta có các hàm sau:  Hàm tính trung bình cộng ( AVERAGE)  Hàm tính tổng ( SUM) Hàm tìm giá trị lớn nhất ( MAX), nhỏ nhất (MIN) Hàm đếm các bộ giá trị ( COUNT) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí  Các phép gộp nhóm: Nhóm các bộ trong một quan hệ theo một giá trị của một số các thuộc tính và sau đó áp dụng các hàm kết tập trên từng nhóm một cách độc lập.  Phép gộp nhóm được định nghĩa như sau:  < ds các hàm kết tập > (r) Trong đó : -  là kí hiệu của phép gộp nhóm - : là danh sách các thuộc tính của quan hệ. - : là danh sách các cặp ( . TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí • Kết quả của phép gộp nhóm là một quan hệ. Ngoài các thuộc tính cơ sở để gộp nhóm, quan hệ kết quả còn có các thuộc tính tương ứng với các phần tử trong danh sách hàm kết tập. • Nếu ds các thuộc tính cơ sở để gộp nhóm là rỗng thì các hàm kết tập được áp dụng cho các giá trị thuộc tất cả các bộ trong quan hệ. Khi đó quan hệ kết quả chỉ có một bộ. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Ví dụ : Giả sử có quan hệ NHAN_VIEN MA_NV HO_TEN NG_SINH MA_P LUONG 1 Hồng Mai 22/4/1982 P1 1000000 2 Mạnh Khánh 27/6/1978 P3 2500000 3 Xuân Quỳnh 17/5/1977 P2 1200000 4 Ngọc Bích 25/4/1979 P1 2000000 5 Minh Tú 19/3/1981 P3 1500000 6 Hồng Vân 19/4/1980 P1 1800000 7 Ngọc Anh 27/5/1982 P2 1800000 8 Mai Lan 16/8/1979 P1 1200000 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Nếu thực hiện phép gộp nhóm MA_PHONG  COUNT MA_NV, AVERAGE LUONG (NHAN_VIEN) Thì quan hệ kết quả sẽ là : MA_P COUNT MA_NV AVERAGE LUONG P1 4 1500000 P2 2 2000000 P3 2 1500000 Nếu thực hiện phép gộp nhóm :  COUNT MA_NV, AVERAGE LUONG (NHAN_VIEN) Thì quan hệ kết quả sẽ là : COUNT MA_NV AVERAGE LUONG 8 1666666.7 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí MA_NV HO_TEN NG_SINH GIOI_TINH MA_P LUONG 1 Trần Anh 28/3/1978 Nam P2 2000000 2 Ngọc Hà 17/4/1979 Nữ P1 1700000 3 Hồng Mai 29/6/1980 Nữ P4 2300000 4 Hoàng Hà 24/5/1980 Nam P2 1800000 5 Ngọc Lan 7/11/1979 Nữ P1 2500000 Bài tập: Xét các CSDL gồm các lược đồ quan hệ được cho bởi các thể hiện của chúng như sau: NHAN_VIEN MA_P TEN_P ĐIA_CHI P1 Hành chính quản trị P302 - Nhà A P2 Nghiên cứu và PT Tầng 3 - Nhà B P3 Giám đốc Tầng 2- Nhà A P4 Kỹ thuật P205 - Nhà C PHONG TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí DU_AN MA_DA TEN_DA ĐIA_ĐIEM_DA MA_P D1 Phần mềm A HÀ NỘI P4 D5 Mạng B NAM ĐỊNH P2 D20 Giáo trình điện tử HẢI PHÒNG P1 CHAM_CONG MA_NV MA_DA SO_GIO 1 D8 20 2 D4 15 3 D1 17 4 D8 24 5 D20 30 6 D1 27 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Yêu cầu : 1. Tìm tên dự án có mã là D20 2.Cho biết tên các thành phố có dự án thực hiện. 3. Cho biết tên phòng thực hiện dự án có mã là D20 4. Cho biết tên và lương của những nhân viên thực hiện dự án D8 và làm việc trên 20 giờ 5. Cho biết họ tên và lương của những nhân viên thuộc phòng " Nghiên cứu & PT" 6. Đếm số nhân viên trong công ty và tính mức lương trung bình của các nhân viên. 7. Đếm số dự án mà công ty đã thực hiện TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí