Tóm tắt luận văn Truy vấn trong cơ sở dữ liệu phân tán và ứng dụng

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- PHẠM VĂN TUÂN TRUY VẤN TRONG CƠ SỞ DỮ LIỆU PHÂN TÁN VÀ ỨNG DỤNG Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60. 48. 01( Khoa học máy tính) TÓM TẮT LUẬN VĂN THẠC SĨ HÀ NỘI – NĂM 2012 Luận văn được hoàn thành tại: HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG Người hướng dẫn khoa học: PGS. TS Lê Huy Thập Phản biện 1:…………………………………… Phản biện 2: ………………………………… Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn thông Vào lúc: ......giờ.....ngày.......tháng......năm ..... Có thể tìm hiểu luận văn tại: - Thư viện của Học viện Công nghệ Bưu chính Viễn thông 1 PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Xã hội ngày càng phát triển kèm theo yêu cầu khối lượng thông tin cần xử lý, lưu trữ tăng lên. Trên thực tế, các doanh nghiệp, các đơn vị và các tổ chức phải phân bố trên một vùng rộng lớn về mặt vật lý, có thể dàn trải trên phạm vi nhiều thành phố hoặc toàn bộ quốc gia hay đến một vài quốc gia, thậm chí trên toàn cầu. Do đó, dữ liệu không thể lưu trữ tập trung ở một địa điểm nhất định mà giải khắp các địa điểm mà cơ quan, tổ chức hay doanh nghiệp đó hoạt động. Khi dữ liệu không còn lưu trữ tập trung thì vấn đề làm thế nào để quản lý, tốc độ truy xuất dữ liệu phục vụ cho công tác chuyên môn không bị ảnh hưởng, không bị gián đoạn được đặt ra. Đó chính là tiền đề để cơ sở dữ liệu phân tán ra đời. Khi khối lượng thông tin phải xử lý ngày càng lớn, phong phú và đa dạng thì vấn đề đặt ra là xử lý thông tin như thế nào để giảm chi phí đến mức tối thiểu. Một trong các giải pháp có khả năng khả thi là phải tối ưu hóa các câu lệnh khi truy vấn dữ liệu nên tôi chọn nghiên cứu “ Truy vấn trong cơ sở dữ liệu phân tán và ứng dụng” làm đề tài luận văn tốt nghiệp của mình. 2. Phạm vi nghiên cứu của đề tài Đề tài nghiên cứu về các vấn đề cơ bản của cơ sở dữ liệu phân tán, các nguyên lý chung, các kỹ thuật, các thuật 2 toán liên quan đến vấn đề truy vấn và cài đặt thử nghiệm thuật toán truy vấn phân tán. 3. Ý nghĩa khoa học Trên cơ sở nghiên cứu về các mô hình CSDL phân tán và các cơ chế truy vấn để xây dựng thuật toán truy vấn tối ưu. Những kết quả dự kiến của luận văn sẽ góp phần vào việc thiết kế CSDL phân tán phục vụ cho việc truy vấn hiệu quả. 3 CHƯƠNG I: TỔNG QUAN 1.1 Giới thiệu chương 1.2.1 Nội dung 1.2.1 Giới thiệu về hệ quản trị cở sở dữ liệu phân tán 1.2.1.1 Khái niệm Cơ sở dữ liệu phân tán là một tập hợp các dữ liệu phụ thuộc logic lẫn nhau của cùng một hệ thống và được lưu trữ trên các trạm của một mạng máy tính. Cơ sở dữ liệu phân tán làm tăng khả năng truy cập tới cơ sở dữ liệu lớn trên mạng. Trong hệ thống đó mỗi máy tính quản lý một cơ sở dữ liệu thành phần được gọi là một nute hoặc site. Hệ quản trị cơ sở dữ liệu phân tán(DBMS) là phần mềm quản trị cơ sở dữ liệu và luôn được đảm bảo trong suốt đối với người sử dụng và cho phép tính tự trị. Định nghĩa này nhấn mạnh hai khía cạnh quan trong của cơ sở dữ liệu phân tán. - Tính phân tán - Sự tương quan logic 1.2.1.2 Những ưu điểm của cơ sở dữ liệu phân tán - Cho phép quản lý dữ liệu với nhiều mức trong suốt - Tăng độ tin cậy và khả năng sẵn sàng - Cải thiện hiệu năng - Dễ dàng mở rộng 4 1.2.1.3 Những nhược điểm của cơ sở dữ liệu phân tán - Tăng độ phức tạp thiết kế và cài đặt hệ thống - Hệ thống phần cứng cũng phức tạp hơn vì cần có nhiều trạm và các trạm phải được kết nối trên mạng. - Các phần mềm hệ thống đảm bảo quản trị, duy trì kết nối, trao đổi dữ liệu trên mạng. - Bảo mật khó khăn 1.2.1.4 Các đặc trưng trong suốt của cơ sơ dữ liệu phân tán 1.2.1.4.1 Trong suốt phân tán - Cho phép xử lý dữ liệu trên hệ cơ sở dữ liệu phân tán như đối với cơ sở dữ liệu tập trung. - Trong suốt phân tán thể hiện: + Trong suốt địa điểm + Trong suốt tên + Trong suốt bản sao + Trong suốt phân mảnh 1.2.1.4.2 Trong suốt giao dịch Cơ sở dữ liệu phân tán cho phép một giao dịch có thể cập nhật, sửa chữa dữ liệu trên các máy trạm khác nhau. 1.2.1.4.3 Trong suốt thất bại Đảm bảo tại một trạm của hệ thống bị hỏng thì hệ thống vẫn làm việc bình thường 1.2.1.4.4 Trong suốt thao tác Cho phép các câu lệnh thao tác dữ liệu đơn giản để truy cập được các cơ sở dữ liệu tại trạm cục bộ hoặc trạm từ xa. 5 1.2.1.4.5 Trong suốt về tính không thuần nhất Cho phép tự động kết hợp nhiều hệ quản trị cơ sở dữ liệu khác nhau với các khả năng trao đổi dữ liệu, xử lý cập nhật dữ liệu, xử lý giao tác phân tán trên toàn bộ hệ thống. 1.2.1.4.6 Kiến trúc tham chiếu của cơ sở dữ liệu phân tán - Lược đồ tổng thể - Phân mảnh - Lược đồ vị trí - Lược đồ ánh xạ cục bộ 1.2.2 Các phương pháp phân mảnh Phân mảnh là chia các bảng dữ liệu thành các bảng dữ liệu con. Có ba kiểu phân mảnh một quan hệ tổng thể: Phân mảnh ngang, phân mảng dọc và phân mảnh hỗn hợp. Ba yêu cầu của phân mảnh: - Điều kiện không mất thông tin - Điều kiện xây dựng lại - Điều kiện rời nhau 1.2.2.1 Phân mảnh ngang Phân mảnh ngang là sự phân chia một quan hệ thành các tập con các bộ, mỗi tập con được xác định bởi phép chọn với tân từ p trên quan hệ tổng thể R: Ri = σ pi với pi là tân từ của Ri .Để có thể khôi phục được R ta dùng phép hợp các quan hệ R = R1 R2 … Rn . 6 1.2.2.2 Phân mảnh ngang dẫn xuất Phân mảnh ngang dẫn xuất là sự phân mảnh quan hệ con dựa theo cách phân mảnh của quan hệ cha mẹ. 1.2.2.3 Phân mảnh dọc Phân mảnh dọc là sự chia một quan hệ thành các quan hệ con, cùng với tập thuộc tính khóa: Ri = Π{ATTRI} R, trong đó ATTRi là tập con của thuộc tính của R, cùng với khóa của R. Tiêu chuẩn cho sự phân mảnh dọc là đúng đắn: - Điều kiện đầy đủ - Điều kiện xây dựng lại - Điều kiện rời nhau 1.2.2.4 Phân mảnh hỗn hợp Là sự kết hợp cả phân mảnh dọc và phân mảnh ngang. 1.2.2.5 Nhân bản - Nhân bản dữ liệu đầy đủ - Không có nhân bản dữ liệu - Nhân bản dữ liệu từng phần 1.2.2.6 Định vị Là quá trình gán từng mảnh, từng bản sao của phân mảnh cho một trạm cụ thể trong hệ thống phân tán. 1.2.3 Giới thiệu một số thuật toán cơ bản trong hệ cơ sở dữ liệu tập trung 1.2.3.1 Nguyên lý chung của tối ưu hóa truy vấn Một câu vấn tin bậc cao dạng SQL sẽ có rất nhiều câu vấn tin dạng đại số quan hệ tương đương. Phương pháp để tìm ra được 7 câu vắn tin đại số quan hệ có chi phí ít nhất, sau đó chuyển câu vấn tin đại số đã tìm được đó trở lại dạng SQL, được gọi là “Sự tối ưu hóa”. 1.2.3.2 Các chiến lược tối ưu cơ bản Các chiến lược bao gồm - Thực hiện phép chọn sớm nhất có thể - Tổ hợp phép chọn xác định với phép tích Decartes thành phép kết nối - Tổ hợp dãy các phép toán một ngôi như phép chọn và phép chiếu - Tìm các biểu thức con chung trong một biểu thức - Xử lý các tệp trước - Đánh giá trước khi thực hiện phép toán 1.2.3.3 Phân rã câu truy vấn thành những câu truy vấn con - Đồ thị nối các quan hệ - Tách câu truy vấn thành các câu truy vấn con - Dùng phép nửa kết nối để giảm kích thước quan hệ - Phương pháp thay thế n – bộ 1.2.3.4 Thuật toán INGRES Thuật toán: INGRES – QOA Input: MVQ: Truy vấn đa biến với n biến Output: output: Kết quả thưc hiện Begin Output 8 If n =1 then Output run(MVQ) { Thực hiện truy vấn một biến} Else begin {tách MVQ thành m truy vấn một biến và một truy vấn nhiều biến } OVQ1,…, OVQm, MVQ’ MVQ For I 1 to m do Begin Output’ run(OVQi) {Thực thi OVQi} Output output output’ {hợp tất cả các kết quả } Endfor V CHOOSE – VARIABLE(MVQ’) { V được chọn cho phép thế toàn bộ} For mỗi bộ t V do Begin MVQ’’ thay thế các giá trị cho t trong MVQ’ output INGRES – QOA(MVQ’’) {gọi đệ quy} output output output’{ hợp tất cả các kết quả} end Endif END. 1.2.3.5 Thuật toán SYSTEM R Thuật toán: R – QOA 9 Input: QT: Cây truy vấn với n quan hệ Output: output : kết quả thực hiện Begin For mỗi quan hệ Ri QT do Begin For mỗi đường truy cập APij to Ri do xác định cost(APij) endfor best_ APi ở Pij với chi phí tối thiểu endfor for mỗi order(Ri1,Ri2,…,Rim) với i = 1,2 …,n! do begin build strategy(…(best APi1 .. Ri2 ) .. Ri3) ………Rin ) tính toán chi phí của chiến lược endfor output chiến lược với chi phí tối thiểu End.{R- QOA} 1.3 Kết luận chương 10 CHƯƠNG 2 : CÁC THUẬT TOÁN TỐI ƯU TRONG HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN 2.1 Giới thiệu chương 2.2 Nội dung 1. Phân rã câu truy vấn a. Chuẩn hoá b. Phân tích c. Loại bỏ dư thừa d. Viết lại 2. Định vị dữ liệu phân tán a. Rút gọn phân mảnh ngang nguyên thuỷ b. Rút gọn phân mảnh dọc c. Rút gọn phân mảnh gián tiếp d. Rút gọn phân mảnh hỗn hợp 3. Khái quát về xử lý câu truy vấn a. Vấn đề xử lý truy vấn b. Các mục tiêu của xử lý câu truy vấn c. Các giai đoạn xử lý câu truy vấn 4. Tối ưu hoá các câu truy vấn phân tán  Đầu vào bộ tối ưu hoá câu truy vấn  Các thuật toán tối ưu hoá truy vấn trong môi trường phân tán 2.2.1 Thuật toán INGRES phân tán Thuật toán : D- INGRES – QOA Input : MVQ : Truy vấn đa biến với n biến 11 Output : output : Kết quả của truy vấn đa biến cuối cùng BEGIN For mỗi OVQi có thể tách ra in MVQ do {chạy tất cả các truy vấn một biến} Run(OVQi) (1) Endfor MVQ’ _ list REDUCE(MVQ) {thay thế MVQ bởi n truy vấn không thể rút gọn} (2) While n 0 do {n – số truy vấn không thể rút gọn } (3) Begin {Chọn truy vấn không thể rút gọn liên quan đến các mảnh nhỏ nhất } MVQ’ select _ query(MVQ’_list); (3.1) {Xác định các đoạn để truyền và trạm xử lý MVQ’} Fragmen- site- list SELECT _ RATEGY(MVQ’); (3.2) {truyền các mảnh đã chọn tới các trạm đã chọn} For mỗi cặp (F,S) trong Fragnemt – site – list do (3.3) Chuyển đoạn F tới trạm S; End – for Run(MVQ’); n n-1; (3.4) End – while {đầu ra của thuật toán là kết quả của MVQ’ cuối cùng} 12 End. (D- INGRES - QOA) Bước 1 : Xử lý địa phương tất cả các truy vấn một biến (phép chọn và phép chiếu). Bước 2: Thuật toán thu gọn được áp dụng cho truy vấn ban đầu, tách các truy vấn không thể rút gọn và các truy vấn một biến ra. Bỏ qua các truy vấn một biến vị đã xử lý ở bước 1 Bước 3: Áp dụng cho các câu truy vấn không thể rút gọn. Bước 3.1: Chọn các truy vấn chưa được xử lý và liên quan đến các mảnh nhỏ hơn. Bước 3.2: Chọn chiến lược tốt nhất để xử lý truy vấn MVQ’ (truy vấn không thể rút gọn và có ít nhất hai biến). Chiến lược này được mô tả bởi một danh sách các cặp (F,S), trong đó F là một mảnh để truyền tới trạm xử lý S. Bước 3.3: Truyền tất cả các mảnh tới trạm xử lý chúng. Bước 3.4: Thực hiện MVQ’. Nếu có các truy vấn con còn lại, thuật toán quay lại bước 3 và thực hiện bước lặp tiếp theo, ngược lại thuật toán kết thúc. 2.2.2 Thuật toán R* Thuật toán : R* - QOA Input : QT : Câu truy vấn Output : strat : Chiến lược chi phí tối thiểu BEGIN For mỗi quan hệ Ri QT do begin for mỗi đường truy nhập APij to Ri do 13 Xác đinh cost(APij) endfor best_APi APij với chi phí tối thiểu ; endfor For mỗi thứ tự (Ri1,Ri2,...,Rin) với i = 1,2,...,n! Do Begin Xây dựng chiến lược (...(best APi1  Ri2)  Ri3)  ...  Rin) ; tính toán chi phí chiến lược ; endfor strat chiến lược với chi phí tối thiểu ; For mỗi trạm k chứa một quan hệ liên quan trong QT do Begin LSk chiến lược cục bộ (strategy, k); Send(LSk, site k) { mỗi chiến lược cục bộ được tối ưu hoá tại trạm k} Endfor END. {R* - QOA} Thuật toán này được diễn giải như sau: Bộ tối ưu hoá phải chọn thứ tự kết nối, đường truy cập vào mỗi mảnh thẳng (chẳng hạn chỉ mục nhóm, quét tuần tự,...). Các quyết định này dựa trên các thống kê và thông tin đường truy nhập 2.2.3 Thuật toán SDD -1 Thuật toán SDD – 1 – QOA 14 Input : QG : Đồ thị truy vấn với n quan hệ, các thống kê của mỗi quan hệ Output : ES : Chiến lược thực hiện BEGIN ES local- operations(QG); Sửa đổi các thống kê để phản ánh kết quả của xử lý địa phương ; BS {Tập các phép nửa kết nối có lợi }; For mỗi phép nửa kết nối SJ trong QG do If cost(SJ) < benefit(SJ) then BS BS SJ; End-if End-for While BS do {Chọn các phép kết nối có lợi} Begin SJ most_benefit(BS) {SJ: semijoin có benefit_cost lớn nhất} BS BS – SJ; {Loại SJ khỏi BS} ES ES + SJ; Sửa đổi các thống kê để phản ánh kết quả của SJ thêm vào; BS BS – các phép nửa kết nối không có lợi; BS BS Các phép nửa kết nối có lợi mới; End-while 15 {chọn trạm thực hiện} AS(ES) chọn trạm i mà i chứa số lượng dữ liệu lớn nhất sau tất cả các phép toán cục bộ; ES ES sự truyền của các quan hệ trung gian tới AS(ES); {Tối ưu hoá sau} For mỗi quan hệ Ri tại AS(ES) do For mỗi phép nửa kết nối SJ của Ri và Rj do If cost(ES) > cost(ES – SJ) then ES ES – SJ; End-if End-for End-for End. {SDD -1- QOA}  Giai đoạn khởi đầu: sinh ra một tập những phép nửa kết nối có lợi (BS), vào một chiến lược thực thi(ES) bao gồm các xử lý địa phương.  Giai đoạn tiếp theo: Lặp lại lựa chọn ra các phép nửa kết nối có lợi (SJi) từ BS, sửa đổi các thống kê cơ sở dữ liệu và BS. Sự sửa đổi ảnh hưởng đến các thống kê của quan hệ R liên quan trong SJi và phép nửa kết nối còn lại trong BS mà sử dụng quan hệ R. Vòng lặp kết thúc khi tất cả các phép nửa kết nối được thêm vào ES sẽ là thứ tự thực thi của chúng. 16  Giai đoạn chọn các trạm thực hiện: Với mỗi trạm đề cử đánh giá chi phí truyền tất cả dữ liệu được yêu cầu tới nó và chọn trạm có chi phí nhỏ nhất.  Giai đoạn tối ưu hoá sau: Loại bỏ những phép kết nối trong chiến lược thực thi chỉ ảnh hưởng đến quan hệ được lưu trữ tại trạm thực hiện. 2.3 Kết luận chương - Sự phân rã : Dịch một câu truy vấn được diễn đạt trong một ngôn ngữ bậc cao kiểu SQL thành một câu truy vấn tương đương diễn đạt trong một biến thanis của đại số quan hệ. - Sự cục bộ hoá: Là phép biến đổi theo lược đồ sắp đặt một câu truy vấn phân tán thành một câu truy vấn tương đương được diễn đạt trên các mảnh. - Việc thực hiện thao tác của câu truy vấn đã được tối ưu hoá để thu được kết quả. 17 CHƯƠNG 3 : ỨNG DỤNG 3.1 Giới thiệu chương 3.2 Nội dung 3.2.1 Giới thiệu công ty TNHH HOMETECH 3.2.2 Cơ sở dữ liệu hàng hóa tập trung của công ty TNHH HOMETECH Table : InternetSales Tên cột Kiểu dữ liệu Giải thích ProductKey Int Khóa ngoại(bảng Product) CustomerKey Int Khóa ngoại SalesOrderNumber Nvarchar(20) Mã đơn đặt hang OrderQuantity Smallint Chất lượng yêu cầu UnitPrice Money Giá trên 1 đơn vị sản phẩm DiscountAmount Float Lượng giảm giá ProductStandardCosst Money Giá chuẩn của sản phẩm TotalProductCost Money Tổng giá trị của phẩm 18 Table : Geography Tên cột Kiểu dữ liệu Giải thích GeographyKey Int Khóa chính StateProvinceCode Nvarchar(3) Mã thành phố StareProvinceName Nvarchar(50) Tên tỉnh, thành phố CountryRegionName Nvarchar(50) Tên vùng PostalCode Nvarchar(15) Mã vùng quốc tế Table : Product Tên cột Kiểu dữ liệu Giải thích ProductKey Int Khóa chính ProductAlternateKey Nvarchar(25) Mã sản phẩm EnglishProductName Nvarchar(50) Tên sản phẩm StandardCost Money Giá chuẩn Color Nvarchar(15) Màu sắc SafetyStockLevel Smallint Mức độ lưu trữ hang ListPrice Money Giá ghi trên bao bì Ze Nvarchar(50) Kích thước Eight Float Cân nặng EnglishDescription Nvarchar(400) Ghi chú thêm StartDate Datetime Ngày nhập EndDate Datetime Ngày kết thúc 19 Table : Customer Tên cột Kiểu dữ liệu Giải thích CustomerKey Int Khóa chính GeographyKey Int Khóa ngoại FirstName Nvarchar(50) Tên MiddleName Nvarchar(50) Tên đệm LastName Nvarchar(50) Tên họ BirthDate Datetime Ngày sinh MaritalStatus Nchar(1) Tình trạng hôn nhân Gender Nvarchar(1) Giới tính EmailAddress Nvarchar(50) Địa chỉ Email AddressLine1 Nvarchar(120) Địa chỉ 1 Phone Nvarchar(20) Điện thoại DateFirstPurchase Datetime Ngày đầu tiên mua hàng 3.2.3 Phân mảnh cơ sở dữ liệu hàng hóa của công ty TNHH HomeTech 20 3.2.4 Ứng dụng thuật toán INGRES để giải quyết bài toán truy vấn cơ sở dữ liệu hàng hóa đã được phân mảnh Các bảng dữ liệu gồm có Customer, Geography, InternetSales, Product. Giao diện chính :  Giao diện kết nối Truy vấn với câu hỏi như sau : Select Customer.GeographyKey, Customer.FirstName, InternetSales.ProductKey, InternetSales.TotalProductCost from Customer, InternetSales Where InternetSales.CustomerKey = Customer.CustomerKey - Thời gian thực hiện là : 0,0930054s - Số lượng bản ghi là : 2 21 Truy vấn với câu truy vấn sau : Select Customer.GeographyKey, Customer.FirstName, InternetSales.ProductKey, InternetSales.TotalProductCost, Product.EnglishProductName From Customer, InternetSales, Product Where internetSales.CustomerKey = Customer.CustomerKey And Product.ProductKey = InternetSales.ProductKey and Customer.GeographyKey = 1 - Thời gian thực hiện là : 0,005s - Số lượng bản ghi là : 2 22 3.3 Kết luận chương Đề tài đã cài đặt thuật toán INGRES phân tán để xử lý phân tán câu truy vấn và lựa chọn được phương án xử lý câu truy vấn phân tán với chi phí nhỏ nhất từ các trạm. Ứng dụng cho phép thực hiện: - Thực hiện truy vấn trên từng máy trạm - Cho phép thực hiện các câu truy vấn đơn giản phân tán trên các máy trạm thực hiện cài đặt với thuật toán INGRES phân tán. Hiện tại đề tài chỉ thực hiện các câu truy vấn đơn giản chưa thực hiện được các câu truy vấn phân tán lồng nhau. Quá trình tích hợp dữ liệu có được từ các máy trạm hiện tại chưa được tối ưu nên thời gian thực hiện các câu truy vấn phân tán chưa nhanh. Do vậy cần được sự giúp đỡ của các thầy, các cô để có thể hoàn thiện hơn nữa trong tương lai. 23 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI 1. Kết luận Việc lựa chọn các giải pháp khả thi để thực hiện phân tán cơ sở dữ liệu sao cho phù hợp với yêu càu thực tế là một bước quan trọng khởi đầu khi xây dựng một hệ phân tán. Một giải pháp phân tán dữ liệu phù hợp sẽ làm tăng tốc độ xử lý dữ liệu và mang lại hiệu quả kinh tế cao. Trên mô hình thực tế và các lý thuyết về cơ sở dữ liệu phân tán thì việc tìm hiểu các biện pháp tối ưu hóa các truy vấn là một vấn đề hết sức cần thiết. Luận văn đã phần nào đáp ứng được nhu cầu đó. 2. Hướng phát triển của đề tài Phân tích sâu sắc hơn về các thuật toán INGRES phân tán, R*,SDD-1 để có thể cho một đánh giá về mức độ phức tạp của các thuật toán đó và khuyến cáo trong trường hợp nào nên dùng thuật toán nào sẽ hiệu quả. 24 TÀI LIỆU THAM KHẢO [1]. Lê Huy Thập, Cơ sở lý thuyết song song, NXB THÔNG TIN VÀ TRUYỀN THÔNG, 2010, 300 p [2]. Lê Huy Thập, Giáo trình Kỹ thuất lập trình, Tập 1, NXB Khoa học tự nhiên và công nghệ, Hà Nội 10 năm 2008, 298 p. [3]. Robert Sedgewick, Cẩm nang thuật toán Vol.1 and vol.2, NXB Khoa học và Kỹ thuật, 2001. [4]. M.Tamer Ozsu, Patrick Valduriez. Nguyên lý các hệ cơ dữ liệu phân tán. Trần Đức Quang biên dịch. NXB Thống kê, 1999 [5]. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Khoa học và Kỹ thuật, 1996 [6]. Phạm Thế Quế(2009), “Giáo trình Cơ sở dữ liệu phân tán ”, NXB Thông tin và truyền thông [7]. Nguyễn Bá Tường (2005), “Nhập môn cơ sở dữ liệu phân tán”, NXB khoa học kỹ thuật [8]. Seyed H. Roo, Parallel processing and Parallel Algorithms, Theory and Coputation, Springer 1999 [9]. Japan Information Processing Development Corporation, Central Academy of Information Technology, Internal Design And Programming, 1978