Chương 6: Chuẩn hóa cơ sở dữ liệu

Cơ Sở Lý Thuyết Nếu Q là một lược đồ quan hệ được tách thành các lược đồ con Q1,Q2,...,Qk và F là tập phụ thuộc hàm, nói rằng phép tách (phân rã ) là phép tách có bảo toàn thông tin đối với F nếu với mỗi quan hệ r trên Q thỏa F:
Nội dung trích xuất từ tài liệu:
Chương 6: Chuẩn hóa cơ sở dữ liệu Môn CƠ SỞ DỮ LIỆU Chương 6: Chuẩn hóa  cơ sở dữ liệu Nội dung 1. PHÉP KẾT NỐI BẢO TOÀN THÔNG TIN Cơ Sở Lý Thuyết  Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn  Thông Tin 2. PHÉP TÁCH BẢO TOÀN PHỤ THUỘC HÀM Cơ sở lý thuyết  Thuật toán  3. CÁCH TIẾP CẬN PHÂN Rà ĐỂ THIẾT KẾ CSDL 4. CÁCH TIẾP CẬN TỔNG HỢP ĐỂ THIẾT KẾ CSDL 2 1. PHÉP KẾT NỐI BẢO TOÀN T.TIN Cơ Sở Lý Thuyết Nếu Q là một lược đồ quan hệ được tách thành các lược đồ con Q1,Q2,...,Qk và F là tập phụ thuộc hàm, nói rằng phép tách (phân rã ) là phép tách có bảo toàn thông tin đối với F nếu với mỗi quan hệ r trên Q thỏa F: Q =ΠQ1(r) * ΠQ2 (r)* . . * ΠQk(r) Tức là r được tạo nên từ phép kết nối tự nhiên của các hình chiếu của nó trên Qi ( i =1..k) 3 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt) Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn Thông Tin Dữ liệu vào: Lược đồ quan hệ Q(A1,A2,…An) và tập các phụ thuộc  hàm F, phép tách = {Q,Q,…,Qk}. Dữ liệu ra: Phép tách có bảo toàn thông tin hay không?  (1)Thiết lập bảng với k + 1 dòng, n + 1 cột . Cột j ứng với thuộc tính AJ(i=1...n), hàng i ứng với lược đồ quan hệ Qi(i=1…k). Tại ví trí hàng i, cột j ta điền ký hiệu Aj nếu AJ Qi, Đầu tiên đặt t=1 và đặt vào các ô còn lại của bảng ký hiệu bt theo chiều từ trái sang phải và từ trên xuống dưới, sau đó tăng t lên một đơn vị và lặp lại thao tác điền bt như trên. Cho đến khi mọi ô của bảng điều đã có ký hiệu. (2)Xét lần lượt các phụ thuộc hàm trong F, áp dụng cho bảng vừa mới thành lập ở trên. Giả sử xét (X Y) F, chúng ta tìm những hàng giống nhau ở tất cả các thuộc tính của X, nếu thấy những hàng như vậy ta sẽ làm cho các ký hiệu của hai hàng này bằng nhau ở tất cả các thuộc tính của Y. 4 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt) Thuật Toán Kiểm Tra Tính Kết Nối Bảo Toàn Thông Tin (tt) Khi làm cho 2 ký hiệu này bằng nhau, ta gặp 3 trường hợp sau đây: nếu một trong hai ký hiệu là AJ thì cho ký hiệu kia trở thành AJ,  nếu hai ký hiệu là bk hoặc bl thì có thể cho chúng trở thành bt hoặc  bt (với t=min (k,l)), nếu cả hai ký hiệu là aj thì giữ nguyên (lúc đó chỉ số j của các ký  hiệu này phải giống nhau) Chú ý rằng bước này có thể được lặp lại (cho các phụ thuộc hàm) cho đến khi không còn áp dụng được nữa (nghĩa là cho đến khi nào ở một lần duyệt qua tất cả các phụ thuộc hàm trong F mà bảng không có sự thay đổi nào. (3)Xét bảng kết quả, nếu thấy trong bảng này có một hàng chứa toàn aj (i=1..n) thì kết luận đó là phép tách bảo toàn thông tin, ngược lại thì là phép tách mất mát thông tin. 5 1. PHÉP KẾT NỐI BẢO TOÀN TT (tt) Ví dụ:  6 2. PHÉP TÁCH BẢO TOÀN PTH Cơ sở lý thuyết  Cho phân rã p = {Q1,Q2,…Qk} của một lược đồ quan hệ, và tập phụ thuộc hàm F. Hình chiếu của F trên một tập các thuộc tính Z ký hiệu ΠZ(Q) là tập các phụ thuộc hàm X → Y ∈ F+ sao cho XY ⊆ Z . Ta nói phân rã p bảo toàn tập phụ thuộc hàm F nếu hợp của tất cả các phụ thuộc hàm trong Qi(F) với i=1..k suy ra được tất cả các phụ thuộc hàm trong F. Lý do p cần bảo toàn tập F đó là vì các phụ thuộc hàm trong F có thể  được xem là các ràng buộc toàn vẹn cho quan hệ Q. Nếu các phụ thuộc hình chiếu không suy ra được F thì khi biểu diễn Q qua p , chúng ta có thể thấy rằng giá trị hiện hành của các Qi biểu diễn một quan hệ Q không thỏa F, ngay cả nếu p là phép tách không mất thông tin ứng với F. Khi đó mỗi thao tác cặp nhật trên mỗi Ri sẽ cần phải thực hiện một phép nối để kiểm tra lại rằng các ràng buộc không bị vi phạm. Dữ liệu vào: Một phân rã p={Q1,Q2,…Qk} và một tập các phụ thuộc  hàm F(f1,f2,…,fm} Dữ liệu ra: phép tách p có bảo toàn phụ thuộc hàm hay không ? 7  2. PHÉP TÁCH BẢO TOÀN PTH (tt) Phép tách bảo toàn phụ thuộc hàm Về nguyên tắc,chúng ta có thể dễ dàng kiểm tra xem một  phân rã p = {Q1,Q2,…Qk} có bảo toàn tập phụ thuộc F hay không. Chúng ta chỉ cần tính F+ rồi chiếu nó trên tất cả các thành phần Qi. Sau đó lấy hợp của các tập phụ thuộc kết quả rồi kiểm ra xem tập này có tương đương với F hay không ? Tuy nhiên trong thực tế, tính F+ là một công việc hết sức  khó khăn vì số lượng các phụ thuộc chứa trong nó thường là hàm mũ theo kích thước của F. Nhưng có một cách để kiểm tra tính bảo toàn này mà không cần phải tính F+; phương pháp này có chi phí thời gian tỷ lệ với hàm đa 8 2. PHÉP TÁCH BẢO TOÀN PTH (tt) Thuật toán Chúng ta gọi G là hợp của các Qi(F), để tính xem G có tương đương  với F hay không chúng ta xét mỗi phụ thuộc hàm X Y F và xác định xem X+ (được tính ứng với G) có chứa Y hay không ? nếu có thì phụ thuộc hàm này thuộc G. Chúng ta định nghĩa phép toán Q trên tập các thuộc tính Z ứng với  một tập phụ thuộc F là phép thế Z bằng Z ((Z Q)+ Q) trong đó bao đóng luôn được lấy ứng với F, phép toán này nối Z với những thuộc tính A sao cho (Z Q) A QF. Do đó chúng ta tính X+ ứng với G bằng cách khởi đầu với X, qua danh sách các Qi, chúng ta lần lượt thực hiện các phép toán Qi với mỗi i, nếu tại một lần lặp nào đó không có một phép toán Qi nào làm thay đổi các tập thuộc tính hiện có thì chúng ta đã thực hiện xong; tập kết quả là X+ Nếu Y là một tập con của Z, là kết quả của thực hiện các phép trên  thì X Y G+ , nếu mỗi phụ thuộc hàm trong F đều thuộc G thì là đúng, ngược lại là sai. *Chú ý: Một phân rã có thể bảo toàn thông tin nhưng không chắc bảo 9 3. TIẾP CẬN PHÂN RàĐỂ TK CSDL Theo quan điểm của cách tiếp cận này, các quan hệ con của cấu trúc  cơ dở dữ liệu ban đầu sẽ lần lượt được phân ...