Bài giảng cơ sở dữ liệu - Bài 3: Thiết kế cơ sở dữ liệu phân tán - Đỗ Phúc

Distributed DBMS Page 5. 1 Thiết kế CSDL phân tán PGS.TS. Đỗ Phúc Khoa Hệ thống thông tin Trường Đại học Công nghệ thông tin, ĐHQG-HCM Distributed DBMS Page 5. 2 Bài toán thiết kế  Nguyên tắc chung: Quyết định bố trí dữ liệu và chương trình trên các vị trí của mạng máy tính cũng như thiết kế bản thân mạng.  Trong Hệ QTCSDLPT, việc bố trí ứng dụng bao gồm:  Bố trí phần mềm Hệ QTCSDLPT; và  Bố trí các ứng dụng chạy trên CSDL. Distributed DBMS Page 5. 3 Các khía cạnh của bài toán Level of sharing Level of knowledge Access pattern behavior partial information dynamic static data data + program complete information Distributed DBMS Page 5. 4 Thiết kế phân tán  Từ trên xuống (Top-down)  Thiết kế hệ thống từ đầu  Các hệ thống đồng chất (homogeneous systems)  Từ dưới lên (Bottom-up)  Khi đã có CSDL ở một số vị trí Distributed DBMS Page 5. 5 Thiết kế từ trên xuống User Input View Integration User Input Requirements Analysis Objectives Conceptual Design View Design Access Information ES’sGCS Distribution Design Physical Design LCS’s LIS’s GCS: Global conceptual schema ES:External Schema LCS:Local conceptual schema Distributed DBMS Page 5. 6 Các vấn đề của thiết kế phân tán Tại sao phải phân mảnh dữ liệu? Cách phân mảnh? Mức độ phân mảnh? Cách kiểm tra tính đúng đắn? Cách cấp phát? Các thông tin cần thiết? Distributed DBMS Page 5. 7 Phân mảnh dữ liệu  Chỉ để phân tán các quan hệ?  Đơn vị phân tán nào là hợp lý?  Quan hệ  views là tập con của quan hệ -> cục bộ  Cần truyền thông ( qua mạng) nhiều hơn- nếu quan hệ được lưu ở nơi khác với vị trí khởi động truy vấn  Các phân mảnh của quan hệ (quan hệ con)-thích hợp  Thực hiện đồng thời một số giao tác nhằm truy cập các phần khác nhau của quan hệ  Views không được định nghĩa trên một mảnh duy nhất sẽ yêu cầu nhiều xử lý.  Kiểm soát dữ liệu ngữ nghĩa (đặc biệt là ép thỏa toàn vẹn) là điều khó khăn Distributed DBMS Page 5. 8 PROJ1 : các projects có kinh phí nhỏ hơn $200,000 PROJ2 : các projects có kinh phí lớn hơn hay bằng $200,000 PROJ1 PNO PNAME BUDGET LOC P3 CAD/CAM 250000 New York P4 Maintenance 310000 Paris P5 CAD/CAM 500000 Boston PNO PNAME LOC P1 Instrumentation 150000 Montreal P2 Database Develop. 135000 New York BUDGET PROJ2 Các kiểu phân mảnh– ngang New York New York PROJ PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal P3 CAD/CAM 250000 P2 Database Develop. 135000 P4 Maintenance 310000 Paris P5 CAD/CAM 500000 Boston e ork Distributed DBMS Page 5. 9 Các kiểu phân mảnh– dọc PROJ1: thông tin về kinh phí của đề án PROJ2: thông tin về tên và vị trí của đề án PNO BUDGET P1 150000 P3 250000 P2 135000 P4 310000 P5 500000 PNO PNAME LOC P1 Instrumentation Montreal P3 CAD/CAM New York P2 Database Develop. New York P4 Maintenance Paris P5 CAD/CAM Boston PROJ1 PROJ2 New York New York PROJ PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal P3 CAD/CAM 250000 P2 Database Develop. 135000 P4 Maintenance 310000 Paris P5 CAD/CAM 500000 Boston e ork Distributed DBMS Page 5. 10 Mức độ phân mảnh Phân mảnh đến mức độ nào sẽ quyết định đến hiệu năng truy vấn Tìm mức độ thích hợp để phân hoạch trong phạm vi Bộ hay Thuộc tính Phân mảnh (ngang, dọc) Quan hệ (không phân mảnh) Số hữu hạn các kiểu Distributed DBMS Page 5. 11  Tính đầy đủ (completeness)  Phân rã quan hệ R thành các mảnh R1, R2, ..., Rn là đầy đủ nếu và chỉ nếu mỗi mục dữ liệu trong R đều có thể tìm thấy trong quan hệ Ri nào đó.  Tính tái tạo (reconstruction)  Nếu quan hệ R được phân rã thành các mảnh R1, R2, ..., Rn, thì sẽ tồn tại một toán tử quan hệ  sao cho: R = 1≤i≤nRi  Tính rời nhau (disjointness)  Nếu quan hệ R được phân rã thành các mảnh R1, R2, ..., Rn, và mục dữ liệu di thuộc về Rj, thì di không thuộc về bất kỳ mảng nào khác Rk (k ≠ j ). Tính đúng đắn trong phân mảnh Distributed DBMS Page 5. 12 Các cách cấp phát  Không nhân bản (non-replicated)  Phân hoạch: mỗi mảnh nằm trên một vị trí, đây là bản sao duy nhất của một mảnh trên mạng.  Nhân bản (replicated)  Nhân bản đầy đủ: một mảnh ở một vị trí ( full replication), toàn bộ CSDL đều tồn tại ở từng vị trí.  Nhân bản từng phần: mỗi mảnh ở vài vị trí ( partial replication)  Quy tắc: If thì nên nhân bản , otherwise nhân bản có thể phát sinh vấn đề read - only queries update queries 1 Distributed DBMS Page 5. 13 So sánh các kiểu nhân bản Full-replication Partial-replication Partitioning QUERY PROCESSING Easy Same Difficulty Same DifficultyDIRECTORY MANAGEMENT Easy or Non-existant CONCURRENCY CONTROL EasyDifficultModerate RELIABILITY Very high High Low REALITY Possible application Realistic Possible application Distributed DBMS Page 5. 14  Có 4 nhóm:  thông tin về CSDL  thông tin về ứng dụng  Thông tin về mạng truyền thông  Thông tin về hệ thống máy tính Các yêu cầu về thông tin Distributed DBMS Page 5. 15  Phân mảnh ngang (HF)  Phân mảnh ngang nguyên thủy (PHF)  Phân mảnh ngang được suy(DHF)  Phân mảnh dọc (VF)  Phân mảnh hỗn hợp (HF) Phân mảnh Distributed DBMS Page 5. 16  Thông tin về CDSL  Quan hệ  Lực lượng của từng quan hệ: card(R) Phân mảnh ngang nguyên thủy PHF – yêu cầu thông tin TITLE, SAL SKILL ENO, ENAME, TITLE PNO, PNAME, BUDGET, LOC ENO, PNO, RESP, DUR EMP PROJ ASG L 1 L 2 L 3 Với link L1 Owner(L1)=SKILL Member(L1)=EMP Quan hệ nằm tại đuôi của link là owner và qhệ nằm tại đầu (có mũi tên) của link là member Distributed DBMS Page 5. 17  Thông tin về ứng dụng  simple predicates : Cho R[A1, A2, , An], vị từ đơn pj là pj : Ai Value với {=,,≥,≠}, ValueDi và Di là domain của Ai. Với quan hệ R, chúng ta định nghĩa Pr = {p1, p2, ,pm} Ví dụ: các vị từ đơn giản PNAME = "Maintenance" BUDGET ≤ 200000  minterm predicates : Cho R và Pr={p1, p2, ,pm} định nghĩa M={m1,m2,,mr} là M={ mi|mi = pjPrpj* }, 1≤j≤m, 1≤i≤z với pj* = pj hay pj* = ¬(pj). Phân mảnh ngang nguyên thủy PHF – Yêu cầu thông tin Distributed DBMS Page 5. 18 Ví dụ: minterm predicates m1: PNAME="Maintenance" BUDGET≤200000 m2: NOT(PNAME="Maintenance") BUDGET≤200000 m3: PNAME= "Maintenance" NOT(BUDGET≤200000) m4: NOT(PNAME="Maintenance") NOT(BUDGET≤200000) Phân mảnh ngang nguyên thủy PHF – Yêu cầu về thông tin Distributed DBMS Page 5. 19  Thông tin ứng dụng  Độ tuyển hội sơ cấp: minterm selectivities: sel(mi)  Số các bộ (tuple) của quan hệ được câu truy vấn truy cập. Câu truy vấn được chỉ định bằng minterm predicate mi.  Tần số truy cập: access frequencies: acc(qi)  Tần số truy cập dữ liệu của ứng dụng qi.  Cũng có thể xác định tần số truy cập cho minterm predicate. Phân mảnh ngang nguyên thủy PHF – yêu cầu về thông tin Distributed DBMS Page 5. 20 Định nghĩa : Rj = Fj(R ), 1 ≤ j ≤ w Với Fj là công thức chọn, thích hợp là minterm predicate. Do vậy, Phân mảnh ngang Ri của quan hệ R gồm tất cả các bộ của R thỏa minterm predicate mi.  Cho tập các minterm predicates M, có nhiều phân mảnh ngang của quan hệ R ứng với nhiều minterm predicates. Tập các phân mảng ngang cũng được gọi là minterm fragments. Phân mảnh ngang nguyên thủy Primary Horizontal Fragmentation Distributed DBMS Page 5. 21 Cho: Quan hệ R, tập các vị từ đơn Pr Kết quả: Tập các mảnh của R = {R1, R2,,Rw} thỏa quy tắc phân mảnh. Yêu cầu : Pr phải đầy đủ (complete) xem slide tiếp theo Pr phải tối tiểu (minimal) Phân mảnh ngang nguyên thủy PHF – Thuật toán Distributed DBMS Page 5. 22  Tập các simple predicates Pr được gọi là đầy đủ nếu và chỉ nếu các truy cập đến các bộ (tuple) của các mảnh hội tối thiểu (minterm fragments) được định nghĩa theo Pr phải thỏa yêu cầu với một ứng dụng bất kỳ, hai bộ của cùng một minterm fragment phải có cùng xác suất truy cập  Ví dụ : Cho PROJ[PNO,PNAME,BUDGET,LOC], trên quan hệ này có hai ứng dụng. Tìm các kinh phí của từng đề án tại từng vị trí. (1) Tìm các đề án có kinh phí nhỏ hơn $200000. (2) Tính đầy đủ của các Simple Predicates Distributed DBMS Page 5. 23 Theo (hình 5.8 trang 124 sách GK), Pr={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”} Là không đầy đủ vì ứng dụng (2). Xác suất truy vấn hai bộ P2,P3 là khác nhau trong mảnh PROJ2 Ta cần sửa đổi Pr ={LOC=“Montreal”,LOC=“New York”,LOC=“Paris”, BUDGET≤200000,BUDGET>200000} Thì Pr đầy đủ. Tính đầy đủ của các Simple Predicates Distributed DBMS Page 5. 24  Để một vị tự phát sinh phân mảnh, (vd, biến mảnh f thành các mảnh con fi và fj) thì cần phải có một ứng dụng truy cập fi và fj với các xác suất trên các bộ của mảnh đó là khác nhau. Nói cách khác, simple predicate phải liên ứng (relevant) với việc tạo ra phân mảnh.  Nếu tất cả các predicates của tập Pr đều có liên ứng thì Pr is tối tiểu (minimal). acc(mi) ––––– card(fi) acc(mj) ––––– card(fj) ≠ Tính tối tiểu của vị từ đơn acc(mi): tần số truy cập của ứng dụng Distributed DBMS Page 5. 25 Ví dụ : Pr ={LOC=“Montreal”,LOC=“New York”, LOC=“Paris”, BUDGET≤200000,BUDGET>200000} Là tối tiểu (ngoài ra nó còn đầy đủ). Tuy vậy, nếu thêm PNAME = “Instrumentation” Thì Pr không cực tiểu vì vị từ này không có liên ứng với Pr (không có ứng dụng nào truy cập khác nhau trên các mảnh được tạo ra). Tính cực tiểu của vị từ đơn Đầy đủ: xác suất truy cập các bộ giống nhau Tối tiểu: các vị từ đều có liên đới. Liên đới: có ứng dụng truy cập khác nhau trên các mảnh tạo ra. Distributed DBMS Page 5. 26 Cho: quan hệ R và tập các vị từ Pr Kết quả: Tập đầy đủ và tối tiểu các vị từ đơn Pr' cho Pr Quy tắc 1: Quan hệ hay mảnh được phân thành ít nhất là hai phần khác nhau và được ít nhất một ứng dụng truy cập các bộ với xác suất khác nhau. Thuật toán COM_MIN Distributed DBMS Page 5. 27 Khởi tạo :  Tìm pi Pr sao cho pi phân hoạch R theo quy tắc 1  Gọi Pr' = pi ; Pr Pr – pi ; F fi Lặp lại việc thêm các vị từ vào Pr' cho đến khi nó đầy đủ  Tìm pj Pr sao cho pj phân hoạch fk được định nghĩa theo minterm predicate trên Pr' theo quy tắc 1  Đặt Pr' = Pr'  pi ; Pr Pr – pi; F  F  fi  Nếu pk Pr' là không liên ứng thì Pr'  Pr' – pk F  F – fk Thuật toán COM_MIN Distributed DBMS Page 5. 28 Dùng COM_MIN để phân mảnh. Nhập: quan hệ R và tập các vị từ đơn Pr Xuất: tập các minterm predicates M ấn định cách phân mảnh quan hệ R.  Pr'  COM_MIN (R,Pr)  Xác định tập M các minterm predicates  Xác định tập I các phép kéo theo giữa các pi  Pr  Khử các minterms mâu thuẫn khỏi M Thuật toán PHORIZONTAL Distributed DBMS Page 5. 29  Cho các quan hệ ứng viên: PAY và PROJ.  Phân mảnh quan hệ PAY  Ứng dụng: Kiểm tra thông tin lương và quyết định tăng lương.  Các bản ghi của Nhân viên được lưu ở 2 vị trí  ứng dụng chạy ở 2 vị trí mỗi nơi xử lý các mẫu tin có lương thấp hơn hay bằng 30000 và một nơi khác xử lý các mẫu tin có lương cao hơn 30000.  Các vị từ đơn được dùng để phân hoạch quan hệ PAY là: p1 : SAL ≤ 30000 p2 : SAL > 30000 Thuật toán COM-MIT Pr={p1, p2} Với i = 1 , ta tìm được p1 thỏa quy tắc 1: phân quan hệ PAY thành 2 phần là phần thỏa SAL ≤ 30000 và phần không thỏa SAL ≤ 30000, hai phần này được truy cập khác nhau bởi ứng dụng. Phân mảnh ngang nguyên thủy PHF – Ví dụ (1/2) Distributed DBMS Page 5. 30 Phân mảnh ngang nguyên thủy PHF – Ví dụ (2/2) Pr‘ <- p1 Pr = {p2} F ={f1} , f1 là mảnh hội sơ cấp theo p1 Trong Pr còn p2 , nhưng p2 không thể phân hoạch mảnh f1 do đó Pr‘ = { p1 } là đầy đủ và tối thiểu  Các Minterm predicates m1 : (SAL ≤ 30000) m2 : NOT(SAL ≤ 30000)  (SAL > 30000) Distributed DBMS Page 5. 31 PHF – Ví dụ: phân mảnh ngang cho quan hệ PAY TITLE Mech. Eng. Programmer SAL 27000 24000 PAY1 PAY2 TITLE Elect. Eng. Syst. Anal. SAL 40000 34000 Distributed DBMS Page 5. 32  Các ứng dụng:  Tìm tên và kinh phí của các đề án theo vị trí -location (LOC) Được phát sinh ỏ 3 vị trí  Truy cập thông tin đề án theo kinh phí ( budget ) Một ví trí truy cập ≤ 200000, vị trí khác truy cập >200000  Các vị từ đơn  Cho ứng dụng (1) p1 : LOC = “Montreal” p2 : LOC = “New York” p3 : LOC = “Paris”  Cho ứng dụng (2) p4 : BUDGET ≤ 200000 p5 : BUDGET > 200000 PHF – Ví dụ phân mảnh nganh quan hệ PROJ Distributed DBMS Page 5. 33  Dùng thuật toán COM-MIN ta có  Pr = Pr' = {p1,p2,p3,p4,p5}  Phân mảnh quan hệ PROJ tiếp theo  Minterm fragments còn lại sau khi khử m1 : (LOC = “Montreal”)  (BUDGET ≤ 200000) m2 : (LOC = “Montreal”)  (BUDGET > 200000) m3 : (LOC = “New York”)  (BUDGET ≤ 200000) m4 : (LOC = “New York”)  (BUDGET > 200000) m5 : (LOC = “Paris”)  (BUDGET ≤ 200000) m6 : (LOC = “Paris”)  (BUDGET > 200000) Phân mảnh ngang nguyên thủy PHF – Ví dụ Distributed DBMS Page 5. 34 Phân mảnh ngang nguyên thủy PHF – Ví dụ PROJ1 PNO PNAME BUDGET LOC PNO PNAME BUDGET LOC P1 Instrumentation 150000 Montreal P2 Database Develop. 135000 New York PROJ2 PROJ4 PROJ6 PNO PNAME BUDGET LOC P3 CAD/CAM 250000 New York PNO PNAME BUDGET LOC MaintenanceP4 310000 Paris Distributed DBMS Page 5. 35  Tình đầy đủ  Do Pr' là đầy đủ và tối tiểu, các vị từ chọn là đầy đủ  Tái tạo  Nếu quan hệ R được phân mảnh thành FR = {R1,R2,,Rr} R = Ri FR Ri  Rời nhau  Các minterm predicates làm cơ sở cho phân mảnh cần phải rời nhau từng đôi. Phân mảnh ngang nguyên thủy PHF – Tính đúng đắn Distributed DBMS Page 5. 36  Được xác định theo quan hệ member của link dựa trên phép chọn được chỉ định trên owner của nó .  Mỗi link là một equijoin.  Có thể hiện thực Equijoin bằng semijoins. Phân mảnh ngang được suy Derived Horizontal Fragmentation TITLE, SAL SKILL ENO, ENAME, TITLE PNO, PNAME, BUDGET, LOC ENO, PNO, RESP, DUR EMP PROJ ASG L1 L2 L3 Quan hệ nằm tại đuôi của link là owner và qhệ nằm tại đầu (có mũi tên) của link là member Member(L1)= EMP Distributed DBMS Page 5. 37 Chon link L với owner(L)=S và member(L)=R, các mảnh ngang được suy của R được định nghĩa như sau: Ri = R F Si, 1≤i≤w Với w là số lớn nhất các mảnh được xác định trên R và Si = Fi(S) , Si là các phân mảnh ngang của owner Với Fi là công thức theo đó xác định phân mảnh ngang nguyên thủy Si. Phân mảnh ngang được suy DHF – Định nghĩa Distributed DBMS Page 5. 38 Given link L1 where owner(L1)=SKILL and member(L1)=EMP EMP1 = EMP SKILL1 EMP2 = EMP SKILL2 where SKILL1 = SAL≤30000(SKILL) SKILL2 = SAL>30000(SKILL) Phân mảnh ngang được suy DHF – Ví dụ ENO ENAME TITLE E3 A. Lee Mech. Eng. E4 J. Miller Programmer E7 R. Davis Mech. Eng. EMP1 ENO ENAME TITLE E1 J. Doe Elect. Eng. E2 M. Smith Syst. Anal. E5 B. Casey Syst. Anal. EMP2 E6 L. Chu Elect. Eng. E8 J. Jones Syst. Anal. TITLE, SAL SKILL ENO, ENAME, TITLE EMP L1 Distributed DBMS Page 5. 39  Tính đầy đủ  Toàn vẹn tham chiếu  Cho R là quan hệ member của link có owner là quan hệ S được phân mảnh thành FS = {S1, S2, ..., Sn}. Ngoài ra gọi A là thuộc tính kết nối giữa R và S. Thì với từng bộ t của R, tồn tại bộ t' của S sao cho t[A]=t'[A]  Tái tạo  Giống phân mảnh ngang nguyên thủy.  Rời nhau  Chi có join graphs giữa owner và các member fragments. Phân mảnh ngang được suy DHF – Tính đúng đắn Distributed DBMS Page 5. 40 Phân mảnh dọc Vertical Fragmentation Distributed DBMS Page 5. 41  Đã được nghiên cứu trong ngữ cảnh tập trung  Phương pháp luận thiết kế ( bài ôn về PTH, thiết kế CSDL)  Gom cụm vật lý  Khó hơn phân mảnh ngang vì có nhiều cách. Hai tiếp cận:  nhóm  Các thuộc tính tới phân mảnh  tách  Quan hệ tới phân mảnh Phân mảnh dọc Vertical Fragmentation Distributed DBMS Page 5. 42  Các mảnh chồng nhau Overlapping fragments  Gom nhóm ( grouping )  Các mảnh không chồng nhau  Tách ( splitting ) Ta không xem xét các thuộc tính khóa được nhân bản là có chồng nhau. Tiện lợi: Dễ ép thỏa các Phụ thuộc hàm (kiểm tra ràng buộc...) Phân mảnh ngang Vertical Fragmentation Distributed DBMS Page 5. 43  Thông tin ứng dụng  Các ái lực thuộc tính (Attribute affinities)  Độ đo phản ánh các thuộc tính quan hệ gần nhau  Nhận được từ dữ liệu sử dụng ban đầu  Giá trị sử dụng thuộc tính (Attribute usage values)  Cho tập các truy vấn Q = {q1, q2,, qq} chạy trên quan hệ R[A1, A2,, An], use(qi,•) được định nghĩa tương ứng VF – Yêu cầu thông tin use(qi,Aj) = 1 nếu thuộc tính Aj được tham chiếu bới truy vấn qi 0 ngược lại   Distributed DBMS Page 5. 44 Xét 4 truy vấn cho quan hệ PROJ q1: SELECT BUDGET q2: SELECT PNAME,BUDGET FROM PROJ FROM PROJ WHERE PNO=Value q3: SELECT PNAME q4: SELECT SUM(BUDGET) FROM PROJ FROM PROJ WHERE LOC=Value WHERE LOC=Value Gọi A1= PNO, A2= PNAME, A3= BUDGET, A4= LOC VF – Định nghĩa use(qi,Aj) q1 q2 q3 q4 A1 1 0 1 0 0 01 1 0 01 1 0 0 1 1 A2 A3 A4 Distributed DBMS Page 5. 45 Độ đo ái lực thuộc tính giữa 2 thuộc tính Ai và Aj của quan hệ R[A1, A2, , An] ứng với tập quan hệ Q = (q1, q2, , qq) được định nghĩa như sau: VF – Độ đó ái lực aff(Ai,Aj) aff (Ai, Aj)  (query access)all queries that access Ai and Aj query access  access frequency of a query  access executionall sites Distributed DBMS Page 5. 46 Giả sử từng truy vấn trong ví dụ trước truy cập trong từng lần thực hiện. Giả định tần số truy cập Thì aff(A1, A3) = 15*1 + 20*1+10*1 = 45 ( dòng q1) Các ma trận ái lực thuộc tính AA is VF – tính aff(Ai, Aj) q1 q2 q3 q4 S 1 S 2 S 3 15 20 10 5 0 0 25 2525 3 0 0 A A A A1 2 3 4 A A A A 1 2 3 4 45 0 45 0 0 80 5 75 45 5 53 3 0 75 3 78 Distributed DBMS Page 5. 47  Lấy ma trận ái lực AA và tổ chức lại các thứ tự của thuộc tính để tạo các cụm có các thuộc tính ứng với cụm có độ ái lực cao hơn cụm khác  Thuật toán năng lượng liên kết - Bond Energy Algorithm (BEA) được dùng để gom cụm các thực thể. BEA tìm thứ tự các thực thể ( trong trường hợp này là các thuộc tính) sao cho độ đo ái lực toàn cục sau là cực đại. VF – Thuật toán gom cụm AM  (affinity of Ai and Aj with their neighbors) j  i  Distributed DBMS Page 5. 48 Nhập: Ma trận AA Xuất: Ma trận ái lực gom cụm CA là một sắp xếp của các hoán vị AA Khởi tạo: Đặt và cố định một trong các cột của AA vào CA. Lặp: Đặt n-i cột còn lại vào i+1 vị trí còn lại trong ma trận CA. Đối với từng cột, chọn vị trí đóng góp (contri bution) lớn nhất vào độ đo ái lực toàn cục. Sắp thứ tự dòng:Sắp xếp các dòng theo thứ tự cột. Thuật toán năng lượng liên kết Bond Energy Algorithm Distributed DBMS Page 5. 49 Vị trí “tốt nhất”? Xác định mức đóng góp của bố trí: cont(Ai, Ak, Aj) = 2bond(Ai, Ak)+2bond(Ak, Al) –2bond(Ai, Aj) Với Thuật toán năng lượng liên kết Bond Energy Algorithm bond(Ax,Ay) = aff(Az,Ax)aff(Az,Ay) z 1 n  Distributed DBMS Page 5. 50 Xét ma trận AA và ma trận tương ứng CA sau đây với A1 và A2 đã được đặt. Đặt A3: Thứ tự (0-3-1) : cont(A0,A3,A1) = 2bond(A0 , A3)+2bond(A3 , A1)–2bond(A0 , A1) = 2* 0 + 2* 4410 – 2*0 = 8820 Thứ tự (1-3-2) : cont(A1,A3,A2) = 2bond(A1 , A3)+2bond(A3 , A2)–2bond(A1,A2) = 2* 4410 + 2* 890 – 2*225 = 10150 Thứ tự (2-3-4) : cont (A2,A3,A4) = 1780 A A A A1 2 3 4 A A A A 1 2 3 4 45 0 5 0 0 80 5 75 45 5 53 3 0 75 3 78 AA = A A1 2 45 0 0 80 45 5 0 75 CA= BEA – Ví dụ Distributed DBMS Page 5. 51 Do vậy ma trận CA có dạng BEA – Ví dụ A1 A2A3 45 0 45 0 45 5 53 3 0 80 5 75 Distributed DBMS Page 5. 52 Sau khi đặt A4, dạng cuối cùng của ma trận CA (sau khi tổ chức dòng) là BEA – Ví dụ A AA A1 23 4 A A A A 1 2 3 4 45 45 0 0 45 53 5 3 0 5 80 75 0 3 75 78 Distributed DBMS Page 5. 53 Cách chia tập các thuộc tính gom cụm {A1, A2, , An} thành hai (hay nhiều hơn) các tập {A1, A2, , Ai} và {Ai, , An} sao cho không có (hay có tối thiểu) các ứng dụng truy cập cả hai (hay nhiều hơn một) của các tập hợp. VF – Thuật toán A1 A2 Ai Ai+1 Am A1 A2 A3 Ai Ai+1 Am BA . . . TA Distributed DBMS Page 5. 54 Định nghĩa TQ = tập các ứng dụng chỉ truy cập TA BQ = tập các ứng dụng chỉ truy cập BA OQ = tập các ứng dụng chỉ truy cập vừa TA và BA và CTQ = tổng số các truy cập đến các thuộc tính bởi các ứng dụng chỉ truy cập TA CBQ = tổng số các truy cập đến thuộc tính bởi ứng dụng chỉ truy cập BA COQ = tổng số các truy cập đến thuộc tính bởi ứng dụng truy cập cả TA và BA Sau đó tìm điểm dọc theo đường chéo làm cực đại VF – Algorithm CTQCBQCOQ2 Distributed DBMS Page 5. 55 Có hai vấn đề:  Tạo Cluster ở điểm giữa ma trận CA  Dịch lên một dòng và dịch trái một cột, áp dụng thuật toán tìm điểm phân hoạch tốt nhất  Làm điều này cho tất cả các dịch chuyển khả dĩ  Chi phí O(m2)  Nhiều hơn 2 clusters  Phân hoạch theo m-cách  Thử với 1, 2, , m–1 điểm tách dọc theo đường chéo và tìm điểm tốt nhất cho từng điểm  Chi phí O(2m) VF – Algorithm Distributed DBMS Page 5. 56 A relation R, defined over attribute set A and key K, generates the vertical partitioning FR = {R1, R2, , Rr}.  Completeness  The following should be true for A: A = ARi  Reconstruction  Reconstruction can be achieved by R = K Ri Ri FR  Disjointness  TID's are not considered to be overlapping since they are maintained by the system  Duplicated keys are not considered to be overlapping VF – Correctness Distributed DBMS Page 5. 57 Phân mảnh hỗn hợp Hybrid Fragmentation R HFHF R1 VF VFVFVFVF R11 R12 R21 R22 R23 R2     Distributed DBMS Page 5. 58 Bố trí phân mảnh theo các vị trí  Phát biểu bài toán Cho : F = {F1, F2, , Fn} mảnh S ={S1, S2, , Sm} các vị trí trên mạng Q = {q1, q2,, qq} ứng dụng, truy vấn Tìm phân bố “tối ưu” của F trên S.  Tối ưu  Chi phí cực tiểu  Truyền thông + bộ nhớ + xử lý ( đọc & cập nhật)  Chi phí theo thời gian (thông thường)  Công năng Thời gian đáp ứng và/hay kết quả  Ràng buộc  Ràng buộc trên từng vị trí (bộ nhớ & xử lý) Distributed DBMS Page 5. 59 Yêu cầu thông tin  Thông tin về CSDL  Sựa lựa chọn các bộ truy vấn của các mảnh  Kích thước của mảnh  Thông tin về ứng dụng  Kiểu truy cập và số truy cập  Tính cục bộ của truy cập  Thông tin về mạng truyền thông  Đơn giá lưu trữ dữ liệu tại vị trí  Đơn giá xử lý tại một vị trí  Thông tin về hệ thống máy tính  Băng thông  latency  Tổn phí truyền thông Distributed DBMS Page 5. 60 Cấp phát tập tin(FAP) so với cấp phát CSDL (DAP):  Các phân mảnh không phải là các tập tin riêng rẻ  Cần duy trì các mối quan hệ  Truy cập đến CSDL thường phức tạp hơn  Không thể áp dụng mô hình truy cập tập tin từ xa  Mối quan hệ giữa cấp phát và xử lý truy vấn  Cần xem xét việc ép thỏa ràng buộc toàn vẹn  Cần xem xét kiểm soát đồng hành Cấp phát Distributed DBMS Page 5. 61 Yêu cầu thông tin  Thông tin về CSDL  Sựa lựa chọn các bộ truy vấn của các mảnh  Kích thước của mảnh  Thông tin về ứng dụng  Số các truy cập đọc của truy vấn đến một mảnh  Số các truy cập cập nhật của truy vấn đến một mảnh  Ma trận biểu thị các truy vấn cập nhật mảnh  Ma trận tương tự để đọc  Vị trí nguyên thủy của từng truy vấn  Thông tin vị trí  Đơn giá lưu trữ dữ liệu tại vị trí  Đơn giá xử lý tại vị trí  Thông tin về mạng  Chi phí truyền thông/khung sườn (frame) giữa 2 vị trí  Kich thước khung sườn Distributed DBMS Page 5. 62 Dạng tổng quát min(Total Cost) thỏa mãn ràng buộc về thời gian đáp ứng ràng buộc về bộ nhớ ràng buộc xử lý Biến quyết định Mô hình cấp phát xij  1 nếu mảnh Fi được lưu ở vị trí Sj 0 ngược lại    Distributed DBMS Page 5. 63  Tổng chi phí  Chi phí bộ nhớ (của Fj tại vị trí Sk)  Chi phí xử lý truy vấn (cho một truy vấn) processing component + transmission component Mô hình cấp phát (unit storage cost at Sk)  (size of Fj) xjk query processing cost  all queries cost of storing a fragment at a site all fragmentsall sites Distributed DBMS Page 5. 64  Chi phí xử lý truy vấn Processing component access cost + integrity enforcement cost + concurrency control cost  Access cost  Integrity enforcement and concurrency control costs  Can be similarly calculated Mô hình cấp phát (no. of update accesses+ no. of read accesses)  all fragmentsall sites xijlocal processing cost at a site Distributed DBMS Page 5. 65  Chi phí xử lý truy vấn Thành phần truyền thông Chi phí xử lý cập nhật + chi phí xử lý đọc  Cost of updates  Retrieval Cost Mô hình cấp phát update message cost  all fragmentsall sites acknowledgment cost all fragmentsall sites (minall sites all fragments cost of retrieval command  cost of sending back the result) Distributed DBMS Page 5. 66  Ràng buộc  Thời gian đáp ứng execution time of query ≤ max. allowable response time for that query  Ràng buộc bộ nhớ (for a site)  Ràng buộc xử lý (for a site) Mô hình cấp phát storage requirement of a fragment at that site  all fragments storage capacity at that site processing load of a query at that site  all queries processing capacity of that site Distributed DBMS Page 5. 67  Các phương pháp giải  FAP is NP-complete  DAP also NP-complete  Các Heuristics dựa trên  Vị trí kho hoàng duy nhất (for FAP)  Bài toán xếp ba lô (knapsack problem)  Kỹ thuật nhánh và cận (branch and bound techniques)  Bài toán luồng (network flow) Mô hình cấp phát Distributed DBMS Page 5. 68  Cố gắng giảm không gian lời giải  Giá đình tất các các phân hoạch ứng viên đều đã biết; chọn phân hoạch “tốt nhất”  Bỏ đi các đầu tiên  Trượt cửa sổ trên các mảnh Mô hình cấp phát