Tài liệu Mô hình tối ưu hóa truy vấn hai pha trong cơ sở dữ liệu và ứng dụng

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG NGUYỄN VĂN CHUNG MÔ HÌNH TỐI ƢU HÓA TRUY VẤN HAI PHA TRONG CƠ SỞ DỮ LIỆU VÀ ỨNG DỤNG Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Ngƣời hƣớng dẫn khoa học: PGS.TS LÊ HUY THẬP Thái Nguyên - 2013 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn i LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là do bản thân tự nghiên cứu và thực hiện theo sự hƣớng dẫn khoa học của thầy PGS. TS. Lê Huy Thập Tôi hoàn toàn chịu trách nhiệm về tính pháp lý quá trình nghiên cứu khoa học của luận văn này. Ngƣời Cam Đoan Nguyễn Văn Chung Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn ii LỜI CẢM ƠN Lời đầu tiên tôi xin gửi lời cảm ơn đến thầy giáo PGS. TS. Lê Huy Thập đã định hƣớng, hƣớng dẫn và giúp đỡ tôi rất nhiều về mặt chuyên môn trong quá trình tìm hiểu và thực hiện luận văn. Tôi xin gửi lời biết ơn sâu sắc đến các thầy, các cô đã dạy dỗ và truyền đạt những kinh nghiệm quý báu cho chúng tôi trong suốt hai năm cao học ở trƣờng Đại học Công nghệ thông tin và truyền thông Thái Nguyên. Cuối cùng, xin chân thành cảm ơn gia đình và bạn bè đã động viên, quan tâm, giúp đỡ tôi hoàn thành khóa học và luận văn. Thái nguyên, tháng 09 năm 2013 Tác giả Nguyễn Văn Chung Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn iii MỤC LỤC LỜI CAM ĐOAN .............................................................................................. i LỜI CẢM ƠN ................................................................................................... ii MỤC LỤC ........................................................................................................ iii DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT ...................................................... v DANH MỤC CÁC BẢNG............................................................................... vi DANH MỤC CÁC HÌNH VẼ ........................................................................ vii MỞ ĐẦU ........................................................................................................... 1 1. Đặt vấn đề...................................................................................................... 1 2. Đối tƣợng và phạm vi nghiên cứu ................................................................. 1 3. Hƣớng nghiên cứu của đề tài ........................................................................ 1 4. Những nội dung nghiên cứu chính ................................................................ 1 Chƣơng 1: CƠ SỞ LÝ THUYẾT ...................................................................... 3 1.1. Giới thiệu về logic ...................................................................................... 3 1.2. Tổng quan về CSDL phân tán .................................................................... 9 1.2.1. Không gian tìm kiếm .......................................................................................10 1.2.2. Các chiến lƣợc tìm kiếm ..................................................................................13 1.2.3. Mô hình chi phí phân tán .................................................................................15 1.2.4. Các dạng chi phí song song và mô hình chi phí song song trên bộ tối ƣu hóa truy vấn........................................................................................................................22 1.3. Kết luận chƣơng 1 .................................................................................... 25 Chƣơng 2: MÔ HÌNH TỐI ƢU HÓA TRUY VẤN HAI PHA ..................... 26 2.1. Mô hình tối ƣu hóa truy vấn hai pha JOQR ............................................. 26 2.1.1. Cây truy vấn tiền xử lý ....................................................................................26 2.1.2. Cây toán tử........................................................................................................29 2.2. Tối ƣu hóa giai đoạn JOQR ..................................................................... 31 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn iv 2.2.1. Cực tiểu hóa chi phí phân mảnh lại ................................................................32 2.2.2. Khả phân mảnh và toán tử cảm thuộc tính .....................................................34 2.2.3. Bài toán tối ƣu hóa ...........................................................................................37 2.3. Kết luận chƣơng 2 .................................................................................... 48 Chƣơng 3: CHƢƠNG TRÌNH THỬ NGHIỆM.............................................. 49 3.1. Ứng dụng tại trƣờng Cao đẳng kinh tế - kỹ thuật Vĩnh Phúc (Dạng demo) .... 49 3.1.1. Giới thiệu CSDL của trƣờng Cao đẳng kinh tế - kỹ thuật Vĩnh Phúc........49 3.1.2. Cực tiểu hóa chi phí phân mảnh lại CSDL tại mục 3.1.1 .............................62 3.2. Kết luận chƣơng 3 .................................................................................... 66 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA LUẬN VĂN ....................... 67 TÀI LIỆU THAM KHẢO ............................................................................... 68 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn v DANH MỤC CÁC KÝ HIỆU, VIẾT TẮT DBMS (Database management system) ESPS (Executor Sever Process) JOQR (Join Ordering and Query Rewriting) LAN (Local Area Network) QEP (Query Execution Plan) SPJ (Selection Projection Joint) SQL (Structured Query Language) WAN (Wide area network) TW (Total Work) RT (Response Time) MC (Memory Consumption) Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn vi DANH MỤC CÁC BẢNG Bảng 1-1. Bảng chân trị các phép toán mệnh đề .............................................. 4 Bảng 1-2. Thứ tự ưu tiên của các phép toán ..............................................................4 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn vii DANH MỤC CÁC HÌNH VẼ Hình 1-1. Quá trình tối ưu hoá vấn tin .......................................................................9 Hình 1-2. Sơ đồ kết nối các quan hệ .........................................................................11 Hình 1-3. Các cây nối tương đương .........................................................................12 Hình 1-4. Các loại cây ...............................................................................................13 Hình1–5. Xây dựng tối ưu hoá một cách đơn định theo kiểu quy hoạch động ......14 Hình 1-6. Hành động của thể tối ưu hoá trong một chiến lược ngẫu nhiên hoá ...15 Hình 1-7. Truyền dữ liệu trong câu vấn tin ..............................................................17 Hình 2-1. Cây truy vấn tiền xử lý ..............................................................................27 Hình 2-2. Cây toán tử tương ứng với cây trong hình 2-1 ........................................31 Hình 2-3. Sơ đồ phân mảnh ngang dữ liệu tại các nút ............................................33 Hình 2-4. Các cây truy vấn khác nhau về phân hoạch dữ liệu, đường nét đứt cho thấy phải phân bố lại quan hệ ...................................................................................33 Hình 2-5. Cây toán tử tương ứng với câu truy vấn ..................................................37 Hình 2-6. Cây gốc và các phương án tô màu ...........................................................39 Hình 2-7. Đồ thị vấn tin .............................................................................................42 Hình 2-8. Cây nối của đồ thị vấn tin trên hình 2-7 ..................................................43 Hình 2-9. Ảnh hưởng của thứ tự phép nối đến chi phí phân mảnh ngang .............43 Hình 3-1. Sơ đồ kết nối các quan hệ .........................................................................53 Hình 3-2. Màn hình chính của chương trình ............................................................54 Hình 3-3. Cây truy vấn ban đầu của ví dụ 1.............................................................55 Hình 3-4. Cây sau khi sắp lại phép nối ví dụ 1 ........................................................55 Hình 3-5. Màn hình nhập câu truy vấn.....................................................................56 Hình 3-6. Câu truy vấn ban đầu và sau biểu diễn lại ví dụ 1 ..................................56 Hình 3-7. Kết quả của câu truy vấn ví dụ 1 ..............................................................57 Hình 3-8. Cây truy vấn ban đầu của ví dụ 2.............................................................58 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn viii Hình 3-9. Cây sau khi sắp lại phép nối ví dụ 2 ........................................................58 Hình 3-10. Giao diện câu truy vấn ban đầu và sau biểu diễn lại ví dụ 2 ...............59 Hình 3-11. Kết quả của câu truy vấn ví dụ 2............................................................59 Hình 3-12. Cây truy vấn ban đầu của ví dụ 3 ..........................................................60 Hình 3-13. Cây sau khi xếp lại phép nối của ví dụ 3 ...............................................61 Hình 3-14. Giao diện câu truy vấn ban đầu và sau biểu diễn lại ví dụ 3 ...............61 Hình 3-15. Kết quả của câu truy vấn ví dụ 3............................................................62 Hình 3-16. Sơ đồ phân mảnh ngang dữ liệu tại các nút của ví dụ 1.......................62 Hình 3-17. Cây gốc và các phương án tô màu của ví dụ 1 .....................................63 Hình 3-18. Giao diện pha 2 của ví dụ 1....................................................................63 Hình 3-19. Giao diện kết quả pha 2 của ví dụ 1.......................................................64 Hình 3-20. Sơ đồ phân mảnh ngang dữ liệu tại các nút của ví dụ 2.......................64 Hình 3-21. Cây gốc và các phương án tô màu của ví dụ 2 .....................................65 Hình 3-22. Giao diện pha 2 của ví dụ 2....................................................................65 Hình 3-23. Giao diện kết quả pha 2 của ví dụ 1.......................................................66 Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 1 MỞ ĐẦU 1. Đặt vấn đề Tối ƣu hóa vấn tin là quá trình tìm một phƣơng án thực hiện câu vấn tin QEP (Query Execution Plan) tối ƣu (theo nghĩa hạ thấp tối đa hàm chi phí, hoặc cực đại hàm lợi ích ở một dạng nào đó). Tối ƣu câu truy vấn trong cơ sở dữ liệu song song bằng mô hình tối ƣu hóa truy vấn hai pha bao gồm: i. Sắp xếp lại thứ tự các phép nối ii. Biểu diễn lại cây truy vấn. Bộ tối ƣu hóa thực hiện hai bƣớc này để tạo ra một cây truy vấn tiền xử lý, xác định những yếu tố nhƣ thứ tự thực hiện các phép toán và chiến lƣợc thực hiện mỗi phép toán. Bộ tối ƣu sẽ triển khai các mô hình và giải thuật song song để tìm kiếm một phƣơng án tốt nhất cho việc thi hành song song. 2. Đối tƣợng và phạm vi nghiên cứu Các biểu thức logic Cơ sở dữ liệu phân tán Xử lý song song và phân tán 3. Hƣớng nghiên cứu của đề tài Các dạng chi phí song song Nghiên cứu mô hình tối ƣu hóa hai pha. 4. Những nội dung nghiên cứu chính Luận văn đƣợc trình bày trong 3 chƣơng, có phần mở đầu, phần kết luận, phần mục lục, phần tài liệu tham khảo. Chƣơng 1: Cơ sở lý thuyết Chƣơng 2: Mô hình tối ƣu hóa truy vấn hai pha Chƣơng 3: Chƣơng trình thử nghiệm Kết luận và hƣớng phát triển của luận văn Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 2 5. Phƣơng pháp nghiên cứu Nghiên cứu kỹ các kiến thức, chủ đề có liên quan đến đề tài. Nghiên cứu các mô hình chi phí song song và mô hình chi phí song song trên bộ tối ƣu hóa truy vấn. Nắm vững các kiến thức cơ bản của tối ƣu hóa hai pha. 6. Ý nghĩa khoa học của đề tài Luận văn giúp cho việc tối ƣu hóa câu truy vấn phân tán bằng phƣơng pháp hai pha. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 3 Chƣơng 1: CƠ SỞ LÝ THUYẾT 1.1. Giới thiệu về logic 1.1.1. Khái niệm về mệnh đề và chân trị Một mệnh đề là một phát biểu nào đó mà chỉ cho hai giá trị: True hoặc False. Giá trị True, hoặc False của một mệnh đề đƣợc gọi là chân trị của mệnh đề. Chân trị True đƣợc viết là 1, chân trị False đƣợc viết là 0 Ví dụ 1.1.1: "6 là số chẵn" - mệnh đề đúng nên chân trị 1. "6 là số nguyên tố" - mệnh đề sai nên chân trị 0. 1.1.2. Mệnh đề sơ cấp Là mệnh đề không thể phân nhỏ hơn đƣợc nữa - có thể nói mệnh đề sơ cấp là một phát biểu đơn giản nhất. Ví dụ 1.1.2: "Số chẵn chia hết cho hai". Các mệnh đề sơ cấp thƣờng đƣợc gắn với các ký hiệu là các ký tự viết thƣờng: p, q, r, ... mà ta gọi là các biến mệnh đề hay biến logic. 1.1.3. Mệnh đề phức hợp Mệnh đề phức hợp là mệnh đề đƣợc tạo ra từ các mệnh đề sơ cấp hoặc các mệnh đề phức hợp khác bằng cách dùng các từ liên kết, AND - "và", OR "hoặc", ... Ví dụ 1.1.3: "Số 2 là số chẵn và là số nguyên tố" gồm 2 mệnh đề "Số 2 là số chẵn" từ nối "và" và "Số 2 là số nguyên tố" 1.1.4. Các phép toán mệnh đề (phủ định); theo); (hội); (tuyển); (hoặc hay tổng trực giao); (kéo (kéo theo hai chiều),... chân trị từng trƣờng hợp đƣợc cho trong bảng 1-1: Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 4 Bảng 1-1. Bảng chân trị các phép toán mệnh đề P q 0 0 1 0 0 0 1 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 p p q p q p q p q p q p q 1.1.5. Thứ tự ƣu tiên của các phép toán logic Thứ tự ƣu tiên của các phép toán logic đƣợc liệt kê theo mức ƣu tiên từ trên xuống dƣới, từ trái sang phải ở bảng 1-2: Bảng 1-2. Thứ tự ưu tiên của các phép toán Ký hiệu phép toán Nghĩa của phép toán , , Phủ định , Hội, tuyển , Kéo theo, Kéo theo hai chiều Ghi chú: Nếu các phép toán trong cùng một dòng có thứ tự nhập nhằng hoặc muốn chỉ ra mức ƣu tiên của phép toán thì cần bổ sung thêm dấu ( ). Ví dụ 1.1.4: p q có nghĩa là p ( q) . Còn p q r để ƣu tiên phép toán hay cần cho thêm dấu () để chỉ rõ sự ƣu tiên, chẳng hạn (p q ) r . 1.1.6. Biểu thức logic Biểu thức logic có thể nói chính là mệnh đề phức hợp, biểu thức logic thƣờng đƣợc ký hiệu bởi các chữ in hoa Ví dụ 1.1.5: E= p (q r) ) (r s) Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 5 P = E, F G, (G H) ( G E),...; trong đó P, E, F, G, H là các biểu thức logic. Bảng chân trị của các biểu thức logic là bảng liệt kê chân trị có thể có theo mọi khả năng chân trị của các biến mệnh đề có trong biểu thức Hai biểu thức logic E và F đƣợc gọi là tƣơng đƣơng và viết E F khi và chỉ khi E và F luôn có cùng chân trị. Để kiểm tra xem hai biểu thức logic có tƣơng đƣơng với nhau hay không chúng ta dựa vào bảng chân trị hay bằng phƣơng pháp chứng minh logic. Ví dụ 1.1.6: Cho hai biểu thức logic E = p q và F = p q thì E F. Biểu thức logic E đƣợc gọi là hằng True nếu chân trị của E luôn luôn là 1, tức là E 1. Ví dụ 1.1.7: p thì E là hằng đúng vì E E=p 1. Biểu thức logic E đƣợc gọi là hằng False nếu chân trị của E luôn luôn là 0, tức là E 0. Ví dụ 1.1.8: E=p p thì E 0. Chú ý: Theo định nghĩa E1 F1 khi và chỉ khi E1 F1, điều này có thể viết gọn nhƣ sau: E1 F1 1. Ví dụ 1.1.9: E1 = p p thì E1 E1 = (p q) ( p 1. q) thì E1 Quan hệ bắc cầu: Nếu E Số hóa bởi Trung tâm Học liệu F và F 1. G thì E G. http://lrc.tnu.edu.vn 6 1.1.7. Các luật logic i. Luật phủ định của phủ định p p ii. Luật giao hoán p q q p p q q p iii. Luật kết hợp p (q r) (p q) r p (q r) (p q) r iv. Luật phân phối p (q r) (p q) (p r) p (q r) (p q) (p r) v. Luật Demorgan (p q) p q (p q) p q vi. Luật về phản tử bù p p 1 p p 0 vii. Luật kéo theo p q p q viii. Luật tƣơng đƣơng p q (p q) (q p) ix. Các luật đơn giản của phép tuyển p p p p 1 1 p 0 p Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 7 p (p q) p x. Các luật đơn giản của phép hội p p p p 1 p p 0 0 p (p q) p 1.1.8. Quy tắc thay thế tƣơng đƣơng Cho E là một biểu thức logic, nếu thay thế một biểu thức con của nó bởi một biểu thức tƣơng đƣơng với biểu thức con đó, biểu thức logic E' mới nhận đƣợc sẽ tƣơng đƣơng với E Ví dụ 1.1.10: E= p q q, do đó ta có thể thay thế q bởi Vì q E' = = p q và đƣợc q Dùng bảng chân trị cho E và E' ta sẽ thấy E E'. 1.1.9. Quy tắc bất biến đối với biểu thức logic hằng True Cho E là một biểu thức logic hằng True, nếu thay thế một biến mệnh đề p nào đó trong E bởi một biểu thức logic bất kỳ ta sẽ nhận đƣợc biểu thức logic E' mới cũng là hằng True. Ví dụ 1.1.11: E = (p q) ( p q) thì E 1(E là hằng True). Bây giờ ta thay thế q trong E bởi q E' = (p (q r)) ( p (q r ta sẽ đƣợc: r)) theo quy tắc 2 ta cũng có E' 1. 1.1.10. Biểu thức hội cơ bản Biểu thức logic F = F (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến mệnh đề sơ cấp, đƣợc gọi là biểu thức hội cơ bản, nếu: Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 8 F = q1 q2 qn : với qi = pi hoặc qi = p i (i = 1, n ). .... Ví dụ 1.1.12: F(x, y, z) = x z, trong đó x, y, z là các biến mệnh đề sơ cấp. y 1.1.11. Biểu thức tuyển cơ bản Biểu thức logic E = E (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến mệnh đề sơ cấp, đƣợc gọi là biểu thức tuyển cơ bản, nếu: E = q1 q2 .... qn : với qi = pi hoặc qi = p i (i = 1, n ). Ví dụ 1.1.13: F(x, y, z) = x z, trong đó x, y, z là các biến mệnh đề sơ cấp. y 1.1.12. Biểu thức tuyển chính tắc Biểu thức logic E = E (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến mệnh đề sơ cấp, đƣợc gọi là dạng tuyển chính tắc, nếu: E = E1 E2 En : với Ei (i = 1, n ) là biểu thức hội cơ bản của các pi .... Ví dụ 1.1.14: E(x, y, z) = (x y z) (x y chính tắc vì E1 = (x y z), E2 = ( x z) y (x y z), là biểu thức tuyển z), E3 = (x y z) là các biểu thức hội cơ bản Định lý 1.1.1: Mọi biểu thức logic E (p1, p2, ..., pn) đều tƣơng đƣơng với một biểu thức tuyển chính tắc duy nhất. Tức E (p1, p2, ..., pn) E1 E2 .... Em (duy nhất) với Ei (i = 1, m ) là các biểu thức hội cơ bản. Ei = q1 q2 .... qn với qi = pi hoặc qi = p i (i = 1, n ). 1.1.13. Biểu thức hội chính tắc Biểu thức logic F = F (p1, p2, ..., pn), trong đó pi (i = 1, n ) là các biến mệnh đề sơ cấp, đƣợc gọi là dạng hội chính tắc, nếu: Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 9 F = F1 F2 .... Fn : với Fi (i = 1, n ) là biểu thức tuyển cơ bản của các pi Ví dụ 1.1.15: F(p1, p2, p3) = (p1 p2 tuyển chính tắc vì F1 = (p1 p3) p2 ( p1 p2 p3), F2 = ( p1 p3) p2 (p1 p2 p3), là biểu thức p3), F3 = ( p1 p2 p3) là các biểu thức tuyển cơ bản. Định lý 1.1.2: Mọi biểu thức logic F (p1, p2, ..., pn) đều tƣơng đƣơng với một biểu thức hội chính tắc duy nhất. Tức F (p1, p2, ..., pn) F1 F2 .... Fm (duy nhất) với Fi (i = 1, m ) là các biểu thức tuyển cơ bản. Ei = q1 q2 .... qn với qi = pi hoặc qi = p i (i = 1, n ). 1.2. Tổng quan về CSDL phân tán Tối ƣu hóa vấn tin là tìm phƣơng án thực hiện câu vấn tin để tiêu tốn ít nhất thời gian hoặc kinh phí (một hàm mục tiêu nào đó). Thể tối ƣu hóa vấn tin, là một phần mềm chịu trách nhiệm thực hiện tối ƣu hóa câu vấn tin, nó đƣợc tạo ra bới ba thành phần: Không gian tìm kiếm, mô hình chi phí và chiến lƣợc tìm kiếm (xem hình l-1). CÂU VẤN TIN Tạo ra không gian tìm kiếm Qui tắc biến đổi câu vấn tin QEP TƢƠNG ĐƢƠNG Phƣơng pháp tìm kiếm Mô hình chi phí, hay hàm mục tiêu QEP TỐT NHẤT Hình 1-1. Quá trình tối ưu hoá vấn tin Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 10 Không gian tìm kiếm là tập các phƣơng án có thể thực hiện câu vấn tin. Những phƣơng án này là tƣơng đƣơng, theo nghĩa là chúng sinh ra cùng một kết quả nhƣng khác nhau về cách thực hiện. Do khác nhau về cách thực hiện vì thế khác nhau về hiệu năng. Không gian tìm kiếm thu đƣợc bằng cách áp dụng các qui tắc biến đổi, chẳng hạn những qui tắc của phép toán đại số quan hệ. Mô hình chi phí làm nhiệm vụ tiên đoán chi phi của một phƣơng án thực hiện đã cho. Để làm điều này, mô hình chi phí phải có đủ thông tin cần thiết về môi trƣờng thực hiện phân tán. Chiến lƣợc tìm kiếm sẽ tìm trong không gian tìm kiếm để chọn ra phƣơng án tốt nhất dựa theo mô hình chi phí. Nó xác định các phƣơng án nào cần đƣợc kiểm tra và theo thứ tự nào. Chi tiết về môi trƣờng (tập trung hay phân tán) đƣợc ghi nhận trong không gian tìm kiếm và mô hình chi phí. 1.2.1. Không gian tìm kiếm Không gian tìm kiếm là tập các QEP biểu diễn cho câu vấn tin. Các QEP là tƣơng đƣơng, theo nghĩa chúng sinh ra cùng một kết quả nhƣng khác nhau ở thứ tự thực hiện các thao tác cài đặt, vì thế sẽ khác nhau về hiệu năng. Không gian tìm kiếm thu đƣợc bằng cách áp dụng các qui tắc biến đổi. Mô hình (hàm) chi phí đƣợc dùng để chỉ ra chi phí của QEP tƣơng ứng. Chiến lƣợc tìm kiếm làm nhiệm vụ tìm kiếm, khám phá không gian tìm kiếm và chọn ra QEP tốt nhất dựa theo mô hình chi phí. Nó xác định xem QEP nào đƣợc kiểm tra và theo thứ tự nào. Một QEP tƣơng đƣơng với một cây toán tử. Cây toán tử là một đồ thị vô hƣớng, không chu trình, đƣợc dùng để thể hiện một câu vấn tin bậc thấp (Đại số quan hệ), gốc là các trƣờng nằm sau SELECT, lá là các quan hệ cơ sở nằm sau FROM, và các nút là các phép toán nằm sau WHERE nhƣng đƣợc chuyển sang dạng phép toán đại số quan hệ. Cách thực hiện các phép toán trên cây theo hƣớng từ lá về gốc. Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn 11 Để nêu bật các đặc trƣng của thể tối ƣu hoá vấn tin, chúng ta thƣờng tập trung nghiên cứu các cây nối là loại cây toán tử với các phép toán nối hoặc phép toán tích Descartes hoặc phép toán hợp. Ví dụ 1.2.1: Xét cơ sở dữ liệu của công ty, với các quan hệ (hình 1-2) nhƣ sau: Hình 1-2. Sơ đồ kết nối các quan hệ Trong đó: Quan hệ PROJ: Projects - Các dự án PNO: Mã dự án PNAME: Tên dự án BUDGET: Ngân sách dự án LOC: Location - Nơi triển khai dự án Quan hệ PAY: Payments - Chi trả lương TITLE - Trình độ chuyên môn SAL: Salary - Lƣơng Quan hệ EMP: Employees - Nhân công ENO: Mã nhân công ENAME: Tên nhân công TITLE - Trình độ chuyên môn Số hóa bởi Trung tâm Học liệu http://lrc.tnu.edu.vn