Thiết kế cơ sở dữ liệu phân tán - Hồ Bảo Quốc

Thiết kế cơ sở dữ liệu phân tán TS. Hồ Bảo Quốc Nội dung • Chiến lược phân tán • Các yêu cầu của thiết kế phân tán • Phân mảnh • Cấp phát dữ liệu • Thiết kế DDB trên ORACLE Vấn đề • Đối với một hệ phân tán tổng quát Phải quyết định vị trí phân bố dữ liệu và chương trình trên các máy trên hệ thống mạng cũng như có thể phải thiết kế cả hệ thống mạng • Đối với một HQTCSDL phân tán – Nơi đặt HQTCSDL phân tán – Nơi đặt các ứng dụng chạy trên CSDL Trục tham chiếu Chiến lược phân tán • Từ trên xuống (Top down) – Xuất phát từ một lược đồ toàn cục để xây dựng các lược đồ cục bộ – Hệ thống thuần chủng • Từ dưới lên (Bottom – up) – Tích hợp các lược đồ cục bộ đã có sẳn – Hệ thống đa chủng Thiết kế từ trên xuống Các yêu cầu của thiết kế phân tán • Tại sao phải phân mảnh ? • Phân mảnh như thế nào ? • Bao nhiêu mảnh sẽ phải phân ? • Làm sao kiểm tra tính đúng đắn ? • Phân bố các mảnh như thế nào ? • Các yêu cầu thông tin ra sao ? Phân mảnh • Chúng ta không thể chỉ phân tán các quan hệ !!! • Đơn vị phân mảnh sẽ như thế nào là hợp lý ? – Quan hệ ? • Truy xuất thường trên các khung nhìn (view) : chỉ là tập con của quan hệ • Đòi hỏi nhiều xử lý – Các phân mảnh của quan hệ • Cho phép xử lý đồng thời trên các mảnh của một quan hệ • Cho phép truy vấn tin song hành • Một khung nhìn được định nghĩa trên nhiều mảnh => đòi hỏi nhiều xử lý • Khó kiểm sóat dữ liệu ngữ nghĩa (semantic data control) Một ví dụ về phân mảnh ngang Một ví dụ về phân mảnh dọc Cấp độ phân mảnh Tính đúng đắn của phân mảnh • Tính đầy đủ – Một LDQH R được phân ră thành n lược đồ con R1, R2,…Rn là đầy đủ nếu và chỉ nếu mỗi yếu tố dữ liệu trên R đều có thể tìm thấy trong một vài Ri • Tính tái thiết được – Nếu một LDQH R được phân mảnh thành n lược đồ con R1,R2,…,Rn thì phải tồn tại một phép toán quan hệ ∆ sao cho R = ∆ Ri Ri, i=1..n • Tính tách biệt – Nếu một LDQH R được phân ră thành n lược đồ con R1,,R2,…Rn và một mục dữ liệu di trong Rj, thì nó sẽ không nằm trong Rk nào khác (k=1..n và k≠j) Các giải pháp phân bổ • Không nhân bản – CSDL được phân hoặch : mỗi mảnh được phân bổ trên mỗi vị trí khác nhau • Có nhân bản – Nhân bản toàn bộ : mỗi mảnh được phân bổ lên tất cả các vị trí – Nhân bản một phần : mỗi mảnh chỉ được phân bổ lên vài vị trí • Nguyên tắc chủ đạo – Nếu truy vấn chỉ đọc > truy vấn cập nhật thì việc nhân bản là thuận lợi ngược lại thì nhân bản có thể gây nên nhiều vấn đề Các yếu tố thông tin cần thiết • Thông tin về có sở dữ liệu • Thông tin về các ứng dụng • Thông tin về mạng truyền thông • Thông tin về hệ thống máy Các lọai phân mảnh • Phân mảnh ngang – Phân mảnh ngang nguyên thủy – Phân mảnh ngang dẫn xuất • Phân mảnh dọc • Phân mảnh tổ hợp Phân mảnh ngang nguyên thủy Các thông tin cần thiết • Thông tin về các ứng dụng – Vị từ đơn giản (predicate simple): cho một LDQH R(A1,A2,…,An), một vị từ đơn giản pj là một biểu thúc luận lý Pj : Ai  giá trị ở đây  = {=,,≥,≠}, giá trị  Dom(Ai) Với một R, chúng ta định nghĩa Pr ={p1,p2,…,pm} Ví dụ : JNAME =« Maintenance » BUDGET< 200000 – Vị từ hội sơ cấp (minterm predicate) là hội (conjunction) của các vị từ đơn giản định nghĩa M={m1,m2,…,mz} như sau : Các thông tin cần thiết (tt.) • Điều kiện của một câu truy vấn có thể được biểu diễn dưới dạng chuẩn hội (conjunctive normal form) của các vị từ hội sơ cấp E=  mi Không mất tính tổng quát chúng ta sẽ làm việc với các vị từ sơ cấp Vấn đề là làm sao xác định được một tập các vị từ đơn giản đầy đủ và tối thiểu Các thông tin cần thiết (tt.) Ví dụ : với Pr gồm 2 vị từ hội đơn giản JNAME =« Maintenance »;BUDGET≤ 200000 chúng ta có các vị từ hội sơ cấp sau : Các thông tin cần thiết (tt.) • Thông tin về cơ sở dữ liệu – Các mối liên hệ (relationships) – Lực lượng của quan hệ card(R) Vi dụ Các thông tin cần thiết (tt.) • Thông tin về các ứng dụng – Độ tuyển hội sơ cấp (minterm selectivity) kh. sel(mi) : số bộ của quan hệ được truy xuất theo một câu truy vấn của người dùng được đặc tả theo vị từ hội sơ cấp mi – Tần số truy xất (access frequency) kh. Acc(qi): tần số mà một ứng dụng qi truy xuất dữ liệu Phân mảnh ngang nguyên thủy • Định nghĩa Rj = R: Fj 1≤j≤m ở đây Fj là một công thức chọn (là một vị từ hội sơ cấp mi) – Như vậy một phân mảnh Rj là các bộ của R thỏa vị từ hội sơ cấp mi – Cho trước một tập các vị từ hội sơ cấp M, số phân mảnh ngang bằng số lượng vị từ hội sơ cấp => tập phân mảnh ngang này được gọi là tập các phân mảnh ngang sơ cấp Thuật toán • Input : một quan hệ R, tập các vị từ đơn giản Pr • Output : Một tập phân mảnh của R={R1,R2,…Rn} thỏa hai tính chất – Đầy đủ – Tối thiểu Tính đầy đủ • Một tập các vị từ đơn giản Pr là đầy đủ, nếu và chỉ nếu, xác suất truy xuất của mơi ứng dụng đến một bộ bất kỳ của một phân mảnh ngang cơ sở bất kỳ là như nhau • Ví dụ: – Giả sử J[JNO,JNAME,BUDGET,LOC] có hai ứng dụng được định nghĩa trên nó: (1). Tìm thông tin về BUDGET tại mỗi vị trí (LOC) (2). Tìm các dự án có BUDGET nhỏ hơn 200000 Tính đầy đủ • Theo (1) Sẽ là không đầy đủ theo (2) Nếu thay đổi Pr như sau Thì Pr bây giờ là đầy đủ Tính tối thiểu • Một vị từ đơn là liên quan (relevant) đến một hành động phân mảnh nếu nó phân mảnh f thành hai mảnh fi, fj và có ít nhất một ứng dụng truy xuất đến các mảnh fi,fj khác nhau • Nếu tất cả các vị từ đơn trong Pr điều liên quan đến các hành động phân mảnh thì Pr được gọi là tối thiểu • Ví dụ: là tối thiểu nhưng nếu chúng ta thêm vào thì sẽ không còn tối thiểu Thuật tóan COM_MIN • Input : Một quan hệ R, và tập các vị từ đơn Pr • Output :Một tập Pr’ đầy đủ và tối thiểu của Pr • Qui tắc 1 : Một quan hệ hoặc một phân mảnh đựoc phân hoặch thành ít nhất hai phần được truy xuất khác nhau bởi một ứng dụng Thuật toán COM_MIN 1. Khởi tạo – Tìm một Pi Pr sao cho Pi phân hoặch R theo qui tắc 1 – Pr’=pi; Pr= Pr-pi; F = fi 2. Lặp và thêm vị từ vào Pr’ cho đến khi nó đầy đủ 1. Tìm một pj  Pr sao cho pj phân hoặch một mảnh fk của Pr’ theo qui tắc 1 2. Pr’=Pr’pj;Pr=Pr – pj; F=FFj 3. Nếu  pk  Pr’, là mmột vị từ không liên quan thì Pr’ = Pr’ –pk; F = F – pk Giải thuật phân mảnh ngang • Sử dụng thuật tóan COM_MIN để phân rã • Input : một quan hệ R, một tập các vị từ đơn giản Pr • Output : Một tập các vị từ sơ cấp M theo đó quan hệ R được phân rã 1. Pr’ nhận đựoc từ thuật tóan COM_MIN 2. Xác định tập M của các vị từ cơ sở 3. Xác định tập I các suy diễn giữa các pk  Pr 4. Lọai bỏ các vị từ cơ sở mâu thuẩn trong M Ví dụ • Hai quan hệ cần phân mảnh : S và J • Phân mảnh quan hệ S – Ứng dụng : kiểm tra mức lương và tăng lương – Các mẩu tin về nhân viên đựoc lưu trử ở hai vị trí => ứng dụng sẽ được thực thi ở hai nơi – Các vị từ đơn giản – Pr={p1,p2} là đầy đủ và tối thiểu : Pr’=Pr – Các vị từ cơ sở Ví dụ • Phân mảnh quan hệ S (tiếp theo) – Các suy diễn – M1 mâu thuẩu vơi i1, m4 là mâu thuẩn với i2 • Phân mảnh quan hệ J – Ứng dụng : • Tìm tên và BUDGET của một dự án theo mă số (JNO) : ứng dụng được thực thi trên 3 vị trí • Truy xuất thông tin dự án thông qua BUDGET : mmọt vị trí lưu giữ các dự án có BUDGET≤ 200000 và một vị trí khác lưu giữ các dự án có BUDGET>200000 – Các vị từ đơn giản • Cho ứng dụng 1 • Cho ứng dụng 2 – Pr’=Pr={p1,p2,p3,p4,p5} • Phân mảnh quan hệ J (tiếp theo) Phân mảnh cơ sở sau khi loại bỏ các mâu thuẩn Tính đúng đắn • Tính đầy đủ Bởi vì Pr’ là đầy đủ và tối thiểu nên các vị từ được chọn là đầy đủ • Tính tái thiết Nếu quan hệ R được phân mảnh FR={R1,R2,…,Rn} thì • Tính tách biệt Ví các vị từ hội cơ sở có tính lọai trừ tương hỗ (mutually exclusive) Phân mảnh ngang dẫn xuất Phân mảnh ngang dẫn xuất • Được định nghĩa trên quan hệ thành viên theo một pháp chọn trên quan hệ chủ của một mối liên kết – Mỗi liên kết là một phép kết bằng (equijoin) – Một phép kết bằng có thể cà đặt theo nghĩa của một phép kết nửa (semi-join) Định nghĩa • Cho một liên kết L, Owner(L)=S và Member(L)=R. Phân mảnh ngang dẫn xuất của R được định nghĩa như sau : ở đây w là số mảnh sẽ có của R ở đay Fi là là công thức mà đã sinh ra phân mảnh Si Ví dụ • Xét liên kết L có Owner(L)=S và Member(L)=E ở đây Tính đúng đắn • Tính đầy đủ (được bảo đảm do) – Ràng buộc toàn vẹn tham chiếu • Tính tái thiết được – Như đối với phân mảnh ngang nguyên thủy • Tính tách rời – Do cách mảnh của quan hệ chủ là tách rời Phân mảnh dọc Phân mảnh dọc • Đã được nghiên cứu trong môi trường tập trung – Phương pháp thiết kế – Phân nhóm vật lý • Trên môi trường phân tán : khó hơn so với phân mảnh ngang, do có nhiều giải pháp chọn lựa – Có hai cách tiếp cận • Gom nhóm các thuộc tính : giả sử mỗi phân mảnh là một thuộc tích => gom nhóm để có phân mảnh lớn hơn • Tách thuộc tính : đi từ quan hệ để tách các nhóm thuộc tính có tính liên kết cao Phân mảnh dọc (tt.) • Gom nhóm các thuộc tính Các phân mảnh giao nhau  Tách thuộc tính  Các phân mảnh không giao nhau  Phù hợp với thiết kế từ trên xuống  Chúng ta không xem việc các mảnh có chứa khóa của quan hệ ban đầu là giao nhau Các thông tin cần thiết • Thông tin về ứng dụng – Độ liên kết của thuộc tính (attribute affinities) : • Đo độ liên kết của một thuộc tính với các thuộc tính khác – Giá trị sử dụng của thuộc tính (attribute usage value) • Cho một tập các câu truy vấn Q={Q1,Q2,…,Qm} thực hiện trên một quan hệ R(A1,A2,…,An), chúng ta định nghĩa • Chúng ta cũng định nghĩa vector use(qi,) Độ đo liên kết thuộc tính • Độ đo liên kết thuộc tính giữa hai thuộc tính Ai, Aj của quan hệ R(A1,A2,…,An) với một tập hợp các câu truy vấn Q(Q1,Q2,…,Qm) được định nghĩa như sau Định nghĩa use(qi,Aj) • Cho 4 quan hệ sau : Cho A1=JNO, A2=JNAME, A3=BUDGET, A4=LOC Ví dụ • Giả sử mỗi câu truy vấn trong ví dụ trước truy xuất các thuộc tính một lần trong mỗi lần thực hiện • Giả sử tần xuất truy xuất thì và ma trận độ đo liên kết Giải thuật phân nhóm • Từ ma trận độ đo liên kết thuộc tính AA, tìm giải pháp sắp xếp lại các thuộc tính để nhận được các nhóm thuộc tính có độ đo liên kết cao hơn độ liên kết với các thuộc tính của nhóm khác • Thuật tóan năng lượng liên kết BEA (Bond energy algorithm) được sử dụng để phân nhóm các thực thể sao cho độ đo liên kết tổng thể là cao nhất Thuật toán BEA • Input : ma trận liên kết thuộc tính AA • Output : một ma trận liên kết CA đã phân nhóm 1. Khởi tạo : đặt và cố định một cột của AA vào ma trận CA 2. Lặp: đặt n-i cột còn lại vào i+1 vị trí còn lại của CA, sao cho nó đóng góp lớn nhất vào đọ đo liên kết toàn cục 3. Thứ tự của dòng : theo thứ tự cột Thế nào là vị trí tốt nhất • Vị trí nào là tốt nhất ? Định nghĩa sự đóng góp của một vị trí • ở đây Ví dụ: • Xét ma trận CA như sau, trong đó 2 cột A1, A2 đã được đặt, chọn vị trí đặt cho A3 • Nếu đặt (0-3-1) • Nếu đặt (1-3-2) • Nếu đặt (2-3-4) Ví dụ • Bởi vậy, vị trí được chọn là Ví dụ • Sau khi A4 được đặt, chúng ta có CA như sau Thuật tóan phân mảnh dọc • Làm thế nào chúng ta có thể chia một tập thuộc tính đã gom nhóm A1,A2,…,An thành hai (hay nhiều) tập {A1,…,Ai} và {Ai,...,An} sao cho không có (hoặc ít nhất) cácưứng dụng truy xuất cả hai tập này Thuật toán • Định nghĩa – TQ : tập các ứng dụng chỉ truy xuất TA – BQ : tập các ứng dụng chỉ truy xuất BA – OQ : tập các ứng dụng truy xuất cả hai TA và BA Và – CTQ : tổng số truy xuất đến các thuộc tính của các ưng dụng chỉ truy xuất TA – CBQ : tổng số truy xuất đến các thuộc tính của các ứng dụng chỉ truy xuất BA – COQ : tổng số truy xuất đén các thuộc tính của các ứng dụng truy xuẩt cả hai TA và BA Vấn đề : Tìm một điểm trên đường chéo sao cho biểu thức sao lơn nhất Thuật tóan Hai vấn đề 1. Phân nhóm tiến hành từ giửa ma trận CA 1. Dời một dòng lên và một cột sang trái và áp dụng thuật toán tìm điểm phân hoặch tốt nhất 2. Thực hiện việc này cho tất cả các hagnh động dời có thể 3. Chi phí 2. Phân ra nhiều hơn hai nhóm 1. Phân hoặch m mảnh 2. Thử 1,2,…m-1 điểm phân hoặch, để tìm ra điểm phân hoặch tốt nhất 3. Chi phí Tính đúng đắn Một quan hệ R trên tập thuộc tính A và khóa K,có các phân mảnh dọc FR={R1,…,Rz} 1. Tính đầy đủ 2. Tính tái thiết được 3. Tính tách biệt Phân mảnh hổn hợp Ví dụ Cấp phát phân mảnh • Vấn đề Cho F={F1,..,Fm} các phân mảnh S={S1,…,Sn} các vị trí (node) Q={q1,…,qs} các ứng dụng Tìm một phân bổ tối ưu các Fi trên các Sj • Yếu tố tối ưu – Chi phí thấp nhất • Truyền thông + lưu trữ + xử ký • Chi phí về thời gian đáp ứng – Hiệu suất • Thời gian đáp ứng – Các ràng buộc • Ràng buộc trên mỗi vị trí (lưu trử + xử lý) Các giải pháp cấp phát • Cấp phát tập tin (File Allocation) vs Cấp phát cơ sở dữ liệu (Database Allocation) – Các phân mảnh không phải là các tập tin riêng rẽ : các mối liên hệ phải được quan tâm – Truy cập cơ sở dữ liệu thì phức tạp hơn – Chi phí bảo đảm ràng buộc tòabn vẹn phải được tính đến – Chi phí quản lý truy xuất đồng thời Các thông tin cần thiết • Thông tin về cơ sở dữ liệu – Tần suất chọn các phân mảnh – Kích thước của phân mảnh • Thông tin về ứng dụng – Số truy xuất chỉ đọc của một câu truy vấn đến một phân mảnh – Số truy xuất cập nhật của một câu truy vấn đến một phân mảnh – Một ma trận chỉ ra câu truy vấn nào sẽ thao tác trên mảnh nào – Vị trí kích họat của các câu truy vấn • Thông tin về vị trí – Đơn gia xử lý – Đơn giá lưu trữ • Thông tin về mạng – Chí phí truyền giữa hai vị trí – Kích thước của một đơn vị truyền Mô hình cấp pháp • Dạng tổng quát Min(tổng chi phí) ràng buộc 1. thời gian đáp ứng 2. lưu trử 3. xử lý Mô hình cấp phát • Tổng chi phí • Chi phí lưu trữ • Chi phí xử lý câu truy vấn