Tập bài giảng Cơ sơ dữ liệu phân tán - Phần 1

sở dữ liệu phân tán 123 Cho một quan hệ toàn cục R thì các mảnh ngang Ri của R là: Ri = iF  (R); 1 ni  Trong đó: + Fi là điều kiện chọn hoặc công thức chọn (selection formula) 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 là mỗi bộ của quan hệ toàn cục đƣợc đƣa vào trong một và chỉ một mảnh. Xác định phân mảnh ngang chính của một quan hệ toàn cục là xác định một tập hợp các vị từ chọn (selection predicate) đầy đủ và tách biệt. Các bộ của một mảnh phải đƣợc tham chiếu giống nhau trong tất cả các ứng dụng. Ví dụ 3.7: Xét quan hệ NV đƣợc phân thành hai mảnh ngang chính NV1 và NV2 với hai vị từ đơn giản LUONG 35000 và LUONG >35000 nhƣ sau: NV1 = 35000LUONGσ  (NV) NV2 = 35000LUONG σ  (NV) Nếu các miền của các thuộc tính có trong các điều kiện chọn là liên tục và vô hạn thì khó định nghĩa một tập hợp các điều kiện F={F1, F2,, Fn} dùng để phân mảnh quan hệ một cách đúng đắn. Nếu thêm một bộ có LUONG=50000 vào NV thì phải xét lại việc phân mảnh để quyết định thêm một bộ mới vào mảnh NV2 hoặc phân mảnh lại và định nghĩa thêm một mảnh mới NV3: NV2 = σ SAL≥35000 AND SAL ≤ 40000 ( NV) NV3 =  SAL > 40000 (NV) Các giá trị của SAL phải không âm nên phải thêm một vị từ đơn giản 0 ≤ SAL vào tập Pr Trong thực tế, vấn đề này có thể đƣợc giải quyết bằng cách giới hạn miền của các thuộc tính phù hợp với các yêu cầu của ứng dụng. Định nghĩa một mảnh ngang: Một mảnh ngang Ri của quan hệ R bao gồm tất cả các bộ của quan hệ R thỏa mãn vị từ giao tối thiểu mi. Cho trƣớc một tập hợp các vị từ giao tối thiểu M thì số mảnh ngang bằng số vị từ giao tối thiểu. Tập hợp các mảnh ngang này cũng thƣờng đƣợc gọi là tập hợp các mảnh giao tối thiểu (minterm fragment). Ví dụ 3.8: Xét ví dụ 3.5 có tập vị từ giao tối thiểu: M={m1, m2, m3, m4}. Do đó số mảnh ngang là 4. Tập các mảnh ngang là: Tập bài giảng Cơ sở dữ liệu phân tán 124 DA1= 1m σ (DA) MADA TENDA NS VT D3 Nâng cấp hệ thống mạng 28000 Hà Nội D5 Xây dựng hệ thống quản lý tài chính 30000 Hà Nội DA2= 2m σ (DA) MADA TENDA NS VT D2 Thiết kế trang Web bán hàng 12000 Hà Nội DA3= 3m σ (DA) MADA TENDA NS VT D4 Xây dựng phần mềm quản lý điểm 25000 Nam Định DA4= 4m σ (DA) MADA TENDA NS VT D1 Xây dựng phần mềm quản lý lƣơng 20000 Nam Định Ví dụ 3.9: Xét ví dụ 3.6 có tập vị từ giao tối thiểu: M={m1, m2}. Do đó số mảnh ngang là 2. Tập các mảnh ngang là: NV= 1m σ (NV) MANV HOTEN LUONG THUE MAQL MAP NV2 Hà Tấn Đạt 2000 20 QL2 12 NV5 Lê Diệu Huyền 1300 14 QL4 5 NV= 2m σ (NV) MANV HOTEN LUONG THUE MAQL MAP NV1 Nguyễn Minh Anh 4000 10 QL1 10 NV3 Trung Khang 3500 15 QL3 15 NV4 Nguyễn Kiên Nam 3000 8 QL3 15 2) Các bƣớc thiết kế phân mảnh ngang chính theo chiến lƣợc từ trên xuống. Bƣớc 1: Tìm lƣợc đồ toàn cục Bƣớc 2: Vẽ đồ thị kết nối biểu diễn mối liên hệ giữa các quan hệ toàn cục Bƣớc 3: Tìm tập các vị từ đơn giản PR Bƣớc 4: Tìm tập các vị từ đầy đủ và tối thiểu PR‟=COM_MIN(Pr, R)={p1, p2,, pn} Bƣớc 5: Tìm tập hợp các vị từ giao tối thiểu M= {m1, m2,, mk} có thể đƣợc định nghĩa trên PR‟ Bƣớc 6: Tìm tập các phép suy diễn I={i1, i2, , ih} Bƣớc 7: Tìm tập các vị từ giao tối thiểu có nghĩa M‟= PHORIZONTAL(PR, R)={m1, m2,, mg} Tập bài giảng Cơ sở dữ liệu phân tán 125 Bƣớc 8: Viết biểu thức phân mảnh ngang chính theo M‟ Ri = im σ (R); 1 i g  3) Đặc tính của vị từ đơn giản Chúng ta vẫn chƣa nêu ra đƣợc một giải thuật có thể phân mảnh một quan hệ R và một tập hợp các ứng dụng sẽ tham chiếu đến nó. Việc chọn lựa các vị từ không thể dựa vào các quy tắc chính xác, bởi vì việc nhận biết một vị từ có ích cho việc mô tả phân mảnh sẽ dựa vào trực giác của ngƣời thiết kế. Nhƣng chúng ta biết rằng, định nghĩa các mảnh ngang dựa vào các vị từ giao tối thiểu. Do đó, bƣớc đầu tiên của bất kỳ giải thuật phân mảnh nào là xác định một tập hợp các vị từ đơn giản có một đặc tính nào đó. Chúng ta có thể định nghĩa hai đặc tính đặc trƣng cho sự phân mảnh thích hợp, đó là tính đầy đủ (completeness) và tính tối thiểu (minimality) của các vị từ đơn giản. 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 các vị từ đơn giản, 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 (tức là mi chứa pi và mj chứa pi) và tồn tại ít nhất một ứng dụng tham chiếu khác nhau đến hai mảnh fi và fj (tƣơng ứng mi và mj). Do đó, pi là vị từ thích hợp nếu và chỉ nếu: )( )( i i fcard macc # )( )( j j fcard macc Một tập hợp các vị từ đơn giản Pr đƣợc gọi là đầy đủ (complete) nếu và chỉ nếu bất kỳ hai 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 hợ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. Ví dụ 3.10: Xét ví dụ 3.5 với tập vị từ đơn giản: PDA={p1, p2}. - Khi đó p1 là vị từ thích hợp vì: + Tồn tại m1 và m3 chỉ khác nhau ở p1 (m1=p1  p2 ,m3=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA1; ứng dụng 2 truy xuất đến mảnh DA3 - Khi đó p2 là vị từ thích hợp vì: + Tồn tại m1 và m2 chỉ khác nhau ở p2 (m1=p1  p2 , m2=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA1; ứng dụng 1 truy xuất đến mảnh DA3 Do đó PDA={p1, p2} là tối thiểu và đầy đủ Ví dụ 3.11: Xét ví dụ 3.6 với tập vị từ đơn giản: PNV={p1}. - Tồn tại m1 và m2 chỉ khác nhau ở p1 (m1=p1, m2=p1) - Ứng dụng 1 truy xuất đến mảnh DA1; không có ứng dụng nào truy xuất đến mảnh DA2 Khi đó p1 không là vị từ thích hợp Tập bài giảng Cơ sở dữ liệu phân tán 126 Do đó PNV={p1} là đầy đủ nhƣng không tối thiểu Ví dụ 3.12: Xét ví dụ 3.5 với tập vị từ đơn giản: PDA={p1}. Khi đó PDA={p1} là không đầy đủ, bởi vì các ứng dụng tham chiếu đến các bộ của mà có ngân sách lớn hơn 20000 ở trong mỗi mảnh đƣợc tạo ra bởi PDA có xác suất lớn hơn. 4) Điều kiện phân mảnh đúng đắn Cho Pr={ p1, p2, , pm} là một tập hợ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. 5) Các phép suy diễn Bƣớc thứ 5 trong quá trình thiết kế phân mảnh ngang chính là tìm tập hợp các vị từ giao tối thiểu có thể đƣợc định nghĩa trên các vị từ trong tập hợp Pr‟. Các vị từ giao tối thiểu này xác định các mảnh đƣợc sử dụng trong bƣớc định vị. Lƣu ý rằng, việc xác định một tập hợp đầy đủ các vị từ có thể rất tốn kém trong một số trƣờng hợp, bởi vì tập hợp này có thể rất lớn. Trong thực tế, tập hợp các vị từ giao tối thiểu là luỹ thừa của số vị từ đơn giản. Chẳng hạn, điều này xảy ra khi đƣa ra các vị từ để mô tả các tham chiếu khác nhau của các ứng dụng khác nhau, sử dụng các tiêu chí khác nhau. Trong trƣờng hợp này, các mảnh sẽ tƣơng ứng với các kết hợp của các tiêu chí này. Trong thực tế, việc tìm một tập hợp đầy đủ các vị từ phải đƣợc thực hiện theo một cách “hợp lý”, bằng cách: - Tập chung vào các ứng dụng khá quan trọng - Không phân biệt các mảnh có các đặc điểm rất giống nhau. Trong tập hợp đầy đủ các vị từ, chúng ta loại bỏ các vị từ vô nghĩa mà chúng mâu thuẫn với tập hợp các phép suy diễn I để tìm ra các vị từ giao tối thiểu. Việc tìm các phép suy diễn I dựa vào các quy tắc biến đổi tƣơng đƣơng sau: p1  p2  p2  p1 (1) p1  p2  p2  p1 (2)  ( p)  p (3) (p1  p2)   p1   p2 (4) p1  (p2  p3)  (p1  p2)  (p1  p3) (5) p1  (p2  p3)  (p1  p2)  p3 (6) p1  (p2  p3)  (p1  p2)  p3 (7) p1  (p2  p3)  (p1  p2)  (p1  p3) (8) (p1  p2)   p1   p2 (9) p  p = false (10) p  p = p (11) a) Trƣờng hợp 1: Đối với vị từ đẳng thức Tập bài giảng Cơ sở dữ liệu phân tán 127 Cho Pr = { p1, p2 } với: p1: att = value_1 p2: att = value_2 Và miền của att là {value_1, value_2}, thì tập hợp I bao gồm hai phép suy diễn (implication) là: i1: (att = value_1)   ( att = value_2) i2:  (att = value_1)  ( att = value_2) Do đó, I={i1, i2} b) Trƣờng hợp 2: Đối với các vị từ bất đẳng thức Cho Pr = { p1, p2 } với: p1: att > value_1 p2: att ≤ value_1 Thì tập hợp I bao gồm hai phép suy diễn (implication) là: i1: (att > value_1)   (att ≤ value_1) i2:  (att > value_1)  (att ≤ value_1) Do đó, I={i1, i2} Ví dụ 3.13: Xét hệ thống quản lý dự án trong ví dụ 3.2. Giả sử PDA={p1, p2} + p1: VT=„Nam Định„ + p2: VT=„Hà Nội„ Khi đó ta có tập các phép suy diễn I= i1, i2}, trong đó: + i1: (VT=„Nam Định„)   (VT=„Hà Nội„) + i2:  (VT=„Nam Định„)  (VT=„Hà Nội„) Ví dụ 3.14: Xét hệ thống quản lý dự án trong ví dụ 3.2. Giả sử PTL={p1, p2} p1: LUONG<3000 p2: LUONG≥3000 Khi đó ta có tập các phép suy diễn I= i1, i2}, trong đó: + i1: (LUONG<3000)   (LUONG≥3000) + i2:  (LUONG<3000 „)  (LUONG≥3000). 6) Thuật toán COM_MIN Thuật toán COM_MIN là thuật toán xây dựng một tập hợp các vị từ Pr‟ là đầy đủ và tối thiểu. Bắt đầu: Xét một vị từ pi phân chia các bộ của R thành hai phần và tồn tại ít nhất một ứng dụng tham chiếu khác nhau đến hai phần này. Cho Pr‟ = pi. Phương pháp: Tập bài giảng Cơ sở dữ liệu phân tán 128 Xét một vị từ đơn giản mới pj mà phân chia ít nhất một mảnh fk của Pr‟ thành hai phần và tồn tại ít nhất một ứng dụng tham chiếu khác nhau đến hai phần này. Bƣớc 1: Cho Pr‟ Pr‟pj Bƣớc 2: Loại bỏ các vị từ không thích hợp ra khỏi Pr‟. Bƣớc 3: Lặp lại bƣớc 2 cho đến khi tập hợp các mảnh giao tối thiểu của Pr‟ là đầy đủ. Quy tắc 1: Là quy tắc cơ bản về tính đầy đủ và tính tối thiểu mà một quan hệ hoặc một mảnh đƣợc phân chia thành ít nhất hai phần và tồn tại ít nhất một ứng dụng tham chiếu khác nhau đến hai phần này. fi của Pr‟: mảnh fi đƣợc xác định theo vị từ giao tối thiểu đƣợc định nghĩa trên các vị từ của Pr‟. Giải thuật 3.1 COM_MIN Đầu vào: Pr: tập hợp các vị từ đơn giản; R: quan hệ; Đầu ra: Pr‟: tập hợp các vị từ đơn giản là đầy đủ và tối thiểu Khai báo F: tập hợp các mảnh giao tối thiểu Begin Tìm pi  Pr sao cho pi phân chia R theo quy tắc1; Pr‟ = pi; Pr = Pr - pi; F = {fi}; { fi là mảnh giao tối thiểu theo pi } Repeat Begin tìm pj Pr sao cho pj phân chia mảnh fh nào đó của Pr‟ theo quy tắc 1; Pr‟ = Pr‟  pj; Pr = Pr - pj; F = F  {fj} - fh ; while pk Pr‟ là một vị từ không thích hợp do begin Pr‟ = Pr‟ - pk; F = F - fk; end End Until Pr‟ là đầy đủ End. {COM_MIN} 7) Thuật toán PHORIZONTAL Giải thuật để phân mảnh ngang chính đƣợc trình bày trong giải thuật 3.2 đƣợc gọi là PHORIZONTAL. Phần nhập là một quan hệ Ri cần đƣợc phân mảnh ngang chính, và Pri là tập hợp các vị từ đơn giản đƣợc xác định theo các ứng dụng tham chiếu đến Ri. Tập bài giảng Cơ sở dữ liệu phân tán 129 Phần xuất là tập hợp các vị từ giao tối thiểu Mi dùng để tạo ra các mảnh giao tối thiểu (là các mảnh ngang của Ri). Giải thuật 3.2 PHORIZONTAL Đầu vào: R: quan hệ; Pr: tập hợp các vị từ đơn giản. Đầu ra: M: tập hợp các mảnh giao tối thiểu . begin Pr‟ = COM_MIN(Pr, R) Xác định M là tập hợp các vị từ giao tối thiểu; Xác định I là tập các phép suy diễn giữa pi  Pr‟ For each mi  M do If mi là mâu thuẫn với I then M = M - mi end.{PHORIZONTAL} a) Trƣờng hợp 1: Đối với vị từ đẳng thức Ta có tập vị từ giao tối thiểu đƣợc định nghĩa theo Pr: m1: (att = value_1)  ( att = value_2) m2: (att = value_1)   ( att = value_2) m3:  (att = value_1)  ( att = value_2) m4:  (att = value_1)   ( att = value_2) M={m1, m2, m3, m4} Trong trƣờng hợp này, các vị từ m1, m4 mâu thuẫn với tập hợp các phép suy diễn I. Do đó có thể loại bỏ chúng ra khỏi tập hợp M. Trong tập hợp I, các vị từ m2 và m3 có thể rút gọn: m2: att = value_1 m3: att = value_2 b) Trƣờng hợp 2: Đối với các vị từ bất đẳng thức Ta có tập vị từ giao tối thiểu đƣợc định nghĩa theo Pr: m1: (att > value_1)  (att ≤ value_1) m2: (att > value_1)   ( att ≤ value_1) m3:  (att > value_1)  ( att ≤ value_1) m4:  (att > value_1)   ( att ≤ value_1) M={m1, m2, m3, m4} Trong trƣờng hợp này, các vị từ m1, m4 mâu thuẫn với tập hợp các phép suy diễn I. Do đó có thể loại bỏ chúng ra khỏi tập hợp M. Trong tập hợp I, các vị từ m2 và m3 có thể rút gọn: m2: att > value_1 m3: att ≤ value_1 Tập bài giảng Cơ sở dữ liệu phân tán 130 Ví dụ 3.15: Xét hệ thống quản lý dự án trong ví dụ 3.2. m1: (VT=„Nam Định„)  (VT=„Hà Nội„) m2: (VT=„Nam Định„)   (VT=„Hà Nội„) m3:  (VT=„Nam Định„)  (VT=„Hà Nội„) m4:  (VT=„Nam Định„)   (VT=„Hà Nội„) M={m1, m2, m3, m4} Khi đó, các vị từ m1, m4 mâu thuẫn với tập hợp các phép suy diễn I. Do đó có thể loại bỏ chúng ra khỏi tập hợp M. Trong tập hợp I, các vị từ m2 và m3 có thể rút gọn: m2: VT=„Nam Định„ m3: VT=„Hà Nội„ Cuối cùng, M={m2, m3} Ví dụ 3.16: Xét hệ thống quản lý dự án trong ví dụ 3.2. m1: (LUONG<3000) (LUONG≥3000) m2: (LUONG<3000)   (LUONG≥3000) m3:  (LUONG<3000)  (LUONG≥3000) m4:  (LUONG<3000)   (LUONG≥3000) M={m1, m2, m3, m4} Khi đó, các vị từ m1, m4 mâu thuẫn với tập hợp các phép suy diễn I. Do đó có thể loại bỏ chúng ra khỏi tập hợp M. Trong tập hợp I, các vị từ m2 và m3 có thể rút gọn: m2: LUONG<3000 m3: LUONG≥3000 Cuối cùng, M={m2, m3} Ví dụ 3.17: Xét hệ thống quản lý dự án trong ví dụ 3.2. Giả sử có một ứng dụng truy xuất DA theo vị trí thực hiện dự án, áp dụng thuật toán COM_MIN và PHORIZONTAL để: - Phân mảnh ngang chính quan hệ DA - Phân mảnh ngang dẫn xuất quan hệ HS Các bước thiết kế phân mảnh ngang chính quan hệ toàn cục DA: Bƣớc 1: Lƣợc đồ toàn cục (Theo đề bài) Bƣớc 2: Vẽ đồ thị kết nối biểu diễn mối liên hệ giữa các quan hệ toàn cục (Trong ví dụ 3.2) Bƣớc 3: Tìm tập các vị từ đơn giản PDA PDA={p1, p2} + p1: VT=„Nam Định„ + p2: VT=„Hà Nội„ Bƣớc 4: Tìm tập các vị từ đầy đủ và tối thiểu PDA„ =COM_MIN(PDA, DA): Tập bài giảng Cơ sở dữ liệu phân tán 131 F= Xét p1 chia DA theo quy tắc 1 thành 2 phần f1= 1p σ (DA) và f2= 1p σ  (DA); PDA„={p1} PDA={p2} F={f1, f2} Xét p2 không chia mảnh nào của F PDA„={p1} PDA={p2} F={f1, f2} Vậy PDA„={p1} là tối thiểu và đầy đủ Chú ý: Nếu xét p2 trƣớc thì PDA„={ p2} là tối thiểu và đầy đủ. Bƣớc 5: Tìm tập hợp các vị từ giao tối thiểu định nghĩa trên PDA‟: M={m1, m2} m1=p1, m2=p1 Bƣớc 6: Tìm tập các phép suy diễn I= Bƣớc 7: Tìm tập các vị từ giao tối thiểu có nghĩa M‟= PHORIZONTAL(PDA, DA)={m1, m2} + PDA„ =COM_MIN(PDA, DA): + M={m1, m2} + I= Nên M‟= {m1, m2} Bƣớc 8: Viết biểu thức phân mảnh ngang chính theo M‟ DA1= 1m σ (DA) = 1p σ (DA)=σ VT=„Nam Định„ (DA) DA2= 2m σ (DA)= 1p σ  (DA)=σ (VT=„Nam Định„) (DA) Kết quả phân mảnh: DA1 MADA TENDA NS VT D1 CSDL 20000 Nam Định D4 PHÁT TRIỂN 25000 Nam Định DA2 MADA TENDA NS VT D2 CÀI ĐẶT 12000 Hà Nội D3 BẢO TRÌ 28000 Hà Nội Ví dụ 3.18: Xét hệ thống quản lý dự án trong ví dụ 3.2. Giả sử hệ thống có các ứng dụng sau: Ứng dụng 1: Truy xuất các bộ của DA theo vị trí là “Nam Định” Tập bài giảng Cơ sở dữ liệu phân tán 132 Ứng dụng 2: Truy xuất các bộ của DA có ngân sách bằng 25000 Ứng dụng 3: Truy xuất các bộ của DA có ngân sách khác 25000 Áp dụng thuật toán COM_MIN và PHORIZONTAL để: - Phân mảnh ngang chính quan hệ DA - Phân mảnh ngang dẫn xuất quan hệ HS Các bước thiết kế phân mảnh ngang chính quan hệ toàn cục DA: Bƣớc 1: Lƣợc đồ toàn cục (Theo đề bài) Bƣớc 2: Vẽ đồ thị kết nối biểu diễn mối liên hệ giữa các quan hệ toàn cục (Trong ví dụ 3.2) Bƣớc 3: Tìm tập các vị từ đơn giản PDA PDA={p1, p2, p3} + p1: VT=„Nam Định„ + p2: NS= 25000 + p3: NS ≠ 25000 Bƣớc 4: Tìm tập các vị từ đầy đủ và tối thiểu PDA„ =COM_MIN(PDA, DA): F= Xét p1 chia DA theo quy tắc 1 thành 2 phần f1= 1p σ (DA) và f2= 1p σ  (DA); PDA„={p1} PDA={p2, p3} F={f1, f2} Xét p2 chia f1 theo quy tắc 1 thành 2 phần f11= 2p σ (f1) và f12= 2p σ  (f1); PDA„={p1, p2} PDA={p3} F={f11, f12, f2} p1 là vị từ thích hợp vì: + Tồn tại m1 và m3 chỉ khác nhau ở p1 (m1=p1  p2 ,m3=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA1= 1m σ (DA); ứng dụng 2 truy xuất đến mảnh DA3== 3m σ (DA); p2 là vị từ thích hợp vì: + Tồn tại m1 và m2 chỉ khác nhau ở p2 (m1=p1  p2 , m2=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA1= 1m σ (DA); ứng dụng 1, 3 truy xuất đến mảnh DA2= 2m σ (DA); Xét p3 chia f3 theo quy tắc 1 thành 2 phần f21= 3 p σ (f2) và f22= 3 p σ  (f2); PDA„={p1, p2, p3} Tập bài giảng Cơ sở dữ liệu phân tán 133 PDA=  F={f11, f12, f21, f22} Khi đó ta có tập vị từ giao tối thiểu M={m1, m2, m3, m4, m5, m6, m7, m8} Sử dụng tính chất phủ định của đẳng thức Attribute=Value là Attribute  Value p3  p2 ta có m1=p1  p2  p3 = False m2=p1  p2  p3 = p1  p2 m3=p1  p2  p3 = p1  p2 m4=p1  p2  p3 =False m5=p1  p2  p3 = False m6=p1  p2  p3 = p1  p2 m7=p1  p2  p3 = p1  p2 m8=p1  p2  p3 = False p1 là vị từ thích hợp vì: + Tồn tại m1 và m3 chỉ khác nhau ở p1 (m2=p1  p2 ,m6=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA2= 2m σ (DA); ứng dụng 2 truy xuất đến mảnh DA6= 6m σ (DA); p2 là vị từ thích hợp vì: + Tồn tại m1 và m2 chỉ khác nhau ở p2 (m2=p1  p2 , m3=p1  p2) + Ứng dụng 1, 2 truy xuất đến mảnh DA2= 2m σ (DA); ứng dụng 1, 3 truy xuất đến mảnh DA3= 3m σ (DA); p3 là không là vị từ thích hợp vì không tồn tại mi chứa p3 và mj chứa p3 Vậy PDA„={p1, p2} là tối thiểu và đầy đủ Chú ý: Nếu sử dụng phép biến đổi tƣơng tƣơng p2  p3 ta có PDA„={p1, p3} là tối thiểu và đầy đủ. Bƣớc 5: Tìm tập hợp các vị từ giao tối thiểu định nghĩa trên PDA‟: M={m1, m2, m3, m4} m1=p1  p2 m2=p1  p2 m3=p1  p2 m4=p1  p2 Bƣớc 6: Tìm tập các phép suy diễn I= Bƣớc 7: Tìm tập các vị từ giao tối thiểu có nghĩa M‟= PHORIZONTAL(PDA, DA)={m1, m2, m3, m4} + PDA„ =COM_MIN(PDA, DA): + M={m1, m2, m3, m4} Tập bài giảng Cơ sở dữ liệu phân tán 134 + I= Nên M‟= {m1, m2, m3, m4} Bƣớc 8: Viết biểu thức phân mảnh ngang chính theo M‟ DA1= 1m σ (DA) = 1 2pp σ  (DA)=σ VT=„Nam Định„ NS= 25000 (DA) DA2= 2m σ (DA)= 21p p σ  (DA)=σ VT=„Nam Định„ (NS= 25000) (DA) DA3= 3m σ (DA)= 21 pp σ   (DA)=σ (VT=„Nam Định„)  NS= 25000 (DA) DA4= 4m σ (DA)= 1 2pp σ   (DA)=σ (VT=„Nam Định„) (NS= 25000) (DA) Kết quả phân mảnh: DA1 MADA TENDA NS VT D4 PHÁT TRIỂN 25000 Nam Định DA2 MADA TENDA NS VT D1 CSDL 20000 Nam Định DA3= MADA TENDA NS VT DA4 MADA TENDA NS VT D2 CÀI ĐẶT 12000 Hà Nội D3 BẢO TRÌ 28000 Hà Nội 3.3.3. Thiết kế phân mảnh ngang dẫn xuất 1) Định nghĩa thiết kế phân mảnh ngang dẫn xuất Phân mảnh ngang dẫn xuất của một quan hệ toàn cục R không dựa trên các đặc tính của các thuộc tính riêng của nó, mà đƣợc suy dẫn từ mảnh ngang của một quan hệ khác. Phân mảnh ngang dẫn xuất đƣợc định nghĩa trên trên các quan hệ bộ phận của đƣờng liên hệ theo phép chọn trên quan hệ chủ của đƣờng liên hệ này. Điều quan trọng cần nhớ hai điểm: Thứ nhất, đƣờng liên hệ giữa quan hệ chủ và quan hệ bộ phận đƣợc định nghĩa là một phép kết nối bằng. Thứ hai, một phép kết nối bằng có thể thực hiện bằng các phép nửa kết nối. Điểm thứ hai là đặc biệt quan trọng đối với các mục đích của chúng ta, bởi vì chúng ta muốn phân chia quan hệ bộ phận theo sự phân mảnh của quan hệ chủ của nó, Tập bài giảng Cơ sở dữ liệu phân tán 135 nhƣng chúng ta cũng muốn mảnh kết quả chỉ đƣợc định nghĩa trên các thuộc tính của quan hệ bộ phận. Cho trƣớc một đƣờng liên hệ L với owner(L) = S và member(L) = R, các mảnh ngang dẫn xuất của R đƣợc định nghĩa nhƣ sau: Ri =R  F Si , 1  i  n Trong đó: - n là số lƣợng lớn nhất các mảnh sẽ đƣợc định nghĩa trên R - Si = iF  (S) - Fi là công thức dùng để định nghĩa mảnh ngang chính Si - F là điều kiện nửa kết nối (semi - join condition). Quan hệ R có thể là quan hệ chủ của một đƣờng liên hệ khác L‟ và quan hệ bộ phận là T, và cứ nhƣ thế. Trong trƣờng hợp tổng quát, chúng ta có thể có một cây phân mảnh ngang dẫn xuất (derived horizontal fragmentation tree), trong đó nút cha là quan hệ chủ và các nút con của nó là các quan hệ bộ phận. Để thực hiện phân mảnh ngang dẫn xuất, có ba dữ liệu vào là: - Tập hợp các mảnh con của quan hệ chủ - Quan hệ bộ phận - Tập hợp các vị từ nửa kết nối giữa quan hệ chủ và quan hệ bộ phận 2) Các bƣớc thiết kế phân mảnh ngang dẫn xuất theo chiến lƣợc từ trên xuống. Bƣớc 1: Tìm lƣợc đồ toàn cục Bƣớc 2: Vẽ đồ thị kết nối biểu diễn mối liên hệ giữa các quan hệ toàn cục Bƣớc 3: Tìm tập các vị từ đơn giản PS Bƣớc 4: Tìm tập các vị từ đầy đủ và tối thiểu PS‟=COM_MIN(PS,S)={p1, p2,, pn} Bƣớc 5: Tìm tập hợp các vị từ giao tối thiểu M= {m1, m2,, mk} có thể đƣợc định nghĩa trên PS‟ Bƣớc 6: Tìm tập các phép suy diễn I={i1, i2, , ih} Bƣớc 7: Tìm tập các vị từ giao tối thiểu có nghĩa M‟= PHORIZONTAL(PS, S)={m1, m2,, mg} Bƣớc 8: Viết biểu thức phân mảnh ngang chính theo M‟ Tập bài giảng Cơ sở dữ liệu phân tán 136 Si = im σ (S); 1 i g  Bƣớc 9: Viết biểu thức phân mảnh dẫn xuất Ri =R  F Si , 1 i g  Ví dụ 3.19: Xét ví dụ 3.17 Các bước thiết kế phân mảnh ngang dẫn xuất quan hệ toàn cục HS: Từ bƣớc 1 đến bƣớc 8 đã đƣợc thực hiện trong ví dụ 3.17 Bƣớc 9: Các biểu thức phân mảnh ngang dẫn xuất HS1= HS  HS.MaDA= DA.MaDADA1 HS2= HS  HS.MaDA= DA.MaDADA2 Kết quả phân mảnh ngang dẫn xuất: HS1 MANV MADA NV TG A1 D1 Quản lý 12 A2 D1 Phân tích 34 A3 D4 Lập trình 10 A6 D4 Kỹ thuật 36 HS2 MANV MADA NV TG A2 D2 Phân tích 6 A3 D3 Kỹ thuật 12 A4 D2 Quản lý 6 A5 D2 Quản lý 20 A7 D3 Quản lý 48 A8 D3 Lập trình 15 Ví dụ 3.20: Xét ví dụ 3.18 Các bước thiết kế phân mảnh ngang dẫn xuất quan hệ toàn cục HS: Từ bƣớc 1 đến bƣớc 8 đã đƣợc thực hiện trong ví dụ 3.18 Bƣớc 9: Các biểu thức phân mảnh ngang dẫn xuất HS1= HS  HS.MaDA= DA.MaDADA1 HS2= HS  HS.MaDA= DA.MaDADA2 HS3= HS  HS.MaDA= DA.MaDADA3 HS4= HS  HS.MaDA= DA.MaDADA4 Kết quả phân mảnh ngang dẫn xuất: Tập bài giảng Cơ sở dữ liệu phân tán 137 HS1 MANV MADA NV TG A3 D4 Lập trình 10 A6 D4 Kỹ thuật 36 HS2 MANV MADA NV TG A1 D1 Quản lý 12 A2 D1 Phân tích 34 HS3= MANV MADA NV TG HS MANV MADA NV TG A2 D2 Phân tích 6 A3 D3 Kỹ thuật 12 A4 D2 Quản lý 6 A5 D2 Quản lý 20 A7 D3 Quản lý 48 A8 D3 Lập trình 15 3) Đồ thị kết nối Phân mảnh ngang dẫn xuất đƣợc dùng để tạo điều kiện thuận lợi cho phép kết nối giữa các mảnh. Một phép kết nối phân tán (distributed join) là một phép kết nối giữa các quan hệ đƣợc phân mảnh ngang. Khi một ứng dụng cần thực hiện phép kết nối giữa hai quan hệ toàn cục R và S, thì tất cả các bộ của R và của S phải đƣợc so sánh với nhau. Do đó theo nguyên tắc, cần phải so sánh tất cả các mảnh Ri của R với tất cả các mảnh Sj của S: R F S = (i Ri) F (j Sj) Tuy nhiên, đôi khi có thể suy diễn để xác định một số phép liên hệ từng phần Ri  Sj là rỗng: R F S = (ij(Ri F Sj) Đối với sự phân tán dữ liệu cho trƣớc, điều này xảy ra khi các giá trị của thuộc tính kết nối của Ri và Sj là khác nhau. Một phép kết nối phân tán đƣợc biểu diễn một cách hiệu quả bằng đồ thị kết nối (join graph). Tập bài giảng Cơ sở dữ liệu phân tán 138 Đồ thị kết nối G của phép kết nối phân tán R  S là một đồ thị (N, E) với các nút N biểu diễn các mảnh của R và S; các cạnh vô hƣớng giữa các nút biểu diễn các phép kết nối giữa các mảnh mà kết quả của phép kết nối là khác rỗng. Để đơn giản, chúng ta không đƣa vào trong N các mảnh của R hoặc của S mà chúng kết nối với tất các mảnh của quan hệ khác đều cho kết quả rỗng. Các loại đồ thị kết nối: Hình 3.3. Sơ đồ thiết kế tổng CSDL phân tán Đồ thi kết nối đƣợ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 nối đƣợ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 nối suy giảm có hai loại: - Đồ thị kết nối suy giảm đƣợc gọi là phân tách (partitioned) nếu đồ thị 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 nối suy giảm đƣợc gọi là đơn giản (simple) nếu nó phân tách và mỗi đồ thị con có đúng một cạnh. Việc xác định một phép kết nối có đồ thị kết nối đơn giản là rất quan trọng trong thiết kế CSDL. Một cặp mảnh đƣợc nối với nhau bằng một cạnh trong đồ thị kết nối đơn giản có một tập hợp các giá trị chung của các thuộc tính kết nối. Do đó có thể xác định phân mảnh và định vị của hai quan hệ toán hạng R và S sao cho đồ thị kết nối là đồ thị đơn giản và các cặp mảnh tƣơng ứng đƣợc đặt tại cùng một nơi, khi đó phép kết nối có thể đƣợc thực hiện theo cách phân tán bằng cách thực hiện phép kết nối cục bộ các cặp mảnh và sau đó tập hợp các kết q