Chương IV. Thiết kế cơ sở dữ liệu phân bố

07/05/14 1 CHƯƠNG IV. THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN BỐ TRƯỜNG CAO ĐẰNG CÔNG NGHỆ THÔNG TIN TP.HỒ CHÍ MINH Giảng Viên: Th.S Lê Thị Minh Nguyện Email: nguyenltm@hotmail.com NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 2 07/05/14 2 Các bước thiết kế CSDL phân bố Thiết kế CSDL tập trung  Thiết kế lược đồ ý niệm  Thiết kế CSDL vật lý Thiết kế CSDL phân bố  Thiết kế lược đồ toàn cục  Thiết kế phân mãnh  Thiết kế định vị mãnh  Thiết kế CSDL vật lý cục bộ 3 Thiết kế CSDL phân tán: Cần phải hiểu biết thật chính xác về các yêu cầu của ứng dụng, nhất là đối với các ứng dụng quan trọng hơn. Cần quan tâm đến  Nơi chạy ứng dụng  Tần suất chạy ứng dụng  Số lượng, loại và sự phân tán của các truy xuất 4 Các bước thiết kế CSDL phân bố 07/05/14 3 5 Các bước thiết kế CSDL phân bố NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 6 07/05/14 4 Mục tiêu của thiết kế CSDL PB Tính cục bộ xử lý - processing locality  Phân tán dữ liệu để cực đại hóa cục bộ xử lý – đặt dữ liệu càng gần các ứng dụng sử dụng các dữ liệu này càng tốt  Một quan hệ không là một đơn vị phân tán  Tính cục bộ xử lý dựa vào các tham chiếu cục bộ và các tham chiếu từ xa Tính sẵn sàng và độ tin cậy  Tính sẵn sàng  Độ tin cậy 7 Điều phối tải làm việc  Cực đại hóa mức độ song song các ứng dụng  Điều phối tải làm việc có thể ảnh hưởng ngược lại với tính cục bộ xử lý  Tính đồng thời nội truy vấn Chi phí lưu trữ và khả năng lưu trữ có sẵn  Khả năng lưu trữ có sẵn tại mỗi nơi  Chi phí lưu trữ dữ liệu là không đáng kể so với các chi phí CPU, nhập/xuất và truyền thông của các ứng dụng 8 Mục tiêu của thiết kế CSDL PB 07/05/14 5 NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 9 Các cách tiếp cận thiết kế CSDL Thiết kế từ trên xuống – Top-down design  Thiết kế lược đồ toàn cục  Thiết kế phân mảnh CSDL  Định vị các mảnh tại các nơi  Thiết kế dữ liệu vật lý đặt tại mỗi nơi 10 07/05/14 6 11 Cách tiếp cận từ trên xuống Cách tiếp cận từ dưới lên Thiết kế từ dưới lên – Bottom-up design  Chọn một mô hình CSDL chung để mô tả lược đồ toàn cục của CSDL  Chuyển đổi mỗi lược đồ cục bộ thành mô hình dữ liệu chung  Tích hợp các lược đồ cục bộ thành một lược đồ toàn cục chung 12 07/05/14 7 NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 13 Thiết kế phân mãnh ngang Một mảnh là một tập hợp con gồm các bộ của quan hệ Phân mảnh ngang chính là phân chia một quan hệ dựa vào các vị từ định tính được định nghĩa trên quan hệ này Phân mảnh ngang dẫn xuất là phân chia một quan hệ dựa vào các vị từ định tính được định nghĩa trên một quan hệ khác 14 07/05/14 8 Thông tin về CSDL  Trong lược đồ ý niệm toàn cục, các quan hệ được kết nối với nhau  Trong mô hình liên kết thực thể (ER model) • Quan hệ chủ hoặc quan hệ nguồn • Quan hệ bộ phận hoặc quan hệ đích • Các hàm OWNER(L) và MEMBER(L) 15 Thiết kế phân mãnh ngang Biểu diễn các mối liên kết giữa các quan hệ dùng các đường liên kết 16 Thiết kế phân mãnh ngang 07/05/14 9 Thông tin về ứng dụng (application)  Các vị từ được sử dụng trong các truy vấn  Chỉ phân tích các ứng dụng quan trọng để xác định các vị từ này  Giả sử phân mảnh ngang quan hệ R(A1,A2,,An), với Ai là thuộc tính được định nghĩa trên miền Di: Chúng ta có các định nghĩa sau đây: 17 Thiết kế phân mãnh ngang Thông tin về ứng dụng (application)  Vị từ đơn giản (simple predicate) pj được định nghĩa trên R có dạng Aiθ value  θ là một trong các phép so sánh =, #, , ≥  value được chọn từ miền giá trị của Ai (value € Di) Ký hiệu Pr là tập hợp các vị từ đơn giản được định nghĩa trên quan hệ R. Các phần tử của Pr được ký hiệu là pj 18 Thiết kế phân mãnh ngang 07/05/14 10 Thông tin về ứng dụng (application)  Vị từ giao tối thiểu (minterm predicate) mj đối với tập các vị từ đơn giản Pr={p1, p2,, pm} là một tổ hợp giao của tất cả các vị từ xuất hiện trong Pr (ở dạng thông thường hoặc ở dạng phủ định) sao cho mj không bị mâu thuẫn mj = ᴧp*i, 1 ≤ i ≤ m Với p*i ={ pi | ¬pi} và mj ≠ false  Gọi tập các vị từ giao tối thiểu: M={m1, m2,, mz} 19 Thiết kế phân mãnh ngang Thông tin về ứng dụng (application)  Độ chọn giao tối thiểu sel(mj) (mintern selectivity) – số bộ quan hệ sẽ được truy xuất bởi một truy vấn tương ứng với một vị từ giao tối thiểu cho trước.  Tần số truy xuất acc(qi) (access frequency) – tần số của các ứng dụng truy xuất dữ liệu. Q={q1, q2,..., qq} tập hợp các truy vấn, acc(qi) cho biết tần số truy vấn 20 Thiết kế phân mãnh ngang 07/05/14 11 NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 21 Thiết kế phân mãnh ngang chính Mảnh ngang chính được xác định bằng phép chọn trên quan hệ chủ của lược đồ CSDL. Ri = σFI (R), 1 ≤ i ≤ n  Fi điều kiện chọn của mảnh Ri  Nếu Fi ở dạng chuẩn giao thì nó là một vị từ giao tối thiểu mi  Tính đúng đắn của phân mảnh ngang chính: mỗi bộ của quan hệ chủ được đưa vào trong một và chỉ một mảnh. 22 07/05/14 12 Xác định phân mảnh ngang chính của một quan hệ chủ là xác định một tập các vị từ chọn (selection predicate) đầy đủ và tách biệt Các bộ thuộc cùng một mảnh phải được tham chiếu giống nhau trong tất cả các ứng dụng Mảnh ngang hoặc mảnh giao tối thiểu Ri bao gồm tất cả các bộ của R thỏa mãn vị từ giao tối thiểu mi 23 Thiết kế phân mãnh ngang chính Các bước thiết kế phân mảnh ngang  Bước 1: Tìm tập các vị từ chọn Pr’ là đầy đủ và tối thiểu  Bước 2: Tìm tập các vị từ giao tối thiểu có thể đuợc định nghĩa trên các vị từ của Pr’ 24 Thiết kế phân mãnh ngang chính 07/05/14 13 Một vị từ đơn giản pi được gọi là thích hợp (relevant) đối với một tập Pr, nếu tồn tại ít nhất hai vị từ giao tối thiểu mi và mj của Pr mà các biểu thức của chúng chỉ khác nhau ở pi (mi chứa pi, mj chứa ¬pj) và tồn tại ít nhất một ứng dụng tham chiếu khác nhau đến 2 mảnh fi và fj (tương ứng với mi và mj) 25 Thiết kế phân mãnh ngang chính Một tập vị từ đơn giản Pr được gọi là đầy đủ (complete) nếu và chỉ nếu 2 bộ nào thuộc bất kỳ mảnh giao tối thiểu nào được định nghĩa theo Pr, thì bất kỳ ứng dụng nào đều tham chiếu đến hai bộ này cùng với một xác suất. Một tập các vị từ đơn giản Pr được gọi là tối thiểu (minimal) nếu tất cả các vị từ của nó là các vị từ thích hợp 26 Thiết kế phân mãnh ngang chính 07/05/14 14 27 Thiết kế phân mãnh ngang chính Pr = (p1, p2,, pm) – tập các vị từ đơn giản Để cho Pr biểu diễn phân mảnh đúng đắn và hiệu quả thì Pr phải đầy đủ và tối thiểu 28 Thiết kế phân mãnh ngang chính 07/05/14 15 EMP(EMPNUM,NAME,SAL,TAX,MGRNUM,DEPTNUM,JOB) DOM(DEPTNUM)={1,2} Ứng dụng quan trọng:  Thông tin thành viên là nhân viên các dự án  Dữ liệu các nhân viên là người lập trình 29 Thiết kế phân mãnh ngang chính Q: Qui tắc cơ bản về tính đầy đủ và tối thiểu: Một quan hệ hoặc một mảnh được phân mảnh "thành ít nhất hai phần và chúng được truy xuất khác nhau bởi ít nhất một ứng dụng“ Xét thuât tóan COM_MIN 30 Thiết kế phân mãnh ngang chính 07/05/14 16 31 Thiết kế phân mãnh ngang chính 32 Thiết kế phân mãnh ngang chính 07/05/14 17 Ví dụ P1={SAL>35000} SAL>35000: thích hợp P1 P2={SAL>35000, DEPTNUM=1} DEPTNUM=1: thích hợp với P2 P3={SAL>35000, DEPTNUM=1, JOB=‘P’} JOB=‘P’: thích hợp với P3 SAL>35000: không thích hợp P1  P4={DEPTNUM=1, JOB=‘P’} Đầy đủ và tối thiểu 33 NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 34 07/05/14 18 Thiết kế phân mãnh ngang dẫn xuất Phân mảnh ngang dẫn xuất được định nghĩa trên các quan hệ bộ phận của đường liên kết theo phép chọn trên quan hệ chủ của đường liên kết này Đường liên kết giữa quan hệ chủ và quan hệ bộ phận được định nghĩa là một phép kết bằng Một phép kết bằng có thể thực hiện bằng các phép nửa kết 35 Xét đường liên kết L với owner(L) = S và member(L) = R, các mảnh ngang dẫn xuất được định nghĩa như sau n – số lượng lớn nhất các mảnh được định nghĩa trên R Si= σFI (S), với Fi là công thức dùng để định nghĩa mảnh ngang chính Si F – điều kiện nửa kết 36 Thiết kế phân mãnh ngang dẫn xuất 07/05/14 19 Để thực hiện phân mảnh ngang dẫn xuất cần có  Tập các mảnh của quan hệ chủ  Quan hệ bộ phận  Tập các vị từ nữa kết giữa quan hệ chủ và quan hệ bộ phận 37 Thiết kế phân mãnh ngang dẫn xuất Phép kết phân bố (distributed join) là một phép kết giữa các quan hệ được phân mảnh ngang Có thể suy diễn để xác định một số phép kết từng phần Phép kết phân tán được biểu diễn bằng đồ thị kết (join graph) 38 Thiết kế phân mãnh ngang dẫn xuất 07/05/14 20 Đồ thị kết được gọi là hoàn toàn (total) nếu nó chứa tất cả các cạnh có thể có giữa các mảnh của R và S Đồ thị kết được gọi là suy giảm (reduced) nếu không có một số cạnh giữa các mảnh của R và S  Đồ thị kết suy giảm phân hoạch (partitioned)  Đồ thị kết suy giảm đơn giản (simple) 39 Thiết kế phân mãnh ngang dẫn xuất Đồ thị kết suy giảm phân hoạch – bao gồm hai hoặc nhiều đồ thị con và không có các cạnh giữa chúng Đồ thị kết suy giảm đơn giản – phân hoạch và mỗi đồ thị con có đúng 1 cạnh 40 Thiết kế phân mãnh ngang dẫn xuất 07/05/14 21 41 Đồ thị kết Đồ thị kết phân hoạch Đồ thị kết đơn giản Thiết kế phân mãnh ngang dẫn xuất Có thể có nhiều đường liên kết đến một quan hệ R và có nhiều cách phân mảnh ngang dẫn xuất cho R dựa trên 2 tiêu chuẩn:  Sự phân mảnh có các đặc điểm kết tốt hơn  Sự phân mảnh được sử dụng trong nhiều ứng dụng hơn 42 Thiết kế phân mãnh ngang dẫn xuất 07/05/14 22 NỘI DUNG Các bước thiết kế CSDL phân bố Mục tiêu của thiết kế CSDL phân bố Các cách tiếp cận thiết kế CSDL Thiết kế phân mãnh ngang Thiết kế phân mãnh ngang chính Thiết kế phân mãnh ngang dẫn xuất Thiết kế phân mãnh dọc 43 Phân mãnh dọc Phân mảnh tách biệt (Vertical partitioning fragmentation): các tập thuộc tính không giao nhau Phân mảnh nhóm gom tụ (Vertical clustering fragmentation): các tập thuộc tính có thể giao nhau  Lưu ý có nhân bản, không nên cập nhật thường xuyên thuộc tính bị phủ lấp Phân mảnh tối ưu (Optimal fragmentation)  Tạo lược đồ phân mảnh, tối thiểu hóa thời gian thực hiện của các ứng dụng 44 07/05/14 23 Cách tiếp cận phân tách (split approach)  QH toàn cục được tách dần dần để tạo mảnh dựa trên cách phân mảnh có lợi dựa trên truy suất của các applications Cách tiếp cận gom nhóm (grouping approach)  Thuộc tính kết hợp dần để tạo mảnh. Gắn mỗi attribute cho mỗi mảnh và sau đó kết hợp dần dần thỏa một tiêu chuẩn nào đó. 45 Phân mãnh dọc Tự lực/ái lực/lực hút (affinity)  Là số đo lực hút của các thuộc tính  Chỉ ra mức độ liên đới giữa các thuộc tính Các khái niệm  Tập vấn tin người dùng (ứng dụng): Q=(qi..q);  Quan hệ R(Ai..n)  Giá trị sử dụng thuộc tính của qi với Aj: use(qi,Aj)=0/1 46 Phân mãnh dọc 07/05/14 24 Xét quan hệ:  PROJ(Pno, pname,budget,loc)  q1: Select budget from PROJ where pno=value  q2: Select pname,budget from PROJ  q3: Select pname from PROJ where loc =value  q4: Select sum(budget) from PROJ where loc=value  Đặt: PROJ(A1,A2,A3,A4) 47 Phân mãnh dọc Ma trận sử dụng thuộc tính: 48 Phân mãnh dọc 07/05/14 25 Tập các ứng dụng q của Q  Q(A,B) = {q € Q: use(q,A)=use(q,B)=1} Số đo lực hút/ái lực giữa Ai, Aj của R với Q: Trong đó:  refl(q): số truy xuất đến thuộc tính (Ai,Aj) cho mỗi ứng dụng q tại vị trí Rl  Accl(q): số đo tần số truy xuất q đến Ai,Aj tại vị trí l. 49 Phân mãnh dọc Kiểm tra Cho các quan hệ toàn cục:  NV(MaNV, Hoten, MaNQL, Phong, Luong, Diachi)  DA(MaDA, TenDA, Diadiem, KP)  Phancong(MaNV,MaDA) Các quan hệ được phân đoạn như sau: 50 07/05/14 26 Kiểm tra  NV1(MaNV, Hoten,MaNQL, Diachi, Phong): Gồm các nhân viên có lương 5tr. USD trở lên  NV2(MaNV, Hoten,MaNQL, Diachi, Phong): Gồm các nhân viên có lương dưới 5tr. USD  NV3(MaNV, Hoten, Lương): Gồm các nhân viên có lương 5tr. USD trở lên  NV4(MaNV, Hoten, Lương): Gồm các nhân viên có lương dưới 5tr. USD  DA1: Danh sách dự án ở TP.HCM có KP từ 1 tỉ trở lên;  DA2: Danh sách dự án ở TP.HCM có KP dưới 1 tỉ;  DA3: Danh sách dự án ở các tỉnh thành khác có KP từ 500 tr. trở lên;  DA4: Danh sách dự án ở các tỉnh thành khác có KP dưới 500 tr;  Quan hệ Phân công được phân mãnh theo Dự án. 51 Kiểm tra Vì một nguyên nhân giả định, nhân viên có MaNV NV01005 vi phạm kỷ luật. Quyết định phạt hành chính được thành lập trừ lương mỗi tháng 2tr., thuyên chuyển công tác nhân viên này về làm bảo vệ ở dự án Đồng Nai và rút kinh phí ở dự án nhân viên này đang công tác 100tr. đồng đưa vào ngân sách cty. Viết truy vấn xử lý trường hợp trên (mức trong suốt định vị dữ liệu). 52 07/05/14 27 53