Bài giảng Chương 4: Đại số quan hệ và phép tính quan hệ

Chia sẻ: Nguyễn Phú Tiền | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

97
lượt xem 5
download

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

Bài giảng Chương 4: Đại số quan hệ và phép tính quan hệ trình bày về phép toán một ngôi, phép toán hai ngôi, phép toán khác, phép tính quan hệ tiến bộ, phép tính quan hệ biến miền. Mời bạn đọc 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 Chương 4: Đại số quan hệ và phép tính quan hệ

Nội dung trình bày Chương 4 Giới thiệu Phép toán một ngôi Đại số quan hệ Phép toán hai ngôi. Phép toán khác. và Phép tính quan hệ biến bộ. Phép tính quan hệ Phép tính quan hệ biến miền. Giới thiệu (1) Giới thiệu (2) Đại số quan hệ Toán hạng • Là tập hợp các phép toán cơ sở của mô hình dữ liệu • Các thể hiện quan hệ. quan hệ. • Biểu thức đại số quan hệ là một chuỗi các phép toán. • Các tập hợp. • Kết quả của một biểu thức là một thể hiện quan hệ. Toán tử là các phép toán Ý nghĩa • Phép toán tập hợp • Cơ sở hình thức cho các phép toán của mô hình quan - Hội, giao, hiệu, tích Cartesian. hệ. • Phép toán quan hệ • Cơ sở để cài đặt và tối ưu hóa các truy vấn trong các - Chọn, chiếu, kết, chia, đổi tên. HQT CSDL quan hệ. - Một số phép toán khác. • Được áp dụng trong SQL. more information and additional documents 1 connect with me here: http://facebook.com/ngphutien/
Phép toán 1 ngôi Phép chọn (1) Là các phép toán chỉ tác động lên một quan Để rút trích các bộ dữ liệu thỏa điều kiện chọn từ hệ. một quan hệ. Gồm R A B C D α α 1 7 σA=B ∧ D>5(R) A B C D • Phép chọn (Select). α α 1 7 α β 5 7 • Phép chiếu (Project). β β 12 3 β β 23 10 • Phép đổi tên (Rename). β β 23 10 Cú pháp • σ(R). • là biểu thức logic. Phép chọn (2) Phép chiếu (1) Biểu thức điều kiện Để rút trích các cột ứng với các thuộc tính nào đó • Chứa các mệnh đề có dạng của một quan hệ. - . - . R A B C D A D πA,D(R) • Toán tử so sánh: =, , ≥, ≠. α α 1 7 α 7 α β 5 7 α β 7 3 • Các mệnh đề được nối bởi toán tử logic: ∧, ∨, ¬. β β 12 3 β 10 3 Đặc trưng β β 23 10 β 10 • Phép chọn có tính giao hoán. - σ(σ(R)) = σ(σ(R)). Cú pháp • Kết quả là một quan hệ • π(R). - Có cùng bậc với R. • là danh sách các thuộc tính của R. - Có số bộ ít hơn hoặc bằng số bộ của R. more information and additional documents 2 connect with me here: http://facebook.com/ngphutien/
Phép chiếu (2) Chuỗi các phép toán và phép gán Đặc trưng Chuỗi các phép toán • Phép chiếu không có tính giao hoán. • Muốn sử dụng kết quả của phép toán này làm toán hạng của phép toán khác. - π(π(R)) ≠ π(π(R)). • Muốn viết các phép toán lồng nhau. • Phép chiếu loại bỏ các bộ trùng nhau. - πA,C(σA=B ∧ D>5(R)) • Kết quả là một quan hệ Phép gán - Có bậc bằng số thuộc tính của danh sách thuộc tính. • Muốn lưu lại kết quả của một phép toán. - Có bậc nhỏ hơn hoặc bằng bậc của R. • Để đơn giản hóa một chuỗi phép toán phức tạp. - Có số bộ ít hơn hoặc bằng số bộ của R. • Cú pháp Mở rộng phép chiếu - R’ ← E - E là biểu thức đại số quan hệ. • Cho phép sử dụng các phép toán số học trong danh • Ví dụ sách thuộc tính. - R’ ← σA=B ∧ D>5(R) - πA,2*C(R). πA,C(R’) Phép đổi tên Một số ví dụ Để đổi tên quan hệ và các thuộc tính. Tìm các nhân viên làm việc trong phòng số 4. Cú pháp: cho quan hệ R(A1, ..., An) • σMaPB = 4(NHANVIEN) • Đổi tên quan hệ R thành S Tìm các nhân viên làm việc trong phòng số 4 và có mức - ρS(R). lương từ 25.000 đến 40.000. • Đổi tên quan hệ R thành S và các thuộc tính Ai thành Bi • σMaPB = 4 ∧ Luong ≥ 25.000 ∧ Luong ≤ 40.000(NHANVIEN) - ρS(B1, B2, ..., Bn)(R). Cho biết họ, tên, giới tính và mức lương của các nhân viên. • Đổi tên các thuộc tính Ai thành Bi - ρ(B1, B2, ..., Bn)(R). • πHo, Ten, Gtinh, Luong(NHANVIEN) • Đổi tên quan hệ R thành S và thuộc tính A1 thành B1 Cho biết họ, tên, giới tính và mức lương của các nhân viên - ρS(B1, A2, A3, ..., An)(R). của phòng số 5. • Đổi tên thuộc tính A1 thành B1 • πHo, Ten, Gtinh, Luong(σMaPB = 5(NHANVIEN)) - ρ(B1, A2, A3, ..., An)(R). more information and additional documents 3 connect with me here: http://facebook.com/ngphutien/
Phép toán 2 ngôi Phép toán tập hợp (1) Là các phép toán tác động lên hai quan hệ. Chỉ được sử dụng khi hai quan hệ được tác Gồm 2 loại động là khả hợp. • Phép toán tập hợp Hai quan hệ R(A1, ..., An) và S(B1, ..., Bn) gọi - Phép hội (Union). là khả hợp nếu - Phép giao (Intersection). • Bậc R = Bậc S. - Phép hiệu (Mimus). • Miền xác định Ai ≡ Miền xác định Bi, với i = 1, ..., - Phép tích Cartesian. n. • Phép toán phi tập hợp - Phép kết (Join). - Phép chia (Division). Phép hội Phép giao Hội của R và S Giao của R và S • R∪S • R∩S • Là quan hệ gồm các bộ thuộc R hoặc thuộc S. • Là quan hệ gồm các bộ thuộc R đồng thời thuộc S. • Các bộ trùng nhau bị loại đi. R ∩ S = {t | t ∈ R ∧ t ∈ S} R ∪ S = {t | t ∈ R ∨ t ∈ S} R A C S A C A C R A C S A C A C α 1 α 1 R∩S α 1 α 1 α 1 R∪S α 1 α 5 γ 12 β 23 α 5 γ 12 α 5 β 12 β 23 β 12 β 23 β 12 β 23 β 23 β 23 αγ 1 12 γ 12 β 23 more information and additional documents 4 connect with me here: http://facebook.com/ngphutien/
Phép hiệu Phép toán tập hợp (2) Hiệu của R và S • R-S Đặc trưng • Là quan hệ gồm các bộ thuộc R nhưng không thuộc S. • Phép hội và giao có tính giao hoán R - S = {t | t ∈ R ∧ t ∉ S} - R ∪ S = S ∪ R và R ∩ S = S ∩ R. R A C S A C A C • Phép hội và giao có tính kết hợp R-S α 1 α 1 α 5 - R ∪ (S ∪ T) = (R ∪ S) ∪ T và R ∩ (S ∩ T) = (R ∩ S) α 5 γ 12 β 12 ∩ T. β 12 β 23 β 23 Phép tích Cartesian Một số ví dụ Tích Cartesian của R và S (không nhất thiết khả hợp). Tìm mã số các nhân viên của phòng số 5 hoặc giám sát • R×S trực tiếp các nhân viên phòng số 5. • Là quan hệ Q mà mỗi bộ là một tổ hợp của một thuộc R và một bộ thuộc S. • Q1 ← σMaPB = 5(NHANVIEN) • Bậc Q = Bậc R + Bậc S. Q2 ← πMaNV(Q1) • Số bộ Q = Số bộ R × Số bộ S. Q3 ← πMaGS(Q1) R × S = {(a1, ..., am, b1, ..., bn) | (a1, ..., am) ∈ R ∧ (b1, ..., bn) ∈ S} Q ← Q2 ∪ Q3 R A B C S D E A B C D E Cho biết họ, tên của các nhân viên nữ và tên các thân nhân α α 1 1 7 R×S α α 1 1 7 của họ. α β 5 5 7 α α 1 5 7 • Q1 ← σGTinh = ‘Nu’(NHANVIEN) β β 12 α β 5 1 7 Q2 ← ρ(HoNV, TenNV, MaNV1)(πHo, Ten, MaNV(Q1)) α β 5 5 7 Q3 ← Q2 × THANNHAN β β 12 1 7 Q4 ← σMaNV1 = MaNV(Q3) β β 12 5 7 Q ← πHoNV, TenNV, Ten(Q4) more information and additional documents 5 connect with me here: http://facebook.com/ngphutien/
Phép kết Phép kết theta Để kết hợp các bộ có liên quan từ hai quan Biểu thức điều kiện • Chứa các mệnh đề có dạng hệ. - Ai Bj. Có 3 loại + Ai là thuộc tính của R. + Bj là thuộc tính của S. • Kết theta (Theta Join) + Miền xác định Ai ≡ Miền xác định Bj. • Toán tử so sánh: =, , ≥, ≠. - R S. • Các mệnh đề được nối bởi toán tử logic: ∧. - là biểu thức logic. • Kết bằng (Equi Join) R A B C S E F R A=E ∧ C
Phép chia (1) Phép chia (2) A B C S D E R A B C D E Để rút trích các bộ của một quan hệ liên quan với α α 1 7 2 α α 1 7 2 tất cả các bộ của quan hệ còn lại. α β 12 2 5 α α 1 2 5 Cho 2 quan hệ R(Z) và S(X) β α 23 α β 12 7 2 • Z tập hợp các thuộc tính của quan hệ R. β β 3 β α 23 7 2 • X tập hợp các thuộc tính của quan hệ S. β β 23 β β 3 1 10 β β 12 β α 23 2 5 • X ⊆ Z. πA,B,C(R) β β 23 10 10 • R chia S là quan hệ T(Y) với Y = Z – X. β β 12 1 2 - T(Y) = {t | t ∈ πY(R) ∧ ∀ u ∈ S ⇒ (t, u) ∈ R}. Cú pháp R÷S A B C • R÷S α α 1 β α 23 Một số ví dụ Các phép toán khác Cho biết tên, địa chỉ của các nhân viên của phòng Nghiên Để biểu diễn các truy vấn mà không thể thực hiện cứu. với các phép toán đại số quan hệ cơ sở • Q1 ← σTenPB = ‘Nghien cuu’(PHONGBAN) • Các truy vấn mang tính chất thông kê đơn giản trên một Q2 ← Q1 * NHANVIEN tập hợp các giá trị hoặc các nhóm tập hợp giá trị dữ liệu. Q ← πHo, Ten, DChi(Q2) • Các truy vấn dùng để tạo các báo cáo. Cho biết tên các nhân viên tham gia tất cả các dự án do phòng số 5 điều phối. Gồm • Q1 ← πMaDA(σPhongQL = 5(DUAN)) • Hàm tập hợp (Aggregate Function). Q2 ← πMaNV, MaDA(THAMGIA) • Phép gom nhóm các bộ dữ liệu (Grouping). Q3 ← Q2 ÷ Q1 • Phép kết mở rộng (Outer Join). Q ← πHo, Ten(Q3 * NHANVIEN) more information and additional documents 7 connect with me here: http://facebook.com/ngphutien/
Hàm tập hợp và gom nhóm (1) Hàm tập hợp và gom nhóm (2) Để thực hiện các truy vấn thống kê đơn giản trên tập hợp các giá trị số S A B E F • SUM - Tính tổng của các giá trị trong tập hợp. ρS(A, B, E, F)(A, BℱSUM(C), AVG(C)(R)) α α 1 1 • AVG - Tính giá trị trung bình của các giá trị trong tập hợp. α β 5 5 • MAX, MIN - Tìm giá trị lớn nhất, nhỏ nhất của các giá trị trong tập hợp. β β 32 16 Để đếm số bộ của một quan hệ hoặc số các giá trị của một thuộc tính. R A B C D • COUNT Để gom nhóm các bộ của một quan hệ theo các thuộc tính rồi áp dụng α α 1 7 α β 5 8 AℱMAX(C), MIN(C)(R) A MAX_C MIN_C các hàm tập hợp. Cú pháp β β 12 3 α 5 1 • ℱ(R) β β 20 10 β 20 12 • là danh sách các thuộc tính thuộc R. • là danh sách các cặp (hàm tập hợp, thuộc tính) áp dụng trên các nhóm. ℱCOUNT(C), AVG(D)(R) COUNT_C AVG_D 4 7 Phép kết mở rộng (1) Phép kết mở rộng trái Để giữ lại tất cả các bộ trong một quan hệ bất chấp Giữ lại tất cả các bộ của quan hệ ở bên trái phép toán kết chúng có được liên kết với các bộ trong quan hệ mà không liên kết được với bộ nào của quan hệ bên phải. còn lại hay không nhằm tránh mất thông tin hoặc R A B C tạo các báo cáo. α α 1 A B C D E α α 1 2 7 Có 3 dạng α β 5 α α 1 12 3 β β 12 • Mở rộng trái (Left Outer Join) R C
Phép kết mở rộng phải Phép kết mở rộng hai phía Giữ lại tất cả các bộ của quan hệ ở bên phải phép toán kết Giữ lại tất cả các bộ của từng quan hệ ở hai bên phép toán mà không liên kết được với bộ nào của quan hệ bên trái. kết mà không liên kết được với bộ nào của quan hệ còn lại. R A B C R A B C A B C D E α α 1 α α 1 α β 5 1 7 A B C D E α β 5 α β 5 α β 5 2 7 α α 1 1 7 β β 12 β β 12 R S β β R S β β 23 C>D 12 1 7 β β 23 C=D β β 12 12 3 β β 12 2 7 β β 23 23 10 S D E β β 23 1 7 S D E α β 5 null null 1 7 β β 23 2 7 1 7 null null null 2 7 2 7 β β 23 12 3 2 7 12 3 null null null 23 10 12 3 23 10 23 10 Một số ví dụ Phép tính quan hệ (1) Với mỗi phòng ban cho biết mã số, tổng số nhân viên và Một số khái niệm logic toán học mức lương trung bình. • Mệnh đề • ρ(MaPB, SoNV, LuongTB)(MaPBℱCOUNT(MaNV), AVG(Luong) - Các khẳng định có giá trị chân lý xác định. (NHANVIEN)) • Vị từ - Là một khẳng định P(x, y, ...) với x, y, ... là các biến trên các miền xác Với mỗi nhân viên cho biết họ, tên và tên phòng nếu họ là định A, B, ... trưởng phòng. + P(x, y, ...) không là mệnh đề. • Q1 ← NHANVIEN PHONGBAN + Thay x, y, ... bằng các giá trị cụ thể ta được một mệnh đề. MaNV = TrPhong - x, y, ... là các biến tự do. Q ← πHo, Ten, TenPB(Q1) • Lượng từ - Mệnh đề “∀x ∈ A, P(x)” và “∃x ∈ A, P(x)” là các lượng từ hóa của vị từ P(x). + ∀ là lượng từ phổ dụng. + ∃ là lượng từ tồn tại. - x không còn là biến tự do, nó bị buộc bởi các lượng từ ∀ hay ∃. more information and additional documents 9 connect with me here: http://facebook.com/ngphutien/
Phép tính quan hệ (2) Biến bộ và quan hệ miền giá trị Tổng quan Biến bộ (Tuple Variable) • Ngôn ngữ hình thức của mô hình quan hệ. • Biến biến thiên trên một quan hệ R xác định. • Chỉ quan tâm đến nội dung dữ liệu cần truy vấn. R được gọi là quan hệ miền giá trị của biến bộ (Range Relation). • Ngôn ngữ phi thủ tục. Phép tính quan hệ biến bộ đơn giản • Dựa trên logic toán học. • {t | P(t)}. Chia làm 2 dạng - t là biến bộ. • Phép tính quan hệ biến bộ. - P(t) là vị từ hoặc công thức. • Phép tính quan hệ biến miền (miền xác định). Ví dụ • {t | t ∈ NHANVIEN ∧ t.Luong > 50000}. • {t.Ho, t.Ten | NHANVIEN(t) ∧ t.Luong > 50000} Biểu thức và công thức (1) Biểu thức và công thức (2) Biểu thức tổng quát của phép tính quan hệ biến bộ P được xây dựng từ các Biến bộ tự do và bị buộc công thức nguyên tử liên • F là nguyên tử • {t1.Aj, t2.Ak, ..., tn.Am | P(t1, t2, ..., tn, ..., tn+m)} kết với nhau bởi các phép - Biến bộ là tự do. - t1, ..., tn+m là các biến bộ. toán logic ∧, ∨, ¬ theo các • (∀t)(F), (∃t)(F) - Ai là thuộc tính của quan hệ miền giá trị ứng với biến bộ ti. luật sau - Biến bộ là bị buộc. 1. Công thức nguyên tử là • ¬F, F ∧ G, F ∨ G Công thức nguyên tử công thức. - Biến bộ là tự do hoặc bị • Thuộc một trong 3 dạng sau 2. F là công thức thì ¬F cũng là buộc. - t ∈ R hoặc R(t) t ∈ NHANVIEN hoặc NHANVIEN(t) công thức. - Biến bộ có thể là tự do trong F và bị buộc trong G. - ti.A tj.B. t.MaNV = s.MaNV F, G là công thức thì F ∧ G, F ∨ G cũng là công thức Ví dụ - ti.A c. t.Luong > 50000 3. F là công thức thì (∀t)(F) • F1: NHANVIEN(d) • Có chân trị ĐÚNG hoặc SAI. cũng là công thức. • F2: (∀d)(d.MaGSat = 4. F là công thức thì (∃t)(F) ‘123456789’) cũng là công thức. more information and additional documents 10 connect with me here: http://facebook.com/ngphutien/
Biến đổi giữa hai lượng từ Truy vấn dùng lượng từ tồn tại (1) Quy tắc biến đổi Tìm tên và địa chỉ của các nhân viên phòng Nghiên • (∀) thay bằng ¬(∃), và ngược lại. cứu. • ∧ thay bằng ∨, và ngược lại. NHANVIEN(e) ∧∧ (∃d)(PHONGBAN(d) • {e.Ten, e.DChi | NHANVIEN(e) (∃d)(PHONGBAN(d) ∧∧ • ¬P thay bằng P, và ngược lại. d.TenPB = ‘Nghiên cứu’ ∧ d.MaPB = e.MaPB) e.MaPB)} Một số biến đổi thường gặp • {e.Ten, e.DChi | NHANVIEN(e) ∧ F} - F = (∃d)(PHONGBAN(d) ∧ F1) • (∀x)(P(x)) ⇔ ¬(∃x)(¬(P(x))) - F1 = (d.TenPB = ‘Nghiên cứu’ ∧ d.MaPB = e.MaPB) • (∃x)(P(x)) ⇔ ¬(∀x)(¬(P(x))) • (∀x)(P(x) ∧ Q(x)) ⇔ ¬(∃x)(¬(P(x)) ¬(P(x)) ∨ ¬(Q(x)) ¬(Q(x))) • (∀x)(P(x) ∨ Q(x)) ⇔ ¬(∃x)(¬(P(x)) ∧ ¬(Q(x))) • (∃x)(P(x) ∧ Q(x)) ⇔ ¬(∀x)(¬(P(x)) ∨ ¬(Q(x))) • (∃x)(P(x) ∨ Q(x)) ⇔ ¬(∀x)(¬(P(x)) ∧ ¬(Q(x))) Truy vấn dùng lượng từ tồn tại (2) Truy vấn dùng lượng từ tồn tại (3) Với mỗi dự án triển khai tại Thủ Đức, cho biết mã Với mỗi nhân viên, cho biết họ tên của nhân viên dự án, mã phòng quản lý dự án và họ tên người và họ tên của người quản lý nhân viên đó. trưởng phòng. NHANVIEN(e) ∧∧ • {e.Ho, e.Ten, s.Ho, s.Ten | NHANVIEN(e) DUAN(p) ∧∧ • {p.MaDA, p.Phong, e.Ho, e.Ten | DUAN(p) NHANVIEN(s) ∧ e.MaGSat = s.MaNV } NHANVIEN(e) ∧ p.Diadiem = ‘Thủ Đức’ ∧ (∃d)(PHONGBAN(d) ∧ d.MaPB = p.Phong ∧ d.TrPhg = Nhận xét e.MaNV) e.MaNV)} • Một vài biến bộ trong cùng một truy vấn có thể có cùng quan hệ miền giá trị. Nhận xét • Trong một truy vấn có thể có nhiều biến bộ tự do. more information and additional documents 11 connect with me here: http://facebook.com/ngphutien/
Truy vấn dùng lượng từ tồn tại (4) Truy vấn sử dụng lượng từ phổ dụng Tìm các nhân viên tham gia các dự án do phòng số Tìm các nhân viên tham gia tất cả các dự án do 5 điều phối. phòng số 5 điều phối. • {e | NHANVIEN(e) ∧ (∃x)(∃w)(DUAN(x) ∧ THAMGIA(w) ∧ • {e | NHANVIEN(e) ∧ ((∀x)(¬(DUAN(x)) ∨ ¬(x.MaDA = 5) x.Phong = 5 ∧ x.MaDA = w.MaDA ∧ x.MaNV = w.MaNV)} ∨ ((∃w)(THAMGIA(w) ∧ w.MaNV = e.MaNV ∧ x.MaDA = w.MaDA))))} • {e | NHANVIEN(e) ∧ F} - F = (∀x)(¬(DUAN(x)) ∨ F1) - F1 = ¬(x.MaDA=5) ∨ F2 - F2 = (∃w)(THAMGIA(w) ∧ w.MaNV=e.MaNV ∧ x.MaDA=w.MaDA) • {e | NHANVIEN(e) ∧ (¬(∃x)(DUAN(x) ∧ x.MaDA = 5 ∧ (¬(∃w)(THAMGIA(w) ∧ w.MaNV = e.MaNV ∧ x.MaDA = w.MaDA))))} Biểu thức an toàn Phép tính quan hệ biến miền Xét biểu thức Định nghĩa hình thức Biểu thức tổng quát của phép tính quan hệ biến • {t | ¬(NHANVIEN(t))} • Miền xác định của biểu thức miền • Nhận xét là tập hợp gồm - Kết quả của biểu thức không - Các hằng xuất hiện trong P. • {x1, x2, ..., xn | P(x1, x2, ..., xn, ..., xn+m)} là một số hữu hạn các bộ. - Giá trị thuộc tính của các bộ - x1, ..., xn+m là các biến miền. của các quan hệ xuất hiện - Biểu thức là không an toàn. trong P. Công thức nguyên tử Biểu thức an toàn là biểu • Thuộc một trong 3 dạng sau • Ví dụ thức có một số hữu hạn - {t | R(t) ∧ t.A = 5} - ∈ R hoặc R(x1, ..., xj) các bộ trong kết quả. - Mxđ = {5, 1, 7, 23, 10} - xi xj. • Biểu thức là an toàn nếu mọi - xi c. R A B giá trị trong kết quả thuộc miền xác định của biểu thức. • Có chân trị ĐÚNG hoặc SAI. 1 7 23 10 Các khái niệm khác tương tự biến bộ. more information and additional documents 12 connect with me here: http://facebook.com/ngphutien/