Tài liệu Cơ sở dữ liệu phân tán và tối ưu hoá vấn tin

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYẾN QUANG THẢO Cơ sở dữ liệu phân tán và tối ưu hoá vấn tin luËn v¨n th¹c SĨ CÔNG NGHỆ THÔNG TIN Hµ néi - 2006 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYẾN QUANG THẢO Cơ sở dữ liệu phân tán và tối ưu hoá vấn tin Mã số : 1.01.10 luËn v¨n th¹c SĨ CÔNG NGHỆ THÔNG TIN Người hướng dẫn khoa học: PGS.TS. Hồ Thuần Hµ néi - 2006 1 MỤC LỤC LỜI NÓI ĐẦU ............................................................................................................4 Chương 1 KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN ....................................6 1.1 Cơ sở dữ liệu quan hệ........................................................................................6 1.2 Các dạng chuẩn. ................................................................................................7 1.3 Ngôn ngữ dữ liệu quan hệ [4]. ..........................................................................9 1.4 Hệ cơ sở dữ liệu phân tán [4]. .........................................................................11 1.4.1 Các khái niệm về CSDL PT.....................................................................12 1.4.2 Các mục tiêu của hệ quản trị CSDL PT. ..................................................13 1.4.3 Kiến trúc hệ quản trị CSDL PT................................................................14 1.4.4 Phân mảnh, nhân bản và cấp phát dữ liệu................................................17 Chương 2 MỘT SỐ NGUYÊN LÝ CHUNG CỦA TỐI ƯU HÓA TRUY VẤN....23 2.1 Mục tiêu của bài toán xử lý truy vấn [4].........................................................23 2.2 Độ phức tạp của các phép toán đại số quan hệ. ..............................................27 2.3 Mô tả bộ xử lý truy vấn...................................................................................28 2.4 Phân rã truy vấn và định vị dữ liệu. ................................................................32 2.4.1 Phân rã truy vấn .......................................................................................32 2.4.2 Định vị dữ liệu .........................................................................................40 2.5 Tối ưu hóa truy vấn phân tán. .........................................................................46 2.5.1 Tối ưu hóa truy vấn ..................................................................................47 2.5.2 Tối ưu hóa truy vấn trong môi trường tập trung ......................................54 2.5.3 Các thuật toán tối ưu hóa truy vấn trong môi trường phân tán ................61 Chương 3 MỘT SỐ ĐỀ XUẤT KHÁC VỀ XỬ LÝ PHÉP NỐI TRONG CÁC HỆ CSDL.........................................................................................................................85 3.1 Ứng dụng lý thuyết đồ thị trong tối ưu hóa truy xuất CSDL để thực hiện phép nối [9]. ...................................................................................................................85 3.1.1 Sử dụng chỉ mục để thực hiện phép nối...................................................86 3.1.2 Mô hình đồ thị kết nối trang.....................................................................88 3.1.3 Xác định cận trên của kích thước bộ nhớ đệm.........................................90 3.1.4 Các Heuristic để làm giảm lượng bộ nhớ đệm cần thiết..........................92 3.1.5 Lược đồ bộ nhớ đệm dựa trên cơ sở lưu trữ toàn bộ trang. .....................94 3.1.6 Xác định kích thước bộ nhớ đệm để thực hiện một truy xuất cho mỗi trang...................................................................................................................95 3.2 Một số phương án tiếp cận xử lý nối phân tán khác. ....................................102 3.2.1 Sử dụng thông tin phụ thuộc vị trí (placement dependency) để thực hiện nối [7]. .............................................................................................................102 3.2.2 Thuật toán phân mảnh và nhân bản [7]..................................................105 3.2.3 Thuật toán qui hoạch băm [7] ................................................................107 3.2.4 Xử lý truy vấn chuỗi [7].........................................................................110 3.2.5 Tăng tốc xử lý truy vấn nhờ AHYPERF [12] ........................................114 KẾT LUẬN .............................................................................................................124 TÀI LIỆU THAM KHẢO.......................................................................................125 2 DANH MỤC CÁC HÌNH VẼ Hình 1. 1 CSDL trung tâm trên một mạng................................................................12 Hình 1. 2 Môi trường của hệ CSDL PT ....................................................................12 Hình 1. 3 Kiến trúc tham chiếu CSDL PT ................................................................15 Hình 1. 4 Các thành phần của một hệ quản trị CSDL PT .........................................17 Hình 1. 5 Các kiểu phân mảnh ..................................................................................18 Hình 1. 6 Các quan hệ đã được chuẩn hóa................................................................19 Hình 1. 7 Phân mảnh ngang nguyên thủy cho quan hệ DUAN ................................20 Hình 1. 8 Phân mảng dọc cho quan hệ DUAN .........................................................21 Hình 2. 1 Các chiến lược thực thi .............................................................................25 Hình 2. 2 Lược đồ tổng quát xử lý truy vấn phân tán ...............................................31 Hình 2. 3 Các đồ thị quan hệ.....................................................................................35 Hình 2. 4 Đồ thị truy vấn không liên thông ..............................................................35 Hình 2. 5 Thí dụ về cây truy vấn...............................................................................37 Hình 2. 6 Cây truy vấn tương đương ........................................................................39 Hình 2. 7 Cây truy vấn đã được viết lại ....................................................................40 Hình 2. 8 Cây truy vấn sau khi thay thế....................................................................41 Hình 2. 9 Rút gọn phân mảnh ngang (với phép chọn) ..............................................42 Hình 2. 10 Rút gọn cho phân mảnh ngang (với phép nối)........................................43 Hình 2. 11 Rút gọn cho phân mảnh dọc....................................................................44 Hình 2. 12 Rút gọn cho phân mảnh gián tiếp............................................................45 Hình 2. 13 Rút gọn cho phân mảnh hỗn hợp ............................................................46 Hình 2. 14 Quá trình tối ưu hóa truy vấn ..................................................................47 Hình 2. 15 Các cây nối tương đương ........................................................................48 Hình 2. 16 Hai hình thái của các cây nối ..................................................................49 Hình 2. 17 Hành động của bộ tối ưu hóa khi áp dụng chiến lược đơn định .............49 Hình 2. 18 Hành động của bộ tối ưu hóa khi áp dụng chiến lược ngẫu nhiên..........50 Hình 2. 19 Thí dụ về truyền dữ liệu cho một truy vấn..............................................51 Hình 2. 20 Đồ thị nối của câu truy vấn q1 ................................................................60 Hình 2. 21 Các thứ tự nối khác nhau ........................................................................61 Hình 2. 22 Truyền các toán hạng trong phép toán hai ngôi ......................................62 Hình 2. 23 Đồ thị nối của câu truy vấn phân tán ......................................................63 Hình 2. 24 Biến đổi câu truy vấn có chu trình ..........................................................73 Hình 2. 25 Truy vấn mẫu và số liệu thống kê ...........................................................76 Hình 3. 1 Quan hệ với các bộ tham gia nối...............................................................87 Hình 3. 2 Hai dãy truy xuất trang dữ liệu của hình 3.1.............................................87 Hình 3. 3 Đồ thị kết nối trang của CSDL trong hình 3.1 ..........................................88 Hình 3. 4 Quan hệ giữa kích thước tập trang và hệ số chọn .....................................89 Hình 3. 5 Một đồ thị kết nối trang tổng quát.............................................................90 Hình 3. 6 Giá trị lát cắt biểu diễn lượng bộ nhớ đệm cần thiết.................................91 Hình 3. 7 Kích thước thước bộ nhớ đệm của heuristic 1 và 2 ..................................93 Hình 3. 8 Kích thước trung bình của danh sách tìm về.............................................93 Hình 3. 9 Đồ thị kết nối trang và đồ thị không chu trình tương ứng ........................96 3 Hình 3. 10 Đồ thị kết nối trang .................................................................................99 Hình 3. 11 Đồ thị không chu trình thu được từ hình 3.10.........................................99 Hình 3. 12 Hai quan hệ được phân mảnh................................................................102 Hình 3. 13 Cấu hình trước khi xử lý nối .................................................................105 Hình 3. 14 Một ví dụ về phân mảnh trên các trạm..................................................107 Hình 3. 15 Mô tả cách tạo bản sao cho bộ ..............................................................108 Hình 3. 16 Tính toán chi phí từ dưới – lên.............................................................112 Hình 3. 17 PERF của R và S ...................................................................................115 Hình 3. 18 Mô tả quan hệ........................................................................................118 4 LỜI NÓI ĐẦU Cơ sở dữ liệu (CSDL) là một trong những lĩnh vực được quan tâm nhiều trong công nghệ thông tin. Ra đời từ những năm 60 đến nay, đã xuất hiện nhiều thế hệ quản trị CSDL, và cũng đã có nhiều ứng dụng trong khoa học kỹ thuật cũng như trong các ngành kinh tế khác. Việc nghiên cứu CSDL đã và đang phát triển ngày càng phong phú, đa dạng. Từ những năm 70, mô hình dữ liệu quan hệ do E.F. Codd đưa ra đã tạo một cơ sở vững chắc cho các vấn đề nghiên cứu về CSDL. Với ưu điểm về tính cấu trúc, và khả năng hình thức hóa phong phú, CSDL quan hệ dễ dàng mô phỏng các hệ thống thông tin đa dạng trong thực tiễn, làm tăng khả năng xử lý, quản trị, khai thác dữ liệu, thông tin. Trên thực tế nhiều hệ quản trị CSDL thương mại, xây dựng trên mô hình quan hệ, đã và đang được lưu hành, sử dụng rộng rãi trên thị trường như:DBASE, ORACLE, MS SQL… Cho đến nay đã có hàng loạt các vấn đề về CSDL được nghiên cứu, giải quyết. Với mục đích tìm hiểu để nâng cao khả năng ứng dụng của của các hệ CSDL, luận văn tập trung vào việc nghiên cứu vấn đề “tối ưu hóa câu truy vấn trong CSDL phân tán”. CSDL phân tán nói riêng và các hệ phân tán nói chung là một lĩnh vực nghiên cứu không mới, nhưng gần đây cùng với sự phát triển nhanh chóng và mạnh mẽ của công nghệ truyền thông, mạng Internet và đặc biệt là xu thế phát triển của thương mại điện tử, thì 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 cũng như các nhà sản xuất phần mềm. Như ta đã biết, thành công ngày càng tăng của công nghệ CSDL quan hệ trong việc xử lý dữ liệu một phần là do tính dễ dùng khả năng khai thác, tìm kiếm dữ liệu của các ngôn ngữ phi thủ tục (như SQL), và chính nó đã cải thiện đáng kể công việc phát triển ứng dụng và khả năng sáng tạo của người dùng. Các ngôn ngữ phi thủ tục của CSDL quan hệ đã cho phép diễn tả câu truy vấn phức tạp một cách chính xác và đơn giản. Đặc biệt là để có được câu trả lời cho một câu truy vấn thì người sử dụng 5 không cần phải xác định chính xác trình tự tiến hành các thao tác/phép toán trong một câu truy vấn. Trình tự này được xử lý bởi Bộ xử lý truy vấn (query processor) của hệ quản trị CSDL, và đó là bài toán xử lý truy vấn hay tối ưu hóa truy vấn. Tối ưu hóa truy vấn là việc xác định một chiến lược thực hiện truy vấn sao cho có thể cực tiểu hóa được hàm chi phí. Đây là bài toán khó, đặc biệt là trong môi trường phân tán bài toán này thuộc lớp NP-Hard. Để tránh một chi phí tối ưu hóa quá lớn thì cách tiếp cận dùng các heuristic được sử dụng để có thể đạt được một chiến lược thực thi gần tối ưu. Các yếu tố cần được xem xét khi giải bài toán này là: sự phân tán dữ liệu, chi phí xử lý cục bộ, chi phí truyền… Các yếu tố quyết định đến việc cực tiểu hàm chi phí có thể có nhiều, nhưng những yếu tố quan trọng nhất là trình tự thực hiện tối ưu các phép nối, việc chọn các bản sao, các mảnh phải truy xuất, cũng như việc chọn các trạm thực hiện và việc sử dụng các giải thuật truy xuất dữ liệu cục bộ và phân tán. Với những nét chính ở trên, nội dung của bản luận văn này trình bày các nguyên lý chung, các kỹ thuật, thuật toán liên quan đến vấn đề tối ưu hóa truy vấn và một số phương án đề xuất cho việc giải quyết bài toán tối ưu này. Luận văn được chia làm 3 phần: Chương 1: KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN - Chương này trình bày những kiến thức cơ bản của hệ CSDL phân tán, kiến trúc tham chiếu, các kiểu phân mảnh, các mức trong suốt phân tán. Chương 2: MỘT SỐ NGUYÊN LÝ CHUNG CỦA TỐI ƯU HÓA CÂU TRUY VẤN - Chương này trình bày nguyên lý chung của tối ưu hóa truy vấn trong CSDL nói chung và trong CSDL phân tán nói riêng. Trong chương này cũng có trình bày một số thuật toán kinh điển để tối ưu hóa câu truy vấn được sử dụng trong các hệ CSDL quan hệ như INGRES, SYSTEM R… Chương 3: Chương 3 MỘT SỐ ĐỀ XUẤT KHÁC VỀ XỬ LÝ PHÉP NỐI TRONG CÁC HỆ CSDL - Chương này trình bày một số các đề xuất cải tiến, các kỹ thuật xử lý truy vấn dựa trên việc xử lý các nối và có nhận xét, đánh giá và so sánh. 6 Chương 1 KHÁI QUÁT VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN Chương này trình bày một cách khái quát những kiến thức cơ sở về mô hình quan hệ (lược đồ quan hệ, ngôn ngữ dữ liệu quan hệ…), về hệ CSDL phân tán (các kiến trúc, đặc trưng, và các vấn đề của CSDL phân tán…)[4]. Chương này cung cấp những kiến thức cơ sở cho các chương sau. 1.1 Cơ sở dữ liệu quan hệ Cơ sở dữ liệu (CSDL) là một tập hợp dữ liệu có cấu trúc, liên quan đến các hiện tượng thực tế mà chúng ta cố gắng mô hình hóa chúng. CSDL quan hệ là loại CSDL được cấu trúc theo dạng bảng (table). Về hình thức quan hệ (relation) là một tập con của tích Descartes của một hoặc nhiều miền trị (domain) xác định trên tập các thuộc tính (attributes). Một quan hệ r xác định trên tập thuộc tính Ω = { A1 , A2 ,... An } , khi đó : r ⊆ Dom( A1 ) × Dom( A2 ) × ... × Dom( An ) Mỗi hàng của quan hệ được gọi là một bộ (tuple), như vậy quan hệ r là một tập hợp các n-bộ có dạng: r ⊆ {(a1 , a2 ,..., an ) | ai ∈ Dom( Ai ), với i = 1,2,...n} Trong đó Dom( Ai ) là miền giá trị của thuộc tính Ai . Số thuộc tính của quan hệ gọi là bậc của quan hệ. Quan hệ r có thể bị thay đổi theo thời gian do việc thực hiện các phép toán cập nhật trên r (thêm vào, loại bỏ, sửa đổi các bộ). Lược đồ quan hệ (relation scheme). Một lược đồ quan hệ R là một cặp có thứ tự R =< Ω, F > , trong đó Ω là tập hữu hạn các thuộc tính của quan hệ, F là tập các điều kiện giữa các thuộc tính (F còn gọi là tập các ràng buộc toàn vẹn). Một ràng buộc trên tập các thuộc tính { A1 , A2 ,..., An } là một tính chất trên tập tất cả các quan hệ xác định trên tập thuộc tính này. 7 Còn khi nói đến một lược đồ quan hệ, trong đó chỉ tập trung vào khía cạnh mô tả cấu trúc của một quan hệ mà không quan tâm đến bộ cụ thể, ta sẽ dùng ký hiệu: R ( A1 , A2 ,..., An ) Với R là tên của quan hệ, A1 , A2 ,..., An là danh sách tên các thuộc tính. Thể hiện quan hệ. Với lược đồ quan hệ R, theo thời gian, nhiều quan hệ có cấu trúc và ràng buộc toàn vẹn được mô tả bởi lược đồ này. Mỗi quan hệ như vậy còn được gọi là một thể hiện của lược đồ R. Lược đồ quan hệ mô tả cấu trúc của quan hệ. Tại mỗi thời điểm lược đồ quan hệ sẽ có một thể hiện quan hệ cụ thể. Khóa của một lược đồ quan hệ là một tập con các thuộc tính không rỗng nhỏ nhất sao cho giá trị của các thuộc tính trong khóa cho phép xác định duy nhất mỗi bộ của quan hệ. Các thuộc tính có mặt trong ít nhất một khóa gọi là các thuộc tính khóa. Một tập có chứa khóa được gọi là siêu khóa (supperkey). Ta có thể định nghĩa một cách hình thức như sau: Cho lược đồ quan hệ R =< Ω, F > , K ⊆ Ω , K được gọi là khóa của lược đồ quan hệ R nếu thỏa mãn 2 điều kiện sau: i. Bất kỳ hai bộ khác nhau t1 , t 2 ∈ r , r là một thể hiện của R, luôn có t1[ K ] ≠ t 2 [ K ] . ii. Không tồn tại K ' ⊂ K thỏa mãn điều kiện trên. Tập K sẽ là siêu khóa nếu chỉ thỏa mãn điều kiện (i). 1.2 Các dạng chuẩn. Chuẩn hóa – là một quá trình từng bước thay thế một tập quan hệ đã cho bằng các tập quan hệ có cấu trúc ngày càng đơn giản và chuẩn tắc hơn [Tsichritzis and Lochovsky, 1977]. Mục đích của chuẩn hóa là loại bỏ những bất thường của một quan hệ. Quan hệ được chuẩn hóa là quan hệ trong đó mỗi miền của một thuộc tính chỉ chứa những giá trị nguyên tố (atomic), tức là không phân nhỏ đượ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ệ: 8 Về sau Boyce và Codd đã định nghĩa một phiên bản sửa đổi của dạng 3NF, thường được gọi là dạng chuẩn Boyce-Codd (BCNF). Tiếp sau đó là các dạng chuẩn 4NF [Fagin, 1977] và chuẩn 5NF [Fagin, 1979] Yêu cầu của chuẩn hóa là không làm mất mát thông tin khi thay một quan hệ 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ã đó được 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 hóa là bảo toàn phụ thuộc (dependency preservation). Phân rã được gọi là bảo toàn phụ thuộc nếu hợp của các phụ thuộc hàm của các quan hệ được phân rã tương đương với bao đóng (closure) của các phụ thuộc hàm trong quan hệ ban đầu. Định nghĩa dạng chuẩn 1NF. Một lược đồ quan hệ R được gọi là ở dạng chuẩn 1NF nếu và chỉ nếu toàn bộ các miền có mặt trong R đều chỉ chứa các giá trị nguyên tố [2]. Định nghĩa dạng chuẩn 2NF. Lược đồ quan hệ R ở dạng chuẩn 2NF nếu nó ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khóa của R phụ thuộc hàm đầy đủ vào mỗi một khóa [2]. Định nghĩa dạng chuẩn 3NF. Lược đồ quan hệ R ở dạng chuẩn 3NF nếu nó ở dạng chuẩn 1NF và nếu mỗi thuộc tính không khóa của R là không phụ thuộc hàm bắc cầu vào mỗi một khóa [2]. Định nghĩa dạng chuẩn BCNF. Lược đồ quan hệ với tập các phụ thuộc hàm được gọi là ở dạng chuẩn BCNF nếu X → A thỏa trên R, A ∉ X thì X là một siêu khóa của R [2]. 9 Định nghĩa phụ thuộc hàm đầy đủ. Cho lược đồ quan hệ R với tập thuộc tính Ω = { A1 , A2 ,... An } , X và Y là hai tập thuộc tính khác nhau X ⊆ Ω và Y ⊆ Ω . Y là phụ thuộc hàm đầy đủ vào X nếu Y là phụ thuộc hàm vào X nhưng không phụ thuộc vào bất kỳ một tập con thực sự nào của X [2]. 1.3 Ngôn ngữ dữ liệu quan hệ [4]. Các ngôn ngữ thao tác dữ liệu (DML) được phát triển cho mô hình quan hệ (được gọi là ngôn ngữ truy vấn – query language) được chia thành hai nhóm cơ bản.: các ngôn ngữ dựa trên đại số quan hệ (relational algebra) và các ngôn ngữ dựa trên phép tính quan hệ. Khác biệt giữa chúng là cách thức người sử dụng đưa ra câu truy vấn. Đại số quan hệ thuộc loại thủ tục (procedural), trong đó người dùng cần phải đặc tả, nhờ một số toán tử, xem làm thế nào để thu được kết quả. Ngược lại phép tính quan hệ thuộc loại phi thủ tục (nonpropcedural), người sử dụng chỉ cần đặc tả các mối liên hệ cần phải bảo đảm trong kết quả. Cả hai đều được Codd đưa ra và đều tương đương về khả năng diễn tả. Đại số quan hệ được sử dụng nhiều hơn trong các nghiên cứu về CSDL phân tán vì nó ở mức thấp hơn và tương ứng trực tiếp hơn với chương trình được trao đổi trên mạng. Về cơ bản thì phép tính quan hệ có thể được dịch thành đại số quan hệ. Đại số quan hệ là cơ sở quan trọng trong việc tối ưu hóa truy vấn, sau đây sẽ trình bày một số các phép toán trên các quan hệ. Đại số quan hệ có một tập hợp các phép toán trên các quan hệ. Mỗi toán tử nhận một hoặc hai quan hệ làm toán hạng và cho ra một quan hệ mới (quan hệ kết quả), đến lượt nó lại có thể sử dụng làm toán hạng cho một toán tử khác. Các phép toán này cho phép vấn tin và cập nhật CSDL quan hệ. Có năm phép toán cơ bản và năm phép khác có thể được định nghĩa theo năm phép toán cơ bản này. Đó là các phép chọn (selection), chiếu (projection), hợp (union), trừ (set difference), và tích Descartes. Hai phép toán đầu tiên thuộc loại một ngôi, ba phép toán sau thuộc loại hai ngôi. Các phép toán bổ sung có thể là: giao (intersection), nối θ ( θ -join), nối tự nhiên (natural join), nối nửa (semi join) và phép chia (division) [4]. Trong đó toán hạng của phép toán hai ngôi phải khả hợp 10 (union compatible). Hai quan hệ được gọi là khả hợp nếu chúng có cùng bậc (có số thuộc tính bằng nhau) và thuộc tính thứ i của quan hệ này có miền xác định trùng với miền của thuộc tính thứ i của quan hệ kia. 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 thỏa 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 đi trong quan hệ R những thuộc tính không nằm trong X. Vì thế bậc của quan hệ kết quả luôn nhỏ hơn bậc của quan hệ gốc ∏ 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ần chú ý rằng R và S phải khả hợp. R ∪ S = {t | t ∈ R hoặc t ∈ S hoặc t ∈ R và 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 × 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 hai quan hệ R và S, là tập tất cả các bộ t thuộc về cả hai quan hệ R và S. Giao có thể biểu thị bằng các toán tử cơ bản như sau: R ∩ S = {t | t ∈ R, t ∈ S } = R − ( R − S ) Nối- θ . Phép nối này 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 nhất là nối- θ , hay đơn giản là nối. Với F là vị từ nối: R >< F S = σ F ( R × S ) 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, gồm tất cả các bộ t là bộ ghép của bộ r thuộc R và bộ s[Y] với s bộ thuộc S thỏa r[X]=s[X] R >< S = {(u , v) | u ∈ R ∧ v = s[Y ] ∧ s ∈ S ∧ s[ X ] = u[ X ]} 11 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 t bộ trên 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 ) × S ) − R ) , với A' là tập thuộc tính của R không thuộc S. 1.4 Hệ cơ sở dữ liệu phân tán [4]. Cơ sở dữ liệu phân tán là sự hợp nhất của hai cách tiếp cận xử lý dữ liệu dường như đối lập nhau: công nghệ CSDL và công nghệ mạng máy tính. Một trong những mục đích, động cơ chính của việc sử dụng các hệ CSDL là việc tích hợp các dữ liệu, giao tác của một xí nghiệp, tổ chức và cho phép truy xuất tập trung, do vậy có thể điều khiển được các truy xuất đến dữ liệu đó. Còn công nghệ mạng lại đi ngược lại với mọi nỗ lực tập trung hóa. Mấu chốt của vấn đề là mục tiêu quan trọng của công nghệ CSDL là sự tích hợp mà không phải là sự tập trung hóa, như vậy ta vẫn có thể có được sự tích hợp mà không cần sự tập trung hóa và đó chính là mục tiêu của CSDL phân tán (CSDL PT). Chúng ta có thể định nghĩa một CSDL PT là một tập hợp nhiều CSDL có liên đới logic và được phân bố trên một mạng máy tính. Vậy hệ quản trị CSDL PT được định nghĩa là một hệ thống phần mềm cho phép quản lý các CSDL PT, và làm cho việc phân tán trở nên trong suốt đối với người sử dụng. Với các hệ CSDL PT chúng ta dễ dàng nhận thấy những ưu điểm tiềm năng như sau: ™ 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 PT cung cấp khả năng trong suốt phân tán (distribution transparent) với ý nghĩa là che dấu các chi tiết như dữ liệu được lưu trữ ở đâu trong hệ thống… Hệ quản trị CSDL PT có thể cung cấp các khả năng trong suốt sau: 9 Trong suốt phân tán, hay trong suôt mạng 9 Trong suốt nhân bản 9 Trong suốt phân mảnh 12 ™ Tăng tính tin cậy và tính sẵn sàng. ™ Cho phép dùng chung dữ liệu trong khi 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ề CSDL PT Ở mức phần cứng vật lý, những nhân tố chính phân biệt một hệ CSDL PT với một hệ CSDL tập trung là: Có nhiều máy tính được gọi là trạm hay nút (node) 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 và các lệnh giữa các trạm. Hình 1. 1 CSDL trung tâm trên một mạng Hình 1. 2 Môi trường của hệ CSDL PT 13 Một hệ quản trị CSDL PT 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 PT. Ngoài chức năng của các hệ quản trị CSDL và của phần mềm quản trị truyền thông, hệ quản trị CSDL PT 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ủ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 phân tán. ™ 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 (site) 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 PT là tính thuần nhất hay không thuần nhất. Một CSDL PT thuần nhất (homogeneous DDB) 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 PT thuần nhất thường là kết quả của cách tiếp cận thiết kế trên xuống, trong đó ta thiết kế một CSDL PT từ một CSDL tập trung. Một CSDL PT không thuần nhất (heterogeneous DDB) là một CSDL PT có được bằng cách tích hợp một tập các 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ị CSDL PT. Sự độc lập dữ liệu và trong suốt phân bố. 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 giữ trong từ điển dữ liệu (catalog), và được hệ quản trị CSDL PT sử dụng để định vị dữ liệu. Đây là một dạng trong suốt cơ bản cần có trong một hệ CSDL PT, nó liên quan đến tính độc lập dữ liệu 14 (data independence) 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ự 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 PT. Trong suốt phân mảnh. Việc truy cập tới dữ liệu thường được xác định trên các quan hệ con (thu được từ việc chia nhỏ các quan hệ gốc) được gọi là các mảnh (fragment). Việc phân mảnh (ngang, dọc, hỗn hợp) làm tăng hiệu năng, tính sẵn sàng, độ tin cậy của CSDL PT. Trong suốt phân mảnh 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 mảnh 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 PT 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. 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 PT có thể hoàn toàn phi 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ị CSDL PT Có nhiều kiểu kiến trúc CSDL như, các hệ CSDL client/server, 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à server ) hay còn gọi là các hệ phân tán ngang hàng. Và kiểu kiến trúc này cũng là kiểu được tập trung thảo luận ở phần này. 15 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, mà chúng ta gọi là lược đồ trong cục bộ (LIS). Hình ảnh về toàn thể CSDL được mô tả bởi lược đồ khái niệm toàn cục (GCS), nó mô tả cấu trúc logic của dữ liệu ở mọi vị trí. Để xử lý việc phân mảnh và nhân bản ta sử dụng lược đồ khái niệm cục bộ (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ộ. Và 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 1.3 Các thành phần cụ thể của một hệ CSDL PT . Ở đây hệ QT CSDL PT gồm 2 thành phần (mô tả trong Hình 1.4). Một thành phần xử lý mọi tương tác với người sử dụng là Bộ xử lý tiếp nhận người dùng (User Processor), còn thành phần kia lo việc xử lý dữ liệu (Data Processor). Hình 1. 3 Kiến trúc tham chiếu CSDL PT 16 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à định dạng dữ liệu để chuyển cho người sử dụng các kết quả. Bộ kiểm soát dữ liệu ngữ nghĩa (semantic 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 thiểu chi phí, và phiên dịch các câu truy vấn toàn cục thành 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 của 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. Bộ hỗ trợ thực thi (Runtime support processor) truy xuất CSDL tùy vào các lệnh trong lịch (schedule) do bộ tối ưu vấn tin sinh ra. Nó là giao diện với bộ điều hành và chứa bộ quản lý vùng đệm CSDL (database buffer manager), chịu trách nhiệm quản lý vùng đệm và quản lý việc 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 phải 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. 17 Hình 1. 4 Các thành phần của một hệ quản trị CSDL PT 1.4.4 Phân mảnh, nhân bản và cấp phát dữ liệu 1.4.4.1 Phân mảnh Sự phân mảnh 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 PT. Các mảnh đượ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 mảnh 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 mảnh. Do vậy việc phân mảnh 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 mảnh 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 mảnh sẽ bị giảm hiệu suất hoạt động (ví 18 dụ việc truy xuất dữ liệu từ nhiều mảnh 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 mảnh. Còn vấn đề nữa, là việc liên quan đến việc kiểm soát dữ liệu ngữ nghĩa (semantic data control), đặc biệt là vấn đề kiểm tra tính toàn vẹn. Do kết quả của việc phân mảnh, 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 mảnh khác nhau và được cấp phát cho những trạm khác nhau, vậy nên việc đơn giản như 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 mảnh 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). Hình 1. 5 Các kiểu phân mảnh Thí dụ 1.1: Để tiện miêu tả ta sẽ sử dụng một CSDL mẫu mô hình hóa cho một công ty để làm ví dụ. Các thực thể được mô hình hóa là nhân viên -NHANVIEN và các dự án DUAN. Với mỗi nhân viên thì có những thông tin sau: mã số nhân viên – MSNV, tên nhân viên – TENNV, nghề nghiệp - NNGH, lương – LUONG, mã số dự án – MSDA mà nhân viên đó đang làm việc, nhiệm vụ - NVU trong dự án đó, thời gian – TGIAN được phân công trong dự án tính theo tháng. Tương tự như vậy với mỗi dự án thì cũng có nhiều thông tin như: MSDA, tên dự án – TENDA, ngân sách dự án – NSDA, địa điểm tiến hành dự án - DD. Các lược đồ quan hệ cho CSDL này có thể được định nghĩa như sau: NHANVIEN(MSNV,TENNV,NNGH,LUONG,MSDA,NVU,TGIAN) DUAN(MSDA,TENDA,NSDA,DDDA) Sau khi thực hiện các bước chuẩn hóa ta thu được: NHANVIEN(MSNV,TENNV,NNGH)