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ệ
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 2
Giới thiệu
 Maths Database
 1970 1981 Codd
 Algebra Relational Algebra ACM 
 1972 YOU Turing 
 Logic Relational Calculus Award
 Geometry
 2???
  ??? ??? 
  Award
 2???
 Other fields
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 3
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 4
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 5
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 6
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.A | P(t) }
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 7
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 8
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 9
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 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ụ 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 12
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 13
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 14
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 15
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 16
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 17
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 18
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 19
Định nghĩa hình thức
 Một công thức truy vấn tổng quát có dạng
 { t1.Ai, t2.Aj, tn.Ak | P(t1, t2, , tn) }
 - 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ố
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 20
Biến bộ
 Biến tự do (free variable)
{ t | t NHANVIEN  t.LUONG > 30000 }
 t là biến tự do
 Biến kết buộc (bound variable)
 { t | t NHANVIEN  s PHONGBAN (s.MAPHG t.PHG) }
 Biến tự do Biến kết buộc
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 21
Công thức nguyên tố
 (i) t R
 - t là biến bộ t NHANVIEN
 - R là quan hệ
 (ii) t.A  s.B
 - A là thuộc tính của biến bộ t t.MANV = s.MANV
 - B là thuộc tính của biến bộ s
 -  là các phép so sánh , , , , , 
 (iii) t.A  c
 - c là hằng số s.LUONG > 30000
 - A là thuộc tính của biến bộ t
 -  là các phép so sánh , , , , , 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 22
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
 R A B C
 t1 = t1 R có chân trị ĐÚNG
 10 1
 20 1 t2 = t2 R có chân trị SAI
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 23
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ộ
 R A B C Nếu t là bộ 
 10 1 Thì t.B > 5 có chân trị ĐÚNG (10 > 5)
 20 1
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 24
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 25
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 26
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 27
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 28
Công thức an toàn
 Xét công thức
 { t | (t NHANVIEN) }
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 29
Công thức an toàn (tt)
 Ví dụ
 { t | t NHANVIEN  t.LUONG > 30000 }
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 30
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 31
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 | P(x1, x2, , xn) }
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 32
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 33
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 34
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 35
Công thức nguyên tố
 (i) R
 - xi là biến miền
 - R là quan hệ có n thuộc tính
 (ii) x  y
 - 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) x  c
 - c là hằng số
 - x là biến miền
 -  là các phép so sánh , , , , , 
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 36
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 37
Công thức an toàn
 Xét công thức
 { p, r, s |  ( NHANVIEN) }
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 38
Công thức an toàn (tt)
 Xét công thức
 { x | y ( R)  z ( R  P(x, z)) }
 Công thức 1 Công thức 2
 - 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
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 39
Công thức an toàn (tt)
 Biểu thức
 { x1, x2, , xn | P(x1, x2, , xn) }
 đượ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)
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 40
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 41
Cơ sở dữ liệu - Khoa CNTT - ĐH KHTN TPHCM 42