Bài giảng Cơ sở dữ liệu - Chương 6: Phép tính quan hệ (Bản đẹp)

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
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
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’
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 11
Ví dụ 3 
 Cho biết các nhân viên (MANV) làm việc ở phòng
‘Nghien cuu’
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
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
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
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
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ơ 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
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ơ 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
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ộcBiế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
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’
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
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