MỞ ĐẦU Khi dữ liệu đƣợc lƣu trữ trên máy tính thì việc sử dụng nó nhƣ thế nào để có hiệu quả là một thách thức đối với ngƣời sử dụng. Để khai thác một cơ sở dữ liệu tốt cần phải có một hệ quản trị cơ sở dữ liệu tốt. Việc xử lý các truy vấn, quản lý giao tác là hai chức năng quan trọng của một hệ quản trị cơ sở dữ liệu. Tìm hiểu về lý thuyết và thực tiễn của hai chức năng này có ý nghĩa trong việc xây dựng các hệ quản trị cơ sở dữ liệu.
Thông qua việc nghiên cứu một số tài liệu khoa học có liên quan, trong luận văn này chúng tôi đã đi sâu tìm hiểu các vấn đề với đề tài “xử lý truy vấn và quản lý các giao tác”. Luận văn bao gồm hai chƣơng: Chƣơng 1: Xử lý và tối ƣu truy vấn Một truy vấn trên cơ sở dữ liệu là một biểu thức đại số quan hệ, thực hiện một loạt các thao tác trên cơ sở dữ liệu quan hệ để lấy ra các thông tin cần thiết cho việc quản lý. Nghiên cứu về xử lý và tối ƣu truy vấn là nghiên cứu các thuật toán thực hiện các phép toán đại số quan hệ cũng nhƣ tìm cách thực hiện biểu thức đại số quan hệ theo một trật tự nào đó để có câu trả lời nhanh nhất. Chƣơng 2: Quản lý giao tác Quản lý giao tác là rất cần thiết, đặc biệt khi các giao tác xẩy ra đồng thời và có cạnh tranh nhau một số khoản mục dữ liệu trong cơ sở dữ liệu, tính nhất quán có thể không còn đƣợc bảo toàn nữa.
Do vậy hệ thống cần điều khiển sự tƣơng tác giữa các giao tác đồng thời. Do kinh nghiệm làm việc với cơ sở dữ liệu còn ít, chắc chắn trong luận văn còn nhiều thiếu sót. Chúng tôi chân thành mong đƣợc các thầy, các cô, và bạn bè đóng góp ý kiến. 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1 XỬ LÝ VÀ TỐI ƯU TRUY VẤN Trong chƣơng này trình bầy các kỹ thuật mà hệ quản trị cơ sở dữ liệu (DBMS) sử dụng để xử lý, tối ƣu hoá và thực thi các truy vấn bậc cao.
Một truy vấn đƣợc trình bầy trong một ngôn ngữ bậc cao, nhƣ SQL, đầu tiên phải đƣợc kiểm tra, phân tích và xác nhận tính hợp lệ. Bộ quét sẽ xác định các dấu hiệu ngôn ngữ, nhƣ các từ khóa SQL, tên các thuộc tính và tên các quan hệ trong nội dung câu truy vấn, trong khi đó bộ phân tích sẽ kiểm tra cú pháp của truy vấn để xác định xem nó có đƣợc trình bầy phù hợp với các luật cú pháp của ngôn ngữ truy vấn hay không. Một truy vấn cũng phải đƣợc xác nhận tính hợp lệ bằng cách kiểm tra tất cả các tên quan hệ và thuộc tính là hợp lệ, và các tên có ý nghĩa trong lƣu đồ cơ sở dữ liệu cụ thể đƣợc truy vấn. Sau đó một biểu diễn bên trong của truy vấn đƣợc tạo ra, thƣờng là nhƣ một cấu trúc dữ liệu cây gọi là một cây truy vấn.
Cũng có thể biểu diễn truy vấn bằng cách sử dụng một cấu trúc dữ liệu đồ thị gọi là đồ thị truy vấn. Sau đó DBMS sẽ phải đƣa ra một chiến lƣợc thực hiện để lấy ra kết quả của truy vấn từ các file cơ sở dữ liệu. Một truy vấn thƣờng có nhiều chiến lƣợc thực hiện, và quá trình chọn một chiến lƣợc phù hợp để xử lý một truy vấn gọi là tối ƣu truy vấn.1 thể hiện các bƣớc khác nhau của việc xử lý một truy vấn bậc cao. Bộ tối ƣu truy vấn có nhiệm vụ tạo ra một phƣơng án thực hiện và bộ tạo mã tạo ra chƣơng trình để thực hiện phƣơng án đó.
Bộ xử lý cơ sở dữ liệu thời gian chạy có nhiệm vụ chạy chƣơng trình truy vấn trong kiểu thông dịch hoặc biên dịch để tạo ra kết quả của truy vấn. Nếu có một lỗi chạy chƣơng trình đƣợc tạo ra thì bộ xử lý cơ sở dữ liệu thời gian chạy sẽ sinh ra một thông báo lỗi. Thuật ngữ tối ƣu đƣợc sử dụng ở đây là không chính xác vì trong một vài trƣờng hợp, phƣơng án thực hiện đƣợc lựa chọn không phải là chiến lƣợc tốt nhất, nó chỉ là một chiến lƣợc hiệu quả và hợp lý cho việc thực hiện truy vấn. Việc tìm ra một chiến lƣợc tốt nhất thƣờng phải mất nhiều thời gian, ngoại trừ những truy vấn đơn giản, và có thể yêu cầu thông tin về việc các file 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đƣợc cài đặt nhƣ thế nào và ngay cả nội dung của các file, những thông tin đó có thể không có trong từ điển hệ quản trị cơ sở dữ liệu.
Vì vậy, lập kế hoạch của một chiến lƣợc thực hiện là chính xác hơn tối ƣu truy vấn. Truy vấn viết trong ngôn ngữ bậc cao Scanning, parsing, validating Dạng biểu diễn bên trong Query Optimiser Phương án thực hiện Query Code Generator Chương trình thực hiện truy vấn Runtime Database Processor Kết quả của truy vấn Hình 1.1 Các bước điển hình khi xử lý một truy vấn bậc cao 1.1 Chuyển các truy vấn SQL thành đại số quan hệ Một truy vấn SQL đầu tiên chuyển đổi thành một biểu thức đại số quan hệ mở rộng tƣơng đƣơng, đƣợc biểu diễn nhƣ là cấu trúc dữ liệu cây truy vấn, và sau đó đƣợc tối ƣu. Thông thƣờng các truy vấn SQL đƣợc phân tích thành các khối truy vấn, tạo nên các đơn vị cơ sở mà có thể chuyển đổi thành những 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com phép toán đại số và đƣợc tối ƣu. Một khối truy vấn chứa một biểu thức SELECT – FROM – WHERE đơn và có thể có các mệnh đề Group by và Having nếu chúng là một phần của biểu thức.
Vì vậy các truy vấn đƣợc lồng bên trong một truy vấn đƣợc xác định nhƣ các khối truy vấn riêng rẽ. [6] Xét các quan hệ sau: EMPLOYEE, DEPARTMENT, WORKS-ON và PROJECT. EMPLOYEE FNAME LNAME SSN ADDESS SEX SALAR DNO BDATE Y DEPARTMENT DNAME DNUMBER MGRSSN MGRSTARTDATE PROJECT PNAME PNUMBER PLOCATION DNUM WORKS-ON ESSN PNO HOURS Bảng 1.1 Các quan hệ Trong đó: Quan hệ EMPLOYEE chứa thuộc tính của các nhân viên: FNAME: tên của các nhân viên LNAME: họ và tên đệm của nhân viên SSN: mã nhân viên BDATE: ngày sinh của mỗi nhân viên ADDESS: địa chỉ của nhân viên SEX: giới tính của nhân viên SALARY: mức lƣơng của từng nhân viên 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com DNO: mã số phòng ban mà nhân viên đó làm việc Quan hệ DEPARTMENT chứa thông tin về các phòng ban: DNAME: tên của mỗi phòng ban DNUMBER: mã số của mỗi phòng ban MGRSSN: mã số của ngƣời quản lý từng phòng MGRSTARTDATE: ngày bắt đầu làm quản lý của ngƣời quản lý phòng ban Quan hệ PROJECT chứa thông tin về các dự án: PNAME: tên của dự án PNUMBER: mã số dự án PLOCATION: nơi thực hiện dự án DNUM: mã số của phòng thực hiện dự án Quan hệ WORKS-ON chứa thông tin về thời gian làm việc của mỗi nhân viên: ESSN: mã số của nhân viên PNO: mã số dự án mà nhân viên đó tham gia HOURS: số giờ mà nhân viên đó thực hiện Xét truy vấn SQL sau trên quan hệ EMPLOYEE trong bảng 1.1 SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > (SELECT MAX(SALARY) FROM EMPLOYEE WHERE DNO=5); Truy vấn này chứa một truy vấn con lồng bên trong và vì vậy có thể đƣợc tách thành 2 khối: Khối trong là: SELECT MAX (SALARY) FROM EMPLOYEE WHERE DNO=5 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Và khối ngoài là: SELECT LNAME, FNAME FROM EMPLOYEE WHERE SALARY > c Với c biểu diễn kết quả do khối trong trả lại. Khối trong có thể đƣợc chuyển thành biểu thức quan hệ mở rộng nhƣ sau: FMAX SALARY(DNO=5(EMPLOYEE)) Và khối ngoài đƣợc chuyển sang biểu thức quan hệ nhƣ sau: LNAME, FNAME(SALARY>C (EMPLOYEE)) Sau đó bộ tối ƣu truy vấn sẽ chọn một phƣơng án thực hiện cho từng khối.
Chú ý rằng trong ví dụ ở trên khối trong chỉ cần thực hiện một lần để đƣa ra lƣơng lớn nhất, sau đó khối ngoài sử dụng lƣơng lớn nhất này nhƣ là hằng số c. Truy vấn đó gọi là truy vấn lồng nhau không liên kết. Việc tối ƣu các truy vấn lồng nhau liên kết sẽ khó khăn hơn nhiều.2 Các thuật toán cơ bản thực hiện phép toán truy vấn Một hệ quản trị cơ sở dữ liệu (RDBMS) phải có các thuật toán để thực hiện các kiểu phép toán quan hệ khác nhau có thể xuất hiện trong một chiến lƣợc thực hiện truy vấn. Các phép toán bao gồm phép toán đại số quan hệ cơ bản và mở rộng, hoặc là tổ hợp các phép toán này.
Với mỗi phép toán (hoặc một tổ hợp phép toán) nhƣ thế, thƣờng phải có sẵn một hoặc nhiều thuật toán để thực hiện nó.1 Sắp xếp ngoài Sắp xếp là một trong các thuật toán cơ bản đƣợc sử dụng trong xử lý truy vấn. Ví dụ, khi một truy vấn SQL chỉ ra một mệnh đề Order by, kết quả truy vấn phải đƣợc sắp xếp. Sắp xếp cũng là một bộ phận then chốt trong các thuật toán đƣợc sử dụng cho phép nối (Join) hoặc các phép toán khác nhƣ phép hợp (Union), phép giao (Intersection) và trong các thuật toán loại bỏ bản 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ghi trùng nhau đối với phép chiếu (Project) khi một truy vấn SQL chỉ ra tuỳ chọn Distinct trong mệnh đề Select. Sắp xếp ngoài đề cập đến các thuật toán sắp xếp phù hợp với các file lớn đƣợc lƣu trữ trên đĩa mà không xếp vào bộ nhớ chính, ví dụ hầu hết các file cơ sở dữ liệu.
Thuật toán sắp xếp ngoài thƣờng sử dụng chiến lƣợc sắp xếp trộn, nó bắt đầu bằng việc sắp xếp các file con nhỏ, gọi là các run, của file chính và sau đó trộn các run đã đƣợc sắp xếp tạo nên các file con lớn hơn và các file con đó lại đƣợc trộn với nhau. Giống nhƣ các thuật toán khác, thuật toán sắp xếp trộn đòi hỏi một không gian phòng đợi (buffer space) trong bộ nhớ chính, ở đó việc sắp xếp và trộn các run đƣợc thực hiện. Thuật toán cơ bản đƣợc đƣa ra ở hình 1.2 gồm hai giai đoạn: (1) giai đoạn sắp xếp, (2) giai đoạn trộn. Trong giai đoạn sắp xếp, các run của file có thể đặt vừa vào bộ đệm có sẵn sẽ đƣợc đọc vào trong bộ nhớ chính và đƣợc sắp xếp bằng cách dùng một thuật toán sắp xếp trong rồi đƣợc ghi trở lại vào đĩa nhƣ các file con đƣợc sắp xếp tạm thời.
Kích cỡ của run và số lƣợng run ban đầu (n R) đƣợc chỉ ra bởi các khối file (b) và không gian phòng đợi có sẵn (nB).