Giáo trình Cơ sở dữ liệu: Phần 2 - Cao Thị Nhạn, Nguyễn Thị Thanh Bình

Giáo trình Cơ sở dữ liệu: Phần 2 trình bày ngôn ngữ tân từ, ngôn ngữ truy vấn SQL, các khái niệm liên quan đến phụ thuộc hàm, khóa, các thuật toán tìm phủ tối thiểu của tập phụ thuộc hàm, tìm khóa cuối, ràng buộc toàn vẹn dữ liệu, giới thiệu các dạng chuẩn, phân rã bảo toàn thông tin, bảo toàn phụ thuộc hàm, cách phân rã bảo toàn bảo toàn thông tin và bảo toàn phụ thuộc.
Nội dung trích xuất từ tài liệu:
Giáo trình Cơ sở dữ liệu: Phần 2 - Cao Thị Nhạn, Nguyễn Thị Thanh BìnhChươ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 haybiểu diễn một tình trạng thế giới thực. Ngôn ngữ tân từ ứng dụng logic toán để thể hiệntruy 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ệmDạ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ếnbộ. 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 , t 2 . A2 ,..., t n . An | P(t1 , t 2 ,..., t n , t n +1 ,..., t n + m )}, với: Trang 55/109 • t1 , t 2 ,..., t n , t n+1 ,..., t n + 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. t i . 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. t i . A θ c hoaë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 > 500000Nhậ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/109Mộ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 toá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 đúng1.3. Lượng từ tồn tại ∃ và với mọi ∀Biến bộ tự do và biến kết buộcMộ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 )Fhay 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ếtbuộc phụ thuộc vào nó là tự do hay kết buộc trong F1 và F2Biế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{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 ...