Bài giảng môn học Cơ sở dữ liệu

FROM Student WHERE suburb=‘‘Bundoora’’ ; BundooraNorman8507 BalwynMary8452 BundooraGlen3936 KewRobert1108 SuburbNameId Student BundooraNorman8507 BundooraGlen3936 SuburbNameId )(" StudentBundoorasuburb=σ 13 73 Truy vấn có điều kiện trên 1 bảng Một số ví dụ khác: • Đưa ra tên của các hãng cung ứng có trụ sở tại London SELECT sname FROM Supplier WHERE city = ‘London’; • Đưa ra mã số và tên của các hãng cung ứng nằm ở London và có số nhân viên lớn hơn 75 SELECT sid, sname FROM Supplier WHERE city = ‘London’ AND size > 75; 74 Biểu diễn điều kiện lựa chọn • Các phép toán quan hệ: =, !=, , = • Các phép toán logic: NOT, AND, OR • Phép toán phạm vi: BETWEEN, IN, LIKE – Kiểu dữ liệu số • attr BETWEEN val1 AND val2 ( (attr>=val1) and (attr<=val2) ) • attr IN (val1, val2, ...) ( (attr=val1) or (attr=val2) or ... ) – Kiểu dữ liệu xâu • LIKE: sử dụng đối sánh mẫu xâu với các ký tự % hoặc _,? (thay thế cho 1 ký tự bất kỳ), * hay % (thay thế cho 1 xâu ký tự bất kỳ) 75 Biểu diễn điều kiện lựa chọn - Ví dụ: • Đưa ra thông tin của các hãng cung ứng có số nhân viên trong khoảng từ 100 đến 150 SELECT * FROM Supplier WHERE size BETWEEN 100 AND 150; • Đưa ra mã số của hãng cung ứng mặt hàng P1 hoặc P2 – Cách 1: SELECT sid FROM SupplierProduct WHERE pid = ‘P1’ OR pid = ‘P2’; – Cách 2: SELECT sid FROM SupplierProduct WHERE pid IN (‘P1’, ‘P2’); 76 Biểu diễn điều kiện lựa chọn - Ví dụ (tiếp) • Đưa ra thông tin của hãng sản xuất có trụ sở đặt tại thành phố bắt đầu bằng chữ New SELECT * FROM SUPPLIER WHERE city LIKE ‘New%’; 77 Truy vấn có sử dụng phép toán đổi tên • SQL cho phép đổi tên các bảng và các cột trong một câu truy vấn (sau mệnh đề SELECT và FROM) sử dụng cấu trúc: • AS –Đưa ra tên và số nhân viên của các hãng cung ứng ở Paris SELECT sname AS HangOParis, size AS SoNhanVien FROM Supplier WHERE city = ‘Paris’; SELECT SID , Stud.Name as SName, Sub.Name as Subject FROM Student as Stud,Takes, Subject as Sub WHERE (Id=SID) and (SNO = No) 78 Truy vấn phức tạp trên nhiều bảng • Điều kiện kết nối SELECT T1.C1,T1.C2,T2.C1,T2.C4, ... FROM T1, T2 WHERE condition_expression • Ví dụ: đưa ra danh sách mã sinh vien (Id), tên sinh viên (Name), thành phố (Suburb), mã khoá học (Course) mà các sinh viên đã đăng ký SELECT Id, Name, Suburb,Course FROM Student,Enrol WHERE Id=SID 14 79 Truy vấn phức tạp trên nhiều bảng Một số ví dụ khác: • Đưa ra tên của hãng có cung ứng mặt hàng P1 SELECT sname FROM Supplier S, SupplyProduct SP WHERE S.sid = SP.sid AND SP.pid = ‘P1’; • Đưa ra tên và mã số của hãng cung ứng ít nhất một mặt hàng màu đỏ SELECT sname, sid FROM Supplier S, SupplyProduct SP, Product P WHERE S.sid = SP.sid AND P.pid = SP.pid AND P.colour = ‘red’; 80 Loại trừ các bản ghi trùng nhau • Từ khoá DISTINCT SELECT DISTINCT , , FROM ,, • Ví dụ: đưa ra danh sách tên các khoa (dept) tương ứng với các khoá học (Course). Mỗi giá trị chỉ hiện thị một lần SELECT DISTINCT Dept FROM Course 81 Tìm kiếm có sắp xếp • Sắp xếp các bản ghi kết quả theo một thứ tự cho trước SELECT , , FROM ,, [WHERE ] ORDER BY | [ASC|DESC] • Ví dụ: đưa ra danh sách tên các sinh viên theo thứ tự tăng dần SELECT Name FROM Student ORDER BY Name ASC 82 Phân nhóm các bản ghi kết quả • Phân nhóm các bản ghi kết quả theo giá trị của 1 hoặc nhiều thuộc tính SELECT , , FROM ,, [WHERE ] [GROUP BY, , ] • Cột được chỉ ra trong mệnh đề GroupBy được sử dụng làm cơ sở để chia nhóm. Cột này cũng bắt buộc phải được chỉ ra trong mệnh đề Select • Ví dụ đưa ra tên các sinh viên nhóm theo thành phố của sinh viên đó SELECT Suburb, Count(Id) FROM Student GROUP BY Suburb SELECT Suburb, Name FROM Student GROUP BY Suburb 83 Điều kiện hiển thị các bản ghi kết quả • Lựa chọn các bản ghi kết quả để hiển thị SELECT , , FROM ,, [WHERE ] HAVING • Ví dụ: đưa ra tên các thành phố có nhiều hơn 3 sinh viên SELECT Suburb, COUNT(ID) FROM Student GROUP BY Suburb HAVING COUNT(ID) > 3 84 Các phép toán tập hợp: UNION, MINUS, INTERSECT • Ví dụ: đưa ra danh sách tên các môn học không có sinh viên nào tham dự SELECT DISTINCT Subject.Name FROM Subject MINUS SELECT DISTINCT Subject.Name FROM Student, Takes, Subject WHERE Student.Id = Takes.SID and Takes.SNO = Subject.No • Tìm sid của hãng cung ứng đồng thời 2 mặt hàng P1 và P2 SELECT sid FROM SupplyProduct WHERE pid = ‘P1’ INTERSECT SELECT sid FROM SupplyProduct WHERE pid = ‘P2’ • Tìm mã số của hãng không cung ứng mặt hàng nào SELECT sid FROM Supplier MINUS SELECT sid FROM SupplyProduct 15 85 Các câu truy vấn lồng nhau • Là trường hợp các câu truy vấn (con) được viết lồng nhau • Thường được sử dụng để – Kiểm tra thành viên tập hợp (IN, NOT IN) – So sánh tập hợp (>ALL, >=ALL, <ALL,<=ALL,=ALL, NOT IN,SOME, ) • vd:SELECT * FROM Supplier WHERE SIZE>=ALL(SELECT SIZE FROM Supplier); – Kiểm tra các bảng rỗng (EXISTS hoặc NOT EXISTS) • Các truy vấn con lồng nhau thông qua mệnh đề WHERE 86 Các câu truy vấn lồng nhau (tiếp) • Kiểm tra thành viên tập hợp với IN và NOT IN: –Đưa ra mã số của các hãng cung ứng đồng thời 2 mặt hàng P1 và P2: SELECT DISTINCT sid FROM SupplyProduct WHERE pid = ‘P1’ AND sid IN (SELECT sid FROM SupplyProduct SP2 WHERE SP2.pid = ‘P2’); –Đưa ra sid của các hãng không cung ứng mặt hàng P3: SELECT sid FROM SupplyProduct WHERE sid NOT IN (SELECT sid From SupplyProduct SP2 WHERE SP2.pid = ‘P3’); 87 Các câu truy vấn lồng nhau (tiếp) • So sánh tập hợp: Sử dụng các phép toán , ≥,≤,=,≠ kèm với các mệnh đề ANY và ALL – Đưa ra tên của các hãng có số nhân viên đông nhất: SELECT sname FROM Supplier WHERE size ≥ ALL(SELECT size FROM Supplier) – Đưa ra sid của hãng cung ứng một mặt hàng với số lượng bằng ít nhất 1 trong số lượng các mặt hàng được cung ứng bởi S2 SELECT sid FROM SupplyProduct WHERE sid ≠ ‘S2’ AND quantity = ANY(SELECT quantity FROM SupplyProduct SP2 WHERE SP2.sid = ‘S2’); 88 Các câu truy vấn lồng nhau (tiếp) • Kiểm tra tập hợp rỗng với EXISTS và NOT EXISTS –EXISTS(câu truy vấn con): nhận giá trị đúng khi câu truy vấn con cho ra kết quả là một quan hệ khác rỗng –NOT EXISTS(câu truy vấn con): nhận giá trị đúng khi câu truy vấn con cho ra kết quả là một quan hệ rỗng 89 Các câu truy vấn lồng nhau (tiếp) • Đưa ra thông tin của các nhà cung cấp đã cung ứng ít nhất một mặt hàng SELECT * FROM Supplier S WHERE EXISTS (SELECT sid FROM SupplyProduct SP WHERE S.sid = SP.sid); • Đưa ra thông tin của các nhà cung cấp không cung ứng mặt hàng nào SELECT * FROM Supplier S WHERE NOT EXISTS (SELECT * FROM SupplyProduct SP WHERE S.sid = SP.sid); 90 Các hàm thư viện • Hàm tính toán trên nhóm các bản ghi – MAX/MIN – SUM – AVG – COUNT • Hàm tính toán trên bản ghi – Hàm toán học: ABS, SQRT, LOG, EXP, SIGN, ROUND – Hàm xử lý xâu ký tự: LEN, LEFT, RIGHT, MID – Hàm xử lý thời gian: DATE, DAY, MONTH, YEAR, HOUR, MINUTE, SECOND – Hàm chuyển đổi kiểu giá trị: FORMAT 16 91 Một số ví dụ với các hàm thư viện • Có bao nhiêu mặt hàng khác nhau được cung ứng SELECT COUNT(DISTINCT pid) FROM SupplyProduct; • Có tổng cộng bao nhiêu nhân viên làm cho các hãng ở Paris SELECT SUM(size) FROM Supplier WHERE city = ‘Paris’; • Đưa ra số lượng mặt hàng trung bình mà hãng S1 cung ứng SELECT AVG(quantity) FROM SupplyProduct WHERE sid = ‘S1’; 92 Một số truy vấn phức tạp • Đưa ra tên của hãng S1 và tổng số mặt hàng mà hãng đó cung ứng SELECT sname, SUM(quantity) FROM Supplier S, SupplyProduct SP WHERE S.sid = SP.sid AND S.sid = ‘S1’ GROUP BY sname; • Đưa ra mã số các hãng cung ứng và số lượng trung bình các mặt hàng được cung ứng bởi từng hãng SELECT sid, AVG(quantity) FROM SupplyProduct GROUP BY sid; • Đưa ra mã số các hãng cung ứng mà số lượng mặt hàng trung bình được cung cấp bởi hãng đó là trong khoảng từ 75 đến 100 SELECT sid, AVG(quantity) FROM SupplyProduct GROUP BY sid HAVING AVG(quantity) BETWEEN 75 AND 100 93 Các câu lệnh cập nhật dữ liệu • Thêm ¾INSERT INTO table[(col1,col2,)] VALUES (exp1,exp2,) ¾INSERT INTO table[(col1,col2,)] SELECT col1,col2, FROM tab1, tab2, WHERE • Ví dụ ¾INSERT INTO Student(Id, Name, Suburb) VALUES (‘‘1179’’,‘‘David’’,‘‘Evr’’) 94 Các câu lệnh cập nhật dữ liệu • Xóa dữ liệu: DELETE FROM WHERE ; • Ví dụ: DELETE FROM SupplyProduct WHERE sid = ‘S4’; DELETE FROM Student WHERE Suburb = ‘‘Bundoora’’; 95 Các câu lệnh cập nhật dữ liệu • Sửa đổi dữ liệu: – UPDATE SET ( = Giá trị mới , ) [WHERE ]; • Ví dụ: – Hãng S1 chuyển tới Milan UPDATE Supplier SET city = ‘Milan’ WHERE sid = ‘S1’; – Tất cả các mặt hàng được cung cấp với số lượng nhỏ hơn 100 đều tăng số lượng lên 1.5 lần UPDATE SupplyProduct SET quantity = quantity * 1.5 WHERE quantity < 100; 96 17 97 Lời hay ý đẹp "Người kém thông minh nhưng say sưa với công việc, tiến mạnh và xa hơn người cực thông minh mà lãnh đạm với công việc". J. Deval 11 Lý thuyết thiết kế cơ sở dữ liệu quan hệ Nguyễn Hồng Phương phuongnh-fit@mail.hut.edu.vn Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 2 Nội dung • Tổng quan về thiết kế CSDLQH • Phụ thuộc hàm • Phép tách các sơ đồ quan hệ (SĐQH) • Các dạng chuẩn đối với các SĐQH 3 Tổng quan về thiết kế CSDLQH • Vấn đề của một sơ đồ quan hệ được thiết kế chưa tốt: Giả sử ta cần một cơ sở dữ liệu lưu trữ thông tin về các hãng cung ứng. Sơ đồ quan hệ được thiết kế trong đó tất cả các thuộc tính cần thiết được lưu trong đúng 1 quan hệ: Suppliers(sid, sname, city, numofemps, product, quantity) 100Bolt75TokyoBlakeS3 78Screw124ParisJ&JS2 100Nut100LondonSmithS1 50Screw100LondonSmithS1 quantityproductNOEcitysnamesid 4 Các vấn đề đối với CSDL VD • Dư thừa dữ liệu: Hãng nào cung ứng nhiều hơn 1 mặt hàng thì thông tin của hãng đó sẽ bị lặp lại trong bảng (VD S1), mặt hàng được cung ứng bởi nhiều hãng cũng bị lặp lại (VD Screw) • Dị thường dữ liệu khi thêm: Nếu có một hãng chưa cung cấp mặt hàng nào, vậy giá trị cho thuộc tính product và quantity trong bộ dữ liệu mới được thêm vào sẽ không được xác định • Dị thường dữ liệu khi xóa: Nếu một hãng chỉ cung cấp 1 mặt hàng, nếu ta muốn xóa thông tin về sự cung cấp này thì ta sẽ mất thông tin về hãng cung cấp • Dị thường dữ liệu khi sửa đổi: Do thông tin bị lặp lại nên việc sửa đổi 1 bộ dữ liệu có thể dẫn đến việc không nhất quán trong dữ liệu về một hãng nếu sơ sót không sửa đổi trên toàn bộ các bộ giá trị liên quan đến hãng đó 5 Đề xuất giải pháp • Nếu sơ đồ trên được thay thế bằng 2 sơ đồ quan hệ –Supp(sid, sname, city, numofemps) –Supply(sid, product,quantity) Thì tất cả các vấn đề nêu ở trên sẽ được loại bỏ. Tuy nhiên khi tìm kiếm dữ liệu thì chúng ta phải thực hiện kết nối 2 bảng chứ không chỉ là chọn và chiếu trên 1 bảng như ở cách thiết kết trước 6 Mục đích của chuẩn hoá • Xác định được 1 tập các lược đồ quan hệ cho phép tìm kiếm thông tin một cách dễ dàng, đồng thời tránh được dư thừa dữ liệu • Hướng tiếp cận: Một trong những kỹ thuật được sử dụng là Tách các lược đồ quan hệ có vấn đề thành những lược đồ quan hệ chuẩn hơn. Phụ thuộc hàm có thể được sử dụng để nhân biết các lược đồ chưa chuẩn và đề xuất hướng cải tiến 27 Phụ thuộc hàm • Định nghĩa: Cho R(U) là một sơ đồ quan hệ với U là tập thuộc tính {A1, A2,,An}. X, Y là tập con của U. Nói rằng X xác định Y hay Y là phụ thuộc hàm vào X ( X Æ Y) nếu với 1 quan hệ r xác định trên R(U) và 2 bộ bất kỳ t1, t2 thuộc r mà t1[X] = t2[X] thì ta có t1[Y] = t2[Y] 8 Ví dụ • Ví dụ 1: • A Æ B, A Æ C, B Æ C • Ví dụ 2: trong cơ sở dữ liệu mẫu dùng trong chương 3, ta có bảng S, với mỗi giá trị của sid đều tồn tại một giá trị tương ứng cho sname, city và status. Do đó ta có sid Æ sname, sid Æ city, sid Æ status c2b3a4 c1b1a3 c2b2a2 c1b1a1 CBA 9 Hệ tiên đề Amstrong đối với phụ thuộc hàm Cho – R(U) là 1 sơ đồ quan hệ, U là tập các thuộc tính. – X,Y,Z,W U (Ký hiệu: XY = X Y) • Phản xạ (reflexivity) Nếu Y X thì X Y • Tăng trưởng (augmentation) Nếu X Y thì XZ YZ • Bắc cầu (transitivity) Nếu X Y, Y Z thì X Z 10 Hệ quả của hệ tiên đề Amstrong • Luật hợp (union) Nếu X Y, X Z thì X YZ. • Luật tựa bắc cầu (pseudotransitivity) Nếu X Y, WY Z thì XW Z. • Luật tách (decomposition) Nếu X Y, Z Y thì X Z 11 Ví dụ • Ví dụ 1: Cho tập phụ thuộc hàm {ABÆC, CÆA} Chứng minh: BC Æ ABC C Æ A BC Æ AB AB Æ C AB Æ ABC BC Æ AB, AB Æ ABC BC Æ ABC • Ví dụ 2: Cho lược đồ quan hệ R(ABEIJGH) và tập phụ thuộc hàm F = {ABÆE, AGÆJ, BEÆI, EÆG, GIÆH} Chứng minh: AB Æ GH 12 Bao đóng của một tập phụ thuộc hàm • Định nghĩa: Cho F là một tập phụ thuộc hàm. Bao đóng của F ký hiệu là F+ là tập lớn nhất chứa các phụ thuộc hàm có thể được suy ra từ các phụ thuộc hàm trong F • Bao đóng của một tập phụ thuộc hàm có thể rất lớn, sẽ chi phí rất tốn kém cho việc tìm kiếm bao đóng của 1 tập phụ thuộc hàm. Do đó để thuận tiện cho việc kiểm tra xem một phụ thuộc hàm có được suy diễn từ một tập phụ thuộc hàm có sẵn không, người ta có thể sử dụng Bao đóng của 1 tập thuộc tính 313 Bao đóng của một tập các thuộc tính đối với tập các phụ thuộc hàm • Định nghĩa: Cho một lược đồ quan hệ R(U), F là một tập phụ thuộc hàm trên U. X là tập con của U. Bao đóng của tập thuộc tính X ký hiệu là X+ là tập tất cả các thuộc tính được xác định hàm bởi X thông qua tập F X+ = {A U| X A F+} • Ta có thể thấy là định nghĩa về bao đóng của một tập thuộc tính dựa trên bao đóng của tập phụ thuộc hàm. Trên thực tế, người ta đưa ra một thuật toán để giúp xác định bao đóng của một tập thuộc tính dễ dàng hơn 14 Thuật toán 1: Tìm bao đóng của một tập thuộc tính đối với tập phụ thuộc hàm • Vào: Tập hữu hạn các thuộc tính U, tập các phụ thuộc hàm F trên U X U • Ra: X+ • Thuật toán B0 X0 = X Bi Tính Xi từ Xi-1 Nếu Y Z F và Y Xi-1 và A Z và A Xi-1 thì Xi = Xi-1 A ngược lại, Xi = Xi-1 Nếu Xi Xi-1 thì lặp Bi ngược lai, chuyển Bn Bn X+ = Xi 15 Ví dụ • Cho R(U) , U = {A, B, C, D, E, F} F = {ABÆC, BCÆAD, DÆE, CFÆB} Tính (AB)+ • Thực hiện: –Bước 0: X0 = AB –Bước 1: X1 = ABC ( do ABÆ C) –Bước 2: X2 = ABCD (do BCÆAD) –Bước 3: X3 = ABCDE (do DÆE) –Bước 4: X4 = ABCDE 16 Bổ đề • X Y được suy diễn từ hệ tiên đề Amstrong khi và chỉ khi Y X+ • Chứng minh: –Giả sử Y=A1...An, với A1,...,An là các thuộc tính và Y X+ –Từ định nghĩa X+ ta có X Ai. Áp dụng tiên đề Amstrong cho mọi i, suy ra X Y nhờ luật hợp. –Ngược lại, giả sử có X Y, áp dụng hệ tiên đề Amstrong cho mỗi i, ta có X Ai, Ai Y nhờ luật tách. Từ đó suy ra Y X+ 17 Khoá • Định nghĩa: Cho lược đồ quan hệ R(U), F là một tập các phụ thuộc hàm xác định trên U. K là một tập con của U, K được gọi là khoá tối thiểu của R nếu như – KÆU là một phụ thuộc hàm trong F+ – Với mọi tập con thực sự K’ của K thì K’ÆU không thuộc F+ • Với những gì ta đã đề cập trong phần bao đóng ở trên, ta có thể nói, để thỏa mãn là một khoá tối thiểu thì K+ = U và K là tập thuộc tính nhỏ nhất có tính chất như vậy 18 Thuật toán 2: Tìm khoá tối thiểu • Vào: U = {A1, A2, , An} , F • Ra: khoá tối thiểu K xác định được trên U và F • Thuật toán B0 K0= U Bi Nếu (Ki-1\{Ai})ÆU thì Ki= Ki-1\ {Ai} ngược lại, Ki= Ki-1 Bn+1 K = Kn 419 Ví dụ • Cho U = {A, B, C, D, E} • F = {ABÆC, ACÆB, BCÆDE}. TÌm một khoá tối thiểu của một quan hệ r xác định trên U và F • Thực hiện • B0: K0= U = ABCDE • B1: Kiểm tra xem có tồn tại phụ thuộc hàm (K0\{A})ÆU (BCDEÆU) hay không. Ta cần phải sử dụng thuật toán 1 để kiểm tra điều kiện tương đương là (BCDE)+ có bằng U không. (BCDE)+= BCDE , khác U. Vậy K1 = K0 = ABCDE • B2: Tương tự, thử loại bỏ B ra khỏi K1 ta có (ACDE)+ = ABCDE = U. Vậy K2 = K1 \ {B} = ACDE • B3: K3 = ACDE • B4: K4 = ACE • B5: K5 = AC • Vậy AC là một khoá tối thiểu mà ta cần tìm 20 Nhận xét về phụ thuộc hàm • Từ một tập các phụ thuộc hàm có thể suy diễn ra các phụ thuộc hàm khác • Trong một tập phụ thuộc hàm cho sẵn có thể có các phụ thuộc hàm bị coi là dư thừa • Æ Làm thế nào để có được một tập phụ thuộc hàm tốt? 21 Tập phụ thuộc hàm tương đương • Định nghĩa: Tập phụ thuộc hàm F là phủ của tập phụ thuộc hàm G hay G là phủ của F hay F và G tương đương nếu F+ = G+. – Ký hiệu là F G • Kiểm tra tính tương đương của 2 tập phụ thuộc hàm B.1. Với mỗi phụ thuộc hàm Y Z F, Z Y+ (trên G) thì Y Z G+ Nếu với phụ thuộc hàm f F, f G+ thì F+ G+ B.2. Tương tự, nếu phụ thuộc hàm g G, g F+ thì G+ F+ B.3. Nếu F+ G+ và G+ F+ thì F G 22 Ví dụ • Cho lược đồ quan hệ R(U) với U = {A, B, C, D, E, F} F = {ABÆC, DÆEF, CÆBD} G = {ACÆB, DÆEF, BÆCD} Hỏi F và G có phải là 2 tập pth tương đương hay không? • Thực hiện: Đối với các phụ thuộc hàm trong F – f1= ABÆC. AB+ (đối với G) = ABCDEF = U. Vậy f1 thuộc G+ – f2= DÆEF thuộc G nên chắc chắn thuộc G+ – f3= CÆBD. C+ (đối với G) = C không chứa BD. Vậy f3 không thuộc G+ – Kết luận F không tương đương với G 23 Tập phụ thuộc hàm không dư thừa • Đ/N: Tập phụ thuộc hàm F là không dư thừa nếu không XÆY F sao cho F \ {XÆY} F. • Thuật toán 3: Tìm phủ không dư thừa của 1 tập phụ thuộc hàm – Vào: Tập thuộc tính U, F = {Li ÆRi: i = 1..n} – Ra : Phủ không dư thừa F’ của F – Thuật toán B0 F0= F Bi Nếu Fi-1\ {LiÆRi} Fi-1 thì Fi = Fi-1 \ {LiÆRi} ngược lại, Fi = Fi-1 Bn+1 F’ = Fn 24 Phủ tối thiểu của 1 tập phụ thuộc hàm • Đ/N: Fc được gọi là phủ tối thiểu của 1 tập phụ thuộc hàm F nếu thỏa mãn 3 điều kiện sau: Đk1: Với f Fc, f có dạng X Æ A, trong đó A là 1 thuộc tính Đk2: Với f = XÆY Fc, ! A X (A là 1 thuộc tính): (Fc \ f) U {(X \ A)ÆY} Fc Đk3: ! XÆA Fc : Fc \ {XÆA} Fc 525 Thuật toán 4: Tìm phủ tối thiểu của một tập phụ thuộc hàm • Vào: Tập thuộc tính U, F = {LiÆRi: i = 1..n} • Ra: phủ tối thiểu Fc của tập phụ thuộc hàm F • Thuật toán B.1. Biến đổi F về dạng F1={Li Æ Aj} trong đó Aj là 1 thuộc tính bất kỳ thuộc U (thoả mãn đk1) B.2. Loại bỏ thuộc tính thừa trong vế trái của các phụ thuộc hàm Lần lượt giản ước từng thuộc tính trong vế trái của từng phụ thuộc hàm trong F1 thu được F1’. Nếu F1’ F1 thì loại bỏ thuộc tính đang xét Khi không có sự giản ước nào xảy ra nữa ta thu được F2 thỏa mãn đk2 B.3. Loại bỏ phụ thuộc hàm dư thừa Lần lượt kiểm tra từng phụ thuộc hàm f. Nếu F2 \ f F2 thì loại bỏ f Khi không cò phụ thuộc hàm nào có thể loại bỏ thi thu đươc F3 thoả mãn đk3 B.4. Fc = F3 26 Ví dụ 1 • U = {A,B,C} F = {AÆBC, BÆC, AÆB, ABÆC}. Tìm phủ tối thiểu của F? – F1 = {AÆB, AÆC, BÆC, ABÆC} – Xét các pth trong F1 mà vế trái có nhiều hơn 1 thuộc tính ABÆC. Giản ước A thì ta còn BÆC có trong F1, vậy A là thuộc tính thừa. Tương tự ta cũng tìm được B là thừa, vậy loại bỏ luôn ABÆC khỏi F1.F2 = {AÆB, AÆC, BÆC} – Bỏ pth thừa: AÆC là thừa. Vậy Fc = {AÆB, BÆC} 27 Ví dụ 2 • Tìm phủ tối thiểu của tập phụ thuộc hàm F = {AÆB, ABCDÆE, EFÆG, ACDFÆEG} – F1 = {AÆB, ABCDÆE, EFÆG, ACDFÆE, ACDFÆG} – Loại bỏ thuộc tính thừa trong 3 phụ thuộc hàm ABCDÆE, ACDFÆE và ACDFÆG Xét ABCDÆE: Giả sử giản ước A , ta còn BCDÆE, kiểm tra BCDÆE có được suy ra từ F1 không, ta tính (BCD)+ (đối với F1). (BCD)+ = BCD, không chứa E, vậy thì BCDÆE không được suy diễn ra từ F, vậy A không phải là thuộc tính thừa trong pth đang xét. B là thừa vì từ F1 ta có AÆB dẫn đến (ACD)+ = ABCDE có chứa E Làm tương tự ta thấy không có thuộc tính nào là thừa nữa. F2 = {AÆB, ACDÆE, EFÆG, ACDFÆE, ACDFÆG} 28 Ví dụ 2 (tiếp) – Loại bỏ pth thừa trong F2: Lần lượt thử loại bỏ 1 pth ra khỏi F2, nếu tập pth thu đựoc sau khi loại bỏ vẫn tương đương với F2 thì pth vừa loại là thừa AÆ B không thừa vì nếu loại pth này khỏi F2 thì từ tập phụ thuộc hàm còn lại A+ không chứa B Tương tự , ACDÆE, EFÆ G không thừa ACDFÆ E là phụ thuộc hàm thừa vì nếu loại bỏ pth này, trong tập pth vẫn còn lại ACDÆE, theo tiên đề tăng trưởng ta sẽ suy ra được ACDFÆE ACDFÆG là thừa vì nếu loại bỏ pth này, trong tập pth còn lại vẫn có ACDÆE và EFÆG, do đó ta vẫn có (ACDF)+ = ACDEFG có chứa G – Vậy Fc = { AÆB, ACDÆE, EFÆG} 29 Phép tách các Sơ đồ quan hệ • Mục đích –Thay thế một sơ đồ quan hệ R(A1, A2, , An) bằng một tập các sơ đồ con {R1, R2, , Rk} trong đó Ri R và R = R1 U R2 U U Rk • Yêu cầu của phép tách –Bảo toàn thuộc tính, ràng buộc –Bảo toàn dữ liệu 30 Phép tách không mất mát thông tin • Đ/N: Cho lược đồ quan hệ R(U) phép tách R thành các sơ đồ con {R1, R2, , Rk} được gọi là phép tách không mất mát thông tin đ/v một tập phụ thuộc hàm F nếu với mọi quan hệ r xác định trên R thỏa mãn F thì: r = R1(r) R2(r) Rk (r) • Ví dụ: Phép tách mất mát thông tin Supplier(sid, sname,city,NOE, pid, pname,colour,quantity) ÆS1(sid,sname,city,NOE) và SP1(pid,pname,colour,quantity) • Ví dụ: Phép tách không mất mát thông tin ÆS1(sid,sname,city,NOE) và SP2(sid,pid,pname,colour,quantity) >< 631 Định lý tách đôi • Cho lược đồ quan hệ R(U), tập pth F , phép tách R thành R1(U1), R2(U2) là một phép tách không mất mát thông tin nếu 1 trong 2 phụ thuộc hàm sau là thỏa mãn trên F+: U1 ∩ U2Æ U1 - U2 U1 ∩ U2Æ U2 - U1 • Hệ quả: Cho lược đồ quan hệ R(U) và phụ thuộc hàm XÆY thỏa mãn trên R(U). Phép tách R thành 2 lược đồ con R1(U1), R2(U2) là một phép tách không mất mát thông tin với: U1 = XY U2 = XZ Z = U \ XY 32 Thuật toán 5: Kiểm tra tính không mất mát thông tin của 1 phép tách • Vào: R(A1, A2, , An), F, phép tách {R1, R2, , Rk} • Ra: phép tách là mất mát thông tin hay không • Thuật toán B.1. Thiết lập một bảng k hàng, n cột Nếu Aj là thuộc tính của Ri thì điền aj vào ô (i,j). Nếu không thì điền bij. B.i. Xét f = XÆY F Nếu 2 hàng t1, t2 thuộc bảng : t1[X] = t2[X] thì đồng nhất t1[Y] = t2[Y], ưu tiên về giá trị a Lặp cho tới khi không thể thay đổi được giá trị nào trong bảng B.n. Nếu bảng có 1 hàng gồm các kí hiệu a1, a2, , an thì phép tách là không mất mát thông tin ngược lại, phép tách không bảo toàn thông tin 33 Ví dụ • R = ABCD được tách thành R1=AB, R2 =BD, R3=ABC, R4=BCD. F = {AÆC, BÆC, CDÆB, CÆD} • B.1: Tạo bảng gồm 4 hàng, 4 cột a4a3a2b14R4 b43a3a2a1R3 a4b32a2b12R2 b41b31a2a1R1 DCBA 34 Ví dụ (tiếp) • B.2 & 3: • Từ A Æ C, ta có • Từ B Æ C, ta có a4a3a2b14R4 b43a3a2a1R3 a4b32a2b12R2 b41a3a2a1R1 DCBA a4a3a2b14R4 b43a3a2a1R3 a4a3a2b12R2 b41a3a2a1R1 DCBA 35 Ví dụ (tiếp) • Từ C Æ D, ta có • Vậy ta có 2 hàng có toàn các giá trị a. Chứng tỏ phép tách đã cho là không mất mát thông tin a4a3a2b14R4 a4a3a2a1R3 a4a3a2b12R2 a4a3a2a1R1 DCBA 36 Phép tách bảo toàn tập phụ thuộc hàm • Hình chiếu của tập phụ thuộc hàm Cho sơ đồ quan hệ R, tập phụ thuộc hàm F, phép tách {R1, R2, , Rk} của R trên F. Hình chiếu Fi của F trên Ri là tập tất cả XÆY F+: XY Ri • Phép tách sơ đồ quan hệ R thành {R1, R2, , Rk} là một phép tách bảo toàn tập phụ thuộc hàm F nếu (F1 F2 Fk)+ = F+ hay hợp của tất cả các phụ thuộc hàm trong các hình chiếu của F lên các sơ đồ con sẽ suy diễn ra các phụ thuộc hàm trong F. 737 Ví dụ • Ví dụ 1: R = {A, B, C} F = { AÆB, BÆC, CÆA} được tách thành R1 = AB, R2 = BC. Phép tách này có phải là bảo toàn tập phụ thuộc hàm không? • Ví dụ 2: R = {A, B, C} , F = {ABÆC, CÆB} được tách thành R1 = AB, R2 = BC. Phép tách này có bảo toàn tập pth không, có mất mát thông tin không? • Ví dụ 3: R = { A, B, C, D} , F = {AÆB, CÆD} được tách thành R1 = AB, R2 = CD. Phép tách này có bảo toàn tập pth không, có mất mát thông tin không? • Vậy một phép tách có bảo toàn tập phụ thuộc hàm thì không đảm bảo là nó sẽ không mất mát thông tin và ngược lại 38 Các dạng chuẩn đối với SĐQH • Quay lại vấn đề thiết kế cơ sở dữ liệu quan hệ, câu hỏi mà chúng ta đặt ra trong quá trình này là Có cần thiết phải tinh chỉnh thiết kế nữa hay không, thực sự thiết kế mà chúng ta có được đã là tốt hay chưa. Để giúp trả lời câu hỏi này, người ta đưa ra các định nghĩa về các dạng chuẩn. Có một vài dạng chuẩn đã được xem xét, khi một quan hệ thuộc vào một dạng chuẩn nào đó thì ta có thể coi như là một số các vấn đề về dư thừa dữ liệu hay dị thường dữ liệu đã được ngăn ngừa hay tối thiểu hóa • Các dạng chuẩn mà chúng ta quan tâm – Dạng chuẩn 1 (1NF) – Dạng chuẩn 2 (2NF) – Dạng chuẩn 3 (3NF) – Dạng chuẩn Boye-Code (BCNF) 39 Dạng chuẩn 1 (1NF) • Định nghĩa: Một sơ đồ quan hệ R được gọi là ở dạng chuẩn 1 nếu tất cả các miền giá trị của các thuộc tính trong R đều chỉ chứa giá trị nguyên tố – Giá trị nguyên tố là giá trị mà không thể chia nhỏ ra được nữa • Một quan hệ r xác định trên sơ đồ quan hệ ở dạng chuẩn 1 thì quan hệ đấy là ở dạng chuẩn 1 • Ví dụ: Quan hệ không ở dạng chuẩn 1 và quan hệ sau khi chuẩn hóa về dạng chuẩn 1 75ScrewParisSmith 120Bolt 100NutLondonBlake pricename productcitysname priceitemcitysname 75ScrewParisSmith 120BoltLondonBlake 100NutLondonBlake 40 Dạng chuẩn 2 (2NF) • Định nghĩa: Một sơ đồ quan hệ R được coi là ở dạng chuẩn 2 nếu –Sơ đồ quan hệ này ở 1NF –Tất cả các thuộc tính không khoá đều phụ thuộc hàm đầy đủ vào khoá chính (Lưu ý, A là một thuộc tính khoá nếu A thuộc một khoá tối thiểu nào đó của R. Ngược lại A là thuộc tính không khoá) 41 Phụ thuộc hàm đầy đủ • Định nghĩa: Cho lược đồ quan hệ R(U), F là tập phụ thuộc hàm trên R. X, Y U. Y được gọi là phụ thuộc đầy đủ vào X nếu: - XÆY thuộc F+ - ! X’ X : X’ÆY F+ • Các phụ thuộc hàm không đầy đủ còn gọi là phụ thuộc bộ phận 42 Ví dụ • Sales(sid, sname, city, item, price) • F = {sidÆ(sname,city), (sid,item)Æprice} • Khoá chính (sid,item), ta có sname, city không phụ thuộc hàm đầy đủ vào khoá chính => Quan hệ Sales không thuộc 2NF • S(sid, sname, city) và Sales (sid, item, price) là quan hệ thuộc 2NF 843 Dạng chuẩn 3 (tiếp) • Định nghĩa: Một sơ đồ quan hệ R được coi là ở dạng chuẩn 3 nếu –Sơ đồ quan hệ này ở 2NF –Mọi thuộc tính không khoá đều không phụ thuộc bắc cầu vào khoá chính 44 Phụ thuộc bắc cầu • Định nghĩa: Cho lược đồ quan hệ R(U). F là tập phụ thuộc hàm trên R(U). X,Y,Z U. Ta nói Z là phụ thuộc bắc cầu vào X nếu ta có XÆY , YÆ Z thuộc F+. Ngược lại, ta nói Z không phụ thuộc bắc cầu vào X 45 Ví dụ • Ví dụ 1: Trong ví dụ tách về dạng chuẩn 2 ta có: S (sid, sname, city) và Sales(sid, item, price). Xét quan hệ S, pth sid Æ sname, city tồn tại trên S, sid là khoá chính, các thuộc tính không khoá sname, city đều phụ thuộc trực tiếp vào sid. S thuộc 3NF. Tương tự ta có Sales cũng thuộc 3NF • Ví dụ 2: – ItemInfo(item, price, discount). F = {itemÆprice, priceÆdiscount}. Khoá chính là item, thuộc tính không khoá discount phụ thuộc bắc cầu vào khoá chính item. Vậy quan hệ này không ở 3NF. – ItemInfo(item, price) và Discount(price, discount) thuộc 3NF. 46 Dạng chuẩn Boye-Codd • Định nghĩa: Một sơ đồ quan hệ R(U) với một tập phụ thuộc hàm F được gọi là ở dạng chuẩn Boye-Codd (BCNF) nếu với XÆA F+ thì – A là thuộc tính xuất hiện trong X hoặc – X chứa một khoá của quan hệ R. • Ví dụ – R = {A,B,C} ; F = {ABÆC , CÆB}. – R không phải ở BCNF vì CÆB, C không phải là khoá • Chú ý: – Một quan hệ thuộc 3NF thì chưa chắc đã thuộc BCNF. Nhưng một quan hệ thuộc BCNF thì thuộc 3NF 47 Tách bảo toàn tập phụ thuộc hàm về 3NF • Vào: R(U), F (giả thiết F là phủ tối thiểu) • Ra: Phép tách bảo toàn tập phụ thuộc hàm về 3NF • Thuật toán B1. Với các Ai U, Ai F thì loại Ai khỏi R và lập 1 quan hệ mới cho các Ai B2. Nếu f F, f chứa tất cả các thuộc tính của R (đã bỏ các Ai ở bước trên) thì kết quả là R B3. Ngược lại, với mỗi XÆ A F, xác định một quan hệ Ri(XA). Nếu XÆAi, XÆAj thì tạo một quan hệ chung R’(XAiAj) 48 Ví dụ Cho R = {A,B,C,D,E,F,G} F = {AÆB, ACDÆE, EFÆG} (đã tối thiểu) • Xác định phép tách bảo toàn tập phụ thuộc hàm về 3NF B1. Không lập được quan hệ nào mới. B2. ! f F: f chứa tất cả các thuộc tính của R B3. AÆB Ö R1(AB) ACDÆE Ö R2(ACDE) EFÆG Ö R3(EFG) 949 Tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm về 3NF • Yêu cầu: – Bảo toàn tập phụ thuộc hàm (như thuật toán trên) – Đảm bảo là có một lược đồ con chứa khoá của lược đồ được tách • Các bước tiến hành B1. Tìm một khoá tối thiểu của lược đồ quan hệ R đã cho B2. Tách lược đồ quan hệ R theo phép tách bảo toàn tập phụ thuộc hàm. B3. Nếu 1 trong các sơ đồ con có chứa khoá tối thiểu thì kết quả của B2 là kết quả cuối cùng Ngược lại, thêm vào kết quả đó một sơ đồ quan hệ được tạo bởi khoá tối thiểu tìm được ở 1 50 Ví dụ • Cho R(U) trong đó U = {A,B,C,D,E,F,G}. F = {AÆB, ACDÆE, EFÆG} • Tìm một khoá tối thiểu của R: K0 = ABCDEFG K1 = K0 do nếu loại A thì BCDEFG Æ U không thuộc F+ K2 = K1 \{B} = ACDEFG do ACDEFG Æ U thuộc F+ K3 = K2 do nếu loại C thì ADEFG Æ U không thuộc F+ K4 = K3 do nếu loại D thì ACEFG Æ U không thuộc F+ K5 = K4 \{E} = ACDFG do ACDFG Æ U thuộc F+ K6 = K5 do nếu loại F thì ACDG Æ U không thuộc F+ K7 = K6 \{G} = ACDF do ACDF Æ U thuộc F+ • Vậy khoá tối thiểu cần tìm là ACDF 51 Ví dụ (tiếp) • Dùng kết quả của ví dụ ở phần tách bảo toàn tập phụ thuộc hàm ta có một phép tách R thành 3 sơ đồ con R1 = AB, R2= ACDE, R3 = EFG • Do khoá ACDF không nằm trong bất kỳ một sơ đồ con nào trong 3 sơ đồ con trên, ta lập một sơ đồ con mới R4 = ACDF • Kết quả cuối cùng ta có phép tách R thành 4 sơ đồ con {R1, R2, R3, R4} là một phép tách không mất mát thông tin và bảo toàn tập phụ thuộc hàm 52 Tách không mất mát thông tin về BCNF • Vào: Sơ đồ quan hệ R, tập phụ thuộc hàm F. • Ra: phép tách không mất mát thông tin bao gồm một tập các sơ đồ con ở BCNF với các phụ thuộc hàm là hình chiếu của F lên sơ đồ đó. • Cách tiến hành B1. KQ = {R}, B2.Với mỗi S KQ, S không ở BCNF, xét X A S, với điều kiện X không chứa khoá của S và A X. Thay thế S bởi S1, S2 với S1=A X , S2 = S \ A. B3. Lặp (B2) cho đến khi S KQ đều ở BCNF KQ gồm các sơ đồ con của phép tách yêu cầu 53 Kết luận • Tầm quan trọng của thiết kế CSDL – ảnh hưởng đến chất lượng dữ liệu lưu trữ – Hiệu quả của việc khai thác dữ liệu • Mục đích của thiết kế CSDL: – Tránh dư thừa dữ liệu – Tránh dị thường dữ liệu khi thêm/xoá/sửa đổi – Hiệu quả trong tìm kiếm ¾Đưa về các dạng chuẩn – 2NF: giản ước sự dư thừa để tránh các dị thuờng khi cập nhật – 3NF: tránh các dị thường khi thêm/xoá 54 10 55 Lời hay ý đẹp "Nếu anh thấy một gia đình hạnh phúc, anh nên tin rằng ở trong gia đình có một người đàn bà biết quên mình." (René Bazin) 11 Tối ưu hóa câu truy vấn Nguyễn Hồng Phương phuongnh-fit@mail.hut.edu.vn Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 2 NHP Nội dung • Tổng quan về xử lý truy vấn • Tối ưu hóa các biểu thức đại số quan hệ 3 NHP Tổng quan về xử lý truy vấn • Xử lý một truy vấn bao gồm 3 bước chính: –Phân tích và Biên dịch câu truy vấn: Trong bước này, hệ thống phải dịch câu truy vấn từ dạng ngôn ngữ bậc cao thành một ngôn ngữ biểu diễn dữ llệu bên trong để máy tính có thể thao tác trên đó. Một biểu diễn bên trong thích hợp và hỗ trợ cho bước tối ưu hóa tiếp theo là biểu diễn bằng ngôn ngữ đại số quan hệ 4 NHP Tổng quan về xử lý truy vấn (tiếp) –Tối ưu hóa câu truy vấn: Mục tiêu của bước tối ưu hóa là chọn ra một kế hoạch thực hiện câu truy vấn có chi phí thấp nhất. • Để thực hiện được điều này, trước tiên ta cần biến đổi 1 biểu thức ĐSQH đầu vào thành một biểu thức ĐSQH tương đương nhưng có thể xử lý được 1 cách hiệu quả và ít tốn kém hơn. Bước con đầu tiên này được gọi là tối ưu hóa đại số. • Tiếp theo đó, ta cần phải đặc tả các thuật toán đặc biệt tiến hành thực thi các phép toán , chọn 1 chỉ dẫn cụ thể nào đó để sử dụng. • Các dữ liệu thống kê về CSDL sẽ giúp ta trong quá trình xem xét và lựa chọn. Ví dụ như: 5 NHP Tổng quan về xử lý truy vấn (tiếp) – Số bộ trong quan hệ – Kích thước của một bộ – Số khối (block) chứa các bộ của quan hệ – Số bộ của quan hệ mà một khối có thể chứa – Các thông tin về cơ chế truy nhập, chỉ dẫn trên quan hệ • Chi phí cho việc thực hiện một truy vấn được đo bởi chi phí sử dụng tài nguyên như việc truy cập đĩa, thời gian CPU dùng để thực hiện một truy vấn. • Trong chương này, chúng ta sẽ tập trung vào việc đánh giá các biểu thức đại số quan hệ chứ không đi vào chi tiết việc tính toán chi phí cho việc thực hiện đánh giá một truy vấn. 6 NHP Tổng quan về xử lý truy vấn (tiếp) –Thực hiện đánh giá truy vấn: Từ một kế hoạch thực hiện có được do Trình tối ưu hóa cung cấp, hệ thống sẽ tiến hành thực hiện các thao tác trên dữ liệu trong CSDL và đưa ra câu trả lời cho truy vấn đó. Truy vaán ñaàu vaøo Bieåu thöùc ÑSQH Keá hoaïch thöïc hieänCaâu tra û lô øi truy vaán Bieân dòch truy vaán Toái öu hoùa truy vaán Thöïc hieän tìm kieám dl CSDL Thoáng keâ veà dl 27 NHP Đánh giá biểu thức ĐSQH • Sau bước phân tích và biên dịch, ta có một truy vấn được biểu diễn bằng một biểu thức đại số quan hệ bao gồm nhiều phép toán và tác động lên nhiều quan hệ khác nhau. Ta sẽ phải tiến hành đánh giá biểu thức này. Có 2 hướng tiếp cận để thực thi quá trình đánh giá biểu thức ĐSQH: –Vật chất hóa (Materialize) –Đường ống (Pipeline) 8 NHP Đánh giá biểu thức ĐSQH (tiếp) • Vật chất hóa: Trong cách tiếp cận này thì ta lần lượt đánh giá các phép toán theo một thứ tự thích hợp. Kết quả của việc đánh giá mỗi phép toán sẽ được lưu trong một quan hệ trung gian tạm thời để sử dụng làm đầu vào cho các phép toán tiếp theo. • Điểm bất lợi của cách tiếp cận này là việc cần thiết phải xây dựng các quan hệ trung gian tạm thời nhất là khi các quan hệ này thường phải được ghi ra đĩa (trừ khi chúng có kích thước rất nhỏ). Mà việc đọc và ghi ra đĩa có chi phí khá lớn. 9 NHP Đánh giá biểu thức ĐSQH (tiếp) • Đường ống: Chúng ta có thể cải thiện hiệu quả đánh giá truy vấn bằng cách làm giảm bớt số lượng các quan hệ trung gian tạm thời được tạo ra. Điều này có thể đạt được nhờ việc kết hợp một vài phép toán quan hệ vào một đường ống của các phép toán. Trong đường ống thì kết quả của một phép toán được chuyển trực tiếp cho phép toán tiếp theo mà không cần phải lưu lại trong quan hệ trung gian. • Rõ ràng, cách tiếp cận thứ hai sẽ hạn chế được nhược điểm của cách tiếp cận đầu tiên, nhưng có những trường hợp, ta bắt buộc phải vật chất hóa chứ không dùng đường ống được. 10 NHP Đánh giá biểu thức ĐSQH (tiếp) • Ví dụ: Chúng ta có một biểu thức đại số quan hệ gồm 2 phép toán: kết nối và chiếu. • Trong cách tiếp cận vật chất hóa, xuất phát từ phép toán ở mức thấp nhất là phép kết nối tự nhiên, kết quả của phép kết nối này sẽ được lưu trong một quan hệ trung gian. Sau đó , đọc từ quan hệ trung gian này để tiến hành chiếu lấy kết quả mong muốn. • Trong cách tiếp cận đường ống, khi một bộ được sinh ra trong phép kết nối 2 quan hệ, bộ này sẽ được chuyển trực tiếp đến phép chiếu để xử lý và kết quả được ghi vào quan hệ đầu ra. Quan hệ kết quả sẽ được tạo lập một cách trực tiếp. 11 NHP Tối ưu hóa các biểu thức ĐSQH • Mục tiêu là tổ chức lại trình tự thực hiện các phép toán trong biểu thức để giảm chi phí thực hiện đánh giá biểu thức đó. • Trong quá trình tối ưu hóa, ta biểu diễn một biểu thức ĐSQH dưới dạng một cây toán tử. Trong cây thì các nút lá là các quan hệ có mặt trong biểu thức, các nút trong là các phép toán trong biểu thức • Ví dụ : Đưa ra tên hãng cung ứng mặt hàng có mã là 'P1': Select sname From S, SP Where S.sid = SP.sid And pid = 'P1' • Biểu thức ĐSQH tương ứng là? • Cây toán tử tương ứng là? 12 NHP Các chiến lược tối ưu tổng quát 1. Đẩy phép chọn và phép chiếu xuống thực hiện sớm nhất có thể: vì hai phép toán này giúp làm giảm kích thước của quan hệ trước khi thực hiện các phép toán 2 ngôi 2. Nhóm dãy các phép chọn và chiếu: Sử dụng chiến lược này nếu như có một dãy các phép chọn hoặc dãy các phép chiến trên cùng một quan hệ 3. Kết hợp phép chọn và tích Đề các thành phép kết nối: Nếu kết quả của một phép tích Đề các là đối số của 1 phép chọn có điều kiện chọn là phép so sánh giữa các thuộc tính trên 2 quan hệ tham gia tích Đề các thì ta nên kết hợp 2 phép toán thành phép kết nối. 4. Tìm các biểu thức con chung trong biểu thức đại số quan hệ để đánh giá chỉ một lần 313 NHP Các chiến lược tối ưu tổng quát (tiếp) 5. Xác định các phép toán có thể được đưa vào đường ống và thực hiện đánh giá chúng theo đường ống 6. Xử lý các tệp dữ liệu trước khi tiến hành tính toán: Tạo lập chỉ dẫn hay sắp xếp tệp dữ liệu có thể góp phần làm giảm chi phí của các phép tính trung gian 7. Ước lượng chi phí và lựa chọn thứ tự thực hiện: Do với mỗi câu truy vấn có thể có nhiều cách khác nhau để thực hiện, với việc ướng lượng chi phí (số phép tính, tài nguyên sử dụng, dung tích bộ nhớ, thời gian thực hiện ..) ta có thể chọn cách đánh giá biểu thức ĐSQH có chi phí nhỏ nhất. 14 NHP Các phép biến đổi tương đương biểu thức ĐSQH • Hai biểu thức ĐSQH E1 và E2 là tương đương nếu chúng cho cùng một kết quả khi áp dụng trên cùng một tập các quan hệ • Trong phần này, ta có các ký hiệu dạng sau: – E1, E2, E3, là các biểu thức đại số quan hệ – F1, F2, F3, là các điều kiện chọn hoặc là các điều kiện kết nối – X1, X2, Y, Z, U1, U2, là các tập thuộc tính 15 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 1. Quy tắc kết hợp của phép tích Đề các và kết nối • Qui tắc này sử dụng cho chiến lược số 7. Thứ tự thực hiện các phép kết nối hay tích Đề các là rất quan trọng vì kích thước của quan hệ trung gian có thể rất lớn nếu không cân nhắc kỹ. Lựa chọn thứ tự thực hiện các phép toán này thì tùy thuộc vào kích thước của các quan hệ tham gia phép toán và cả ngữ nghĩa của quan hệ (mối liên hệ) )()( )*(**)*( )()( 3221132211 321321 321321 EEEEEE EEEEEE EEEEEE FFFF >< ≡ ≡ ××≡×× 16 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) • VD: S* SP * P có thể được thực hiện theo 3 thứ tự như sau 1)(S*SP)*P 2)(S*P)*SP 3)S*(SP*P) Xét theo ngữ nghĩa S, P không kết nối được nên (1) và (3) là tốt hơn (2). Xét về kích thước thì (3) tốt hơn (1) vì S có 4 thuộc tính còn P có 3 thuộc tính, tuy nhiên, cũng còn tùy thuộc vào lực lượng của 2 quan hệ S và P nữa 17 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 2. Quy tắc giao hoán trong phép tích Đề các và kết nối 3. Quy tắc đối với dãy các phép chiếu 4. Quy tắc đối với dãy các phép chọn 1221 1221 1221 ** EEEE EEEE EEEE FF >< ≡ ≡ ×≡× n XXXX XXX EE n ⊆⊆⊆ ∏≡∏∏∏ ... )()...)(...( 21 121 )()...)(....( ...2121 EE FnFFFnFF ∧∧∧≡ σσσσ 18 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 5. Quy tắc giao hoán phép chọn và phép chiếu Quy tắc này áp dụng khi F là điều kiện xác định được trên tập thuộc tính X. Tổng quát hơn ta có: ))(())(( EE XFFX ∏≡∏ σσ )))((())(( EE XYFXFX ∏∏≡∏ σσ 419 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 6. Quy tắc đối với phép chọn và phép tích Đề các • Ta ký hiệu: – E1(U1) có nghĩa là biểu thức E1 xác định trên tập thuộc tính U1 – F1(U1) có nghĩa là điều kiện chọn F1 xác định trên tập thuộc tính U1 – Quy tắc biến đổi liên quan đến phép chọn và tích Đề các được phát biểu như sau: • tương đương với: – trong trường hợp F = F1(U1) – trong trường hợp F = F1(U1) F2(U2) – trong trường hợp F = F1(U1) F2(U1U2) ))()(( 2211 UEUEF ×σ 211 )( EEF ×σ )()( 2211 EE FF σσ × ))(( 2112 EEFF ×σσ 20 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 7. Quy tắc đối với phép chọn và phép hợp: 8. Quy tắc đối với phép chọn và phép trừ: )()()( 2121 EEEE FFF σσσ ∪≡∪ )()()( 2121 EEEE FFF σσσ −≡− 21 NHP Các phép biến đổi tương đương biểu thức ĐSQH (tiếp) 9. Quy tắc đối với phép chiếu và tích Đề các: 10.Quy tắc đối với phép chiếu và phép hợp: 21 212211 ,, )()())()(( UZUYYZX EEUEUE ZYX ⊂⊂= ∏×∏≡×∏ )()()( 2121 EEEE XXX ∏∏≡∏ UU 22 NHP Ví dụ • Tìm tên hãng cung ứng ít nhất 1 mặt hàng màu đỏ hoặc màu xanh SELECT sname FROM S, P, SP WHERE S.sid = SP.sid AND P.pid = SP.pid AND (colour = ‘Red’ OR colour = ‘Green’); • Biểu thức đại số quan hệ tương đương với câu truy vấn trên là: ))(( )'''Re'(.... PSPSGreencolourdcolourpidSPpidPsidSPsidSsname ××∏ =∨=∧=∧=σ 23 NHP 24 NHP Lời hay ý đẹp "Phẩm cách chân chính của con người là ở trong cách họ sống chứ không phải ở cái họ có" Blackie 11 An toàn và toàn vẹn dữ liệu Nguyễn Hồng Phương phuongnh-fit@mail.hut.edu.vn Bộ môn Hệ thống thông tin Viện Công nghệ thông tin và Truyền thông Đại học Bách Khoa Hà Nội 2 Nội dung • An toàn dữ liệu –Xác minh người sử dụng –Kiểm tra quyền truy nhập của người sử dụng –Các câu lệnh an toàn dữ liệu trong SQL • Toàn vẹn dữ liệu –Các ràng buộc toàn vẹn trong SQL –Điều khiển tương tranh 3 An toàn dữ liệu • Định nghĩa: Tính an toàn dữ liệu là sự bảo vệ dữ liệu trong cơ sở dữ liệu chống lại những truy nhập, sửa đổi hay phá hủy bất hợp pháp. • Người sử dụng hợp pháp là những người sử dụng được cấp phép, được ủy quyền. Ngược lại là những người sử dụng bất hợp pháp. • Để đảm bảo tính an toàn cho cơ sở dữ liệu, chúng ta cần có một cơ chế để quản lý người dùng cho hợp lý. • Những nhóm người dùng khác nhau trong hệ CSDL có quyền sử dụng khác nhau đối với các dữ liệu trong CSDL. 4 Các quyền truy nhập của người sử dụng • Quyền đọc dữ liệu: được phép đọc một phần hay toàn bộ dữ liệu trong CSDL • Quyền cập nhật dữ liệu: được phép sửa đổi một số giá trị nhưng không được xóa dữ liệu trong CSDL • Quyền xóa dữ liệu: được phép xóa dữ liệu trong CSDL • Quyền bổ sung dữ liệu: được phép thêm dữ liệu mới vào trong CSDL nhưng không được phép thay đổi dữ liệu • Quyền tạo chỉ dẫn trên các quan hệ trong CSDL • Quyền thay đổi sơ đồ cơ sở dữ liệu: thêm hay xóa các thuộc tính của các quan hệ trong CSDL • Quyền loại bỏ quan hệ trong CSDL • Quyền quản lý tài nguyên: được phép thêm các quan hệ mới vào CSDL 5 Trách nhiệm của người quản trị hệ thống • Để có thể phân biệt được người sử dụng trong hệ CSDL, người quản trị hệ thống phải có trách nhiệm: – Xác định các quyền cụ thể mà mỗi người sử dụng hay một nhóm người sử dụng được phép thực hiện, xác định vai trò và trách nhiệm của mỗi người sử dụng. Điều này được gọi chung là Phân quyền người sử dụng – Cung cấp một phương tiện cho người sử dụng để hệ thống có thể nhận biết được người sử dụng đó hay còn gọi là Xác minh người sử dụng 6 Xác minh người sử dụng • Để xác minh được người sử dụng, người ta có thể dùng các kỹ thuật sau: – Kỹ thuật dùng tài khoản và mật khẩu, mật khẩu cũng được bảo vệ bởi hệ thống một cách kỹ càng. – Kỹ thuật sử dụng các hàm kiểm tra cho người sử dụng: Hệ thống đưa cho người sử dụng một số ngẫu nhiên x, người sử dụng dùng một hàm F tính nhẩm kết quả và đưa kết quả y = F(x) vào hệ thống. Trong lúc đó, hệ thống cũng tính toán và so sánh kết quả với y. Người sử dụng hợp pháp là người biết hàm biến đổi F và đưa vào giá trị y đúng. – Kỹ thuật dùng thẻ điện tử, thẻ thông minh. – Kỹ thuật sử dụng nhận dạng tiếng nói, vân tay v..v. 27 Kiểm tra quyền truy nhập của người sử dụng • Mỗi người sử dụng sẽ có một bộ hồ sơ do người quản trị thiết lập và được hệ thống quản lý, trong hồ sơ đó sẽ có chi tiết về các thao tác người sử dụng được phép thực hiện: – Phân quyền người sử dụng: Người quản trị hệ thống phải có trách nhiệm xác định khung nhìn để kiểm soát xem mỗi người sử dụng chỉ được truy nhập phần dữ liệu nào trong CSDL và có được các quyền nào trong số các quyền đọc, thêm, xóa , sửa đổi. – Xác định và kiểm soát sự lưu chuyển dữ liệu: Hệ thống phải bảo trì danh sách các quyền một cách chặt chẽ vì người sử dụng có thể được quyền lan truyền các quyền cho người sử dụng khác. 8 Các câu lệnh an toàn dữ liệu trong SQL • Câu lệnh tạo khung nhìn • Câu lệnh phân quyền cho người sử dụng • Câu lệnh thu hồi quyền của người sử dụng 9 Câu lệnh tạo khung nhìn • CREATE VIEW [(d/s cột)] AS • Danh sách các cột trong khung nhìn là phần không bắt buộc. Trong trường hợp người sử dụng muốn đặt tên khác cho các cột xuất hiện trong khung nhìn thì người sử dụng có thể chỉ ra tên các cột, dữ liệu trên cột thì tương ứng với các cột trong mệnh đề Select của câu truy vấn. 10 Ví dụ câu lệnh tạo khung nhìn • Cho cơ sở dữ liệu gồm 2 quan hệ: Nhânviên(Id,Họtên,ĐC,Lương,NămBD,Đánhgiá,PhòngCT) Phòng(PId, Tên, ĐC, Điệnthoại, Trưởngphòng) • Câu lệnh tạo khung nhìn cho một nhân viên của phòng Khoa Học có thể được định nghĩa như sau: CREATE VIEW NVKH(HọtênNhânviên, Địachỉliênlạc) AS SELECT Họtên,Địachỉ FROM Nhânviên WHERE PhòngCT IN (SELECT PId FROM Phòng WHERE Tên =‘Khoa Học’) 11 Câu lệnh phân quyền cho NSD • GRANT ON TO [WITH GRANT OPTION] • : có thể bao gồm 1 hay nhiều thao tác được liệt kê dưới đây: – Insert: chèn dữ liệu vào trong CSDL có sẵn nhưng không được thay đổi bất kỳ mục dữ liệu nào trong CSDL – Update: sửa đổi dữ liệu nhưng không được xóa dữ liệu – Delete: xóa dữ liệu trong CSDL – Select : tìm kiếm – Create: tạo lập các quan hệ mới – Alter: Thay đổi cấu trúc của quan hệ – Drop: Loại bỏ quan hệ – Read/Write: Đọc và Ghi 12 Câu lệnh phân quyền cho NSD (tiếp) • : bảng hoặc khung nhìn • : Một người hay một nhóm hay một danh sách người sử dụng. Từ khóa public được dùng thay thế cho mọi người sử dụng • [With Grant Option] Nếu dùng từ khóa này trong câu lệnh phân quyền thì người dùng xuất hiện trong có quyền được lan truyền các quyền vừa được tuyên bố cho những người dùng khác 313 Ví dụ câu lệnh phân quyền cho NSD • Trao quyền đọc, ghi, tìm kiếm, sửa đổi dữ liệu cho nhân viên tên Hoa của phòng Khoa học trên khung nhìn vừa tạo lập trong phần trước GRANT read, write, select, update ON NVKH TO Hoa; • Trao quyền cho trưởng phòng Khoa học – ông HungNC GRANT read, write, select, update, delete ON NVKH TO HungNC WITH GRANT OPTION; 14 Câu lệnh thu hồi quyền của NSD • REVOKE ON <Đối tượng> FROM [RESTRICT/CASCADE] • , , giống như đối với câu lệnh GRANT. • Phần [RESTRICT/CASCADE] là chỉ ra cơ chế thu hồi với các quyền đã được người dùng trong <D/s người dùng> lan truyền 15 Câu lệnh thu hồi quyền của NSD (tiếp) • Nếu Restrict thì có nghĩa là chỉ hủy bỏ quyền của những người có trong danh sách, quyền đã được lan truyền cho người khác không bị thu hồi. • Nếu dùng Cascade thì hủy bỏ quyền của người trong , đồng thời kéo theo hủy bỏ quyền mà người dùng đó đã luân chuyển cho những người khác. • Ví dụ: REVOKE update,delete ON NVKH FROM HungNC CASCADE 16 Toàn vẹn dữ liệu • Định nghĩa: Tính toàn vẹn dữ liệu là sự bảo vệ dữ liệu trong CSDL chống lại những sự sửa đổi, phá hủy vô căn cứ để đảm bảo tính đúng đắn và chính xác của dữ liệu. • Các thao tác có thể ảnh hưởng đến tính đúng đắn của CSDL là thêm, xóa , sửa đổi. • Để đảm bảo tính toàn vẹn dữ liệu, cần phải chỉ ra và duy trì những ràng buộc toàn vẹn liên kết với mỗi quan hệ. Các ràng buộc toàn vẹn cung cấp 1 phương tiện để đảm bảo rằng các thao tác được thực hiện bởi những người sử dụng hợp pháp không làm mất đi tính đúng đắn của CSDL. • Trong hệ thống đa người dùng, để đảm bảo được toàn vẹn dữ liệu, hệ thống còn phải có được một trình điều khiển tương tranh để tránh đụng độ giữa các thao tác được đưa ra bởi những người sử dụng khác nhau tại cùng một thời điểm 17 Các ràng buộc toàn vẹn trong SQL • Các ràng buộc về khóa chính, khóa ngoài, kiểm tra trên miền sử dụng Check chúng ta đã đề cập đến khi nói về câu lệnh tạo bảng trong CSDL. • Các khẳng định: Là một vị từ biểu thị một điều kiện mà CSDL phải luôn luôn thỏa mãn. Các khẳng định được tạo ra bằng câu lệnh: CREATE ASSERTION CHECK 18 Ví dụ về khẳng định • Số lượng mặt hàng được cung cấp bởi các hãng có số nhân viên < 50 phải nhỏ hơn 100: CREATE ASSERTION KĐSốlượng CHECK NOT EXISTS (SELECT * FROM S WHERE numofemps < 50 AND sid IN (SELECT sid FROM SP WHERE quantity >= 100)) 419 Các ràng buộc toàn vẹn trong SQL (tiếp) • Các kích hoạt: Là một thao tác được thực hiện một cách tự động khi có một thay đổi đối với CSDL. Kích hoạt là các cơ chế có ích để báo động hoặc thực hiện những nhiệm vụ được định sẵn khi các điều kiện nhất định được thỏa mãn. • Kích hoạt có thể được định nghĩa để hủy bỏ, hoặc kiểm tra và thực hiện một số các sự kiện do đó nó có thể được coi là một biện pháp để đảm bảo toàn vẹn dữ liệu. 20 Ví dụ về kích hoạt • Nhânviên(ID,Họtên,Lương,Địachỉ,Ngườ iquảnlý) • Một nhân viên bao giờ cũng có lương ít hơn lương người trưởng phòng, điều kiện này phải được kiểm tra khi thêm bộ dữ liệu. DEFINE TRIGGER ThemNV ON INSERT Nhânviên IF Nhânviên.Lương > (SELECT E.Lương FROM Nhânviên AS E WHERE E.ID = Nhânviên.Ngườiquảnlý) THEN ABORT; 21 Điều khiển tương tranh • Trong hệ CSDL đa người dùng, hệ thống cần đưa ra giải pháp chống đụng độ giữa các giao dịch (một dãy các thao tác) được đưa ra bởi những người dùng khác nhau để tránh việc một đối tượng dữ liệu nào đó bị làm mất tính đúng đắn trong quá trình cập nhật. 22 Các kỹ thuật điều khiển tương tranh • Kỹ thuật dùng khóa: Khi một giao dịch cần dữ liệu nào thì xin hệ điều hành một khóa trên phần dữ liệu đó, các giao dịch khác phải đợi đến khi giải phóng khóa mới được sử dụng phần dữ liệu đó. Có thể người ta sử dụng các loại khóa khác nhau ví dụ như khóa đọc – cho phép nhiều giao dịch đọc cùng 1 lúc, khóa ghi – chỉ 1 giao dịch có được tại một thời điểm. • Kỹ thuật gán nhãn thời gian: Mỗi giao dịch được gán một nhãn T theo thời gian, giao dịch nào cần được ưu tiên thì được gán nhãn thời gian nhỏ hơn và được thực hiện trước. Kỹ thuật này giúp đưa yêu cầu đồng thời về thực hiện tuần tự. 23 24 Lời hay ý đẹp "Khi nói sự thật bạn sẽ không phải nhớ mình vừa nói gì, mà bạn cũng không bao giờ quên những gì mình vừa nói" S.Raybum