Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu các đặc tính của phân mảnh dọc trong CSDL phân tán và ứng dụng

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

Thêm vào BST

Báo xấu

25
lượt xem 5
download

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

Luận văn này tập trung vào việc nghiên cứu các đặc trưng của phân mảnh dọc và áp dụng để thiết kế CSDL quản lý thông tin cung đường tỉnh Lạng Sơn, nơi tôi đang sống và công tác. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu các đặc tính của phân mảnh dọc trong CSDL phân tán và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ XUÂN OANH NGHIÊN CỨU CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC TRONG CSDL PHÂN TÁN VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN, NĂM 2020
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ XUÂN OANH NGHIÊN CỨU CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC TRONG CSDL PHÂN TÁN VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 84 8 01 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẤN KHOA HỌC TS. LÊ VĂN PHÙNG THÁI NGUYÊN, NĂM 2020
i LỜI CAM ĐOAN Tôi xin cam đoan toàn bộ nội dung luận văn này là do tôi tự sưu tầm, tra cứu thông tin trên mạng Internet, trong một số sách tham khảo để sắp xếp, hoàn thiện cho phù hợp với nội dung yêu cầu của đề tài. Đến nay, nội dung luận văn của tôi chưa từng được công bố hay xuất bản dưới bất kỳ hình thức nào. Nếu sai tôi xin chịu hoàn toàn trách nhiệm. Ngày 7 tháng 11 năm 2020 Tác giả Vũ Xuân Oanh
ii LỜI CẢM ƠN Trong suốt quá trình học tập và thực hiện đề tài, em đã nhận được sự giúp đỡ tận tình và những chỉ bảo ân cần của các Thày cô trong viện Công nghệ thông tin – Viện khoa học và công nghệ Việt nam, các Thày cô trong trường đại học Công nghệ Thông tin và Truyền thông, cùng các bạn bè đồng nghiệp. Đặc biệt là sự giúp đỡ của TS Lê Văn Phùng, người thầy trực tiếp hướng dẫn, đưa ra ý tưởng, định hướng, chỉnh sửa các kiến thức chuyên môn và tận tình giúp đỡ em trong suốt quá trình nghiên cứu và thực hiện luận văn. Qua đây cho phép em được bày tỏ lời cảm ơn tới tất cả các thầy cô giáo ở Viện Công nghệ thông tin và Trường Đại học Công nghệ Thông tin và Truyền thông, đã giảng dạy và tạo mọi điều kiện thuận lợi giúp đỡ chúng em trong quá trình học tập, nghiên cứu. Cuối cùng, tôi xin cảm ơn đến gia đình, các bạn bè đồng nghiệp đã chia sẻ động viên giúp đỡ tôi về chuyên môn cũng như về mọi mặt trong cuộc sống, đó là nguồn động viên khích lệ giúp tôi có nghị lực hơn để hoàn thành khoá học. Học viên Vũ Xuân Oanh
iii MỤC LỤC LỜI CAM ĐOAN ............................................................................................. i LỜI CẢM ƠN .................................................................................................. ii MỤC LỤC ....................................................................................................... iii DANH MỤC CÁC BẢNG VÀ CÁC HÌNH .................................................. v TRONG LUẬN VĂN ...................................................................................... v LỜI MỞ ĐẦU .................................................................................................. 1 Chương 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ PHÂN MẢNH .............................................................................................................. 1 1.1. Những nét chung nhất về cơ sở dữ liệu phân tán.................................... 3 1.2. Vấn đề phân mảnh trong cơ sở dữ liệu phân tán .................................... 8 1.2.1. Lý do phân mảnh .......................................................................... 8 1.2.2. Giải pháp phân mảnh .................................................................... 9 1.2.3. Mức độ phân mảnh ....................................................................... 9 1.2.4. Các quy tắc phân mảnh ................................................................. 10 1.2.5. Các chiến lược phân mảnh ............................................................ 11 Chương 2. CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC .......................... 13 2.1. Định hướng heuristic để phân mảnh dọc .............................................. 13 2.2. Đặc tính có nối không mất thông tin..................................................... 14 2.2.1. Khái niệm có nối không mất thông tin ......................................... 14 2.2.2. Thuật toán kiểm tra tính nối không mất thông tin ........................ 15 2.2.3. Thuật toán phân mảnh dọc có nối không mất thông tin ............... 18 2.3. Đặc tính bảo toàn phụ thuộc ................................................................. 20 2.3.1.Định nghĩa phân mảnh dọc bảo toàn phụ thuộc ............................ 20 2.3.4. Thuật toán kiểm tra phân mảnh dọc có nối không mất thông tin và bảo toàn phụ thuộc .................................................................................. 23 2.4. Phân mảnh dọc thành các BCNF, bảo toàn phụ thuộc, nối không mất thông tin ....................................................................................................... 26 2.4.1. Một số mệnh đề bổ trợ .................................................................. 27
iv 2.4.2. Thuật toán phân mảnh lược đồ quan hệ thành các BCNF, có nối không mất thông tin ................................................................................ 27 2.4.3. Thuật toán phân mảnh thành các BCNF, có bảo toàn phụ thuộc . 32 2.4.4. Thuật toán phân mảnh dọc thành các BCNF, có nối không mất thông tin và bảo toàn phụ thuộc .............................................................. 33 Chương 3. ỨNG DỤNG THIẾT KẾ CSDL VỀ THÔNG TIN CÁC CUNG ĐƯỜNG BỘ TRÊN ĐỊA BÀN LẠNG SƠN .................................. 36 3.1. Bài toán quản lý thông tin các cung đường bộ trên địa bàn TP. Lạng Sơn... 36 3.1.1. Giới thiệu Thành phố Lạng Sơn ................................................... 36 3.1.2. Hiện trạng quản lý thông tin các cung đường bộ trên địa bàn TP. Lạng Sơn ................................................................................................. 37 3.2. Thuật toán sử dụng và xác định dữ liệu đầu vào .................................. 38 3.2.1. Thuật toán sử dụng........................................................................ 38 3.2.2. Dữ liệu đầu vào ............................................................................. 38 3.3. Môi trường thử nghiệm ......................................................................... 40 3.4. Nội dung và kết quả thử nghiệm ........................................................... 41 3.4.1. Nội dung thiết kế cơ sở dữ liệu các cung đường TP. Lạng Sơn .. 41 3.4.2. Phương án đề xuất phân mảnh dữ liệu (nếu có yêu cầu xây dựng CSDL phân tán) ...................................................................................... 46 3.4.3. Một số giao diện chính .................................................................. 51 3.4.4. Hướng dẫn sử dụng chương trình thử nghiệm ............................. 53 3.5. Đánh giá chương trình thử nghiệm ....................................................... 58 PHẦN KẾT LUẬN ........................................................................................ 62 TÀI LIỆU THAM KHẢO ............................................................................ 63
v DANH MỤC CÁC BẢNG VÀ CÁC HÌNH TRONG LUẬN VĂN Bảng 3.1.Bảng so sánh nội dung các bước trong quy trình thiết kế CSDL mức logic ................................................................................................................. 59 Hình 1.1. Minh họa về một DDBS.................................................................... 7 Hình 1.2. CSDL tập trung, không phải là DDBS.............................................. 8 Hình 2.1. Một bảng gồm hai hàng tổng quát .................................................. 17 Hình 3.1. Mô hình Thực thể- Mối quan hệ (Mô hình E_R): .......................... 45 Hình 3.2. Sơ đồ định vị của các mảnh tại các vị trí ........................................ 48 Hình 3.3. Các mảnh và hình ảnh vật lý của một quan hệ tổng thể ................. 49 Hình 3.4. Mô hình mạng của hệ thống quản lí các cung đường ..................... 50 Hình 3.5. Giao diện trang chủ ......................................................................... 51 Hình 3.6.Giao diện nhập liệu .......................................................................... 51 Hình 3.7. Giao diện tìm khóa .......................................................................... 52 Hình 3.8. Giao diện phân mảnh thành hệ lược đồ đạt 3NF ............................ 52 Hình 3.9. Các bước thiết kế CSDL mức logic trong mô hình CSDL tập trung ......................................................................................................................... 59
1 LỜI MỞ ĐẦU Cơ sở dữ liệu (CSDL) phân tán là một lĩnh vực được nghiên cứu từ lâu, nhưng gần đây do sự phát triển nhanh chóng của công nghệ truyền tin và mạng interrnet, cùng với xu thế toàn cầu hoá trong mọi lĩnh vực, đặc biệt trong lĩnh vực phân tán dữ liệu và thiết kế, CSDL phân tán đã trở thành một lĩnh vực thu hút nhiều sự quan tâm của các nhà nghiên cứu trong lĩnh vực CNTT. Khái niệm phân tán (hoặc phân mảnh) ở đây được hiểu là phân tán thông tin và các thông tin đó được chứa trên các máy tính ở các vị trí khác nhau của một hệ thống máy tính có liên hệ với nhau được gọi là mạng máy tính. Việc phân mảnh sẽ làm tăng mức độ hoạt động đồng thời (song song) và như thế làm tăng lưu lượng hoạt động của hệ thống. Việc phân mảnh được tiến thành theo 2 cách ngang và dọc. Trong đó việc chia dọc một quan hệ thành các quan hệ con chứa một tập con các thuộc tính của quan hệ gốc được gọi là phân mảnh dọc. Việc phân mảnh dọc có nhiều đặc trưng (đặc tính) quan trọng đã và đang được tập trung nghiên cứu ở trong cũng như ngoài nước cả về mặt lý luận cũng như ứng dụng thực tiễn. Đặc biệt trong lĩnh vực thiết kế, cho phép các vấn tin ảnh hưởng đến các quan hệ nhỏ hơn, vì thế giảm bớt truy xuất và tiết kiệm bộ nhớ. Phân mảnh dọc được nghiên cứu trong ngữ cảnh của các hệ CSDL cả tập trung và phân tán. Tuy CSDL phân tán được phát triển từ CSDL tập trung nhưng nó vẫn có những ứng dụng gía trị để thiết kế CSDL tập trung. Với mong muốn nắm vững hơn các tri thức phục vụ công tác nghiên cứu chuyên môn cũng như áp dụng vào đời sống kinh tế -xã hội cùng với sự gợi ý của Thầy hướng dẫn, tôi đã lựa chọn đề tài "Nghiên cứu các đặc tính của phân
2 mảnh dọc trong CSDL phân tán và ứng dụng" để làm luận văn tốt nghiệp thạc sĩ. Luận văn này tập trung vào việc nghiên cứu các đặc trưng của phân mảnh dọc và áp dụng để thiết kế CSDL quản lý thông tin cung đường tỉnh Lạng Sơn, nơi tôi đang sống và công tác.
3 Chương 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ PHÂN MẢNH 1.1. Những nét chung nhất về cơ sở dữ liệu phân tán Cơ sở dữ liệu (CSDL) phân tán là một tập hợp các dữ liệu phục thuộc logic lẫn nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính. CSDL phân tán làm tăng khả năng truy nhập tới CSDL lớn trên mạng. Trong hệ thống đó mỗi máy tính quản lý một CSDL thành phần được gọi là 1 node hoặc site. Hệ quản trị CSDL phân tán (DBMS) là phần mềm quản trị CSDL, đảm bảo trong suốt đối với người sử dụng và cho phép tính tự trị nghĩa là mỗi cơ sở dữ liệu thành phần vẫn được quản trị độc lập và riêng biệt [5]. Định nghĩa này nhấn mạnh 2 khía cạnh quan trọng của CSDL phân tán: 1- Tính phân tán: thực tế dữ liệu không cư trú ở cùng một trạm, vì vậy chúngta có thể phân biệt một CSDL phân tán với CSDL tập trung. 2- Sự tương quan logic: Các dữ liệu có một số tính chất ràng buộc lẫn nhauvà như vậy có thể phân biệt CSDL phân tán với tập các CSDL địa phương hoặc với các tệp ở các trạm khác nhau trên mạng. 3 - Các đặc trưng trong suốt của CSDL phân tán thể hiện ở chỗ: +Trong suốt phân tán: Cho phép xử lý dữ liệu trên hệ CSDL phân tán giống như đối với CSDL tập trung. Người sử dụng (NSD) không cần biết dữ liệu đã được phân mảnh như thế nào, các bản sao dữ liệu để ở đâu, vị trí vật lý lưu trữ dữ liệu ở đâu. Trong suốt phân tán thể hiện: + Trong suốt địa điểm: NSD không cần biết lưu trữ vật lý của dữ liệu ở đâu, mà có quyền truy cập đến CSDL tại bất cứ nút nào trên mạng. Trong truy vấn chỉ cần chỉ ra tên dữ liệu mà không cần chỉ ra vị trí. Các thao tác để lấy hoặc cập nhật một dữ liệu từ xa được tự động thực hiện bởi hệ thống tại địa điểm đưa ra yêu cầu. Tính trong suốt về vị trí rất hữu ích, nó cho phép người
4 dùng bỏ qua các bản sao dữ liệu đã tồn tại ở mỗi vị trí. Do đó có thể di chuyển một bản sao dữ liệu từ một nút này đến một nút khác và cho phép tạo các bản sao mới mà không ảnh hưởng tới các ứng dụng; + Trong suốt tên: Khi một đối tượng đã được đặt tên thì có thể truy nhập chính xác không cần đặc tả thêm; + Trong suốt bản sao: Sự nhân bản là quá trình sao chép và duy trì dữ liệu trong hệ CSDL phân tán. Cùng một dữ liệu (được lưu trữ vật lý tại một vị trí) có thể sử dụng được trên nhiều vị trí khác nhau. Các bản sao có thể được lưu trữ trên nhiều nút làm tăng hiệu suất, độ tin cậy và tính sẵn sàng của hệ thống. Các ứng dụng có thể truy nhập dữ liệu tại các nút mà không cần phải truy cập từ xa giảm truyền tải trên mạng lớn. Hệ thống cho phép tiếp tục thực hiện nếu như các nút từ xa có sự cố. Trong suốt bản sao bảo đảm NSD không biết đó là các bản sao vì dữ liệu luôn được cập nhật và đồng bộ với dữ liệu gốc. - Trong suốt phân mảnh: Một quan hệ trong CSDL phân tán có thể phân mảnh ngang hoặc phân mảnh dọc nghĩa là được tách thành các bộ dữ liệu hoặc các quan hệ con và lưu trữ trên nhiều nút khác nhau. Trong suốt phân mảnh cho phép NSD không cần biết có sự phân mảnh, các truy vấn dữ liệu vẫn được viết như CSDL tập trung. - Trong suốt giao dịch: CSDL phân tán cho phép một giao dịch có thể cập nhật, sửa đổi dữ liệu trên các nút khác nhau. - Trong suốt thất bại: Đảm bảo tại một nút của hệ thống bị hỏng thì hệ thống vẫn làm việc bình thường (do cơ chế tạo bản sao hoặc làm việc trên các nút không bị sự cố). - Trong suốt thao tác: Cho phép các câu lệnh thao tác các dữ liệu đơn giản để truy nhập được các CSDL tại nút cục bộ hoặc nút từ xa. Các thao tác xử lý dữ liệu từ xa không phức tạp và đảm bảo vẫn giống như khi thao tác dữ liệu trên hệ CSDL không phân tán.
5 - Trong suốt về tính không thuần nhất: Cho phép hỗn hợp nhiều hệ quản trị CSDL khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử lý giao tác phân tán trên toàn hệ thống. 4- Đối với CSDL tập trung, tính dư thừa hạn chế được càng nhiều càng tốt. Trong khi đó, CSDL phân tán có tính dư thừa dữ liệu vì: - Tính cục bộ của chương trình ứng dụng sẽ tăng nếu dữ liệu đặt ở nhiều nơi mà chương trình ứng dụng cần. - Khả năng sẵn sàng của hệ thống cao bởi vì khi có lỗi ở một nơi nào đó trong hệ thống thì không ảnh hưởng đến hoạt động của chương trình ứng dụng. 5. Trong CSDL phân tán, dữ liệu được chia ra thành nhiều phần nhỏ và chỉ có một bản sao logic tổng thể duy nhất để tiện cho việc truy xuất dữ liệu; cấu trúc truy xuất phức tạp không phải là công cụ chính để truy xuất hiệu quả (hiệu quả theo nghĩa là thời gian tìm kiếm và chuyển dữ liệu nhỏ nhất, chi phí truyền thông thấp nhất). Mỗi cách thức truy xuất CSDL phân tán được người lập trình viết hoặc tạo ra bởi một bộ tối ưu. Cách viết và truy cập CSDL phân tán cũng giống như viết chương trình duyệt trong CSDL tập trung. Công việc mà chương trình duyệt này làm là xác định xem có thể truy cập đến được bao nhiêu CSDL con. 6. Trong CSDL phân tán, vấn đề điều khiển giao tác tự trị có ý nghĩa quan trọng. Giao tác tự trị là phương tiện đạt được sự toàn vẹn trong CSDL; Mặt khác, vấn đề an toàn CSDL cũng phức tạp hơn vì còn liên quan đến mạng truyền thông. CSDL phân tán có một số ưu và nhược điểm sau:
6 1. Ưu điểm: Tính hữu dụng cơ bản nhất của CSDL phân tán là dữ liệu của các CSDL vật lý riêng biệt được tích hợp logic với nhau giúp NSD trên mạng có thể truy nhập được. Nó có khả năng: - Cho phép quản lý dữ liệu với nhiều mức trong suốt. Hệ quản trị CSDL phân tán cung cấp khả năng trong suốt phân tán với ý nghĩa che giấu đặc tính phân tán với NSD. - Tăng độ tin cậy và khả năng sẵn sàng. Đối với CSDL tập trung thì CSDL được đặt tại một nút nên khi có sự cố sẽ khó khôi phục và khó xử lý, bị ngừng khả năng làm việc khi gặp sự cố. Đối với CSDL phân tán thì độ tin cậy ở đây là hệ thống đang làm việc (không bị ngừng) tại thời điểm nào đó, tính sẵn sàng của hệ thống vẫn tiếp tục làm việc. Khi dữ liệu và CSDL phân tán trên một vài nút, một nút có thể gặp sự cố trong khi các nút khác vẫn có thể hoạt động hoặc sử dụng các thành phần khác của CSDL. Chỉ trên các nút bị sự cố, dữ liệu và ứng dụng không thể truy cập được. Để nâng cao độ tin cậy và tính sẵn sàng, có thể áp dụng cơ chế tạo bản sao trên nhiều nút. - Cải thiện hiệu năng, do dữ liệu của CSDL phân tán được đặt gần nơi xử lý nên hiệu năng được cải thiện đáng kể. - Cho phép thêm CSDL mới, tăng kích cỡ CSDL, thêm bộ xử lý, thêm các CSDL thành phần trong CSDL phân tán. 2. Nhược điểm: - Độ phức tạp thiết kế và cài đặt hệ thống tăng: Hệ quản trị CSDL phân tán phải bổ sung thêm các chức năng như: + Theo dõi dấu vết dữ liệu; + Xử lý các truy vấn phân tán; + Quản lý giao dịch phân tán; + Phục hồi CSDL phân tán;
7 + Quản lý các bản sao; + Quản lý thư mục - catalog phân tán. - Khó điều khiển tính nhất quán về dữ liệu; - Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng là rất khó khăn;. - Bảo mật khó khăn. Ở mức vật lý, những đặc trưng phân tán được thể hiện rõ: - Có nhiều máy tính được gọi là các nút/trạm; - Các nút này phải được kết nối bởi một kiểu mạng truyền thông để truyền dữ liệu và những câu lệnh giữa các nút với nhau. Mỗi nút có thể truy nhập dữ liệu ở các nút khác. Khác với mô hình dữ liệu tập trung (tài nguyên tập trung tại một máy tính), CSDL trong hệ thống CSDL phân tán được chứa trong nhiều máy tính (nút), các máy tính này được nối với nhau qua các hệ thống truyền thông và chúng không chia sẻ bộ nhớ chung cũng như không dùng chung đồng hồ. Các bộ xử lý trong hệ thống phân tán có kích cỡ và chức năng khác nhau (chẳng hạn có thể bao gồm các bộ vi xử lý, trạm làm việc, máy tính mini, hay các máy lớn vạn năng). Workstation 1 Workstation 2 Workstation 5 Mạng M¹truyền số ng truyÒnliệu CSDL d÷ liÖu CSDL Workstation 4 Workstation 3 CSDL CSDL Hình 1.1. Minh họa về một DDBS
8 Chú ý rằng, nếu CSDL nằm tại một nút mạng thì hệ thống đó không phải là DDBS: Workstation 1 Workstation 2 Workstation 5 Mạng truyền dữ liệu Workstation 4 Workstation 3 Hình 1.2. CSDL tập trung, không phải là DDBS 1.2. Vấn đề phân mảnh trong cơ sở dữ liệu phân tán Trong quá trình thiết kế, các quan hệ được phân mảnh thành các quan hệ nhỏ hơn. Các câu hỏi có tương hỗ lẫn nhau được quan tâm gồm: 1. Tại sao lại cần phân mảnh? 2. Chúng ta nên phân mảnh như thế nào? 3. Chúng ta nên phân thành bao nhiêu mảnh? 4. Có cách nào để kiểm tra tính chính xác của sự phân mảnh? 5. Chúng ta nên cấp phát các mảnh như thế nào cho các nút? 6. Thông tin cần thiết cho phân mảnh và cấp phát là gì? 1.2.1. Lý do phân mảnh Theo quan điểm phân tán dữ liệu, không phân mảnh giá trị dữ liệu. Trong các hệ thống tệp phân tán, việc phân tán được thực hiện trên cơ sở toàn bộ các tập tin. Đối với phân mảnh, vấn đề quan trọng là đơn vị phân tán thích hợp. Một quan hệ không phải là một đơn vị phù hợp. Vì sao vậy?. Lý do thứ nhất, việc truy cập các ứng dụng tại các nút được xác định không phải trên toàn bộ quan hệ mà chỉ trên các tập con của chúng. Lý do thứ hai, nếu các ứng dụng có các
9 khung nhìn đã xác định trên một quan hệ nhất định ở các nút khác nhau thì việc phân mảnh giúp ích cho việc không phải truy cập dữ liệu từ xa, không gây ra các rắc rối trong cập nhật và không gặp vấn đề giới hạn lưu trữ của kho. Lý do cuối cùng, sự phân mảnh kéo theo khả năng truy vấn song song, do đó làm tăng mức độ xử lý đồng thời. Tuy vậy, việc phân mảnh cũng gây ra nhiều khó khăn. Nếu các ứng dụng có các yêu cầu mâu thuẫn ngăn cản việc tách quan hệ thành các quan hệ con riêng biệt, các ứng dụng mà quan điểm được xác định trên nhiều hơn một quan hệ con có thể bị giảm hiệu suất. Chẳng hạn, việc lấy dữ liệu từ hai mảnh và kết nối chúng là rất phức tạp. Cực tiểu hoá các liên kết đã phân tán là một bài toán cơ bản về phân mảnh. Vấn đề thứ hai liên quan đến kiểm soát ngữ nghĩa dữ liệu, đặc biệt là để kiểm tra tính toàn vẹn. Do phân mảnh, các thuộc tính có thể bị phân bổ trong các quan hệ con khác nhau tại các nút khác nhau. 1.2.2. Giải pháp phân mảnh Mô hình quan hệ được biểu diễn ở dạng bảng, vì vậy vấn đề là tìm ra những cách chia một bảng thành các bảng nhỏ hơn. Rõ ràng có hai lựa chọn: chia nó theo chiều ngang (horizontal) hoặc theo chiều dọc (vertical). 1.2.3. Mức độ phân mảnh Quyết định mức độ phân mảnh CSDL là một quyết định quan trọng ảnh hưởng đến việc thực hiện truy vấn. Trên thực tế, các vấn đề liên quan đến lý do phân mảnh là một tập con của các câu trả lời cho câu hỏi chúng ta đang giải quyết ở đây. Mức độ phân mảnh đi từ một cực, nghĩa là không phân mảnh, sang cực khác, để phân mảnh đến mức từng bộ (trong trường hợp phân mảnh ngang) hoặc với mức mỗi thuộc tính (trong trường hợp phân mảnh dọc).
10 Tất nhiên, sự phân mảnh có thể được lồng nhau. Nếu tổ hợp theo nhiều kiểu, người ta sẽ nhận cách phân mảnh hỗn hợp. Mặc dù chúng ta không coi phân mảnh hỗn hợp là một chiến lược phân mảnh nguyên thủy, nhiều phân vùng thực tế có thể là hỗn hợp. Chúng ta đã biết về các bất lợi của các đơn vị phân mảnh rất lớn và rất nhỏ. Điều mà chúng ta cần là tìm ra mức độ phân mảnh phù hợp là sự thỏa hiệp giữa hai thái cực. Mức độ như vậy chỉ có thể được xác định đối với các ứng dụng sẽ hoạt động trên CSDL. Vấn đề là làm thế nào? Nói chung, các ứng dụng cần phải được đặc trưng với một số tham số. Các mảnh riêng lẻ có thể được xác định theo các giá trị của các tham số này. Trong phần sau chúng ta sẽ mô tả các đặc tính này có thể được thực hiện như thế nào cho các kiểu phân mảnh đã lựa chọn 1.2.4. Các quy tắc phân mảnh Chúng ta sẽ thực thi ba quy tắc đồng thời sau trong quá trình phân mảnh để bảo đảm rằng CSDL không bị thay đổi ngữ nghĩa trong quá trình phân mảnh [5]. 1. Tính đầy đủ (completeness). Nếu một quan hệ R bị phân mảnh thành n quan hệ con FR = {R1, R2,. . . , Rn}, mỗi thuộc tính trong R cũng có thể được tìm thấy trong một hoặc nhiều hơn các Ri. Đặc tính này bảo đảm rằng các dữ liệu trong một quan hệ toàn cục được ánh xạ thành các quan hệ con mà không bị tổn thất. Lưu ý rằng trong trường hợp phân mảnh ngang, người ta thường nhắm đến một “bộ”, trong khi trong trường hợp phân mảnh theo chiều dọc, nhắm đến một “thuộc tính”. 2. Tính tái thiết (reconstruction). Nếu một quan hệ R được phân mảnh thành n mảnh FR = {R1, R2, . . . , Rn}, thì có thể xác định một toán tử quan hệ  sao cho: R =Ri, Ri FR
11 Toán tử  sẽ khác nhau cho các dạng phân mảnh khác nhau (ngang hay dọc); Tuy nhiên, điều quan trọng là nó có thể xác định được. Khả năng tái cấu trúc lại quan hệ từ các mảnh của nó bảo đảm rằng các ràng buộc xác định trên dữ liệu sẽ được duy trì. 3. Tính tách rời (disjointness). Nếu một quan hệ R được phân mảnh theo chiều ngang thành n mảnh FR = {R1, R2,..., Rn} và bộ dữ liệu (bản ghi) tj nằm trong Rj thì nó không nằm trong bất kỳ quan hệ con Rk khác (k ≠ j) để bảo đảm các mảnh ngang là rời nhau. Nếu quan hệ R được phân mảnh theo chiều dọc, thì các khóa chính của nó phải lặp lại trong tất cả các mảnh của nó (để tái thiết). Do đó, trong trường hợp phân mảnh dọc, sự tách rời chỉ được xác định trên các thuộc tính không phải là khóa chính của quan hệ. 1.2.5. Các chiến lược phân mảnh Có hai chiến lược phân mảnh cơ bản: ngang và dọc. Từ đó, có thể mở rộng thành chiến lược tích hợp phân mảnh kiểu lai ghép (hybrid) [5]. 1. Phân mảnh ngang Phân mảnh ngang phân rã một quan hệ bằng cách cắt khúc quan hệ đó. Do đó mỗi khúc có một tập con giá trị của các bộ trong quan hệ. Như vậy, phân mảnh ngang chính là việc chia quan hệ thành nhiều 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 kỹ thuật phân mảnh ngang: nguyên thủy (primary) và dẫn xuất (derived). Phân mảnh ngang nguyên thủy của một quan hệ được thực hiện bằng cách sử dụng các vị từ (predicate) được định nghĩa trên chính quan hệ đó. Còn phân mảnh ngang dẫn xuất là sự phân rã quan hệ nhờ các vị từ được định nghĩa trên quan hệ khác.
12 2. Phân mảnh dọc Phân mảnh dọc (Vertical Fragmentation) một quan hệ R là việc phân mảnh để tạo ra các mảnh con R1, R2,..., Rrmà mỗi mảnh con chứa một tập con các thuộc tính của R cùng với khóa chính của R. Mục tiêu của phân mảnh dọc là chia một quan hệ thành một tập các quan hệ nhỏhơn để nhiều ứng dụng có thể thực hiện trên một mảnh. Như vậy, phân mảnh "tối ưu" là sinh ra một lược đồ phân mảnh để giảm thiểu thời gian thực hiện của các ứng dụng chạy trên các mảnh này. Phân mảnh dọc cho phép các truy vấn với quan hệ nhỏ hơn, do đó dẫn đến một số lượng nhỏ các truy cập đến nút.
13 Chương 2. CÁC ĐẶC TÍNH CỦA PHÂN MẢNH DỌC 2.1. Định hướng heuristic để phân mảnh dọc Một phân mảnh dọc cho một quan hệ r (có R thuộc tính) sinh ra các mảnh r1,r2,...rk, mỗi mảnh chứa một tập con thuộc tính của R và cả khóa của r. Mục đích của phân mảnh dọc là phân hoạch một quan hệ thành tập các quan hệ nhỏ hơn để nhiều ứng dụng có thể chỉ chạy trên 1 quan hệ. Trong ngữ cảnh này, một phân mảnh “tối ưu” là một phân mảnh sinh ra một lược đồ phân mảnh cho phép giảm tối đa thời gian thực thi các ứng dụng chạy trên các mảnh đó. Phân mảnh dọc đã được nghiên cứu trong ngữ cảnh của các hệ CSDL tập trung lẫn phân tán. Lý do chính trong ngữ cảnh tập trung là sử dụng nó làm một công cụ thiết kế, cho phép các vấn tin ảnh hưởng đến các quan hệ nhỏ hơn, vì thế giảm bớt số truy xuất và tiết kiệm bộ nhớ. Phân mảnh dọc tất nhiên phức tạp hơn so với phân mảnh ngang vì do tổng số chọn lựa có thể có của phân hoạch dọc rất lớn. Để có được các lời giải tối ưu cho bài toán phân mảnh dọc thực sự rất khó nên người ta đã đưa ra 2 loại heuristic cho phân mảnh dọc một quan hệ[8]: 1.Nhóm thuộc tính: bắt đầu bằng cách gán mỗi thuộc tính cho một mảnh, và tại mỗi bước, nối một số mảnh lại cho đến khi thỏa mãn một tiêu chuẩn nào đó. Kỹ thuật nhóm thuộc tính được Hammer and Niamir đề xuất lần đầu năm 1979 cho các CSDL tập trung và về sau được Sacca và Wiederhold dùng năm 1985 cho các CSDL phân tán. 2.Tách mảnh: bắt đầu bằng một quan hệ và quyết định cách phân mảnh có lợi dựa trên hành vi truy xuất của các ứng dụng trên các thuộc tính. kỹ thuật này được Hoffer and Severance thảo luận lần đầu tiên cho thiết kế CSDL tập trung năm1975, sau đó được Navathe và các đồng tác giả mở rộng cho môi trường phân tán năm 1984.