Bài giảng chương 3: Đại số quan hệ - Đặng Quốc Việt

Chương 3. ĐẠI SỐ QUAN HỆ GV: Đặng Quốc Việt dqviet@cit.ctu.edu.vn Đại số quan hệ(Relational Algebra) Đại số quan hệ là một bộ  = (M, P ), trong đó M : tập các quan hệ cho trước P : tập các phép toán cơ bản sau. Các phép toán cơ bản: Phép chọn  Phép chiếu  Phép hợp  Phép giao  Phép tích Descart x Phép trừ - hay \ Phép chia : hay / Phép -kết nối Phép kết nối tự nhiên * Phép kết nối mở rộng Các phép toán này có: Đầu vào: 1 hoặc nhiều quan hệ Đầu ra: một quan hệ mới gọi là quan hệ kết quả. Biểu thức quan hệ Định nghĩa: là một biểu thức gồm các quan hệ trong 1 CSDL và các phép toán quan hệ. Ví dụ: MAÎHAÌNG, TÃNHG ( ÂVT=”caïi” (HAÌNG)) Độ ưu tiên của các phép toán trong 1 biểu thức quan hệ: Phép toán một ngôi Tùy theo HQTCSDL cụ thể, có thể có những qui định riêng Ví dụ - CSDL Đào Tạo Trong chương này, các ví dụ sử dụng các quan hệ sau: SV(MASV, HOTEN_SV, NAMS_SV, DCHI_SV, TENLOP) MON(MAMH, TENMON, SO_TC, LOAI_MON) GV( MAGV, HOTEN_GV, NAMS_GV, HOCVI) HOC(MASV, MAMH, STT_HK, NKHOA, LANTHI, K_QUA) DAY(MAGV, MAMH, STT_HK, NKHOA) Xác định khóa chính, khóa ngoại cho từng quan hệ Vẽ sơ đồ cho thấy sự thông thương giữa các quan hệ Phép chọn(Select Operation) Mục đích: Xây dựng một tập con gồm các bộ của quan hệ đã cho, thỏa biểu thức logic cho trước. Định nghĩa: Cho quan hệ R trên tập thuộc tính U, ký hiệu R(U). Cho biểu thức logic E phát biểu trên U gồm có: Các thuộc tính hoặc các hằng Các phép toán so sánh số học: , , , , =,  Các phép toán logic: , ,  Phép chọn quan hệ R theo điều kiện E, ký hiệu R(E) hay E(R) P = R(E)=E(R) = {t | t  R and t(E)} Trong đó: t(E): nghĩa là bộ t thỏa biểu thức điều kiện E Ví dụ: Liệt kê danh sách sinh viên lớp DI0056A1 Tenlop = “DI0056A1” (SV) Lọc bảng theo chiều ngang Phép chọn – Ví Dụ So_TC = 3 (MON) MON Bảng Kết quả: Tìm thông tin chi tiết của các sinh viên thuộc lớp DI0056A1 và sinh vào năm 1980 Tìm thông tin về kết quả học môn TH409 và TH490 của sinh viên. Phép chiếu(Project Operation) Mục đích: Cho kết quả là một quan hệ gồm các bộ của quan hệ đã cho trong đó loại bỏ đi một số thuộc tính không được liệt kê. Định nghĩa: Cho quan hệ R(U)=(A1, A2, …, An), Ai U và tập thuộc tính X  U Phép chiếu quan hệ R trên X là tập hợp: P =R[X] = X (R) = {t[X] | t  R} Vì quan hệ là tập hợp => Những dòng trùng nhau bị xóa khỏi quan hệ kết quả Ví dụ: Liệt kê mã số sv, họ tên và tên lớp. mssv, hoten_sv, tenlop (SV) Lọc bảng theo chiều dọc Phép chiếu – Ví dụ  MAMH, So_TC (MON) MON Bảng Kết quả: Liệt kê danh sách gồm mã số sinh viên và điểm thi lần 1 của môn TH409 trong học kỳ vừa rồi. Cho biết điểm của từng môn học đã tích lũy được của sinh viên. Phép hợp(Union Operation) Hai quan hệ tương thích: nếu chúng có cùng tập thuộc tính, hay lược đồ quan hệ Định nghĩa: Hợp của 2 quan hệ tương thích R(U) và S(U) là một quan hệ P gồm các bộ thuộc ít nhất một trong hai quan hệ đã cho. P = R  S = R + S = {t | t  R hoặc t  S} Ví dụ: Liệt kê danh sách gồm họ tên của sinh viên và họ tên của giáo viên. hoten_sv (SV)  hoten_gv (GV) Phép trừ(Set Difference Operation) Định nghĩa: hiệu của 2 quan hệ tương thích R(U) và S(U) là một quan hệ P gồm các bộ có trong R nhưng không có trong S. P = R \ S = R – S = {t | t  R và t  S} Ví dụ: Tìm mã các môn học có dạy ở học kỳ 2 năm học 04-05 nhưng không có dạy ở học kỳ 2 năm học 05-06. mamh STT_KH = 2  NKHOA = ’04-05’(DAY) – mamh STT_KH = 2  NKHOA = ’05-06’(DAY) R Phép giao(Set-Intersection Operation) Định nghĩa: Giao của 2 quan hệ tương thích R(U) và S(U) là một quan hệ P gồm các bộ thuộc cả hai quan hệ đã cho. R  S ={ t | t  R và t  S } Có thể biễu diễn phép giao qua phép trừ: R  S = R - (R - S) Ví dụ: Tìm mã số của các giáo viên có dạy môn có mã số TH409 và môn có mã số TH490. magv MAMH = ‘TH409’ (DAY)  magv MAMH = ‘TH490’(DAY) R Ví dụ phép Hợp, Giao, Trừ A: Những môn dạy ở NK 04-05 B: Những môn dạy ở NK 05-06 A  B A  B A \ B A  B A  B A \ B Phép chia(Division Operation) Định nghĩa: Cho 2 quan hệ R(U) có n ngôi và S(V) có m ngôi, V  U và S . Đặt X = U – V. Phép chia quan hệ R cho S cho kết quả là một quan hệ gồm các bộ t có (n-m) thuộc tính, sao cho với mọi bộ v trong S, thì là một bộ thuộc R R : S = R/S = { t | t  R(U-V)  ( v  S) (  R ) } Ví dụ: Tìm mã số của các sinh viên có học tất cả các môn. masv, mamh(HOC) / mamh(MON) R Ví dụ: R: Giáo viên dạy môn: S: Các môn học quan tâm Phép chia - ví dụ(Division Operation) Tích Đề-các (Cartesian-Product Operation) Định nghĩa: Cho 2 quan hệ R(U) n ngôi, có a bộ và S(V) m ngôi, có b bộ, và U  V =  Tích Descart của R và S là tập gồm (a.b) bộ, mỗi bộ có (n+m) thuộc tính. R x S = { | u  R  v  S } Nếu U  V  , vậy thì phải đổi tên các thuộc tính trùng nhau. R x S: DS sinh viên để lên điểm R: DS Lớp S: DS Môn học trong học kỳ này Tích Đề-các – ví dụ (Cartesian-Product Operation) Ví dụ: Phép kết nối θ (Inner join, join) Định nghĩa: Cho 2 quan hệ R(U) và S(V) θ là một trong các phép toán số học: , , , , =,  Phép kết nối giữa quan hệ R đối với thuộc tính A U và quan hệ S đối với thuộc tính B V, được ký hiệu R S R S= {| uU  v V u[A] θ v[B] } Phép kết nối chỉ thực hiện được khi θ thực hiện được giữa A và B. Nếu không dựa trên phép so sánh θ thì R S là phép tích Descartes, nếu θ là phép so sánh “=“ thì gọi là phép kết nối bằng. Phép kết nối θ – Ví dụ Ví dụ: Tìm thông tin về sinh viên lớn tuổi hơn một giáo viên nào đó. SV GV Phép kết nối tự nhiên(Natural-Join Operation) Nếu kết nối θ dựa trên phép so sánh “=“ tại các thuộc tính cùng tên của 2 quan hệ R và S và một trong hai thuộc tính đó bị loại bỏ qua phép chiếu thì gọi là phép kết nối tự nhiên, ký hiệu *. Ví dụ: Tìm tên các môn học có dạy trong học kỳ 2 05-06. A: mamh STT_KH = 2  NKHOA = ’05-06’(DAY) B: mamh, TenMon (MON) A * B Những dòng không có ở cả 2 bảng sẽ không có mặt ở bảng KQ Phép kết nối mở rộng(Outer join) Định nghĩa: Phép toán này cho phép làm việc với thông tin bị thiếu, tức là vẫn thực hiện phép kết nối tự nhiên trên các trị trống của thuộc tính dùng để kết nối. Có 3 loại kết nối mở rộng: trái, phải và hai bên Cho 2 quan hệ R và S: Trái: R S = P  ( R * S ) P={| u  R, u không tương ứng với bộ nào của S, v S, các giá trị của các thuộc tính trong v đều là null } Phải: R S = Q  ( R * S ) Q={| v  s, v không tương ứng với bộ nào của R, u  R, các giá trị của các thuộc tính trong u đều là null } Hai bên: R S = P  Q  ( R * S ) P và Q được định nghĩa như trên. Phép kết nối mở rộng – ví dụ(Outer join) R: DS GV của Khoa S: Phân công dạy trong HK này Phép đổi tên(Rename Operation) Cho phép chúng ta đặt tên, và nhờ đó ta có thể tham chiếu đến kết quả của các biểu thức đại số quan hệ. Cho phép chúng ta tham chiếu đến một quan hệ nhiều lần, dùng trong các phép kết nối. Ví dụ:  x (E) Sẽ trả về kết quả của biểu thức E với tên X Nếu kết quả của biểu thức quan hệ E có n ngôi, thì: x (A1, A2, …, An) (E) Sẽ trả về kết quả của E với tên X, và với các thuộc tính được đặt tên là A1, A2, …., An. Phép gán(Assignment Operation) Phép gán () cung cấp một phương tiện thuận lợi để biễu diễn các truy vấn phức tạp. Example: Có thể viết R(U)  S(V) như sau temp1  U-V (R)  temp2  U-V ((temp1 x S) – U-V,V (R)) result = temp1 – temp2 Kết quả của biểu thức bên phải dấu  sẽ được gán cho biến biểu thức bên trái dấu . Có thể sử dụng biến ở các biểu thức theo sau. Các hàm kết tập(Aggregate Functions) Các hàm kết tập nhận vào một tập các giá trị và trả về kết quả là một giá trị. avg: giá trị trung bình min: giá trị min max: giá trị max sum: tổng count: đếm những giá trị Các hàm kết tập – Ví dụ (Aggregate Functions) sum SO_TC (MON) max SO_TC (MON) Trong trường hợp ta muốn loại bỏ các giá trị trùng nhau, thì phải thêm từ khoá distinct vào sau tên hàm và dấu gạch ngang (-) Ví dụ : Count-distinct SO_TC (MON) = 3 MON count SO_TC (MON) min SO_TC (MON) avg SO_TC (MON) Ta có thể áp dụng hàm kết tập trên nhiều nhóm khác nhau, mỗi nhóm bao gồm một tập các bộ. Hàm kết tập trên nhóm có dạng: G1, G2, …, Gn g F1 A1, F2 A2,…, Fm Am (E) Trong đó: E là biểu thức quan hệ bất kỳ G1, G2, …, Gn là các thuộc tính mà việc chia nhóm dựa trên các giá trị của chúng. Mỗi Fi là một hàm kết tập. Mỗi Ai là một thuộc tính Các hàm kết tập (cont.)(Aggregate Functions) Các hàm kết tập (cont.)(Aggregate Functions) Biểu thức: MASV g min K_QUA, avg K_QUA (HOC) sẽ cho kết quả như sau: HOC Tính chất đại số quan hệ Tính chất đại số quan hệ (Cont.) Tối Ưu Hóa Biểu Thức Quan Hệ Mục đích: Chuyển biểu thức quan hệ về dạng tương đương nhưng có chi phí thực hiện thấp hơn (thời gian, không gian lưu trữ) Nguyên tắc: Tìm cách chuyển các phép toán để thực hiện sớm nhất đến mức có thể các phép toán có tính chất làm hẹp quan hệ (phép chọn, chiếu). Để thực hiện được điều này, ta dùng cây thực hiện để minh họa cho quá trình thực hiện một biểu thức. Ví dụ: Có biểu thức quan hệ: (SINHVIEN*SV_DT*DETAI) (MADT>3  MASV > MADT  KETQUA>HOCLUC)[TENDT, KETQUA] Tối Ưu Cây Thực Hiện BTQH [TENDT, KETQUA] (MADT > 3  KQ > HL  MASV > MADT) * * SV SV_DT DETAI [TENDT, KETQUA] (MADT > 3) * * SV SV_DT DETAI (KQ>HL) [MADT,TENDT,KQ] [MASV,HL] (MASV> MADT) [MASV, MADT,KQ]