-
Thông tin
-
Hỏi đáp
Lý thuyết Đại số quan hệ | Đại học Kinh Tế Quốc Dân
Lý thuyết Đại số quan hệ | Đại học Kinh Tế Quốc Dân. Tài liệu gồm 19 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!
Đại học Kinh Tế Quốc Dân (3 K)
Lý thuyết Đại số quan hệ | Đại học Kinh Tế Quốc Dân
Lý thuyết Đại số quan hệ | Đại học Kinh Tế Quốc Dân. Tài liệu gồm 19 trang giúp bạn tham khảo, củng cố kiến thức và ôn tập đạt kết quả cao trong kỳ thi sắp tới. Mời bạn đọc đón xem!
Môn: Đại số tuyến tính ( NEU )
Trường: Đại học Kinh Tế Quốc Dân
Thông tin:
Tác giả:
Preview text:
Thế nào là Truy vấn CSDL?
} Cho một CSDL, đưa ra các câu hỏi, nhận được các câu trả lời. } Vd.,
} Cho biết tất cả sinh viên có điểm trung bình > 8 điểm thuộc các khoa TOAN, CNTT
} Cho biết các khoa có hơn 50 giảng viên TH107 - Cơ sở Dữ liệu
} Trong số các khoa, chọn sinh viên đạt điểm trung bình Bài 3
cao nhất trong năm học trước Đại số Quan hệ Bài 3 3 TH107 Dàn bài Ngôn ngữ Truy vấn
} Ngôn ngữ Truy vấn trong Mô hình Quan hệ Query language (QL)
} Các Phép toán Đại số Quan hệ
} Ngôn ngữ truy vấn là một ngôn ngữ cho phép } Các Thao tác Cập nhật
người dùng cập nhật và rút trích dữ liệu được lưu
trong một mô hình dữ liệu.
} Ngôn ngữ truy vấn ¹ Ngôn ngữ lập trình
} QL không nhằm mục đích dùng cho các ứng dụng phức tạp
} QL hỗ trợ truy xuất dễ dàng tới các tập hợp dữ liệu lớn Bài 3 2 TH107 Bài 3 4 TH107 © Bui MT Diem, 2007 1
Ngôn ngữ Truy vấn Quan hệ
Đại số >< Đại số Quan hệ
} Hai ngôn ngữ truy vấn (toán học) là cơ sở của các ngôn Algebra Relational Algebra
ngữ "thực sự" thực hiện (vd., SQL) là
} Đại số là hệ thống toán
} Đại số Quan hệ là một tập
} Đại số Quan hệ (Relational Algebra): mang tính thao tác học bao gồm hợp các phép toán quan
(operational), rất có ưu thế trong việc biểu diễn kế hoạch thi hành
} operands: biến hay giá trị
hệ để rút trích dữ liệu. truy vấn.
trong đó các giá trị mới có
} Giống như đại số với các
} Phép tính Quan hệ (Relation Calculus): khai báo (declarative), thể được tạo ra
không thủ tục (non-procedural), dựa trên ngôn ngữ logic. Cho con số, ĐSQH có
} operators: ký hiệu để chỉ các
phép người dùng mô tả cái họ muốn hơn là cách xử lý nó.
thủ tục tạo ra các giá trị mới
} các operands là các quan hệ
từ các giá trị cho trước
hay các biến đại diện cho
Bình thường, ta không sử dụng ĐSQH trực tiếp … không thấy sản phẩm nào quan hệ.
sử dụng ĐSQH được sử dụng rộng rãi.
} các operators để thực hiện
Nhưng nó được dùng bên trong các HQTCSDL vì ngữ nghĩa rõ ràng, chuẩn,
các công việc trên một quan
có cú pháp rõ ràng. hệ trong CSDL.
Hiểu được đại số quan hệ và phép tính quan hệ là chìa khóa để hiểu cách xử
lý và tối ưu hóa câu truy vấn. 5 TH107 Bài 3 7 TH107 Bài 3 Tổng quát Đại số Quan hệ
} Truy vấn được áp dụng cho các quan hệ, và nhận
} Mọi phép toán quan hệ nhận đầu vào là một hay
về kết quả là một quan hệ
nhiều quan hệ và tạo ra kết quả là một quan hệ.
} Lược đồ của các quan hệ đầu vào đối với một truy vấn
} closure property: input là quan hệ, output là quan hệ là cố định
} unary operators: thao tác trên một quan hệ (= phép
} Lược đồ của kết quả ứng với một truy vấn cũng cố định. toán một ngôi)
Nó được xác định bởi các định nghĩa của cấu trúc ngôn
} binary operators: lấy hai quan hệ làm input (= phép ngữ truy vấn. toán hai ngôi)
} Một chuỗi các phép toán ĐSQH được gọi là một
biểu thức ĐSQH (relational algebra expression). Bài 3 6 TH107 8 TH107 Bài 3 © Bui MT Diem, 2007 2 Dàn bài Phép chọn
} Ngôn ngữ Truy vấn trong Mô hình Quan hệ Selection Operation
} Các Phép toán Đại số Quan hệ
} Phép chọn là phép toán một ngôi. Nó lấy một quan
hệ là input và trả về một quan hệ mới là output chứa } Các Thao tác Cập nhật
một tập con các bộ từ quan hệ input.
} Nghĩa là, quan hệ output có cùng lược đồ quan hệ (cùng số
lượng thuộc tính) như quan hệ input, nhưng có thể có ít bộ hơn.
} Để xác định các bộ nào có trong output, phép chọn
có một điều kiện cụ thể, được gọi là một predicate -
điều kiện chọn P, mà các bộ được trích chọn phải thoả mãn.
} Predicate tương đương với một điều kiện trong mệnh đề . Bài 3 9 TH107 Bài 3 11 TH107 Các phép toán quan hệ
Định nghĩa Hình thức Phép chọn } Phép chọn s } Đại số mở rộng
} Phép chọn tên quan hệ R với predicate P được ký } Phép chiếu mở rộng } Phép chiếu p
hiệu là sP(R) } OUTER JOIN } AGGREGATE FUNCTIONS và
} Định nghĩa: sP(R) = {t | t Î R Ù P(t)}
} Phép toán được hình thành từ GROUPING
lý thuyết tập hợp toán học: trong đó } phép hội È
} R là một quan hệ, t là một biến bộ } phép giao Ç
} P là một công thức (predicate) bao gồm } phép trừ -
} các operands là các hằng số hoặc thuộc tính
} phép tích Cartesian ´
} các phép so sánh: =, ≠, <, ≤, >, ≥
} các phép toán logic: Ù (AND), Ú (OR), Ø (NOT) } Phép kết
} Phép chọn có tính giao hoán: } Phép chia ¸
s (s (R)) = s (s (R)) = s (R) } Phép đổi tên r P1 P2 P2 P1 (P1 Ù P2) Bài 3 10 TH107 Bài 3 12 TH107 © Bui MT Diem, 2007 3 Ví dụ Phép chọn Phép Chiếu Project Operation Nvien ms_nv ten_nv cvu luong s cvu=‘KS’ (Nvien) N1 T. Vu KS 30000 Nvien ms_nv ten_nv cvu luong
} Phép chiếu là phép toán một ngôi. Nó lấy một N2 N. Thanh TK 40000 N1 T. Vu KS 30000
quan hệ là input và trả về một quan hệ mới là N3 V. Minh PT 50000 N4 T.Tram KS 30000
output chứa một tập con các thuộc tính của quan N4 T.Tram KS 30000 N6 M. Tuan KS 50000
hệ input và tất cả các bộ không trùng. N5 P. Thao KT 45000 s
} Quan hệ output có cùng số lượng các bộ như quan hệ N6 M. Tuan KS 50000
luong > 45000 Ú cv=‘TK’ (Nvien) Nvien ms_nv ten_nv cvu luong
input nếu không loại bỏ các thuộc tính làm cho trùng N7 T. Tam LT 60000 N2 N. Thanh TK 40000 N8 T. Thanh LT 55000
} Câu hỏi: Khi nào ta bảo đảm được không bao gờ có giá N3 V. Minh PT 50000
trị trùng khi thực hiện một phép chiếu? N6 M. Tuan KS 50000
} Ngoài quan hệ, phép chiếu lấy từ input tên các N7 T. Tam LT 60000
thuộc tính làm tên các thuộc tính trong quan hệ N8 T. Thanh LT 55000 output. Bài 3 13 TH107 Bài 3 15 TH107 Câu hỏi Phép chọn
Định nghĩa Hình thức Phép Chiếu Tgia ms_nv ms_da nvu tgian 1.
Liệt kê tất cả các nhân viên tham
} Phép chiếu trên quan hệ R với các thuộc tính N1 D1 Quan ly 12 gia dự án D2. output là A đượ 1, …, Ak c ký hiệu là pA (R) 1, …, Ak N2 D1 Phan tich 24 2.
Liệt kê các nhân viên tham gia
với tư cách quản lý dự án. } Định nghĩa: pA
(R) = {t[A1, …, Ak] | t Î R} N2 D2 Thiet ke 6 1, …, Ak 3.
Liệt kê các nhân viên tham gia trong đó N3 D3 Phan tich 10
dự án có người quản lý làm việc hơn 40 tháng.
} R là một quan hệ, t là một biến bộ N3 D4 Tu van 48
Cho biết kết quả trong mỗi trường } {A , …, A N4 D2 Thiet ke 18 1
k} là một tập con các thuộc tính của R mà trên hợp.
đó phép chiếu được thực hiện N5 D2 Phan tich 24
} Thứ tự của A , …, A N6 D4 Quan ly 48 1
k là quan trọng trong kết quả
} Số bộ (cardinality) của p
(R) không nhất thiết bằng N7 D3 Lap trinh 36 A1, …, Ak
với R vì các bộ trùng bị loại bỏ N7 D5 Thiet ke 23 N8 D3 Quan ly 40 } Ta có: } pA (p (R)) = p
(R), với k £ l 1, …, Ak A1, …, Al A1, …, Ak
} Phép chiếu không có tính giao hoán 14 TH107 Bài 1 Bài 3 16 TH107 © Bui MT Diem, 2007 4
Phép Chọn >< Phép Chiếu Câu hỏi Phép chọn A A A … A A A A … A 1 2 3 n 1 2 3 n Tgia ms_nv ms_da nvu tgian 1.
Chỉ trả về các thuộc tính N1 D1 Quan ly 12 nvu và tgian. Phép chọn s N2 D1 Phan tich 24
j, i ³ j i 2.
Chỉ trả về thuộc tính ms_nv. ... N2 D2 Thiet ke 6 ... N3 D3 Phan tich 10 3.
Chỉ trả về thuộc tính ms_da. N3 D4 Tu van 48
Cho biết kết quả với mỗi trường N4 D2 Thiet ke 18 A hợp. 1 A2 A3 … An A1 A2… Ak N5 D2 Phan tich 24 N6 D4 Quan ly 48 p N7 D3 Lap trinh 36 Phép chiếu i
j, n ³ k N7 D5 Thiet ke 23 ... ...
i ³ j N8 D3 Quan ly 40 n k Bài 3 17 TH107 19 TH107 Bài 3 Ví dụ Phép chiếu
Kết hợp Phép Chọn và Phép Chiếu Nvien ms_nv ten_nv cvu luong Nvien ms_nv ten_nv cvu luong
Kết hợp các phép toán cho ra một Nvien cvu N1 T. Vu KS 30000 N1 T. Vu KS 30000 biểu thức quan hệ. KS N2 N. Thanh TK 40000 N2 N. Thanh TK 40000 p TK
ten_nv (sluong<50000 Nvien) N3 V. Minh PT 50000 N3 V. Minh PT 50000 s PT
luong<50000 (p ten_nv, luong Nvien)) N4 T.Tram KS 30000 N4 T.Tram KS 30000 KT
p ten_nv (sluong<50000 (p ten_nv, luong Nvien)) N5 P. Thao KT 45000 N5 P. Thao KT 45000 LT N6 M. Tuan KS 50000 N6 M. Tuan KS 50000
Cho biết các truy vấn nào tương p N7 T. Tam LT 60000 cvu (Nvien) N7 T. Tam LT 60000
đương trong số các truy vấn trên. N8 T. Thanh LT 55000 N8 T. Thanh LT 55000 s
Hai truy vấn được gọi là tương cvu=‘KS’ (Nvien)
đương nếu chúng bảo đảm trả về
cùng một kết quả truy vấn với bất
kỳ thể hiện CSDL nào. Bài 3 18 TH107 20 TH107 Bài 1 © Bui MT Diem, 2007 5 Các Phép toán Tập hợp Ví dụ
} Các phép toán chuẩn trên tập hợp cũng được áp Sinhvien Giaovien dụng trên quan hệ HT DC Ten Dchi
} Phép toán tập hợp là phép toán hai ngôi lấy hai Dinh Ba Tien 731 Tran Hung Dao, Q1, TP HCM Dinh Ba Tien 731 Tran Hung Dao, Q1, TP HCM
quan hệ R và S làm input và tạo ra một quan hệ Le Quynh Nhu 291 Ho Van Hue, QPN, TP HCM Tran Thanh Tam 543 Mai Thi Luu, Q1, TP HCM output.
Sinhvien Ç Giaovien
Sinhvien È Giaovien
} R(A1, A2,…, An), S(B1, B2,…, Bn) phải khả hợp (union HT DC HT DC
compatible), nghĩa là: Dinh Ba Tien 731 Tran Hung Dao, Q1, TP HCM Dinh Ba Tien 731 Tran Hung Dao, Q1, TP HCM
} R và S cùng cấp (cùng số lượng thuộc tính) Le Quynh Nhu 291 Ho Van Hue, QPN, TP HCM
} Với mọi i, dom(A Tran Thanh Tam 543 Mai Thi Luu, Q1, TP HCM
i) = dom(Bi)
} Các cột trong R và S phải có thứ tự sao cho thứ tự của
các thuộc tính giống nhau tương ứng ở cả hai quan hệ
Sinhvien - Giaovien Giaovien - Sinhvien HT DC HT DC Le Quynh Nhu 291 Ho Van Hue, QPN, TP HCM Tran Thanh Tam 543 Mai Thi Luu, Q1, TP HCM Bài 3 21 TH107 Bài 3 23 TH107 Các Phép toán Tập hợp Phép tích
} Các phép toán trên tập hợp hội (union), giao (intersection) và trừ
(difference) trên các quan hệ khả hợp R và S có ý nghĩa như sau:
} Giả sử A = {a, b, c} B = {1, 2} }
Phép hội: tất cả các bộ (loại bỏ bộ trùng) trong R, trong S hoặc cả hai
thì trong lý thuyết tập hợp, phép tích được định
} R È S = {t | t Î R Ú t Î S} nghĩa là: }
Phép giao: tất cả các bộ vừa có trong R vừa có trong S
} R Ç S = {t | t Î R Ù t Î S} }
Phép trừ: tất cả các bộ có trong R nhưng không có trong S
} R – S = {t | t Î R Ù t Ï S}
A ´ B = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}
trong đó R và S là các quan hệ, t là một biến bộ Lưu ý:
} A ´ B là một tập gồm có các cặp (2-tuples) trong
R – S ¹ S – R
đó mỗi cặp bao gồm một thành phần từ A và
R Ç S = R – (R – S) = S – (S – R) R S một thành phần từ B 22 TH107 Bài 3 24 TH107 Bài 1 © Bui MT Diem, 2007 6
Phép tích trong Lý thuyết Tập hợp Phép tích
} Giả sử A = {a, b, c} B = {1, 2} C = {x, y} thì
} Được sử dụng để định nghĩa quan hệ.
Một thể hiện của quan hệ là một tập con của
phép tích các miền giá trị.
A ´ B = {(a, 1), (b, 1), (c, 1), (a, 2), (b, 2), (c, 2)}
} Cũng là một phép toán trong đại số quan hệ. và (A ´ B) ´ C =
Ta sử dụng nó để truy vấn.
{((a,1),x), ((b,1),x), ((c,1),x), ((a,2),x), ((b,2),x), ((c,2),x),
((a,1),y), ((b,1),y), ((c,1),y), ((a,2),y), ((b,2),y), ((c,2),y)} 25 TH107 Bài 1 27 TH107 Bài 1
Đại số Quan hệ >< Lý thuyết Tập hợp (Phép tích) (tt.) Phép tích Cartesian
} Cho A = {a, b, c} B = {1, 2} C = {x, y}
Cartesian Product/ Cross product / Cross Join
với phép tích (A ´ B) ´ C trong lý thuyết tập hợp=
} Phép tích Cartesian của hai quan hệ R (có bậc k1)
{((a,1),x), ((b,1),x), ((c,1),x), ((a,2),x), ((b,2),x), ((c,2),x),
và S (có bậc k2) được ký hiệu là R ´ S
((a,1),y), ((b,1),y), ((c,1),y), ((a,2),y), ((b,2),y), ((c,2),y)} } Định nghĩa:
R ´ S = {t | t[A1, …, Ak1] Î R Ù t[Ak1, …, Ak1+k2] Î S}
Codd đơn giản nó trong đại số quan hệ thành:
} Kết quả của R ´ S là một quan hệ có bậc (k1 + k2)
{(a,1,x), (b,1,x), (c,1,x), (a,2,x), (b,2,x), (c,2,x), (a,1,y),
và bao gồm tất cả (k1 + k2)-tuples trong đó mỗi
(b,1,y), (c,1,y), (a,2,y), (b,2,y), (c,2,y)}
bộ là một phép ghép (concatenation) của một bộ
bằng cách lược bỏ các dấu ngoặc.
của R và một bộ của S.
} Số bộ (cardinality) của R ´ S là |R| * |S| 26 TH107 Bài 1 Bài 3 28 TH107 © Bui MT Diem, 2007 7 Pban.ms_pb ten_pb ms_tp ms_da ten_da nsach Dan.ms_pb P1 Quan ly N8 D1 Thiet bi 150000 P1 Ví dụ Ví dụ P1 Quan ly N8 D2 Phat trien CSDL 135000 P2 P1 Quan ly N8 D3 CAD/CAM 250000 P3 P1 Quan ly N8 D4 Bao tri 310000 P2 r s
r ´ s P1 Quan ly N8 D5 CAD/CAM 500000 P2 P2 Tu van N7 D1 Thiet bi 150000 P1 A B B C D A r.B s.B C D Temp P2 Tu van N7 D2 Phat trien CSDL 135000 P2 (Pban.ms_pb, P2 Tu van N7 D3 CAD/CAM 250000 P3 1 2 ´ 2 5 6 1 2 2 5 6 ten_pb, ms_tp, P2 Tu van N7 D4 Bao tri 310000 P2 3 4 4 7 8 1 2 4 7 8 P2 Tu van N7 D5 CAD/CAM 500000 P2 ms_da, ten_da, P3 Tai vu N5 D1 Thiet bi 150000 P1 9 10 11 1 2 9 10 11 nsach, P3 Tai vu N5 D2 Phat trien CSDL 135000 P2 3 4 2 5 6 Dan.ms_pb) ¬ P3 Tai vu N5 D3 CAD/CAM 250000 P3 3 4 4 7 8 Pban ´ Dan P3 Tai vu N5 D4 Bao tri 310000 P2 P3 Tai vu N5 D5 CAD/CAM 500000 P2 3 4 9 10 11 P4 Phat trien null D1 Thiet bi 150000 P1 P4 Phat trien null D2 Phat trien CSDL 135000 P2 P4 Phat trien null D3 CAD/CAM 250000 P3 P4 Phat trien null D4 Bao tri 310000 P2 P4 Phat trien null D5 CAD/CAM 500000 P2 Bài 3 29 TH107 Bài 3 31 TH107 Ví dụ
Ý nghĩa của Phép tích Cartesian Nvien ms_nv ten_nv cvu luong ms_pb Pban ms_pb ten_pb ms_tp
} Phép tích: Một bộ của một quan hệ lần lượt kết N1 T. Vu KS 30000 P1 P1 Quan ly N8
hợp với một bộ của quan hệ kia N2 N. Thanh TK 40000 P2 P2 Tu van N7 N3 V. Minh PT 50000 P1 P3 Tai vu N5 } Thường thấy hơn, N4 T.Tram KS 30000 P3 P4 Phat trien null
} thay vì đơn giản là tích hai quan hệ, thì nhu cầu kết N5 P. Thao KT 45000 P4
chúng thành cặp chỉ theo các bộ khớp với nhau theo N6 M. Tuan KS 50000 P4 cách nào đó. N7 T. Tam LT 60000 P2 N8 T. Thanh LT 55000 null Dan ms_da ten_da nsach ms_pb D1 Thiet bi 150000 P1 D2 Phat trien CSDL 135000 P2 D3 CAD/CAM 250000 P3 D4 Bao tri 310000 P2 D5 CAD/CAM 500000 P2 30 TH107 Bài 2 Bài 3 32 TH107 © Bui MT Diem, 2007 8 Phép Kết Ra đời
Phép Kết: Để Thuận tiện } Giới hạn lại:
} Lưu ý: Phép kết R
A1=A2 S, trong đó A1 là một
} kết hợp từng phòng và dự án tương ứng mà phòng ban
thuộc tính của quan hệ R và A2 là một thuộc tính
đó chủ trì: có thể thực hiện trực tiếp bằng cách dùng
của quan hệ S, được định nghĩa là sA1=A2 (R ´ S)
phép kết, không cần dùng đến phép tích
} Do đó, thực sự ta không “cần” phép kết. Bất kỳ Pban ms_pb ten_pb ms_tp Dan ms_da ten_da nsach ms_pb P1 Quan ly N8 D1 Thiet bi 150000 P1
truy vấn nào cần diễn đạt, ta luôn dùng ´ và s. P2 Tu van N7 D2 Phat trien CSDL 135000 P2
} Nhưng vì phép kết được dùng rất thường xuyên, P3 Tai vu N5 D3 CAD/CAM 250000 P3
nên nó được định nghĩa như là một phép toán, P4 Phat trien null D4 Bao tri 310000 P2 D5 CAD/CAM 500000 P2 để thuận tiện.
spban.ms_pb=dan.ms_pb(Pban ´ Dan) tương đương với Pban
pban.ms_pb=dan.ms_pb Dan Bài 3 33 TH107 35 TH107 Bài 1 Pban.ms_pb ten_pb ms_tp ms_da ten_da nsach Dan.ms_pb P1 Quan ly N8 D1 Thiet bi 150000 P1 Ví dụ P1 Quan ly N8 D2 Phat trien CSDL 135000 P2
Phép kết … với 6 phép so sánh P1 Quan ly N8 D3 CAD/CAM 250000 P3 P1 Quan ly N8 D4 Bao tri 310000 P2 } Svien ms_sv=ms_gv Gvien P1 Quan ly N8 D5 CAD/CAM 500000 P2 P2 Tu van N7 D1 Thiet bi 150000 P1 } Svien
Svien.tuoi>Gvien.tuoi Gvien Pban.ms_pb ten_pb ms_tp ms_da ten_da nsach Dan.ms_pb P2 Tu van N7 D2 Phat trien CSDL 135000 P2 P1 Quan ly N8 D1 Thiet bi 150000 P1 } Svien P2 Tu van N7 D3 CAD/CAM 250000 P3
Svien.luong≥Gvien.luong Gvien P2 Tu van N7 D2 Phat trien CSDL 135000 P2 P2 Tu van N7 D4 Bao tri 310000 P2 } … P2 Tu van N7 D4 Bao tri 310000 P2 P2 Tu van N7 D5 CAD/CAM 500000 P2 P2 Tu van N7 D5 CAD/CAM 500000 P2 P3 Tai vu N5 D1 Thiet bi 150000 P1
} Phép kết đôi khi còn được gọi là q-Kết, trong đó P3 Tai vu N5 D3 CAD/CAM 250000 P3 P3 Tai vu N5 D2 Phat trien CSDL 135000 P2
q đại diện cho một trong 6 phép so sánh. P3 Tai vu N5 D3 CAD/CAM 250000 P3 P3 Tai vu N5 D4 Bao tri 310000 P2 P3 Tai vu N5 D5 CAD/CAM 500000 P2 P4 Phat trien null D1 Thiet bi 150000 P1 P4 Phat trien null D2 Phat trien CSDL 135000 P2 P4 Phat trien null D3 CAD/CAM 250000 P3 P4 Phat trien null D4 Bao tri 310000 P2 P4 Phat trien null D5 CAD/CAM 500000 P2 34 TH107 Bài 3 36 TH107 Bài 1 © Bui MT Diem, 2007 9 Phép q-Kết Các loại Phép Kết q-Join
} q-Kết là một phép kết tổng quát trong đó nó cho phép bất kỳ biểu
thức nào trong điều kiện F.
} Theta (q) kết là một dạng phát triển từ phép tích
} Tuy nhiên, có các phép kết đặc biệt hơn thường được sử dụng.
Cartesian. Thay vì lấy tất cả các phối hợp của các bộ
từ R và S, ta chỉ lấy tập con của các bộ thỏa mãn điều
Phép kết bằng (equi-join)
Phép kết tự nhiên (natural join)
kiện F cho trước, q-Kết được ký hiệu là R F S } R } R * S F S } Định nghĩa:
} chỉ có phép bằng (=) trong
} chỉ có phép bằng (=) trên một R điều kiện F.
tập thuộc tính cùng tên của cả
F S= {t | t[A1, …, Ak1] Î R Ù t[Ak1, …, Ak1+k2] Î S Ù F(t)} trong đó R và S.
} kết quả trả về có các thuộc tính
} R và S là các quan hệ, t là một biến bộ
kết của R và S. Thuộc tính kết S
} các thuộc tính kết dư thừa của
xuất hiện lặp lại (dư thừa) trong
S sẽ bị loại bỏ khỏi quan hệ kết
} F(t) là một công thức được định nghĩa như là điều kiện của việc chọn quan hệ kết quả. quả. } Lưu ý: R
F S = sF (R ´ S) Bài 3 37 TH107 39 TH107 Bài 3 Ví dụ Ví dụ Cho các quan hệ R S u v
R(A, B) và S(B, C, D). A B B C D A B C D Cho biết R * S A B C B C D 1 2 2 5 6 1 2 5 6 * 1 2 3 2 3 4 3 4 4 7 8 3 4 7 8 6 7 8 2 3 5 A9 10 11 9 7 8 7 8 10
Lược đồ kết quả là (A, B, C, D)
Kết quả của R * S được định nghĩa là A u.B u.C v.B v.C D 1 2 3 7 8 10
p R.A, R.B, S.C, S.D ((s R.B = S.B (R ´ S)) 38 TH107 Bài 1 40 TH107 Bài 1 © Bui MT Diem, 2007 10
Tại sao cần Phép Đổi tên? Ví dụ
} Để giải quyết tình huống nhập nhằng tên thuộc tính } Xét quan hệ Nvien(ms_nv, Nvien ms_nv ten_nv cvu luong ms_pb
} Đối với phép hội, phép trừ, phép kết tự nhiên, quan hệ kết quả sẽ ten_nv, cvu, luong, ms_pb) N1 T. Vu KS 30000 P1
lấy tên thuộc tính của quan hệ đầu tiên N2 N. Thanh TK 40000 P2
} Cho biết tên các nhân viên cùng
} Đối với phép tích, các thuộc tính được đặt tên theo cách: Tên-
phòng với nhân viên V. Minh. N3 V. Minh PT 50000 P1
qh.tên.tt, trong đó tên quan hệ được lấy từ quan hệ của thuộc tính N4 T.Tram KS 30000 P3
} Khi cùng một quan hệ xuất hiện nhiều lần trong một truy N5 P. Thao KT 45000 P4
vấn, sẽ giải quyết như thế nào? p 1 2 N6 M. Tuan KS 50000 P4
ms_pb (sten_nv=‘V. Minh’ Nvien) N7 T. Tam LT 60000 P2
sP (Nvien ´ p ms_pb (sten_nv=‘V. Minh’ Nvien) N8 T. Thanh LT 55000 null
Cho quan hệ R(A,B). Xét R ´ R
1 Tìm (các) phòng ban mà V. Minh làm việc
Tên của thuộc tính trong quan hệ kết quả?
2 Tìm tất cả các nhân viên làm việc ở phòng trên, ta cần tham chiếu
đến quan hệ Nvien một lần nữa.
Nếu ta sử dụng Nvien.mp trong P thì nó lại nhập nhằng với thể hiện
của quan hệ Nvien trong truy vấn mà thuộc tính tham chiếu tới. 41 TH107 Bài 3 43 TH107 Bài 1 Phép Đổi tên Ví dụ Phép Đổi tên Rename Operation 1
} Trả về một quan hệ với tên mới tên-qh-mới r
pten_nv(sNvien.ms_pb=M.ms_pb (Nvien ´ (pms_pb (sten_nv=‘V. Minh’ (rM(Nvien))))
tên-qh-mới(biểu-thức-quan-hệ)
} Trả về một quan hệ trong đó đổi tên các thuộc p tính tương ứng thành A ten_nv(Nvien
Nvien.ms_pb=M.ms_pb (pms_pb (sten_nv=‘V. Minh’ (rM(Nvien)))) 1, A2, …, An
rA1, A2, …, An(biểu-thức-quan-hệ) 2
} Trả về một quan hệ trong đó đổi tên các thuộc
tính tương ứng thành A1, A2, …, An với tên mới tên-qh-mới
1 Để tránh nhập nhằng, sử dụng phép đổi tên
rtên-qh-mới(A1, A2, …, An)(biểu-thức-quan-hệ)
2 Sử dụng phép kết thay cho phép tích và phép chọn
} Đơn giản hóa sử dụng phép gán:
tên-qh-mới(A1, A2, …, An) ¬ biểu-thức-quan-hệ 42 TH107 Bài 1 44 TH107 Bài 1 © Bui MT Diem, 2007 11 Câu hỏi Thực hành Phép chia Division Operator
} Cho : Nhanvien(tennv, manv, ma_nql, phg), Phongban
(tenphg, maphg, trphg), Thannhan(ma_nvien, tentn)
} Phép chia trên hai quan hệ R (A1, …, Am, B1, …, Bn) 1.
Tên nhân viên và tên người quản lý trực tiếp nhân viên đó
và S (B1, …, Bn), được ký hiệu là R ¸ S 2.
Tên nhân viên và tên phòng mà nhân viên làm việc
Tên trưởng phòng và tên phòng mà người đó là trưởng phòng
} Các thuộc tính của S là một tập thuộc tính con của R. 3.
Tên những trưởng phòng có ít nhất một thân nhân
} Định nghĩa: Kết quả phép chia R ¸ S là 1 quan hệ 4.
Tên nhân viên không có thân nhân
trên lược đồ R – S = (A1, …, Am)
1 Một quan hệ có thể có một tập thuộc tính kết để kết với chính quan hệ đó R Þ
¸ S = {t | t Î p A1, …, Am(R) Ù ("u Î S ($(t, u) Î R)) }
phải sử dụng phép đổi tên.
} R ¸ S, với các thuộc tính A , …, A 1
m, là một tập hợp chứa
Giữa 2 quan hệ có thể có nhiều hơn một tập thuộc tính kết mang ý nghĩa 2
tất cả các bộ t sao cho với mọi bộ u trong S, thì có một khác nhau.
bộ <t u> trong R.
3 Phép kết hay phép giao? 4 Phép trừ? 45 TH107 Bài 3 Bài 3 47 TH107 Tìm “Tất cả” Ví dụ Phép chia
} Cho biết kết quả trả về ứng với các truy vấn sau: CC Sp1 Sp2 Sp3 1.
Cho biết mã nhân viên tham gia đề án. mancc masp masp masp masp 2.
Cho biết mã nhân viên tham gia ít nhất một đề án. c1 s1 s2 s2 s1 3.
Cho biết mã nhân viên tham gia tất cả các đề án. c1 s2 s4 s2 4.
Cho biết mã nhân viên tham gia tất cả các đề án do phòng 4 c1 s3 s4 chủ trì. c1 s4 c2 s1
CC ¸ Sp1
CC ¸ Sp2
CC ¸ Sp3 c2 s2
Ta có thể sử dụng phép chia cho các truy vấn có từ “tất cả” (for all) mancc c3 s2 mancc mancc Zero Division? c1 c4 s2 c1 c1 c2 c4 s4 c4 c3 c4 46 TH107 Bài 3 © Bui MT Diem, 2007 12 Ví dụ Phép chia Ví dụ: Dạng 1 & 2 Phancong Dean Deanp4
} Xét quan hệ Nhanvien(honv,tenlot,tennv,manv,luong,phg) ma_nvien mada 999887777 30 mada mada
} Liệt kê họ tên và lương nhân viên làm việc ở phòng số 4. 123456789 1 999887777 10 1 10
p honv, tenlot, tennv, luong ( s phg (Nhanvien) ) = 4 1 123456789 2 987987987 10 2 30 Nv_p4 ¬ s (Nhanvien) 666884444 3 987987987 30 3 phg = 4 2 Kq ¬ p 453453453 1 987987987 1 10
honv, tenlot, tennv, luong (Nv_p4) 453453453 2
Phancong¸ Dean 987654321 30 20 Nv_p4 ¬ sphg (Nhanvien) = 4 3 333445555 2 987654321 20 30 ma_nvien
Kq (ho, lot, ten, luongcb) ¬ p honv, tenlot, tennv, luong (Nv_p4) 333445555 3 888665555 20 1 Dạng lồng 333445555 10
Phancong¸ p (s Dean) mada phong=4 333445555 20
2 Chuỗi các phép gán ma_nvien 999887777
3 hoặc đổi tên bằng cách liệt kê tên thuộc tính mới trong dấu ngoặc 987987987 51 TH107 Bài 1
Xây dựng các Biểu thức Phức tạp
Thứ tự Thực hiện Phép toán
} Kết hợp các phép toán ĐSQH bằng cách sử dụng dấu
1. các phép toán một ngôi: s, p, r
ngoặc và các quy tắc về thứ tự ưu tiên Lồng và dấu ngoặc } 3 loại ký hiệu:
2. phép tích Cartesian và phép kết: ´, 1.
Dạng lồng: Tạo một biểu
• kết quả của một phép toán ĐSQH
thức ĐSQH bằng cách lồng là một quan hệ
3. phép giao, phép chia: Ç, ¸ các phép toán với nhau
• các phép toán ĐSQH có thể được
lồng ghép nhau như các hàm 2. Chuỗi các phép gán: Áp
• biểu diễn dấu ngoặc để diễn đạt
dụng tuần tự từng phép
4. phép hội và phép trừ: È, -
thứ tự thực hiện phép toán
toán một, ở mỗi lần áp
dụng phép toán đặt tên
Dấu ngoặc có thể được dùng để thay đổi thứ tự Chuỗi các Phép Gán cho quan hệ trung gian của các phép toán.
bằng cách thực hiện việc
• Tạo các tên quan hệ tạm gán tên
• Có thể thực hiện việc ngầm đổi
tên bằng cách liệt kê các thuộc 3. Biểu diễn dạng cây tính 50 TH107 Bài 3 52 TH107 Bài 3 © Bui MT Diem, 2007 13 Dạng 3: Cây Biểu thức Ví dụ: Dạng 3 } Nút lá: là các operands } Xét quan hệ pma_nvien
} biến đại diện cho các quan hệ, trong trường hợp đặc Phancong(ma_nvien, soda,
biệt có thể là các quan hệ hằng thoigian)
} Liệt kê mã nhân viên tham s
} Nút trong: là các phép toán, áp dụng cho (các) d<>soda
gia các đề án khác nhau với nút con. cùng thời gian. * rP(ma_nvien, d, Phancong thoigian) Phancong 53 TH107 Bài 1 55 TH107 Bài 1 Ví dụ: Dạng 3 Các Phép toán mở rộng } Xét quan hệ È } Phép chiếu mở rộng Thannhan(ma_nvien, tentn, ngaysinh, quanhe), } Grouping và aggregation Phancong(ma_nvien, soda), } Outer join
} Liệt kê mã nhân viên có con p p ma_nvien ma_nvien
hoặc nhân viên tham gia đề án. squanhe=‘con trai’ Phancong Ú quanhe=‘con gai’ Thannhan 54 TH107 Bài 1 56 TH107 Bài 1 © Bui MT Diem, 2007 14 Phép Chiếu Mở rộng Hàm Kết hợp và Gom nhóm
} Sử dụng như phép chiếu p
} Hàm kết hợp - Aggregate Functions nhận vào tập hợp
L . Thay vì L chỉ liệt kê
danh sách các thuộc tính, thì L có thể chứa các
giá trị và trả về một giá trị đơn.
avg(average value): giá trị trung bình
biểu thức số học liên quan đến các thuộc tính,
min(minimum value): giá trị nhỏ nhất chẳng hạn:
max(maximum value): giá trị lớn nhất 1.
các biểu thức trên thuộc tính, vd. A+B
sum (sum of values): tính tổng
count (number of values): đếm số mẫu tin 2.
xuất hiện trùng các thuộc tính } Định nghĩa: p F (E) 1, F2, …, Fk
} trong đó E là biểu thức đại số quan hệ SUM(A) = 7 R = ( A B )
} F , F , …, F COUNT(A) = 3 1 2 1 2
k là các biểu thức số học có liên quan đến
hằng và thuộc tính trong lược đồ E. MAX(B) = 4 3 4 AVG(B) = 3 3 2 Bài 3 57 TH107 59 TH107 Bài 3 Ví dụ Hàm Kết hợp và Gom nhóm Vd1 Vd2
} Phép toán gom nhóm - Grouping ℱ trong Đ } Cho quan hệ SQH: Thetindung(msthe, trigiathe, R = ( A B ) ℱ sotiensd) 1 2
G1, G2, …, Gn
F1 (A1), F2 (A2), …, Fn (An) (E)
} E là biểu thức đại số quan hệ
} Tìm số tiền còn lại trong thẻ 3 4 p
} Gi là tên thuộc tính gom nhóm (có thể không có) msthe, trigiathe - sotiensd (Thetindung) } Fi là hàm gom nhóm p A+B A1 A2
A+B,A,A (R) = ( )
} A là tên thuộc tính tính toán trong hàm gom nhóm F i i 3 1 1
} Kết quả có một bộ ứng với mỗi nhóm: 7 3 3 1.
Các thuộc tính gom nhóm và 2.
Kết quả của các hàm kết hợp thực hiện trên nhóm đó 58 TH107 Bài 3 Bài 3 60 TH107 © Bui MT Diem, 2007 15 Ví dụ: Outer Join Count_manv Avg_luong 1 } Có ba loại kết ngoài:
} Xét quan hệ Nhanvien(honv, 8 35125 tenlot, tennv, manv, luong,
} Left outer join: R P S ma_nql, phg). Cho biết:
} Kết quả sẽ chứa tất cả các bộ của R khớp với các bộ của S. Với manv … luong ma_nql phg
một bộ thuộc R, nếu không tìm thấy bộ nào khớp với S, thì các 1.
Tổng số nhân viên của công
bộ này cũng được xuất hiện trong kết quả cuối cùng và giá trị 123456789 … 30000 333445555 5 ty và lương trung bình.
thuộc tính tương ứng của S sẽ được đặt là null. 333445555 … 40000 888665555 5 2. Số lượng nhân viên và } Right outer join: R P S 666884444 … 38000 333445555 5
lương trung bình của nhân
} Kết quả sẽ chứa tất cả các bộ của S khớp với các bộ của R. Với viên theo từng phòng
một bộ thuộc S, nếu không tìm thấy bộ nào khớp với R, thì các 453453453 … 25000 333445555 5
bộ này cũng được xuất hiện trong kết quả cuối cùng và giá trị 999887777 … 25000 987654321 4
thuộc tính tương ứng của R sẽ được đặt là null 1 ℱ (Nhanvien) COUNT(manv), AVG(luong) 987654321 … 43000 888665555 4 } Full outer join: R P S ℱ 2 (Nhanvien) phg COUNT(manv), AVG(luong)
} Tất cả các bộ của R và S đều có trong kết quả cho dù chúng có 987987987 … 25000 987654321 4
bộ khớp với quan hệ kia hay không. phg Count_manv Avg_luong 888665555 … 55000 Null 1 5 4 33250 2 4 3 31000 1 1 55000 61 TH107 Bài 1 Bài 3 63 TH107 Outer Join Ví dụ
} Giả sử cần thực hiện phép kết R S. P } p (Nhanvien Phongban) honv, tenlot, tennv, tenphg manv = trphg
} Một bộ của R mà không có bộ trong S để thực hiện phép } p (Nhanvien Phongban)
kết thì gọi là “dangling” (“mồ côi”) honv, tenlot, tennv, tenphg manv = trphg } p (s (Nhanvien } tương tự đối với S honv, tenlot, tennv, tenphg tenphg <> null manv = trphg Phongban))
} Phép kết ngoài (Outer join) bảo đảm giữ các bộ “mồ côi”
bằng cách thêm vào giá trị NULL trong kết quả. honv tenlot tennv tenphg honv tenlot tennv tenphg Dinh Ba Tien Null Nguyen Thanh Tung Nghien Cuu Nguyen Thanh Tung Nghien cuu Tran Hong Quang Dieu Hanh Bui Ngoc Hang Null R = ( A B ) S = ( B C ) R S = ( A B C ) Pham Van Vinh Quan Ly Le Quynh Nhu Null 1 2 2 3 1 2 3 Nguyen Manh Hung Null 4 5 6 7 4 5 Null Tran Thanh Tam Null Null 6 7 Tran Hong Quang Dieu hanh Pham Van Vinh Quan ly 62 TH107 Bài 1 64 TH107 Bài 1 © Bui MT Diem, 2007 16 Dàn bài Thêm
} Ngôn ngữ Truy vấn trong Mô hình Quan hệ
} Hoặc nêu ra một bộ cần chèn, hoặc viết một câu truy vấn
mà kết quả là một tập hợp các bộ cần chèn
} Các Phép toán Đại số Quan hệ
} Trong ĐSQH, thao tác chèn được diễn đạt như sau: } Các Thao tác Cập nhật
r ¬ r È E
trong đó r là một quan hệ và E là một biểu thức ĐSQH. Vd.,
´Phân công cho nhân viên 123456789 làm thêm đề án mã số 20 với số giờ 10.
Phancong ¬ Phancong È {(‘123456789’, 20,10)} Bài 3 65 TH107 67 TH107 Bài 3
Thao tác Cập nhật trên Quan hệ Xóa
} Nội dung của CSDL có thể được cập nhật bằng
} Yêu cầu xóa được diễn đạt tương tự như câu truy vấn, chỉ khác
ở chỗ, thay vì hiển thị các bộ kết quả với người sử dùng, thì
cách dùng các thao tác Thêm, Xóa, Sửa
các bộ được chọn bị xóa khỏi CSDL.
} Tất cả các thao tác này được diễn đạt thông qua
} Chỉ có thể xóa toàn bộ bộ, không thể xóa các giá trị trên các phép toán gán. thuộc tính nào đó.
} Thao tác xóa được diễn đạt trong ngôn ngữ ĐSQH như sau:
r new ¬ các phép toán trên (rold)
r ¬ r – E
trong đó r là một quan hệ và E là một câu truy vấn ĐSQH.
´Xóa tất cả những phân công đề án cho nhân viên 123456789
Phancong ¬ Phancong – (s ma_nvien = ‘123456789’ (Phancong))
´Xóa tất cả những phân công đề án mà địa điểm đề án ở “HA NOI”
r1 ¬ s ddiem_da = ‘Ha Noi’ (Phancong soda = mada Dean)
r2 ¬ p ma_nv, soda, thoigian (r1)
Phancong ¬ Phancong – r2 Bài 3 66 TH107 68 TH107 Bài 3 © Bui MT Diem, 2007 17 Sửa
Tại sao ta sử dụng ĐSQH?
} Để cập nhật, sử dụng phép chiếu tổng quát hóa như sau:
} Được định nghĩa một cách toán học (trong đó quan hệ là r ¬ p tập hợp) F (r) 1, F2, …, Fn
mỗi Fi có giá trị trả về là giá trị mới cho thuộc tính thứ i của r, thuộc
} Được dùng bên trong các HQTCSDL
tính thứ i có thể giữ nguyên (nếu không muốn cập nhật) hoặc sẽ
} Có thể chứng minh hai biểu thức quan hệ tương đương
được cập nhật với giá trị mới đó.
} Fi là một biểu thức, bao gồm hằng và thuộc tính của r, để đưa ra
giá trị mới cho thuộc tính đó. Vd., s (s R) º s (s R) º s R cond1 cond2 cond2 cond1 cond1 Ù cond2
´Tăng thời gian làm việc của tất cả nhân viên lên 1.5 lần º (s R) Ç (s R) cond1 cond2
Phancong ¬ p ma_nv, soda, thoigian * 1.5 (Phancong) R1 R2 º s (R1 cond cond ´ R2) s R º (s R) R) cond1 È (s Ú cond2 cond1 cond2 69 TH107 Bài 3 71 TH107 Bài 3
Tập Đầy đủ các Phép toán ĐSQH “AND”, “OR”, “NOT”
} Tất cả các phép toán được thảo luận ở trên có thể được s
mô tả dựa trên 5 phép toán cơ sở như {
cond1 Úcond2 R º (s cond1 R) È (s cond2 R) s, p, È, -, ´}
→ tập hợp {s, p, È, -, ´} được gọi là tập đầy đủ các phép toán ĐSQH
s cond1 Ù cond2 R º (s cond1 R) Ç (s cond2 R)
s cond1 Ù Øcond2 R º (s cond1 R) – (s cond2 R)
R Ç S = R - (R - S) R P S = s P (R ´ S) R *P S = p (s ttinh P (R ´ S))
R ¸ S = pA (R) - pA ((pA (R) ´ S) - R) 70 TH107 Bài 3 72 TH107 Bài 1 © Bui MT Diem, 2007 18 Kết luận
} Đại số quan hệ: là một tập hợp các phép toán để
ánh xạ quan hệ thành quan hệ.
} Operational, theo nghĩa ta phải mô tả tường minh thứ
tự thực hiện của các phép toán
} Là một tập phép toán đóng! Có thể ghép phép toán.
} Các phép toán cơ sở gồm có: s, p, ´, È, -
} Các phép toán khác định nghĩa trên các phép
toán cơ sở: Ç, , ¸ Bài 3 73 TH107 © Bui MT Diem, 2007 19