Tài liệu Xử lý dữ liệu và bài toán cấp phát

I .. ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG LẠI DƢƠNG QUANG XƢ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH Thái Nguyên, tháng 6 năm 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ II ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CNTT VÀ TRUYỀN THÔNG LẠI DƢƠNG QUANG XƢ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 01 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH GV hƣớng dẫn: PGS. NCVC. TS Lê Huy Thập Thái Nguyên, 2015 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ III LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu do chính tôi thực hiện. Các số liệu, kết quả nêu trong luận văn là trung thực và chƣa từng đƣợc ai công bố trong bất kỳ công trình nào khác. Thái Nguyên, Ngày 10 tháng 4 năm 2015 Tác giả Lại Dƣơng Quang Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ IV LỜI CẢM ƠN Trƣớc hết em xin trân trọng gửi lời cảm ơn đến toàn thể các thầy cô giáo Trƣờng Đại học Công nghệ thông tin và Truyền thông Thái Nguyên đã dạy dỗ chúng em trong suốt quá trình học tập chƣơng trình cao học tại trƣờng. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS. NCVC. TS Lê Huy Thập đã quan tâm, định hƣớng và đƣa ra những lời góp ý, chỉnh sửa quí báu cho em trong quá trình làm luận văn tốt nghiệp Thái Nguyên, Ngày 10 tháng 4 năm 2015 Học viên Lại Dƣơng Quang Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ V MỞ ĐẦU Ngày nay, công nghệ thông tin (CNTT) đã trở thành một nhân tố không thể thiếu trong mọi lĩnh vực của đời sống xã hội. Sự bùng nổ nhu cầu xây dựng các hệ thống thông tin, mà trƣớc hết là các hệ thống thông tin quản lý đã thu hút sự quan tâm của nhiều nhà khoa học. Các hệ thống cơ sở dữ liệu (CSDL) đã lần lƣợt xuất hiện. Các hệ thống CSDL truyền thống đƣợc tập trung quản lý tại một trạm đơn lẻ, việc tính toán, xử lý và lƣu trữ các tập dữ liệu trở lên đơn giản và dễ dàng. Khi nhu cầu thu thập, lƣu trữ, xử lý và trao đổi thông tin ngày càng tăng, các hệ thống xử lý tập trung đã bộc lộ nhiều nhƣợc điểm nhƣ: Khó khăn trong việc tăng khả năng lƣu trữ thông tin, độ sẵn sàng phục vụ của CSDL không cao khi số ngƣời sử dụng tăng, khả năng tính toán của các máy tính đơn lẻ đang dần tới giới hạn vật lý, mô hình tổ chức lƣu trữ và xử lý dữ liệu không phù hợp cho các tổ chức có hoạt động rộng lớn, đa quốc gia. Những nhƣợc điểm này đã đƣợc khắc phục khá nhiều trong hệ thống phân tán. Những sản phẩm của hệ thống phân tán đã xuất hiện nhiều trên thị trƣờng và từng bƣớc chứng minh tính ƣu việt của nó hơn hẳn các hệ thống tập trung truyền thống. Với nhu cầu phát triển mạnh mẽ của công tác quản lý các hệ phân tán và cơ sở dữ liệu phân tán để giải quyết các bài toán ”quản lý” phức tạp đang tồn tại trong các ngành kinh tế, xã hội và an ninh quốc phòng,.... Nhằm hỗ trợ cho vấn đề nêu trên thì việc tính toán, lập trình cấp phát và xử lý dữ liệu cũng phát triển theo. Đặc biệt, việc phân mảnh các quan hệ trong CSDL và chuyển chúng đến các nút trên mạng cũng nhƣ việc cập nhật thông tin (truy cập và truy xuất,...) đến các mảnh ở các vị trí phân tán đã trở thành một chủ đề mới mẻ và đƣợc nhiều ngành khoa học, các bộ môn chuyên ngành nghiên cứu, ứng dụng. Chính vì vậy, tôi đã lựa chọn đề tài: “Xử lý dữ liệu và bài toán cấp phát” để nghiên cứu thực hiện. Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc nhƣ sau: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ VI CHƢƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ BÀI TOÁN CẤP PHÁT. 1.1. Tổng quan về CSDL phân tán. 1.2. Bài toán cấp phát. 1.3. Kết luận chƣơng. CHƢƠNG 2: XỬ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT. 2.1. Thuật toán phân mảnh cơ sở dữ liệu. 2.1.1. Phân mảnh ngang. 2.1.2. Phân mảnh dọc. 2.1.3. Phân mảnh hỗn hợp. 2.2. Tính toán hàm mục tiêu và ràng buộc tại node mạng. 2.2.1. Hàm mục tiêu. 2.2.2. Ràng buộc. 2.3. Bài toán cấp phát dạng QHTT. 2.4. Kết luận chƣơng. CHƢƠNG 3: CÀI ĐẶT VÀ ỨNG DỤNG TẠI CÔNG TY ĐẦU TƢ VÀ THƢƠNG MẠI AN LỘC. 3.1. Khảo sát cơ sở dữ liệu của công ty đầu tƣ và thƣơng mại An Lộc và đƣa ra yêu cầu của bài toán. 3.2. Xây dựng cơ sở dữ liệu phân tán. 3.3. Cài đặt và chạy chƣơng trình cấp phát. 3.4. Kết luận chƣơng. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA ĐỀ TÀI. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ VII DANH MỤC HÌNH ẢNH Hình 1.1: Hệ đa bộ xử lý có bộ nhớ chung ............................................................ 3 Hình 1.2: Hệ đa bộ xử lý có shared disk ................................................................ 3 Hình 1.3: Hệ đa bộ xử lý sở hữu cá nhân .............................................................. 3 Hình 1.4: CSDL đƣợc phân tán trên mạng ............................................................ 4 Hình 1.5: Phân mảnh hỗn hợp và tái thiết phân mảnh hỗn hợp ........................... 11 Hình 2.1: Phân mảnh hỗn hợp .............................................................................. 37 Hình 2.2: Truyền dữ liệu cho câu vấn tin ............................................................. 40 Hình 3.1: Giao diện ban đầu của bài toán ............................................................ 55 Hình 3.2: Giao diện sau khi tiến hành chọn số lƣợng máy trạm ......................... 56 Hình 3.3: Giao diện của quá trình chọn số lƣợng mảnh cơ sở dữ liệu ................. 57 Hình 3.4: Giao diện của quá trình chọn các mảnh cơ sở dữ liệu ......................... 58 Hình 3.5: Giao diện sau quá trình lựa chọn các mảnh cơ sở dữ liệu ................... 59 Hình 3.6: Giao diện lựa chọn các tham số từ file .txt có sẵn ............................... 60 Hình 3.7: Giao diện sau quá trình nhập các tham số ........................................... 61 Hình 3.8: Bảng kết quả của quá trình cấp phát .................................................... 62 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ VIII DANH MỤC BẢNG BIỂU Bảng 2.1: Quan hệ DuAn .......................................................................................... 25 Bảng 2.2: Quan hệ TraLuong ................................................................................... 26 Bảng 2.3: Mảnh dữ liệu (quan hệ) TraLuong1 .......................................................... 26 Bảng 2.4: Mảnh dữ liệu (quan hệ) TraLuong2 .......................................................... 27 Bảng 2.5: Phân hoạch ngang cho quan hệ DuAn: DuAnH1, DuAnH3, DuAnH4, DuAnH6 .......................................................................................................................... 29 Bảng 3.1: Một số bản ghi của quan hệ Giao_Dich tiến hành phân mảnh ngang...... 51 Bảng 3.2: Bảng dữ liệu (quan hệ) của mảnh F1 ....................................................... 52 Bảng 3.3: Bảng dữ liệu (quan hệ) của mảnh F2 ...................................................... 53 Bảng 3.4: Bảng dữ liệu (quan hệ) của mảnh F3 ....................................................... 53 Bảng 3.5: Bảng dữ liệu (quan hệ) của mảnh F4 ....................................................... 53 Bảng 3.6: Bảng dữ liệu (quan hệ) của mảnh F5 ....................................................... 53 Bảng 3.7: Bảng dữ liệu (quan hệ) của mảnh F6 ....................................................... 53 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ IX DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT Thuật ngữ Tên viết tắt Cơ sở dữ liệu phân tán Cơ sở dữ liệu Dữ liệu CSDLPT CSDL DL Quy hoạch tuyến tính QHTT Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ X MỤC LỤC LỜI CAM ĐOAN ............................................................................................................I LỜI CẢM ƠN ................................................................................................................. II MỞ ĐẦU ........................................................................................................................ III DANH MỤC HÌNH ẢNH ............................................................................................. V DANH MỤC BẢNG BIỂU ........................................................................................... VI DANH MỤC CÁC THUẬT NGỮ VIẾT TẮT .............................................................VII MỤC LỤC ................................................................................................................... VIII CHƢƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT ....... 1 1.1. Tổng quan về CSDL phân tán ................................................................1 1.1.1. Xử lý phân tán ..................................................................................1 1.1.2. Hệ cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán .....4 1.1.3. Một số yêu cầu của hệ cơ sở dữ liệu phân tán .................................5 1.1.4. Các đặc điểm của hệ CSDL phân tán.............................................13 1.1.5. Kiến trúc hệ quản trị cơ sở dữ liệu phân ........................................14 1.2. Bài toán cấp phát...................................................................................16 1.2.1. Giới thiệu về bài toán cấp phát ......................................................16 1.2.2. Mô tả bài toán cấp phát ..................................................................20 1.2.3. Hàm mục tiêu (hàm chi phí) ..........................................................20 1.2.4. Các ràng buộc.................................................................................21 1.3. Kết luận chƣơng ....................................................................................22 CHƢƠNG 2: XỬ LÝ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT ................................... 22 2.1. Thuật toán phân mảnh cơ sở dữ liệu .....................................................22 2.1.1. Thuật toán phân mảnh ngang nguyên thủy ....................................22 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ XI 2.1.2. Phân mảnh dọc ...............................................................................30 2.1.3. Phân mảnh hỗn hợp ........................................................................38 2.2. Tính toán hàm mục tiêu và ràng buộc tại node mạng ...........................39 2.2.1. Hàm mục tiêu .................................................................................39 2.2.2. Ràng buộc ......................................................................................44 2.3. Bài toán cấp phát dạng QHTT ..............................................................45 2.4. Kết luận chƣơng ....................................................................................49 CHƢƠNG 3: CÀI ĐẶT VÀ ỨNG DỤNG TẠI CÔNG TY ĐẦU TƢ VÀ THƢƠNG MẠI AN LỘC 3.1. 50 Khảo sát cơ sở dữ liệu của công ty đầu tƣ và thƣơng mại An Lộc và đƣa ra yêu cầu của bài toán ...................................................................................50 3.1.1. Mô tả hệ thống ...............................................................................50 3.1.2. Yêu cầu của bài toán ......................................................................51 3.2. Xây dựng cơ sở dữ liệu phân tán ..........................................................52 3.3. Cài đặt và chạy chƣơng trình cấp phát..................................................58 3.4. Kết luận chƣơng ....................................................................................66 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................................... 67 TÀI LIỆU THAM KHẢO ............................................................................................... 68 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 1 CHƢƠNG 1: TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU VÀ BÀI TOÁN CẤP PHÁT 1.1. Tổng quan về CSDL phân tán Nguyên lý cơ bản của các hệ cơ sở dữ liệu phân tán (CSDLPT) đƣợc xây dựng dựa trên sự hợp nhất của hai hƣớng tiếp cận lý thuyết các hệ cơ sở dữ liệu (CSDL) và công nghệ mạng máy tính. Động lực thúc đẩy sự phát triển mạnh mẽ của CSDLPT, nhu cầu tích hợp đa dạng các loại dữ liệu (DL) nhằm cung cấp nhiều loại hình dịch vụ cho ngƣời sử dụng. Thêm vào đó, với mục tiêu chia sẻ tài nguyên, khai thác, nâng cao khả năng tích hợp và trao đổi tài nguyên mạng cũng thúc đẩy quá trình sử dụng các hệ thống phân tán. Nhu cầu thu thập, lƣu trữ, xử lý và trao đổi thông tin ngày càng tăng, các hệ thống xử lý tập trung đã bộc lộ những nhƣợc điểm sau: [14][13] - Tăng khả năng lƣu trữ thông tin là khó khăn, bởi bị giới hạn tối đa của thiết bị nhớ. - Độ sẵn sàng phục vụ của CSDL không cao khi số ngƣời sử dụng tăng. - Khả năng tính toán của các máy tính đơn lẻ đang dần tới giới hạn vật lý. - Mô hình tổ chức lƣu trữ, xử lý dữ liệu tập trung không phù hợp cho những tổ chức kinh tế, xã hội có hoạt động rộng lớn, đa quốc gia. 1.1.1. Xử lý phân tán Hệ xử lý phân tán hay còn gọi là hệ thống tính toán phân tán đó là một hệ thống bao gồm một số đơn vị xử lý tự vận hành đƣợc liên kết thành mạng và hợp đồng thực hiện các nhiệm vụ mà chúng đƣợc phân công. Các đơn vị xử lý có thể thực hiện đƣợc các chƣơng trình tiền định trên đó. Những đối tƣợng đƣợc phân tán: - Các thiết bị xử lý, các chức năng xử lý: Các chức năng của hệ thống có thể đƣợc chuyển giao cho các thành phần hệ thống. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 2 - Dữ liệu: Dữ liệu đƣợc dùng bởi một số ứng dụng có thể đƣợc phân tán tới một số vị trí xử lý. - Quyền điều khiển: Quyền điều khiển một số nhiệm vụ cũng đƣợc phân tán. Phân loại các hệ thống phân tán: Chúng ta có thể phân loại các hệ thống phân tán theo các tiêu chí sau đây - Mức độ kết nối; - Sự liên đới giữa các thành phần; - Cấu trúc tƣơng giao; - Sự đồng bộ giữa các thành phần. Tại sao phải phân tán: - Nhằm thích ứng tốt hơn với việc phân bố rộng rãi của các công ty, xí nghiệp. - Nhiều ứng dụng công nghệ hiện đại cần đƣợc phân tán. Lý do của việc xử lý phân tán: Để thực hiện tốt hơn các bài toán lớn và phức tạp mà chúng gặp phải hiện nay bằng cách sử dụng quy tắc ”Chia để trị”. Các ƣu điểm cơ bản của xử lý phân tán: - Tận dụng đƣợc sức mạnh tính toán xử lý song song bằng cách sử dụng nhiều bộ xử lý đồng thời. - Giải quyết bài toán theo từng nhóm hoạt động độc lập nên có thể kiểm soát đƣợc chi phí phát triển phần mềm. - Các hệ cơ sở dữ liệu phấn tán cũng có thể đƣợc xem xét để phân tán nhằm mục đích xử lý hiệu quả hơn. Một số hệ thống xử lý hay đƣợc dùng: Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 3 - Hệ thống đa bộ xử lý có bộ nhớ chung (hình 1.1) Hình 1.1: Hệ đa bộ xử lý có bộ nhớ chung - Hệ đa bộ xử lý chia sẻ đĩa (shared disk) (hình 1.2 ) Hình 1.2: Hệ đa bộ xử lý có shared disk - Hệ đa bộ xử lý sở hữu cá nhân (hình1.3) Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 4 Hình 1.3: Hệ đa bộ xử lý sở hữu cá nhân Ghi chú: Phân bố vật lý không nhất thiết là phải cách xa nhau về mặt địa lý; chúng có thể ở trong cùng máy, một văn phòng,... Duy có điều là việc giao tiếp giữa chúng đƣợc thực hiện trên mạng và mạng máy tính đƣợc xem là tài nguyên dùng chung duy nhất. 1.1.2. Hệ cơ sở dữ liệu phân tán và hệ quản trị cơ sở dữ liệu phân tán Hệ CSDL phân tán (Distributed Database System – DDBS) là một tập hợp dữ liệu có liên đới logic và đƣợc phân bố trên các nút của một mạng máy tính. Hệ quản trị CSDL phân tán (Distributed Database Management System – DDBMS) là một hệ thống phần mềm cho phép quản lý các hệ CSDLPT và làm cho việc phân tán trở nên vô hình đối với ngƣời sử dụng. Nhƣ vậy hệ CSDLPT là một tập các tệp dữ liệu vừa có liên đới logic, vừa phải có cùng cấu trúc và vừa phải đƣợc truy xuất qua một giao diện chung. Và phân bố vật lý của các dữ liệu không phải là vấn đề quyết định. Nhận xét: Nếu CSDL nằm tại một nút mạng thì nó không phải là hệ CSDL phân tán, vì vấn đề quản trị CSDL không khác với quản trị CSDL trong môi trƣờng tập trung kiểu client/server của mạng. Nếu một cơ sở dữ liệu đƣợc phân tán trên nhiều nút mạng, khi đó CSDL sẽ là cơ sở dữ liệu phân tán (hình 1.4). Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 5 Hình 1.4: CSDL được phân tán trên mạng 1.1.3. Một số yêu cầu của hệ cơ sở dữ liệu phân tán a. Yêu cầu phân mảnh, nhân bản và vô hình Từ lý do xã hội và kinh tế xã hội phi tập trung, nên để có hiệu quả kinh tế ngƣời ta phân mảnh, nhân bản, phân tán và xử lý chúng tại các vị trí khác nhau. Ví dụ 1.1: Một công ty máy tính, có các văn phòng ở Hà Nội , Hải Phòng, Nha Trang và TP. Hồ Chí Minh, có một số dự án đƣợc thực hiện tại các địa điểm đó, và muốn dùng CSDL để quản lý nhân công, quản lý dự án và các dữ liệu liên quan khác. Giả sử CSDL là CSDL quan hệ , đƣợc cho bởi các quan hệ sau: - Quan hệ nhân viên: NhanVien(MaNV, TenNV, TrinhDoCM) Trong đó NhanVien là tên quan hệ nhân viên, MaNV là mã nhân viên - khóa chính, TenNV là tên nhân viên, TrinhDoCM là trình độ chuyên môn. - Quan hệ dự án: DuAn(MaDuAn, TenDuAn, NganSach) Trong đó MaDuAn là mã số dự án - khóa chính, TenDuAn - tên dự án và NganSach - ngân sách dự án. - Quan hệ trả lƣơng: TraLuong(TrinhDoCM, Luong) Trong đó TrinhDoCM là trình đọ chuyên môn - khóa chính, Luong - Tiền lƣơng. - Quan hệ phân nhiệm: PhanNhiem(MaNV, MaDuAn, ThoiGianLV, ChucVu) Trong đó PhanNhiem là quan hệ phân công nhiệm vụ, MaNV - khóa ngoại, MaDuAn - khóa ngoại, (MaNV, MaDuAn) - khóa chính, ThoiGianLV là thời gian làm việc, ChucVu là chức vụ. Yêu cầu phân mảnh CSDL Giả sử công ty đƣợc phân tán các vị trí khác nhau nhƣ Hà Nội, Hải Phòng, Nha Trang và TP. Hồ Chí Minh, nên công ty muốn để dữ liệu về các nhân viên các dự án của vị trí nào đƣợc lƣu ở vị trí đó, do đó cần phải phân hoạch các quan hệ NhanVien Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 6 và DuAn và lƣu chúng taị các vị trí nhƣ đã yêu cầu. Quá trình làm này đƣợc gọi là phân mảnh. Yêu cầu nhân bản Do yêu cầu về hiệu quả và độ tin cậy cho CSDL nên một phần dữ liệu đã đƣợc phân mảnh ở trên cần phải đƣợc lƣu bản sao tại một số vị trí khác. Quá trình này đƣợc gọi là nhân bản. Do tính chất phân tán của công việc kinh doanh của công ty, ngƣời ta muốn đặt dữ liệu về các nhân viên của văn phòng ở Hải Phòng đƣợc lƣu ở Hải Phòng, nhân viên của văn phòng ở Hà Nội đƣợc lƣu ở Hà Nội v.v… Nhƣ vậy cần có một qúa trình phân hoạch các quan hệ này và lƣu các phân hoạch đó tại các vị trí khác nhau. Yêu cầu vấn tin vô hình Ngƣời sử dụng đặt câu hỏi vấn tin nhƣ với CSDL tập trung tại một điểm nút nào đó mà họ muốn. Vô hình về độc lập dữ liệu là sự vô hình các chi tiết về cấu trúc lƣu trữ dữ liệu nó là dạng vô hình cơ bản của hệ quản trị CSDL phân tán và CSDL tập trung. Do định nghĩa CSDL nên thƣờng có hai mức độc lập là: mô tả cấu trúc logic của dữ liệu và định nghĩa về cấu trúc vật lý. Vì vậy, chúng ta có thể nói đến hai loại độc lập dữ liệu: mức logic thƣờng đƣợc xem là định nghĩa lƣợc đồ, còn mức vật lý đƣợc gọi là mô tả dữ liệu vật lý. - Độc lập dữ liệu về cấu trúc logic: Đó là tính độc lập của các ứng dụng với những thay đổi trong cấu trúc logic của CSDL; tức là nếu có một chƣơng trình ứng dụng nào đó truy xuất vào một tập con thuộc tính nào đó của CSDL thì nó sẽ không bị ảnh hƣởng nếu ta thêm hoặc bớt một số thuộc tính khác (không thuộc tập con thuộc tính trên) vào hoặc từ CSDL đã cho. - Độc lập dữ liệu về cấu trúc vật lý: là vô hình các chi tiết về cấu trúc lƣu trữ dữ liệu. Ngƣời viết ứng dụng không cần quan tâm đến dữ liệu để ở Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 7 đâu (ổ đĩa, hay băng từ, nút mạng,… ) và cách truy xuất dữ liệu (ví dụ tuần tự hay ngẫu nhiên). Vô hình liên kết mạng Ngƣời sử dụng đƣợc tách ra khỏi mọi chi tiết hoạt động của mạng, không biết có sự hiển diện của mạng - nghĩa là ngƣời sử dụng không biết là mình đang làm việc với CSDL tập trung hay phân tán. Vô hình liên kết mạng có thể đƣợc chia thành hai loại: - Vô hình vị trí: Vô hình vị trí là việc thực hiện một lệnh nào đó độc lập với vị trí dữ liệu đƣợc lƣu trữ. - Vô hình đặt tên: Vô hình đặt tên là ngƣời sử dụng dùng một tên duy nhất đƣợc hệ thống đặt trƣớc cho mỗi đối tƣợng CSDL mà không cần biết ai đặt tên đó và tên đó nằm ở đâu,... Nếu không có vô hình đặt tên ngƣời sử dụng bị buộc phải gắn tên vị trí làm thành phần tên của tên đối tƣợng. Chẳng hạn, HaiPhong, NhanVien, TenNV,… Vô hình nhân bản Vô hình nhân bản làm cho ngƣời sử dụng không thể biết họ đang làm việc với các quan hệ (hoặc các mảnh) gốc hay với các bản sao. Việc nhân bản sẽ làm tăng hiệu quả vì có thể làm giảm xung đột đƣờng truyền khi truy cập vào cơ sở dữ liệu, giảm thời gian truyền dữ liệu và tăng độ an toàn và bảo mật. Hơn nữa nếu một số máy lƣu dữ liệu có "hỏng hóc" thì các máy khác có thể truy cập đến các nhân bản khác,… Việc nhân bản gây ra nhiều khó khăn về cập nhật, vì khi một nhân bản có sự thay đổi (xóa, sửa, thêm,…) thì các nhân bản khác kể cả bản gốc liệu có cập nhật kịp thời hay không? Việc có nhân bản hay không, bao nhiêu bản, lƣu trữ của bản sao tại nút nào là tùy thuộc vào nhu cầu ứng dụng quyết định. Vô hình phân mảnh (Fragmentation transparency) Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 8 Vô hình phân mảnh làm cho ngƣời sử dụng không cần tham gia vào việc phân mảnh và không thể biết họ đang làm việc với CSDL gốc hay với các mảnh đã đƣợc phân mảnh từ CSDL gốc. Khi CSDL đƣợc phân mảnh, phải có cách xử lý các câu vấn tin của ngƣời sử dụng, các truy vấn này phải đƣợc thực hiện trên các mảnh. Tức là phải dịch câu truy vấn toàn cục thành nhiều câu truy vấn theo các mảnh. Nhƣ vậy vấn đề vô hình phân mảnh là kéo theo vấn đề vô hình xử lý các câu truy vấn. b. Kỹ thuật phân mảnh Thiết kế phân mảnh dữ liệu là công việc đầu tiên phải thực hiện. Mục đích của việc phân mảnh dữ liệu là tạo ra các đơn vị cấp phát logic, sao cho chi phí để thực hiện truy vấn thông tin là thấp nhất. Các bộ hoặc các thuộc tính của quan hệ không thể đƣợc xem nhƣ một đơn vị cấp phát, vì sẽ làm cho việc cấp phát trở lên phức tạp hơn. Thiết kế phân mảnh bằng cách nhóm một số bộ trong trƣờng hợp phân mảnh ngang hay nhóm các thuộc tính trong trƣờng hợp phân mảnh dọc có cùng đặc tính theo quan điểm cấp phát. Các mảnh hình thành bằng các phƣơng pháp phân mảnh tạo ra các đơn vị cấp phát dữ liệu khác nhau. Các quy tắc phân mảnh Các nguyên tắc để đảm bảo cơ sở dữ liệu khi phân mảnh sẽ đảm bảo tính không thay đổi về ngữ nghĩa. Dƣới đây là ba qui tắc phải tuân thủ khi phân mảnh cơ sở dữ liệu quan hệ. 1. Tính đầy đủ: Quan hệ R đƣợc phân rã thành các mảnh R1, R2…Rn, thì mỗi mục dữ liệu có trong quan hệ R sẽ đƣợc chứa trong ít nhất một mảnh R i (i=1,..,n). Quy tắc này đảm bảo cho các mục dữ liệu trong R đƣợc ánh xạ hoàn toàn vào các mảnh và không bị mất. Mục dữ liệu có thể hiểu là bộ trong phân mảnh ngang và thuộc tính trong phân mảnh dọc. 2. Tính phục hồi: Nếu một quan hệ R đƣợc phân rã thành các mảnh R1, R2,…,Rn. Khi đó nếu gọi FR là tập các mảnh thì: R = ∇ Ri, ∀ Ri∈ FR . Toán tử ∇ thay đổi tùy theo từng loại phân mảnh.. Khả năng phục hồi quan hệ từ các mảnh sẽ đảm bảo bảo toàn các phụ thuộc. Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/ 9 3. Tính tách biệt: Nếu quan hệ R đƣợc phân rã ngang thành các mảnh Ri, i=1,..n và mục dữ liệu di nằm trong một mảnh Ri thì nó sẽ không nằm trong mảnh Rk, (i≠k). Quy tắc này đảm bảo các mảnh phân rã rời nhau. Trong trƣờng hợp phân mảnh dọc, khóa chính của quan hệ phải có mặt trong tất cả các mảnh. Vì vậy tính tách biệt trong phân mảnh dọc đƣợc hiểu không liên quan gì đến khóa chính của quan hệ. Phân mảnh ngang Phân mảnh ngang chính là việc chia quan hệ thành nhiều các nhóm bộ. Kết quả của quá trình phân mảnh 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 mảnh 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 loại phƣơng pháp phân mảnh ngang là: - Phân mảnh ngang nguyên thủy: Là phân mảnh ngang đƣợc thực hiện trên các mệnh đề của chính quan hệ đó. - Phân mảnh ngang dẫn xuất: Là phân rã một quan hệ dựa trên các mệnh đề của quan hệ khác. Phân mảnh ngang nguyên thủy: Phân mảnh ngang nguyên thuỷ là phân rã một quan h ệ thành các tập gồm các bộ dƣ̣a trên các mệnh đề đƣơ ̣c định nghĩa trên quan hệ đó . Phân mảnh ngang nguyên thuỷ đƣơ ̣c định nghĩa bằng một thuật toán chọn trên các quan hệ nguồn của một lƣơ ̣c đồ CSDL. Mảnh ngang R i bao gồm các bộ của R đƣơ ̣c chọn ra theo công thức: Ri   Fi ( R) với 1≤ i ≤z. Trong đó, Fi là công thức chọn đƣơ ̣c sƣ̉ dụng để có đƣơ ̣c mảnh R i. Chú ý rằng chúng ta xét Fi có dạng chuẩn hội, nó là một mệnh đề hội sơ cấp (mi). Tái thiết phân mảnh ngang nguyên thủy là toán tử hợp  . Chẳng hạn: z R   Ri i 1 Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/