Bài giảng Cơ sở dữ liệu - Chương 6: Phép tính quan hệ - Nguyễn Minh Thu

Chương 6 
Phép tính quan hệ 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 2 
Nội dung chi tiết 
 Giới thiệu 
 Phép tính quan hệ trên bộ 
 Phép tính quan hệ trên miền 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 3 
Giới thiệu 
Maths 
Algebra 
Logic 
Relational Algebra 
Relational Calculus 
1970 
1972 
ACM 
Turing 
Award 
1981 Codd 
Database 
Geometry 
??? ??? 
Award 
Other fields 
2??? 
2??? 
YOU 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 4 
Giới thiệu (tt) 
 Là ngôn ngữ truy vấn hình thức 
 Do Codd đề nghị vào năm 1972, “Data Base 
Systems”, Prentice Hall, p33-98 
 Đặc điểm 
- Phi thủ tục 
- Dựa vào lý thuyết logic 
- Rút trích cái gì (what) rút trích như thế nào (how) 
- Khả năng diễn đạt tương đương với ĐSQH 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 5 
Giới thiệu (tt) 
 Có 2 loại 
- Phép tính quan hệ trên bộ (Tuple Rational Calculus) 
 SQL 
- Phép tính quan hệ trên miền (Domain Rational Calculus) 
 QBE (Query By Example) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 6 
Nội dung chi tiết 
 Giới thiệu 
 Phép tính quan hệ trên bộ 
 Phép tính quan hệ trên miền 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 7 
Phép tính quan hệ trên bộ 
 Biểu thức phép tính quan hệ trên bộ có dạng 
- t là biến bộ 
 Biến nhận giá trị là một bộ của quan hệ trong CSDL 
 t.A là giá trị của bộ t tại thuộc tính A 
- P là công thức có liên quan đến t 
 P(t) có giá trị ĐÚNG hoặc SAI phụ thuộc vào t 
- Kết quả trả về là tập các bộ t sao cho P(t) đúng 
{ t.A | P(t) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 8 
Ví dụ 1 
 Tìm các nhân viên có lương trên 30000 
- t NHANVIEN đúng 
 Nếu t là một thể hiện của quan hệ NHANVIEN 
- t.LUONG > 30000 đúng 
 Nếu thuộc tính LUONG của t có giá trị trên 30000 
{ t | t NHANVIEN  t.LUONG > 30000 } 
P(t) P(t) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 9 
Ví dụ 2 
 Cho biết mã và tên nhân viên có lương trên 30000 
- Tìm những bộ t thuộc NHANVIEN có thuộc tính lương 
lớn hơn 30000 
- Lấy ra các giá trị tại thuộc tính MANV và TENNV 
- Tập các MANV và TENNV của những bộ t sao cho t là 
một thể hiện của NHANVIEN và t có giá trị lớn hơn 
30000 tại thuộc tính LUONG 
{ t.MANV, t.TENNV | t NHANVIEN  t.LUONG > 30000 } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 10 
Ví dụ 3 
 Cho biết các nhân viên (MANV) làm việc ở phòng 
‘Nghien cuu’ 
- Lấy ra những bộ t thuộc NHANVIEN 
- So sánh t với một bộ s nào đó để tìm ra những nhân 
viên làm việc ở phòng ‘Nghien cuu’ 
- Cấu trúc “tồn tại” của phép toán logic 
s PHONGBAN  s.TENPHG ‘Nghien cuu’ 
t.MANV | t NHANVIEN 
t R (Q(t)) 
Tồn tại 1 bộ t thuộc quan hệ R sao cho vị từ Q(t) đúng 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 11 
Q(s) 
Ví dụ 3 
 Cho biết các nhân viên (MANV) làm việc ở phòng 
‘Nghien cuu’ 
{ t.MANV | t NHANVIEN  
 s PHONGBAN ( 
 s.TENPHG ‘Nghien cuu’  
 s.MAPHG t.PHG ) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 12 
Ví dụ 4 
 Cho biết tên các nhân viên (TENNV) tham gia làm 
đề án hoặc có thân nhân 
{ t.TENNV | t NHANVIEN  ( 
 s PHANCONG (t.MANV s.MA_NVIEN)  
 u THANNHAN (t.MANV u.MA_NVIEN)) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 13 
Ví dụ 5 
 Cho biết tên các nhân viên (TENNV) vừa tham gia 
làm đề án vừa có thân nhân 
{ t.TENNV | t NHANVIEN  ( 
 s PHANCONG (t.MANV s.MA_NVIEN)  
 u THANNHAN (t.MANV u.MA_NVIEN)) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 14 
Ví dụ 6 
 Cho biết tên các nhân viên (TENNV) tham gia làm 
đề án mà không có thân nhân nào 
{ t.TENNV | t NHANVIEN  
 s PHANCONG (t.MANV s.MA_NVIEN)  
  u THANNHAN (t.MANV u.MA_NVIEN) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 15 
Ví dụ 7 
 Với mỗi đề án ở ‘TP HCM’ cho biết mã đề án, mã 
phòng ban chủ trì và tên người trưởng phòng 
{ s.MADA, s.PHONG, t.TENNV | s DEAN  t NHANVIEN  
 s.DDIEM_DA ‘TP HCM’  
 u PHONGBAN (s.PHONG u.MAPHG  
 u.TRPHG t.MANV) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 16 
Ví dụ 8 
 Tìm các nhân viên (MA_NVIEN) tham gia vào tất cả 
các đề án 
- Cấu trúc “với mọi” của phép toán logic 
t R (Q(t)) 
Q đúng với mọi bộ t thuộc quan hệ R 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 17 
Ví dụ 8 (tt) 
 Tìm các nhân viên (MANV, HONV, TENNV) tham 
gia vào tất cả các đề án 
{ t.MANV, t.HONV, t.TENNV | t NHANVIEN  
 s DEAN ( u PHANCONG ( 
 u.SODA s.MADA  
 t.MANV u.MA_NVIEN )) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 18 
Ví dụ 9 
 Tìm các nhân viên (MANV, HONV, TENNV) tham 
gia vào tất cả các đề án do phòng số 4 phụ trách 
- Cấu trúc “kéo theo” của phép tính logic 
P Q 
Nếu P thì Q 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 19 
Ví dụ 9 (tt) 
 Tìm các nhân viên (MANV, HONV, TENNV) tham 
gia vào tất cả các đề án do phòng số 4 phụ trách 
{ t.MANV, t.HONV, t.TENNV | t NHANVIEN  
 s DEAN ( 
 s.PHONG = 4 ( u PHANCONG ( 
 u.SODA s.MADA  
 t.MANV u.MA_NVIEN ))) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 20 
Định nghĩa hình thức 
 Một công thức truy vấn tổng quát có dạng 
- t1, t2, , tn là các biến bộ 
- Ai, Aj, , Ak là các thuộc tính trong các bộ t tương ứng 
- P là công thức 
 P được hình thành từ những công thức nguyên tố 
{ t1.Ai, t2.Aj, tn.Ak | P(t1, t2, , tn) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 21 
Biến bộ 
 Biến tự do (free variable) 
 Biến kết buộc (bound variable) 
{ t | t NHANVIEN  t.LUONG > 30000 } 
t là biến tự do 
{ t | t NHANVIEN  s PHONGBAN (s.MAPHG t.PHG) } 
Biến kết buộc Biến tự do 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 22 
Công thức nguyên tố 
 (i) 
- t là biến bộ 
- R là quan hệ 
 (ii) 
- A là thuộc tính của biến bộ t 
- B là thuộc tính của biến bộ s 
-  là các phép so sánh , , , , , 
 (iii) 
- c là hằng số 
- A là thuộc tính của biến bộ t 
-  là các phép so sánh , , , , , 
t R 
t.A  s.B 
t.A  c 
t NHANVIEN 
t.MANV = s.MANV 
s.LUONG > 30000 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 23 
Công thức nguyên tố (tt) 
 Mỗi công thức nguyên tố đều mang giá trị ĐÚNG 
hoặc SAI 
- Gọi là chân trị của công thức nguyên tố 
 Công thức (i) 
- Chân trị ĐÚNG nếu t là một bộ thuộc R 
- Chân trị SAI nếu t không thuộc R 
A B 
R 
10 
20 
C 
1 
1 
t1 = 
t2 = 
t1 R có chân trị ĐÚNG 
t2 R có chân trị SAI 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 24 
Công thức nguyên tố (tt) 
 Công thức (ii) và (iii) 
- Chân trị tùy thuộc vào việc thay thế giá trị thật sự của bộ 
vào vị trí biến bộ 
A B 
R 
10 
20 
C 
1 
1 
Nếu t là bộ 
Thì t.B > 5 có chân trị ĐÚNG (10 > 5) 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 25 
Qui tắc 
 (1) Mọi công thức nguyên tố là công thức 
 (2) Nếu P là công thức thì 
- P là công thức 
- (P) là công thức 
 (3) Nếu P1 và P2 là các công thức thì 
- P1  P2 là công thức 
- P1  P2 là công thức 
- P1 P2 là công thức 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 26 
Qui tắc (tt) 
 (4) Nếu P(t) là công thức thì 
- t R (P(t)) là công thức 
 Chân trị ĐÚNG khi P(t) ĐÚNG với mọi bộ t trong R 
 Chân trị SAI khi có ít nhất 1 bộ làm cho P(t) SAI 
- t R (P(t)) là công thức 
 Chân trị ĐÚNG khi có ít nhất 1 bộ làm cho P(t) ĐÚNG 
 Chân trị SAI khi P(t) SAI với mọi bộ t trong R 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 27 
Qui tắc (tt) 
 (5) Nếu P là công thức nguyên tố thì 
- Các biến bộ t trong P là biến tự do 
 (6) Công thức P=P1P2 , P=P1P2 , P=P1 P2 
- Sự xuất hiện của biến t trong P là tự do hay kết buộc 
phụ thuộc vào việc nó là tự do hay kết buộc trong P1, P2 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 28 
Một số biến đổi 
 (i) P1  P2 =  (P1  P2) 
 (ii) t R (P(t)) = t R (P(t)) 
 (iii) t R (P(t)) = t R (P(t)) 
 (iv) P Q = P  Q 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 29 
Công thức an toàn 
 Xét công thức 
- Có rất nhiều bộ t không thuộc quan hệ NHANVIEN 
- Thậm chí không có trong CSDL 
- Kết quả trả về không xác định 
 Một công thức P gọi là an toàn nếu các giá trị trong 
kết quả đều lấy từ miền giá trị của P 
- Dom(P) 
- Tập các giá trị được đề cập trong P 
{ t | (t NHANVIEN) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 30 
Công thức an toàn (tt) 
 Ví dụ 
- Dom(t NHANVIEN  t.LUONG > 30000) 
- Là tập các giá trị trong đó 
 Có giá trị trên 30000 tại thuộc tính LUONG 
 Và các giá trị khác tại những thuộc tính còn lại 
- Công thức trên là an toàn 
{ t | t NHANVIEN  t.LUONG > 30000 } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 31 
Nội dung chi tiết 
 Giới thiệu 
 Phép tính quan hệ trên bộ 
 Phép tính quan hệ trên miền 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 32 
Phép tính quan hệ trên miền 
 Biểu thức phép tính quan hệ trên miền có dạng 
- x1, x2, , xn là các biến miền 
 Biến nhận giá trị là một miền giá trị của một thuộc tính 
- P là công thức theo x1, x2, , xn 
 P được hình thành từ những công thức nguyên tố 
- Kết quả trả về là tập các giá trị x1, x2, , xn sao cho khi 
các giá trị được thay thế cho các xi thì P đúng 
{ x1, x2, , xn | P(x1, x2, , xn) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 33 
Ví dụ 3 
 Cho biết mã và tên nhân viên có lương trên 30000 
{ r, s | x ( 
 NHANVIEN  
 x > 30000 ) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 34 
Ví dụ 4 
 Cho biết các nhân viên (MANV) làm việc ở phòng 
‘Nghien cuu’ 
{ s | z ( 
 NHANVIEN  
 a, b ( PHONGBAN  
 a = ‘Nghien cuu’  b = z )) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 35 
Ví dụ 10 
 Cho biết các nhân viên (MANV, HONV, TENNV) 
không có thân nhân nào 
{ p, r, s | s ( 
 NHANVIEN  
 a ( THANNHAN  a = s )) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 36 
Công thức nguyên tố 
 (i) 
- xi là biến miền 
- R là quan hệ có n thuộc tính 
 (ii) 
- x, y là các biến miền 
- Miền giá trị của x và y phải giống nhau 
-  là các phép so sánh , , , , , 
 (iii) 
- c là hằng số 
- x là biến miền 
-  là các phép so sánh , , , , , 
 R 
x  y 
x  c 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 37 
Nhận xét 
 Một công thức nguyên tố mang giá trị ĐÚNG hoặc 
SAI với một tập giá trị cụ thể tương ứng với các 
biến miền 
- Gọi là chân trị của công thức nguyên tố 
 Một số qui tắc và biến đổi tương tự với phép tính 
quan hệ trên bộ 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 38 
Công thức an toàn 
 Xét công thức 
- Các giá trị trong kết quả trả về không thuộc miền giá trị 
của biểu thức 
- Công thức không an toàn 
{ p, r, s |  ( NHANVIEN) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 39 
Công thức an toàn (tt) 
 Xét công thức 
- R là quan hệ có tập các giá trị hữu hạn 
- Cũng có 1 tập hữu hạn các giá trị không thuộc R 
- Công thức 1: chỉ xem xét các giá trị trong R 
- Công thức 2: không thể kiểm tra khi không biết tập giá trị 
hữu hạn của z 
{ x | y ( R)  z ( R  P(x, z)) } 
Công thức 1 Công thức 2 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 40 
Công thức an toàn (tt) 
 Biểu thức 
 được gọi là an toàn nếu: 
- Những giá trị xuất hiện trong các bộ của biểu thức phải 
thuộc về miền giá trị của P 
- Vị từ : biểu thức x (Q(x)) đúng khi và chỉ khi xác định 
được giá trị của x thuộc dom(Q) làm cho Q(x) đúng 
- Vị từ : biểu thức x (Q(x)) đúng khi và chỉ khi Q(x) 
đúng với mọi giá trị của x thuộc dom(Q) 
{ x1, x2, , xn | P(x1, x2, , xn) } 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 41 
Bài tập về nhà 
 Bài tập 
- Làm lại các bài tập của chương 4 (ĐSQH) 
 Trừ các câu có hàm kết hợp và gom nhóm 
- Biểu diễn bằng 2 ngôn ngữ 
 Phép tính quan hệ có biến là bộ 
 Phép tính quan hệ có biến là miền 
 Đọc 
- Ngôn ngữ QBE 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 42