- Nguyễn Văn Rạng THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN SỬ DỤNG CÁC KỸ THUẬT KHAI PHÁ DỮ LIỆU Chuyên ngành: Công nghệ Thông tin LUẬN VĂN THẠC SĨ KỸ THUẬT CÔNG NGHỆ THÔNG TIN NGƢỜI HƢỚNG DẪN KHOA HỌC PGS.TS Nguyễn Kim Anh Hà Nội – Năm 2015 2 LỜI CAM ĐOAN Tên tôi là Nguyễn Văn Rạng, học viên lớp Cao học lớp 13BCNTT1, chuyên ngành Công nghệ Thông tin, trƣờng Đại học Bách Khoa Hà Nội. - CSDL PHÂN TÁN VÀ BÀI TOÁN THIẾT KẾ PHÂN ĐOẠN. - Tổng quan về CSDL phân tán. - Các bài toán thiết kế phân tán. - Các kỹ thuật thiết kế phân đoạn. - Kỹ thuật phân đoạn ngang. - Thông tin cần thiết của phân đoạn ngang. - Phân đoạn ngang cơ sở. - Phân đoạn ngang dẫn xuất. - KHAI PHÁ DỮ LIỆU VÀ CÁC KỸ THUẬT PHÂN CỤM. - Tổng quan về khai phá dữ liệu. - Các mô hình khai phá dữ liệu. - Bài toán phân cụm dữ liệu. - Tổng quan về kỹ thuật phân cụm. - Các kỹ thuật phân cụm dữ liệu. - THIẾT KẾ PHÂN ĐOẠN NGANG CSDL PHÂN TÁN ỨNG DỤNG MỘT SỐ KỸ THUẬT PHÂN CỤM TRONG KHAI PHÁ DỮ LIỆU. - Các vấn đề về thiết kế phân đoạn. - Kỹ thuật phân đoạn ngang cổ điển. - Phân đoạn ngang sử dụng kỹ thuật phân cụm dữ liệu k-Medoids. - Mô hình dữ liệu. - Thuật toán phân cụm. - Thuật toán phân đoạn ngang sử dụng kỹ thuật phân cụm k-Medoids. - Phân đoạn ngang sử dụng kỹ thuật phân cụm dữ liệu với số cụm tự động đƣợc phát hiện trong quá trình thực hiện phân cụm. - Thuật toán phân đoạn ngang trên cơ sở phân cụm dựa vào lý thuyết tập thô . - 57 6 DANH MỤC CÁC CỤM TỪ VIẾT TẮT STT Viết tắt Cụm từ tiếng Anh Cụm từ tiếng Việt 1 CSDL Database Cơ sở dữ liệu 2 KPDL Data mining Khai phá dữ liệu 3 KDD Knowledge Discovery in Database Khám phá tri thức trong CSDL 4 PCDL Data Clustering Phân cụm dữ liệu 5 DBMS Database Management System Hệ quản trị CSDL 6 DDBMS Distributed Database Management System Hệ quản trị CSDL phân tán 7 KO Knowledge-Oriented Hƣớng tri thức 8 RST Rough Set Theory Lý thuyết tập thô 7 DANH MỤC CÁC HÌNH Hình 1. - Một mô hình CSDL quan hệ thực thể ER. - Các quan hệ tƣơng ứng mô hình dữ liệu ở hình 1. - Một ví dụ kết quả phân đoạn dọc. - Một ví dụ kết quả phân đoạn ngang. - Phân đoạn ngang cơ sở quan hệ PROJ. - Phân đoạn ngang cho quan hệ PAY. - Phân đoạn ngang quan hệ PROJ. - Phân đoạn ngang dẫn xuất quan hệ EMP. - Phân đoạn dẫn xuất của ASG ứng với PROJ. - Phân đoạn dẫn xuất của ASG ứng với EMP. - Dữ liệu mẫu cho ví dụ 3.1. - Kết quả phân đoạn ví dụ 3.1. - Kết quả phân đoạn trong [6. - Dữ liệu mẫu cho ví dụ 3.2. - Kết quả phân đoạn ví dụ 3.2. - Bên cạnh đó, việc ra đời và phát triển nhanh chóng của công nghệ mạng máy tính với mục tiêu chia sẻ tài nguyên, khai thác các tài nguyên thông tin, tích hợp và trao đổi các loại dữ liệu giữa các thành phần trên mạng đã đặt ra nhiệm vụ cho các nhà tin học là phải thiết kế các hệ CSDL phân tán nhằm tích hợp CSDL ở nhiều vị trí khác nhau trên mạng hoặc phân tán CSDL từ một trạm đến các vị trí khác nhau sao cho việc khai thác thông tin đạt hiệu quả cao nhất. - Bài toán thiết kế CSDL phân tán là một trong các bài toán quan trọng ảnh hƣởng đến hiệu quả của hệ CSDL sau này. - Các giải pháp thiết kế CSDL phân tán phụ thuộc rất nhiều vào các nguồn dữ liệu đầu vào và vấn đề khai thác các nguồn dữ liệu đầu vào trong các kỹ thuật thiết kế phân tán. - Bài toán này mặc dù đã đƣợc nhiều nhà tin học quan tâm nhƣng vẫn chƣa có đƣợc các giải pháp thiết kế tối ƣu cho các CSDL phân tán. - Mục tiêu của luận văn là nghiên cứu và cài đặt thử nghiệm các giải pháp thiết kế CSDL phân tán sử dụng các kỹ thuật khai phá dữ liệu. - Chƣơng 1 trình bày tổng quan về CSDL phân tán. - các bài toán thiết kế phân tán. - các kỹ thuật thiết kế phân đoạn ngang và những giải pháp đề xuất gần đây. - 10 Chƣơng 2 trình bày khái quát về khai phá dữ liệu. - các mô hình khai phá dữ liệu. - các kỹ thuật phân cụm và các giải pháp đề xuất gần đây. - Chƣơng 3 tác giả đề xuất một số giải pháp thiết kế phân đoạn CSDL phân tán trên cơ sở các kỹ thuật phân cụm dữ liệu và cài đặt các thuật toán thử nghiệm. - Cụ thể, tác giả đề xuất giải pháp và cài đặt thử nghiệm thuật toán phân đoạn ngang CSDL phân tán sử dụng thuật toán phân cụm k-Medoids. - Tuy nhiên với k-Medoids, số cụm do con ngƣời quyết định, nên chƣa thực sự phù hợp với bài toán phân đoạn ngang cổ điển trong đó số đoạn sẽ tự sinh ra trong quá trình phân đoạn. - Tổng quan về CSDL phân tán Nguyên lý các hệ CSDL phân tán đƣợc xây dựng dựa trên sự hợp nhất của hai hƣớng tiếp cận đối với quá trình xử lý dữ liệu, đó là lý thuyết các hệ CSDL và công nghệ mạng máy tính. - Một CSDL phân tán là một tập hợp nhiều CSDL có liên đới logic và đƣợc phân bố trên một mạng máy tính. - Tính chất phân tán: Toàn bộ dữ liệu của CSDL phân tán không đƣợc đặttập trung ở một nơi mà phân tán trên nhiều trạm trên mạng máy tính, điều này giúp chúng ta phân biệt CSDL phân tán với CSDL tập trung đơn lẻ. - Tương quan logic: Toàn bộ dữ liệu của CSDL phân tán có một số các thuộc tính ràng buộc chúng với nhau, điều này giúp chúng ta có thể phân biệt một CSDL phân tán với một tập hợp CSDL cục bộ hoặc các tệp cƣ trú tại các vị trí khác nhau trong một mạng máy tính. - Các bài toán thiết kế phân tán Thiết kế cơ sở dữ liệu phân tán là bài toán tối ƣu hóa bao gồm các bài toán: phân đoạn và sắp chỗ. - Đối với bài toán phân đoạn, có 2 bài toán con: phân đoạn ngang và phân đoạn dọc. - Phân đoạn ngang là phân chia tập các bản ghi thành các tập bản ghi nhỏ hơn. - Phân đoạn dọc là phân rã tập thuộc tính của lƣợc đồ quan hệ R thành các lƣợc đồ con R1, R2. - Ngoài ra còn có phân đoạn hỗn hợp (kết hợp 2 bài toán trên). - Đối với bài toán sắp chỗ, giả sử có một tập các đoạn dữ liệu F = {F1, F2. - Các kỹ thuật thiết kế phân đoạn Các quan hệ trong CSDL thƣờng đƣợc biểu diễn dƣới dạng bảng. - Việc phân đoạn một quan hệ thành nhiều quan hệ con khác nhau theo các cách khác nhau, sẽ có các cách phân đoạn tƣơng ứng. - Có hai kiểu phân đoạn tƣơng ứng với việc chia quan hệ theo chiều dọc và chia quan hệ theo chiều ngang. - Sau đây là mô hình dữ liệu mẫu để minh họa các kỹ thuật thiết kế phân đoạn. - Một mô hình CSDL quan hệ thực thể ER Hình 2. - Các quan hệ tương ứng mô hình dữ liệu ở hình 1 Phân đoạn theo chiều dọc: Các quan hệ đƣợc chia theo chiều dọc. - Nghĩa là thiết lập một quan hệ mới chỉ có một số thuộc tính từ quan hệ gốc. - Thực chất đây là phép chiếu trên tập con các thuộc tính của quan hệ. - Ví dụ 1.1. - Tách dọc quan hệ PROJ (hình 2) thành 2 quan hệ PROJ1 và PROJ2 nhƣ sau: πPNO, BUDGET (PROJ) và πPNO, PNAME, LOG (PROJ) 14 Hình 3. - Một ví dụ kết quả phân đoạn dọc Phân đoạn ngang: Quan hệ đƣợc chia theo chiều ngang. - Thực chất đây là phép chọn trong quan hệ. - Chọn những bộ của quan hệ thỏa mãn một biểu thức điều kiên cho trƣớc. - Ví dụ 1.2. - Tách ngang quan hệ PROJ (hình 2) thành 2 quan hệ PROJ1 và PROJ2 thỏa theo điều kiện BUDGET ≤ 200000 và BUDGET > 200000 nhƣ sau: σBUDGET ≤ 200000 (PROJ) σBUDGET > 200000 (PROJ) Hình 4. - Một ví dụ kết quả phân đoạn ngang 1.4. - Kỹ thuật phân đoạn ngang 1.4.1. - Giới thiệu Phân đoạn ngang chính là việc chia một quan hệ thành nhiều nhóm. - Kết quả của quá trình phân đoạn ngang là các quan hệ con, số lƣợng quan hệ con phụ thuộc vào điều kiện ràng buộc của các thuộc tính. - Và các bộ trong các quan hệ con là tách biệt nhau. - Phân đoạn ngang thực chất là phép chọn quan hệ thỏa mãn một biểu thức điều kiện cho trƣớc. - Có hai dạng phân đoạn ngang là: 15 Phân đoạn ngang nguyên thủy: Là phân đoạn ngang đƣợc thực hiện trên các vị từ của chính quan hệ đó. - Phân đoạn ngang dẫn xuất: Là phân rã một quan hệ dựa trên các vị từ của quan hệ khác. - Thông tin cần thiết của phân đoạn ngang a. - Thông tin về CSDL có liên quan tới lƣợc đồ khái niệm toàn cục Trong mô hình quan hệ, các mối quan hệ giữa các thực thể đƣợc mô tả nhƣ là những quan hệ. - Trong mô hình quan hệ thực thể (ER), các mối liên hệ giữa các đối tƣợng CSDL đƣợc mô tả rõ ràng. - Nhìn chung mối quan hệ giữa các đối tƣợng trong CSDL thƣờng mô tả bằng các mối quan hệ một - một, một - nhiều và mối quan hệ nhiều - nhiều. - Ví dụ 1.3. - Đây là mối quan hệ môt - nhiều đƣợc biểu diễn bằng một đƣờng nối có hƣớng L1 trỏ từ quan hệ PAY đến EMP. - Mối quan hệ nhiều - nhiều đƣợc trỏ từ các quan hệ EMP và PROJ đến quan hệ ASG. - Quan hệ tại điểm cuối của đƣờng nối đƣợc gọi là quan hệ chủ (quan hệ đích) và các quan hệ tại điểm đầu đƣợc gọi là các quan hệ thành viên (quan hệ nguồn). - Ánh xạ Owner và Member từ tập đƣờng nối tới tập quan hệ. - Khi cho trƣớc một đƣờng nối, hàm sẽ trả về quan hệ đích hay quan hệ nguồn của đƣờng nối. - Cho quan hệ R (A1, A2. - Chúng ta sử dụng Pri để biểu thị tập tất cả các vị từ đơn giản được định nghĩa trên quan hệ Ri. - Ví dụ 1.4. - Cho quan hệ PROJ (hình 2) PNAME = “Maintenance”, BUDGET ≤ 200000 là các vị từ đơn giản. - pim} là các vị từ đơn giản trên quan hệ Ri, tập các vị từ hội sơ cấp Mi = {mi1, mi2
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt