Bài giảng Cơ sở dữ liệu - Bài 9: Ngôn ngữ tân từ - Vũ Văn Định

BÀI 9. NGÔN NGỮ TÂN TỪ I. Logic toán và ứng dụng của nó vào CSDL. ĐN1 : Biểu thức logic là một phát biểu mà giá trị của nó có thể đúng hoặc sai. Biểu thức logic có giá trị luôn luôn đúng ( hoặc sai ) được gọi là hằng đúng hoặc hàng sai. 1. Một số khái niệm : - Hàm: là một ánh xạ từ một miền giá trị vào tập hợp gồm hai giá trị hoặc đúng hoặc sai, thường kí hiệu là f,g,h - Tân từ : Là một biểu thức được xây dựng dựa trên các biểu thức logic, thường kí hiệu P,Q,R - Các phép toán logic : phủ định (¬ ), kéo theo (=>), nối liền (), nối rời ( v ) - Các lượng từ : với mọi () và tồn tại () TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí - ĐN2 : Tân từ một ngôi được định nghĩa trên 1 tập X và một biến x có giá trị chạy trên các phần tử của X. Với mỗi giá trị của x, tân từ P(x) là một mệnh đề logic, tức là nó có giá trị hoặc là đúng hoặc là sai. VD: X là một tập hợp những người có tên như sau : X={ Hoa , Lan, Tuấn, Dũng, T.Anh,} Với tân từ NỮ (x) được xác dịnh như : “ x là người nữ”. Khi đó mệnh đề : NỮ ( Hoa) : cho kết quả là đúng. NỮ ( Tuấn ) : Cho kết quả là sai . TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí ĐN3: Tân từ n ngôi được định nghĩa trên các tập X1, X2,Xn và n biến x1, x2, , xn lấy giá trị trên các tập Xi tương ứng. Với mỗi ai Xi, xi = ai , tân từ n ngôi là một mệnh đề. Kí hiệu : P ( x1, x2, , xn) VD: CHA ( x1, x2 ) : “ x1 là cha của x2” TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí - ĐN4: Từ đựợc định nghĩa một cách truy hồi như sau : i. Từ là một hằng hay một biến ii. f (t1,t2,,tn) là một hàm n ngôi thì f là một từ. - ĐN5: Công thức : i. Công thức nguyên tố là một tân từ n ngôi P(t1,t2,.., tn) , trong đó t1, t2,.., tn là các từ. ii. Nếu F1, F2, .. ,Fn là các công thức thì các biểu thức sau: F1 v F2 , F1  F2 , F1 => f2, ¬ F1 cũng là các công thức. iii. Nếu F1 là công thức thì x: F1, x: F1 cũng là các công thức. iv. Nếu F1 là công thức thì ( F1) cũng là công thức. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí - ĐN6: - Một công thức được gọi là “đóng” nếu mọi biến của nó đều có kèm với lượng từ. - Một công thức được gọi là “mở” nếu tồn tại một biến không có kèm với lượng từ. Biến này gọi là biến tự do. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Diễn giải và mô hình. a. Diễn giải của một công thức: - Một diễn giải của một CT gồm 4 phần : * Miền giá trị của các biến công thức, KH là tập M. * Việc sử dụng công thức: hằng , hàm , tân từ. * Ý nghĩa của công thức * Xác định một quan hệ n ngôi trên tập Mn TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí VD: Cho M = {Tùng, Minh , Hưng, Long, Đoàn, Tuấn} và một CT C có dạng như sau : x  y (z (P(x,y) v P(y,z) => Q (x,z) ) Tập diễn giải của công thức có thể là : - M : miền giá trị của các biến x, y, z - Các tân từ : P: CHA ; Q: ONG - Ý nghĩa : * CHA (x, y): x có cha là y * ONG (x, y): x có ông là y. - Các quan hệ 2 ngôi trên M2 : CHA = {(Tùng, Minh), (Long, Đoàn), (Đoàn, Tuấn),(Minh, Long)} ONG = {(Tùng, Long ), (Minh, Đoàn), (Long, Tuấn) } TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí II. Ứng dụng logic toán trong CSDL 1. Dẫn nhập CSDL : mô hình hoá 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 của thế giới thực. Chú ý : i. Câu hỏi đóng tương ứng với CT đóng. Câu trả lời là có hiệu lực đúng hoặc sai. VD: Tùng có cha là Minh? CHA ( Tùng, Minh)? Con của Long là ai? x CON (Minh, x) ? ii. Câu hỏi mở tương ứng với một CT mở. VD: Cha của Long là ai ? CHA(Long, x ) ? TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Ngôn ngữ tân từ có biến là bộ -n Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n thoả các quy tắc sau : a. Biến: là một bộ của quan hệ b. Từ : là hằng, biến, hay biểu thức có dạng s[c] trong đó : s là biến, c là tập các thuộc tính ( gọi là từ chiếu) c. Các biểu thức: - R s : với R là một quan hệ; s là biến bộ-n được gọi là từ - t1  a, t1  t2: ở đây, t1, t2 là các từ chiếu,  là toán tử so sánh, a là một hằng. ĐN7: Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n đựơc biểu diễn như sau : { s | F } Trong đó s là biến bộ-n, F là một công thức chỉ có một biến tự do là s. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 2. Ngôn ngữ tân từ có biến là miền giá trị Một câu hỏi trong ngôn ngữ tân từ có biến là bộ -n thoả các quy tắc sau : a. Từ : là hằng hoặc biến. b. Công thức nguyên tố: i. Q (t1, t2,..,tn) : với Q là một quan hệ; ti là các từ ii. t1  a1, t2  a2: ở đây, ti là các từ , là phép toán c. Trong 1 CSDL, câu hỏi bằng ngôn ngữ tân từ có dạng : { ( x1, x2,, xk) | F ( x1, x2, , xk) } Ở đây xi (i= 1,2,..,k) là các biến tự do của F và F không có biến tự do nào khác. Câu trả lời là tập các bộ giá trị (x1, x2, .., xk ) mà khi thay vào F thì F là đúng. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí VD: Xét cơ sở dữ liệu Thực tập gồm 3 quan hệ sau đây: SV( SV#, HT, NS, QUE, HL) DT(DT#, TDT, CN, KP) SD(SV#, DT#, NTT, KM, KQ) Q1: Cho danh sách các sinh viên có quê Hà Nội và có điểm học lực >=8.0? - Diễn tả bằng ngôn ngữ tân từ có biến là bộ như sau: { r[HT] | SV r  r[QUE=‘Hà Nội’]  r[HL]>=8.0} Và bằng ngôn ngữ tân từ có biến là miền giá trị như sau: {n | x y z ( SV (n, x, y, ‘Hà Nội’, z)  z >=8.0)} TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Q2: Cho biết tên các sinh viên nam quê Hải Phòng có điểm học lực >8? - Diễn tả bằng ngôn ngữ tân từ có biến là bộ như sau: { r[HT] | SV r  r[GT]=‘Nam’  r[QUE] = ‘Hải Phòng’  r[HL]>=8} - Và bằng ngôn ngữ tân từ có biến là miền giá trị như sau: {n | x t z ( SV (n, x, y, ‘Nam’,’Hải Phòng’, z)  z > 8} TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Q3: Cho danh sách các sinh viên có điểm thực tập =10? - Diễn tả bằng ngôn ngữ tân từ có biến là bộ như sau: { r[HT] | p ( SV q  SD p  q[SV#]=pSV[#]  p[KQ]=9.0} - Và bằng ngôn ngữ tân từ có biến là miền giá trị như sau: {y | z t w a b c ( SV (x, y, z, t, w)  SD(x, a, b, c, 10)} TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí BTVN: Cho quan hệ Thực tập như trên, hãy viết các câu truy vấn sau bằng ngôn ngữ tân từ có biến là bộ -n và có biến là miền giá trị ? 1. Cho thông tin về những sinh viên sinh trước năm 1985 có quê ở Hà Nội? 2. Cho biết các địa điểm thực tập xa trường (KM >100) của đề tài số 5? 3. Cho biết mã của những đề tài có kinh phí lớn hơn 1 triệu và nhỏ hơn 2 triệu? 4. Cho biết mã của sinh viên dưới 20 tuổi, thực tập khá ( có điểm kết quả thực tập >=6.5) TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí Bài 9. Tối ưu hoá câu hỏi Nói chung, các ngôn ngữ bậc cao ( ngôn ngữ con dữ liệu ) đòi hỏi thực hiện trong máy đều rất tốn kém thời gian. Do vậy, trước khi thực hiện các câu hỏi thuộc các ngôn ngữ đó cần thiết phải biến đổi hợp lý để giảm thời gian tính toán. Việc làm đó gọi là "tối ưu hoá ". Ví dụ : Thực hiện câu truy vấn : Cho biết các thông tin cá nhân và việc thực tập của những sinh viên có điểm thực tập >=8. Ta nên chọn ra những sv có điểm thực tập >=8 trong quan hệ SD rồi mới đem kết nối với quan hệ SV để lấy ra nhứng thông tin các nhân của họ . TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí I. Các chiến lược tối ưu tổng quát 1. Thực hiện phép chọn sớm như có thể Biến đổi câu hỏi để đưa phép chọn vào thực hiện trước nhằm làm giảm bớt kích cỡ của kết quả trung gian và do vậy chi phí phải trả giá cho việc truy nhập bộ nhớ thứ cấp cũng như lưu trữ của bộ nhớ chính sẽ nhỏ đi. 2. Tổ hợp những phép chọn xác định với phép tích Đề - Các thành phép kết nối. Nếu kết quả của tích Đề - Các R x S là đối số của phép chọn và phép chọn liên quan tới các phép so sánh giữa các thuộc tính của R và S thì thay phép tích Đề - Các bằng phép kết nối. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 3. Tổ hợp dãy các phép tính một ngôi như các phép chọn và phép chiếu. Một dãy các phép một ngôi ( như phép chọn hoặc phép chiếu) mà kết quả của chúng phụ thuộc vào các bộ của một quan hệ độc lập thì có thể nhóm các phép đó lại. 4. Tìm các biểu thức con chung trong một biểu thức Nếu kết quả của một biểu thức con chung ( biểu thức xuất hiện hơn một lần) là một quan hệ không lớn và nó có thể được đọc từ bộ nhớ thứ cấp với ít thời gian hơn thì nên tính toán trước biểu thức đó chỉ một lần. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí 5. Xử lý các tệp trước Đối với các tệp số, có hai vấn đề quan trọng cần được xử lý trước là sắp xếp trước các tệp và thiết lập các tệp chỉ số. 6. Đánh giá trước khi thực hiện tính toán . Cần tính toán chi phí thực hiện các phép tính để có được trình tự thực hiện các phép tính một cách tốt nhất. TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí II. Biểu thức tương đương Hai biểu thức E1 và E2 gọi là tương đương ( viết tắt là ( E1  E 2 ) nếu chúng biểu diễn cùng một ánh xạ, nghĩa là nếu thay thế cùng các quan hệ cho tên các lược đồ tương ứng ở hai biểu thức cho ra cùng một kết quả. III. Các quy tắc liên quan tới phép kết nối và phép tích Đề- Các L1. Quy tắc giao hoán của phép kết nối và phép tích Đề-Các Nếu E1 và E2 là hai biểu thức quan hệ, F là điều kiện trên các thuộc tính của E1 và E2 thì : E1  E2  E2  E1 E1 * E2  E2 * E1 E1 x E2  E2 x E1 F F TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí L2. Quy tắc kết hợp của phép kết nối và phép tích Đề- Các Nếu E1, E2 và E3 là các biểu thức quan hệ, F1, F2 là điều kiện thì : (E1  E2 )  E3  E1  (E2  E3 ) (E1 * E2) * E3  E1 *( E2 * E3 ) (E1 x E2) x E3  E1 x ( E2 x E3 ) F1 F2 F1 F2 TopTaiLieu.Com | Chia Sẻ Tài Liệu Miễn Phí