›
›

Cơ sở dữ liệu - Chương 5: Ngôn ngữ tân từ

pdf 55 trang vanle 3570
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cơ sở dữ liệu - Chương 5: Ngôn ngữ tân từ", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfco_so_du_lieu_chuong_5_ngon_ngu_tan_tu.pdf

Nội dung text: Cơ sở dữ liệu - Chương 5: Ngôn ngữ tân từ

  1. Chương 5 Ngơn Ngữ Tân Từ Trong CSDL thực hiện việc mơ hình hĩa thơng tin gồm các sự kiện được liên kết hay biểu diễn một tình trạng thế giới thực. Ngơn ngữ tân từ ứng dụng logic tốn để thể hiện truy vấn. Ngơn ngữ tân từ cĩ hai loại, ngơn ngữ tân từ cĩ biến là bộ và ngơn ngữ tân từ cĩ biến là miền giá trị. 1. Ngơn ngữ tân từ cĩ biến là bộ 1.1. Một số khái niệm Dạng thức: {}t | P(t) , với: • t: biến bộ, nhận giá trị là một bộ của quan hệ. Khi đĩ t.A là giá trị của bộ t tại thuộc tính A. • P(t): cơng thức liên quan đến biến bộ t, phụ thuộc vào giá trị của t mà P(t) cho kết quả đúng hay sai. • Kết quả trả về là tập hợp các bộ t thoả P(t) Ví dụ: • Tìm tất cả những nhân viên nam {}t | NHANVIEN(t) ∧ t.Phai =' Nam' • Tìm tất cả những nhân viên nữ và cĩ lương trên 1500000 {}t | NHANVIEN(t) ∧ t.Phai ='Nữ''∧t.Luong > 1500000 Với mỗi biến bộ t, quan hệ R mà t biến thiên trên đĩ được gọi là quan hệ vùng của biến bộ. Giá trị này được chỉ định bằng điều kiện dạng R(t). 1.2. Định nghĩa hình thức của phép tính bộ Dạng tổng quát: {}t1.A1 ,t2 .A2 , ,tn .An | P(t1 ,t2 , ,tn ,tn+1 , ,tn+m ) , với: Trang 55/109
  2. • t1,t2 , ,tn ,tn+1, ,tn+m là các biến bộ • Ai là thuộc tính của quan hệ mà biến bộ ti biến thiên • P là cơng thức hay điều kiện của phép tính bộ. • Cơng thức được hình thành từ các cơng thức nguyên tố Cơng thức nguyên tố: Cĩ 3 dạng: a. R(ti) là cơng thức nguyên tố, với • R là một quan hệ và ti là một biến bộ • Cơng thức này xác định vùng của biến bộ ti dưới hình thức quan hệ cĩ tên R • Ví dụ: DEAN(t), NHANVIEN(x) b. ti .A θ t j .B là cơng thức nguyên tố, với: • θ là phép so sánh () ,=,≤,≥,≠ • ti, tj là các biến bộ • A là thuộc tính của quan hệ trên đĩ bộ ti biến thiên, Blà thuộc tính của quan hệ trên đĩ bộ tj biến thiên • Ví dụ: x.MaPhong = y.Phong, với PHONGBAN(x) và DEAN(y) c. ti .A θ c hoặc c θ t j .B là cơng thức nguyên tố, với: • θ là phép so sánh () ,=,≤,≥,≠ • ti, tj là các biến bộ • A là thuộc tính của quan hệ trên đĩ bộ ti biến thiên, Blà thuộc tính của quan hệ trên đĩ bộ tj biến thiên • c là giá trị hằng • Ví dụ: x.MaPhong = PH01, y.Luong > 500000 Nhận thấy rằng mỗi cơng thức nguyên tố đều mang giá trị đúng hoặc sai. Với (a), R(t) đúng nếu t là một bộ thuộc R, ngược lại mang giá trị sai; với (b, c) giá trị đúng sai phụ thuộc vào kết quả thay thế giá trị thực sự của bộ vào vị trí biến bộ. Trang 56/109
  3. Một cơng thức (hay điều kiện) được hình thành từ một hay nhiều cơng thức nguyên tố và được nối với nhau bằng các tốn tử và, hoặc, phủ định ( ∧, ∨, ¬ ) và được định nghĩa như sau: a. Mọi cơng thức nguyên tố là cơng thức b. Nếu F1 và F2 là các cơng thức thì (F1 ∧ F2 ), (F1 ∨ F2 ), ¬F1 , ¬F2 là cơng thức và cĩ giá trị: • ()F1 ∧ F2 chỉ đúng khi cả F1 và F2 đều đúng • ()F1 ∨ F2 chỉ sai khi cả F1 và F2 đều sai • ¬F1 đúng nếu F1 sai, ¬F1 sai nếu F1 đúng 1.3. Lượng từ tồn tại ∃ và với mọi ∀ Biến bộ tự do và biến kết buộc Một biến bộ t là kết buộc nếu cĩ kèm lượng từ, nghĩa là nĩ xuất hiện trong mệnh đề ∀t ∈ S()P(t) hay ∃t ∈ S()P(t) , ngược lại nĩ được gọi là biến tự do. Nếu F là cơng thức nguyên tố thì mọi biến bộ t trong F đều là biến tự do. Tất cả các biến bộ tự do t trong F được xem là biến kết buộc trong cơng thức F'= (∀t)F hay F'= ()∃t F Đối với các cơng thức F = ()F1 ∧ F2 , F = (F1 ∨ F2 ), F = ¬F1 , F = ¬F2 , biến t là tự do hay kết buộc phụ thuộc vào nĩ là tự do hay kết buộc trong F1 và F2 Biến bộ tự do chỉ ra các bộ mà câu truy vấn trả về, nghĩa là được sử dụng trong vế trái. Ngược lại biến bộ kết buộc thường được sử dụng để thực hiện việc khẳng định các bộ trong CSDL, nghĩa là được sử dụng trong vế phải. Ví dụ: • Cho biết những nhân viên thuộc phịng cĩ mã số 5 và cĩ lương >= 500000 {n | NHANVIEN(n) ∧ n.Phong = 5 ∧ n.Luong ≥ 500000} • Cho biết những đề án do phịng ‘Quản Lý’ phụ trách {d | DEAN(d) ∧ (∃p ∈ PHONGBAN(d.Phong = p.MaPhong ∧ p.TenPhong ='QuanLy'))} • Tìm những nhân viên tham gia trong tất cả các đề án của cơng ty Trang 57/109
  4. {n | NHANVIEN(n) ∧ ()∀d ∈ DEAN(∃p ∈ PHANCONG(p.MaDA = d.MaDA ∧ p.MaNV = n.MaNV )) } Chú ý rằng • ∀t(F) đúng nếu F đúng với mọi bộ t, sai nếu ít nhất một bộ sai. • ∃t(F) sai nếu F sai với mọi bộ t, đúng nếu ít nhất một bộ đúng. 2. Ngơn ngữ tân từ cĩ biến là miền giá trị Biến miền giá trị nhận giá trị từ miền giá trị của một thuộc tính. Dạng thức: {}x1 , x2 , , xn | P , với: • x1 , x2 , , xn là danh sách các biến miền giá trị • P là điều kiện hay cơng thức theo x1 , x2 , , xn • Kết quả câu truy vấn là tập hợp các chọn lựa của các bộ x1 , x2 , , xn sao cho, với mọi i, giá trị xi được thay thế cho các biến tự do xi thì điều kiện đúng. Biến xi cĩ thể là hằng số, khi đĩ tất cả các bộ trong tập hợp đều là hằng số trong vị trí i. Ví dụ: • Cho biết mã nhân viên thuộc phịng cĩ mã số 5 và cĩ lương >= 500000 ⎪⎧ ⎛ NHANVIEN(Ma, Ho,Ten, NSinh, DChi, Phai, Lg, MaQL, Phg)⎞⎪⎫ Ma, Ho,Ten | ∃Phg∃Lg⎜ ⎟ ⎨ ⎜ ⎟⎬ ⎩⎪ ⎝∧ Phg = 5 ∧ Lg ≥ 500000 ⎠⎭⎪ Nhận thấy rằng Ma, Ho,Ten chính là thuộc tính được yêu cầu; Phg, Lg là biến thực sự xuất hiện trong một câu điều kiện. • Tìm họ tên, địa chỉ của nhân viên thuộc phịng ‘Quản Lý’ ⎪⎧ ⎛ NHANVIEN(Ma, Ho,Ten, NSinh, DChi, Phai, Lg, MaQL, Phg) ⎞⎪⎫ Ma, Ho,Ten, DChi | ∃Phg⎜ ⎟ ⎨ ⎜ ⎟⎬ ⎩⎪ ⎝∧ ∃TenPhg()MaPhg,TenPhg,TrPhg, NgayNC ∧ TenPhg ='Quản Lý'⎠⎭⎪ Cơng thức nguyên tố: Cĩ 3 dạng: Trang 58/109
  5. a. R(x1 , x2 , , x j ) là cơng thức nguyên tố, với • R là một quan hệ bậc j • Mỗi xi ,1 ≤ i ≤ n là một biến miền. • Cơng thức này cho biết (x1, x2 , , x j ) là một bộ của quan hệ R, với xi là giá trị thứ i của bộ. • Ví dụ: {}x1 , x2 , , xn | R()x1 , x2 ∧ b. xiθ x j là cơng thức nguyên tố, với: • θ là phép so sánh () ,=,≤,≥,≠ • xi, xj là các biến miền • Ví dụ: MaPhg = Phg. c. xiθ c hoặc cθ x j là cơng thức nguyên tố, với: • θ là phép so sánh () ,=,≤,≥,≠ • xi, xj là các biến miền • c là hằng • Ví dụ: MaPhg = 1. Một cơng thức nguyên tố cĩ 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. Các định nghĩa về cơng thức dựa trên cơng thức nguyên tố, các định nghĩa về biến kết buộc và tự do, các lượng từ trong trường hợp phép tính miền cũng tương tự phép tính bộ. 3. Bài tập Bài 1: Hãy viết bằng ngơn ngữ tân từ theo yêu cầu như bài tập 1 trong chương 4. Bài 2: Hãy viết bằng ngơn ngữ tân từ theo yêu cầu như bài tập 2 trong chương 4. Trang 59/109
  6. Chương 6 Ngơn Ngữ Truy Vấn SQL SQL (Structured Query Language) là ngơn ngữ CSDL quan hệ chuẩn dành cho các CSDL quan hệ thương mại. Từ những năm 70, SQL được phát triển từ IBM với hệ quản trị CSDL quan hệ SYSTEM- R với ngơn ngữ giao tiếp CSDL là Sequel (Structured English Query Language). Năm 1986, phiên bản chuẩn được chấp nhận bởi ANSI (American National Standards Institute) gọi là SQL-86 hay SQL1 và năm 1987 được chấp nhận bởi ISO (International Standards Organization). Từ đĩ các phiên bản đã được đưa ra vào 1992, 1999, 2003. 1. Các lệnh hỏi Các lệnh hỏi hay cịn được gọi là truy vấn rút trích dữ liệu. Lệnh SELECT là lệnh cơ bản để rút trích thơng tin từ CSDL. Chú ý rằng lệnh SELECT khơng hồn tồn giống như phép tốn chọn trong đại số quan hệ, SQL cho phép một bảng cĩ hai hay nhiều bộ cĩ giá trị giống nhau trên mọi thuộc tính cùng tồn tại 1.1. Cú pháp lệnh truy vấn Cú pháp lệnh truy vấn: SELECT FROM WHERE GROUP BY HAVING ORDER BY với: Trang 60/109
  7. • SELECT : tên các thuộc tính được lấy giá trị • FROM : tên các bảng cần để xử lý câu truy vấn • WHERE : biểu thức điều kiện chọn và điều kiện kết các bộ trong các quan hệ được chỉ ra trong mệnh đề FROM • GROUP BY : chỉ ra các thuộc tính gom nhĩm • HAVING : chỉ ra điều kiện để trích chọn các nhĩm • ORDER BY : thứ tự hiển thị kết quả câu truy vấn Trong câu lệnh, SELECT và FROM là bắt buộc, những thành phần cịn lại cĩ thể khơng cĩ. 1.2. Phép chiếu Sử dụng mệnh đề SELECT, kết quả gần giống với phép chiếu của đại số quan hệ, liệt kê các thuộc tính cần hiển thị trong kết quả câu truy vấn. Ví dụ: • Tìm mã nhân viên, họ tên tất cả các nhân viên SELECT MaNV, HoNV, TenNV FROM NHANVIEN • Tìm mã đề án, tên các đề án SELECT MaDA, TenDA FROM DEAN 1.3. Phép chọn Sử dụng mệnh đề WHERE, kết quả gần giống với phép chọn của đại số quan hệ, nêu điều kiện liên quan đến thuộc tính của quan hệ xuất hiện trong mệnh đề FROM. Thường sử dụng AND, OR, NOT, BETWEEN, các phép tốn so sánh. Ví dụ: • Tìm mã nhân viên, họ tên tất cả các nhân viên nam SELECT MaNV, HoNV, TenNV FROM NHANVIEN Trang 61/109
  8. WHERE Phai=’Nam’ 1.4. Phép kết Trong mệnh đề WHERE thường cĩ điều kiện kết nếu như trong mệnh đề FROM cĩ nhiều hơn hai quan hệ. Ví dụ: • Tìm mã nhân viên, họ tên tất cả các nhân viên tham gia vào đề án cĩ mã ‘DA01’ SELECT MaNV, HoNV, TenNV FROM NHANVIEN, PHANCONG WHERE NHANVIEN.MaNV= PHANCONG.MaNV AND MaDA=’DA01’ • Tìm mã nhân viên, họ tên tất cả các nhân viên làm việc tại phịng ‘Tài chính’ SELECT MaNV, HoNV, TenNV FROM NHANVIEN, PHONGBAN WHERE Phong=MaPhong AND TenPhong = ‘Tài chính’ 1.5. Một số lưu ý Sử dụng * Khi cần lấy thơng tin về tất cả các cột của bảng thì sử dụng dấu sao (*) thay vì phải liệt kê mọi tên thuộc tính. Ví dụ: SELECT * FROM NHANVIEN Tên bí danh Khi câu truy vấn cần tham chiếu tới cùng một quan hệ 2 lần thì dùng bí danh cho tên quan hệ. SQL cho phép đổi tên quan hệ và tên thuộc tính được thực hiện bằng AS (cĩ thể dùng hoặc khơng) theo quy tắc: Tên cũ [as] tên mới Ví dụ: SELECT MaNV, HoNV as Ho, TenNV as Ten FROM NHANVIEN Trang 62/109
  9. WHERE Phai=’Nam’ Biểu thức trong mệnh đề SELECT Tên thuộc tính cĩ thể kèm theo tên bảng nếu cần làm rõ bằng cách thêm dấu chấm (.) trước tên thuộc tính. Ví dụ: NHANVIEN.MaNV. Câu lệnh SELECT cịn cho phép thực hiện tính tốn theo cơng thức dựa trên các cột của bảng. Ví dụ: • Tìm mã nhân viên, họ tên và lương nhân viên, trong đĩ lương được tăng thêm 20% cho mọi nhân viên SELECT MaNV, HoNV, TenNV, Luong*1.2 FROM NHANVIEN DISTINCT Như đã trình bày ở trên, SQL cho phép các bộ trùng nhau trong kết quả câu truy vấn. Để loại bỏ các bộ trùng nhau, sử dụng từ khĩa DISTINCT sau SELECT. Ví dụ: • Cho biết những mức lương hiện cĩ trong cơng ty SELECT DISTINCT Luong FROM NHANVIEN Phép so sánh trên chuỗi Sử dụng LIKE để so sánh chuỗi, cĩ 2 ký tự đặc biệt sau: • % (hoặc *): thay thế cho mọi ký tự bất kỳ • _ (hoặc ?) : thay thế cho một ký tự bất kỳ Ví dụ: • Tìm tất cả những nhân viên cĩ tên bắt đầu bằng M như Mai, Minh, SELECT MaNV, HoNV, TenNV FROM NHANVIEN WHERE TenNV LIKE ‘M%’ Trang 63/109
  10. Thứ tự hiển thị Mệnh đề ORDER BY sử dụng để sắp xếp các bộ trong kết quả câu truy vấn dựa trên giá trị các thuộc tính. Trong đĩ: • Asc: sắp theo thứ tự tăng dần (mặc định) • Desc: sắp theo thứ tự giảm dần Ví dụ: • Tìm tất cả những nhân viên phịng 1 và lương tương ứng, sắp xếp giảm dần theo lương SELECT MaNV, HoNV, TenNV, Luong FROM NHANVIEN WHERE Phong = 1 ORDER BY Luong desc 2. Câu truy vấn lồng Ở các ví dụ đã trình bày, mệnh đề WHERE bao gồm thuộc tính đơn, các phép so sánh hằng số. Phần này giới thiệu câu truy vấn lồng, cho phép lồng các câu truy vấn lại với nhau. Khi đĩ câu truy vấn con thơng thường được sử dụng để kiểm tra các tập hợp thành viên, so sánh tập hợp, kiểm tra sự tồn tại. Khi sử dụng truy vấn con trong mệnh đề WHERE của một truy vấn khác, mệnh đề SELECT trong truy vấn con phải phù hợp với số thuộc tính và kiểu dữ liệu của mệnh đề WHERE trong câu truy vấn ngồi. Truy vấn con trả về giá trị tập hợp trong mệnh đề WHERE cĩ dạng: • [NOT] IN ( ) • ANY ( ) • ALL ( ) Kiểm tra sự tồn tại: • [NOT] EXISTS ( ) Các câu truy vấn con trong một mệnh đề WHERE cĩ thể được kết hợp bằng cách sử dụng các phép nối logic Trang 64/109
  11. Ví dụ: • Tìm tất cả những nhân viên nam làm việc trong phịng ‘Tài chính’ SELECT MaNV, HoNV, TenNV FROM NHANVIEN WHERE Phong IN (SELECT MaPhong as Phong FROM PHONGBAN WHERE TenPhong = ‘Tài chính’) AND Phai = ‘Nam’ Trong trường hợp điều kiện ở mệnh đề WHERE của câu truy vấn con tham chiếu tới một thuộc tính của quan hệ được khai báo trong truy vấn cha thì hai câu truy vấn được gọi là tương quan. Các tham chiếu tới các quan hệ và các thuộc tính cha xuất hiện thơng qua việc sử dụng bí danh. Ví dụ: • Tìm tất cả những nhân viên cĩ cùng tên với người thân SELECT nv.MaNV, nv.HoNV, nv.TenNV FROM NHANVIEN as nv WHERE nv.MaNV IN (SELECT MaNV FROM THANNHAN WHERE TenTN = nv.TenNV) • Tìm tất cả những nhân viên cĩ lương lớn hơn mọi nhân viên phịng số 5 SELECT MaNV, HoNV, TenNV FROM NHANVIEN WHERE Luong > ALL (SELECT Luong FROM NHANVIEN WHERE Phong = 5) • Tìm tất cả những nhân viên cĩ lương lớn hơn ít nhất 1 nhân viên phịng số 5 Trang 65/109
  12. SELECT nv1.MaNV, nv1.HoNV, nv1.TenNV FROM NHANVIEN as nv1, NHANVIEN as nv2 WHERE nv1.Luong > nv2.Luong AND nv2.Phong = 5 Cụm từ lớn hơn ít nhất một cĩ thể diễn đạt bằng >SOME. Ví dụ trên được viết lại như sau: SELECT MaNV, HoNV, TenNV FROM NHANVIEN WHERE Luong > SOME (SELECT Luong FROM NHANVIEN WHERE Phong = 5) Hàm EXISTS sử dụng để kiểm tra kết quả của câu truy vấn tương quan cĩ rỗng hay khơng. Khi đĩ • EXISTS (r) mang giá trị true nếu cĩ ít nhất một bộ trong r, false nếu ngược lại. • NOT EXISTS (r) mang giá trị true nếu khơng cĩ bộ nào trong r, false nếu ngược lại. Ví dụ • Cho biết những nhân viên cĩ cùng tên với thân nhân SELECT nv.MaNV, nv.HoNV, nv.TenNV FROM NHANVIEN nv WHERE EXISTS (SELECT * FROM THANNHAN WHERE MaNV = nv.MaNV AND TenTN= nv.TenNV) Giá trị null SQL cho phép sử dụng các giá trị null để chỉ ra giá trị của thuộc tính khơng biết hay khơng tồn tại. Chú ý rằng kết quả của điều kiện ở mệnh đề WHERE là false nếu nĩ liên quan đến null. Trong SQL sử dụng IS NULL hay IS NOT NULL để kiểm tra các giá trị rỗng. Trong đĩ: Trang 66/109
  13. • Phép so sánh bằng (=) khơng dùng được • Các hàm gom nhĩm ngoại trừ COUNT() bỏ qua các giá trị null trong tập các dữ liệu đầu vào • Nếu cĩ điều kiện kết thì các bộ cĩ giá trị null trên thuộc tính kết sẽ khơng cĩ trong kết quả. 3. Hàm kết hợp và gom nhĩm Hàm kết hợp Hàm kết hợp cĩ đầu vào là một tập giá trị và trả về một giá trị đơn • Avg(): giá trị trung bình • Min(): giá trị nhỏ nhất • Max(): giá trị lớn nhất • Sum(): tính tổng • Count(): đếm số mẫu tin Ví dụ • Cho biết những mức lương trung bình và cao nhất của các nhân viên phịng cĩ mã là 5 SELECT AVG(Luong), MAX(Luong) FROM NHANVIEN WHERE Phong = 5 Gom nhĩm Các hàm gom nhĩm được áp dụng trên các nhĩm bộ cùng thuộc tính trong quan hệ. Mỗi nhĩm bộ bao gồm tập hợp các bộ cĩ cùng giá trị trên các thuộc tính gom nhĩm. Trong SQL sử dụng cú pháp như sau: SELECT FROM WHERE GROUP BY Trang 67/109
  14. HAVING • Mệnh đề GROUP BY chỉ ra các thuộc tính gom nhĩm, các thuộc tính trong mệnh đề SELET nằm ngồi một hàm kết hợp phải xuất hiện trong mệnh đề GROUP BY • Mệnh đề HAVING lấy các giá trị của hàm gom nhĩm chỉ trên những nhĩm nào thỏa điều kiện nhất định. Mệnh đề HAVING chỉ ra điều kiện lọc trên các nhĩm, khơng phải điều kiện lọc trên từng bộ. Ví dụ • Cho biết tên phịng và lương trung bình của các nhân viên trong phịng ban lớn hơn 100000. SELECT TenPhong, AVG(Luong) FROM NHANVIEN, PHONGBAN WHERE Phong = MaPhong GROUP BY TenPhong HAVING AVG(Luong)>100000 4. Các lệnh khai báo cấu trúc CSDL Kiểu dữ liệu Chọn hệ quản trị CSDL SQL Server để minh họa, Ta cĩ một số kiểu dữ liệu cơ bản: • Số (number) • Chuỗi (text, char, varchar, nvarchar) • Ngày tháng (datetime) • Logic (bit) Tạo bảng CREATE TABLE ( [not null][unique] [ ], [not null][unique] [ ], Trang 68/109
  15. [not null][unique] [ ], [ ] ) Các thuộc tính được xếp theo thứ tự khi tạo bảng. Các ràng buộc cũng cĩ thể được bổ sung sau bằng cách dùng ALTER TABLE Ví dụ CREATE TABLE PHONGBAN ( MaPhong char(5) not null, TenPhong nvarchar(30), TruongPhong char(5), NgayNhanChuc datetime, PRIMARY KEY (MaPhong), UNIQUE (TenPhong) FOREIGN KEY (TruongPhong) REFERENCES NHANVIEN (MaNV) ) RBTV Một số RBTV trong khi tạo bảng: • Not null: khơng được chứa giá trị null • Khĩa chính: khơng được chứa giá trị null và được xác định bởi PRIMARY KEY • Khĩa ngoại: FOREIGN KEY REFERENCE • Tính duy nhất: cĩ thể chứa giá trị null và được xác định bởi UNIQUE • CHECK : điều kiện đơn giản, khơng chứa các câu truy vấn hay tham chiếu tới các quan hệ khác Trang 69/109
  16. • Trong SQL server, mỗi RBTV cĩ thể được đặt tên bằng cách sử dụng CONSTRAINT . Chú ý rằng tên ràng buộc phải duy nhất trong một lược đồ CSDL. Ví dụ: CREATE TABLE PHONGBAN ( MaPhong char(5) not null, TenPhong nvarchar(30), TruongPhong char(5), NgayNhanChuc datetime, CONSTRAINT PK_PHONGBAN PRIMARY KEY (MaPhong), CONSTRAINT U_PHONGBAN UNIQUE (TenPhong) CONSTRAINT PK_PHONGBAN FOREIGN KEY (TruongPhong) REFERENCES NHANVIEN (MaNV) ) Xĩa bảng DROP TABLE xĩa bảng Ví dụ DROP TABLE PHONGBAN Thay đổi cấu trúc Thêm cột ALTER TABLE NHANVIEN ADD ChuyenMon char(40) Xĩa cột ALTER TABLE NHANVIEN DROP ChuyenMon Bổ sung, thay đổi RBTV ALTER TABLE NHANVIEN DROP CONSTRAINT FK_NHANVIEN ALTER TABLE NHANVIEN ADD CONSTRAINT FK_NHANVIEN FOREIGN KEY (MaNQL) REFERENCES NHANVIEN (MaNV) Trang 70/109
  17. 5. Các thao tác cập nhật dữ liệu 5.1. Thêm Cĩ thể thêm một bộ vào bảng bằng cách sử dụng: INSERT INTO [ , , , ] VALUES ( , , , ) Chú ý rằng thứ tự giá trị trong VALUES là thứ tự các thuộc tính được chỉ ra trong CREATE TABLE Ví dụ INSERT INTO PHANCONG VALUES (‘NV01’, ‘DA01’, 10 ) Cĩ thể thêm nhiều bộ vào bảng bằng cách sử dụng: INSERT INTO [ , , , ] SELECT FROM WHERE 5.2. Xĩa Cĩ thể xĩa một hay nhiều bộ khỏi bảng bằng cách sử dụng DELETE FROM [WHERE ] Ví dụ • Xĩa những nhân viên cĩ mức lương dưới 100000 DELETE FROM NHANVIEN WHERE Luong<100000 • Xĩa những nhân viên làm việc cho phịng ‘Nghiên cứu’ DELETE FROM NHANVIEN WHERE Phong in (SELECT MaPhong FROM PHONGBAN WHERE TenPhong = ‘Nghiên cứu’) Trang 71/109
  18. Chú ý rằng các bộ trong bảng khác cĩ thể bị xĩa do ràng buộc tham chiếu. Để giải quyết vấn đề này cĩ thể khơng cho xĩa hoặc xĩa luơn những bộ đang tham chiếu đến. 5.3. Cập nhật Cập nhật các giá trị thuộc tính của một hay nhiều bộ bằng cách sử dụng UPDATE SET = , = , = [WHERE ] Các bộ thỏa điều kiện sẽ được cập nhật giá trị cho các thuộc tính. Chú ý rằng các bộ trong bảng khác cĩ thể được cập nhật do ràng buộc tham chiếu. Để giải quyết vấn đề này cĩ thể khơng cho thay đổi hoặc thay đổi luơn những giá trị tham chiếu đến. Ví dụ Tăng thêm 100000 cho các nhân viên phịng ‘Nghiên cứu’ UPDATE NHANVIEN SET Luong = Luong +100000 WHERE Phong IN ( SELECT MaPhong FROM PHONGBAN WHERE TenPhong = ‘Nghiên cứu’) 6. Bài tập Thực hiện các câu truy vấn trong bài tập chương 4. Trang 72/109
  19. Chương 7 Phụ thuộc hàm, khĩa và ràng buộc tồn vẹn của lược đồ quan hệ Phụ thuộc hàm (functional dependency) dùng để biểu diễn một cách hình thức các ràng buộc tồn vẹn (RBTV). Phụ thuộc hàm cĩ tầm quan trọng rất lớn trong việc giải quyết các bài tốn tìm khĩa, phủ tối thiểu và chuẩn hĩa cơ sở dữ liệu. Nội dung chương cũng trình bày ràng buộc tồn vẹn (RBTV), các yếu tố liên quan đến ràng buộc tồn vẹn nhằm bảo đảm tính đúng đắn của dữ liệu. 1. Phụ thuộc hàm 1.1. Khái niệm phụ thuộc hàm Xét quan hệ DEAN(MaDA, TenDA, DdiemDA, Phong). Nhận thấy rằng quan hệ DEAN cĩ MaDA là khĩa, nghĩa là từ MaDA cĩ thể xác định được tất cả các thơng tin về tên đề án, địa điểm thực hiện đề án và phịng ban chủ trì đề án. Cĩ thể phát biểu lại như sau: • MaDA xác định TenDA hay TenDA phụ thuộc hàm vào MaDA • MaDA xác định DdiemDA hay DdiemDA phụ thuộc hàm vào MaDA • MaDA xác định Phong hay Phong phụ thuộc hàm vào MaDA được ký hiệu: • MaDA Ỉ TenDA • MaDA Ỉ DdiemDA • MaDA Ỉ Phong Một cách tổng quát, ta cĩ: Định nghĩa phụ thuộc hàm + + Q(A1, A2, , An ) là quan hệ; Q = {A1, A2, , An }; X, Y là hai tập con của Q ; t1, t2 là hai bộ bất kỳ của Q. Trang 73/109
  20. Khi đĩ: XỈY ⇔ (t1.X = t2.X ⇒ t1.Y = t2.Y) Ta nĩi X xác định Y hay Y phụ thuộc hàm vào X. X được gọi là vế trái phụ thuộc hàm, Y được gọi là vế phải phụ thuộc hàm. Phụ thuộc hàm hiển nhiên XỈ Y gọi là phụ thuộc hàm hiển nhiên nếu Y ⊆ X . Phụ thuộc hàm nguyên tố XỈ Y được gọi là phụ thuộc hàm nguyên tố (hoặc nĩi cách khác Y được gọi là phụ thuộc đầy đủ vào X) nếu ∀X '⊄ X đều khơng cĩ phụ thuộc hàm X’ỈY. Như vậy các phụ thuộc hàm MaDA Ỉ TenDA, MaDA Ỉ DdiemDA, MaDA Ỉ Phong là phụ thuộc hàm nguyên tố. Xét quan hệ CTIETHOADON (SoHD, MaHang, SoLuong, DonGia, ThanhTien) và các phụ thuộc hàm như sau: • {SoHD, MaHang} Ỉ SoLuong • {SoHD, MaHang} Ỉ DonGia • {SoHD, MaHang} Ỉ ThanhTien Nhận thấy rằng SoLuong phụ thuộc đầy đủ vào {SoHD, MaHang} nhưng DonGia chỉ phụ thuộc vào MaHang (là một thuộc tính khĩa) chứ khơng phụ thuộc đầy đủ vào khĩa {SoHD, MaHang}. Như vậy, trên một lược đồ quan hệ cĩ thể tồn tại nhiều phụ thuộc hàm. Tập các phụ thuộc hàm được ký hiệu F 1.2. Hệ luật dẫn Amstrong Gọi F là tập phụ thuộc hàm đối với lược đồ quan hệ R định nghĩa trên tập thuộc tính U và XỈY là một phụ thuộc hàm; X ,Y ⊆ U . Khi đĩ ta nĩi rằng XỈY được suy diễn logic từ F nếu R thỏa các phụ thuộc hàm của F thì cũng thỏa XỈY và ký hiệu là F|=XỈY Bao đĩng của tập phụ thuộc hàm Bao đĩng của tập phụ thuộc hàm F, ký hiệu là F+ là là tập tất cả các phụ thuộc hàm được duy diễn từ F. Trong trường hợp F=F+ thì F là họ đầy đủ của các phụ thuộc hàm. Trang 74/109
  21. Hệ luật dẫn Amstrong Amstrong đã đưa ra hệ luật tiên đề cịn được gọi là hệ luật dẫn Amstrong sau: Với X ,Y, Z,W ⊆ U , U là tập thuộc tính. Phụ thuộc hàm cĩ các tính chất sau: (1) Tính phản xạ Nếu Y ⊆ X thì X → Y (2) Tính tăng trưởng Nếu X → Y thì XZ → YZ (3) Tính bắc cầu Nếu X → Y và Y → Z thì X → Z Từ hệ tiên đề Amstrong suy ra một số tính chất sau: (1) Tính phân rã sau Nếu X → YZ và X → Y thì X → Z (2) Tính kết hợp Nếu X → Y và X → Z thì X → YZ (3) Tính tựa bắc cầu Nếu X → Y và YZ → W thì XZ → W Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụ thuộc hàm F={ABỈC, BỈD, CDỈE, CEỈGH, GỈA} Chứng tỏ ABỈE được suy diễn từ F. (1) ABỈC (2) ABỈAB (tính phản xạ) (3) ABỈB (tính phân rã) (4) BỈD (5) ABỈD (tính bắc cầu 3+4) Trang 75/109
  22. (6) ABỈCD (tính hợp 1+5) (7) CDỈE (8) ABỈE (tính bắc cầu 6+7) 1.3. Thuật tốn tìm bao đĩng của tập thuộc tính Bao đĩng của tập thuộc tính + Bao đĩng của tập thuộc tính X đối với tập phụ thuộc hàm F, ký hiệu là X F là tập tất cả các thuộc tính A cĩ thể suy dẫn từ X nhờ tập bao đĩng của các phụ thuộc hàm F+ + + + X F = {A∈ Q |X → A∈ F } Thuật tốn tìm bao đĩng của tập thuộc tính Input: ()Q, F , X ⊆ Q + + Output: X F Bước 1: Tính dãy X (0) , X (1) , , X (i) : • X (0) = X • X (i+1) = X (i) ∪ Z,∃()Y → Z ∈ F(Y ⊆ X (i) ), loại (Y → Z ) ra khỏi F • Dừng khi X (i+1) = X (i) hoặc khi X (i) = Q + + (i) Bước 2: Kết luận X F = X : Ví dụ 1 Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụ thuộc hàm F={ f1: BỈA , f2: DAỈCE, f3: DỈH, f4: GHỈC, f5: ACỈD} + Tìm ACF Trang 76/109
  23. Bước 1: X 0 = AC Bước 2: Từ f1 đến f4 khơng thoả, f5 thoả nên X 1 = AC ∪ D = ACD Lặp lại bước 2: f1 khơng thoả, f2 thỏa nên X 2 = ACD ∪ CE = ACDE f3 thỏa nên X 3 = ACDE ∪ H = ACDEH f4 khơng thỏa, f5 đã thỏa Lặp lại bước 2: f2, f3 và f5 đã thỏa, f1 và f3 khơng thỏa. Nên X 4 = X 3 = ACDEH + Vậy ACF = ACDEH 1.4. Bài tốn thành viên Cho tập thuộc tính Q, tập phụ thuộc hàm F trên Q và một phụ thuộc hàm XỈY trên Q. Câu hỏi đặt ra rằng X → Y ∈ F + hay khơng? Giải quyết: X → Y ∈ F + ⇔ Y ⊆ X + Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụ thuộc hàm F={ f1: BỈA , f2: DAỈCE, f3: DỈH, f4: GHỈC, f5: ACỈD} Cho biết AC → E cĩ thuộc F+ khơng? + Ta cĩ ACF = ACDEH + + Vì E ∈ ACF nên AC → E ∈ F 1.5. Phủ tối thiểu của một tập phụ thuộc hàm 1.5.1. Hai tập phụ thuộc hàm tương đương Trang 77/109
  24. Hai tập phụ thuộc hàm F và G tương đương nếu F + = G + . Ký hiệu F ≡ G F được gọi là phủ G nếu F + ⊇ G + Thuật tốn xác định F và G cĩ tương đương khơng Bước 1: Với mỗi phụ thuộc hàm X → Y ∈ F Kiểm tra X → Y cĩ là thành viên của G khơng. Bước 2: Với mỗi phụ thuộc hàm X → Y ∈ G Kiểm tra X → Y cĩ là thành viên của F khơng. Bước 3: Nếu cả bước 1 và 2 đều đúng thì kết luận F ≡ G Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={ AỈBC , AỈD, CDỈE} G={ AỈBCE , AỈABD, CDỈE} Cho biết F và G cĩ tương đương khơng? Bước 1: + + + AG = ABCDE ⇒ (A → BC ∈G ∧ A → D ∈G ) Hơn nữa ta cĩ (CD → E ∈ F ∧ CD → E ∈ G) Vậy mọi phụ thuộc hàm trong F đều là thành viên của G Bước 2: + + + AF = ABCDE ⇒ (A → BCE ∈ F ∧ A → ABD ∈ F ) Hơn nữa ta cĩ (CD → E ∈ G ∧ CD → E ∈ F ) Vậy mọi phụ thuộc hàm trong G đều là thành viên của F Trang 78/109
  25. Bước 3: Kết luận F ≡ G 1.5.2. Phủ tối thiểu của tập phụ thuộc hàm Phụ thuộc hàm cĩ thuộc tính vế trái dư thừa Cho F là tập các phụ thuộc hàm trên lược đồ quan hệ Q. Khi đĩ Z → Y ∈ F là phụ thuộc hàm cĩ thuộc tính vế trái dư thừa nếu tồn tại A∈ Z mà F = F − (Z → Y )(∪ (Z − A) → Y ) Ngược lại Z → Y là phụ thuộc hàm cĩ thuộc tính vế trái khơng dư thừa hay Y phụ thuộc đầy đủ vào Z. Z → Y cịn được gọi là phụ thuộc hàm đầy đủ. Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={ AỈB , BCỈD, CỈD} Khi đĩ AỈB , CỈD là những phụ thuộc hàm đầy đủ. BCỈD là phụ thuộc hàm cĩ thuộc tính vế trái B dư thừa. Vấn đề là tìm các phụ thuộc hàm đầy đủ tương ứng bằng cách loại bỏ các thuộc tính dư thừa. Thuật tốn tìm các phụ thuộc hàm đầy đủ tương ứng Thực hiện với mỗi phụ thuộc hàm X → Y ∈ F Bước 1: X = A1, A2, An (n>=2, với n=1 thì XỈY là đầy đủ) Đặt Z=X Bước 2: Với mỗi Ai, thực hiện - Tam = Z \ Ai - Nếu Tam → Y ∈ F + thì Z=Tam Tập phụ thuộc hàm cĩ vế phải một thuộc tính Mỗi tập phụ thuộc hàm F đều tương đương với một tập phụ thuộc hàm G mà vế phải của các phụ thuộc hàm thuộc G chỉ gồm một thuộc tính Ví dụ: Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={ AỈBC , AỈD, CDỈE} Trang 79/109
  26. Khi đĩ G={ AỈB, AỈC , AỈD, CDỈE} là tập phụ thuộc hàm cĩ vế phải một thuộc tính và F ≡ G Tập phụ thuộc hàm khơng dư thừa F là tập phụ thuộc hàm khơng dư thừa nếu khơng tồn tại F'⊂ F sao cho F'≡ F . Ngược lại F được gọi là tập phụ thuộc hàm dư thừa. Thuật tốn loại những phụ thuộc hàm dư thừa Với mỗi phụ thuộc hàm X → Y ∈ F nếu X → Y là thành viên của F − {X → Y} thì loại X → Y khỏi F. 1.5.3. Phủ tối thiểu của tập phụ thuộc hàm F được gọi là phủ tối thiểu của tập phụ thuộc hàm (hay tập phụ thuộc hàm tối thiểu) nếu thỏa: (i) F là tập phụ thuộc hàm cĩ thuộc tính vế trái khơng dư thừa (ii) F là tập phụ thuộc hàm cĩ vế phải một thuộc tính (iii) F là tập phụ thuộc hàm khơng dư thừa Thuật tốn tìm phủ tối thiểu của tập phụ thuộc hàm Bước 1: Loại các thuộc tính cĩ vế trái dư thừa của mọi phụ thuộc hàm Bước 2: Phân rã các phụ thuộc hàm cĩ vế phải nhiều thuộc tính thành các phụ thuộc hàm cĩ vế phải một thuộc tính Bước 3: Loại các phụ thuộc hàm dư thừa khỏi F Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụ thuộc hàm F={ BỈA , DAỈCE, DỈH, GHỈC, ACỈD} Tìm phủ tối thiểu của F. Bước 1: Trang 80/109
  27. • Với DAỈCE: + + + o Giả sử D thừa thì A → CE ∈ F : ta cĩ AF = A, CE ∉ AF nên D khơng thừa + + + o Giả sử A thừa thì B → CE ∈ F : ta cĩ DF = DH , CE ∉ DF nên A khơng thừa • Với GHỈC: + + + o Giả sử G thừa thì H → C ∈ F : ta cĩ H F = H , C ∉ H F nên G khơng thừa + + + o Giả sử H thừa thì G → C ∈ F : ta cĩ GF = G , C ∉ GF nên H khơng thừa • Với ACỈD: + + + o Giả sử A thừa thì C → D ∈ F : ta cĩ CF = C , D ∉ CF nên A khơng thừa + + + o Giả sử C thừa thì A → D ∈ F : ta cĩ AF = A, D ∉ AF nên C khơng thừa Vậy mọi phụ thuộc hàm đều là đầy đủ. Bước 2: Phân rã vế phải ta cĩ F={ BỈA , DAỈC, DAỈE, DỈH, GHỈC, ACỈD} Bước 3: Loại các phụ thuộc hàm dư thừa: + + • Với BỈA: ta cĩ BF \{}B→A = B , A∉ BF \{}B→A nên BỈA là khơng thừa + + • Với DAỈC: ta cĩ DAF \{}DA→C = DAEH , C ∉ DAF \{}DA→C nên DAỈC là khơng thừa + + • Với DAỈE: ta cĩ DAF \{}DA→E = DACH , E ∉ DAF \{}DA→E nên DAỈE là khơng thừa + + • Với DỈH: ta cĩ DF \{}D→H = D , H ∉ DF \{}D→H nên DỈH là khơng thừa + + • Với GHỈC: ta cĩ GH F \{}GH →C = GH , C ∉ GH F \{}GH →C nên GHỈC là khơng thừa + + • Với ACỈD: ta cĩ ACF \{}AC→D = AC , D ∉ ACF \{}AC→D nên ACỈD là khơng thừa Vậy phủ tối thiểu của F: PTT(F) = { BỈA , DAỈC, DAỈE, DỈH, GHỈC, ACỈD} 2. Khĩa 2.1. Định nghĩa Cho lược đồ quan hệ Q(A1, A2, , An), Q+ là tập thuộc tính của quan hệ Q, F là tập phụ thuộc hàm trên Q, K là tập con của Q+. Khi đĩ K gọi là một khĩa của Q nếu: Trang 81/109
  28. + + (i) K F = Q + + (ii) Khơng tồn tại K'⊂ K sao cho K’ F = Q Thuộc tính A được gọi là thuộc tính khĩa nếu A∈ K , trong đĩ K là khĩa của Q. Ngược lại thuộc tính A được gọi là thuộc tính khơng khĩa. K’ được gọi là siêu khĩa nếu K ⊆ K' . 2.2. Thuật tốn tìm khĩa 2.2.1. Thuật tốn tìm một khĩa Sử dụng đồ thị cĩ hướng để tìm khĩa như sau: Bước 1: • Mỗi nút của đồ thị là tên một thuộc tính của lược đồ quan hệ R • Cung nối hai thuộc tính A và B thể hiện phụ thuộc hàm A Ỉ B • Thuộc tính chỉ cĩ các mũi tên đi ra (nghĩa là chỉ nằm trong vế trái của phụ thuộc hàm) được gọi là nút gốc • Thuộc tính chỉ cĩ các mũi tên đi tới (nghĩa là chỉ nằm trong vế phải của phụ thuộc hàm) được gọi là nút lá Bước 2: • Xuất phát từ tập các nút gốc (X), dựa trên tập các phụ thuộc hàm F, tìm bao đĩng + X F . + + • Nếu X F = Q thì X là khĩa, ngược lại bổ sung một thuộc tính khơng thuộc nút lá vào X rồi thực hiện tìm bao đĩng của X. Dừng khi tìm được một khĩa của R. Ví dụ Cho lược đồ quan hệ R(A, B, C, D, E, G, H) và tập phụ thuộc hàm F={ BỈA , DAỈCE, DỈH, GHỈC, ACỈD} Tìm một khĩa của R. Phân rã vế phải ta cĩ F ={ BỈA , DAỈC, DAỈE, DỈH, GHỈC, ACỈD} Trang 82/109
  29. Nhận thấy từ đồ thị trên, nút B và G là nút gốc. Khĩa của R phải chứa thuộc tính B hoặc G, trong ví dụ này chọn B. + + + BF = BA , Vì BF ≠ Q nên B khơng là khĩa. Nhận thấy D là thuộc tính ở vế trái của ba phụ thuộc hàm trong F nên bổ sung thuộc tính D vào để xét khĩa. + + + BDF = BDACEH , vì BDF ≠ Q nên BD khơng là khĩa. Bổ sung thuộc tính G. + + + BDGF = BDGACEH , vì BDGF = Q nên BDG là khĩa. 2.2.2. Thuật tốn tìm tất cả các khĩa Tập thuộc tính nguồn, ký hiệu là N, là tập chứa những thuộc tính chỉ xuất hiện ở vế trái, khơng nằm bên vế trái và vế phải của mọi phụ thuộc hàm Tập thuộc tính trung gian, ký hiệu là TG, là tập chứa những thuộc tính vừa xuất hiện ở vế trái, vừa xuất hiện ở vế phải trong các phụ thuộc hàm Thuật tốn + + Bước 1: Tính tập nguồn N. Nếu N F = Q thì chỉ cĩ 1 khố là N, ngược lại qua bước 2 Bước 2: Tính tập trung gian TG. Tính tập tất cả các tập con Xi của tập TG. Bước 3: Tìm tập S chứa mọi siêu khĩa Si: + + Với mỗi Xi, nếu ()N ∪ X i F = Q thì Si = (N ∪ X i ) Bước 4: Loại các siêu khĩa khơng tối tiểu: ∀Si , S j ∈ S , nếu Si ⊂ S j thì S = S − S j Trang 83/109
  30. Ví dụ. Cho lược đồ quan hệ R(A, B, C) và tập phụ thuộc hàm F={ ABỈC, CỈA} Tìm mọi khĩa của R. + + Bước 1: N = {B}, N F = B ≠ Q Bước 2: TG = {AC}, tập các tập con trung gian là CTG = {∅, A,C, AC} Bước 3: N ∪ X + + + N Xi i (N ∪ X i ) ()N ∪ X i = Q ? B ∅ B B Sai B A BA BAC Đúng B C BC BCA Đúng B AC BAC BAC Đúng Như vậy tập siêu khố S = {}BA, BC, BAC Bước 4: Loại các siêu khĩa khơng tối tiểu: Nhận thấy rằng BA ⊂ BAC nên loại siêu khĩa BAC. Tập các khĩa cịn lại là S = {}BA, BC Cải tiến thuật tốn + + Nhận thấy rằng ở bước 3, khi xét tập một con Xi, nếu (N ∪ X i ) = Q , khi đĩ N ∪ X i là một khố. Trong trường hợp này nếu xét tiếp các tập Xj : Xi ⊂ Xj , thì hiển nhiên + + ()N ∪ Xj = Q , và cuối cùng siêu khố N ∪ X j cũng sẽ bị loại ở bước 4. Hơn nữa, bước tính tập con đầu tiên là rỗng cũng khơng cần tính. + + Do đĩ, khi tính bao đĩng của tập thuộc tính, khơng tính Xi = ∅ và nếu ()N ∪ X i = Q , thực hiện loại bỏ các tính tốn cho các trường hợp Xj : Xi ⊂ Xj . Khi đĩ kết thúc thuật tốn tại bước 3, khơng cần thực hiện bước 4 vì tất cả các khố nhận được ở bước 3 đều là tối tiểu. 3. Ràng buộc tồn vẹn 3.1. Ràng buộc tồn vẹn – các yếu tố của ràng buộc tồn vẹn Trang 84/109
  31. Trong CSDL luơn tồn tại nhiều mối liên hệ giữa các thuộc tính, các bộ, các bảng với nhau. Các mối liên hệ này là những điều kiện bất biến mà tất cả các bộ của những quan hệ cĩ liên quan đều phải thỏa mãn tại mọi thời điểm. Những điều kiện bất biến đĩ được gọi là ràng buộc tồn vẹn. Ràng buộc tồn vẹn (Intergrity constraint) viết tắt tiếng việt là RBTV, là một điều kiện được định nghĩa liên quan đến một hay nhiều quan hệ khác nhau. Các mối liên hệ ràng buộc là những điều kiện bất biến mà mọi thể hiện của quan hệ đều phải thỏa mãn trong mọi thời điểm. Trong thực tế, RBTV là các quy tắc quản lý trong thế giới thực. Mục đích của RBTV là bảo đảm tính nhất quán của dữ liệu, bảo đảm rằng dữ liệu luơn biểu diễn đúng ngữ nghĩa trong thực tế. Ví dụ: với giao dịch chuyển tiền, thực hiện qua các bước sau: • Tại tài khoản của người gởi: trừ tiền • Tại tài khoản của người nhận: thêm tiền • Nếu cả hai việc trên đều thành cơng thì hồn tất giao dịch, ngược lại quay lui giao dịch. Qua ví dụ trên, giao dịch thực hiện trừ tiền và tăng tiền trong tài khoản của người gởi và người nhận, nếu khơng thì khơng thực hiện gì cả. Việc thực hiện giao dịch cần phải bảo đảm tính đúng của dữ liệu. Mỗi một RBTV cĩ các yếu tố sau: Bối cảnh Bối cảnh là một hay nhiều quan hệ cần phải sử dụng để kiểm tra RBTV. Hay nĩi cách khác bối cảnh của RBTV là những quan hệ cĩ khả năng bị vi phạm RBTV khi thực hiện các thao tác cập nhật dữ liệu (thêm, xĩa, sửa các bộ) Biểu diễn: điều kiện hay nội dung Điều kiện được kiểm tra trên mọi thay đổi của thể hiện của các quan hệ cơ sở. Điều kiện của một RBTV cĩ thể được biểu diễn bằng nhiều cách khác nhau, chẳng hạn như ngơn ngữ tự nhiên, ngơn ngữ hình thức (thuật tốn, đại số quan hệ, ). Khi một RBTV bị vi phạm, cĩ thể xử lý bằng cách thơng báo cho NSD biết RBTV đã bị vi phạm như thế nào, hoặc từ chối thực hiện thao tác cập nhật dữ liệu và thơng báo cho NSD biết thao tác cập nhật bị từ chối trên các quan hệ nào và tại các bước nào. Trang 85/109
  32. Tầm ảnh hưởng Trong quá trình phân tích thiết kế CSDL, cần thiết phải lập bảng tầm ảnh hưởng cho RBTV nhằm xác định thời điểm cần kiểm tra RBTV, và khi kiểm tra cần kiểm tra trên quan hệ nào. Bảng tầm ảnh hưởng của một RBTV cĩ dạng sau: Tên RBTV Thêm Xĩa Sửa R1 + - +(A) R2 + - +(B) Rn - - + Trong đĩ: Dấu + thể hiện thao tác cĩ thể gây ra vi phạm RBTV. Trong trường hợp +(A) cho biết thao tác sửa cĩ thể gây vi phạm trên thuộc tính A. Dấu - thể hiện thao tác khơng vi phạm RBTV. 3.2. Các loại ràng buộc tồn vẹn Trong quá trình phân tích thiết kế CSDL, yêu cầu cần thiết là phải tìm được những RBTV tiềm ẩn trong CSDL. Việc phân loại RBTV cho phép người phân tích tìm kiếm đầy đủ, tránh bỏ sĩt những RBTV. Các loại RBTV được phân thành hai dạng chính như sau: • RBTV cĩ bối cảnh là một quan hệ • RBTV cĩ bối cảnh là nhiều quan hệ 3.2.1. Ràng buộc tồn vẹn cĩ bối cảnh là một quan hệ RBTV cĩ bối cảnh là một quan hệ được chia thành ba loại: RBTV miền giá trị, RBTV liên bộ và RBTV liên thuộc tính 3.2.1.1. Ràng buộc tồn vẹn miền giá trị Quy định rõ về miền giá trị của một thuộc tính. Ví dụ. Thời gian phân cơng tham gia đề án của một nhân viên khơng quá 40h/tuần • Bối cảnh: quan hệ PHANCONG Trang 86/109
  33. • Biểu diễn: ∀pc ∈ PHANCONG(pc.ThoiGian ≤ 40) • Bảng tầm ảnh hưởng: RB1 Thêm Xĩa Sửa PHANCONG + - +(ThoiGian) Ví dụ. Điểm của mơn học phải là thang điểm 10 • Bối cảnh: quan hệ KETQUA (MaMH, MaLop, MaKH, Diem ) • Biểu diễn: ∀kq ∈ KETQUA(kq.Diem ≥ 0 ∧ kq.Diem ≤ 10) • Bảng tầm ảnh hưởng: RB2 Thêm Xĩa Sửa KETQUA + - +(Diem) 3.2.1.2. Ràng buộc tồn vẹn liên thuộc tính Quy định các ràng buộc giữa các thuộc tính khác nhau trong cùng một quan hệ Ví dụ. Ngày trả sách phải là bằng hoặc sau ngày mượn sách • Bối cảnh: quan hệ MUONSACH(MaSach, MaDocGia, NgayMuon, NgayHenTra, NgayThucTra) • Biểu diễn: ∀ms ∈ MUONSACH ()ms.NgayMuon ≤ ms.NgayHenTra ∧ ms.NgayMuon ≤ ms.NgayThucTra • Bảng tầm ảnh hưởng: RB3 Thêm Xĩa Sửa MUONSACH + - +(NgayMuon, NgayHenTra, NgayThucTra) 3.2.1.3. Ràng buộc tồn vẹn liên bộ Quy định sự tồn tại của một hoặc nhiều bộ phụ thuộc vào sự tồn tại của một hoặc nhiều bộ khác trong cùng quan hệ. RBTV khĩa chính là RBTV liên bộ Trang 87/109
  34. Ví dụ. Mỗi đề án trong cơng ty cĩ một mã duy nhất để phân biệt với các đề án khác • Bối cảnh: quan hệ DEAN • Điều kiện: ∀da1,da2 ∈ DEAN : da1 ≠ da2 ⇒ (da1.MaDA ≠ da2.MaDA) • Bảng tầm ảnh hưởng: RB4 Thêm Xĩa Sửa DEAN + - +(MaDA) RBTV về số lượng các bộ trong một quan hệ. Ví dụ. Mỗi sinh viên trong một học kỳ được đăng ký khơng quá 8 mơn học • Bối cảnh: quan hệ DANGKY(MaSV, MaMH) • Biểu diễn: ∀dk1∈ DANGKY : count(dk2 ∈ DANGKY | dk2.MaSV = dk1.MaSV ) ≤ 8, trong đĩ count() là hàm đếm số bộ của một quan hệ thỏa điều kiện trong ngoặc (). • Bảng tầm ảnh hưởng: RB4 Thêm Xĩa Sửa DANGKY + - +(MaSV) 3.2.2. Ràng buộc tồn vẹn cĩ bối cảnh là nhiều quan hệ RBTV cĩ bối cảnh là nhiều quan hệ được chia thành năm loại: • RBTV tham chiếu • RBTV liên bộ - liên quan hệ • RBTV liên thuộc tính - liên quan hệ • RBTV do thuộc tính tổng hợp • RBTV do chu trình 3.2.2.1. RBTV tham chiếu Quy định giá trị xuất hiện của một tập thuộc tính trong một quan hệ phải xuất hiện trong một tập thuộc tính trong một quan hệ khác. RBTV này cịn được gọi là RBTV tham chiếu, RBTV phụ thuộc tồn tại hay RBTV khĩa ngoại. Trang 88/109
  35. Ví dụ RBTV trên 2 quan hệ Một nhân viên phải thuộc về một phịng trong cơng ty, nghĩa là trong quan hệ NHANVIEN, nếu một mã phịng (Phong) mà nhân viên trực thuộc xuất hiện, thì mã phịng này phải xuất hiện trong quan hệ PHONGBAN, cụ thể là thuộc tính (MaPhong). Như vậy: • Bối cảnh: NHANVIEN, PHONGBAN • Biểu diễn: ∀nv ∈ NHANVIEN()()nv.Phong = NULL ∨ (∃pb ∈ PHONGBAN(nv.Phong = pb.MaPhong)) • Bảng tầm ảnh hưởng: RB5 Thêm Xĩa Sửa NHANVIEN + - +(Phong) PHONGBAN - + +(MaPhong) Ví dụ RBTV trên 1 quan hệ Người quản lý (MaNQL) của một nhân viên cũng phải là một nhân viên trong cơng ty • Bối cảnh: NHANVIEN • Điều kiện: ∀nv ∈ NHANVIEN()()nv.MaNQL = NULL ∨ (∃nv1∈ NHANVIEN (nv.MaNQL = nv1.MaNV )) • Bảng tầm ảnh hưởng: RB6 Thêm Xĩa Sửa NHANVIEN + - +(MaNV, MaNQL) Ảnh hưởng của RBTV đối với các thao tác thêm, xĩa, sửa dữ liệu Giả sử r2 cĩ một khĩa ngoại α tham chiếu đến K trong r1, khi đĩ: π α (r2 ) ⊆ π K (r1 ) Thêm Khi thêm một bộ t2 vào r2 thì phải bảo đảm tồn tại t1 trong r1 sao cho t1[K] = t2 [α] Trang 89/109
  36. Xĩa Giả sử xĩa t1 khỏi r1. Khi đĩ cần xử lý các bộ trong r2 tham chiếu tới t1, nghĩa là s = σ α =t1[K ] (r2 ) . Nếu s ≠ ∅ thì • Khơng thực hiện hành động xĩa dữ liệu, hoặc • Xĩa dây chuyền, nghĩa là xĩa tất cả các bộ trong s Sửa Trường hợp cập nhật t2 trong r2 • Cập nhật t2 trong r2, sửa khĩa ngoại α • Tương tự như trường hợp thêm dữ liệu ' • Kiểm tra t2 [α]∈π K (r1 ) Trường hợp cập nhật t1 trong r1 • Cập nhật t1 trong r1 • Tương tự như trường hợp xĩa dữ liệu • Kiểm tra σ α =t1[K ] (r2 ) = ∅ 3.2.2.2. RBTV liên bộ - liên quan hệ Quy định về từng nhĩm các bộ của nhiều quan hệ bối cảnh khác nhau. Ví dụ Một hĩa đơn bán hàng phải cĩ ít nhất một mặt hàng, nghĩa là một chi tiết hĩa đơn bán hàng phải cĩ ít nhất một mặt hàng. • Bối cảnh: HOADON, CTIETHD • Biểu diễn: ∀hd ∈ HOADON(∃cthd ∈ CTIETHD(hd.MaHD = cthd.MaHD)) • Bảng tầm ảnh hưởng: RB7 Thêm Xĩa Sửa HOADON + - +(MaHD) CTIETHD - + +(MaHD) Trang 90/109
  37. 3.2.2.3. RBTV liên thuộc tính - liên quan hệ Quy định về mối liên hệ giữa các thuộc tính trên nhiều quan hệ bối cảnh khác nhau. Ví dụ Giả sử cho phép thanh tốn tiền nhiều lần và thanh tốn sau khi mua hàng, khi đĩ ngày thanh tốn tiền theo một hĩa đơn mua hàng phải bằng hoặc sau ngày mua hàng. • Bối cảnh: HOADON(MaHD, MaKH, NgayHD, TriGia), THANHTOAN(MaHD, NgayTToan, LanTToan, SoTienTToan) • Biểu diễn: ∀hd ∈ HOADON()∀tt ∈THANHTOAN(hd.MaHD = tt.MahD ⇒ hd.NgayHD ≤ tt.NgayTToan) • Bảng tầm ảnh hưởng: RB8 Thêm Xĩa Sửa HOADON + - +(MaHD, NgayHD) THANHTOAN + - +(MaHD, NgayTToan) 3.2.2.4. RBTV do thuộc tính tổng hợp Quy định về mối liên hệ giữa các thuộc tính do sự cĩ mặt của thuộc tính tính tốn. Ví dụ Điểm trung bình của sinh viên bằng trung bình của các mơn mà sinh viên theo học • Bối cảnh: SINHVIEN(MaSV, HoSV, TenSV, Khoa, DTB) KETQUA (MaSV, MaMon, Diem) • Biểu diễn: ∀sv ∈ SINHVIEN()∃kq ∈ KETQUA(sv.MaSV = kq.MaSV ⇒ sv.DTB = AVG()kq.Diem ) • Bảng tầm ảnh hưởng: RB9 Thêm Xĩa Sửa SINHVIEN + - +(MaSV, DTB) KETQUA + + +(MaSV, Diem) 3.2.2.5. RBTV do chu trình Trang 91/109
  38. Xảy ra khi cĩ sự hiện diện của chu trình. Để nhận diện chu trình, người ta biểu diễn lược đồ CSDL như sau: Nút thể hiện lược đồ NHANVIEN Nút thuộc tính kết MaNV=MaNV Cung nối giữa nút lược đồ và nút thuộc MaNV=MaNV tính kết NHANVIEN Ví dụ Một nhân viên chỉ được phân cơng vào các đề án do phịng mình chủ trì • Bối cảnh: NHANVIEN, DEAN, PHANCONG Đồ thị thể hiện chu trình như sau: MaNV=MaNV PHANCONG NHANVIEN Phong=Phong MaDA=MaDA DEAN • Biểu diễn: ∀pc ∈ PHANCONG()∃nvda ∈ NV _ DA(nvda.MaNV = pc.MaNV ∧ nvda.MaDA = pc.MaDA) với: NV _ DA ← NHANVIEN >< Phong =MaPhong DEAN • Bảng tầm ảnh hưởng: RB10 Thêm Xĩa Sửa Trang 92/109
  39. NHANVIEN - + +(MaNV, Phong) DEAN - + +(MaDA, Phong) PHANCONG + - +(MaDA, MaNV) 4. Bài tập Bài tập 1 • Hãy chứng minh 3 tính chất phân rã, kết hợp và tựa bắc cầu. • Hãy tìm hiểu các tính chất của bao đĩng tập thuộc tính, phủ tối thiểu Bài tập 2 Cho lược đồ quan hệ R(A, B, C, D, E, G) và tập phụ thuộc hàm F={AỈC , AỈEG, BỈD, GỈE } + + + Tìm ABF ,CGDF , AF Bài tập 3 Cho lược đồ quan hệ R(A, B, C, D, E, G) và tập phụ thuộc hàm F={BỈC , AỈEG, BỈA, GỈE } + + + Tìm ABF ,CGDF , AF Bài tập 4 Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={AỈC , BCỈD, DỈE, EỈA } + + + Tìm ABF , BDF , DF Bài tập 5 Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F={BỈC , ACỈD, DỈG, AGỈE } Cho biết AC → E cĩ thuộc F+ khơng? Cho biết BD → AD cĩ thuộc F+ khơng? Trang 93/109
  40. Với các bài tập 7, 8, 9: • Tìm một khĩa (theo thuật tốn tìm một khĩa) • Tìm mọi khĩa (theo thuật tốn tìm mọi khĩa) • Tìm phủ tối thiểu Bài tập 7 Cho lược đồ quan hệ R(A, B, C, D) và tập phụ thuộc hàm F={ABỈCD, BỈC,CỈD} Bài tập 8 Cho lược đồ quan hệ R {ABCDEFGHKLM} và tập phụ thuộc hàm F={ A Ỉ B, C ỈD, EỈ F, G ỈAHK, AH Ỉ G, GLC Ỉ M } Bài tập 9 Cho lược đồ quan hệ R {ABCDEFGHKL} và tập phụ thuộc hàm F={A ỈB, AC ỈD, F Ỉ G, FK Ỉ LEH, E Ỉ FH} Bài tập 10 Với hai bài tốn tình huống là quản lý đề án và quản lý ngân hàng, ngoại trừ các ràng buộc khố chính và khố ngoại, hãy tìm tất cả các RBTV theo yêu cầu: bối cảnh, biểu diễn, tầm ảnh hưởng. Với những RBTV tìm được, hãy phân theo từng loại RBTV. Trang 94/109
  41. Chương 8 Dạng chuẩn và chuẩn hĩa cơ sở dữ liệu Chương này giới thiệu các dạng chuẩn, phân rã bảo tồn thơng tin, bảo tồn phụ thuộc hàm, qua đĩ cũng trình bày cách phân rã bảo tồn bảo tồn thơng tin và bảo tồn phụ thuộc. 1. Dạng chuẩn của lược đồ quan hệ Để dễ dàng trình bày các dạng chuẩn, cần nắm rõ các khái niệm: Thuộc tính khố: Cho lược đồ quan hệ Q()A1 , A2 , , An , thuộc tính B được gọi là thuộc tính khố nếu B là một thuộc tính thành phần trong một khố nào đĩ của Q, ngược lại B được gọi là thuộc tính khơng khố Ví dụ: R(A, B, C, D), F={ABỈC, BỈD, BCỈA} Trong ví dụ trên, lược đồ R cĩ 2 khố là AB, BC. Khi đĩ A, B, C là thuộc tính khố, D là thuộc tính khơng khố. Giá trị nguyên tố Giá trị nguyên tố là giá trị khơng phân nhỏ được nữa. Ví dụ: Giá trị ChiTietMua: “Bánh Orion 1 gĩi, Kẹo mút 2 cây” khơng phải là giá trị nguyên tố vì cĩ thể phân thành: tên hàng, số lượng, đơn vị tính. 1.1. Dạng chuẩn 1 Lược đồ Q ở dạng chuẩn 1 nếu mọi thuộc tính đều mang giá trị nguyên tố. Trong bài tốn xét dạng chuẩn, dạng chuẩn thấp nhất là dạng chuẩn 1. Ví dụ. Cho lược đồ HOADON(MaHD, MaKH, NgayHD, CtietMua, SoTien), và cĩ thể hiện như sau Trang 95/109
  42. MaHD MaKH NgayHD CtietMua SoTien Tên hàng Số lượng ĐVT HD01 KH01 15-10-05 Bánh Orion 1 Gĩi 25.000 Kẹo mút 2 Cây 2.000 HD02 KH01 18-10-05 Gạo 2 Kg 30.000 HD03 KH02 24-10-05 Đường 1 Kg 15.000 Bánh AFC 2 Gĩi 24.000 Nhận thấy rằng CTiếtMua khơng mang giá trị nguyên tố, do đĩ HOADON khơng đạt dạng chuẩn 1. 1.2. Dạng chuẩn 2 1.2.1. Định nghĩa Lược đồ Q ở dạng chuẩn 2 nếu thoả: (1) Q đạt dạng chuẩn 1 (2) Mọi thuộc tính khơng khĩa của Q đều phụ thuộc đầy đủ vào khĩa 1.2.2. Kiểm tra dạng chuẩn 2 Để kiểm tra dạng chuẩn 2 thực hiện: Bước 1: Tìm mọi khĩa của Q Bước 2: Với mỗi khĩa K, tìm bao đĩng của tập tất cả các tập con thực sự Si của K + Bước 3: Nếu tồn tại bao đĩng Si chứa thuộc tính khơng khĩa thì Q khơng đạt dạng chuẩn 2, ngược lại Q đạt dạng chuẩn 2. Ví dụ 1. Cho Q1 (A, B, C, D), F={AỈB, BỈDC} Lược đồ chỉ cĩ một khĩa là A, nên mọi thuộc tính đều phụ thuộc đầy đủ vào khĩa. Do vậy Q1 đạt dạng chuẩn 2. Ví dụ 2. Cho Q2 (A, B, C, D), F={ABỈD, CỈD} Lược đồ cĩ khĩa là ABC, ngồi ra cịn cĩ C⊂ABC mà CỈD, trong đĩ D là thuộc tính khơng khĩa (nghĩa là thuộc tính D khơng phụ thuộc đầy đủ vào khĩa). Do vậy Q2 khơng đạt dạng chuẩn 2. Trang 96/109
  43. Ví dụ 3: Xem ví dụ đơn giản bằng CSDL gồm 2 quan hệ MONHOC, SINHVIEN như sau: MONHOC (MaMH, TenMH, STC, Loai) Tân từ: Mỗi mơn học cĩ mã mơn học (MaMH) duy nhất để phân biệt với các mơn học khác, cĩ tên mơn học (TenMH), số tín chỉ (STC), và loại bắt buộc hay tự chọn (Loai) MaMH TenMH STC Loai CT101 Nhập mơn tin học 4 BB CT102 TH kỹ năng máy tính 5 BB TN311 Xác suất thống kê 3 BB CT103 Thiết kế Web 4 TC CT110 Nguyên lý lập trình 2 5 BB SINHVIEN (MSSV, MaMH, TenSV, DiaChi, Diem) Tân từ: Mỗi sinh viên (MSSV) khi thi một mơn học (MaMH) được ghi nhận lại điểm (Diem), ngồi ra cịn cĩ thơng tin liên quan đến sinh viên như họ tên (TenSV), địa chỉ (DiaChi) MSSV MaMH TenSV DiaChi Diem 0310677 CT101 Nguyễn Thị Hoa 11 Nguyễn Cơng Trứ, Đà Lạt 6 0310678 CT101 Trần Hồng 20 Bùi Thị Xuân, Đà Lạt 4 0310679 CT101 Lê Thanh Sơn 2 Nhà Chung, Đà Lạt 7 0310677 CT102 Nguyễn Thị Hoa 11 Nguyễn Cơng Trứ, Đà Lạt 8 0310678 CT102 Trần Hồng 20 Bùi Thị Xuân, Đà Lạt 8 0310678 TN311 Trần Hồng 20 Bùi Thị Xuân, Đà Lạt 3 0310679 TN311 Lê Thanh Sơn 2 Nhà Chung, Đà Lạt 6 0310677 CT103 Nguyễn Thị Hoa 11 Nguyễn Cơng Trứ, Đà Lạt 9 0310678 CT103 Trần Hồng 20 Bùi Thị Xuân, Đà Lạt 7 Trang 97/109
  44. 0310000 CT110 Nguyễn Ngọc 1 Lê Hồng Phong, Đà Lạt 9 Ở quan hệ SINHVIEN cĩ thể nhận thấy các phụ thuộc: MSSV, MaMH Ỉ Diem MSSVỈTenSV, DiaChi Vậy quan hệ SINHVIEN khơng đạt dạng chuẩn 2 vì thuộc tính TenSV, DiaChi là thuộc tính khơng khố chỉ phụ thuộc vào MSSV: như vậy khơng phụ thuộc đầy đủ vào khố. Trong quá trình cập nhật và lưu trữ dữ liệu xuất hiện những vấn đề sau: • Ở quan hệ SINHVIEN, việc lưu trữ thơng tin một sinh viên bị lặp lại (tên, địa chỉ) • Quá trình cập nhật: o Sửa đổi: Khi cần sửa đổi địa chỉ của một sinh viên (ví dụ như Nguyễn Thị Hoa) cần phải sửa đổi 3 lần vì trùng lắp thơng tin, hơn nữa, khi sửa đổi thơng tin của về một sinh viên lại khơng liên quan đến thơng tin về thi cử. o Thêm: Nếu chèn thêm một bộ vào quan hệ SINHVIEN mà sinh viên chưa thi mơn nào thì khơng được vì khố MSSV, MaMH là khơng đầy đủ. Vấn đề này chỉ được khắc phục khi loại bỏ những thơng tin về kết quả thi cử ra khỏi quan hệ. o Xố: Giả sử rằng cần xĩa bỏ mơn CT110 mà danh sách sinh viên vẫn giữ nguyên. Khi đĩ xĩa bộ {‘CT110’, ‘Nguyên lý lập trình 2’, 5, ‘BB’} trong quan hệ MONHOC và xố bộ {‘0310000’, ‘CT110’, ‘Nguyễn Ngọc’, ‘1 Lê Hồng Phong, Đà Lạt’, 9} trong quan hệ SINHVIEN. Khi đĩ thơng tin về sinh viên sẽ bị mất. Để khắc phục những bất lợi trên, quan hệ SINHVIEN cĩ thể tách thành 2 quan hệ SINHVIEN (MSSV, TenSV, DiaChi) và KETQUATHI (MSSV, MaMH, Diem). Như vậy, 3 quan hệ trên đều đã ở dạng chuẩn thứ 2. Trang 98/109
  45. 1.3. Dạng chuẩn 3 1.3.1. Định nghĩa Định nghĩa 1 Với một lược đồ Q; X, Y là hai tập con của Q+; A là một thuộc tính. Khi đĩ A được gọi là phụ thuộc bắc cầu vào X nếu thỏa: (1) XỈY, YỈA (2) Y X (3) A ∉ XY Lược đồ Q ở dạng chuẩn 3 nếu mọi thuộc tính khơng khĩa đều khơng phụ thuộc bắc cầu vào khĩa. Việc kiểm tra dạng chuẩn 3 theo định nghĩa trên sẽ khĩ cài đặt. Ta cĩ thể thực hiện kiểm tra dạng chuẩn 3 theo định nghĩa sau: Định nghĩa 2 Lược đồ Q ở dạng chuẩn 3 nếu mọi phụ thuộc hàm XỈA∈F+, với A ∉ X đều cĩ: (1) X là siêu khĩa, hoặc (2) A là thuộc tính khĩa 1.3.2. Kiểm tra dạng chuẩn 3 Từ định nghĩa 2, để kiểm tra dạng chuẩn 3 thực hiện các bước sau: Bước 1: Tìm mọi khĩa của Q Bước 2: Phân rã vế phải của mọi phụ thuộc hàm trong F để tập F trở thành tập phụ thuộc hàm cĩ vế phải một thuộc tính Bước 3: Nếu mọi phụ thuộc hàm XỈA ∈F, mà A ∉ X đều thỏa (1) X là siêu khĩa (vế trái chứa một khĩa), hoặc (2) A là thuộc tính khĩa (vế phải là tập con của khĩa) thì Q đạt dạng chuẩn 3, ngược lại Q khơng đạt dạng chuẩn 3. Ví dụ. Cho Q (A, B, C, D), F={ABỈD, CỈD} Bước 1: Q cĩ một khĩa là ABC Trang 99/109
  46. Bước 2: Mọi phụ thuộc hàm trong F đều đã cĩ vế phải một thuộc tính. Bước 3: Với ABỈD, nhận thấy rằng D ∉ ABC cĩ • Vế trái (AB) khơng phải là siêu khĩa. • Hơn nữa vế phải (D) khơng là thuộc tính khĩa Vậy Q khơng đạt dạng chuẩn 3. 1.4. Dạng chuẩn BC (Boyce Codd) 1.4.1. Định nghĩa Lược đồ Q ở dạng chuẩn BC nếu mọi phụ thuộc hàm XỈA∈F+, với A ∉ X đều cĩ X là siêu khĩa. 1.4.2. Kiểm tra dạng chuẩn BC Từ định nghĩa, để kiểm tra dạng chuẩn BC thực hiện các bước sau: Bước 1: Tìm mọi khĩa của Q Bước 2: Phân rã vế phải của mọi phụ thuộc hàm trong F để tập F trở thành tập phụ thuộc hàm cĩ vế phải một thuộc tính Bước 3: Nếu mọi phụ thuộc hàm XỈA ∈F, mà A ∉ X đều thỏa X là siêu khĩa (vế trái chứa một khĩa), thì Q đạt dạng chuẩn BC, ngược lại Q khơng đạt dạng chuẩn BC. Ví dụ. Cho Q (A, B, C, D, E, I), F={ACDỈEBI, CEỈAD} Bước 1: Q cĩ hai khĩa là {ACD, CE} Bước 2: Phân rã vế phải của các phụ thuộc hàm trong F, ta cĩ: F={ACDỈE, ACDỈB, ACDỈI, CEỈA, CEỈD} Bước 3: Mọi phụ thuộc hàm trong F đều cĩ vế trái là một siêu khĩa Vậy Q đạt dạng chuẩn BC. 1.5. Kiểm tra dạng chuẩn Kiểm tra dạng chuẩn của lược đồ quan hệ Q Bước 1: Tìm mọi khĩa của Q Bước 2: Kiểm tra dạng chuẩn BC, nếu đúng thì Q đạt dạng chuẩn BC, Trang 100/109
  47. ngược lại qua bước 3. Bước 3: Kiểm tra dạng chuẩn 3, nếu đúng thì Q đạt dạng chuẩn 3, ngược lại qua bước 4. Bước 4: Kiểm tra dạng chuẩn 2, nếu đúng thì Q đạt dạng chuẩn 2, ngược lại Q đạt dạng chuẩn 1. Kiểm tra dạng chuẩn của lược đồ CSDL Dạng chuẩn của một lược đồ CSDL là dạng chuẩn thấp nhất trong các dạng chuẩn của các lược đồ quan hệ con. 2. Phép phân rã Mục tiêu của việc thiết kế CSDL quan hệ là tạo ra một tập các lược đồ quan hệ cho phép chúng ta lưu trữ thơng tin khơng cĩ những dư thừa khơng cần thiết và truy tìm thơng tin một cách dễ dàng, chính xác. Việc phân rã một lược đồ thành những lược đồ con đều mong muốn đạt được bảo tồn thơng tin và bảo tồn phụ thuộc. 2.1. Phân rã bảo tồn thơng tin Cho lược đồ quan hệ Q (TenNCC, DiaChiNCC, SanPham, DonGia) Phân rã Q thành Q1 và Q2 như sau: Q1 (TenNCC, SanPham, DonGia) Q2 (TenNCC, DiaChiNCC) Khi đĩ ta cĩ các thể hiện sau: Q TenNCC DiaChiNCC SanPham DonGia Nguyễn Mai 10 Nguyễn Cơng Trứ Bánh xốp 10.000 Nguyễn Mai 10 Nguyễn Cơng Trứ Kẹo mè 20.000 Nguyễn Mai 20 Nguyễn Văn Trỗi Kẹo mè 20.000 Q1 TenNCC SanPham DonGia Nguyễn Mai Bánh xốp 10.000 Trang 101/109
  48. Nguyễn Mai Kẹo mè 20.000 Q2 TenNCC DiaChiNCC Nguyễn Mai 10 Nguyễn Cơng Trứ Nguyễn Mai 20 Nguyễn Văn Trỗi Q1> <r.Q2 (r là kết quả của phép kết tự nhiên của các hình chiếu của nĩ trên Q1, Q2) 2.2. Phân rã bảo tồn phụ thuộc hàm Một vấn đề cần quan tâm khi phân rã lược đồ Q thành các lược đồ con Qi với tập các Fi tương ứng được tính từ tập phụ thuộc hàm F. Phép phân rã bảo tồn phụ thuộc (giữ lại Trang 102/109
  49. phụ thuộc) nếu với ri là thể hiện của Qi thoả điều kiện: ri chỉ thoả những phụ thuộc hàm + + XỈY ∈F với XY⊆Qi Định nghĩa Gọi Q1, Q2, , Qn là phân rã của lược đồ quan hệ Q, tập phụ thuộc hàm F trên Q. Hình + chiếu của F trên một tập các thuộc tính Qi ký hiệu ΠQi+(F) là tập các phụ thuộc hàm + + XỈY ∈F với XY⊆Qi + + + ΠQi+(F) = Fi ={XỈY | XỈY ∈F và XY⊆Qi } Khi đĩ phân rã là bảo tồn tập phụ thuộc hàm F nếu F ≡ ∪ ΠQi+(F) 3. Thiết kế CSDL bằng cách phân rã 3.1. Phân rã thành dạng chuẩn BC (hoặc dạng chuẩn 3) bảo tồn thơng tin 3.1.1. Thuật tốn Bước 1: Tìm tất cả các khĩa của Q Bước 2: Tìm phụ thuộc hàm XỈY ∈F cĩ X khơng là siêu khĩa và Y khơng chứa thuộc tính khĩa. • Nếu tìm thấy thì tách Q thành Q1 và Q2 theo cách: o Q1 = Q[XY]; F1 ≡ ΠQ1(F) (tìm bao đĩng của tất cả các tập con của XY để tính F1). Tiếp tục phân rã (Q1, F1). + + o Q2 = Q[Q - Y]; F2 ≡ ΠQ2(F) (tìm bao đĩng của tất cả các tập con của (Q - Y) để tính F2). Tiếp tục phân rã (Q2, F2). • Nếu khơng tìm thấy thì xét dạng chuẩn Qi: o Nếu mọi phụ thuộc hàm trong Fi đều cĩ vế trái là siêu khĩa thì Qi đạt dạng chuẩn BC o Nếu cĩ phụ thuộc hàm trong Fi cĩ vế trái khơng là siêu khĩa và vế phải là thuộc tính khĩa thì Qi đạt dạng chuẩn 3 3.1.2. Ví dụ Ví dụ 1 Cho Q (SDIM), F={SIỈD, SDỈM} Trang 103/109
  50. Bước 1: Q cĩ một khĩa là {SI} Bước 2: Phụ thuộc hàm SDỈM cĩ SD khơng là siêu khĩa nên tách: Q1 = (SDM); F1 = {SDỈM} Q2 = (SDI); F2 = {SIỈD} Để tìm tập phụ thuộc hàm F1, F2 cần tính bao đĩng của mọi tập con. Tìm F1: với Q1 = (SDM): bao đĩng của mọi tập con + S F = S + DF = D + M F = M + SDF = SDM + SM F = SM + DM F = DM + SDM F = SDM F1 = ΠQ1(F) = {SDỈM, SDỈSM, SDỈDM, SDỈSDM } ⇒ F1 = {SDỈM} Tìm F2: với Q2= (SDI): bao đĩng của mọi tập con + S F = S + DF = D + I F = I + SDF = SDM + SI F = SIDM + DI F = DI + SDI F = SDIM Trang 104/109
  51. F2 = ΠQ2(F) = {SIỈD, SIỈSD, SIỈDI, SIỈSDI } ⇒ F2 = {SIỈD} Bước 3: Mọi phụ thuộc hàm trong F1và F2 đều cĩ vế trái là một siêu khĩa nên Q1 và Q2 đạt dạng chuẩn BC. Ví dụ 2 Cho Q (ABCDE), F = {BCỈA, CỈD, AEỈB, BỈD, BỈE} Bước 1: 2 khĩa là {CB, CAE} Bước 2: Từ CỈ D tách thành: • Q1(CD), F1= {CỈD}, Khĩa C. Đạt dạng chuẩn BC. • Q2(CABE), F2= {BỈE, CBỈA, AEỈB} Chi tiết tính F1, F2 như sau: Tìm F1: với Q1 = (CD) + CF = CD + DF = D + CDF = CD Vậy F1 = {CỈD} Tìm F2: với Q2(CABE): + CF = CD + AF = A + BF = BDE + EF = E + CAF = CAD + CBF = CBADE + CEF = CED Trang 105/109
  52. + ABF = ABDE + AEF = AEBD + BEF = BED + CABF = CABDE + CAEF = CAEBD + CBEF = CBEAD + ABEF = ABED + CABEF = CABED F2= {BỈE, CBỈAE, ABỈE, AEỈB, CABỈE, CAEỈB, CBEỈA} Vậy F2= {BỈE, CBỈA, AEỈB} Xét dạng chuẩn Q2: Khố Q2: {CB, CAE}. Vậy Q2 đã đạt dạng chuẩn 3. 3.1.3. Cải tiến thuật tốn Nhận thấy rằng trong tìm phụ thuộc hàm hình chiếu trên Qi, xét tập một con Xi, nếu X + = Q + , khi đĩ nếu tiếp tục xét các tập Xj : Xi ⊂ Xj , thì hiển nhiên X + = Q + , và ()i F ()j F cuối cùng thì phụ thuộc hàm cĩ vế trái Xj cũng sẽ bị loại để chỉ chọn phụ thuộc hàm cĩ vế trái Xi. + + Do đĩ, khi tìm phụ thuộc hàm hình chiếu trên Qi, xét tập một con Xi, nếu ()X i F = Q , thực hiện loại bỏ các tính tốn cho các trường hợp Xj : Xi ⊂ Xj . Ví dụ: với tìm F2 như ví dụ trên: Q2(CABE), F = {BCỈA, CỈD, AEỈB, BỈD, BỈE} + CF = CD + AF = A + BF = BDE + EF = E Trang 106/109
  53. + CAF = CAD + CBF = CBADE , loại các tập CAB, CBE, CABE + CEF = CED + ABF = ABDE + AEF = AEBD + BEF = BED + ABEF = ABED F2= {BỈE, CBỈAE, ABỈE, AEỈB} Vậy F2= {BỈE, CBỈA, AEỈB} 3.2. Phân rã thành dạng chuẩn 3 vừa bảo tồn thơng tin vừa bảo tồn phụ thuộc hàm Bước 1: Tìm phủ tối thiểu của F. Bước 2: Loại bỏ tất cả các thuộc tính của Q khơng liên quan đến một phụ thuộc hàm nào của PTT(F). Bước 3: Nếu cĩ một phụ thuộc hàm trong PTT(F) liên quan đến mọi thuộc tính của Q thì khơng thể phân rã. Ngược lại, qua bước 4. Bước 4: Gom nhĩm những phụ thuộc hàm cĩ cùng vế trái. Với mỗi nhĩm phụ thuộc hàm cĩ cùng vế trái, tạo thành một lược đồ con. Bước 5: Kiểm tra các lược đồ con cĩ thoả dạng chuẩn 3 chưa, nếu chưa thì áp dụng bước 4 để phân rã tiếp. Ví dụ. Cho Q (CTHRSG), F={CỈT, HRỈC, HTỈR, CSỈG, HSỈR} PTT(F) = F = {CỈT, HRỈC, HTỈR, CSỈG, HSỈR} Ta cĩ kết quả phân rã Q1(CT), Q2(HRC), Q3(HTR), Q4(CSG), Q5(HRS) 4. Bài tập Bài tập 7, 8, 9 trong chương 7, với yêu cầu: - Phân rã thành dạng chuẩn BC hoặc dạng chuẩn 3 bảo tồn thơng tin Trang 107/109
  54. - Phân rã thành dạng chuẩn 3 bảo tồn thơng tin và bảo tồn phụ thuộc hàm Trang 108/109
  55. Tài Liệu Tham Khảo 1. Bài giảng Cơ sở dữ liệu, Nguyễn Hữu Tân, Đại Học Đà Lạt, 2004. 2. Bài tập cơ sở dữ liệu, Nguyễn Xuân Huy – Lê Hồi Bắc, NXB thống kê, 2003. 3. Giáo trình Cơ sở dữ liệu, Nguyễn Đăng Tỵ - Đỗ Phúc, Đại Học Quốc gia Tp. Hồ Chí Minh, 2001. 4. Nhập mơn Cơ sở dữ liệu quan hệ, Lê Tiến Vương, NXB Khoa học và Kỹ thuật, 1994. 5. David Maier, The theory of Relational Databases, Computer Science Press, Rockville, 1983. Trang 109/109