Luận văn Thạc sĩ Khoa học máy tính: Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán

Đề tài phân tích, trình bày một cách có hệ thống các nghiên cứu về cơ sở dữ liệu quan hệ, nghiên cứu các phương pháp thiết kế cơ sở dữ liệu phân tán, các kỹ thuật tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, cài đặt thử nghiệm một số thuật toán tối ưu hóa câu truy vấn trong cơ sở dữ liệu phân tán, từ đó đưa ra lựa chọn phù hợp với từng bài toán trên thực tế.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Khoa học máy tính: Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán ĐẠI HỌC THÁI NGUYÊNTRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG LƢƠNG KIM CƢƠNG TỐI ƢU HÓA TRUY VẤN TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2019 ĐẠI HỌC THÁI NGUYÊNTRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN&TRUYỀN THÔNG LƢƠNG KIM CƢƠNG TỐI ƢU HÓA TRUY VẤN TRONG CÁC CƠ SỞ DỮ LIỆU PHÂN TÁN Chuyên ngành: Khoa học máy tính Mã số: 8480101 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. ĐOÀN VĂN BAN Thái Nguyên - 2019 LỜI CAM ĐOAN Tôi xin cam đoan, kết quả của luận văn hoàn toàn là kết quả của tự bản thântôi tìm hiểu và nghiên cứu thông qua tham khảo các tài liệu và được thực hiện dướisự hướng dẫn của PGS.TS Đoàn Văn Ban . Các tài liệu tham khảo được trích dẫnvà chú thích đầy đủ. Tác giả Lương Kim Cương LỜI CẢM ƠN Lời đầu tiên, tôi xin chân thành cảm ơn PGS.TS Đoàn Văn Ban, người đãtrực tiếp giảng dạy tôi trong thời gian học tập và cũng là người đã trực tiếp hướngdẫn, giúp đỡ và tạo mọi điều kiện thuận lợi cho tôi từ lúc nhận đề tài đến khi hoànthành luận văn. Tôi xin gửi lời cảm ơn sâu sắc đến tất cả các Thầy cô đã tham gia giảng dạyvà truyền đạt kiến thức, kinh nghiệm quý báu cho chúng tôi trong hai năm học caohọc tại trường Đại học Công Nghệ Thông Tin và Truyền Thông – Đại học TháiNguyên. Những kiến thức này đã giúp tôi rất nhiều trong quá trình làm luận văncủa mình. Cuối cùng, tôi xin cảm ơn tất cả người thân, bạn bè và đồng nghiệp đã khíchlệ, động viên, đóng góp ý kiến và giúp đỡ tôi hoàn thành luận văn này. Thái Nguyên, ngày…..tháng….năm 2019 Lương Kim Cương i DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮTSTT Ký hiệu Diễn giải 1 CSDL Cơ sở dữ liệu 2 CPU Bộ xử lý trung tâm 3 I/O Cổng vào/ ra 4 DP Quy hoạch động 5 ACO Tối ưu đàn kiến ii DANH MỤC CÁC HÌNH VẼHình 1.1: Kiến trúc tham chiếu của cơ sở dữ liệu phân tán [3] ................................ 9Hình 1.2: Cây phân tách của quan hệ ...................................................................... 13Hình 2.1: Giải pháp A ............................................................................................. 18Hình 2.2: Giải pháp B ............................................................................................. 18Hình 2.3: Sơ đồ quy trình xử lý truy vấn [4]........................................................... 21Hình 2.4: Đồ thị truy vấn và Đồ thị nối .................................................................. 25Hình 2.5: Đồ thị truy vấn và Đồ thị nối với câu truy vấn sai ngữ nghĩa................. 25Hình 2.6: Cây đại số quan hệ .................................................................................. 28Hình 2.7: Cây đại số quan hệ sau khi tái cấu trúc .................................................. 30Hình 2.8: Câu truy vấn gốc ..................................................................................... 32Hình 2.9: Câu truy vấn đã rút gọn .......................................................................... 32Hình 2.10: Rút gọn phân mảnh ngang .................................................................... 33Hình 2.11: Rút gọn phân mảnh dọc ....................................................................... 35Hình 2.12: Rút gọn cho phân mảnh ngang dẫn xuất .............................................. 36Hình 2.13: Rút gọn phân mảnh hỗn hợp ................................................................. 37Hình 2.14: Bộ tối ưu truy vấn ................................................................................. 38Hình 2.15: Các cây nối ............................................................................................ 39Hình 2.16: Hình dáng của một số cây nối ............................................................... 40Hình 2.17: Đồ thị minh họa tổng chi phí và thời gian trả lời ......................... 42Hình 2.18: Đồ thị nối của truy vấn q1 ..................................................................... 58Hình 2.19: Các thứ tự kết nối .................................................................................. 59Hình 2.20: Quá trình quyết định đường đi của đàn kiến .......... ...