Đặt vấn đề Trong thời đại của nền kinh tế tri thức mà chúng ta đang sống, mọi hoạt động muốn đạt hiệu quả cao thì nhất thiết phải có đƣợc thông tin, tri thức cần thiết một cách nhanh chóng và chính xác. Thông tin có thể có đƣợc ở mọi nơi, và CSDL là một trong những nguồn cung cấp thông tin. Vấn đề đặt ra là khối lƣợng thông tin lƣu trữ lớn song đòi hỏi việc xử lý thông tin phải nhanh chóng và hiệu quả. Để lấy đƣợc thông tin cần thiết ta cần thực hiện hàng loạt các thao tác trên CSDL thông qua các câu truy vấn.
Từ câu truy vấn ban đầu có thể thực hiện theo các phƣơng pháp khác nhau để có kết quả song cần phải hạ thấp chi phí thực hiện truy vấn gọi là tối ƣu hoá truy vấn. Tuy nhiên để có đƣợc phƣơng án tối ƣu nhất thì có thể chi phí cho quá trình tối ƣu lại rất cao. Xuất phát từ những đặc điểm chung và tính thời sự nêu trên, tôi đã chọn đề tài nghiên cứu về tối ƣu hoá truy vấn và đi sâu vào tìm hiểu về phƣơng pháp tối ƣu truy vấn bằng Heuristic mong đƣợc đóng góp một phần nhỏ bé trong việc nghiên cứu về các phƣơng pháp tối ƣu hoá truy vấn dữ liệu để khai thác thông tin một cách có hiệu quả và nhanh chóng, trợ giúp cho những ngƣời sử dụng dữ liệu thực hiện tốt công việc của mình. Mục tiêu của luận văn Mục tiêu của đề tài là nghiên cứu các phƣơng pháp tối ƣu hoá truy vấn, đặc biệt tập trung nghiên cứu phƣơng pháp tối ƣu hoá bằng Heuristic.
Luận văn bao gồm các vấn đề chính sau đây: - Nghiên cứu về cơ sở dữ liệu quan hệ và cơ sở dữ liệu phân tán. - Tìm hiểu bài toán tối ƣu hoá truy vấn. - Tìm hiểu một số phƣơng pháp tối ƣu hoá trong môi trƣờng tập trung và phân tán. - Nghiên cứu phƣơng pháp tối ƣu hoá truy vấn bằng Heuristic 3.
Bố cục của luận văn 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Luận văn gồm 4 chƣơng: Chƣơng 1: Tổng quan về cơ sở dữ liệu quan hệ và cơ sở dữ liệu phân tán. Chƣơng 2: Bài toán tối ƣu hoá truy vấn. Chƣơng 3: Một số phƣơng pháp tối ƣu hoá truy vấn trong môi trƣờng tập trung và phân tán Chƣơng4: Phƣơng pháp tối ƣu hoá truy vấn bằng Heuristic, ví dụ minh hoạ. 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chƣơng 1.
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU 1.1 CƠ SỞ DỮ LIỆU QUAN HỆ 1.1 Khái niệm Đƣợc phát triển từ những năm 60, cho đến nay các hệ cơ sở dữ liệu (CSDL) đƣợc tập trung nghiên cứu và phát triển ứng dụng rất mạnh. Khái niệm CSDL cũng đã đƣợc định nghĩa dƣới nhiều góc độ khác nhau, ta có thể hiểu CSDL theo khái niệm là một tập hợp dữ liệu của một tổ chức, xí nghiệp,… đƣợc lƣu trữ trong máy tính, đƣợc nhiều ngƣời sử dụng và cách tổ chức của nó đƣợc chi phối bằng một mô hình dữ liệu[5]. Một ngân hàng dữ liệu thƣờng là tập hợp các thông tin lƣu trữ trong máy tính có liên quan đến một lĩnh vực khoa học, kinh tế hoặc văn hoá, thể thao theo một cách đầy đủ nhất có thể có. Dữ liệu trong ngân hàng thực chất chỉ là một kho dữ liệu trong khi đó một CSDL của một tổ chức hàm chứa cả các thông tin liên quan đến việc bảo mật, cấu trúc lƣu trữ thông tin và sự chia sẻ tài nguyên.2 Tiêu chuẩn của một cơ sở dữ liệu.
Một CSDL cần thoả mãn các tiêu chuẩn sau[1, 4, 6]: 1. Biểu diễn tốt thế giới thực: cung cấp một hình ảnh trung thực của thực tại. Một CSDL trung thực cho phép ngƣời dùng có các thông tin thoả mãn việc sử dụng và cập nhật. Không dư thừa thông tin: mỗi thông tin đảm bảo không bị trùng lặp, chỉ có mặt một lần trong CSDL do đó sự lựa chọn dữ liệu là duy nhất.
Tính độc lập của các chương trình đối với dữ liệu: tƣơng ứng với sự cần thiết làm giảm giá thành bảo trì các chƣơng trình. Những thay đổi về cấu trúc của hệ CSDL là do sự thay đổi của thế giới thực chứ không phải do một ứng dụng cụ thể và nó cho phép nhiều ứng dụng cùng chia sẻ một bộ dữ liệu. Tính an toàn và bí mật của dữ liệu: CSDL đƣợc đảm bảo chỉ những ngƣời có trách nhiệm mới có thể truy cập đến các thông tin và sử dụng chúng. Ngoài ra cũng cần có sự đảm bảo an toàn cho các vật mang thông tin chống lại mọi sự huỷ hoại.
7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Hiệu suất ứng dụng: Mặc dù chia sẻ cùng một nguồn chung, các ứng dụng phải có hiệu suất trong CSDL giống nhau nhƣ trong sử dụng thông tin truyền thông. Các tiêu chuẩn trên là thiết yếu nhất cho một CSDL hoàn thiện và tối ƣu, tuy nhiên các tiêu chuẩn khác nhau sẽ đƣợc ƣu tiên ít nhiều khác nhau tuỳ theo từng mục đích và ứng dụng cụ thể.2 HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 1.1 Hệ quản trị cơ sở dữ liệu Hệ quản trị cơ sở dữ liệu (QTCSDL) là hệ thống phần mềm đặc biệt cho phép khai thác một cách hợp lý các CSDL. Một hệ QTCSDL bao gồm các phần mềm cho phép mô tả, lƣu trữ, thao tác, xử lý các tập hợp dữ liệu.
Đồng thời, hệ QTCSDL đảm bảo sự an toàn và bí mật của các dữ liệu trong một môi trƣờng có nhiều ngƣời sử dụng với những yêu cầu khác nhau có thể có những tác động truy nhập đồng thời lên dữ liệu.2 Các chức năng của hệ quản trị cơ sở dữ liệu Một hệ QTCSDL phải đảm bảo đƣợc các chức năng tối thiểu sau: - Mô tả dữ liệu. - Tìm kiếm dữ liệu đã đƣợc lƣu trữ. - Cập nhật dữ liệu (thêm, bớt, sửa đổi,…). - Chuyển hoá dữ liệu giữa các mức độ lƣợc đồ.
- Điều khiển tính an toàn và toàn vẹn dữ liệu. - Quản lý dữ liệu ở mức thấp (mức các giao tác xử lý dữ liệu).3 Cách thức truy nhập CSDL Truy nhập CSDL là phƣơng pháp khai thác tệp do chƣơng trình ứng dụng sử dụng để chọn những bản ghi. Trong hệ CSDL có các loại truy nhập sau: 1. Tổ chức truy nhập tuần tự: là phƣơng pháp đọc tuần tự các bản ghi của tệp, từ đầu tệp cho đến bản ghi cần tìm.Trong kiểu tổ chức này các bản ghi đƣợc lƣu trữ lần lƣợt, muốn đọc bản ghi thứ n, ta phải lần lƣợt đi qua (n-1) bản ghi trƣớc đó.
Tuy nhiên ta không cần đọc toàn bộ nội dung các 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com bản ghi mà chỉ cần đọc một phần thông tin tối thiểu đủ để xác định xem đó có phải là bản ghi cần hay không. Tổ chức truy nhập trực tiếp: Cho phép truy nhập trực tiếp đến các đơn vị thông tin cần tìm mà không cần đọc lần lƣợt từ đầu. Để truy nhập phải tuân theo phƣơng pháp đã xác định khi tổ chức lƣu trữ. Có hai loại tổ chức truy nhập là tệp trực tiếp và tệp có chỉ số.
Ta phải sử dụng một phần thông tin của bản ghi làm khoá của bản ghi đó. Qua đặc trƣng của khoá cho phép xác định chính xác bản ghi cần tìm. Truy nhập ngẫu nhiên: Kiểu tổ chức này lƣu trữ các bản ghi tại địa chỉ theo một khoá nào đó. Ta thƣờng dùng một thuật toán, một hàm ngẫu nhiên để tính toán ra địa chỉ của bản ghi.
Hàm địa chỉ đƣợc xây dựng theo nhiều phƣơng pháp khác nhau nhƣ phƣơng pháp tính địa chỉ tuyến tính, phƣơng pháp dùng hàm mã cắt v.3 MÔ HÌNH DỮ LIỆU QUAN HỆ Mô hình dữ liệu là tập hợp các khái niệm dùng để biểu diễn các cấu trúc của CSDL. Cấu trúc của một CSDL bao gồm các kiểu dữ liệu, các mối liên kết và các ràng buộc phải tuân theo trên các dữ liệu. Nhiều mô hình còn có thêm tập hợp các phép toán cơ bản để đặc tả các thao tác trên CSDL. Mô hình quan hệ đƣợc Ted Codd đƣa ra vào những năm 1970 và đƣợc sử dụng rất rộng rãi bởi tính đơn giản và cơ sở toán học của nó.1 Khái niệm về quan hệ Một lƣợc đồ quan hệ R, kí hiệu là R(A1, A2,…,An) đƣợc tạo nên từ một tên quan hệ R, một danh sách các thuộc tính A1, A2,…,An.
Số thuộc tính của quan hệ gọi là bậc của quan hệ. Một quan hệ r tƣơng ứng với lƣợc đồ R là : r(R ) D1 x D2 x…x Dn trong đó Di với (1 i n) là miền giá trị của thuộc tính Ai. Một quan hệ đƣợc biểu diễn nhƣ một bảng, trong đó các giá trị của một thuộc tính đƣợc ghi trong một cột và một bộ giá trị của quan hệ đƣợc ghi trên một dòng. 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.2 Các phép toán trên quan hệ Có năm phép toán cơ bản và năm phép toán khác có thể đƣợc định nghĩa theo năm phép toán cơ bản này.
Đó là phép chọn, phép chiếu, phép hợp, phép trừ và phép tích Descartes. Các phép toán bổ sung có thể là: giao, nối, nối tự nhiên, nối nửa và phép chia. Phép chọn trên quan hệ R với vị từ p là tập tất cả các bộ t của R thoả p: p ( R) {t R / p(t )} Phép chiếu của quan hệ R trên tập các thuộc tính X của quan hệ R, là một quan hệ trên tập thuộc tính X, đƣợc xây dựng bằng cách loại bỏ trong quan hệ R những thuộc tính không nằm trong X. Hợp của hai quan hệ R và S, là tập tất cả các bộ thuộc R hoặc thuộc S hoặc thuộc cả hai.
Các bộ trùng lặp bị loại bỏ. R S= {t| tR hoặc t S } Phép trừ: Hiệu của hai quan hệ R và S là tập tất cả các bộ của R không thuộc S R-S = {t| tR và t S } Tích Descartes. Tích Descartes của hai quan hệ R bậc n và S bậc m có kết quả là tập các (n+m) bộ sao cho mỗi bộ này có n thành phần đầu thuộc R và m thành phần sau thuộc S. R x S = {t | t có dạng (a1, a2,…,an, b1, b2,…, bm ) trong đó (a1, a2,…,an) R và (b1,b2,…,bm)S} Phép giao: Giao của 2 quan hệ R và S, là tập tất cả các bộ t thuộc cả hai quan hệ R và S.
Phép nối là một dẫn xuất của tích Descartes. Có nhiều kiểu nối, và kiểu nối tổng quát là nối hay đơn giản là nối.