Tài liệu Thuật toán tụ năng lượng bea (bond energy algorithm) trong thiết kế cơ sở dữ liệu phân tán tuyển sinh trung học phổ thông tỉnh thái nguyên​

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG DƯƠNG VĂN LƯƠNG THUẬT TOÁN TỤ NĂNG LƯỢNG BEA (BOND ENERGY ALGORITHM) TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN TUYỂN SINH TRUNG HỌC PHỔ THÔNG TỈNH THÁI NGUYÊN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN - 2016 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 CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG DƯƠNG VĂN LƯƠNG THUẬT TOÁN TỤ NĂNG LƯỢNG BEA (BOND ENERGY ALGORITHM) TRONG THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN TUYỂN SINH TRUNG HỌC PHỔ THÔNG TỈNH THÁI NGUYÊN 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 NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Đỗ Trung Tuấn Thái Nguyên, 2016 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 những kế t quả trong luận văn là của viê ̣c tìm hiểu, có trích dẫn và tham chiế u đến các nguồ n tư liệu tin cậy. Nội dung luận văn không sao chép từ các kết quả của các luận văn, luận án khác. 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 tiên, tôi xin gửi lời cảm ơn đến trường Đại học Công nghệ thông tin và truyền thông Thái Nguyên, đã tạo điều kiện và tổ chức khóa học này để tôi có thể có điều kiện tiếp thu những kiến thức mới, có thời gian học tập và hoàn thành luận văn cao học này. Tôi xin chân thành cảm ơn các thầy cô đã truyền đạt cho chúng tôi những kiến thức quý báu trong quá trình học tập và làm luận văn. Tôi chân thành cảm ơn ta bè cùng lớp đã giúp đỡ, động viên tôi trong quá trình học tập cũng như thực hiện luận văn. Cuối cùng, tôi xin gửi thành quả này tới gia đình và người thân của tôi, những người đã hết lòng tạo điều kiện và động viên tôi để tôi có được kết quả ngày hôm nay. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn v Mục lục Lời cam đoan .................................................................................. iii Lời cảm ơn ......................................................................................... iv Mục lục ................................................................................................... v DANH MỤC CÁC TỪ VIẾT TẮT ..................................................... viii CÁC BẢNG, HÌNH VẼ......................................................................... ix MỞ ĐẦU ................................................................................................ 1 1. Lý do chọn đề tài ......................................................................... 1 2. Cấ u trúc luận văn ......................................................................... 5 Chương 1................................................................................................. 7 KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN .................................. 7 1.1. Hệ thống cơ sở dữ liệu tập trung .................................................. 7 1.2. Giới thiệu hệ thống cơ sở dữ liệu phân tán .................................. 8 1.3. Ưu điểm, nhược điểm hệ thống cơ sở dữ liệu phân tán ............... 9 1.3.1. Ưu điểm ................................................................................. 9 1.3.2. Khuyết điểm ........................................................................ 10 1.4. Các đặc điểm của hệ thống xử lý phân tán ................................ 10 1.5. Kiến trúc của một hệ CSDL phân tán ........................................ 11 1.6. Các hệ thống phân tán ................................................................ 13 1.6.1. Mô hình khách chủ .............................................................. 13 1.6.2. Mô hình phân tán ngang hàng ............................................. 14 1.6.3. Mô hình nhân bản chính - phụ ............................................ 15 1.6.4. So sánh các mô hình ............................................................ 16 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vi 1.7. Nhu cầu về cơ sở dữ liệu phân tán ............................................. 16 1.7.1. Công tác tuyển sinh THPT tỉnh Thái Nguyên..................... 16 1.7.2. Hạ tầng cơ sở dữ liệu về giáo dục Thái Nguyên ................. 19 1.7.3. Hạ tầng dịch vụ Internet tại Thái Nguyên và ứng dụng cho giáo dục .................................................................................................... 20 1.7.4. Nhu cầu thiết kế cơ sở dữ liệu phân tán phục vụ công tác tuyển sinh THPT ...................................................................................... 22 1.8. Kết luận chương ......................................................................... 24 Chương 2............................................................................................... 25 CƠ SỞ LÍ THUYẾT LIÊN QUAN ...................................................... 25 2.1. Phân đoạn dữ liệu ....................................................................... 25 2.1.1. Giới thiệu ............................................................................. 25 2.1.2. Nhu cầu phân đoạn dữ liệu .................................................. 26 2.1.3. Các điều kiện ràng buộc trong thiết kế phân đoạn .............. 27 2.2. Phân đoạn ngang ........................................................................ 28 2.3. Phân đoạn dọc ............................................................................ 28 2.3.1. Giới thiệu ............................................................................. 28 2.3.2. Quá trình phân đoạn ............................................................ 29 2.3.4. Thuâ ̣t toán tụ năng lượng BEA và ứng du ̣ng ...................... 30 2.3.5. Xác định ma trận sử du ̣ng các thuộc tính ............................ 35 2.3.6. Xây dựng ma trận hấp dẫn xếp cụm.................................... 36 2.3.7. Phân đoạn ma trận hấp dẫn ................................................. 43 2.4. Kết luận chương ......................................................................... 50 Chương 3............................................................................................... 51 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn vii THỬ NGHIỆM VÀ ỨNG DỤNG THỰC TẾ...................................... 51 3.1. Hệ thống cơ sở dữ liệu phục vụ tuyển sinh THPT tại Sở .......... 51 3.1.1. Sơ đồ cơ sở dữ liệu phân tán ............................................... 51 3.1.2. Các truy cập dữ liệu từ các trường ...................................... 52 3.2. Phân đoạn dọc ............................................................................ 52 3.2.1. Đặt vấ n đề ............................................................................ 52 3.2.2. Áp dụng thuâ ̣t toán tụ năng lượng BEA .............................. 53 3.2.3. Thực hiện với dữ liệu cụ thể................................................ 56 3.3. Các sơ đồ thuật toán ................................................................... 58 3.3.1. Chương trình chính.............................................................. 58 3.3.2. Thuật toán phân đoạn ma trận hấp dẫn phân cụm............... 58 3.3.3. Thuật toán tìm phần trên, phần dưới trong ma trận hấp dẫn59 3.4. Kết luận chương ......................................................................... 61 KẾT LUẬN ........................................................................................... 62 Kết quả luận văn đạt được ............................................................. 62 Phương hướng tìm hiểu và thực nghiệm tiếp theo của luận văn ... 63 TÀI LIỆU THAM KHẢO .................................................................... 64 Tiếng Việt ...................................................................................... 64 Tiếng Anh ...................................................................................... 64 PHỤ LỤC .......................................................................................... 65 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn viii DANH MỤC CÁC TỪ VIẾT TẮT CLR Server Common Language Runtime CNTT Công nghệ Thông tin CSDL Cơ sở dữ liệu CSDLPT Cơ sở dữ liệu phân tán DB Database, cơ sở dữ liệu DB2 Tên cơ sở dữ liệu của IBM DD Data Dictionary DDB Distributed DataBase DDBMS Distributed Data Base Management System GDDT Giáo dục và đào tạo GV Giáo viên HS Học sinh ICT Công nghệ thông tin và truyền thông IDE Integrated Development Environment ISO International Organization for Standardization Khách/ chủ Mô hình hệ thống máy chính - máy dự phòng Multitier Client – Server Mô hình đa khách - chủ Peer - to - Peer Mô hình nhóm làm việc RCS Revision Control System SQL Structured Query Language THPT Trung học phổ thong VNPT Vietnam Posts and Telecommunications Group XML eXtensible Markup Language Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn ix CÁC BẢNG, HÌNH VẼ Hình 1.1: Môi trường CSDL tập trung.............................................................. 7 Hình 1.2. Hệ thống cơ sở dữ liệu phân tán ....................................................... 8 Hình 1.3: Môi trường CSDL phân tán .............................................................. 9 Hình 1.4: Sơ đồ tạo CSDL phân tán ............................................................... 11 Hình 1.5: Sơ đồ quá trình tạo CSDL phân tán ................................................ 12 Hình 1.6. Hệ thống khách/ chủ........................................................................ 14 Hình 1.7. Mô phỏng hệ thống Khách/ chủ ...................................................... 15 Bảng 1.1: So sánh các mô hình phân tán ........................................................ 16 Hình 1.8. Trang Web của Sở GDDT Thái Nguyên ........................................ 16 Hình 1.8. Một số trang Web của các trường ................................................... 17 Bảng 1.2. Các trường THPT trong mạng lưới phân tán tại tỉnh Thái Nguyên 17 Hình 1.10. Cổng thông tin điện tử liên quan đến cơ sở dữ liệu văn bản ........ 19 Hình 1.11. Cơ sở dữ liệu tập trung .................................................................. 23 Hình 1.12. Hình dạng thí dụ về cơ sở dữ liệu phân tán đối với công tác tuyển sinh .................................................................................................................. 24 Hình 2.1. Minh họa về sự phân đoạn trên ổ đĩa .............................................. 25 Hình 2.2. Phân đoạn dữ liệu ............................................................................ 26 Hình 2.3. Minh họa tách bảng ......................................................................... 29 Hình 2.4. Bảng dữ liệu biết được khi thiết kế cơ sở dữ liệu ........................... 30 Bảng 2.1. Dữ liệu từ hình trên......................................................................... 30 Hình 2.5. Thí dụ về mức tụ năng lượng ME ................................................... 32 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn x Hình 2.6. Chương trin ̀ h SQL để khai báo lược đồ .......................................... 35 Bảng 2.2. Quá trình Pk truy cập Ci .................................................................. 35 Hình 2.7. Ma trận sử du ̣ng các thuộc tính ....................................................... 35 Hình 2.8. Các tần suất truy cập của các quá trình Pj ....................................... 36 Bảng 2.3. Các AFF tính được dựa trên các ACC, như kết quả trong hình 5 .. 36 Hình 2.9. Ma trận hấp dẫn xếp cụm ................................................................ 37 Hình 2.10. Ma trận hấp dẫn xếp cụm với đường chéo được tính lại .............. 37 Hình 2.11. Thí dụ tính BOND (C1, C3) ........................................................... 38 Hình 2.12. Xét C3 đối với cặp C1, Cp đã hình thành ....................................... 38 Hình 2.13. Thuộc tính C3 được đặt giữa C1, Cp do CONT (C1, C3, Cp) đạt max ......................................................................................................................... 39 Hình 2.14. Vị trí tương đối trước khi xét C4 ................................................... 40 Hình 2.15. Kết quả xếp cột C4......................................................................... 41 Hình 2.16. Cột C5 cần xếp đối với bốn cột đã có ............................................ 41 Hình 2.17. Ma trận hấp dẫn cuối cùng ............................................................ 43 Hình 2.18. Ma trận hấp dẫn cuối cùng đã sắp xếp .......................................... 43 Hình 2.19. Ma trận sử du ̣ng các thuộc tính, như hình 4, nhưng cho T truy cập nhiều Ai ........................................................................................................... 44 Hình 2.20. Chọn điểm x .................................................................................. 45 Hình 2.21. Ma trận đầu vào cho việc tìm x lần đầu ........................................ 46 Hình 2.22. Ma trận đầu vào đối với C5, C5 ..................................................... 47 Hình 2.23. Chuyển vị sau một lần tính giá trị cực đại .................................... 47 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn xi Hình 2.24. Ma trận chuyển vị, là cuối của bước này, đầu vào cho bước chọn x tiếp theo. .......................................................................................................... 48 Hình 2.25. Chuyển vị, nhưng không cần thiết. ............................................... 49 Hình 2.26. Phân đoạn trên ma trận ban đầu, tức ma trận hấp dẫn xếp cụm. .. 49 Hình 3.1. Hệ thống cơ sở dữ liệu phân tán ..................................................... 51 Hình 3.2. Các trạm phân tán được xét trong bài toán tuyển sinh. .................. 56 Hình 3.3. Các thuộc tính của dữ liệu trong bảng cơ sở dữ liệu sẽ phân rã. .... 56 Hình 3.4. Tác động của 8 câu hỏi thông thường trên các thuộc tính cơ sở dữ liệu ................................................................................................................... 56 Hình 3.5. Tần suất truy cập đến cơ sở dữ liệu từ 4 trạm theo 8 dạng câu hỏi. 57 Hình 3.6. Ma trận hấp dẫn cụm trước khi tính toán phân đoạn ...................... 57 Hình 3.7. Chương trình chính của bài toán phân đoạn quan hệ...................... 58 Hình 3.8. Thuật toán tụ năng lượng BEA theo [6. 10], dùng trong phân đoạn dọc ................................................................................................................... 59 Hình 3.9. Thuật toán tìm các phần, dùng để phân đoạn dọc. .......................... 60 Hình 3.10. Minh họa hình của chương 2. ....................................................... 61 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 1 MỞ ĐẦU 1. Lý do chọn đề tài Cùng với cả nước, tuyển sinh Trung học phổ thông (THPT) là kỳ thi cấp tỉnh diễn ra hàng năm của tỉnh Thái Nguyên. Đây là một trong những kỳ thi nhận được nhiều sự quan tâm của xã hội, cũng như các cấp quản lý, các nhà trường trong tỉnh. Đối với mỗi trường THPT về hoạt động tuyển sinh, bên cạnh việc đảm bảo chất lượng khách quan, công bằng đầu vào, thì các thông tin liên quan tới thí sinh là rất cần thiết cho việc biên chế lớp, thống kê, báo cáo các đợt trong năm học, cũng như việc quản lý học sinh sau này. Căn cứ vào hướng dẫn của Bộ Giáo dục và Đào tạo, hàng năm Sở Giáo dục và Đào tạo Thái Nguyên xây dựng kế hoạch và ban hành các văn bản hướng dẫn tuyển sinh vào lớp 10, đồng thời tổ chức các hội nghị tập huấn cho các lãnh đạo, cho các cán bộ phụ trách xây dựng cơ sở dữ liệu tuyển sinh của các nhà trường. Những năm qua, việc ứng dụng công nghệ thông tin trong quản lý thi tuyển sinh THPT tại tỉnh Thái Nguyên mới chỉ ở mức độ “thủ công”, chưa tận dụng được nhiều từ khả năng của lĩnh vực đó mang lại. Cụ thể: Trong nhiều năm qua kỳ thi sử dụng phần mềm Demo do người quản trị cơ sở dữ liệu viết trên hệ quản trị Virual FoxPro. Bên cạnh ưu điểm là người quản trị dễ dàng thực hiện thao tác trực tiếp trên dữ liệu như: ghép nối dữ liệu, sắp xếp, lọc, thống kê, báo cáo… thì nhiều hạn chế vẫn chưa được cải thiện. Đơn cử như, sau khi được tập huấn, cán bộ phụ trách máy tính các trường về triển khai nhập dữ liệu. Sau khi nhập xong, các trường ghi dữ liệu ra đĩa CD và nộp về máy tính của Sở (máy trung tâm). Từ máy trung tâm tiến hành ghép dữ liệu, sắp xếp phòng thi và in các mẫu ra giấy rồi chuyển về cho Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 2 các trường. Từ đây dữ liệu tuyển sinh cơ sở từ các trường (sau khi đã nộp sở) sẽ không còn giá trị sử dụng. Việc sửa chữa thông tin, nhập điểm, xử lý điểm thi diễn ra tại máy trung tâm và kết quả thi cũng in ra giấy gửi cho các trường. Đối với mỗi nhà trường, thông tin của học sinh từ dữ liệu tuyển sinh sẽ rất cần thiết trong suốt quá trình ba năm học THPT nếu như thí sinh đó trúng tuyển. Việc xây dựng dữ liệu tuyển sinh như trên không thể đáp ứng nhu cầu đó, cho nên thực trạng hiện nay, cùng một đối tượng nhưng các nhà trường phải quản lý ở ba lĩnh vực và ba cơ sở dữ liệu khác nhau trong ba năm học THPT, đó là: quản lý tuyển sinh – quản lý học sinh trong nhà trường – thí sinh thi tốt nghiệp THPT. Điều đó không chỉ tính nhất quán cơ sở dữ liệu không được đảm bảo mà còn gây lãng phí, tốn nhiều công sức và rất khó quản lý. Ngay nay cùng với sự phát triển mạnh mẽ về công nghệ, cơ sở hạ tầng thiết bị công nghệ thông tin và viễn thông cũng được đầu tư khá đầy đủ. Cụ thể các trường THPT trong tỉnh được trang bị nhiều máy tính với cấu hình cao, 100% được kết nối mạng Internet với đường truyền băng thông rộng, đội ngũ cán bộ phụ trách máy tính tại các đơn vị được đào tạo cơ bản, trình độ tin học ngày càng nâng cao... Một vấn đề cần quan tâm trong ứng dụng công nghệ thông tin trong ngành giáo dục quê hương Thái Nguyên là phân tích, thiết kế và xây dựng hệ thống thông tin nói chung, cơ sở dữ liệu giáo dục nói riêng. Cơ sở dữ liệu được hiểu theo cách định nghĩa kiểu kĩ thuật thì nó là một tập hợp thông tin có cấu trúc. Tuy nhiên, thuật ngữ này thường dùng trong công nghệ thông tin và nó thường được hiểu rõ hơn dưới dạng một tập hợp liên kết các dữ liệu, thường đủ lớn để lưu trên một thiết bị lưu trữ như đĩa hay băng. Dữ liệu này Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 3 được duy trì dưới dạng một tập hợp các tập tin trong hệ điều hành hay được lưu trữ trong các hệ quản trị cơ sở dữ liệu. Một khâu quan trọng trong phân tích phần mềm đó là việc phân tích và thiết kế cơ sở dữ liệu. Tất cả mọi hệ thống đều phải sử dụng một cơ sở dữ liệu của mình, đó có thể là một cơ sở dữ liệu đã có hoặc một cơ sở dữ liệu được xây dựng mới. Cũng có những hệ thống sử dụng cả cơ sở dữ liệu cũ và mới. Việc phân tích và thiết kế cơ sở dữ liệu cho một hệ thống có thể tiến hành đồng thời với việc phân tích và thiết kế hệ thống hoặc có thể tiến hành riêng. Vấn đề đặt ra là cần xây dựng một cơ sở dữ liệu giảm được tối đa sự dư thừa dữ liệu đồng thời phải dễ khôi phục và bảo trì. Như chúng ta đã biết, cơ sở dữ liệu là một tập hợp các dữ liệu có liên quan đến nhau dưới dạng các bản ghi trong các bảng. Khi phát triển các hệ thống tin học hóa người phát triển không chỉ cần thiết kế các tiến trình xử lý của hệ thống mà còn phải quan tâm đến cách tổ chức dữ liệu. Quá trình này chính là thiết kế cơ sở dữ liệu trong đó chỉ ra các loại dữ liệu được lưu trữ, lượng dữ liệu lưu trữ và cách tổ chức dữ liệu, v.v. Quá trình thiết kế cơ sở dữ liệu chính là quá trình lập kế hoạch và đưa ra cấu trúc của dữ liệu. Vậy tại sao lại cần phải thiết kế cơ sở dữ liệu? Câu trả lời là để có được một dự án hay một hệ thống thành công thì chúng ta không chỉ phải đảm bảo các tiến trình thực thi chính xác mà còn phải đảm bảo một cấu trúc dữ liệu hợp lý. Với việc xác định trước các yếu tố liên quan đến dữ liệu của môi trường xung quanh, chúng ta có thể tránh được các sai sót hay xung đột về sau. Khi thiết kế một cơ sở dữ liệu, chúng ta có thể phải dựa vào một hệ thống thực để mô hình hóa trong cơ sở dữ liệu. Quá trình này bao gồm việc quyết định các bảng cần tạo, các trường dữ liệu cũng như mối quan hệ giữa các bảng. Nếu quá trình này được thực hiện một cách rõ ràng, tự nhiên và tự Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 4 động thì rất tốt, nhưng thường thì không phải như vậy. Một cơ sở dữ liệu được thiết kế tốt cần phải có thời gian, công sức để chuẩn bị, xây dựng và cải tiến. Một cơ sở dữ liệu được thiết kế theo mô hình quan hệ mang lại rất nhiều lợi ích. Dưới đây liệt kê một số lợi ích này:  Giúp thêm mới, cập nhật, xóa dữ liệu hiệu quả hơn;  Việc truy xuất tổng hợp dữ liệu và chiết xuất báo cáo hiệu quả hơn;  Do cơ sở dữ liệu tuân theo mô hình đã được thiết kế tốt, chúng ta có thể biết trước hoạt động của chúng;  Với hầu hết dữ liệu được lưu trữ trong cơ sở dữ liệu mà không phải trong ứng dụng, bản thân cơ sở dữ liệu đã chứa đầy đủ thông tin;  Dễ dàng thay đổi cấu trúc cơ sở dữ liệu. Như đề cập ở trên, thiết kế cơ sở dữ liệu rất cần sự linh hoạt và sáng tạo. Dù là việc thiết kế cơ sở dữ liệu cần phải theo đúng các mô hình chuẩn hóa và mô hình quan hệ, cuối cùng chúng ta vẫn phải đưa ra một thiết kế thể hiện được nghiệp vụ của doanh nghiệp. Lý thuyết thiết kế cơ sở dữ liệu quan hệ thường đề cập đến những vấn đề cần tránh khi thiết kế nhưng lại không hướng dẫn chúng ta bắt đầu từ đâu và cách quản lý nghiệp vụ. Chính vì vậy ta cần phải hiểu rõ nghiệp vụ của tổ chức đó (hay hoàn cảnh nghiệp vụ) mà chúng ta đang mô hình hóa. Một cơ sở dữ liệu thiết kế tốt đòi hỏi người thiết kế phải hiểu rõ nghiệp vụ, cần có thời gian và kinh nghiệm. Là một giáo viên tin học công tác trong ngành giáo dục và đào tạo Thái Nguyên, học viên nhận thấy đây là một kỳ thi quan trọng, việc xây dựng một Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 5 cơ sở dữ liệu phù hợp với tình hình thực tế là rất cần thiết, đáp ứng nhu cầu quản lý, khai thác thông tin và sử dụng nguồn dữ liệu tại các đơn vị. Khi thiết kế cơ sở dữ liệu phân tán, đặc biệt trong phân đoạn dọc, người ta cần tính đến việc tụ năng lượng, ứng với việc xếp sắp các thuộc tính gần nhau. Người ta đã sử dụng thuật toán tụ năng lượng BEA để thực hiện việc này. Thuật toán được sử dụng trong một pha nhỏ của thiết kế phân đoạn dọc cơ sở dữ liệu phân tán. Vì vậy, học viên đã chọn đề tài: “Thuật toán tụ năng lượng BEA (Bond Energy Algorithm) trong thiết kế Cơ sở dữ liệu phân tán tuyển sinh Trung học phổ thông tỉnh Thái Nguyên” nhằm đưa ra giải pháp mới trong hoạt động quản lý thi tuyển sinh và đây cũng là nội dung nghiên cứu cho luận văn của mình. 2. Cấ u trúc luận văn Luận văn được chia thành các chương, với phần mở đầu và kết luận. Cuối luận văn là danh sách các tài liệu tham khảo và trích dẫn trong luận văn.  Chương 1 đề cập khái niệm về cơ sở dữ liệu phân tán, những đặc tính của cơ sở dữ liệu phân tán và những thách thức xử lí dữ liệu trong cơ sở dữ liệu so với cơ sở dữ liệu tập trung truyền thống. Ngoài ra chương 1 còn đề cập nhu cầu về cơ sở dữ liệu phân tán trên địa bàn công tác của học viên, tại Thái Nguyên;  Chương 2 đề cập cơ sở lí thuyết của vấn đề liên quan đến luận văn, tức việc thiết kế cơ sở dữ liệu phân tán, tập trung vào các ki ̃ thuâ ̣t phân rã dữ liệu. Hai kiểu phân rã dữ liệu (i) phân đoạn ngang; (ii) phân đoạn dọc và phân đoạn hỗn hợp được nêu ra, như kiến thức tìm hiểu thêm về hệ thống cơ sở dữ liệu phân tán. Chương 2 tập trung vào phân đoạn dọc, nên thuâ ̣t toán tụ năng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 6 lượng BEA trong thiết kế cơ sở dữ liệu phân tán dọc có ý nghĩa, được luận văn nghiên cứu và thử nghiệm;  Chương 3 trình bày thực nghiệm của luận văn, về thuâ ̣t toán tụ năng lượng và phân đoạn dọc, trong quá trình thiết kế cơ sở dữ liệu phân tán tại Thái Nguyên. Các kết quả này được ứng du ̣ng trong phân tích, thiết kế và xây dựng cơ sở dữ liệu phân tán, phục vụ công tác tuyển sinh tại các trường Trung học Phổ thông của Sở GDDT Thái Nguyên. Cuối luận văn là kết luận, với (i) kết quả luận văn đạt được; (ii) phương hướng tiếp tục tìm hiểu về lí thuyết và ứng du ̣ng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 7 Chương 1 KHÁI NIỆM VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN 1.1. Hệ thống cơ sở dữ liệu tập trung Theo [2], hệ cơ sở dữ liệu tập trung là tất cả dữ liệu đều nằm tại một vị trí, không có sự phân tán dữ liệu. Mạng máy tính mang tính cục bộ, dữ liệu không có tính sẵn sàng như cơ sở dữ liệu phân tán. Nút 2 Nút 1 Giao tiếp mạng Nút 3 Nút 5 Nút 4 Hình 1.1: Môi trường CSDL tập trung Hình trên cho thấy có tồn tại môi trường mạng lưới, nhưng chỉ có duy nhất nút 3 lưu trữ và quản lý dữ liệu, những nút còn lại không đảm nhiệm chức năng đó. Ưu điểm:  Dữ liệu được tập trung một nơi, dễ dàng cho việc xây dựng, bảo trì.  Dự phòng dữ liệu được loại bỏ, không phải lặp lại các phiên bản dữ liệu giống nhau cùng tồn tại trên các trạm. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 8  Tiết kiệm chi phí, không phải xây dựng thêm Server để lưu trữ dữ liệu. Khuyết điểm:  Khả năng tính toán của các máy tính đơn lẻ không thể đáp ứng các nhu cầu lớn của doanh nghiệp.  Độ sẵn sàng của cơ sở dữ liệu không cao khi lượng người sử dụng tăng.  Mô hình tổ chức lưu trữ, xử lý dữ liệu tập trung không còn phù hợp đối với các tổ chức và doanh nghiệp có hoạt động phạm vi rộng lớn, đa quốc gia, trên nhiều vùng lãnh thổ. 1.2. Giới thiệu hệ thống cơ sở dữ liệu phân tán Theo [1], cơ sở dữ liệu phân tán là tập hợp các cơ sở dữ liệu liên quan với nhau về mặt ngữ nghĩa được phân bố trên các máy tính của một mạng máy. Hình 1.2. Hệ thống cơ sở dữ liệu phân tán Hệ quản trị cơ sở dữ liệu phân tán (DDBS – Distributed Database System) là hệ thống phần mềm cho phép quản lý CSDL phân tán và đảm bảo các tính minh bạch trong CSDL phân tán đối với người dùng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn 9 1. Ứng dụng cục bộ: là ứng dụng giao tiếp giữa người dùng và dữ liệu trên một nút trong hệ CSDL phân tán và chỉ liên quan đến CSDL tại nút đó. 2. Ứng dụng toàn cục: yêu cầu truy cập dữ liệu ở nhiều nút thông qua hệ thống mạng máy tính. Nút 2 Nút 1 Giao tiếp mạng Nút 3 Nút 5 Nút 4 Hình 1.3: Môi trường CSDL phân tán 1.3. Ưu điểm, nhược điểm hệ thống cơ sở dữ liệu phân tán Nhận xét về ưu nhược điểm của hệ thống phân tán, theo [1], thấy một số khía cạnh sau: 1.3.1. Ưu điểm  Có thể quản lý cơ sở dữ liệu phân tán ở các mức trong suốt khác nhau: Ví dụ như minh bạch mạng, trong suốt vị trí, trong suốt nhân bản.  Dễ dàng co dãn dữ liệu.  Phản ánh cấu trúc của tổ chức: các phân đoạn dữ liệu được đặt ở những chi nhánh của tổ chức mà nó liên quan đến tạo ra hệ thống dữ liệu có cấu trúc tương ứng với tổ chức công ty đó.  Có thể tự trị dữ liệu tại điạ phương của mình: một chi nhánh tổ chức có thể quản lý, điều khiển dữ liệu của họ một cách độc lập. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn