CHƯƠNG 2: PHÂN RÃ VẤN TIN VÀ CỤC BỘ HÓA DỮ LIỆU
2.1. Phân rã vấn tin câu vấn tin SQL
2.1.1. Phân tích câu vấn tin trên cơ sở “kiểu dữ liệu” và “ngữ nghĩa”
Phân tích câu vấn tin để bỏ đi các câu vấn tin sai hoặc thừa. Những lý do chính là do chúng sai kiểu hoặc sai nghĩa. Khi phát hiện ra một trong những trường hợp này, hệ thống chỉ đơn giản trở về và đưa ra một thông báo giải thích về lý do sai. Ngược lại, quá trình xừ lý vấn tin sẽ được tiếp tục.
Một câu vấn tin gọi là sai kiểu (type incorrect) nếu nó có một thuộc tính hoặc tên quan hệ chưa được khai báo trong lược đồ toàn cục, hoặc kiểu không thích hợp cho các phép toán đang được xử lý. Kỹ thuật được sử dụng để phát hiện các câu vấn tin sẽ nêu ở đây giống như kỹ thuật kiểm tra kiểu trong ngôn ngữ lập trình. Tuy nhiên các khai báo kiểu là một bộ phận của lược đồ toàn cục chứ không phải nằm trong câu vấn tin bởi vì một câu vấn tin quan hệ không tạo ra một kiểu nào mới.
Một câu vấn tin gọi là sai nghĩa (semantically incorrect) nếu các thành phần của nó không tham gia vào việc tạo ra kết quả. Trong ngữ cảnh của phép tính quan hệ, chúng ta không thể xác định được tính đúng đắn ngữ nghĩa cho câu vấn tin tổng quát. Tuy nhiên vẫn có thể xác định được tính đúng đắn ngữ nghĩa của câu vấn tin cho một lớp vấn tin quan hệ, đó là các vấn tin không chứa các tuyển và phủ định bằng cách biểu diễn câu vấn tin như một đồ thị, được gọi là đồ thị kết nối (connection graph) hay đồ thị vấn tin (query graph)
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Chúng ta định nghĩa đồ thị kết nối cho các loại vấn tin hữu ích nhất có chứa phép chọn, chiếu và nối. Trong một đồ thị vấn tin có một nút biểu thị cho một quan hệ kết quả và các nút khác biểu thị cho các quan hệ toán hạng.
Một cạnh giữa hai nút không phải là quan hệ kết quả biểu diễn cho một nối, còn cạnh nối với nút kết quả sẽ biểu thị cho phép chiếu. Còn các nút không phải là kết quả có thể được gắn nhãn là một vị từ chọn hoặc vị từ nối. Một đồ thị con quan trọng của đồ thị vấn tin là đồ thị nối chỉ có các nối mà thôi. Đồ thị nối rất có ích cho giai đoạn tối ưu hóa vấn tin.
Ví dụ 2.1.1-1
Từ các quan hệ trong ví dụ 1.2.2-1 tìm tên (ENAME) và nhiệm vụ (RESP) của các lập trình viên (programmer) đã làm việc cho dự án CAD/CAM trong hơn ba năm (36 tháng).
Câu vấn tin bằng SQL như sau : SELECT EMANE, RESP FROM ẸMP, ASG, PROJ WHERE EMP.ENO = ASG.ENO AND ASG.PNO = PROJ.PNO AND PNAME = “CAD/CAM”
AND DUR >= 36
AND TITLE = “Programmer”
Đồ thị vấn tin cho câu vấn tin trên là hình 2.1-1a
Đồ thị vấn tin giúp cho việc xác định tính đúng đắn về ngữ nghĩa của câu vấn tin hội đa biến không có phủ định. Câu vấn tin sẽ sai ngữ nghĩa nếu đồ thị vấn tin của nó không liên thông.
Câu vấn tin được xem là đúng bằng cách xét các nối kết bị thiếu như một tích Descartes. Nhưng nói chung, vấn đề chính là các vị từ nối từ bị thiếu và câu vấn tin cần được cần loại bỏ.
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Từ đồ thị vấn tin ta có đồ thị nối (hình 2.1b).
Ví dụ 2.1.1-2
Xét câu vấn tin SQL như sau
SELECT ENAME, RESP FROM EMP, ASG, PROJ
WHERE EMP.ENO =ASG.ENO
AND PNAME=”CAD/CAM”
AND DUR > =36
AND TITLE = “Programer”
ASG
EMP PROJ
EMP.ENO = ASG.ENO ASG.PNO = PROJ.PNO
Hình 2.1b. Đồ thị nối của 2.1a
ASG
EMP PROJ
RESULT RESP
EMP.ENO = ASG.ENO ASG.PNO = PROJ.PNO
PNAME = “CAD/CAM”
ENAME TITLE = “Programmer”
DUR >= 36
Hình 2.1a. Đồ thị vấn tin
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Đồ thị vấn tin ở hình 2.2
Dựa vào đồ thị vấn tin ta thấy nó không liên thông. Ba trường hợp có thể xảy ra :
i. Loại bỏ ngay câu vấn tin trên.
ii. Giả định có một tích Descartes giữa quan hệ ASG và PROJ . iii. Suy ra vị trí nối bị thiếu ASG.PNO =PROJ.PNO
2.1.2. Loại bỏ dƣ thừa
Câu vấn tin của người sử dụng thường được diễn tả trên một khung nhìn có thể được bổ sung thêm nhiều vị từ để có được sự tương ứng khung nhìn - quan hệ, bảo đảm được tính toàn vẹn ngữ nghĩa và bảo mật. Khi bổ sung như vậy có thể sinh ra các vị trí dư thừa. Các vị trí dư thừa cần phải loại bỏ.
2.1.3. Viết lại câu vấn tin
Viết lại câu vấn tin bằng đại số quan hệ được chia làm hai bước như sau:
i/ Biến đổi câu vấn tin từ phép tính quan hệ thành đại số quan hệ ii/ Cấu trúc lại câu vấn tin đại số nhằm cải thiện hiệu năng.
Định nghĩa cây toán tử:
ASG
EMP PROJ
RESULT RESP EMP.ENO = ASG.ENO
PNAME = “CAD/CAM”
ENAME TITLE = “Programmer”
DUR >= 36
Hình 2.2 Đồ thị vấn tin không liên thông
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Một cây toán tử là cây với mỗi nút lá biểu thị cho một quan hệ được lưu trong cơ sở dữ liệu, nút không phải là lá biểu thị một quan hệ trung gian được sinh ra bởi phép toán quan hệ. Chuỗi các phép toán để đi theo hướng lá đến gốc, gốc biểu thị kết quả vấn tin.
Cách biến đổi câu vấn tin phép tính quan hệ trở thành một cây toán tử như sau:
i. Trước hết tạo ra các nút lá là các quan hệ trong SQL các nút lá nằm sau FROM.
ii. Nút gốc được tạo ra như phép chiếu chứa các thuộc tính kết quả, các thuộc tính này nằm sau SELECT.
iii. Lượng tử hoá (vị từ sau WHERE ) được chuyển thành các phép tính quan hệ thích hợp (phép chọn, phép nối ,…) đi từ các nút lá đến gốc. Chuỗi này có thể được cho trực tiếp qua thứ tự xuất hiện của các vị trí và các toán tử.
Sáu quy tắc tương đương hay dùng nhất sẽ được trình bày như sau đây:
Gọi R(A) │A={A1, …,An }; S(B) │B = {B1,…,Bn} và T là những quan hệ
i. Tính giao hoán của các phép toán hai ngôi:
Tích Descartes: R S S R (2.1.1)
Phép nối R S S R (2.1.2)
ii. Kết hợp của các phép toán hai ngôi:
Tích Descartes: (R S) T R (S T) (2.2.1)
Phép nối (R S) T R (S T) (2.2.2)
iii. Luỹ thừa đẳng của phép toán đơn ngôi:
Những phép chiếu liên tiếp trên cùng một quan hệ có thể được nhóm lại.
Ngược lại một phép chiếu trên nhiều thuộc tính có thể được tách ra thành nhiều phép chiếu liên tiếp nhau.
Số hóa bởi trung tâm học liệu http://lrc.tnu.edu.vn/
Gọi R(A) là quan hệ trên tập thuộc tính A, A’ A, A” A, A’ A”
thì A’( A’’(R)) A’( R) (2.3.1)
Nhiều phép chọn liên tiếp trên cùng một quan hệ có thể gộp thành phép chọn qua vị từ hội. Ngược lại, phép chọn qua một hội vị từ có thể tách ra thành nhiều phép chọn liên tiếp nhau.
Gọi pi là vị từ áp dụng cho thuộc tính Ai thì có:
P1(A1)( P2 (A2)(R)) P1(A1) P2(A2)(R) (2.3.2) iv. Giao hoán với phép chiếu
A1,…,An ( P(Ap)(R)) A1,…,An( P(Ap)( A1,…,An(R))) (2.4)
Chú ý rằng, nếu Ap là phần tử của {A1,…,An} thì phép chiếu cuối cùng trên {A1,…,An} ở vế phải của hệ thức sẽ không có tác dụng.
v. Giao hoán phép chọn với phép toán 2 ngôi
Phép chọn và tích Descartes có thể được giao hoán bằng các qui tắc sau:
(Ai R)
P(Ai)(R S) ( P(Ai)(R)) S (2.5.1)
Chọn và nối cũng có thể giao hoán:
P(Ai)(R S) P(Ai)(R) P(Aj,Bk)S (2.5.2) Chọn và hợp cũng có thể giao hoán nếu R và T có lược đồ giống nhau:
P(Ai) (R T) P(Ai)(R) P(Ai)(T) (2.5.3)
Chọn và hiệu cũng có thể được giao hoán tương tự.
vi. Giao hoán phép chiếu với phép toán hai ngôi.
Chiếu và tích Descartes có thể được giao hoán. Nếu C = A’ B’, trong đó A’ A, B’ B; A, B là các tập thuộc tính tương ứng của các quan hệ R và S, thì :
C(R S) A’(R) B’(S) (2.6.1)
Chiếu và nối cũng có thể giao hoán:
C(R P(Aj,B k)S) A’(R) P(Ai,Bj) B’(S) (2.6.2)
P(Aj,B k)