›
›

Bài giảng Cơ sở dữ liệu 2 - Chương 5: Xử lý câu truy vấn và tối ưu hóa - Nguyễn Công Thương

ppt 26 trang phuongnguyen 5330
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cơ sở dữ liệu 2 - Chương 5: Xử lý câu truy vấn và tối ưu hóa - Nguyễn Công Thương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptbai_giang_co_so_du_lieu_2_chuong_5_xu_ly_cau_truy_van_va_toi.ppt

Nội dung text: Bài giảng Cơ sở dữ liệu 2 - Chương 5: Xử lý câu truy vấn và tối ưu hóa - Nguyễn Công Thương

  1. CƠ SỞ DỮ LIỆU 2 Giảng viên: Nguyễn Công Thương Khoa Công nghệ thông tin Đại học Sư phạm Kỹ thuật Tp. HCM
  2. Chương 5: Xử lý câu truy vấn và tối ưu hóa Giới thiệu Kế hoạch thực thi câu truy vấn Luật biến đổi câu truy vấn Tối ưu hóa câu truy vấn dựa trên đại số quan hệ Cơ sở dữ liệu 2 2
  3. Giới thiệu Khi nhận được một câu truy vấn, bộ xử lý truy vấn (query processor) sẽ kiểm tra: ◼ Cú pháp của câu truy vấn ◼ Các quan hệ (bảng) và thuộc tính mà nó truy xuất có tồn tại trong cơ sở dữ liệu hay chưa Nếu câu truy vấn thõa mãn điều kiện, bộ xử lý truy vấn sẽ tạo ra một kế hoạch thực thi cho câu truy vấn đó Cơ sở dữ liệu 2 3
  4. Cơ sở dữ liệu 2 4
  5. Kế hoạch thực thi Kế hoạch thực thi là một chuỗi các bước để thực hiện một câu truy vấn Mỗi bước trong kế hoạch thực thi tương ứng với một phép toán quan hệ cộng với các phương thức để đánh giá phép toán Cơ sở dữ liệu 2 5
  6. Kế hoạch thực thi (tt) Ví dụ: SELECT * FROM R, S, T WHERE R.A > a AND R.B = S.B AND S.C = T.C Kế hoạch thực thi có thể là: 1. Thực hiện phép chọn  A>a (R), kết quả là R1 2. Thực hiện phép kết R1  R1.B = S.B S. Kết quả là R2 3. Thực hiện phép kết R2  R2.C = T.C T Cơ sở dữ liệu 2 6
  7. Kế hoạch thực thi (tt) Một kế hoạch thực thi khác có thể là: 1.  A>a (R). Kết quả là R1 2. S  S.C = T.C T. Kết quả là R3 3. R1  R1.B = R3.B R3 Những kế hoạch thực thi khác nhau tạo ra cùng một kết quả được gọi là tương đương Những kế hoạch thực thi tương đương có chi phí rất khác nhau Cơ sở dữ liệu 2 7
  8. Chi phí thực thi câu truy vấn Chi phí thực thi câu truy vấn là tổng của chi phí I/O và chi phí CPU ◼ Chi phí I/O là chi phí của thao tác chuyển dữ liệu giữa bộ nhớ chính và bộ nhớ thứ cấp ◼ Chi phí CPU là chi phí của thao tác kết và kiểm tra điều kiện các tuple trong bộ nhớ chính Chi phí I/O là chi phí chủ yếu. Để giảm chi phí I/O → các cấu trúc đặc biệt (cây B+) Cơ sở dữ liệu 2 8
  9. Không gian tìm kiếm câu truy vấn tối ưu Số kế hoạch thực thi tương đương được xác định bởi 2 thông số: ◼ Số phép toán quan hệ trong câu truy vấn ◼ Số phương thức có thể dùng để thực thi mỗi phép toán Ví dụ: có m phép toán, mỗi phép toán có thể thực thi theo k cách → Có thể có tối đa (m!).km kế hoạch thực thi Cơ sở dữ liệu 2 9
  10. Phương pháp tối ưu hóa Có hai phương pháp: ◼ Tối ưu hóa dựa trên đại số quan hệ: sử dụng một số luật biến đổi heuristic ◼ Tối ưu hóa dựa trên việc ước lượng chi phí: với mỗi câu truy vấn, ước lượng chi phí của mỗi kế hoạch thực thi có thể → chọn kế hoạch thực thi có chi phí thấp nhất Cơ sở dữ liệu 2 10
  11. Luật biến đổi Các luật biến đổi một biểu thức đại số quan hệ thành một biểu thức khác tương đương Giả sử R, S, T là 3 quan hệ Luật 1: Phép chọn theo tầng: Giả sử C1, C2 là hai điều kiện chọn trên R, ta có: C1 and C2(R ) = C1(C2(R )) Cơ sở dữ liệu 2 11
  12. Luật biến đổi (tt) Luật 2: ◼ Nếu điều kiện C chỉ bao gồm các thuộc tính của R, ta có: C( R  S) = (C(R))  S ◼ Nếu C1 chỉ bao gồm các thuộc tính của R, C2 chỉ bao gồm các thuộc tính của S, ta có: C1 and C2(R S) = (C1(R))  (C2(S)) Cơ sở dữ liệu 2 12
  13. Luật biến đổi (tt) Luật 3: giả sử AL = {A1, A2, An, B1, B2, Bm} với A1 An R, B1 Bm S. Nếu điều kiện C ◼ chỉ bao gồm các thuộc tính trong AL: AL(R CS) = (A1, ,An(R )) C ( B1, ,Bm(S)) ◼ bao gồm thêm A’1 A’u R, B’1 B’v S AL (R C S) = AL ((A1, ,An, A’1, ,A’u (R)) C ( B1, ,Bm, B’1, ,B’v(S))) Cơ sở dữ liệu 2 13
  14. Luật biến đổi (tt) Luật 4: ◼ R C1 (SC2 T) = (R C1 S) C2 T ◼ R  (S  T) = (R  S)  T Luật 5: Thay thế phép và  bằng : ◼ C( R S) = R C S Ghi chú: thay thế phép  bằng phép thì luật 2, 3, 4 vẫn đúng. Cơ sở dữ liệu 2 14
  15. Tối ưu hóa dựa trên đại số quan hệ Chuyển câu truy vấn thành biểu thức đại số quan hệ Chuyển thành một biểu thức tương đương hiệu quả hơn sử dụng các luật heuristic Cơ sở dữ liệu 2 15
  16. Các luật biến đổi heuristic Thực hiện phép chọn càng sớm càng tốt Thay thế phép tích Decarte bằng phép kết Nếu có nhiều phép kết, thực hiện phép kết có điều kiện khắt khe trước Dùng phép chiếu để loại những thuộc tính không cần thiết trước Cơ sở dữ liệu 2 16
  17. Cây truy vấn Cây truy vấn là một cây biểu diễn biểu thức đại số quan hệ ví dụ: STUDENT(SSN, Name, Age, GPA, Address) COURSE(Course#, Title, Credit) TAKE(SSN, Course#, Grade) Cơ sở dữ liệu 2 17
  18. Cây truy vấn (tt) select Name from Student, Take, Course where GPA > 3.5 and Title = ‘Database System’ and Student.SSN = Take.SSN and Take.Course# = Course.Course# ➔ Name (GPA>3.5 and Title = ‘Database System’ and Student.SSN = Take.SSN and Take.Course#=Course.Course#(Student Take Course)) Cơ sở dữ liệu 2 18
  19. Cây truy vấn (tt)  Name  GPA > 3.5  Title = ‘Database Systems’  Student.SSN = Take.SSN  Take.Course# = Course.Course# Course Student Take Cơ sở dữ liệu 2 19
  20. Cây truy vấn (tt) Cơ sở dữ liệu 2 20
  21. Cây truy vấn (tt)  Name    Title = ‘Database System’  Take GPA > 3.5 Course Student Cơ sở dữ liệu 2 21
  22. Cây truy vấn (tt)  Name   GPA > 3.5  Take  Title = ‘Database System’ Student Course Cơ sở dữ liệu 2 22
  23. Cây truy vấn (tt)  Name   SSN, Name  Course#, SSN  Course#  GPA > 3.5 Take  Title = ‘Database System’ Student Course Cơ sở dữ liệu 2 23
  24. Kế hoạch thực thi Kế hoạch thực thi được sinh ra: 1. Course# (Title=’Database Systems’(Course)). Kết quả là T1 2. SSN, Course# (Take). Kết quả là T2. 3. T1  T2. Let T3 be the result. 4. SSN, Name (GPA>3.5 (Student)). Kết quả là T4. 5. Name (T3  T4). Cơ sở dữ liệu 2 24
  25. Tổng kết Kế hoạch thực thi Truy vấn tối ưu Cây truy vấn Luật biến đổi Cơ sở dữ liệu 2 25
  26. Questions and answers Cơ sở dữ liệu 2 26