Ngày nay, với việc dữ liệu đa dạng, được phân tán ở nhiều nơi trên toàn cầu làm cho các ứng dụng cơ sở dữ liệu (CSDL), các phương pháp quản trị và khai thác CSDL phân tán truyền thống tỏ ra ít hiệu quả, không đáp ứng được mục tiêu chia sẻ và còn khó khăn trong việc tích hợp và trao đổi thông tin. Để khắc phục được những hạn chế trên, các CSDL phân tán cần được thiết kế sao cho phù hợp hơn với yêu cầu sử dụng, truy xuất và xử lý dữ liệu phân tán. Điều này có thể thực hiện được nhờ vào kỹ thuật khai phá dữ liệu (KPDL), cụ thể là dựa vào các kỹ thuật phân cụm phục vụ cho việc phân mảnh và phân tán, định vị dữ liệu trong thiết kế CSDL phân tán. Hiện có nhiều nghiên cứu liên quan đến bài toán thiết kế CSDL phân tán dựa vào các kỹ thuật phân cụm trong lĩnh vực KPDL, cụ thể: – Bài toán phân mảnh dữ liệu dựa vào phân cụm đã được nhiều tác giả quan tâm và sau đó được phát triển tiếp bởi Özsu M. Tamer và các cộng sự. Tuy nhiên, các kỹ thuật phân mảnh dựa vào các đối tượng được phân cụm có cùng độ tương đồng giữa các nhóm thuộc tính dừng lại cho bài toán phân mảnh dọc dữ liệu trên các lược đồ quan hệ. – Hui ma và các cộng sự đề xuất thuật toán phân cụm CA (Clustered Affinity) để nhóm thuộc tính có mối quan hệ chặt chẽ với nhau (ái lực) và sau đó Navathe và các cộng sự phát triển thuật toán BEA (Bond Enegy Algorithm), phục vụ cho bài toán phân mảnh dọc dữ liệu phân tán. Các thuật toán trên dựa theo ý tưởng các thuộc tính có tần suất xuất hiện đồng thời càng lớn thì thường thuộc về một cụm (phân mảnh). Phương án giải quyết bài toán này đưa về tối ưu hóa một biểu thức bậc 2 có độ phức tạp khá lớn.