Phân mảnh dữ liệu trong thiết kế cơ sở dữ liệu phân tán dựa vào kỹ thuật phân cụm hướng tri thức

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

24
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết Phân mảnh dữ liệu trong thiết kế cơ sở dữ liệu phân tán dựa vào kỹ thuật phân cụm hướng tri thức trình bày sử dụng kỹ thuật phân cụm hướng tri thức cho cả hai bài toán phân mảnh ngang và phân mảnh dọc dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phân mảnh dữ liệu trong thiết kế cơ sở dữ liệu phân tán dựa vào kỹ thuật phân cụm hướng tri thức

Lê Văn Sơn, Lương Văn Nghĩa PHÂN MẢNH DỮ LIỆU TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN DỰA VÀO KỸ THUẬT PHÂN CỤM HƯỚNG TRI THỨC FRAGMENTATION IN DISTRIBUTED DATABASE DESIGN BASED ON KNOWLEDGE-ORIENTED CLUSTERING TECHNIQUE Lê Văn Sơn1 , Lương Văn Nghĩa2 1 Trường Đại học Sư phạm, Đại học Đà Nẵng; Email: levansupham2004@yahoo.com 2 Trường Đại học Phạm Văn Đồng; Email: nghia.itq@gmail.com Tóm tắt – Bài toán tối ưu hóa cơ sở dữ liệu phân tán bao gồm các Abstract – The optimization problem of data fragmentation bài toán: phân mảnh và định vị dữ liệu. Có nhiều phương pháp tiếp is requiring to several interrelated problems including: Data cận khác nhau và nhiều thuật toán được đề xuất để giải quyết các fragmentation and Data allocation. Although we had many different bài toán này. Tuy nhiên, độ phức tạp của thuật toán vẫn còn là một algorithms to approach solving problems, the complexity of thách thức. Trong bài báo này, chúng tôi sử dụng kỹ thuật phân cụm algorithm is always a big challenge to solve. In this paper, hướng tri thức cho cả hai bài toán phân mảnh ngang và phân mảnh we presented a knowledge-oriented clustering technique that is dọc dữ liệu. Độ đo tương tự sử dụng trong hai thuật toán là các độ applying both of vertical fragmentation and horizontal fragmentation đo được phát triển từ các độ đo cổ điển. Kết quả thử nghiệm trên problems. Similarity measures are used in both of algorithms which các tập dữ liệu nhỏ hoàn toàn trùng khớp với kết quả phân mảnh were built in the traditional measures. The experimental result of dựa vào các thuật toán cổ điển. Thời gian thực hiên phân mảnh dữ small data files and the fragmentation result based-on traditional liệu cũng được giảm đáng kể (mặc dù độ phức tạp thuật toán trong algorithm are similar. The execution time of fragmented data is trường hợp tổng quát vẫn chưa thay đổi). significantly reduced. (Although, the complexity of algorithm in the general case is still un-changed). Từ khóa – cơ sở dữ liệu phân tán; phân mảnh; định vị; độ đo tương Key words – distributed database; fragmentation; allocation; tự, phân cụm; kỹ thuật phân cụm hướng tri thức. similarity measures; clustering; knowledge-oriented clustering technique. 1. Đặt vấn đề điển và khai phá dữ liệu [2]. Trong môi trường phân tán, mỗi đơn vị dữ liệu (item) Nội dung chính của bài báo được tổ chức như sau: Các được truy xuất tại các trạm (site) thường không phải là một khái niệm cơ sở được trình bày trong Mục 2. Mục 3, trình quan hệ mà chỉ là một bộ phận của quan hệ. Vì vậy, để tối ưu bày thuật toán phân cụm hướng tri thức. Mục 4, 5 lần lượt hóa quá trình thực hiện các truy vấn, các quan hệ của lược trình bày thuật toán phân mảnh dọc, phân mảnh ngang đề đồ toàn cục (global scheme) được phân mảnh thành các đơn xuất. Mục 6 là phần kết luận. vị dữ liệu. 2. Một số khái niệm cơ sở Các loại phân mảnh dữ liệu bao gồm phân mảnh dọc, phân mảnh ngang, phân mảnh hỗn hợp (mixed) và phân 2.1. Phân mảnh dọc mảnh suy dẫn (derivate). Hai thuật toán cổ điển gắn liền với Phân mảnh dọc là phân rã tập thuộc tính của lược đồ phân mảnh ngang và phân mảnh dọc lần lượt là thuật toán quan hệ R thành các lược đồ con R1 , R2 , .., Rm , sao cho PHORIZONTAL và thuật toán BEA [5]. Nhiều tác giả đã đề các thuộc tính trong mỗi lược đồ con là thường được truy xuất các thuật toán cải biên hai thuật toán này như Navathe vấn cùng nhau. Để thể hiện mức độ hay cùng được truy và đồng sự (1984), Cornell và Yu (1987), Chakravarthy và vấn cùng nhau, Hoffer và Severance đưa ra khái niệm ái lực đồng sự (1994), Bellatreche (2000), Schewe (2002),.. Tuy thuộc tính (attribute affinity) [13]. nhiên, độ phức tạp của các thuật toán này là khá lớn, phân Nếu Q = q1 , q2 , .., qm là tập các ứng dụng, mảnh dọc là O(n2 ) với n là số lượng thuộc tính, phân mảnh R(A1 , A2 , .., An ) là một lược đồ quan hệ. Mối quan hệ giữa ngang là O(2m ) với m là số bản ghi [5][8]. ứng dụng qi và thuộc tính Aj được xác định bởi giá trị sử Trong thời gian gần đây, một số tác giả đã kết hợp giải dụng [2]: bài toán phân mảnh và bài toán định vị bằng các thuật toán 1, Aj có tham gia qi tối ưu [9][14] hay sử dụng các thuật toán heuristic [1][9], use (qi , Aj ) = (1) 0, Aj không có tham gia qi thời gian thực hiện các thuật toán này giảm đáng kể so với các thuật toán cổ điển mặc dù độ phức tạp của giải thuật Đặt Q(A, B) = q ∈ Q|use(q, A).use(q, B) = 1. Ái lực trong trường hợp tổng quát vẫn chưa được cải thiện. Sử giữa 2 thuộc tính Ai , Aj : dụng kỹ thuật luật kết hợp trong khai phá dữ liệu để phân ! mảnh dọc dữ liệu đã được đề cập [10], tuy vậy các kỹ thuật X X Aff(Ai , Aj ) = refl (q) ∗ accl (q) (2) khai phá dữ liệu khác cũng chưa được các tác giả quan tâm q∈Q(Ai ,Aj ) ∀Sl ứng dụng. Trong bài báo này, chúng tôi đề xuất sử dụng thuật toán Trong đó, refl (q): số lần cặp thuộc tính (Ai , Aj ) được phân cụm hướng tri thức cho 2 bài toán phân mảnh dọc và tham chiếu trong ứng dụng q tại trạm Sl; accl(q): tần số truy phân mảnh ngang. Các độ đo tương đồng (similarity) được xuất ứng dụng q đến các thuộc tính (Ai , Aj ) tại trạm Sl . phát triển dựa trên các độ đo đã có trong các thuật toán cổ Thuật toán BEA thực hiện gồm 2 giai đoạn chính: 59
dù tính sinh ra 1 ma trận ái lực tụ thuộc tính CA (Cluster TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II át Affintity matrix) có số đo ái lực chung AM (global ợp (1). measure) affinity Hoán vị hàng, cộtnhất là lớn của ma [5].trân ái lực thuộc tính sinh Một quan hệ tương đương (quan hệ 2 ngôi thỏa các tính ra 1 ma trận ái lực tụ thuộc tính CA (Cluster Affintity matrix) chất phản xạ, đối xứng và bắc cầu) xác định trên U được gọi đã (2).áiTìm điểm AM phân(global hoạchaffinity tập thuộc tính là từ lớn ma có số đo lực chung measure) là một quan hệ không phân biệt trên U. ệu trận tụ thuộc tính CA bằng phương pháp vét cạn, sao nhất [5]. 3. Thuật toán phân cụm hướng tri thức cho (2). [8]: Tìm điểm phân hoạch tập thuộc tính từ ma trận tụ ng thuộc tính CA bằng phương pháp vét cạn, sao cho [8]: Thuật toán phân cụm hướng tri thức KO-Knowledge- Z= CTQ *CBQ – COQ2 đạt cực đại, với: Z = CTQ ∗ CBQ − COQ2 đạt cực đại, với: Oriented Clustering dựa vào lý thuyết tập thô đầu tiên án CTQ   ref j (q j )acc j (qi ) được đề xuất bởi nhóm tác giả Shoji Hirano and Shusaku ng qTQ Sj X X Tsumoto (2001) [12]. Đây là thuật toán phân cụm tự động CTQ = refj (qj )accj (qi ) đã q∈TQ ∀Sj xác định số cụm dựa vào bộ dữ liệu khảo sát. Ý tưởng chính ]. CBQ  CBQ =  X ref jX (q j )acc j (q i ) refj (qj )accj (qi ) của thuật toán phân cụm này gồm 2 giai đoạn [3]: 1. Xây dựng 1 quan hệ tương đương ban đầu trên tập các hư qBQ Sj q∈BQ ∀Sj đối tượng cần phân cụm. 2.   ref X X 2. Hiệu chỉnh các quan hệ tương đương bằng cách sử c.  COQ COQ = refj (qj (j )acc j (q j )acc q i ) j (qi ) dụng một ngưỡng Tk dựa trên độ không phân biệt. qOQ Sj q∈OQ ∀Sj c, Quá trình lặp cập nhật lại Tk cho đến khi thu được phân cụm tốt nhất. A1 A2 .. Ai A i+1 .. An Thuật toán này được nhóm tác giả C.L Bean, A1 C.Kambhampati hiệu chỉnh và thử nghiêm (2008) [4] (bài báo của nhóm tác giả chỉ xây dựng lại quan hệ tương đương .. TA ban đầu dựa vào ý tưởng đường “đẳng trọng” so với cách ủa Ai xây dựng dựa trên gradient của nhóm tác giả Shoji Hiran, m, Shusaku Tsumoto). Các kết quả thử nghiệm của 2 nhóm tác Ai+1 giả trên nhằm minh họa cho thuật toán, chưa đưa ra các ứng là dụng trong thực tế. độ BA Sử dụng thuật toán này để phân mảnh dữ liệu, chúng tôi và An đã đề xuất quan hệ tương đương ban đầu dựa trên khoảng te Hình 1. 1:Ma Hình Matrận trận tụ thuộctính tụ thuộc tính CACA cách trung bình giữa các đối tượng. Thuật toán phân cụm hướng tri thức chúng tôi sử dụng Trong Trong đó, đó, g, cụ thể như sau: AQ(q AQ(qii)= {A ) ={A |use(qi,A j| juse(q j)=1}; i, A TQ={qi | AQ(qi) TA} j ) = 1}; Input: U= Tập các đối tượng cần phân cụm hệ TQ = {qi |AQ(qi ) ⊆ TA}; BQ= i | AQ(qi)  BA}; OQ=Q\ {TQBQ} (Mỗi đối tượng phải được mô tả các thông tin cần thiết ởi BQ ={q{q |AQ(q ) ⊆ BA}; i i để xây dựng độ tương tự). Độ=phức OQ Q{TQtạpcủa thuật toán tỉ lệ với n2 ∪ BQ}. Output: Các phân cụm (tương ứng với các phân mảnh 2.2. Độ Phân mảnh phức tạp của thuật toán tỉ lệ với n2 . ngang dữ liệu) 2.2. Phân Phânmảnh mảnhngang ngang là phân chia tập các bản ghi Method: Bước 1: Xây dựng ma trận độ tương tự S=S(ti , tj ) giữa thành các tập bản ghilà nhỏ Phân mảnh ngang phânhơn. Phân chia tập cácmảnh bản ghingang dựa thành các Ái tập bản ghi nhỏ hơn. Phân mảnh ngang dựa vào các vị điều tất cả các cặp đối tượng(ti , tj ). vào các điều kiện truy vấn được thể hiện qua các từ kiện truy vấn được thể hiện qua các vị từ đơn giản có dạng: Bước 2: Chỉ định một quan hệ không phân biệt ban đầu đơn giản có dạng: Ri cho từng đối tượng. Tổng hợp để có được một phân cụm 2) P : Aj θ ĐặtP:PA j  ban đầu. r = {p1 , p2 , .., pk } là tập các vị từ đơn giản được trích raĐặt Bước 3: Xây dựng ma trận bất khả phân biệt Γ = từ tập Pr các = {pứng 1, pdụng. k} là Một 2, .., p hộitập cácđược vị từ vị từ xâyđơn giản dựng từ Aj) Pr có dạng: ν(ti , tj ) để đánh giá chất lượng phân cụm. được trích ra từ tập các ứng dụng. Một hội vị từ được p1 ∗ ∧p2 ∗ ∧.. ∧ pn ∗ (3) Bước 4: Sửa đổi phân cụm theo một quan hệ bất khả xây dựng từ Pr có dạng: phân biệt mới Rimod cho từng đối tượng để đạt được một ác Trong đó pi ∗là vị từ mang 1 trong giá trị là pi hay ¬pi p1*  p2* ..pn* (2.3) phân cụm sửa đổi. ực Thuật toán PHORIZONTAL sử dụng các hội vị từ Bước 5: Lặp lại bước 3 và 4 cho đến khi thu được một có thểTrong đó ptừi*Plàr , vị xây dựng để từ tìmmang 1 trong các điều kiện giá phântrịmảnh là pi phân cụm ổn định. ngang dữ liệu [11]. Quan hệ r(R) sẽ được phân mảnh thành Chi tiết của thuật toán có thể tham khảo [4][12]. Điểm {r1 (R), r2 (R), .., rk (R)}, với ri (R) = σFi (r(R)), 1 ≤ i ≤ k; cần lưu ý là chúng tôi đề xuất cách xây dựng quan hệ không Fi là một vị từ hội sơ cấp (mj ). phân biệt ban đầu khác với 2 nhóm tác giả Shoji Hirano, 2.3. Hệ thống thông tin và quan hệ không phân biệt Shusaku Tsumoto và C.L Bean, C.Kambhampati như sau: Hệ thống thông tin là một cặp SI=(U, A), trong đó U là Quan hệ không phân biệt ứng với thuộc tính thứ i: tập hữu hạn các đối tượng U={t1 , t2 , .., tn }, A là tập hữu Ri = {(ti , tj ) ∈ U × U : d(ti , tj ) ≤ Thi với j = 1, 2, hạn khác rỗng các thuộc tính. . . . , n} 60
Định nghĩa 1. Độ đo tham chiếu của giao tác qi {q1, q2, q3, q4}, và F = {f1, fLê Văn Sơn, Lương Văn Nghĩa 2, f3, f4} = {45, 5, 75, 3}. với thuộcTrongtính đó Aj d(t ký i hiệu , tj ) làM(q i, Ajcách khoảng Mij2làđốitần ) haygiữa suấttham tượng - TậpTừtần giảsuất thiếtthựcta có cácứng hiện vectorvới đặc trưng tập các tham giao tác gia qphân giao tác i cụm. tham chiếu đến thuộc tính A j được xác định {q chiếu: 1 , q2 , q3 , q4 }, và F = {f1 , f2 , f3 , f4 } = {45, 5, 75, 3}. bởi giá trị: Ngưỡng Thi được xác định như sau: Từ giả thiết ta có các vector đặc trưng tham chiếu: q q q q 1 2 3 4 M(qi, Aj) = Mij= nuse(qi ,TẠP Aj )* fi  VA1= 45q1 0 q2 0 q3 0 q4 CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ ………………. X VA12== 045 5 0 75 0 0 0 Với: fi làThtần i =suất thực(1  − s(t hiện củai , tjgiao tác − )) /(n qi 1) và  (4) VA23== 450 5 5 0 75 3 0 j=1,j6=i use(qi, Aj) xácĐịnh định nghĩa bởi công 1. Độthứcđo(2.1). tham chiếu của giao tác qi {qVA 1, q3 = 045 0 5 = {f 2, q3, q4}, và F75 4= 0 1,3f2,3f3, f4} = {45, 5, 75, 3}. Với s(t , t ) là độ tương tự của 2M(q đối tượng ti , tj .M [2].là tần suất VA4 = 0 0 75 3 với thuộc i j tính A ký hiệu Định nghĩa 2. Vector đặc trưngi, tham j Aj) haychiếu ijVA j Từ giả thiết ta có các vector đặc trưng tham 4. giao của thuộc tính Phân tác Aqji ứng mảnh tham dọc chiếu với cơ đến hệtham thuộc sởchiếu dữ tính của liệu các phân Ajtán được giao tácxác dựa vàođịnh MaMa trận độ tương chiếu: tương trận độ tự S4x4 tự = (s(A S4x4 k , Akl )) = (s(A ,A l)) k=1,4;l=1,4 k=1,4;l=1,4 bởi giá thuật trị: toán phân cụm (q1, q2, ..,qm) được xác định như sau: hướng tri thức A1 A2 A3 q1 qA2 4 q3 q4 Để chuyểnM(qiq, bàiAj) toán = Mphân ij = usemảnh (qi ,dọc A j )trọng * f i hệ cơ sở dữ A1 1 0VA1=0.9918 45 00 0 0 1 liệu phân tán, các q … q giả thiết2 bài toán được mchuyển đổi sang A2 1VA2=0.0073 0 50.9970 75 0 Với: giả thiết bài fi là toán tầncụm phân suấtdựathực vàohiện các của kháigiao niệmtác sau:qi và A3 VA3= 45 50.0026 1 0 3 VAj= M1j M2j … Mmj A4 01 75 use(q 4.1. ) xácvàđịnh i, Ajtính Thuộc bởiđặc Vector công thức trưng (2.1). tham chiếu VA4= 0 3 Kết quả phân mảnh bằng thuật toán phân cụm 4.2. Độ Địnhđo nghĩa tương Định 1.đồng của nghĩa Độ đo 2.2Vector tham thuộc chiếu tính đặc trưngtáctham của giao qi vớichiếu thuộcVAj Kết quả phân mảnh bằng thuật toán phân cụm hướng tri tính hướng tri thức thức thu được:thu được: củaAjthuộc Định ký hiệu M(qi, nghĩatính 3. A Độ Aj) hay tham j ứng đo với Mij làchiếu tương đồng tần suất của của giao cáctác 2 thuộc qi tác giao Ma trận độ tương tự S4x4= (s(Ak, Al)) k=1,4;l=1,4 tham chiếu đến thuộc tính Aj được xác định bởi giá trị Cụm Tập thuộc tính tính A(q , ql 2có k, 1A được xác 2 m)vector , ..,q đặc định trưngnhư sau:chiếu tương tham Cụm ATập 1 thuộc A2 A tính 3 A4 M(q , A ) = M = use(q , A ) ∗ fi 1 1 {A1, {A A3} } ứng với bộ các i j giao tácij(qq1,1 q2, ..,q i i A1 {A 1 ,A 0}1 , A30.9918 0 q:2 Với: fi là tần suất thực hiện của giao tác q… m): qm 2 2 {A4 ,A } i và use(qi , Aj ) A22 12 40.0073 0.9970 VAđịnh xác k = (M , M2kthức bởi1kcông , .., (1). Mmk) Nhận xét: A3 1 0.0026 Nhận xét: VA M M … M Kết Kếtquả quảphân phân mảnh nàytrùng trùngkhớp khớpvới với VAl = Định (M1l2. nghĩa j=, .., M 1j , MVector 2l đặc ml )trưng 2j tham chiếu VAj mj của thuộc A 4 1 kết quả mảnh này kết quả phân tính Aj ứng với tham chiếu của các giao tác (q1 , q2 , .., qm ) phân được xácđo định bởi độ đo cosin: mảnhmảnh dọc dọc theo Kết theo thuậtquả toánphân thuật toán BEA. mảnh BEA. bằng thuật toán phân cụm Độ 4.2.xác được định tương như sau:đồng của 2 thuộc tính hướng tri thức thu được: Định nghĩa 3. Độ m đo tương đồng của 2 thuộc Phânmảnh 5. 5.Phân mảnhngang ngang hệ cơsởsởdữ hệ cơ dữliệuliệu phân phân tántán dựadựa vào tính VA Akk, *AVA l có VA q1 2 Mvector qM2 ik *... M il m Mđặc trưng q ... Mtham chiếu tương cụm Cụm vào thuật toán phân cụm hướng tri thức thuật toán phân hướng Tập tri thuộc thức tính jl= s(Ak, Aứng l) =  1j i 1 2j mj 1 {A1, A3} với VAkbộ* các VAl giao tác m (q1, q2, ..,q m m):: (4.1) Tươngtự như Tương như phân mảnh phân mảnh 2 dọc2trong dọc {A ,Atrong hệ hệ cơ cơ sở liệu sở dữ dữ 4} 4.2. Độ đo tương đồng của M VAk = (M1k, M2k, ..,ikMmk) i   1 2 thuộc 2 * i 1  tínhM 2 il phân liệu phân thuật tán, Nhận toán việc chuyển tán,xét: đổi giả thiết phân mảnh việc chuyển đổi giả thiết phân mảnh PHORIZONTAL dựa trên các khái ngang niệm [2] cơ từ sở Định nghĩa 3. Độ đo tương đồng của 2 thuộc tính Ak , Al ngang [2] từ thuật toán PHORIZONTAL dựa trên các có 2 vectorVA đặcl = (M1l, M2l, .., Mml) trưng tham chiếu tương ứng với bộ các giao sau: Kết quả phân mảnh này trùng khớp với kết quả 4.3. Phân mảnh dọc): dựa vào thuật toán phân cụm khái niệm cơ sở sau: tác (q1 , qđược xác định bởi độ đo cosin: 2 , .., qm phân mảnh 5.1. Vector hóa cácdọc bảntheo ghi thuật của một toán quanBEA hệ[A9]. hướng tri thức 5.1. Vector hóa các bản ghi của một quan hệcác vị từ VAk = (M1k , M2k , .., Mmk ) m Xét quan mảnh hệ r(R)={T ngang 1, T hệ 2 , cơ .., Tsởl }, dữ tậpliệu phân tán dựa  Để minh họa 5. Phân VAl = (Mphân mảnh dọc dựa vào 1l , M2l , .., Mml ) M ik *thuật M il toán đơn giản rút trích từ các ứng dụng trên r(R) là hệtoán r(R)={T1,cụm ..,Tl}, tập các vị từ Pr = vào {Pr1thuật Prmphân VAk *VA Xét quan T2, hướng tri các thức phân cụms(Ahướng k, Al) = tri thức, sử ldụng lại igiả 1 thiết ví dụ bài , Pr2 , .., }. Vector hóa nhị phân bản ghi được xác địnhVA bởi *độVAđo cosin: (4.1)đơn giản rút trích Tương từ các như ứngphân dụng mảnh trên r(R) dọc là trongPr={Pr 1, hệ cơ sở dữ toán phân mảnh dọc kdựa vào thuật toán m BEA được m theo qui tắc:   l m}. Vector hóa nhị phân các bản ghi theo qui 2 2 MP m * M il Pr2, ..,Prliệu phânPrtán, việc chuyển Prj đổi ... giả Prmthiết phân mảnh ik trình bày trong [2]: i 1 Miki ∗1Mil Pr ... VAk ∗ VAl tắc: 1 2 ngang T1[2] Pra1từ11 thuật Pr2a12 ..toán ...PrPHORIZONTAL dựa trên các i=1 a1j.. Pr ... a1m - Tậps(Acác k , Athuộc l) = tính: kVA Att = {A k k ∗ kVAl k = s 1, A m2, A3, A4} s m (5) j m 4.3. Phân mảnh dọc - Tập các giao tác: Q = {q1, q2, q3i=1 dựa vào P thuật M , q4}ik 2 ∗ toán M P phân 2 il cụm khái niệm ... cơ ... sở T1 a11 a12 .. a1j .. a1m ...sau: ... ... ... ... i=1 T ai1 a ... aij ... aim hướngMa tri trận thứcsừ dụng: .. i .. i2 .. 5.1.TiVector ... a ...hóa ... a các .. bản ... ghi a ... của .. ... một a ... quan hệ Để minh họa 4.3. Phân mảnh dọc phân dựa A1 A2 A3 A4 vào mảnh thuật dọc toán dựa phân vào cụm thuật hướng toán T l i1 a l1 i2 al2 ... ij a lj ...im alm tri thức .. Xét quan .. hệ r(R)={T1, T .. 2, ..,Tl}, tập các vị từ phân cụmqhướng 1 1 tri0 thức, 1 sử 0dụng lại giả thiết ví dụ bài Tl al1 a(l2 .. alj .. alm Để minh toán phânqhọa 2mảnh 0phândọc1mảnh dựa 1 dọcvào 0dựathuậtvào thuậttoántoánBEA được phân đơn giản rút trích 1, từ khicácTi[Pr ứng j] =dụngtruetrên r(R) là Pr={Pr1, ∀aij = cụm hướng trình bàytriqtrong 3thức,0 [2]: sử 1dụng 0lại giả1 thiết ví dụ bài toán phân Pr2, ..,Prm}. Vector  1, khi 0, khihóa Tinhị Ti[Pr [Pr j=] j ]phân falsecác bản ghi theo qui true [A8] q4vào0thuật0 toán1BEA1được trình bày trong [2]: aij   mảnh dọc dựa tắc: 0, khi Ti [Pr j ]  false - -Tập Tập các thuộc các thuộc tính: tính Att = {A Att, A 1 = {A 1, A2, A3, A4} 2 , A3 , A4 } 5.2. Độ đo tương đồngPrcủa 1 2Prvector 2 .. nhị Prj phân .. Prm - Tập tầnTập - -Tập các các suấtgiaothực giao tác Q tác: hiên= ứng {qQ , với = q {q , qtập 1,, qqcác , 2} q 3giao , q 4}tác: T a a .. a .. a1m 1 2 3 4 5.2. ĐộXétđo tươngxđồng 2 vector i và xjcủa 1 11 , được 2 vector 12 biểu diễn nhịbằng 1j phân các biến nhị Ma trận sử Ma dụng: trận sừ dụng: .. .. phân. Giả sử các biến nhị phân có cùng trọng số. Ta có bảng .. Ti ai1 ai2 .. aij .. aim A1 A2 A3 A4 sự kiện như Bảng 1. Trong đó q là số các biến nhị phân bằng .. .. .. 4 q1 1 0 1 0 1 đối với cả 2 vector xi và xj , s là số các biến nhị phân bằng Tl al1 al2 .. alj .. alm q2 0 1 1 0 0 đối với xi nhưng bằng 1 đối với xj , r là số các biến nhị q3 0 1 0 1 phân bằng 1 đối với xi nhưng bằng  0 đối 1, khi [Prxj ]j ,  Tivới t là số các true q4 0 0 1 1 avới biến nhị phân bằng 0 đối  cả 2 vector x và x [2]. 0, khi Ti [Pr j ]  false ij i j  - Tập tần suất thực hiên ứng với tập các giao tác: 61
nhưng bằng 0 đối với xj, t là số các biến nhị phân bằng p1 p2 T1 1 0 0TẠP đốiCHÍ vớiKHOA cả 2 HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 1(74).2014.QUYỂN II vector xi và xj [2]. T2 0 1 Bảng Bảng 1: Bảngsự 1. Bảng sựkiện chobiến kiện cho biếnnhịnhị phân phân Nhận xét: Kết quả phân T3 mảnh 1 này 0trùng khớp với kết quả phân mảnh ngang theo T4 thuật 0toán PHORIZONTAL. 0 Đối tương j 1 0 Tổng 6. Kết luận T 5 0 1 1 q r q+r T6 1 0 Đối tượng i Trong bài báo này chúng T7 tôi1trình bày 0 giải pháp phân 0 s t s+t mảnh dọc và ngang của hệ T8 cơ sở0 dữ liệu 1 phân tán dựa vào Tổng q+s r+t p thuật toán phân cụm hướng tri thức. Với giải pháp này chúng Sự khác nhau của 2 vector xi và trên Sự khác nhau của 2 vector xi và xj dựa xj dựa trên các các biến nhị đã đềKết tôi 5.4. quả xuất đượcphân cách mảnh chuyểnngang đổi giả quanthiết các hệbài Emp toántheo biến nhị phân đối xứng (symmetric phân đối xứng (symmetric binary dissimilarity) là: binary phânthật toán phân cụm hướng tri thức mảnh cổ điển trở về giả thuyết cho bài toán phân cụm. dissimilarity) là: Trong thuật toán phânCụm cụm hướng Tập các bảntri thức, ghi chúng tôi có r+s d(xi , xj ) = (6) đề xuất cách xây dựng1quan hệ T1, T3, T6, T7 ban đầu dựa tương đương r sq + r + s + t vào ngưỡng khoảng cách, đây làTđiểm khác biệt với 2 thuật d ( xi , x j ) (5.1) 2 2, T5, T8 q r s t toán của 2 nhóm tác giả3 Shoji Hirano, T4 Shusaku Tsumoto và Sự khác nhau của 2 vector xi và xj dựa trên các biến nhị C.L Bean, C.Kambhampati đã đề xuất trước đó. Sựđối phân bất khác nhau xứng của 2 vector (asymmetric và xj dựa trên các binaryxidissimilarity) Nhận xét: Kết quả thử nghiệm trên các bộ dữ liệu trong [13] cho biến nhị phân bất đối xứng r + s(asymmetric binary thấy kết quảKếttrùng quả lắp phân vớimảnh này kết quả có trùng được từ khớp với toán 2 thuật kết quả d(xi , xj ) = (7) dissimilarity) là: q+r+s phân mảnh phân mảnh cổ điển theo thuật toán và là PHORIZONTAL ngang thuật toán BEA. PHORIZONTAL. r s Ngoài dữ liệu thử nghiệm như đã trình bày, chúng tôi còn Độdđo ( xitương xi và xj , , x j ) đồng (similarity) giữa 2 vector (5.2) Kết luận thử6.nghiệm trên một số bộ dữ liệu khác, kết quả có được được xác định bởi hệq r s số Jaccard: cũng tương đồng với Trong bài 2báo thuật toán này cổ điển chúng tôinêu trên. trình bày giải pháp Độ đo tương sim(xđồng (similarity) i , xj ) = 1 − d(xi , xjgiữa ) 2 vector(8)xi Tuy các bộ cơ sở dữ liệu phân tán phân mảnh dọc và ngang của hệ cơ sở dữ liệu thử nghiệm cònphân nhỏ tán và xj, được xác định bởi hệ số Jaccard: nhưng lại phù hợp với các thử nghiệm trên [2] cho các phân dựa vào thuật toán phân cụm hướng tri thức. Với giải 5.3. Phân mảnh ngang dựa vào thuật toán phân cụm mảnh cổ điển, đồng thời so sánh được với kết quả trên thuật sim hướng i , x j )  1  d ( xi , x j ) tri( xthức (5.3) toánpháp phânnày cụm hướngtôitriđã chúng đề đã thức xuấtđề được xuất. Thờicách gian chuyểntới, đổi giả tôi chúng thiết sẽ các bài các sưu tập toánbộphândữ liệumảnhđã đượccỗ điểncôngtrở bố vềcó giả Sử dụng lại giả thiết ví dụ bài toán phân mảnh ngang dựa 5.3. vào Phân mảnh thuật toán ngang dựa vào PHORIZONTAL thuật được trìnhtoán phân[2]: bày trong cụm kíchthuyết cho bài toán phân cụm. thước lớn hơn để có thử nghiệm so sánh tính khả dụng hướng của giải pháp đề xuất với việc kết hợp các kỹ thuật phân Giảtri sử thức có một quan hệ Emp cụm khácTrongdựa vàothuật thuật toán toán diphân truyền,cụm tiếnhướng hóa haytricácthức, Sử dụng lại ENO giả thiết ENAME ví dụ bài toán phân mảnh TITLE chúng thuật tôi có đề toán heuristic kếtxuất cách hợp với các xây côngdựngcụ toánquan hệ lý học như tương ngang dựa vào T1 thuật E1 toánJjoe PHORIZONTAL Elect-Eng được trình đương thuyết ban tập tập thô, đầumờdựa vàođểngưỡng [3][4] đánh giákhoảng và chỉ racách, đây là các giải T bày trong [2]: 2 E 2 M.Smith Syst-Analyst pháp phânkhác điểm mảnhbiệtdữ liệu vớivới2 hiệu thuậtnăng toáncao. của 2 nhóm tác giả T3 E3 A.Lee Mech-Eng Giả sử T4có một E4 quan hệ EmpProgrammer J.Smith Shoji Hirano, Shusaku Tsumoto và C.L Bean, Tài liệu tham khảo BảngT2. 5 DữE5liệu mẫu B.Casey để Syst-Analyst phân đoạn ngang C.Kambhampati đã đề xuất trước đó. T6 E6 L.Chu Elect-Eng [1] Adrian Runceanu, Towards Vertical Fragmention in Distributed TENO 7 E7 ENAME R.David TITLE Mech-Eng Kết quả Databases, thử nghiệm International Joint trên các bộondữComputer, Conferences liệu trong T1 T8E1 E8 Jjoe J.Jone Elect-Eng Syst-Analyst [13] cho thấy Information, andkết quảSciences, Systems trùng lắp với kết quả and Engineering có 2007) (CISSE được từ Conference; 01/2007. T2 Xét E2 M.Smith Syst-Analyst 2 thuật [2] Lương Văntoán phân Nghĩa mảnh (2013), Phân cổđoạnđiển là PHORIZONTAL dọc, ngang trong thiết kế cơ T32 vị từE3đơn giản:A.Lee Mech-Eng - Tp41 =(TITLE>“Programmer”) E4 J.Smith và Programmer vàsở thuật toán BEA. Ngoài dữ liệu và Công nghệ, Đại học Đà Nẵng, số 3(64).2013. thử nghiệm như đã dữ liệu phân tán dựa trên kỹ thuật phân cụm, Tạp chí Khoa học - Tp52 =(TITLE
Lê Văn Sơn, Lương Văn Nghĩa [9] Marwa F. F. Areed, Ali I.El-Dosouky, Hesham A. Ali, A Heuristic 20-24, Volume 5– No.9. Approach for Horizontal Fragmentation and Allocation in DOODB, [12] Shoji Hirano and Shusaku Tsumoto, A Knowledge-Oriented infos2008.fci.cu.edu.eg/infos/DB-02-P009-016.pdf. Clustering Technique Based on Rough Sets, Computer Software and [10] Narasimhaiah Gorla, Pang Wing Yan Betty, Vertical Applications Conference, 2001. COMPSAC 2001. Fragmentation in Databases Using Data-Mining Technique, www. [13] Tamer O., Valduriez P.. (1999), Principles of Distributed Database irmainternational.org/chapter/vertical-fragmentation-databases-us- Systems, Prentice Hall Englewood Cliffs, Second Edition, New ingdata/40404/. Jersey 07362. [11] Shahidul Islam Khan, A. S. M. Latiful Hoque (2010), A New [14] Yin-Fu Huang, Jyh-her Chen, Fragment Allocation in Distributed Technique for Database Fragmentation in Distributed Systems, Database Design, Journal of Information Science and Engineering, International Journal of Computer Applications (0975 – 8887), pp. 491-506(2001). (BBT nhận bài: 21/12/2013, phản biện xong: 22/01/2014) 63