Đại số quan hệ để tối ưu hóa truy vấn
Khi một truy vấn được đặt, trước tiên nó được quét, phân tích cú pháp và xác thực. Sau đó, một đại diện nội bộ của truy vấn được tạo ra, chẳng hạn như cây truy vấn hoặc biểu đồ truy vấn. Sau đó, các chiến lược thực thi thay thế được nghĩ ra để lấy kết quả từ các bảng cơ sở dữ liệu. Quá trình chọn chiến lược thực thi thích hợp nhất để xử lý truy vấn được gọi là tối ưu hóa truy vấn.
Các vấn đề về tối ưu hóa truy vấn trong DDBMS
Trong DDBMS, tối ưu hóa truy vấn là một nhiệm vụ quan trọng. Độ phức tạp cao vì số lượng các chiến lược thay thế có thể tăng theo cấp số nhân do các yếu tố sau:
- Sự hiện diện của một số mảnh vỡ.
- Phân phối các phân đoạn hoặc bảng trên các trang web khác nhau.
- Tốc độ của các liên kết truyền thông.
- Chênh lệch về khả năng xử lý cục bộ.
Do đó, trong một hệ thống phân tán, mục tiêu thường là tìm chiến lược thực thi tốt để xử lý truy vấn hơn là chiến lược tốt nhất. Thời gian để thực hiện một truy vấn là tổng thời gian sau:
- Đã đến lúc giao tiếp các truy vấn tới cơ sở dữ liệu.
- Thời gian để thực thi các đoạn truy vấn cục bộ.
- Thời gian để tập hợp dữ liệu từ các trang web khác nhau.
- Thời gian hiển thị kết quả ra ứng dụng.
Xử lý truy vấn
Xử lý truy vấn là một tập hợp tất cả các hoạt động bắt đầu từ vị trí đặt truy vấn đến hiển thị kết quả của truy vấn. Các bước được thể hiện trong sơ đồ sau:
Đại số quan hệ
Đại số quan hệ xác định tập hợp các hoạt động cơ bản của mô hình cơ sở dữ liệu quan hệ. Một chuỗi các phép toán đại số quan hệ tạo thành một biểu thức đại số quan hệ. Kết quả của biểu thức này đại diện cho kết quả của một truy vấn cơ sở dữ liệu.
Các hoạt động cơ bản là -
- Projection
- Selection
- Union
- Intersection
- Minus
- Join
Phép chiếu
Phép chiếu hiển thị một tập hợp con các trường của bảng. Điều này tạo ra một phân vùng dọc của bảng.
Syntax in Relational Algebra
$$ \ pi _ {<{AttributeList}>} {(<{Tên bảng}>)} $$
Ví dụ, chúng ta hãy xem xét cơ sở dữ liệu Sinh viên sau:
| Roll_No | Name | Course | Semester | Gender |
| 2 | Amit Prasad | BCA | 1 | Nam giới |
| 4 | Varsha Tiwari | BCA | 1 | Giống cái |
| 5 | Asif Ali | MCA | 2 | Nam giới |
| 6 | Joe Wallace | MCA | 1 | Nam giới |
| số 8 | Shivani Iyengar | BCA | 1 | Giống cái |
Nếu chúng ta muốn hiển thị tên và khóa học của tất cả sinh viên, chúng ta sẽ sử dụng biểu thức đại số quan hệ sau:
$$ \ pi_ {Name, Course} {(STUDENT)} $$
Lựa chọn
Phép toán lựa chọn hiển thị một tập hợp con các bộ giá trị của bảng thỏa mãn các điều kiện nhất định. Điều này tạo ra một phân vùng ngang của bảng.
Syntax in Relational Algebra
$$ \ sigma _ {<{Điều kiện}>} {(<{Tên bảng}>)} $$
Ví dụ, trong bảng Sinh viên, nếu chúng ta muốn hiển thị chi tiết của tất cả sinh viên đã chọn tham gia khóa học MCA, chúng ta sẽ sử dụng biểu thức đại số quan hệ sau:
$$ \ sigma_ {Course} = {\ small "BCA"} ^ {(STUDENT)} $$
Sự kết hợp của các hoạt động chiếu và lựa chọn
Đối với hầu hết các truy vấn, chúng ta cần kết hợp các thao tác chiếu và lựa chọn. Có hai cách để viết các biểu thức này:
- Sử dụng trình tự các phép chiếu và lựa chọn.
- Sử dụng thao tác đổi tên để tạo kết quả trung gian.
Ví dụ: để hiển thị tên của tất cả các sinh viên nữ của khóa học BCA -
- Biểu thức đại số quan hệ sử dụng trình tự các phép chiếu và phép chọn
$$ \ pi_ {Name} (\ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)}) $$
- Biểu thức đại số quan hệ sử dụng thao tác đổi tên để tạo kết quả trung gian
$$ FemaleBCAStudent \ leftarrow \ sigma_ {Gender = \ small "Female" AND \: Course = \ small "BCA"} {(STUDENT)} $$
$$ Kết quả \ leftarrow \ pi_ {Name} {(FemaleBCAStudent)} $$
liên hiệp
Nếu P là kết quả của một phép toán và Q là kết quả của một phép toán khác, thì hợp của P và Q ($ p \ cup Q $) là tập hợp tất cả các bộ giá trị nằm trong P hoặc trong Q hoặc trong cả hai không trùng lặp .
Ví dụ: để hiển thị tất cả học sinh đang ở Học kỳ 1 hoặc đang tham gia khóa học BCA -
$$ Sem1Student \ leftarrow \ sigma_ {Semester = 1} {(STUDENT)} $$
$$ BCAStudent \ leftarrow \ sigma_ {Course = \ small "BCA"} {(STUDENT)} $$
$$ Kết quả \ leftarrow Sem1Student \ cup BCAStudent $$
Ngã tư
Nếu P là kết quả của một phép toán và Q là kết quả của một phép toán khác, thì giao của P và Q ($ p \ cap Q $) là tập hợp tất cả các bộ giá trị cả P và Q.
Ví dụ, với hai lược đồ sau:
EMPLOYEE
| EmpID | Tên | Tp. | Phòng ban | Tiền lương |
PROJECT
| PId | Tp. | Phòng ban | Trạng thái |
Để hiển thị tên của tất cả các thành phố nơi có dự án và cả nhân viên cư trú -
$$ CityEmp \ leftarrow \ pi_ {City} {(EMPLOYEE)} $$
$$ CityProject \ leftarrow \ pi_ {City} {(PROJECT)} $$
$$ Kết quả \ leftarrow CityEmp \ cap CityProject $$
Dấu trừ
Nếu P là kết quả của một phép toán và Q là kết quả của một phép toán khác thì P - Q là tập hợp tất cả các bộ giá trị thuộc P và không thuộc Q.
Ví dụ: để liệt kê tất cả các phòng ban không có dự án đang thực hiện (dự án có trạng thái = đang tiếp tục) -
$$ AllDept \ leftarrow \ pi_ {Department} {(EMPLOYEE)} $$
$$ ProjectDept \ leftarrow \ pi_ {Department} (\ sigma_ {Trạng thái = \ small "đang diễn ra"} {(PROJECT)}) $$
$$ Result \ leftarrow AllDept - ProjectDept $$
Tham gia
Phép toán tham gia kết hợp các bộ giá trị liên quan của hai bảng khác nhau (kết quả của các truy vấn) thành một bảng duy nhất.
Ví dụ: hãy xem xét hai lược đồ, Khách hàng và Chi nhánh trong cơ sở dữ liệu Ngân hàng như sau:
CUSTOMER
| CustID | AccNo | TypeOfAc | BranchID | DateOfOpening |
BRANCH
| BranchID | Tên chi nhánh | IFSCcode | Địa chỉ |
Để liệt kê chi tiết nhân viên cùng với chi tiết chi nhánh -
$$ Kết quả \ leftarrow CUSTOMER \ bowtie_ {Customer.BranchID = Branch.BranchID} {BRANCH} $$
Dịch các truy vấn SQL thành Đại số quan hệ
Các truy vấn SQL được dịch thành các biểu thức đại số quan hệ tương đương trước khi tối ưu hóa. Lúc đầu, một truy vấn được phân tách thành các khối truy vấn nhỏ hơn. Các khối này được dịch sang các biểu thức đại số quan hệ tương đương. Tối ưu hóa bao gồm tối ưu hóa từng khối và sau đó tối ưu hóa toàn bộ truy vấn.
Ví dụ
Chúng ta hãy xem xét các lược đồ sau:
NHÂN VIÊN
| EmpID | Tên | Tp. | Phòng ban | Tiền lương |
DỰ ÁN
| PId | Tp. | Phòng ban | Trạng thái |
LÀM
| EmpID | PID | Giờ |
ví dụ 1
Để hiển thị chi tiết của tất cả nhân viên kiếm được mức lương ÍT hơn mức lương trung bình, chúng tôi viết truy vấn SQL:
SELECT * FROM EMPLOYEE
WHERE SALARY < ( SELECT AVERAGE(SALARY) FROM EMPLOYEE ) ;Truy vấn này chứa một truy vấn con lồng nhau. Vì vậy, điều này có thể được chia thành hai khối.
Khối bên trong là -
SELECT AVERAGE(SALARY)FROM EMPLOYEE ;Nếu kết quả của truy vấn này là AvgSal, thì khối bên ngoài là -
SELECT * FROM EMPLOYEE WHERE SALARY < AvgSal;Biểu thức đại số quan hệ cho khối bên trong -
$$ AvgSal \ leftarrow \ Im_ {AVERAGE (Lương)} {EMPLOYEE} $$
Biểu thức đại số quan hệ cho khối bên ngoài -
$$ \ sigma_ {Lương <{AvgSal}>} {EMPLOYEE} $$
Ví dụ 2
Để hiển thị ID dự án và trạng thái của tất cả các dự án của nhân viên 'Arun Kumar', chúng tôi viết truy vấn SQL:
SELECT PID, STATUS FROM PROJECT
WHERE PID = ( SELECT FROM WORKS WHERE EMPID = ( SELECT EMPID FROM EMPLOYEE
WHERE NAME = 'ARUN KUMAR'));Truy vấn này chứa hai truy vấn con lồng nhau. Do đó, có thể được chia thành ba khối, như sau:
SELECT EMPID FROM EMPLOYEE WHERE NAME = 'ARUN KUMAR';
SELECT PID FROM WORKS WHERE EMPID = ArunEmpID;
SELECT PID, STATUS FROM PROJECT WHERE PID = ArunPID;(Ở đây ArunEmpID và ArunPID là kết quả của các truy vấn bên trong)
Biểu thức đại số quan hệ cho ba khối là:
$$ ArunEmpID \ leftarrow \ pi_ {EmpID} (\ sigma_ {Name = \ small "Arun Kumar"} {(EMPLOYEE)}) $$
$$ ArunPID \ leftarrow \ pi_ {PID} (\ sigma_ {EmpID = \ small "ArunEmpID"} {(WORKS)}) $$
$$ Kết quả \ leftarrow \ pi_ {PID, Trạng thái} (\ sigma_ {PID = \ small "ArunPID"} {(PROJECT)}) $$
Tính toán các toán tử đại số quan hệ
Việc tính toán các toán tử đại số quan hệ có thể được thực hiện theo nhiều cách khác nhau và mỗi cách thay thế được gọi là access path.
Phương án tính toán phụ thuộc vào ba yếu tố chính:
- Loại nhà điều hành
- Bộ nhớ khả dụng
- Cấu trúc đĩa
Thời gian để thực hiện một phép toán đại số quan hệ là tổng của:
- Đã đến lúc xử lý các bộ giá trị.
- Đã đến lúc tìm nạp các bộ giá trị của bảng từ đĩa vào bộ nhớ.
Vì thời gian để xử lý một tuple nhỏ hơn rất nhiều so với thời gian tìm nạp tuple từ bộ lưu trữ, đặc biệt là trong hệ thống phân tán, truy cập đĩa thường được coi là thước đo để tính toán chi phí của biểu thức quan hệ.
Tính toán lựa chọn
Việc tính toán hoạt động lựa chọn phụ thuộc vào độ phức tạp của điều kiện lựa chọn và tính sẵn có của các chỉ mục trên các thuộc tính của bảng.
Sau đây là các lựa chọn thay thế tính toán tùy thuộc vào các chỉ số -
No Index- Nếu bảng không được sắp xếp và không có chỉ mục, thì quá trình lựa chọn bao gồm việc quét tất cả các khối đĩa của bảng. Mỗi khối được đưa vào bộ nhớ và mỗi bộ trong khối được kiểm tra để xem liệu nó có thỏa mãn điều kiện lựa chọn hay không. Nếu điều kiện được thỏa mãn, nó được hiển thị dưới dạng đầu ra. Đây là cách tiếp cận tốn kém nhất vì mỗi bộ được đưa vào bộ nhớ và mỗi bộ được xử lý.
B+ Tree Index- Hầu hết các hệ thống cơ sở dữ liệu được xây dựng dựa trên chỉ mục B + Tree. Nếu điều kiện lựa chọn dựa trên trường, là khóa của chỉ mục B + Tree này, thì chỉ mục này được sử dụng để truy xuất kết quả. Tuy nhiên, việc xử lý các câu lệnh lựa chọn với các điều kiện phức tạp có thể liên quan đến số lượng truy cập khối đĩa lớn hơn và trong một số trường hợp, quá trình quét hoàn toàn bảng.
Hash Index- Nếu các chỉ mục băm được sử dụng và trường khóa của nó được sử dụng trong điều kiện lựa chọn, thì việc truy xuất các bộ giá trị bằng chỉ mục băm trở thành một quá trình đơn giản. Chỉ mục băm sử dụng hàm băm để tìm địa chỉ của một thùng chứa giá trị khóa tương ứng với giá trị băm. Để tìm một giá trị khóa trong chỉ mục, hàm băm được thực thi và địa chỉ thùng được tìm thấy. Các giá trị chính trong nhóm được tìm kiếm. Nếu tìm thấy kết quả khớp, bộ giá trị thực sẽ được tải từ khối đĩa vào bộ nhớ.
Tính toán các phép nối
Khi chúng ta muốn nối hai bảng, giả sử P và Q, mỗi bộ trong P phải được so sánh với mỗi bộ trong Q để kiểm tra xem điều kiện nối có thỏa mãn hay không. Nếu điều kiện được thỏa mãn, các bộ giá trị tương ứng được nối với nhau, loại bỏ các trường trùng lặp và được nối vào quan hệ kết quả. Do đó, đây là hoạt động tốn kém nhất.
Các phương pháp phổ biến cho phép nối máy tính là:
Phương pháp tiếp cận vòng lặp lồng nhau
Đây là cách tiếp cận tham gia thông thường. Nó có thể được minh họa thông qua mã giả sau (Bảng P và Q, với các bộ giá trị tuple_p và tuple_q và thuộc tính nối a) -
For each tuple_p in P
For each tuple_q in Q
If tuple_p.a = tuple_q.a Then
Concatenate tuple_p and tuple_q and append to Result
End If
Next tuple_q
Next tuple-pPhương pháp tiếp cận sắp xếp-hợp nhất
Trong cách tiếp cận này, hai bảng được sắp xếp riêng dựa trên thuộc tính nối và sau đó các bảng đã sắp xếp được hợp nhất. Kỹ thuật sắp xếp bên ngoài được áp dụng vì số lượng bản ghi rất nhiều và không thể chứa trong bộ nhớ. Sau khi các bảng riêng lẻ được sắp xếp, mỗi bảng trong số các bảng được sắp xếp sẽ được đưa vào bộ nhớ, được hợp nhất dựa trên thuộc tính nối và các bộ giá trị đã nối sẽ được viết ra.
Phương pháp kết hợp băm
Cách tiếp cận này bao gồm hai giai đoạn: giai đoạn phân vùng và giai đoạn thăm dò. Trong giai đoạn phân vùng, các bảng P và Q được chia thành hai tập hợp các phân vùng riêng biệt. Một hàm băm chung được quyết định dựa trên. Hàm băm này được sử dụng để gán các bộ giá trị cho các phân vùng. Trong giai đoạn thăm dò, các bộ giá trị trong một phân vùng của P được so sánh với các bộ giá trị của phân vùng tương ứng của Q. Nếu chúng khớp nhau, thì chúng được viết ra.