Bài giảng môn học Cơ sở dữ liệu - Chương 6: Phép tính quan hệ

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ộ
- Tuple Relational Calculus (TRC)
 Phép tính quan hệ trên miền
- Domain Relational Calculus (DRC)
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ộ
• SQL
- Phép tính quan hệ trên miền
• QBE (Query By Example)
• DataLog (Database Logic)
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 ‘Nghiên cứu’ 
s.MAPHG t.PHG ) }
MANV HOTEN PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
MAPHG TENPHG
1 Điều Hành
3 Nghiên cứu
4 Kinh Doanh
MANV
2
4
NHANVIEN
PHONGBAN
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)) }
MANV HOTEN PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
NHANVIEN
MANV MADA
1 1
3 2
PHANCONG
MA_NVIEN TENTN
2 A
3 B
3 C
THANNHAN
t1
t2
t3
t4
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)) }
MANV HOTEN PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
NHANVIEN
MANV MADA
1 1
3 2
PHANCONG
MANV TENTN
2 A
3 B
3 C
THANNHAN
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) }
MANV HOTEN PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
NHANVIEN
MANV MADA
1 1
3 2
PHANCONG
MANV TENTN
2 A
3 B
3 C
THANNHAN
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 15
Ví dụ 7-a
 Với mỗi đề án ở „TP HCM‟ cho biết mã đề án và tên
phòng ban chủ trì đề án đó.
{ s.MADA, s.PHONG, p.TENPHG | s DEAN  p 
PHONGBAN  s.DDIEM_DA = ‘HCM’  s.PHONG = 
p.MAPHG }
MAPHG TENPHG
1 Điều Hành
3 Nghiên cứu
4 Kinh Doanh
PHONGBAN
MADA TENDA PHONG DDIEM_DA 
10 Sản phẩm X 1 HCM
20 Sản phẩm Y 3 Hà Nội
30 Sản phẩm Z 3 HCM
DEAN
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 16
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 17
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 18
Ví dụ 8 (tt)
 Tìm các nhân viên (MANV, TENNV) tham gia vào
tất cả các đề án
MANV TENNV PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
5 Hiền 1
NHANVIEN
MADA TENDA
10 Sản phẩm X
30 Sản phẩm Y
DEAN
MA_NVIEN MADA
1 10
2 30
2 10
3 10
3 30
4 30
PHANCONG
{ t.MANV, t.TENNV | t NHANVIEN 
s DEAN ( u PHANCONG (
u.MADA s.MADA 
t.MANV u.MA_NVIEN )) }
t1
t2
t3
t4
t5
s1
s2
u1
u2
u3
u4
u5
u6
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 19
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 20
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 21
MANV TENNV PHG
1 Tùng 1
2 Tiến 3
3 Trang 4
4 Trung 3
5 Hiền 1
NHANVIEN
MADA TENDA PHONG
10 Sản phẩm X 4
30 Sản phẩm Y 5
70 Sản phẩm Z 4
DEAN
MA_NVIEN MADA
1 10
2 30
2 10
3 10
3 70
4 30
1 70
PHANCONG
{ 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 22
Đị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 23
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ộcBiến tự do
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 24
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 25
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
t R
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 26
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)
t.A  s.B t.A  c
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 27
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 28
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 29
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
Bài tập
1. Tìm tên nhân viên và tên phòng ban của nhân viên
2. Tìm tên nhân viên và tên người quản lý của nhân
viên
3. Tìm tên nhân viên và tên trưởng phòng của phòng
ban mà nhân viên trực thuộc
4. Tìm tên nhân viên, tên phòng ban của nhân viên,
tên trưởng phòng và tên người quản lý của nhân
viên
5. Tìm tên nhân viên có tham gia đề án 'Sản Phẩm X'
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 30
Bài tập
6. Tìm nhân viên có lương cao nhất
7. Tìm nhân viên có lương cao nhất và tên người
quản lý của nhân viên đó
8. Tìm những nhân viên có lương cao nhất theo
từng phòng ban
9. Tìm tên những nhân viên chưa tham gia đề án nào
10. Tìm các đề án mà nhân viên '009' chưa làm
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 31
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 32
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 33
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 34
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 35
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 36
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 37
Ví dụ 1
 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 38
Ví dụ 3 
 Cho biết các nhân viên (MANV) làm việc ở phòng
„Nghien cuu‟
{ s | NHANVIEN 
 PHONGBAN (
a = ‘Nghien cuu’  b = z )) }
{ t.MANV | t NHANVIEN 
s PHONGBAN ( 
s.TENPHG ‘Nghien cuu’ 
s.MAPHG t.PHG ) }
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 39
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 40
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 41
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 42
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 43
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 44
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
- Lượng 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
- Lượng 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 45