›
›

Bài giảng Các hệ quản trị CSDL - Chương 4: Tổ chức khai thác - Nguyễn Thúy Ngọc

pdf 66 trang ngocly 3460
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Các hệ quản trị CSDL - Chương 4: Tổ chức khai thác - Nguyễn Thúy Ngọc", để 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:

  • pdfbai_giang_cac_he_quan_tri_csdl_chuong_4_to_chuc_khai_thac_ng.pdf

Nội dung text: Bài giảng Các hệ quản trị CSDL - Chương 4: Tổ chức khai thác - Nguyễn Thúy Ngọc

  1. Trường Đại học Sư phạm thành phố Hồ Chí Minh Khoa Công nghệ thông tin CÁC HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU TỔ CHỨC KHAI THÁC
  2. Mục tiêu ● Hiểu quy trình thực hiện các câu truy vấn ● Xây dựng những câu truy vấn một cách hiệu quả Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 2
  3. Tài liệu tham khảo [1] Ramez Elmasri, Shamkant B. Navathe, Fundamentals of Database Systems (ch. 19), 6th Edition. [2] Jeffrey D. Ullman, Jennifer Widom, Hector Garcia-Monlina, Database Systems: The complete Book (ch. 15, ch. 16), 2001. [3] Nguyễn An Tế, Nguyễn Tiến Dũng, Nguyễn Thúy Ngọc, Slide bài giảng Các hệ CSDL, 2011-2012 Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 3
  4. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 4
  5. 1. Quy trình thực hiện câu truy vấn Câu truy vấn biểu diễn bằng ngôn ngữ cấp cao Kết quả Runtime Database Preprocessor Processor Hình thức trung gian của truy vấn (tree, graph) Code Query Code Query Optimizer Generator Cách thực hiện Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 5
  6. 1. Quy trình thực hiện câu truy vấn (tt.) Preprocessor Scanning: xác định các từ khóa, tên thuộc tính, tên các quan hệ, Parsing: kiểm tra cú pháp ngôn ngữ, biểu diễn Parse Tree Validating: kiểm tra ngữ nghĩa: quan hệ, thuộc tính, kiểu dữ liệu Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 6
  7. 1. Quy trình thực hiện câu truy vấn (tt.) Query Optimizer lựa chọn chiến thuật thực hiện phù hợp cho việc xử lý câu truy vấn Query Code Generator phát sinh code để thực hiện kế hoạch đã được lựa chọn Runtime Database Processor biên dịch code của câu truy vấn để trả về kết quả truy vấn Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 7
  8. 1. Quy trình thực hiện câu truy vấn (tt.) SQL query Parse Query Query expression tree Select logical query plan Query Logical query plan tree Optimizer Select physical plan Physical query plan tree Execute plan Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 8
  9. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 9
  10. 2. Tiền xử lý câu truy vấn SELECT FROM WHERE IN = LIKE = Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 10
  11. Quy trình thực hiện câu truy vấn (tt.) NHANVIEN (manv, tennv, ngaysinh, phai, luong) THAMGIA (mada, manv, ngaybatdau, ngayketthuc) Liệt kê mã đề án mà nhân viên tham gia có lương >2.000.000 SELECT mada FROM THAMGIA WHERE manv IN ( SELECT manv FROM NHANVIEN WHERE luong >‘2.000.000’ Vẽ cây phân tích cú pháp (query expression tree) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 11
  12. SELECT FROM WHERE mada THAMGIA IN luong SELECT FROM WHERE > mada NHANVIEN luong 2.000.000 Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 12
  13. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 3.1 Chuyển đổi từ SQL sang ĐSQH 3.2 Các quy tắc biến đổi tương đương trong ĐSQH 4. Tối ưu hóa câu truy vấn Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 13
  14. 3.1 Chuyển đổi từ SQL sang ĐSQH ● Query block: khối truy vấn đơn vị SELECT-FROM-WHERE-GROUP BY-HAVING dùng để chuyển sang ĐSQH ● Truy vấn lồng: tách thành khối lệnh ghép thành các khối truy vấn đơn vị (query blocks) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 14
  15. 3.1 Chuyển đổi từ SQL sang ĐSQH (tt.) SELECT honv, tennv FROM NHANVIEN WHERE luong> (SELECT MAX (luong) FROM NHANVIEN WHERE maphong = 5); SELECT honv, tennv SELECT MAX (luong) FROM NHANVIEN FROM NHANVIEN WHERE luong > C WHERE maphong = 5 πhonv, tennv (σluong>C(NHANVIEN)) ℱMAX luong (σmaphong=5 (NHANVIEN)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 15
  16. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 3.1 Chuyển đổi từ SQL sang ĐSQH 3.2 Các quy tắc biến đổi tương đương trong ĐSQH 4. Tối ưu hóa câu truy vấn Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 16
  17. 3.2 Các quy tắc biến đổi – QT 1 QT1: Xử lý các toán tử AND trong điều kiện  c1ANDc2 ANDcn R  c1  c2  cn R NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong)  maphong = ‘KT’ AND phai = ‘NAM’ (NHANVIEN)   maphong = ‘KT’(  phai = ‘NAM’ (NHANVIEN)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 17
  18. 3.2 Các quy tắc biến đổi – QT 2 QT2: Thay đổi thứ tự của các phép chọn  c1  c2 R  c2  c1 R NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong)  maphong = ‘KT’( phai = ‘NAM’ (NHANVIEN))   phai = ‘NAM’( maphong = ‘KT’ (NHANVIEN)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 18
  19. 3.2 Các quy tắc biến đổi – QT 3 QT3: Xử lý các phép chiếu DS1 DS 2 DSn R  DS1 R NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) manv, honv, tennv ( manv, honv, tennv, ngaysinh (NHANVIEN))  manv, honv, tennv (NHANVIEN) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 19
  20. 3.2 Các quy tắc biến đổi – QT 4 QT4: Thay đổi thứ tự các phép chọn và phép chiếu A1,A2, ,An  c R  c A1,A2, ,An R Nếu như c  [A1 An] NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) manv, honv, tennv, phai ( phai = ‘NAM’ (NHANVIEN))  phai= ‘NAM’( manv, honv, tennv, phai (NHANVIEN)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 20
  21. 3.2 Các quy tắc biến đổi – QT 5 QT5: Tính giao hoán của phép kết và tích Descartes R C S (S C R) R x S (S x R) NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) PHONGBAN (maphong, tenphong, maql) (NHANVIEN PHONGBAN)  NV.maphong= PB.maphong (PHONGBAN NHANVIEN) NV.maphong= PB.maphong Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 21
  22. 3.2 Các quy tắc biến đổi – QT 6a QT6a: Thay đổi thứ tự giữa phép chọn và phép kết  c R S ( c (R)) S Nếu như c  R (hay c  S) NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) PHONGBAN (maphong, tenphong, maql) phai = ‘NAM’(NHANVIEN PHONGBAN)  (phai = ‘NAM’ (NHANVIEN)) PHONGBAN Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 22
  23. 3.2 Các quy tắc biến đổi – QT 6b QT6b: Phân phối giữa phép chọn và phép kết  R S ( (R)) ( (S) ) c c1 c2 Nếu c = c1 and c2, (c1 R và c2 S) NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) PHONGBAN (maphong, tenphong, maql) phai= ‘NAM’ AND tenphong= ‘Kế toán’(NHANVIEN PHONGBAN)  (phai = ‘NAM’ (NHANVIEN)) (tenphong= ‘Kế toán’ (PHONGBAN)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 23
  24. 3.2 Các quy tắc biến đổi – QT 7a QT7a: Phân phối giữa phép chiếu và phép kết R S ( (R)) ( (S))  L C A1,A2 , A3 , AN C B1,B2 , B3 , BM L = {A1, ,AN,B1, ,BM}; R (A1, ,AN); S (B1, ,BM) Với c  L NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) PHONGBAN (maphong, tenphong, maql) manv,tennv,maphong,tenphong(NHANVIEN PHONGBAN)  NV.maphong=PB.maphong ( manv, honv, maphong(NHANVIEN)) ( tenphong, maphong(PHONGBAN)) NV.maphong=PB.maphong Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 24
  25. 3.2 Các quy tắc biến đổi – QT 7b QT7b: Phân phối giữa phép chiếu và phép kết R S ( (R)) ( (S))  L C A ,A , A , A ,A A A C B ,B , B , B B B B 1 2 3 N N 1 N 2 N K 1 2 3 M M 1 M 2 M P Với c  L, R(A1, ,AN, AN+1, AN+K) S(B1, ,BM, BM+1, ,BM+P) NHANVIEN (manv, honv, tennv, ngaysinh, phai, luong, maphong) PHONGBAN (maphong, tenphong, maql) manv, tennv, tenphong (NHANVIEN PHONGBAN)  NV.maphong=PB.maphong ( manv, tennv, maphong(NHANVIEN)) ( tennv,maphong(PHONGBAN)) NV.maphong=PB.maphong Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 25
  26. 3.2 Các quy tắc biến đổi – QT 8 QT8: Giao hoán của phép hội và phép giao R  S  S  R R  S  S  R Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 26
  27. 3.2 Các quy tắc biến đổi – QT 9 QT9: Kết hợp giữa phép kết, tích Descartes, hội và giao (R  S)  T R  (S  T) Trong đó  là 1 trong các phép toán , X, ,  Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 27
  28. 3.2 Các quy tắc biến đổi – QT 10 QT 10: Phân phối của phép chọn đối với các phép toán  c (R  S) ( c (R))  ( c (S)) Nếu  là 1 trong các phép toán , , ─ Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 28
  29. 3.2 Các quy tắc biến đổi – QT 11 QT 11: Phân phối của phép chiếu đối với các phép toán Nếu  là 1 trong các phép toán , , ─ L (R  S) (L (R))  (L (S)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 29
  30. 3.2 Các quy tắc biến đổi – QT 12 QT 12: Chuyển các phép (, ) thành phép kết  c (R x S) R cS Luật De Morgan c  NOT (c1 AND c2)  NOT (c1) OR NOT (c2) c  NOT (c1 OR c2)  NOT (c1) AND NOT (c2) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 30
  31. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn 4.1 Giải thuật Heuristic 4.2 Ước lượng chi phí Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 31
  32. 4.1 Giải thuật heuristic 1. Áp dụng QT 1, tách các phép chọn liên kiện thành 1 dãy các phép chọn. 2. Áp dụng QT 2,4,6 và 10, để đẩy phép chọn xuống càng sâu càng tốt 3. Áp dụng QT 9 để tái tổ chức cây cú pháp sao cho phép chọn được thực hiện có lợi nhất (chọn ít nhất) heuristic 4. Phối hợp tích Decartes với các phép chiếu thích hợp theo sau 5. Áp dụng QT 3, 4, 7 và 11 để đẩy phép chiếu xuống càng sâu càng tốt (có thể phát sinh phép chiếu mới) 6. Tập trung các phép chọn 7. Áp dụng QT3 để loại những phép chiếu vô ích Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 32
  33. 4.1 Giải thuật heuristic (tt.) Liệt kê họ tên NHANVIEN sinh sau năm 1960 và làm dự án ‘ABC’ Ngôn ngữ SQL SELECT honv, tennv FROM NHANVIEN NV, DEAN DA, THAMGIA TG WHERE mada=‘ABC’ AND NV.manv=TG.manv AND DA.mada=TG.mada AND ngaysinh> ’31-12-1960’ Ngôn ngữ ĐSQH honv, tennv(  mada = ‘ABC’  ngaysinh > ’31-12-1960’  NV.manv=TG.manv  DA.mada=TG.mada (NHANVIEN x DEAN x THAMGIA)) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 33
  34. 4.1 Giải thuật heuristic (tt.) honv, tennv( mada = ‘ABC’  ngaysinh > ’31-12-1960’  NV.manv=TG.manv  DA.mada=TG.mada (NHANVIEN x DEAN x THAMGIA))  honv, tennv mada = ‘ABC’  ngaysinh > ’31-12-1960’ NV.manv=TG.manv x DA.maDA=TG.mada x DEAN NHANVIEN THAMGIA Cây biểu diễn biểu thức truy vấn (1) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 34
  35. 4.1 Giải thuật heuristic (tt.)  honv, tennv DA.maDA=TG.mada x NV.manv=TG.manv mada = ‘ABC’ DEAN ngaysinh > ’31-12-1960’ THAMGIA NHANVIEN Đưa phép chọn xuống sâu các nhánh (2) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 35
  36. 4.1 Giải thuật heuristic (tt.)  honv, tennv NV.manv=TG.manv x DA.maDA=TG.mada  ngaysinh > ’31-12-1960’ NHANVIEN  mada = ‘ABC’ THAMGIA DEAN Hoán vị phép chọn (3) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 36
  37. 4.1 Giải thuật heuristic (tt.)  honv, tennv NV.manv=TG.manv  DA.maDA=TG.mada ngaysinh > ’31-12-1960’ NHANVIEN  THAMGIA mada = ‘ABC’ DEAN Thay thế các phép tích Descartes và phép chọn bằng phép kết (4) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 37
  38. 4.1 Giải thuật heuristic (tt.)  honv, tennv NV.manv=TG.manv  manv  manv, honv, tennv DA.maDA=TG.mada   ngaysinh > ’31-12-1960’ mada  mada,manv NHANVIEN mada = ‘ABC’ THAMGIA DEAN Đẩy phép chiếu xuống dưới (5) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 38
  39. 4.1 Giải thuật heuristic (tt.) Ngôn ngữ ĐSQH honv,tennv(( mada(  mada = ‘ABC’ (DEAN))) ( mada, manv(THAMGIA)) DA.mada=TG.mada NV.manv=TG.manv ( manv,honv,tennv(  ngaysinh > ’31-12-1960’ (NHANVIEN)))) Ngôn ngữ SQL SELECT honv, tennv FROM (SELECT mada FROM DEAN WHERE mada = ‘ABC’) AS DA INNER JOIN (SELECT mada, manv FROM THAMGIA) AS TG ON DA.mada=TG.mada INNER JOIN (SELECT manv, honv, tennv FROM NHANVIEN WHERE ngaysinh> ’31-12-1960’ ) NV ON NV.manv=TG.manv Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 39
  40. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn 4.1 Giải thuật Heuristic 4.2 Ước lượng chi phí Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 40
  41. 4.2 Ước lượng chi phí (tt.) ● So sánh chi phí giữa những cách thực hiện câu truy vấn: chọn cách có chi phí thấp nhất Chi phí lưu trữ thứ cấp Chi phí lưu trữ Chi phí tính toán Chi phí sử dụng bộ nhớ Chi phí truyền thông Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 41
  42. 4.2 Ước lượng chi phí (tt.) •Các tham số về kích thước file NHANVIEN manv tenv phai hsl .Số mẩu tin của bảng (tuples): T(R) NV01 An Nam 1.5 .Kích thước 1 mẩu tin: S(R) NV02 Bình Nam 1.5 .Tổng số block chứa tất cả các bộ: b NV03 Dung Nữ 3 .Số mẩu tin của 1 block: bfr NV04 Duyên Nữ 2.5 .Số giá trị khác nhau của thuộc tính A (kích thước của miền giá trị): V(R,A) manv: char (20) tennv: nvarchar (50) phai: nvarchar (10) hsl (hệ số lương): double Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 42
  43. Ví dụ R A B C D A: chuỗi 20 bytes x 1 10 a B: số nguyên 4 bytes x 1 20 b C: ngày 8 bytes y 1 30 a D: chuỗi 68 bytes y 1 40 c 1 block = 1024 bytes z 1 50 d (block header: 24 bytes) T(R) = 5 V(R, A) = 3 V(R, B) = 1 S(R) = 100* V(R, C) = 5 V(R, D) = 4 B(R) = 1
  44. Bài tập ví dụ: ● Cho quan hệ R(a,b,c) – Trong đó: a,b integer 4 Bytes c string 100 Bytes Header mỗi bộ là 12 Bytes 1 Block 1024 Bytes Block Header 24 Bytes Số mẫu tin của bảng T(R)= 10 000 Tính số mẫu tin trong 1 block? Số Block cần thiết để lưu trữ 10 000 mẫu tin? Tính kích thước file tối thiểu chứa được số mẫu tin trên? Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 44
  45. Bài tập ví dụ: ● Cho quan hệ R(a,b,c) – Trong đó: a,b integer 4 Bytes c string 100 Bytes Header mỗi bộ là 12 Bytes 1 Block 1024 Bytes Block Header 24 Bytes Số mẫu tin của bảng T(R)= 10 000 Tính số mẫu tin trong 1 block? btr= 1000/120 ≈ 8 Số Block cần thiết để lưu trữ 10 000 mẫu tin? B(R)= 10 000/8= 1250 Kích thước file tối thiểu chứa được số mẫu tin trên? (1250*1024) Bytes Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 45
  46. Bài tập ví dụ: ● Cho quan hệ R(a,b,c) – Trong đó: a,b integer 4 Bytes c string 100 Bytes Header mỗi bộ là 12 Bytes 1 Block 1024 Bytes Block Header 24 Bytes Số mẫu tin của bảng T(R)= 10 000 Nếu S= + , (푅) Tính B(R) (gợi ý: 1 Tuple 116 Bytes) Nếu U= , (푅) Tính B(R) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 46
  47. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn 4.1 Giải thuật Heuristic 4.2 Ước lượng chi phí 4.2.1 Hàm chi phí cho Select 4.2.2 Hàm chi phí cho Join Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 47
  48. 4.2.1 Hàm chi phí cho Select [Ullman + 2001] ● Ước lượng W= A=x (R) (đối với điều kiện =) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 48
  49. 4.2.1 Hàm chi phí cho Select [Ullman + 2001] ● Ước lượng W= A>x (R) (đối với điều kiện >, >=, <, <=) Cách 1 Cách 2 Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 49
  50. 4.2.1 Hàm chi phí cho Select ● Ví dụ Cho R (A, B, C), tính chi phí S= A=10  B<20 (R) Với T(R)=10.000; V(R,A) = 50 Ta có: Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 50
  51. 4.2.1 Hàm chi phí cho Select (tt.) [Elmasri+2003] .Hàm tính chi phí cho Select theo phương pháp tìm kiếm Pi: Si .Chi phí truy cập block tính theo hàm Si: CSi Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 51
  52. 4.2.1 Hàm chi phí cho Select (tt.) ● S1. Tìm kiếm tuyến tính – Duyệt từng mẩu tin, và kiểm tra giá trị thuộc tính của mẩu tin đó có thỏa mãn điều kiện chọn (không nhất thiết là điều kiện =) hay không – Độ phức tạp: O(n) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 52
  53. 4.2.1 Hàm chi phí cho Select (tt.) ● S1. Tìm kiếm tuyến tính (tt.) – Đối với thuộc tính không khóa CS1a = b – Đối với điều kiện =, thuộc tính khóa CS1b = (b/2) o đặc biệt, nếu không tìm thấy mẩu tin nào CS1b = b Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 53
  54. 4.2.1 Hàm chi phí cho Select (tt.) ● S2. Tìm kiếm nhị phân – Nếu điều kiện chọn (=) trên thuộc tính có sắp xếp thứ tự thì việc tìm kiếm nhị phân hiệu quả hơn tìm kiếm tuyến tính – Độ phức tạp: O(log2n) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 54
  55. 4.2.1 Hàm chi phí cho Select (tt.) ● S2. Tìm kiếm nhị phân (tt.) CS2 = log2b + [(s/bfr)] – 1 s: số mẩu tin thỏa mãn điều kiện = trên thuộc tính Ak – Đặc biệt đối với điều kiện = trên thuộc tính khóa (hay UNIQUE) CS2 =log2b Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 55
  56. 4.2.1 Hàm chi phí cho Select (tt.) ● Ví dụ: Cho lược đồ quan hệ Nhanvien (manv, honv, tennv, ngaysinh, gioitinh, luong, maphong) Phongban (maphong, tenphong, ngaythanhlap, maql) Câu hỏi: Tính chi phí cho câu truy vấn sau Truy vấn: maphong>5  manv=‘NV05’ (Nhanvien) Biết rNV = 10.000 mẩu tin, bNV=2000 blocks Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 56
  57. 4.2.1 Hàm chi phí cho Select (tt.) ● Truy vấn: maphong>5  manv=‘NV05’ (Nhanvien) – Đối với điều kiện maphong>5 CS1a= b=2000 – Đối với điều kiện manv=‘NV05’ CS1a= b/2=1000 3 CS2 = log2b = log22000 = log22.10 = 1+ 3log210 11 Vậy chọn điều kiện manv=‘NV05’ để thực hiện trước Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 57
  58. Nội dung 1. Quy trình thực hiện câu truy vấn của DBMS 2. Tiền xử lý câu truy vấn 3. Chuyển đổi câu truy vấn 4. Tối ưu hóa câu truy vấn 4.1 Giải thuật Heuristic 4.2 Ước lượng chi phí 4.2.1 Hàm chi phí cho Select 4.2.2 Hàm chi phí cho Join Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 58
  59. 4.2.2 Hàm chi phí cho Join [Ullman,+ 2001] R1 (A, B, C); R2 (A, D) TH1: V(R1,A) V(R2,A) TH2: V(R2,A) V(R1,A) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 59
  60. 4.2.2 Hàm chi phí cho Join (tt.) [Ullman + 2001] ● Tổng quát ● Số lượng giá trị của thuộc tính không tham gia phép kết V (W, A) = min {V (R1, A), V(R2, A)} V (W, B) = V (R1, B) V (W, C) = V (R1, C) V (W, D) = V (R2, D) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 60
  61. 4.2.2 Hàm chi phí cho Join (tt.) [Elmasri+2003] .Hàm tính chi phí cho Join theo phương pháp tìm kiếm Pi : Ji .Chi phí truy cập block tính theo hàm Ji : Cji Lưu ý: hàm tính chi phí chỉ dựa trên số block chuyển từ memory đến đĩa (chưa đề cập thời gian tính toán, chi phí lưu trữ và các yếu tố khác) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 61
  62. 4.2.2 Hàm chi phí cho Join (tt.) ● Độ chọn lọc của phép kết (js) js = | (R C S) | / | R x S | = | (R C S) | / (|R| * |S |) 0 <= js <= 1 ● Kích thước của tập kết quả sau khi thực hiện phép kết | (R C S) | = js * |R| * |S | ● R.A=S.B – Nếu A là khóa của R thì | (R C S) | <= |S|, js<= 1/|R| – Nếu B là khóa của S thì | (R C S) | <= |R|, js<= 1/|S| Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 62
  63. 4.2.2 Hàm chi phí cho Join (tt.) ● J1. Phép kết lồng nhau – Giả sử R là vòng lặp ngoài CJ1 = bR + (bR*bS) + ((js* |R|* |S|)/bfrRS) Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 63
  64. 4.2.2 Hàm chi phí cho Join (tt.) ● Ví dụ: Tính chi phí cho phép kết sau Truy vấn: NHANVIEN NV.maphong=PB.maphong PHONGBAN Biết: rNhanvien=10000, rPhongban=125, bNhanvien=2000, bPhongban=13, brfNV_PB =4 Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 64
  65. 4.2.2 Hàm chi phí cho Join (tt.) ● js = 1/|PHONGBAN| = 1/125 ● Sử dụng J1 với NHANVIEN là vòng lặp ngoài CJ1= bNV+ (bNV*bPB) + ((js*rNV*rPB)/brfNV_PB) =2000 + (2000*13) + ((1/125 * 10000 * 125)/4) =30500 ● Sử dụng J1 với PHONGBAN là vòng lặp ngoài CJ1= bPB+ (bPB*bNV) + ((js*rNV*rPB)/brfNV_PB) =13+ (13*2000) + ((1/125 * 10000 * 125)/4) =28513 Vậy sử dụng PHONGBAN là vòng lặp ngoài Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 65
  66. Nguyễn Thúy Ngọc Các hệ CSDL- Tổ chức khai thác] 66