Bài giảng Cơ sở dữ liệu - Chương 3: Cơ bản về thiết kế cơ sở dữ liệu - Phạm Nguyên Thảo

Trường Đại học Khoa học Tự nhiên Khoa Công nghệ Thông tin Bộ môn Hệ thống Thông tin Chương 3: Cơ bản về thiết kế cơ sở dữ liệu Phạm Nguyên Thảo pnthao@fit.hcmuns.edu.vn 2 Nội dung • Khái niệm về phụ thuộc hàm • Khái niệm về dạng chuẩn • Chuẩn bị cài đặt CSDL • Cài đặt chỉ mục với SQL Server 3 Khái niệm phụ thuộc hàm • Phụ thuộc hàm (PTH) – functional dependency thể hiện sự phụ thuộc của một tập thuộc tính (Y) đối với một tập thuộc tính khác(X) – Định nghĩa dựa trên những ngữ nghĩa, qui tắc tìm hiểu được từ môi trường ứng dụng – Ký hiệu XY 4 Khái niệm PTH (tt) • Cho quan hệ Q(X, Y, Z), với X, Y, Z là các tập thuộc tính, X  , Y   – Một thể hiện TQ của Q thỏa PTH XY nếu: q,q’TQ, q.X = q’.X =>q.Y = q’.Y – TQ vi phạm PTH XY nếu: q,q’ TQ: q.X = q’.X và q.Y  q’.Y – PTH XY được gọi là định nghĩa trên Q nếu TQ là thể hiện của Q, TQ thỏa PTH này – PTH XY gọi là phụ thuộc hàm hiển nhiên  Y X 5 PTH – ví dụ • Xét lịch xếp lớp của một cơ sở giảng dạy trong một ngày, ta có các phụ thuộc hàm sau: – (1) GV, Giờ  Lớp ( nếu biết giảng viên và giờ dạy, ta sẽ biết được lớp mà giảng viên dạy vào giờ đó) – (2) Giờ, Lớp  Phòng (Cho một giờ học và lớp học cụ thể, ta sẽ biết được lớp đang học phòng nào vào giờ đó)  Nếu biết giảng viên và giờ dạy, ta sẽ biết Phòng mà giảng viên dạy vào giờ đó  (3) GV,Giờ  Phòng 6 Hệ tiên đề Amstrong để suy dẫn PTH • Luật phản xạ: Y X, XY • Luật cộng: Nếu X Y và Z  W thì X,W Y,Z • Luật bắc cầu: Nếu X Y và Y Z thì X Z 7 Một số luật dẫn thông dụng khác • Từ các luật dẫn trong tiên đề Amstrong ta có thể suy ra các luật dẫn khác, một số sau đây thường được sử dụng: – Luật bắc cầu giả: Nếu X Y và Y,W  Z thì X,W  Z – Luật hội: Nếu X Y và X Z thì X Y,Z – Luật phân rã: Nếu X Y và Z Y thì X Z Ghi chú: X,Y hay XY có nghĩa là X Y 8 Khái niệm khóa dựa trên PTH • Cho quan hệ Q và F là tập PTH định nghĩa trên Q • K  Q+ là một khóa của Q nếu: i. f: K Q+  F+ (K xác định tất cả các thuộc tính còn lại trong Q+) ii. K’  K | K’  Q+ (ghi chú: Q+ là tập thuộc tính của quan hệ Q ) 9 Nội dung • Khái niệm về phụ thuộc hàm • Khái niệm về dạng chuẩn • Chuẩn bị cài đặt CSDL • Cài đặt chỉ mục với SQL Server 10 Tình trạng trùng lắp thông tin • Phụ thuộc hàm là một loại ràng buộc toàn vẹn • Khi thêm, xóa, cập nhật dữ liệu phải đảm bảo không vi phạm PTH – Các PTH mà vế trái là một khóa: được kiểm tra hiệu quả bằng cơ chế khóa của HQT – Các PTH mà vế trái không là một khoá: khó kiểm tra, thường gây ra tình trạng trùng lắp thông tin 11 Tình trạng trùng lắp thông tin (tt) • Ví dụ: MON_KT(N,G,P,M,GV); F2 = {N,G,PM; M GV} Với một thể hiện: – Nhận xét về sự trùng lắp thông tin và bất tiện khi thêm/ xóa/ sửa dữ liệu? N G P M GV 2 8:00 – 10:00 101 Giải thuật X 2 10:00 – 12:00 101 CSDL Y 2 8:00 – 10:00 103 Giải thuật X T_MÔN_KT 12 Tình trạng trùng lắp thông tin (tt) • Các bất tiện gây ra do trùng lắp thông tin: – Bất tiện khi thêm/cập nhật : để đảm bảo dữ liệu nhất quán, phải kiểm tra và cập nhật hàng loạt trên các thông tin trùng lắp – Mất thông tin khi xóa 13 Khái niệm dạng chuẩn • Dạng chuẩn là một tiêu chuẩn được đưa ra để đánh giá chất lượng của một lược đồ CSDL • Mục tiêu khi nâng cấp dạng chuẩn của một lược đồ: giảm thiểu trùng lắp thông tin 14 Định nghĩa các dạng chuẩn • Dạng chuẩn 1: – Một quan hệ ở dạng chuẩn 1 không có các trường lặp và các trường kép, còn được gọi là cấu trúc phẳng. – Ví dụ: LỊCH_COI_THI (GV_CT, N,G,P,M,GV) F = {f1: GV_CTN,G,P: một giảng viên coi thi chỉ coi vào một ngày(N), một giờ (G) và trong một phòng(P) duy nhất f2: M  GV : mỗi môn thi (M) có một giảng viên (GV) duy nhất phụ trách f3: N,G,P  M : mỗi ngày, vào một giờ, trong một phòng, chỉ có một môn thi duy nhất } 15 Định nghĩa các dạng chuẩn (tt) • Dạng chuẩn 2: – Một quan hệ Q ở dạng chuẩn 2 nếu và chỉ nếu tất cả thuộc tính không khóa đều phụ thuộc đầy đủ vào khóa, tức là: (f: XY)  F, không tồn tại X’  X sao cho (X’Y)  F+ – Ví dụ: MON_KT(N,G,P,M,GV); F2 = {N,G,PM; M GV} 16 Định nghĩa các dạng chuẩn (tt) • Dạng chuẩn 3: – Q ở DC3 nếu và chỉ nếu với mỗi phụ thuộc hàm XA không hiển nhiên định nghĩa trên Q (A là thuộc tính đơn, X là tập thuộc tính), một trong hai điều kiện sau được thỏa: i. Hoặc X chứa một khóa của Q ii. Hoặc A là một thuộc tính trong khóa của Q – Ví dụ: LỊCH_KT(N,G,P,M); F1 = {N,G,P M; M P } (LỊCH_KT có hai khóa là (N,G,P) và (N,G,M) ) GIANG_DAY(M,GV) ; F2 = {M  GV} 17 Định nghĩa các dạng chuẩn (tt) • Dạng chuẩn BCK (Boyce_Codd_Kent) – Q ở DC BCK nếu và chỉ nếu: với mỗi PTH không hiển nhiên X  A định nghĩa trên Q thì B  Q+, ta luôn có (XB) là một PTH thuộc F+. Hay nói cách khác, X chứa một khóa của Q – Ví dụ: LICH_KT_1(M,P) ; F1 = {M P} LICH_KT_2(M,N,G); F2 =  GIANG_DAY(M,GV); F3 = {M  GV} 18 Tính lồng nhau của các dạng chuẩn DC 1 DC 2 DC 3 DC BCK 19 Dạng chuẩn của lược đồ CSDL • Định nghĩa: Cho một lược đồ CSDL C = {}, i = 1..n Dạng chuẩn của C là dạng chuẩn thấp nhất trong các dạng chuẩn của các Qi 20 Nâng cấp lược đồ - Thuật toán phân rã • Mục tiêu: Đưa lược đồ về dạng chuẩn cao hơn. • Thuật toán: Với mọi quan hệ Q trong lược đồ đạt dạng chuẩn thấp: – Chọn một PTH XY gây ra dạng chuẩn thấp cho quan hệ Q – Phân rã Q thành Q1(XY) và Q2(Q + - Y) – Đệ qui, phân rã tiếp Q1 và Q2 cho đến khi các quan hệ kết quả đều đạt dạng chuẩn mong muốn 21 Nâng cấp lược đồ - Thuật toán phân rã (tt) • Ví dụ: LỊCH_COI_THI (GV_CT, N,G,P,M,GV) F = {f1: GV_CTN,G,P: một giảng viên coi thi chỉ coi vào một ngày(N), một giờ (G) và trong một phòng(P) duy nhất f2: M  GV : mỗi môn thi (M) có một giảng viên (GV) duy nhất phụ trách f3: N,G,P  M : mỗi ngày, vào một giờ, trong một phòng, chỉ có một môn thi duy nhất } – Áp dụng thuật toán phân rã để đưa lược đồ trên về dạng chuẩn BCK ? 22 Dạng chuẩn – nhận xét – Dạng chuẩn càng cao thì càng giảm được trùng lắp thông tin. Lược đồ ở dạng chuẩn BCK không còn trùng lắp thông tin. – Tuy nhiên, dạng chuẩn cao có thể gây ra khó khăn khi truy vấn (các quan hệ bị tách nhỏ nên phải thực hiện nhiều phép kết hơn) – Đôi khi dạng chuẩn cao gây khó khăn trong kiểm tra một số PTH (trong ví dụ về DC BCK, để kiểm tra PTH N,G,PM, ta phải kết LICH_KT_1 và LICH_KT_2 ) 23 Nội dung • Khái niệm về phụ thuộc hàm • Khái niệm về dạng chuẩn • Chuẩn bị cài đặt CSDL • Cài đặt chỉ mục với SQL Server 24 Các vấn đề chính • Cân nhắc các thông tin về khối lượng dữ liệu và tần suất khai thác: – Quyết định gộp – tách bảng (Thông thường các quan hệ nên đạt DC 3 trở lên, tuy nhiên đôi khi chấp nhận dạng chuẩn thấp hơn để truy vấn thuận lợi hơn) – Lựa chọn khoá chính cho bảng (trường hợp bảng có nhiều khóa, chọn một khoá làm khoá chính, các khóa còn lại dùng ràng buộc unique để cài đặt) – Lựa chọn chỉ mục cho bảng 25 Lựa chọn chỉ mục (index) • Không có chỉ mục, HQT thực hiện truy vấn bằng cách duyệt qua từng dòng trong bảng • Cài đặt các chỉ mục cho bảng giúp truy vấn thông tin nhanh hơn (tìm kiếm trên B-Tree) • Khóa chính và các ràng buộc unique : hiển nhiên là các chỉ mục của bảng • Cơ sở để chọn cài đặt chỉ mục: các nhu cầu truy vấn thực hiện thường xuyên trên CSDL 26 Lựa chọn chỉ mục (tt) • Nghĩ đến việc cài đặt chỉ mục cho các trường hợp sau: – Trường hợp 1: Có nhu cầu truy vấn thường xuyên các bộ của bảng Q theo một số (tập)thuộc tính nào đó Ví dụ: GiaoDich(MãGD, ,NgàyGD) Có nhu cầu truy xuất thường xuyên các bộ của giao dịch trong một ngày hoặc trong một khoảng thời gian nhất định: cài đặt chỉ mục trên thuộc tính NgayGD của quan hệ GiaoDich 27 Lựa chọn chỉ mục (tt) – Trường hợp 2: tập thuộc tính tham gia vào phép kết của một câu truy vấn xảy ra thường xuyên Ví dụ: HocSinh(STT, Lop, HoTen,) KetQua(STTHS, Lop, Mon, Diem) Thường xuyên có nhu cầu truy vấn: cho biết kết quả học tập của một học sinh select hs.STT, hs.Lop, hs.HoTen, kq.Mon, kq.Diem from HocSinh hs join KetQua kq on hs.STT = kq.STT and hs.Lop = kq.Lop Cài đặt chỉ mục (STT, Lop) cho quan hệ KetQua 28 Lựa chọn chỉ mục (tt) – Trường hợp 2 (tt) Tổng quát: trên mô hình quan hệ, xác định các con đường truy xuất thường xuyên:  Từ một bộ của Q1(có một giá trị cụ thể của A là a) có nhu cầu truy xuất thường xuyên các bộ của Q2 tương ứng (tìm kiếm các bộ của Q2 với A = a) : khai báo chỉ mục (A) cho Q2 Truy xuất thường xuyên có ngữ nghĩa tương tự phép kết Lưu ý: một chỉ mục (AB) khác với hai chỉ mục (A) và (B) 1 2 Q2(ABY) Q1(AX) 29 Các loại chỉ mục • Có hai loại chỉ mục: – Clustered index – Nonclustered index 30 Clustered index • Các bộ được sắp xếp vật lý theo chỉ mục (thật sự nằm ở nút lá của cây) • Mỗi bảng chỉ có thể có một clustered index, thường là khóa chính 31 Nonclustered index: • Chỉ mục logic, dữ liệu thật sự không được sắp xếp vật lý theo chỉ mục • Nút lá là con trỏ trỏ đến vị trí của bộ dữ liệu, hoặc trỏ đến giá trị của clustered index (trong trường hợp bảng có clustered index) 32 Nonclustered index (tt): – Không có clustered index: 33 Nonclustered index (tt) – Có clustered index 34 Lựa chọn chỉ mục (tt) • Một số cân nhắc khi chọn chỉ mục: – Sử dụng nhiều chỉ mục tăng tốc độ truy vấn, nhưng làm giảm hiệu quả của các thao tác thêm/xoá/ cập nhật dữ liệu – Không nên tạo chỉ mục trên các bảng quá nhỏ (vài trăm dòng) . – Chỉ nên chọn chỉ mục mà mỗi giá trị của nó tương ứng với một số ít bộ. Nếu mỗi giá trị chỉ mục ứng với trên 20% số lượng bộ trong bảng, thực hiện truy vấn bình thường bằng cách duyệt qua các dòng trong bảng sẽ hiệu quả hơn. 35 Một số cân nhắc khi chọn chỉ mục (tt) – Các giá trị chỉ mục phải phân bố đều các bộ trong bảng. – Cố gắng dùng các chỉ mục với số thuộc tính ít (chiếm ít không gian và cần ít chi phí duy trì hơn chỉ mục với số thuộc tính lớn) – Clustered index phải nhỏ (số thuộc tính ít, kích thước nhỏ), vì các chỉ mục nonclustered đều phải gắn kết tới nó. 36 Nội dung • Khái niệm về phụ thuộc hàm • Khái niệm về dạng chuẩn • Chuẩn bị cài đặt CSDL • Cài đặt chỉ mục với SQL Server 37 Một số qui định • Một bảng có tối đa 249 nonclustered index (bao gồm cả những index ngầm định khi khai báo khoá chính và chỉ mục) • Kích thước tối đa của một chỉ mục (tổng kích thước các thuộc tính tham gia vào chỉ mục) không quá 900 bytes • Mặc định: chỉ mục clustered được khai báo ngầm định cùng với khai báo khoá chính, các trường hợp khác là nonclustered (tất nhiên có thể chỉ định khác đi) 38 Cú pháp khai báo chỉ mục Create [ Unique ][ Cluster| Nonclustered] Index index_name On {table | view } (column [ Asc | Desc] [ ,...n ] ) 39 Cài đặt chỉ mục – Ví dụ Create nonclustered index idx_STTHS_Lop On KETQUA (STTHS, Lop) 40 Q&A