Bài giảng Cơ sở dũ liệu - Chương 12: Thiết kế vật lý database

rọng trong nhiều ứng dụng máy tính.Có 2 loại hashing:Static hashing: kích thước của bảng hash không thay đổi, thường được dùng cho các quan hệ ít thay đổiDynamic hashing: kích thước của bảng hash có thể mở rộng ra hay thu nhỏ lại, thích hợp cho các quan hệ thường xuyên phải thêm mới hay xóa bớt bản ghi69Static hashingChỉ mục hash sẽ đưa các entry chỉ mục tương ứng với các bản ghi dữ liệu vào 1 tập con riêng biệt gọi là bucket dựa vào hàm hash h.Một entry chỉ mục mới sẽ được đưa vào 1 bucket thích hợp dựa vào kết quả tính hàm h thông qua giá trị search key v  h(v) là địa chỉ của bucket. 70Cấu trúc chỉ mục hashhOverflow ChainBucketHash computationv71Nguyên lý dò tìmĐầu tiên phép dò tìm bằng với giá trị search key v được thực hiện thông qua hàm h(v), khôi phục bucket chứa trang tham chiếu.Kế đến duyệt (scan) nội dung của trang để xác định entry chứa v. Vì không thể có 1 bucket nào khác chứa entry với giá trị khóa v, do đó nếu không tìm thấy entry trong bucket thì có nghĩa là giá trị đó không có trong file. Không cần phải duy trì 1 cấu trúc cây, entry chỉ mục có thể được khôi phục chỉ bởi 1 thao tác I/O72So sánh chỉ mục cây và chỉ mục hashChỉ mục hash được thiết kế đúng có thể thực hiện phép dò bằng hiệu quả hơn chỉ mục cây. Vì với chỉ mục cây, nhiều trang chỉ mục cần phải được khôi phục trước khi tiến tới mức lá.Nhưng nếu dò tìm bằng được thực hiện liên tiếp thì chỉ mục cây hiệu quả hơn73Ví dụCần khôi phục các bản ghi với giá trị search key k0< k1< < kl mà sự tuần tự của các search key này cũng biểu diễn thứ tự các bản ghi cần được khôi phục. Vì các lá chỉ mục của cây được sắp xếp theo khóa nên khả năng tận dụng bộ nhớ khi khôi phục các lá chỉ mục là rất lớn. Với chỉ mục hash, mỗi giá trị search key được hash vào 1 bucket khác nhau nên việc khôi phục các entry chỉ mục một cách liên tục sẽ không thể tận dụng được bộ nhớ.74Chỉ mục hashDù chỉ mục hash có nhiều thuận lợi trong việc dò tìm bằng nhưng không thể dò tìm theo miền hay dò tìm 1 phần khóa. 75Hàm hash tĩnhH(v) = (a*v +b) mod Ma,b là các hằng sốV: giá trị search keyM: số bucket thường là 1 số nguyên tố lớn hay lũy thừa của 2Vì M cố định nên hàm hash là static76Đặc tính của hashing tĩnhTính hiệu quả của hashing tĩnh phụ thuộc vào việc tất cả các entry trong mỗi bucket có nằm trong cùng 1 trang hay không?Số entry trong 1 bucket thì tỷ lệ nghịch với M: nếu số bucket ít hơn thì số entry trong mỗi bucket sẽ nhiều hơn có thể các entry không nằm hết trong 1 trang, sẽ phải có thêm các trang overflow Việc chọn giá trị cho M là quan trọng. 77Đặc tính của hashing tĩnhNếu  là fan-out, L là tổng số entry chỉ mục thì nếu chọn M = L/  sẽ làm cho các bucket bị overflow 1 trang.Nếu dùng filffactor <1 thì sẽ làm tăng số bucket. Số entry trong mỗi bucket sẽ là * fillfactor và M = L/(  * fillfactor)78Đặc tính của hashing tĩnhViệc dùng fillfactor chỉ làm giảm nhưng không giải quyết được vấn đền overflow nhất là khi bảng tăng nhanh mà không dự đoán trước được. 79Dynamic Hashing algorithmMục tiêu của hashing động là thay đổi động số bucket để giảm hay loại trừ các chuỗi overflow khi các hàng dữ liệu được thêm hay xóa. Hai loại giải thuật hashing động:Extendable hashingLinear hashing80Hashing tĩnh sử dụng hàm hashing tĩnh để phân hoạch tập các giá trị search key thành các tập con Si,1≤ I ≤ M và map mỗi tập con này vào 1 bucket. Mỗi phần tử v của Si sẽ xác định được Bi nhờ vào giá trị h(v)Dynamic Hashing algorithm81Dynamic Hashing algorithmSơ đồ hashing động cho phép Si đuợc phân hoạch ở thời gian chạy thành các tập con riêng biệt Si’ và Si” và Bi thành các Bi’ và Bi”sao cho các phần tử của Si’ ánh xạ vào các phần tử của Bi’ và các phần tử của Bi”Bằng cách giảm số giá trị được ánh xạ vào bucket , việc phân chia này có lợi thế là thay 1 bucket bị overflow thành 2 bucket không bị đầy. Việc thay đổi ánh xạ này ngụ ý là thay đổi hàm hash82Extendable hashingGiải thuật này sử dụng sự tuần tự của các hàm h2, h3,, hb dựa vào hàm hash đơn h, hàm này sẽ hash các giá trị search key vào số nguyên n bit. Đối với mỗi giá trị k, 0 ≤k≤b, hk(v) là 1 số nguyên được tạo thành bởi k bit cuối của giá trị h(v): hk(v) = h(v) mod 2kMiền của mỗi hk sẽ gấp đôi miền của hàm đứng trước nó hk-1. Tại bất kỳ thời điểm nào, một hàm đặc biệt trong chuỗi hk sẽ được dùng để dò tìm giá trị. 83Extendable hashingHashing động sẽ dùng giai đoạn thứ hai của ánh xạ để xác định bucket nào có liên quan đến giá trị search key v. Ánh xạ này sử dụng mức gián tiếp được thực thi thông qua thư mục (directory). Giá trị được tạo ra bởi hk(v) sẽ dùng như chỉ mục trong thư mục, và con trỏ trong thư mục sẽ tham chiếu đến bucket có liên quan với v. Các entry phân biệt trong thư mục có thể tham chiếu đến cùng 1 bucket, vì vậy v1 và v2 có thể được ánh xạ vào cùng bucket cho dù hk(v1) và hk(v2) là khác nhau84Ví dụGiả sử miền của h là tập các số nguyên giữa 0 và 210 – 1. Giả sử một trang bucket có thể chứa 2 entry chỉ mục và tại thời điểm đang xét, h2 đang được dùng để hash các giá trị search key. V ì k=2 nên directory có 2k = 4 entry 85Ví dụGiả sử giá trị của hàm h như sau:	 v	h(v)	pete	1001111010	mary	0100000000	jane	1100011110	bill	0100000000	john	0001101001	vince	1101110101	karen	0000110111H hash pete thành 1001111010 và vì h2 chỉ dùng 2 bit cuối 10, ứng với entry chỉ mục thứ 3 của directory, pete sẽ được chứa trong Bucket B286h2MarybillJohnvincePetejanekarenvDirectoryB0B1B2B387Ví dụNếu thêm bản ghi mới sol mà h(sol) = 0001010001. h2 sẽ ánh xạ john, vince à sol vào cùng bucket B1, gây ra tràn. Thay vì tạo chuỗi các overflow, extendable hashing phân chia B1, tạo thêm bucket mới là B5.Để phân bố 5 bucket thì cần dùng hàm hash mà miền của nó chứa nhiều hơn 4 giá trị, vì vậy h3 sẽ được thay thế cho h2.Vì h3(john) = 001, h3(vince)=101, khác nhau ở bit trái nhất, h3 sẽ ánh xạ john và vince vào 2 bucket khác nhau. 88h3MarybillJohnsolPetejanevincevB0B1B2B33Current_hashkarenB589Giải thuật phân chia bucket Một bucket mới B1 được tạo và nội dung của bucket bị tràn sẽ chia thành B và B’ bằng hàm hash kế tiếp theo thứ tựMột directory mới được tạo ra bằng cách nối bản sao của thư mục cũ vào chính nóCon trỏ đến B trong bản sao được thay thế bằng con trỏ đến B’90Hoàn chỉnh giải thuật phân chia bucketNên lưu trữ chỉ mục của hàm hash hiện hành thông qua biến current_hash. Số entry của directory sẽ là 2current_hash .Nếu thêm bản ghi judy và h(judy) = 1110000110  judy sẽ được ánh xạ vào B2, sẽ làm cho bucket bị tràn và cần phân chia. Nhưng không cần phải chuyển sang hàm kế tiếp h4 vì h3 phân biệt được judy và jane (110) với pete (010), nên chỉ cần tạo 1 bucket mới cho judy và jane và cập nhật con trỏ thích hợp trong thư mục91h3MarybillJohnsolPetevincevB0B1B2B33Current_hashkarenB5JudyjaneB6233233Bucket_level[6]92Hoàn chỉnh giải thuật phân chia bucketNên lưu trữ số lần phân chia của mỗi bucket thông qua biến mảng bucket_level[i]. Lúc đầu bucket_level[0]=0 và khi Bi nào được phân chia thì bucket_level[i] +1 được xem là mức của bucket cho cả Bi và B vừa được tạo ra. 93Linear hashingKhuyết điểm của extendable hashing có liên quan đến directory.Directory là cần thiết khi 1 bucket được phân chia, có thể cần chuyển hàm hash lên miền lớn hơnCác search key được hash vào những bucket khác nhau sẽ được hash đến các giá trị khác. Vì miền của hk+1 chứa gấp hai lần số phần tử của miền hk, vì vậy hi(v) và hi+1(v) có thể không giống nhau. 94Linear hashingMột cách khác cũng sử dụng cùng 1 chuỗi các hàm hash h0, h1, h2,, hb, nhưng hi và hi+1 được sử dụng cùng lúc:Hi dành cho các giá trị thuộc vào bucket không bị phân chiaHi+1 dành cho các giá trị thuộc vào bucket bị phân chia  Ưu điểm: cung cấp cùng 1 ánh xạ trước và sau khi phân chia cho các search key mà không liên quan gì đến sự phân chia. 95Linear hashingViệc phân chia bucket được thực hiện qua nhiều giai đoạn: Các bucket tồn tại từ giai đoạn dầu 96DenormalizationMục tiêu thiết kế CSDL:Hiệu quả trong việc sử dụng không gian đĩaHiệu quả trong việc truy xuất dữ liệuDenormalization là quá trình biến đổi các quan hệ đã chuẩn hóa thành các bảng có các bản ghi vật lý không chuẩn hóa.Mục tiêu của denormalization là tối ưu hóa việc xử lý dữ liệuDenormalization hoặc kết hợp hoặc phân chia các quan hệ97DenormalizationTrường hợp 2 thực thể quan hệ 1-1:Ngay cả khi 1 trong 2 thực thể là tùy chọn (optional), nếu các thực thể luôn tồn tại cùng nhau thì nên kết hợp chúng lại thành 1 định nghĩa bản ghiVí dụ: một sinh viên có thể nộp hoặc không nộp đơn xin học bổng98Student_IDCampus_AddressApplication_IDApplication_DateQualificationsStudent_IDStudent_IDCampus_AddressApplication_DateQualificationsQuan hệ đã chuẩn hóaQuan hệ đã khử chuẩn hóaApplication_Date và Qualifications có thể có giá trị null99DenormalizationTrường hợp thực thể kết hợp có thuộc tính không khóa:Nên kết hợp 3 quan hệ từ 2 thực thể cơ bản lúc đầu lạiMục đích: để tránh việc phải dùng thao tác kết nối (join) giữa các quan hệ này khi việc truy xuất dữ liệu này được dùng thường xuyên 100VENDORITEMPRICE QUOTEPriceVENDORITEMPRICE QUOTEContact_NameDescriptionVendor_IDAddressItem_IdVendor_IdAddressContact_NameItem_IdDescriptionVendor_IdItem_IdPriceVENDORPRICE QUOTEITEMQuan hệ đã chuẩn hóa101Vendor_IdAddressContact_NameVendor_IdItem_IdDescriptionPriceVENDORPRICE QUOTEQuan hệ đã khử chuẩn hóa102DenormalizationTrường hợp dữ liệu tham chiếu:Dữ liệu tham chiếu nằm trên thực thể phía 1 của mối kết nối 1-M và thực thể phía 1 không quan hệ thêm với thực thể nào khác.Nên trộn hai thực thể này vào trong 1 bảng khi số thực thể điển hình của thực thể phía M ứng với mỗi thực thể phía 1 tương đối ít.Ví dụ: nhiều mặt hàng (item) có cùng 1 phiếu lưu kho103VENDORITEMPRICE QUOTEWhere_StoreSTORAGEINSTRUCTIONSITEMControl_forDescriptionItem_IDContainer_TypeItem_IdInstr_IdWhere_StoreContainer_TypeItem_IdDescriptionInstr_IdSTORAGEITEMQuan hệ đã chuẩn hóa104DenormalizationTrường hợp tạo nhiều bảng hơn bằng cách phân chia 1 quan hệ thành nhiều bảngPhân chia (partition) quan hệ có 2 dạng:Chiều ngangChiều dọc105Item_IdDescriptionWhere_StoreContainer_TypeITEMQuan hệ đã khử chuẩn hóa106