Tối ưu hóa truy vấn trong các cơ sở dữ liệu phân tán

+ ConstructAntSolution: Một tập m con kiến nhân tạo xây dựng giải pháp từ các thành phần của một tập hữu hạn các giải pháp có sẵn. Ban đầu tập này rỗng.

+ ApplyLocalSearch: Khi các giải pháp đã được xây dựng và trước khi cập nhật pheromone, chức năng này sẽ cải thiện các giải pháp thu được bởi các con kiến thông qua tìm kiếm cục bộ. Bước này không bắt buộc.

+ UpdatePheromones: Nó làm tăng giá trị pheromone gắn liền với giải pháp tốt và làm giảm với các giải pháp xấu. Điều này đạt được bằng:

+ Giảm tất cả các giá trị pheromone qua việc bốc hơi pheromone

+ Tăng mức pheromone với tập các giải pháp tốt được chọn.

ACO được thiết kế và phát triển đặc biệt để giải quyết vấn đề liên tục của tối ưu tổ hợp (tối ưu hóa kết nối). Số lượng quan hệ trong một truy vấn càng tăng thì sử dụng càng nhiều bộ nhớ và nhiều xử lý. Hệ quản trị cơ sở dữ liệu phân tán hiện đang được sử dụng như một hệ quản trị cơ sở dữ liệu chuẩn trong tất cả các ứng dụng thương mại bao gồm dữ liệu ở các trạm khác nhau. Hành vi đánh dấu đường đi của loài kiến được áp dụng để hướng những con kiến đến các khu vực chưa được khám phá trong không gian tìm kiếm và thăm tất cả các node mà không biết hình dạng đồ họa của các giải pháp tối ưu được tạo ra trong truy vấn CSDL phân tán. Kiến tính toán thời gian chạy của các kế hoạch thực thi của truy vấn được cung cấp và đưa ra kết quả tối ưu, nhanh chóng, hiệu năng cao với chi phí hiệu quả.

 Quy hoạch động (DP)[6]

Quy hoạch động là một thuật toán tối ưu hóa truy vấn nổi tiếng nhất trong hệ quản trị cơ sở dữ liệu. Quy hoạch động hoạt động theo cách từ dưới lên và xây dựng tất cả các kế hoạch con có thể. Giải pháp tối ưu cho bất kỳ kế hoạch con nào cũng được tính toán duy nhất một lần và không được tính lại. Đầu tiên, thuật toán xây dựng các kế hoạch truy cập cho mọi quan hệ trong câu truy vấn và liệt kê tất cả các kế hoạch có hai kết nối trong giai đoạn 2. Quy hoạch động tiếp tục cho đến khi nó đã liệt kê tất cả các kế hoạch n kết nối. Một kế hoạch hiệu quả có thể tỉa các kế hoạch khác với cùng kết quả đầu ra. Quy hoạch động sẽ liệt kê (A B) và

(B A) là hai kế hoạch thay thế nhưng chỉ có kế hoạch tốt hơn trong hai được giữ lại sau khi cắt tỉa. Các kế hoạch thực thi được trừu tượng hóa trong PT (Processing Trees). Đầu vào của các vấn đề tối ưu hóa được đưa ra như một đồ thị truy vấn. Đồ thị truy vấn này bao gồm tất cả các quan hệ được kết nối như là các nút lá. PT là một cây nhị phân đơn giản. Lá tương ứng với các quan hệ cơ bản và các nút tương ứng bên trong tham gia các phép kết nối. Các cạnh thể hiện luồng của kết quả thành phần từ nút lá về gốc của cây. Mỗi kế hoạch sẽ có một chi phí thực hiện. Mục đích của tối ưu hóa là tìm kế hoạch với chi phí thấp nhất có thể. Nếu quan hệ trong của mỗi kết nối là một quan hệ cơ bản, PT đc gọi là left-deep tree. Sẽ có n! cách để phân bổ n quan hệ cơ bản tới các lá của loại PT này. Nếu ko có hạn chế về PT thì nó được gọi là bushy tree. Trong nghiên cứu này, sẽ sử dụng left-deep tree.

Mô hình chi phí dựa trên tổng thời gian xử lý (CPU time + I/O time) được sử dụng. Chi phí của một kế hoạch được tính toán từ dưới lên. Mức đầu tiên bao gồm kết nối 2 chiều (2-way join). Tất cả các cặp có thể của n quan hệ được đánh giá cho tất cả các trạm. Nếu hai quan hệ ở trên cùng một trạm, chi phí chỉ bao gồm CPU+ I/O để thực hiện phép kết nối bằng sử dụng thuật toán kết nối nested-loop. Nếu chỉ một trong các quan hệ, gọi là A ở trạm kết nối, chi phí tổng là chi phí truy cập B từ trạm của nó, chi phí chuyển B tới trạm kết nối thông qua mạng truyền thông, chi phí kết nối các bộ của quan hệ A với các bộ của quan hệ B và ghi kết quả các bộ (A,B) được kết nối trên ổ đĩa cục bộ. Nếu không có quan hệ nào được lưu trữ ở trạm nối, tổng chi phí là chi phí quét cả A và B, chuyển chúng qua mạng truyền thông, thực hiện phép kết nối và ghi kết quả lên ổ đĩa. Đối với các mức trên của PT, các kết quả kết nối trung gian được coi là bảng cơ sở.

 Kết hợp thuật toán tối ưu đàn kiến và quy hoạch động để tối ưu hóa truy vấn trong cơ sở dữ liệu phân tán [6].

Cơ chế phản hồi tích cực và tính toán phân tán của ACO làm cho nó rất mạnh. ACO có khả năng xử lý song song và tìm kiếm toàn cầu, có khả năng phân tán thấp và tốc độ hội tụ cao. ACO có một số hạn chế như sự hình thành ban đầu do ACO

không có cách bắt đầu một cách có hệ thống. Tốc độ hội tụ của ACO thấp ở giai đoạn đầu do lượng pheromone trên các đường đi khác nhau rất ít nhưng tốc độ hội tụ tăng đối với câu trả lời tối ưu vì cơ chế phản hồi tích cực. Từ đó, sự kết hợp của ACO với các thuật toán khác như quy hoạch động, thuật toán di truyền và thuật toán tối ưu hóa bầy đàn được đề xuất để cung cấp kết quả tốt hơn trong xử lý truy vấn CSDL.

Khi kết hợp với quy hoạch động, chúng ta mô phỏng các hoạt động của kiến trên đồ thị của PT (Processing Trees). Mỗi quá trình tính toán thời gian chạy của một kế hoạch thực hiện sẽ được coi là một con kiến trong thuật toán. Các giải pháp đại diện cho thức ăn. Kiến có được thức ăn càng sớm thì lượng pheromone chúng tiết ra trên đường đi của giải pháp càng nhiều. Càng cần nhiều thời gian cho một con kiến đi theo đường này thì thời gian bay hơi càng nhiều. Kiến kiếm ăn liên tục tìm kiếm kế hoạch thực hiện tốt hơn. Các đường đi là những lựa chọn thay thế tổ hợp cho các kế hoạch của quy hoạch động ở mỗi mức. Nếu có 5 trạm trong phép kết nối của (A B C), sẽ có 5 đường đi khác nhau. A B là một trong các truy vấn con trong kế hoạch này. Với 5 trạm, chúng ta phải kiểm tra thời gian trả lời của từng trạm. Nếu có thể tìm ra giải pháp tối ưu ở trạm 2 thì tăng pheromone của nó trong khi các giải pháp khác của (A B) bị giảm pheromone do bị bay hơi. Thuật toán sử dụng một tham số giới hạn không gian tìm kiếm (SSL-search space limit) để kiểm soát độ phức tạp thời gian và không gian của thuật toán. Không gian tìm kiếm sẽ được thu gọn bằng cách sử dụng pheromone của mỗi kế hoạch con. Nếu ko có quá trình thu gọn (cắt tỉa) này thì DP-ACO sẽ hoạt động giống quy hoạch động. Tăng giá trị SSL sẽ làm tăng theo cấp số nhân yêu cầu về thời gian và không gian của thuật toán. Pheromone của mỗi đường được đánh giá theo phương trình:

( ) (∑ ( ) ())

( )

Đường đi quyết định có thể được tính toán theo công thức sau:

∑

l ϵ subsolutions

Trong đó pkij là xác suất dịch chuyển của con kiến thứ k chuyển từ giải pháp con thứ i sang giải pháp con thứ j, l là một thành phần của các giải pháp con. Các giải pháp con này được sắp đặt như câu lệnh SQL, α và β kiểm soát sự quan trọng tương đối của pheromone τij với các thông tin heuristic ηij.

Các giải pháp con cho mỗi kết nối đa chiều được tính toán và pheromone

được cập nhật phụ thuộc vào lực lượng của các quan hệ. Lượng tỉa được kiểm soát bởi các tham số SSL.

2.5. Kết luận chương

Chương này đã trình bày những vấn đề cơ bản về xử lý câu truy vấn, các thành phần chính của tối ưu hóa truy vấn, bao gồm không gian tìm kiếm, mô hình chi phí và chiến lược tìm kiếm; đã minh họa việc sử dụng các kỹ thuật kết nối và nửa kết nối trong các thuật toán tối ưu cơ bản như D-INGRES, System R*, SDD-1, DP-ACO. Mỗi phương pháp tối ưu đều có ưu điểm, nhược điểm của nó. Phương pháp tối ưu phân tán tĩnh, động có ưu nhược điểm giống như trong hệ thống tập trung, phương pháp tối ưu dựa trên phép nửa kết nối sử dụng tốt nhất với mạng chậm, phương pháp hỗn hợp là tốt nhất trong môi trường động ngày nay vì nó trì hoãn các quyết định quan trọng như lựa chọn sao chép và phân phối các truy vấn con đến các trạm tại thời điểm khởi động truy vấn. Vì vậy, nó có thể tăng tính sẵn sàng và cân bằng tải của hệ thống tốt hơn.

Chương này tập trung nghiên cứu truy vấn nối vì truy vấn nối là các truy vấn thường xuyên nhất trong môi trường quan hệ và chúng đã được nghiên cứu rộng rãi. Tuy nhiên, việc tối ưu hóa truy vấn chung chứa phép kết nối, phép hợp và hàm tính tổng là vấn đề khó hơn. Phân tán các phép hợp trên các nối là phương pháp

đơn giản và tốt do truy vấn có thể được giảm như hợp của các truy vấn nối con được tối ưu riêng lẻ. Phép hợp cũng thường được sử dụng trong hệ quản trị cơ sở dữ liệu phân tán vì chúng cho phép cục bộ hóa các quan hệ được phân mảnh ngang.

CHƯƠNG 3.

CÀI ĐẶT THUẬT TOÁN TỐI ƯU HÓA TRUY VẤN PHÂN TÁN

3.1. Xác định bài toán

Trong quản lý bán hàng thì một khách hàng có thể mua một hay nhiều sản phẩm, mua một lần hay nhiều lần. Do đó, cần có phần mềm để quản lý việc bán hàng. Vì vậy khi thiết kế cơ sở dữ liệu sẽ bao gồm các thông tin về sản phẩm (mã sản phẩm, tên sản phẩm, màu sắc, kích cỡ, trọng lượng, giá, ngày nhập,…) và thông tin về khách hàng (tên, ngày sinh, địa chỉ, điện thoại,…) và thông tin về hàng hóa của khách hàng mỗi lần mua (mã đơn hàng, sản phẩm, số lượng, đơn giá, tổng tiền hóa đơn,…). Trong phạm vi luận văn, tôi sẽ demo một phần cơ sở dữ liệu gồm các bảng sau:

Table: Geography

Tên cột	Kiểu dữ liệu	Giải thích
GeographyKey	Int	Khóa chính
City	nvarchar(30)	Tỉnh, thành phố
StateProvinceCode	nvarchar(3)	Mã thành phố
StateProvinceName	nvarchar(50)	Tên tỉnh, thành phố
CountryRegionCode	nvarchar(3)	Mã vùng
EnglishCountryRegionName	nvarchar(50)	Tên vùng
PostalCode	nvarchar(15)	Mã vùng quốc tế

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 (bảng Customer)
SalesOrderNumber	nvarchar(20)	Mã đặt đơn hàng
OrderQuantity	Smallint	Chất lượng yêu cầu
UnitPrice	Money	Giá trên một đơn vị sản phẩm
Discount Amount	Float	Lượng giảm giá
ProductStandardCost	Money	Giá chuẩn của sản phẩm
TotalProductCost	Money	Tổng giá trị của sản phẩm

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 (bảng Geography)
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
EmaiAddress	nvarchar(50)	Địa chỉ mail
TotalChildren	Tinyint	Tổng số con
NumberCarsOwned	Tinyint	Số xe ô tô sở hữu
AddressLine1	nvarchar(120)	Địa chỉ 1
AddressLine2	nvarchar(120)	Địa chỉ 2
Phone	nvarchar(20)	Điện thoại
DateFirstPurchase	Datetime	Ngày đầu tiên mua hàng
CommuteDistance	nvarchar(15)	Khoảng cách

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
EnglichsProductName	nvarchar(50)	Tên sản phẩm
SandardCost	Money	Giá chuẩn
Color	nvarchar(15)	Màu sắc
SafetyStockLevel	Smallint	Mức độ lưu trữ hàng
ListPrice	Money	Giá ghi trên bao bì
Ze	nvarchar(50)	Kích thước
Weight	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
Status	nvarchar(7)	Trạng thái