LỚP LIÊN THÔNG CNTT 2010 CÙNG NHAU HỌC TẬP
Bạn có muốn phản ứng với tin nhắn này? Vui lòng đăng ký diễn đàn trong một vài cú nhấp chuột hoặc đăng nhập để tiếp tục.

Bài tập CSDL phân tan(chuong 3)

2 posters

Go down

Bài tập CSDL phân tan(chuong 3) Empty Bài tập CSDL phân tan(chuong 3)

Bài gửi by nhuhaipt2004 Wed 09 Nov 2011, 3:39 pm

Tổng hợp cơ sở dữ liệu phân tán.

Chào mọi người. Nhằm giúp mọi người ôn bài tốt hơn. Mình đã tổng hợp 2 dạng bài tập có thể ra thi đó là phân mảnh ngang nguyên thủy(Primary Horizontal Fragment) và phân mảnh dọc(Vertical Fragment).Các bạn nên đọc kèm theo sách (Nguyên lý các hẹ cơ sở dữ liệu phân tán).Mình sẽ trình bày thuật toán phân mảnh ngang nguyên thủy trước.

I. Phân mảnh ngang nguyên thủy Primary Horizontal Fragment:
Đầu tiên chúng ta cần nắm rõ các định nghĩa sau, trước khi đi vào ví dụ, để ôn tập được tốt hơn các bạn nên đọc thêm sách và vở ghi chép bài trên lớp. Ví dụ mình sẽ trình bày ở đây được lấy từ sách ra.

1. Tính đầy đủ (Completeness): Tập các vị từ Pr được gọi là đầy đủ nếu và chỉ nếu xác suất mỗi ứng dụng truy xuất đến một bộ bất kỳ thuộc về một mảnh hội sơ cấp nào đó được định nghĩa theo Pr đều bằng nhau.
Ứng dụng ở đây là gì: ở đây ứng dụng có thể là nhiều câu truy vấn hoặc có thể chỉ là 1 câu truy vấn.

Ví dụ ứng dụng truy xuất các bộ của bảng PROJ theeo LOC như thế ứng dụng này sẽ có 3 câu truy vấn tương ứng với miền giá trị của LOC
P1: LOC = “Montreal”
P2: LOC =”NewYork”
P3: LOC =”Paris”
Trên đây đó chỉ là 1 ứng dụng có 3 câu truy vấn tương ứng với 3 giá trị của LOC. Tuy nhiên ta có thể giới hạn số lượng câu truy vấn của ứng dụng không nhất thiết khi nào số câu truy vấn cũng tương ứng với miền giá trị
Ví dụ: Mình có 1 ứng dụng chỉ truy xuất tới những dự án nào có ngân sách trên 200000 đô la(Trong khi đó miền giá trị của ngân sách là >=200000 và <200000)
Ok, đến đây chắc bạn đã hiểu rõ thế nào là 1 ứng dụng
Để hiểu rõ hơn định nghĩa các bạn đọc sách trang 125, ví dụ 5.9
Phân tích ví dụ: Trong ví dụ này có 2 ứng dụng truy xuất tới PROJ. Một, ứng dụng truy xuất theo vị trí, hai là ứng dụng chỉ truy xuất tới những dự án nào có ngân sách trên 200000 đô la.

Nhìn sang hình 5.8(trang 124) ở PROJ2 nếu xét ứng dụng truy cập theo vị trí. Thì mỗi bộ trong PROJ2 đều có tần truy xuất như nhau (select * from PROJ2 where loc=’new york’ – bộ nào cũng đều được 1 lần truy xuất , select * from PROJ2 where loc=’montreal’ – bộ nào cũng đều không được truy xuất và tương tự đối với select * from where loc=’Paris’). Như thế nếu Pr={loc=’montreal’,loc=’new york’,loc=’paris’} thì pr đầy đủ . Tuy nhiên nếu ta thêm 1 ứng dụng nữa chỉ truy xuất đến những dự án có ngân sách trên 200000 đô la thì xét trong PROJ2 chỉ có 1 bộ được truy cập tới (P3|CAD/CAM|250000|NewYork) như thế vi phạm tính đầy đủ.

2.Tính cực tiểu:
Quả thật để hiểu được tính chất này khiến mình mất rất nhiều thời gian. Để hiểu được tính chất này là phải hiểu được cụm từ sau: “có ít nhất một ứng dụng truy xuất đến fi và fj theo những cách khác nhau" (Trang 126). Thực ra ở trên mục I.1 mình đã nói ứng dụng là gì, nếu bạn đã nắm được nó ở trên thì đọc dòng này thì không có gì là khó hiểu cả. Ví dụ nha: Ứng dụng của mình là tập những câu truy vấn truy cập theo tên của dự án. Và miền giá trị của tên dự án là(Montreal, Newyork, Paris) như thế sẽ có 3 cách truy cập
(3 câu SQL) tương ứng.

Định nghĩa tính cực tiểu: Nếu một vị từ ảnh hưởng đến cách thực hiện phân mảnh (nghĩa là khiến cho phân mảnh f bị phân nhỏ hơn thành các mảnh, chẳng hạn fi và fj), thì phải có ít nhất 1 ứng dụng truy xuất fi và fj theo những cách khác nhau. Nói 1 cách khác khi f bị phân nhỏ ra thành 2 phân mảnh con fi và fj. Thì phải có liên đới tương ứng với fi và fj. Tức là mảnh nào cũng đều có ít nhất ứng dụng truy cập tới theo những cách khác nhau(Trang 126-SGK). Nếu tất cả các vị từ đơn giản của tập Pr đều có liên đới thì Pr cực tiểu.

Xét ví dụ 5.10 (trang 126). Trong thí dụ 5.5 ta đã có Pr={loc=’montreal’,loc=’new york’,loc=’paris’,budget<=200000,budget>200000} là đầy đủ và cực tiểu (kì vậy đầy đủ thì đúng, còn cực tiểu thì chưa tin—làm sao biết được nó cực tiểu – cái này qua phần thuật toán sẽ rõ, tạm thời ta chấp nhận nó là đầy đủ và cực tiểu). Nếu bây giờ ta thêm PNAME vào thì ... (khoan hãy đọc trong sách) ... thì mảnh PROJ1 chỉ phân nhỏ ra được chính nó thôi chứ không phân ra được 2 mảnh (fi và fj) như thế thì lấy đâu ra các mảnh mà có thẻ có ít nhất 1 ứng dụng truy xuất khác nhau đến các mảnh được tạo ra (thực tế ở đây chỉ có 1). Bây giờ quay lại đọc sách thử coi ...
Bây giờ không phải là ví dụ trong sách mà ví dụ sau

Xét 1 phân mảnh f sau :
PNO PNAME BUDGET LOC
P2 Database develop 100000 Newyork
P3 CAD/CAM 200000 Newyork
P3 Dzi dzi đó 200000 NewYork

Bây giờ xét vị từ p: budget <= 100000 vị từ này phân mảnh thành 2 mảnh f1(có budget <=10000 ) và 1 mảnh f2(có budget>100000), dễ dàng thấy ứng dụng truy cập theo budget sẽ truy cập tới 2 mảnh f1 và f2 theo 2 cách khác nhau đó là (1 : select * from f where budget<=100000, 2 : select * from f where budget>100000)  thỏa tính cực tiểu

3. Qui tắc cơ bản về tính đầy đủ và tính cực tiểu : nó khẳng định rằng một quan hệ hoặc một mảnh được phân hoạch 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.
fi của Pr’ : mảnh fi được định nghĩa theo một vị từ hội sơ cấp trên các vị từ Pr’

4. Thuật toán COM_MIN :
Nguyên liệu : R : Quan hệ ; Pr : tập các vị từ đơn giản(các ứng dụng sẽ truy vấn dựa vào các vị từ đơn giản này)
Thành phẩm : Pr’ : tập các vị từ đơn giản
Declare :
F : Tập các mảnh hội sơ cấp
Begin
Tìm một vị từ pi thuộc Pr sao cho pi phân hoạch R theo qui tắc 1 (-ít nhất phải có 2 mảnh con được tạo ra(nếu thỏa thì sẽ tạo ra fi và fk), 2 mảnh con đó được truy xuất bởi ít nhất 1 ứng dụng và theo những cách khác nhau)
Pr’  pi
Pr  Pr – pi
F  fi {fi là mảnh hội sơ cấp theo pi}
Do
Begin
Tìm một pj thuộc Pr sao cho pj phân hoạch một mảnh fz (fz ở đay
có thể là fi hoặc fk ở bước trước đã phân mảnh – z ở đây là
biến chạy)của Pr’ theo qui tắc 1
Pr’  Pr’ U pj
Pr  Pr – pj
F  F U fz
If tồn tại pk(k ở đây là biến chạy để quét lại các vị từ trong Pr’)
thuộc Pr’, là một vị từ không có liên đới(ko có phân
mảnh nào tương ứng với nó cả).
Begin
Pr’  Pr’ – pk
F  F – fk
End.
End
Until Pr’ đầy đủ (tần số truy xuất của ứng dụng(dựa theo Pr’) tới mỗi bộ của các mảnh bằng nhau)
End. {//ket thuc thuật toán COM_MIN}.

Sau khi đã có tập vị từ đơn giản Pr’, ta suy dẫn ra các vị từ hội sơ cấp....Đọc kỹ cuối trang 127, đầu trang 128

Khi đã nắm được các định nghĩa trên ta xét ví dụ 5.11(trang 128)
Ở ví dụ này chỉ có 1 ứng dụng truy xuất PAY, và ứng dụng này là 2 câu vấn tin ứng với 2 vị từ đơn giản (simple predicate)
P1 : SAL <= 30000
P2 : SAL > 30000
Vì vậy cho ra tập các vị từ đơn giản khởi đầu là Pr ={p1,p2}.
Ta tiến hành chạy tay thuật toán COM_MIN
Với i =1 ta có Pr’={p1} // Thỏa mãn qui tắc 1
Phân quan hệ thành 2 mảnh con : (1 mảnh có sal<=30000 và 1 mảnh có sal>30000). Xem hình 5.9(tr129)
Xét tính cực tiểu : 2 mảnh mà p1 tạo ra được truy xuất theo 2 cách khác nhau (1 : truy xuất theo pay<=30000 , 2 : truy xuất theo pay>30000) bởi cùng 1 ứng dụng. Do đó thỏa tính cực tiểu.
Thêm p1 vào Pr’
Đến đây ta kiểm tra tính đầy đủ của Pr’. Xem hình 5.9(tr129) ta có thể dễ dàng thấy được mỗi bộ trong mỗi mảnh được phân ra đều có cùng tần suất truy cập bởi ứng dụng truy cập theo PAY.
Sau khi đã có tập Pr’ ta đi tìm các vị từ hội sơ cấp có thể tạo ra từ Pr’
Trong ví dụ trên ta có tập vị từ hội sơ cấp M gồm 2 vị từ hội sơ cấp sau :
m1 : (SAL<=30000)
m2 : ~(SAL<30000)=SAL > 30000
Sau đó chúng ta định nghĩa hai mảnh Fs={PAY1,PAY2} theo M
Xem sách hình 5.9 trang 129
Cái khó đầu tiên ở phân mảnh ngang theo mình nghĩ là thuật toán COM_MIN. Sau khi đã tối giản được Pr thành Pr’. Các bước sau chạy tay hoàn toàn không khó.
Còn 1 ví dụ nữa trong sách sau ví dụ này, các bạn đọc có gì không hiểu thì post lên diễn đàn cùng trao đổi.


II.Phân mảnh dọc (Vertical Fragment)
Phân mảnh dọc là chúng ta gom những thuộc tính thường được truy xuất chung với nhau vào 1 mảnh.
Để tiến hành phân mảnh dọc chúng ta cần 1 số thông tin có liên quan đến ứng dụng(câu truy vấn) và các thuộc tính của quan hệ cần phân hoạch sau:

1. Ma trận sử dụng thuộc tính:
Ma trận sử dụng thuộc tính (USE_MATRIX)là ma trận mà mỗi phần tử của ma trận đó được định nghĩa như sau:


Ma trận sử dụng thuộc tính biểu diễn mối liên hệ giữa các câu truy vấn và các thuộc tính của quan hệ cần phân mảnh.

2. Ma trận ái lực thuộc tính AA_MATRIX:
Các phần tử trong ma trận sử dụng thuộc tính không đủ tổng quát để làm cơ sở cho việc tách và phân mảnh. Điều này là do chúng không biểu thị cho độ lớn của tần số ứng dụng. Số đo tần số có thể được chứa trong định nghĩa về số đo ái lực thuộc tính aff(Ai,Aj), biểu thị cho cầu nối (bond) giữa hai thuộc tính của một quan hệ theo cách chúng được truy xuất.
Ma trận ái lực thuộc tính gồm các phần tử là số đo ái lực giữa 2 thuộc tính Ai,Aj được định nghĩa như sau :



3. Ma trận ái lực tụ (CA_MATRIX) :
Sau khi đã tính được ma trận ái lực thuộc tính (AA_MATRIX) ta dùng thuật toán năng lượng nối BEA (Bond energy algorithm) để thực hiện gom nhóm các thuộc tính lại với nhau (các thuộc tính có số đo ái lực gần bằng nhau thì được xếp kề nhau)

Để tính được ma trận ái lực tụ ta cần đưa ra 1 số khái niệm sau :

1. Năng lượng cầu nối giữa 2 thuộc tính.

2. Cont(Ai,Ak,Aj) đây là số đo ái lực chung khi đặt thuộc tính Ak vào giữa các thuộc tính Ai, Aj.


Chú ý: ta có các Ai, Aj, Ak là các thuộc tính của quan hệ đang phân mảnh,ta giả sử có sãn vị trí Ai, Aj => ta đi tìm vị trí của Ak trong ma trận CA ở 1 trong 3 vị trí
- Bên trái Ai (Nếu bên trái Ai không có thuộc tính nào khác thì ta có công thức tính cont như sau):
Cont(A0,Ak,Ai) = 2bond(A0,Ak) + 2bond(Ak,Ai) – 2bond(A0,Ai) mà bond(A0,Abất kì) =0
=> Cont(A0,Ak,Ai) = 0 + 2bond(Ak,Ai) – 0
- Giữa Ai,Aj:
Cont(Ai,Ak,Aj) = 2bond(Ai,Ak) + 2bond(Ak,Aj) – 2bond(Ai,Aj)
- bên phải Aj(Nếu bên phải Aj không có thuộc tính nào khác thì ta có công thức tính cont như sau):
Cont(Aj,Ak,An+1) = 2bond(Aj,Ak) + 2bond(Ak,An+1) – 2bond(Aj,An+1) mà bond(Abất kì,An+1) =0
=> Cont(Aj,Ak,An+1) = 2bond(Ak,Aj) + 0 – 0

Sau khi đã đưa ra các khái niệm trên ta dùng thuật toán thuật toán BEA để gom các thuộc tính có số đo ái lực gần bằng nhau về cùng 1 nhóm.

Quá trình sinh ra ma trận ái lực tụ(CA) được thực hiện qua ba bước:
1. Khởi gán: Đặt và cố định một trong các cột của AA vào trong CA. Cột 1 được chọn trong thuật toán này.
2. Thực hiện lặp: Lấy lần lượt một trong n-i cột còn lại(trong đó i là số cột đã được đặt vào CA) và thử đặt chúng vào n-i vị trí còn lại trong ma trận CA.Chọn nơi đặt sao cho nó đóng góp nhiều nhất cho số đo ái lực chung được mô tả ở trên. Tiếp tục bước này đến khi không còn cột nào nữa để đặt.
3. Sắp thứ tự hàng: Một khi thứ tự cột đã được xác định, các hàng cũng cần được đặt lại để các vị trí tương đối của chúng phù hợp với các vị trí tương đối của các cột
Thuật toán BEA như sau:

Nguyên liệu: AA : ma trận ái lực thuộc tính
Thành phẩm: CA : ma trận ái lực tụ
Begin
{Khởi gán: Cần nhớ rằng AA là một ma trận nxn}
CA(,1)  AA(,1)
CA(,2)  AA(,2)
index  3 {index là vị trí của thuộc tính AAindex cần chèn vào}
while(index <= n) do
begin
for i from 1 to index-1 by 1 do
tính cont(Ai-1 , Aindex , Ai )
end for
tính cont(Aindex-1,Aindex,Aindex+1) {tính điều kiện biên}
loc  nơi đặt, được cho bởi giá trị có cont lớn nhất
for i from index to loc by -1 do {Dịch chuyển ma trận}
CA(,j)  CA(,j-1)
end for
CA(,loc)  AA(,index)
index  index + 1
end while
sắp thứ tự các hàng theo thứ tự tương đối của các cột
End.


4. Thuật toán Phân hoạch :
Mục đích của hành động tách thuộc tính là tìm ra các tập thuộc tính được truy xuất cùng nhau hầu như bắng các tập ứng dụng riêng biệt. Thí dụ nếu ta có thể biết được hai thuộc tính A1,A2, chỉ được truy xuất bới ứng dụng q1 và các thuộc tính A3,A4 được các ứng dụng khác truy xuất, chẳng hạn là q2,q3, thì quyết định phân mảnh là tầm thường. Công việc chính nằm ở chỗ là tìm ra một phương pháp theo kiểu thuật toán để xác định các nhóm này.
Trước khi đi vào thuật toán ta đưa ra các định nghĩa sau





Xét ma trận thuộc tính tụ (ở hình trên). Nếu tìm được một điểm nằm trên đường chéo cố định, hai tập thuộc tính sẽ được xác định. Một tập { A1 A2 A3 … Ai} nằm tại góc trên trái và tập thứ 2 { Ai+1 … An} ở về bên phải và nằm phía dưới của điểm này. Chúng ta gọi tập thứ nhất là tập các thuộc tính nằm trên góc đỉnh(Top Atrribute) kí hiệu là TA và tập thứ 2 là tập các thuộc tính nằm góc đáy (Bottom Attribute) kí hiệu là BA.
Gọi Q={q1,q2,...qq} là tập các ứng dụng, khi đó ta có các địng nghĩa sau :


Phương trình (1) định nghĩa tập thuộc tính được truy xuất bởi ứng dụng qi ; TQ là BQ tương ứng là các tập ứng dụng chỉ được truy xuât TA và BA, còn OQ là tập ứng dụng truy xuất cả hai.
Ở đây nảy sinh ra bài toán tối ưu hóa. Nếu có n thuộc tính trong một quan hệ thì sẽ có n-1 vị trí khả hữu có thể là điểm phân chia trên đường chéo của ma trận thuộc tính tụ cho quan hệ đó. Vị trí tốt nhất để phân chia là vị trí sinh ra các tập TQ và BQ sao cho tổng các truy xuất chỉ một mảnh là lớn nhất, còn tổng các truy xuất cả hai mảnh là nhỏ nhất. Vì thế chúng ta định nghĩa các phương trình chi phí như sau :

Mỗi phương trình trên đếm tổng số truy xuất đến các thuộc tính bởi các ứng dụng trong các lớp tương ứng của chúng. Dựa trên số liệu này, bài toán tối ưu hóa được định nghĩa là bài toán tìm điểm x (1<=x<=n) sao cho biểu thức :
là lớn nhất. Đặc trưng của biểu thức này là nó định nghĩa hai mảnh sao cho giá trị của CTQ và CBQ càng gần bằng nhau càng tốt. Điều này cho phép ta cân bằng tải trọng khi các mảnh xử lý được phân tán đến các vị trí khác nhau. Rõ ràng thuật toán phân hoạch có độ phức tạp tuyến tính theo số thuộc tính của quan hệ O(n).
Có hai điều phức tạp cần làm rõ. Điều đầu tiên ứng với hành động tách thuộc tính. Thủ tục trên tách tập thuộc tính làm hai. Đối với các tập thuộc tính lớn có thể cần phải phân hoạch thành m dòng.
Thiết kế một thuật toán phân hoạch m dòng có thể được nhưng chi phí tính toán cao. Dọc theo đường chéo của ma trận CA, chúng ta cần phải kiểm tra xem điểm nào làm cho z có giá trị lớn nhất. Vì thế độ phức tạp của một thuật toán như thế là O(2m). Đương nhiên định nghĩa của z phải được sửa lại cho những trường hợp có nhiều điểm phân tách.
Điều phức tạp thứ hai liên quan đến vị trí của khối thuộc tính tạo ra một mảnh. Thảo luận của chúng ta đến lúc này đã giả sử rằng điểm tách là duy nhất và nó chia ra ma trận CA thành một phân hoạch trên trái và phân hoạch thứ hai cũng được tạo bới những thuộc tính còn lại. Tuy nhiên phân hoạch này cũng có thể được tạo ra ở ngay trong ma trận CA. Trong trường hợp này chúng ta cần sửa lại thuật toán một chút. Cột tận trái của ma trận CA được xê dịch thành cột tận phải và hàng trên cùng được xê dịch xuống dưới đáy. Sau thao tác xê dịch này chúng ta kiểm tra n-1 vị trí trên đường chéo để tìm giá trị z lớn nhất. Ý tưởng của hành động tách là chuyển khối thuộc tính tạo ra một tụ đến góc trái trên cùng của ma trận, là nơi có thể xác định được nó dễ dàng. Với việc đưa thêm thao tác xê dịch vào, độ phức tạp của thuật toán phân hoạch tăng thêm một hệ số n và trở thành O(n2).
Với giả thuyết đã có trước một thủ tục xê dịch là SHIFT, chúng ta có thuật toán phân hoạch như dưới đây. Nguyên liệu là ma trận ái lực tụ CA, quan hệ R cần phân mảnh, ma trận sử dụng thuộc tính và ma trận tần số truy xuất. Thành phẩm là một tập các mảnh FR = {R1,R2} trong đó Ri thuộc {A1, A2, ..., An} và R1 giao R2 bằng các thuộc tính khóa của quan hệ R.
Thuật toán phân hoạch
Nguyên liệu : CA : ma trận ái lực tụ ; R : quan hệ ; USE : ma trận sử dụng thuộc tính ; acc : ma trận tấn số truy cập
Thành phẩm : F : tập các mảnh
Begin
{xác định giá trị z cho cột thứ nhất}
{các chỉ mục trong phương trình chi phí chỉ ra điểm tách}
Tính CTQ0
Tính CBQ0
Tính COQ0
Best  CTQ0 * CBQ0 – (COQ0)2
Do
Begin
For i from 1 to n-2 by 1 do
Begin
Tính CTQi
Tính CBQi
Tính COQi
z  CTQi * CBQi – (COQi)2
if z> best then
begin
best  z
ghi nhận điểm tách vào trong hành động xê dịch
end if
End – For
Gọi SHIFT(CA)
End – begin.
Until không thể thực hiện SHIFT được nữa

Xây dựng lại ma trận theo vị trí xê dịch
{K là tập khóa chính của R}


End.


II. Bài toán ví dụ :

Cho biết các thông tin sau:
A={A1,A2,A3,A4} A1: là khóa chính
Q={q1,q2,q3,q4}
S={S1,S2,S3}
A : Tập các thuộc tính
Q : Các câu truy vấn
S : Vị trí phân tán
Ref(qk)=1
Ma trận sử dụng thuộc tính:

A1 A2 A3 A4
q1 0 1 1 0
q2 1 1 1 0
q3 1 0 0 1
q4 0 0 1 0

Ma trận tần số truy cập tại các vị trí
S1 S2 S3
q1 10 20 0
Q2 5 0 10
Q3 0 35 5
Q4 0 10 0

Chạy tay bài toán:
Đầu tiên ta tính ma trận ái lực. Tính aff từng cặp thuộc tính với nhau ta có kết quả sau
Aff(A2,A3)=acc1(q1)+acc2(q1)+ acc3(q1)+ acc1(q2)+acc2(q2)+ acc3(q2)=45
Tương tự ta tính được aff các cặp thuộc tính khác và được ma trận ái lực thuộc tính như sau:
A2 A3 A4
A2 45 45 0
A3 45 55 0
A4 0 0 40

Sau khi đã tính được ma trận ái lực thuộc tính, ta đi tính ma trận ái lực tụ CA_MATRIX.
Tính chỉ số bond giữa hai thuộc tính

Bond(A2,A3)= = aff(A2,A2) * aff(A2,A3) + aff(A3,A2)*aff(A3,A3) + aff(A4,A2)* aff(A4,A3) = 4500

Tính tương tự ta có
Bond(A2,A4) =0
Bond(A3, A4)=0

Sau đó ta tính số đo đóng góp thực cho số đo ái lực chung khi đặt thuộc tính Ak vào giữa Ai và Aj theo cách sau:

Ta đi tìm vị trí của Ak trong ma trận CA ở 1 trong 3 vị trí
- Bên trái Ai (Nếu bên trái Ai không có thuộc tính nào khác thì ta có công thức tính cont như sau):
Cont(A0,Ak,Ai) = 2bond(A0,Ak) + 2bond(Ak,Ai) – 2bond(A0,Ai) mà bond(A0,Abất kì) =0
=> Cont(A0,Ak,Ai) = 0 + 2bond(Ak,Ai) – 0
- Giữa Ai,Aj:
Cont(Ai,Ak,Aj) = 2bond(Ai,Ak) + 2bond(Ak,Aj) – 2bond(Ai,Aj)
- bên phải Aj(Nếu bên phải Aj không có thuộc tính nào khác thì ta có công thức tính cont như sau):
Cont(Aj,Ak,An+1) = 2bond(Aj,Ak) + 2bond(Ak,An+1) – 2bond(Aj,An+1) mà bond(Abất kì,An+1) =0
=> Cont(Aj,Ak,An+1) = 2bond(Ak,Aj) + 0 – 0

Theo cách trên ta tìm vị trí để chèn A4 vào và có các kết quả như sau:
Theo thứ tự A0A4A2A3
Cont(A0,A4,A2)=2bond(A0,A4) + 2bond(A4,A2) – 2 bond(A0,A2) = 0 + 0 - 0=0
Theo thứ tự A2,A4,A3
Cont(A2,A4,A3)= -9000
Theo thứ tự A2,A3,A4,A5
Cont(A3,A4,A5) = 0
Dựa vào các chỉ sô đóng góp thực tính được ở trên ta thấy có 2 chỉ thứ tự trả về cùng kết quả là 0, ta chọn một trong 2 thứ tự trên đó là thứ tự A2,A3,A4,A5 do đó đặt A4 ngay sau A3 (vì Cont(A3,A4,A5) = 0) và kết quả ta thu được ma trận CA như sau:
A2 A3 A4
A2 45 45 0
A3 45 55 0
A4 0 0 45

Sau khi đã có được ma trận CA ta tiến hành chạy tay thuật toán phân mảnh dọc
(trong bài toán ví dụ này ta không cần gọi tới thủ tục SHIFT để xê dịch các thuộc tính).

AQ(q1) = {A2,A3}
AQ(q2) = {A2,A3} (Không xét A1 vì A1 là thuộc tính khóa)
AQ(q3) = {A4}
AQ(q4) = {A3}

1. Với TA ={A2}; BA ={A3,A4}

TQ = Ф ; BQ = {q3,q4}
OQ = Q \ (TQ U BQ) = {q1,q2}
CTQ = = 0 (vì TQ = Ф)
CBQ = = acc1(q3) + acc1(q4) + acc2(q3) + acc2(q4) + acc3(q3) + acc3(q4) = 0 + 0 + 35 + 10 + 5 + 0 =50

COQ = = acc1(q1) + acc1(q2) + acc2(q1) + acc2(q2) + acc3(q1) + acc3(q2) = 10 + 5 + 20 + 0 + 0 + 10 = 45

CTQ * CBQ – COQ2 = -2025 (-452)
2. Với TA ={A2,A3}; BA ={A4}
TQ = {q1,q2,q4}
BQ = {q3}
OQ = Q\{TQ U BQ} = Ф
CTQ = 55
CBQ = 40
COQ = 0
CTQ* CBQ – COQ2 = 2200

 So sánh kết quả ở hai bước ta được kết quả phân hoạch sau khi đã thêm thuộc tính khóa vào như sau
Mảnh 1 : A1,A2,A3
Mảnh 2 : A1, A4



nhuhaipt2004
Administrator
Administrator

Tổng số bài gửi : 96
Join date : 26/08/2010

Về Đầu Trang Go down

Bài tập CSDL phân tan(chuong 3) Empty Re: Bài tập CSDL phân tan(chuong 3)

Bài gửi by bienxanh Sat 12 Nov 2011, 8:45 am

đọc xong vẫn không hiểu chi hết, chán quá đi. Chắc môn này nốc ao quá,hu...hu....

bienxanh
Thành viên mới
Thành viên mới

Tổng số bài gửi : 10
Join date : 11/10/2010

Về Đầu Trang Go down

Về Đầu Trang

- Similar topics

 
Permissions in this forum:
Bạn không có quyền trả lời bài viết