Tài liệu Tối ưu truy vấn cơ sở dữ liệu quan hệ và cơ sở dữ liệu phân tán bằng phương pháp Heuristic

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƢỜNG ĐẠI HỌC CÔNG NGHỆ =====o0o===== Đinh Thị Lan Phƣơng TỐI ƢU TRUY VẤN CƠ SỞ DỮ LIỆU QUAN HỆ VÀ CƠ SỞ DỮ LIỆU PHÂN TÁN BẰNG PHƢƠNG PHÁP HEURISTIC LUẬN VĂN THẠC SĨ Hà Nội - 2007 MỤC LỤC LỜI CẢM ƠN ............................................................................................................. 1 MỤC LỤC ................................................................................................................... 2 CÁC THUẬT NGỮ VIẾT TẮT .................................................................................. 4 MỞ ĐẦU ..................................................................................................................... 5 Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU ......................................................... 7 1.1 CƠ SỞ DỮ LIỆU QUAN HỆ............................................................................. 7 1.1.1 Khái niệm.................................................................................................... 7 1.1.2 Tiêu chuẩn của một cơ sở dữ liệu. ............................................................... 7 1.2 HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ..................................................................... 8 1.2.1 Hệ quản trị cơ sở dữ liệu ............................................................................. 8 1.2.2 Các chức năng của hệ quản trị cơ sở dữ liệu ................................................ 8 1.2.3 Cách thức truy nhập CSDL......................................................................... 8 1.3 MÔ HÌNH DỮ LIỆU QUAN HỆ ....................................................................... 9 1.3.2 Các phép toán trên quan hệ........................................................................ 10 1.3.3 Các dạng chuẩn của mô hình quan hệ ........................................................ 11 1.4 HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN ................................................................. 13 1.4.1 Các khái niệm về cơ sở dữ liệu phân tán.................................................... 13 1.4.2 Các mục tiêu của hệ quản trị cơ sở dữ liệu phân tán. ................................. 15 1.4.3 Kiến trúc hệ quản trị cơ sở dữ liệu phân tán............................................... 16 1.4.4 Phân đoạn, nhân bản và cấp phát dữ liệu ................................................... 19 1.5 KẾT LUẬN CHƢƠNG 1 ................................................................................ 21 Chƣơng 2. TỔNG QUAN VỀ TỐI ƢU HOÁ TRUY VẤN........................................ 22 2.1 BÀI TOÁN TỐI ƢU HÓA TRUY VẤN .......................................................... 22 2.2 BỘ TỐI ƢU TRUY VẤN ............................................................................... 23 2.2.1. Không gian tìm kiếm ................................................................................ 24 2.2.2 Chiến lƣợc tìm kiếm .................................................................................. 26 2.2.3 Mô hình chi phí ......................................................................................... 27 2.3 KẾT LUẬN CHƢƠNG 2 ................................................................................. 31 Chƣơng 3. MỘT SỐ PHƢƠNG PHÁP TỐI ƢU TRUY VẤN ................................... 32 3.1 MỘT SỐ PHƢƠNG PHÁP TỐI ƢU HOÁ TRUY VẤN TRONG MÔI TRƢỜNG TẬP TRUNG........................................................................................ 32 3.1.1 Thuật toán INGRES .................................................................................. 32 3.1.2 Thuật toán System R ................................................................................. 36 3.2 MỘT SỐ PHƢƠNG PHÁP TỐI ƢU HOÁ TRUY VẤN TRONG MÔI TRƢỜNG PHÂN TÁN .......................................................................................... 41 3.2.1 Thuật toán INGRES phân tán ................................................................... 41 2 3.2.2 Thuật toán System R* .............................................................................. 45 3.2.3 Thuật toán SDD-1 ..................................................................................... 50 3.3 KẾT LUẬN CHƢƠNG 3 ................................................................................. 59 Chƣơng 4. TỐI ƢU TRUY VẤN BẰNG PHƢƠNG PHÁP HEURISTIC.................. 60 4.1 CÁC CHIẾN LƢỢC TỐI ƢU TỔNG QUÁT .................................................. 60 4.2 CÁC PHÉP BIẾN ĐỔI ĐẠI SỐ QUAN HỆ ................................................... 61 4.2.1 Biểu thức quan hệ...................................................................................... 61 4.2.2 Biến đổi tƣơng đƣơng của đại số quan hệ .................................................. 62 4.3 THUẬT TOÁN HEURISTIC ........................................................................... 64 4.4 VÍ DỤ TỐI ƢU HOÁ CÂU HỎI THEO HEURISTIC ..................................... 65 4.5 KẾT LUẬN CHƢƠNG 4 ................................................................................. 77 KẾT LUẬN ............................................................................................................... 79 TÀI LIỆU THAM KHẢO.......................................................................................... 81 3 CÁC THUẬT NGỮ VIẾT TẮT Tên viết tắt Tên khoa học Giải nghĩa CSDL DataBase Cơ sở dữ liệu ES External Schema Lƣợc đồ ngoài MRQ Multi Relation Query Truy vấn đa quan hệ ORQ One Relation Query Truy vấn đơn quan hệ OVQP One Variable Query Processor Bộ xử lý truy vấn một biến QEP Query Excution Plan Hoạch định thực thi truy vấn QTCSDL DataBase System Quản trị cơ sở dữ liệu 4 MỞ ĐẦU 1. Đặ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. 2. 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 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 Chƣơng 1. TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU 1.1 CƠ SỞ DỮ LIỆU QUAN HỆ 1.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. 1.1.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. 2. 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. 3. 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. 4. 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 5. 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ể. 1.2 HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 1.2.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. 1.2.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). 1.2.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 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. 2. 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. 3. 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.v… 1.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.3.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 1.3.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.  X ( R)  {t[ X ] | t  R} Phép hợp. 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| tR 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| tR 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. R S = {t | t R, t S } = R - (R-S) Nối - . 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. Với F là vị từ nối: R  F S = F (R x S) 10 Nối tự nhiên. Giả sử hai quan hệ R và S có tập thuộc tính chung là X. Phép nối tự nhiên của hai quan hệ R và S là quan hệ trên tập thuộc tính của R và tập Y các thuộc tính của S không nằm trong X R  S = {(u,v)|uR  v = s[Y] sS s[X] = u[X]} Nối nửa của hai quan hệ R và S theo vị từ p cho kết quả là: R < p S =X (R  P S ) với X là tập các thuộc tính của R Phép chia. Chia quan hệ R bậc n cho quan hệ S bậc m (trong đó n>m và m  0) là tập các bộ t trên bộ n-m thuộc tính sao cho với mọi bộ uS thì (t,u) R RS = A‟(R)-A‟((A‟(R)xS)-R), với A‟ là tập thuộc tính của R không thuộc S. 1.3.3 Các dạng chuẩn của mô hình quan hệ Các quan hệ dùng trên mỗi hệ QTCSDL phải thoả mãn điều kiện[4]: - Hạn chế tối thiểu sự dƣ thừa thông tin. - Cho phép các cập nhật nhanh nhất. - Tránh những sự rời rạc liên quan đến quá trình cập nhật. Chuẩn hoá - là một quá trình từng bƣớc thay thế một tập quan hệ đã cho bằng tập các quan hệ có cấu trúc ngày càng đơn giản và chuẩn tắc hơn. Mục đích của chuẩn hoá là loại bỏ những bất thƣờng của một quan hệ. Quan hệ đƣợc chuẩn hoá là quan hệ trong đó mỗi miền giá trị của một thuộc tính chỉ chứa những giá trị nguyên tố tức là không phân nhỏ ra đƣợc nữa và do đó mỗi giá trị trong quan hệ cũng là nguyên tố. Theo lý thuyết ban đầu Codd đƣa ra có 3 dạng chuẩn của quan hệ. Về sau Boyce và Codd đã định nghĩa một phiên bản sửa đổi của dạng chuẩn ba, thƣờng gọi là dạng chuẩn Boyce-Codd (BCNF). Tiếp sau đó là các dạng chuẩn bốn (4NF) và chuẩn năm (5 NF) đƣợc đề nghị dựa trên các phụ thuộc hàm đa trị và các phụ thuộc hàm nối. 11 Dạng không chuẩn hóa Dạng chuẩn thứ nhất (1NF) Dạng chuẩn thứ hai (2NF) Dạng chuẩn thứ ba (3NF) Chuẩn hoá dữ liệu có thể đƣợc xem nhƣ là một quá trình phân tích các lƣợc đồ quan hệ cho trƣớc dựa trên các phụ thuộc hàm và các khoá chính của chúng để đạt đến các tiêu chuẩn mong muốn là cực tiểu sự dƣ thừa và cực tiểu các phép cập nhật bất thƣờng. Yêu cầu của chuẩn hoá là không làm mất mát thông tin khi thay một quan hệ này bằng các quan hệ khác. Nếu chúng ta có thể nối các quan hệ kết quả để tạo thành quan hệ ban đầu, thì quá trình phân rã đó gọi là phân rã không mất thông tin. Một yêu cầu khác đối với quá trình chuẩn hoá là bảo toàn phụ thuộc. Phân rã đƣợc gọi là bảo toàn phụ thuộc nếu đảm bảo rằng từng phụ thuộc hàm sẽ đƣợc biểu hiện trong các quan hệ riêng rẽ sau khi tách. Định nghĩa dạng chuẩn 1 (1 NF): Một lƣợc đồ quan hệ R đƣợc gọi là ở dạng chuẩn 1 nếu và chỉ nếu toàn bộ các miền thuộc tính có mặt trong R đều chỉ chứa các giá trị nguyên tố [1]. Nhƣ vậy 1NF không cho phép quan hệ có các thuộc tính đa trị hoặc có các nhóm thuộc tính đa trị. Định nghĩa dạng chuẩn 2 (2 NF): Một lƣợc đồ quan hệ ở dạng chuẩn 2NF nếu nó đã ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khoá của R phụ thuộc hàm đầy đủ vào mỗi một khoá [1]. 12 Định nghĩa dạng chuẩn 3 (3 NF): Một lƣợc đồ quan hệ R ở dạng chuẩn 3NF nếu nó đã ở dạng chuẩn 2NF và nếu mỗi thuộc tính không khoá của R là không phụ thuộc hàm bắc cầu vào mỗi một khoá [1]. Định nghĩa dạng chuẩn BCNF: Một lƣợc đồ quan hệ R với tập các phụ thuộc hàm đƣợc gọi là ở dạng chuẩn BCNF nếu X A thoả mãn trên R, A X thì X là một siêu khoá của R [1]. 1.4 HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN Ta có thể định nghĩa, CSDL phân tán là một tập hợp các dữ liệu thuộc về một hệ thống có liên quan với nhau một cách logic và đƣợc phân bố trên một mạng máy tính. Hệ quản trị CSDL phân tán đƣợc định nghĩa là một hệ thống phần mềm cho phép quản lý các CSDL phân tán và làm cho việc phân tán trở nên trong suốt với ngƣời sử dụng. Với các CSDL phân tán chúng ta dễ dàng nhận thấy những ƣu điểm tiềm năng nhƣ:  Quản trị dữ liệu phân tán với nhiều mức trong suốt khác nhau. 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 là che dấu đặc tính phân tán đối với ngƣời sử dụng. Hệ quản trị CSDL phân tán có thể cung cấp các khả năng trong suốt sau: - Trong suốt phân tán. - Trong suốt phân đoạn. - Trong suốt nhân bản.  Tăng tính tin cậy và tính sẵn sàng.  Cho phép dùng chung dữ liệu vẫn duy trì đƣợc biện pháp điều khiển cục bộ.  Cải tiến hiệu năng.  Tính dễ mở rộng. 1.4.1 Các khái niệm về cơ sở dữ liệu phân tán Ở mức phần cứng vật lý, những nhân tố chính phân biệt một hệ CSDL phân tán với một hệ CSDL tập trung là: Có nhiều máy tính gọi là trạm hay nút (node). 13 Các trạm phải đƣợc kết nối bởi một kiểu mạng truyền thông nào đó để truyền dữ liệu. Một hệ quản trị CSDL phân tán là một tập các phần mềm hệ thống bao gồm các phần mềm quản trị các dữ liệu phân tán, các phần mềm quản trị truyền thông và các hệ quản trị CSDL địa phƣơng/cục bộ lƣu trú trên mỗi trạm của hệ CSDL phân tán. Ngoài các chức năng của các hệ quản trị CSDL tập trung và của phần mềm Trạm 1 Trạm 2 Trạm 3 Trạm 5 Trạm 4 Hình 1- Cơ sở dữ liệu trung tâm trên một mạng Trạm 1 Trạm 2 Trạm 3 Trạm 5 Trạm 4 Hình 2- Môi trường của hệ Cơ sở dữ liệu phân tán 14 quản trị truyền thông, hệ quản trị CSDL phân tán còn có các chức năng đặc biệt sau :  Quản lý một từ điển dữ liệu tổng thể lƣu trữ thông tin liên quan đến các dữ liệu phân tán.  Định nghĩa các dữ liệu phân tán.  Kiểm tra ngữ nghĩa các dữ liệu phân tán.  Định giá các câu truy vấn phân tán do ngƣời dùng đƣa ra.  Quản lý các giao tác và dữ liệu.  Bảo mật giao tác và dữ liệu.  Phục hồi CSDL phân tán, cung cấp khả năng phục hồi dữ liệu từ những trạm bị lỗi (sập).  Quản trị nhân bản dữ liệu. Một tính chất quan trọng của các CSDL phân tán là tính thuần nhất hay không thuần nhất. Một CSDL phân tán thuần nhất có đƣợc bằng cách chia một CSDL thành một tập các CSDL cục bộ, mỗi CSDL cục bộ này đƣợc quản trị bởi cùng một hệ quản trị CSDL. Một CSDL phân tán thuần nhất thƣờng là kết quả của cách tiếp cận thiết kế từ trên xuống, trong đó thiết kế một CSDL phân tán từ một CSDL tập trung. Một CSDL phân tán không thuần nhất là một CSDL phân tán có đƣợc bằng cách tích hợp một tập CSDL cục bộ (có thể đƣợc xây dựng từ các mô hình dữ liệu khác nhau) đƣợc quản trị bởi các hệ quản trị CSDL khác nhau, thành một CSDL duy nhất. 1.4.2 Các mục tiêu của hệ quản trị cơ sở dữ liệu phân tán. Sự độc lập dữ liệu và trong suốt phân tán. Ngƣời dùng có thể không quan tâm đến sự phân tán dữ liệu. Các thông tin này đƣợc lƣu trữ trong từ điển dữ liệu, và đƣợc hệ quản trị CSDL phân tán sử dụng để định vị dữ liệu. Đây là một dạng trong suốt cơ bản cần có trong CSDL phân tán, nó liên quan đến tính độc lập dữ liệu và làm tăng khả năng thích ứng của các ứng dụng đối với những thay đổi trong định nghĩa và tổ chức của dữ liệu và ngƣợc lại. Khi đó không có sự 15 khác biệt nào giữa các ứng dụng chạy trên CSDL tập trung với ứng dụng chạy trên CSDL phân tán. Trong suốt phân đoạn. Việc truy cập tới dữ liệu đƣợc xác định trên các quan hệ con (thu đƣợc từ việc chia nhỏ quan hệ gốc) đƣợc gọi là các đoạn (fragment). Việc phân đoạn làm tăng hiệu năng, tính sẵn sàng, độ tin cậy của CSDL phân tán. Trong suốt phân đoạn che dấu sự phân đoạn đối với ngƣời dùng. Trong suốt nhân bản. Một giải pháp cho sự tin cậy dữ liệu là việc tạo ra dƣ thừa dữ liệu dƣới một hình thức nào đó. Mỗi đoạn dữ liệu đƣợc sao lƣu thành hai hay nhiều bản, mỗi bản đƣợc lƣu trên một trạm khác nhau, đƣợc gọi là sự nhân bản. Nó giúp hệ CSDL phân tán nâng cao hiệu năng, độ tin cậy và tính sẵn sàng. Tuy nhiên việc nhân bản sẽ gây khó khăn cho việc cập nhật CSDL, và việc duy trì và quản lý các bản sao là phức tạp và tốn kém. Việc trong suốt nhân bản là việc che dấu khiến ngƣời dùng chỉ nhìn thấy các quan hệ không có nhân bản. Tính trong suốt đối với hệ quản trị CSDL phân tán cho phép che dấu đối với ngƣời dùng việc các hệ quản trị CSDL cục bộ có thể khác nhau. Tính tự trị của các trạm. Đây là mục tiêu cho phép mỗi trạm điều khiển và thao tác dữ liệu địa phƣơng của nó độc lập với các trạm khác. Do đó việc quản trị của CSDL phân tán có thể hoàn toàn không tập trung. Tính mở rộng. Là khả năng mở rộng bằng việc đƣa thêm các trạm mới vào mạng với ảnh hƣởng tối thiểu lên các CSDL cục bộ và các chƣơng trình ứng dụng hiện có. 1.4.3 Kiến trúc hệ quản trị cơ sở dữ liệu phân tán. Có nhiều kiểu kiến trúc CSDL nhƣ, các hệ CSDL client/sever, các phức hệ CSDL, hay các CSDL trong môi trƣờng phân tán đầy đủ (không có sự phân biệt nào giữa client và sever) hay còn gọi là các hệ phân tán ngang hàng. Các hệ phân tán ngang hàng. Tổ chức vật lý trên mỗi máy có thể rất khác nhau, do đó ta cần phải có một định nghĩa tổ chức dữ liệu vật lý cho mỗi trạm, gọi là lƣợc đồ trong cục bộ (Local Internal Schema - LIS). Hình ảnh toàn thể của CSDL đƣợc mô tả bởi lƣợc đồ khái niệm toàn cục (Global Conceptual Schema GCS), nó mô tả cấu trúc logic của dữ liệu ở mọi vị trí. 16 Để xử lý việc phân đoạn và nhân bản, sử dụng lƣợc đồ khái niệm cục bộ (Local Conceptual Schema - LCS), mô tả tổ chức logic của dữ liệu tại mỗi trạm. Do đó trong kiến trúc này lƣợc đồ khái niệm toàn cục là hợp của các lƣợc đồ khái niệm cục bộ. Các ứng dụng truy xuất dữ liệu thông qua lƣợc đồ ngoài (ES), đƣợc định nghĩa là một tầng nằm trên lƣợc đồ khái niệm toàn cục. Các khái niệm trên đƣợc mô tả trong hình 3. ES1 ES2 ESn GCS LCS1 LCS2 LCSn LIS1 LIS2 LISn ES-lƣợc đồ ngoài (External Schema) LCS-lƣợc đồ khái niệm cục bộ (Local GCS-lƣợc đồ khái niệm toàn cục (Global Conceptual Conceptual Schema) LIS-lƣợc đồ trong cục bộ (Local Internal Schema) Schema) Hình 3- Kiến trúc tham chiếu Cơ sở dữ liệu phân tán Các thành phần cụ thể của một hệ CSDL phân tán Thành phần đầu tiên bao gồm: Bộ giao tiếp người dùng (user interface handler): diễn dịch các lệnh của ngƣời sử dụng và đinh dạng dữ liệu để chuyển cho ngƣời dùng các kết quả. Bộ kiểm soát dữ liệu ngữ nghĩa (sematic data controller): sử dụng các ràng buộc toàn vẹn (integrity constraints) và thông tin cấp phép, quyền hạn (authorization), đƣợc định nghĩa nhƣ thành phần của lƣợc đồ khái niệm toàn cục để kiểm tra, xác định xem các câu truy vấn có xử lý đƣợc hay không. Bộ tối ưu truy vấn toàn cục (global query optimizer): xác định một chiến lƣợc hoạt động để giảm chi phí, và phiên dịch các câu truy vấn toàn cục thành 17 câu truy vấn cục bộ thông qua việc sử dụng các lƣợc đồ toàn cục, khái niệm cục bộ và thƣ mục toàn cục, ngoài ra còn chịu trách nhiệm tạo ra một chiến lƣợc thực thi tốt cho các phép nối phân tán. Bộ theo dõi hoạt động toàn cục (global execution monitor) có trách nhiệm điều phối việc thực hiện phân tán các yêu cầu ngƣời dùng và cũng đƣợc gọi là bộ quản lý giao dịch phân tán (distributed transaction manager). Thành phần thứ hai gồm: Bộ tối ưu truy vấn cục bộ (local query processor) chịu trách nhiệm chọn ra một đƣờng truy xuất thích hợp nhất để truy xuất các dữ liệu. Bộ khôi phục cục bộ (local recovery manager) đảm bảo cho các CSDL cục bộ duy trì đƣợc tính nhất quán khi có sự cố xảy ra. Ngƣời sử dụng Yêu cầu ngƣời dùng Bộ tiếp nhận ngƣời dùng (user processor) trả lời của hệ thống Lƣợc đồ ngoài Bộ giao tiếp ngƣời dùng Bộ kiểm soát dữ liệu ngữ nghĩa Lƣợc đồ khái niệm toàn cục Bộ tối ƣu truy vấn toàn cục Thƣ mục/Từ điển toàn cục Bộ theo dõi hoạt động toàn cục Bộ xử lý dữ liệu (data processor) Lƣợc đồ khái niệm cục bộ Bộ tối ƣu hoá truy vấn cục bộ Bộ khôi phục cục bộ Nhật ký hệ thống Lƣợc đồ trong cục bộ Bộ hỗ trợ thực thi Hình 4- Các thành phần của một hệ quản trị CSDL phân tán 18 Bộ hỗ trợ thực thi (runtime support processor): truy xuất CSDL tuỳ vào các lệnh trong lịch do bộ tối ƣu truy vấn sinh ra. Nó là giao diện với bộ điều hành, chứa bộ quản lý vùng đệm và việc quản lý truy xuất dữ liệu. Một điểm lƣu ý là hai thành phần này chỉ là phân chia về mặt tổ chức chứ không bắt buộc phải cài đặt trên các trạm khác nhau. Tuy nhiên cũng có những gợi ý tách biệt những trạm chỉ thực hiện truy vấn ra khỏi những hệ thống có đầy đủ chức năng, và khi đó các trạm này chỉ cần có bộ xử lý tiếp nhận ngƣời dùng. 1.4.4 Phân đoạn, nhân bản và cấp phát dữ liệu 1.4.4.1 Phân đoạn Sự phân đoạn dữ liệu nhằm chia một quan hệ tổng thể thành các đơn vị logic (các đoạn/mảnh), có thể đƣợc sắp đặt tối ƣu trong CSDL phân tán. Các đoạn đƣợc xử lý nhƣ một đơn vị, qua đó cho phép thực hiện nhiều giao dịch đồng thời. Ngoài ra việc phân đoạn các quan hệ còn cho phép thực hiện song song câu truy vấn bằng cách phân chia câu truy vấn thành một tập các câu truy vấn con tƣơng ứng với các đoạn. Do vậy việc phân đoạn sẽ làm tăng mức độ hoạt động đồng thời và nhƣ thế làm tăng lƣu lƣợng hoạt động của hệ thống. Tuy nhiên việc phân đoạn cũng có những hạn chế. Nhƣ việc những ứng dụng có các khung nhìn đƣợc định nghĩa trên nhiều đoạn sẽ bị giảm hiệu suất hoạt động (ví dụ việc truy xuất dữ liệu từ nhiều đoạn rồi nối hoặc hợp chúng lại với chi phí cao), tránh đƣợc điều này là một kỹ thuật cơ bản của kỹ thuật phân đoạn. Còn vấn đề nữa liên quan đến việc kiểm soát dữ liệu ngữ nghĩa, đặc biệt là những vấn đề kiểm tra tính toàn vẹn. Do kết quả của việc phân đoạn, các thuộc tính tham gia vào một phụ thuộc có thể bị phân rã vào các đoạn khác nhau và đƣợc cấp phát cho những trạm khác nhau, do đó việc kiểm tra các phụ thuộc cũng phải thực hiện truy tìm dữ liệu trên nhiều trạm khác nhau. Việc phân đoạn của một quan hệ phải đƣợc xác định bởi ngƣời quản trị CSDL, và phải tuân thủ ba quy tắc: không mất mát thông tin, khôi phục lại đƣợc và không trùng lặp (chỉ áp dụng cho phân đoạn ngang). 19 Các kiểu phân đoạn: Phân đoạn dọc Phân đoạn ngang Phân đoạn hỗn hợp Hình 5 - Các kiểu phân đoạn Phân đoạn ngang: Phân đoạn ngang là sự phân chia một quan hệ thành các tập các bộ con, mỗi tập con đƣợc xác định bởi phép chọn áp dụng cho quan hệ (phân đoạn ngang nguyên thuỷ): Ri = Fi (R), 1 i  z trong đó Fi là vị từ chọn trên quan hệ R Hay đƣợc xác định bởi phép nối nửa của một quan hệ với mỗi đoạn ngang của một quan hệ khác (phân đoạn ngang dẫn xuất): Ri = R < Si, 1 i  w với w là số lƣợng các đoạn đƣợc định nghĩa trên R Si = Fi (S) với Fi là vị từ chọn để định nghĩa phân đoạn ngang nguyên thuỷ S. Phân đoạn dọc: Phân đoạn dọc là sự phân hoạch một quan hệ thành tập con các bộ, mỗi tập đƣợc xác định bởi phép chiếu đƣợc áp dụng cho quan hệ, tức là: Ri =X (R), trong đó X  là tập con của tập các thuộc tính của R. Để khôi phục lại quan hệ từ các phân đoạn dọc, cần phải thêm vào mỗi đoạn khoá chính của quan hệ. Phân đoạn hỗn hợp: Là sự kết hợp giữa phân đoạn dọc và phân đoạn ngang. 1.4.4.2 Nhân bản và cấp phát Việc nhân bản nhằm nâng cao khả năng sẵn sàng của dữ liệu. Mức nhân bản cao nhất là nhân bản toàn bộ dữ liệu, tại mỗi trạm của hệ thống phân tán đều đƣợc nhân bản toàn bộ CSDL, với mức này chỉ cần ít nhất một trạm làm việc là hệ thống có thể hoạt động. Nhƣng với mức nhân bản này thì hệ thống bị ảnh hƣởng đáng kể tới tốc độ trong quá trình cập nhật dữ liệu. 20