Phân mảnh và định vị dữ liệu phân tán bằng tác tử di động

á trình phân mảnh gắn liền với quá trình cấp phát và các bài toán cụ thể, cần lưu ý một điều quan trọng là cho 
đến hiện tại chúng ta vẫn chưa có một thuật toán tổng quát tối ưu cho bài toán phân mảnh tổng quát và cấp phát dữ liệu 
trên mạng. 
 Tính tối ưu có thể được định nghĩa với hai giá trị: 
 Chi phí nhỏ nhất: Hàm chi phí gồm chi phí lưu mảnh Fi tại vị trí Sj, chi phí vấn tin Fi tại vị trí Sj, chi phí cập 
nhật Fi tại tất cả các vị trí có chứa nó, và chi phí truyền dữ liệu. Vì vậy bài toán cấp phát ở đây là cố gắng tìm một lược 
đồ cấp phát với hàm chi phí thấp nhất. 
 Hiệu quả: Chiến lược cấp phát được thiết kế nhằm duy trì hiệu quả là giảm thấp thời gian đáp ứng và tăng tối đa 
lưu lượng hệ thống tại mỗi vị trí. 
 Mô hình cấp phát: có mục tiêu là giảm thiểu tổng chi phí xử lý và lưu trữ. Min(Total_Cost) ứng với ràng buộc 
thời gian đáp ứng, ràng buộc lưu trữ và ràng buộc xử lý. Ma trận x(n, m) thể hiện cách cấp phát mảnh vào các site: 
 { 
Trần Đình Toàn, Nguyễn Mậu Hân 549 
 Ví dụ 5: Ma trận x(nxm) cho biết mảnh Fi được cấp phát tại site Sj 
 SSSS1 2 3 4
 F1 0 1 1 0
 F 2 1 1 0 0
 F 3 1111
 F 4 0 0 1 1
 F 5 0 0 0 1
 Ví dụ 6: Ma trận RM(qxf) dòng là các truy vấn, cột là các mảnh, ma trận thể hiện số lần truy vấn chỉ đọc, phần 
tử rij trong ma trận RM thể hiện số lần câu truy vấn qi thực hiện chỉ đọc tại mảnh Fj. 
 FFFFF1 2 3 4 5
 q1 2 0 1 0 0
 q2 2 3 0 0 0
 q3 3 0 1 1 0
 q4 0 0 2 0 0
 Ví dụ 7: Ma trận UM(qxn) dòng là các truy vấn, cột là các mảnh, ma trận thể hiện số lần truy vấn cập nhật. Phần 
tử uij trong ma trận UM thể hiện số lần câu truy vấn qi thực hiện cập nhật tại mảnh Fj. 
 FFFFF1 2 3 4 5
 q1 0 0 1 0 2
 q2 0 3 0 0 0
 q3 3 0 1 1 0
 q4 0 0 0 0 3
 Hệ thống phân tán có thể được biểu diễn như một đồ thị G=(V, E), trong đó V là tập đỉnh của đồ thị đại diện cho 
các site, E là tập cạnh của đồ thị đại diện là đường kết nối giữa các đỉnh (sites) của đồ thị. Mỗi cạnh được gán 1 giá trị 
gọi là chi phí (cost). 
 Tác tử di động [1] 
 Tác tử di động là một tác tử có khả năng di chuyển một cách tự trị từ nút mạng này sang nút mạng khác và thực 
hiện các các công việc được giao thay thế cho con người. Khi di chuyển, các tác tử di động đóng gói mã nguồn, dữ liệu 
và cả trạng thái thi hành, nhờ vậy tác tử di động có thể dừng việc thi hành đang thực hiện tại máy này, di chuyển sang 
máy khác và khôi phục lại sự thi hành. 
 Các tác tử di động có thể giúp làm giảm lưu lượng trên mạng thay vì phải truyền một lượng lớn thông tin trên 
mạng thì chúng ta chỉ cần truyền chức năng của chúng. Các tác tử di động cũng có thể xử lý trước dữ liệu và chỉ truyền 
các kết quả. Còn được gọi là nén ngữ nghĩa. 
 Tác tử 
 Cơ chế ra quyết định động Tác
 Thông tin ra 
 Thông tin từ 
 môi trường môi trường 
 Cảm nhận Trạng thái 
 Hình 1. Cấu trúc của tác tử 
 Từ Hình 1, chúng ta có thể thấy tác tử nhận thông tin từ môi trường (bao gồm thông tin từ các tác tử khác) thông 
qua cơ quan cảm nhận. Nhờ có cơ chế ra quyết định, tác tử lựa chọn hành động cần thực hiện. Quá trình ra quyết định 
có thể sử dụng thông tin về trạng thái bên trong của tác tử. Trong trường hợp đó, tác tử lưu trữ trạng thái dưới dạng 
những cấu trúc dữ liệu riêng. Hành động do cơ chế ra quyết định lựa chọn sau đó được tác tử thực hiện thông qua cơ 
quan tác động. Cơ chế suy diễn có thể thay đổi cho từng kiểu kiến trúc cụ thể và ảnh hưởng tới những thành phần khác. 
550 PHÂN MẢNH VÀ ĐỊNH VỊ DỮ LIỆU PHÂN TÁN BẰNG TÁC TỬ DI ĐỘNG 
Chẳng hạn có thể có kiến trúc trong đó quá trình suy diễn không sử dụng tới trạng thái bên trong và do vậy tác tử 
không cần lưu giữ các thông tin này. Đối với các tác tử có thêm khả năng khác như học tự động, kiến trúc tác tử có 
thể có thêm thành phần riêng để thực hiện các chức năng này. 
 Tác tử di động là một phần mềm thông minh, nó bao gồm cả các yêu cầu người dùng và kết hợp với tính ưu việt 
của tác tử. Vì thế truy vấn dữ liệu dựa trên tác tử di động không chỉ đáp ứng các yêu cầu người dùng mà còn khắc phục 
được các khuyết điểm của các hệ thống thông thường khác. 
 Chúng ta có thể phân biệt một tác tử từ một hệ chuyên gia bởi thực tế một hệ chuyên gia đóng vai trò như một 
nhà tư vấn và đưa ra lời khuyên trong việc lựa chọn các giải pháp trong khi một tác tử thông minh có thể hành động để 
thay đổi môi trường. 
 Giải quyết bài toán phân tán là đặc trưng hợp tác làm việc của các tác tử di động khi các vấn đề cần sự giải 
quyết tập thể, cũng như phân tán nguồn tài nguyên sẵn có như tri thức, khả năng và chuyên môn giữa các tác tử. 
 Vấn đề cấp phát dữ liệu có thể mô hình hóa bằng phương pháp tác tử di động bởi vì nó được mô tả trong thuật 
toán tìm kiếm cho các tác tử, chúng ta có thể phân bài toán này như bài toán tìm đường đi. Bài toán tìm đường đi bao 
gồm các thành phần: 
 Tập N các nút, mỗi nút đại diện cho một trạng thái. 
 Tập L là tập các liên kết có hướng, mỗi cái đại diện cho một toán tử có sẵn để các tác tử giải quyết vấn đề. 
 Giả sử chúng ta biết trạng thái ban đầu. 
 Tập G các nút, mỗi nút đại diện cho một trạng thái mục tiêu. 
 Với mỗi liên kết, trong số của liên kết được định nghĩa đại diện cho các chi phí áp dụng các toán tử. Chúng ta 
gọi trọng số của đường liên kết giữa hai nút là khoảng cách giữa hai nút, gọi các nút có hướng từ nút liền kề nút i. 
Trong bài toán tìm đường đi tối ưu theo quy tắc: một đường là tối ưu nếu và chỉ nếu mọi phân khúc của nó là tối ưu. Vì 
vậy, nếu tồn tại một đường ngắn nhất từ nút bắt đầu đến nút mục tiêu và tồn tại nút x ở giữa trên đường đó, phân khúc 
từ nút đầu đến nút x là đường tối ưu từ nút đầu đến nút x. Tương tự, phân khúc từ nút x tới nút mục tiêu cũng đại diện 
cho đường đi ngắn nhất từ nút x đến nút mục tiêu. 
 Mô tả giải pháp sử dụng tác tử di động trong cấp phát dữ liệu. 
 Hệ thống được tổ chức như là đồ thị có hướng với phương pháp sử dụng các tác tử di động thông minh để tìm ra 
các đường đi ngắn nhất từ một truy vấn được tạo ra ở mỗi nút đến các nút khác liên quan đến truy vấn đó. 
 Có nhiều giải pháp cho cấp phát mảnh dữ liệu trong các mô hình hệ thống cổ điển. Nhưng trong giải pháp sử 
dụng tác tử di động nó có thể phản ứng với môi trường và thay đổi nó để thực hiện tốt mục tiêu của mình. Vì vậy 
chúng tôi kết hợp mô hình đồ thị với bài toán tìm đường đi cho các tác tử cũng như với các loại hình học tập như học 
không giám sát, học tập trung và hợp tác. 
 Mục tiêu của hệ thống tác tử là tìm đường đi từ cấu hình ban đầu đến cấu hình mục tiêu, có nghĩa là cần phải 
phân mảnh dữ liệu và để có được sự cân bằng trong đồ thị, như vậy chúng ta có thể có được thời gian đáp ứng hợp lý 
từ mỗi nút nơi chúng ta có thể bắt đầu một truy vấn. 
 Chi phí của mỗi cạnh có một ý nghĩa đó là những đáp ứng tốt nhất của hệ thống trong phần lớn các trường hợp, 
vì vậy khi thực hiện cấp phát dữ liệu cần phải chú ý, ban đầu chúng ta có thể ước chừng, dự đoán, truy cập từ một site 
tới dữ liệu của site khác để biết thời gian đáp ứng trên một đơn vị thời gian. Chúng tôi xây dựng đồ thị kết hợp chi phí 
của thời gian chuyển giao đơn vị dữ liệu. Khi thực hiện cấp phát dữ liệu chúng tôi tăng kích thước vật lý của các mảnh 
với chi phí của chuyển giao từng đơn vị và từ đó có được ma trận khoảng cách trong biểu đồ. Qua đó có thể áp dụng 
một số thuật toán ma trận để có một số giá trị nhỏ nhất như các thuật toán Floyd-Hu và Floyd-Warshall-Hu. 
 Thuật toán Floyd-Hu: 
 k 1 k+1
 Xét ma trận V= (vij) các giá trị của các cạnh đồ thị. Định nghĩa ma trận V , k =1,..., n+1 và V =V, và tính V 
bởi * + 
 Đầu vào: Đồ thị cho bởi ma trận V 
 Đầu ra: Ma trận đường đi ngắn nhất giữa các cặp đỉnh i, j 
 Giai đoạn 1: Khởi tạo 
 Giai đoạn 2: Các bước lặp 
 for k=1 to n do 
 for i=1 to n do 
 for j=1 to n do 
Trần Đình Toàn, Nguyễn Mậu Hân 551 
 * + 
 end for 
 end for 
 end for 
 Độ phức tạp của thuật toán là O(n3), trong đó n là số đỉnh của đồ thị. 
 Xây dựng hệ thống với tác tử di động lưu trú trên thực tế có thể cung cấp thông tin chính xác về việc chuyển dữ 
liệu. Tác tử di động có thể học từ hệ thống và cung cấp một số thống kê về số lần xuất hiện truy vấn trên một site cụ 
thể, đại diện x tỷ lệ phần trăm của chi phí. Một chi phí khác y tỷ lệ phần trăm là thời gian thực quan trọng cho một truy 
vấn thực thi ở một site. Chi phí này có thể được xác định bởi tác tử vì tác tử có thể di chuyển qua lại giữa các site và 
hợp tác với các tác tử khác. Chúng ta có thể thực hiện khởi tạo tham số ban đầu và gán lại giá trị cho các biến. Chúng 
tôi xây dựng hệ thống tác tử như vậy để nó có thể phản ứng và thay đổi bằng cách gán một số giá trị của chính nó để 
cải thiện đáp ứng. 
 Hệ thống có thể thay đổi giá trị của x và y hoặc có thể thêm các biến khác để mô tả chi phí tốt hơn. Chi phí cuối 
cùng liên quan đến một cạnh được thể hiện bởi 3 yếu tố: truy vấn qo xuất hiện, thời gian thực rti và thời gian đáp ứng 
rmt lại sau mỗi lần truy vấn. Công thức chi phí cho mỗi cạnh sẽ là: 
 Cost=qo * x + rti * y + rmt * (100 – x – y) 
 Chi phí này có thể có tính động tự nhiên do hệ thống mạng có thể chậm bởi đường truyền, giao tiếp dữ liệu 
khác, những thay đổi của cấu trúc mạng hay thời gian thực bắt đầu khởi tạo của truy vấn ở một nút của hệ thống. 
 Chúng ta có thể áp dụng nhiều thuật toán tìm kiếm đa tác tử thời gian thực, chia vấn đề chi phí trong nhiều mục 
tiêu con có thể thay đổi trong suốt thời gian tồn tại của tác tử: 
 ( )
 ∑ ∑ ∑ ∑ 
 Trong đó: Total Cost là tổng chi phí, Q là tập các truy vấn, S là tập các site và F là tập các mảnh dữ liệu, x và y 
là tỷ lệ của các yếu tố liên quan đến chi phí như số lần truy vấn của query ở một site và thời gian thực để thực thi truy 
vấn ở một site. 
 Ví dụ 8: Từ ví dụ 1 và ví dụ 2, giả sử 4 mảnh ngang của quan hệ EMP được cấp phát trên 4 site lần lượt mảnh 
EMP1 trên site S1, EMP2 trên site S2, EMP3 trên site S3, EMP4 trên site S4 và chiến lược phân tán là chia nhỏ dữ liệu, 
giả sử một yêu cầu ―Cho biết thông tin của các nhân viên gồm ENO, ENAME có TITLE là Elec. Eng hoặc 
Programmer‖. Câu truy vấn SQL tương ứng là: 
 SELECT ENO, ENAME 
 FROM EMP 
 WHERE TITLE= ―Elec. Eng‖ OR TITLE= ―Programmer‖ 
 Giả sử trả lời truy vấn tại S3, gọi x, y, z là số byte dữ liệu được truyền lần lượt từ site S1, S2, S4 về S3, theo mô hình 
chi phí truyền thống thì tổng chi phí thực hiện là: Total_cost=CCPU * #instr + CI/O * #I/OS + CMSG * #msgs + CTR * #bytes, 
trong đó, hai thành phần chi phí của một lệnh CPU (CCPU) và chi phí của một xuất nhập đĩa (CI/O) là các chi phí địa 
phương, hai thành phần chi phí (CMSG, CTR) là chi phí truyền thông để chuyển số byte dữ liệu từ trạm này đến trạm khác 
và giả sử hai thành phần chi phí này được biểu thị theo đơn vị thời gian, nên tổng chi phí truyền dữ liệu từ site S1, S2, S4 về 
S3 là: Total_cost= 3CMSG + CTR * (x + y + z), như vậy chi phí này sẽ lớn khi x, y và z lớn. Vì truyền dữ liệu có thể được 
thực hiện song song nên thời gian trả lời của truy vấn là: Response_time = max{CMSG + CTR * x, CMSG + CTR * y, CMSG + 
CTR * z}, thời gian trả lời tối thiểu đạt được nếu tăng mức độ xử lý song song, tuy nhiên không có nghĩa sẽ được tổng chi 
phí thấp mà có thể ngược lại, tổng chi phí có thể tăng do có nhiều xử lý cục bộ và truyền song song. 
 Theo giải pháp sử dụng tác tử di động, tác tử được khởi tạo tại site S3, tác tử di chuyển giữa các site và mang 
yêu cầu tới site S1 và S4 xử lý truy vấn tại 2 site này, sau đó chuyển kết quả về site S3 lúc này chi phí truyền dữ liệu là: 
Total_cost= 2CMSG + CTR * (x’ + z’), trong đó x’, z’ lần lượt là số byte dữ liệu thỏa điều kiện truy vấn, như vậy chi phí 
truyền dữ liệu thấp hơn mô hình truyền thống do chỉ truyền dữ liệu là kết quả của truy vấn. Thời gian trả lời của truy 
vấn nếu thực hiện truyền dữ liệu song song là: Response_time = max{CMSG + CTR * x’, CMSG + CTR * z’}, so với mô 
hình truyền thống thời gian trả lời của truy vấn theo giải pháp tác tử di động cũng thấp hơn. 
 V. KẾT LUẬN 
 Sử dụng tác tử di động có thể cung cấp giải pháp tốt trong cấp phát dữ liệu cho hệ thống phân tán. Lợi ích của 
việc sử dụng tác tử là làm tăng tính tự trị và tăng tính linh hoạt của hệ thống, đồng thời tác tử di động có thể phản ứng 
lại các thay đổi của hệ thống, thêm vào đó tác tử di động làm giảm đáng kể sự tác động của con người vào quản trị hệ 
thống. Bài báo đã trình bày giải pháp phân mảnh và cấp phát dữ liệu trong CSDL phân tán sử dụng tác tử di động làm 
552 PHÂN MẢNH VÀ ĐỊNH VỊ DỮ LIỆU PHÂN TÁN BẰNG TÁC TỬ DI ĐỘNG 
tăng hiệu suất hệ thống và giảm chi phí truyền dữ liệu so với giải pháp truyền thống. Trong thời gian tới chúng tôi tiến 
hành thực nghiệm trên các bộ dữ liệu khác nhau nhằm đánh giá giải pháp đã đề xuất, đồng thời tiếp tục nghiên cứu và 
phát triển áp dụng tác tử di động vào tối ưu hóa truy vấn CSDL phân tán. 
 TÀI LIỆU THAM KHẢO 
[1] Peter Braun, Wilhelm Rossak, Mobile Agents – Basis concepts, Mobility models and the Tracy toolkit, Morgan Kaufmann 
 Publishers, USA, 2005. 
[2] M. Tamer Özsu, Patrick Valduriez, Principles of Distributed Database Systems, Springer, 2011. 
[3] Shahidul Islam Khan, Dr. A. S. M. Latiful Hoque, A New Technique for Database Fragmentation in Distributed Systems, 
 International Journal of Computer Applications, Vol 5, 2010. 
[4] Nicoleta, Magdalena Iacob, Fragmentation and Data Allocation in the Distributed Environments, Annals of the University of 
 Craiova, Mathematics and Computer Science Series, Vol.38, 2011. 
[5] Prof. Y M Naik, Shilpa Tarihal, Roopali Swami, shwini Purandare, Kiran Adike, Distributed Information Retrieval Using 
 Mobile Agent, American International Journal of Research in Science, Technology, Engineering & Mathematics, pp. 182-185, 
 USA, 2013. 
[6] A. Suganya, R. Kalaiselvi, Efficient Fragmentation and Allocation in Distributed Databases, International Journal of Engineering 
 Research & Technology, Vol.2, 2013. 
[7] Vivek N. Waghmare, Snehal D. Patkar, Pranali B. Patil, An Agent Based Mobile Transaction and Disconnection Management 
 System, International Journal of Emerging Technology and Advanced Engineering, Vol. 5, 2015. 
[8] Van Nghia Luong, Ha Huy Cuong Nguyen, Van Son Le, An improvement on fragmentation in Distribution Database Design 
 Based on Knowledge-Oriented Clustering Techniques, International Journal of Computer Science and Information Security, 
 Vol. 13, 2015. 
 FRAGMENTATION AND ALLOCATION OF DISTRIBUTED DATA 
 BY MOBILE AGENT 
 Tran Dinh Toan, Nguyen Mau Han 
ABSTRACT — In this paper, we introduce solutions fragmented data and data allocation using mobile agent in distributed 
database systems, the use of mobile agent in order to increase the autonomy, flexibility and responsiveness to change of the system. 
We focus on the fragmentation and data allocation for the purpose of optimized data allocation, thereby, to reduce the cost of data 
transmission, improve system performance. 
Keywords — Distributed database, fragmentation, allocation, mobile agents, optimization.