Cơ sơ dữ liệu phân tán - 17

m1= p1  p2 = (VT=‟Hà Nội‟  NS>20000) m2=p1  p2 =(VT=‟Hà Nội‟ (NS>20000)) m3= p1  p2=((VT=‟Hà Nội‟) NS>20000)

m4= p1 p2=( (VT=‟Hà Nội‟)(NS>20000))

Do (NS>20000)=(NS≤20000) và ((VT=‟Hà Nội‟)=(VT=‟Nam Định‟) nên m1= (VT=‟Hà Nội‟  NS>20000)

m2=(VT=‟Hà Nội‟  NS≤20000)

m3=(VT=‟Nam Định‟ NS>20000)

m4=(VT=‟Nam Định‟ NS≤20000)

- Tập vị từ giao tối thiểu: M={m1, m2, m3, m4}.

- Độ chọn giao tối thiểu của các vị từ giao tối thiểu: Sel(m1)=2 Sel(m2)=1

Sel(m3)=1 Sel(m4)=1

Ví dụ 3.6: Xét hệ thống quản lý kinh doanh của một công ty trong ví dụ 2.13 với một ứng dụng truy xuất NV theo lương nhỏ hơn 3000.

NV

MANV

HOTEN	LUONG	THUE	MAQL	MAP
NV1	Nguyễn Minh Anh	4000	10	QL1	10
NV2	Hà Tấn Đạt	2000	20	QL2	12
NV3	Trung Khang	3500	15	QL3	15
NV4	Nguyễn Kiên Nam	3000	8	QL3	15
NV5	Lê Diệu Huyền	1300	14	QL4	5

Có thể bạn quan tâm!

• Truy Xuất Csdl Trước Khi Nhập Vào Các Giá Trị
• Vấn Đề Thiết Kế Cơ Sở Dữ Liệu Phân Tán
• Thiết Kế Phân Mảnh Cơ Sở Dữ Liệu
• Thiết Kế Phân Mảnh Ngang Dẫn Xuất
• Kiểm Tra Điều Kiện Đúng Đắn Khi Phân Mảnh Ngang
• Cơ sơ dữ liệu phân tán - 20

Xem toàn bộ 312 trang tài liệu này.

- Các vị từ đơn giản được định nghĩa trên quan hệ DA: p1: LUONG<3000

- Tập vị từ đơn giản: PNV={p1}.

- Các vị từ giao tối thiểu được định nghĩa dựa trên các vị từ đơn giản m1= p1 =(LUONG<3000)

m2= p1 =(LUONG<3000)

Do (LUONG<3000)=(LUONG≥3000) nên m1= (LUONG<3000) m2=(LUONG≥3000)

- Tập vị từ giao đối thiểu: M={m1, m2}.

- Độ chọn giao tối thiểu của các vị từ giao tối thiểu: Sel(m1)=2 Sel(m2)=3

3.3.2. Thiết kế phân mảnh ngang chính

1) Định nghĩa thiết kế phân mảnh ngang chính

Cho một quan hệ toàn cục R thì các mảnh ngang Ri của R là:

i

Ri = F (R); 1 i n

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 = σLUONG35000

NV2 = σLUONG35000

(NV)

(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à:

1

DA1= σm (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

2

DA2= σm (DA)

MADA

TENDA	NS	VT
D2	Thiết kế trang Web bán hàng	12000	Hà Nội

3

DA3= σm

(DA)

MADA

TENDA	NS	VT
D4	Xây dựng phần mềm quản lý điểm	25000	Nam Định

4

DA4= σm (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à:

m

NV= σ (NV)

1

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

m

NV= σ (NV)

2

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}

Bước 8: Viết biểu thức phân mảnh ngang chính theo M‟

i

Ri = σm (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:

acc(mi )

card ( fi )

# acc(m j )

card ( f j )

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

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

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:

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

End

end

Pr‟ = Pr‟ - pk; F = F - fk;

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.

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