Bài giảng Phân hóa vân tin và cục bộ hóa dữ liệu

CHƯƠNG V PHÂN HOÁ VẤN TIN VÀ CỤC BỘ HOÁ DỮ LIỆU 8.1. Phân rã vấn tin Phân rã (PR) vấn tin là một giai đoạn đầu tiên của quá trình xử lý câu vấn tin,nó biến đổi câu vấn tin dạng phép tính quan hệ thành câu vấn tin đại số quan hệ. Các vấn tin nhập xuất đều tham chiếu đến các quan hệ toàn cục và không dùng đến các thông tin về phân bố dữ liệu ,vì thế phân rã vấn tin giống nhau trong cả hệ tập trung lẫn phân tán . Các bước phân rã vấn tin gồm : chuẩn hoá; phân tích; loại bỏ dư thừa và viết lại câu vấn tin . 8.1.1. Chuẩn hoá Mục đích chuẩn hoá là bíên đổi câu vấn tin thành dạng chuẩn để tiếp tục xử lý với các ngôn ngữ quan hệ như SQL ,biểu đồ quan trọng nhất là lượng trì hoá vấn tin(query quali-fication) (mệnh đề WHERE) ,có thể là một vị từ phi lượng tử với độ phức tạp nào đó với tất cả các lượng từ cần thiết như "-với mọi, $-tồn tại được đặt phía trước . Dạng chuẩn hội(Conjunctive normal form) là hội(^) của các tuyển(v) Ví dụ : (p11 v p12 v … v p1n)^…^(pm1 v pm2 v …pnm) Trong đó : p là vị trí đơn giản . Dạng chuẩn tuyển (disjunction normal from) là tuyển của các hội. Ví dụ: (p11^p12^…^p1n) v …v(pm1^pm2^…^pmn) Các quy tắc (^ ≡ AND, v ≡ OR, ┐ ≡ NOT) P1 ^ P2 ↔ P2 ^ P1 P1 v P2 ↔ P2 v P1 P1 ^ ( P2 ^ P3) ↔ ( P1 ^ P2) ^ P3 P1 v (P2 v P3) ↔ (P1 v P2) v P3 P1 ^ ( P2 v P3) ↔ (P1 v P2) v (P1 v P3) P1 v (P2 ^ P3) ↔ ( P1 v P2) ^(P1 v P3) ┐( P1 ^ P2) ↔ ┐P1 v ┐P2 ┐(P1 v P2) ↔ ┐P1 ^ ┐P2 ┐(┐P)↔P Dạng chuẩn hội thường được sử dụng trong thực tế bởi vì các lượng từ hoá vấn tin thường chứa nhiều vị từ AND hơn vị từ OR .Tuy nhiên nó cũng lặp lại nhiều vị từ cho các câu vấn tin có nhiều tuyển và ít hội. Ví dụ 8.1-1 : Tìm tên các nhân viên đang làm ở dự án P1trong 12 hoặc 24 tháng. Câu vấn tin bằng SQL như sau: SELECT ENAME FROM EMP, ASG WHERE EMP.ENO = AGS.ENO AND ASG.PNO = “P1” AND DUR =12 OR DUR = 24 Lượng từ hoá chuẩn hội là : (EMP.ENO =ASG.ENO)^ (ASG.PNO = “P1”)^((DUR=12) OR (DUR=24)) Còn lượng tử hóa chuẩn tuyển là : { (EMP.ENO =ASG.ENO)^ (ASG.PNO = “P1”)^(DUR=12) } v { (EMP.ENO =ASG.ENO)^ (ASG.PNO = “P1”)^(DUR=24) } 8.1.2. Phân tích Ví dụ 8.1-2: Tìm tên 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. Câu vấn tin bằng SQL như sau : SELECTS EMANE , RESP FROM ẸMP, ASG,PROJ WHERE EMP.ENO = ASG.ENO AND ASG.PNO =PROJ.PNO AND PNAME = “CAD/CAM” AND DVR ³ 36 AND TITLE = “Programmer” Đồ thị vấn tin cho câu vấn tin trên là:  ASG EMP PROJ RESULT RESP EMP.ENO = ASG.ENO ASG.PNO = PROJ.PNO PNAME = “CAD/CAM” ENAME TITLE = “Programmer” DUR³36 Hình 8.1-1. Đồ thị vấn tin Đồ thị nối của đồ thị vấn tin là đồ thị ở hình 8.1-1a ASG EMP PROJ EMP.ENO = ASG.ENO ASG.PNO = PROJ.PNO Hình 8.1-1b. Đồ thị nối của 8.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ỏ. Ví dụ 8.1-4: SELECT ENAME,RESP FROM EMP, ASG,PROJ WHERE EMP.ENO =ASG.ENO AND ASG.ENO = PROJ.PNO AND PNAME=”CAD/CAM” AND DUR > =36 AND TITLE = “PROGRAM” Đồ thị vấn tin ở 8.1-2 ASG EMP PROJ RESULT RESP EMP.ENO = ASG.ENO PNAME = “CAD/CAM” ENAME TITLE = “Programmer” DUR³36 Hình 8.1-2 Đồ thị vấn tin không liên thông 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. 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 8.1.3 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ỏ. Người ta có thể loại bỏ vị trí dư thừa khi áp dụng các quy tắc luỹ đẳng sau : P ^ P = P P v P = P P ^ T = P P v F = P P ^ F = F P v F = T P ^ ┐P = F P v ┐P = T P1 ^ (P1 v P2) = P1 10 .P1 v (P1 ^ P2) = P1 Ví dụ:8.1.3_1: Câu SQL: SELECT TITLE FROM EMP WHERE (NOT(TITLE=”progarmmer”)) AND (TITLE=”Progarmmer” OR TITLE=”Elect.Eng.” AND NOT(TITLE= “Elect.Eng.”) OR ENAME = “J.Doe” Có thể đơn giản hoá nhờ các quy tắc trên và trở thành SELECT TITLE FROM EMP WHERE ENAME= “J.Doe” Đặt P1 = TITLE=”program” P2= TITLE=”Elect.Eng.” P3=ENAME=”J.Doe” Thì câu SQL viết lại (┐P1^(P1 v P2)^┐P2) v P3=P3 Theo quy tắc luỹ đẳng 5 Vì (┐P1^(P1 v P2)^┐P2) v P3= (┐P1^((P1 ^ ┐P2) v (P2 ^ ┐P2)) v P3=(┐P1^P1^ ┐P2) v P3 Áp dụng quy tắc 7 → (F ^ P2) v (┐P1 ^ F) v P3↔F v F v P3↔P3. 8.1.4 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ỏ i/Biến đổi câu vấn tin từ phép tính quan hệ thành đại số quan hệ và ii/Cấu trúc lại câu vấn tin đại số nhằm cải thiện hiệu năng. Một cây toán tử là một 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á (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ử. Ví dụ :8.1.4_1: Tìm tên các nhân viên, trừ J.Doe đã làm cho dự án CAD/CAM trong một hoặc hai năm Câu SQL là : SELECT ENAME {Gốc } FROM ASG.ENO=EMP.ENO AND ENAME ≠ “J.Doe” AND PROJ.PNAME= “CAD/CAM” AND (DUR=12 OR DUR=24) Cây toán tử như sau (hình 8.1.4_1): Qua áp dụng quy tắc biến đổi , có thể có cây tương đương với cây ở 8.1.4_1. 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. Giao hoán phép toán: R*S « S*R; R wvS « SwvR ii. Kết hợp: (R*S)*T « R*(S*T) (RwvS) wvT « Rwv (SwvT) 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. 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) Nhiều phép chọn liên tiếp sP(A1) trên cùng một quan hệ, trong đó Pi là một vị từ áp dụng cho thuộc tính Ai thì có thể được nhóm lại như sau: sP1(A1) (sP2(A2)(R)) « sP1(A1) Ç P2(A2) 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. sDUR=12 Ú DUR=24 sPNAME = ”CAD/CAM” sENAME ¹ ”J.Doe” wvPNO wv PROJ ASG EMP Hình 8.1.4 – 1. Ví dụ về cây toán tử ÕENAME Chọn Nối Chiếu iv. Giao hoán với phép chiếu ÕA1,…,An (sP(Ap)(R)) « ÕA1,…,An (sP(Ap)(ÕA1,…,An(R))) 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) sP(Ai)(R*S) « (sP(Ai)(R))*S Chọn và nối cũng có thể giao hoán: sP(Ai)(RwvP(Aj,Bk)S) « sP(Ai)(R)wvP(Aj,Bk)S Chọn và hợp cũng có thể giao hoán nếu R và T có lược đồ giống nhau: sP(Ai)(RÈT) « sP(Ai)(R) È sP(Ai)(T) 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) Chiếu và nối cũng có thể giao hoán: ÕC(RwvP(Aj,Bk)S) « ÕA’(R)wvP(Ai,Bj)ÕB’(S) Để vế phải đúng, cần phải có Ai Î A’, Bj Î B’. Bởi vì C = A’ÈB’ nên Ai và Bj Î C vì thế chúng ta không cần chiếu lên C một khi đã chiếu trên A’ và B’. Chiếu và hợp cũng có thể được giao hoán như sau: ÕC(RÈS) « ÕC(R)ÈÕC(S) Chiếu và hiệu có thể được giao hoán tương tự. Áp dụng 6 qui tắc trên, cho phép tạo ra nhiều cây tương đương. Ví dụ. Cây ở hình 8.1.4 – 1 tương đương với cây sau: sPNAME = ”CAD/CAM” Ù (DUR=12 Ú DUR=24) Ù ENAME ¹ ”J.Doe” wvPNO wv PROJ ASG EMP Hình 8.1.4 – 2. Cây tương đương ÕENAME Có thể viết lại cây toán tử này như sau để tránh tích Descartes: wvPNO sPNAME = ”CAD/CAM” sENAME ¹ ”J.Doe” PROJ ASG EMP Hình 8.1.4 – 3. Cây toán tử đã được viết lại ÕENAME ÕPNO,ENAME wvENO ÕPNO,ENO ÕENO,ENAME sDUR=12 Ú DUR=24 ÕPNO 8.2. Cục bộ hoá dữ liệu phân tán Tầng cục bộ hoá dữ liệu (mục 5.5 chương 5) chịu trách nhiệm dịch câu vấn tin đại số trên quan hệ toàn cục sang câu vấn tin đại số trên các mảnh vật lý. Cục bộ hoá có sử dụng các thông tin được lưu trong lược đồ phân mảnh. Một cách cục bộ hoá (Cbh) một vấn tin phân tán khá thô sơ là tạo ra một câu vấn tin trong đó mối quan hệ toán cục được thay bằng chương trình cục bộ hoá của nó. Chương trình cục bộ hoá là một chương trình đại số quan hệ mà các toán hạng là các quan hệ nó được dùng để xây dựng lại quan hệ toàn cục dựa trên qui tắc tái thích. Tuy nhiên cách làm này không hiệu quả vì nhiều tái thiết cấu trúc. Vì vậy chúng ta sẽ dùng các kỹ thuật rút gọn. 8.2.1. Rút gọn cho phân mảnh ngang nguyên thuỷ. Phân mảnh ngang một quan hệ dựa trên các vị từ chọn. Ví dụ 8.2.1 – 1: EMP1 = sENO £ “E3” (EMP) EMP2 = s“E3” < ENO £ “E6” (EMP) EMP3 = s ENO > “E6” (EMP) Chương trình cục bộ hoá cho quan hệ phân mảnh ngang trên là hợpcác mảnh lại: EMP = EMP1 È EMP2 È EMP3 Vì vậy dạng vấn tin gốc được xác định trên EMP sẽ thu được nhờ thay EMP bởi EMP1 È EMP2 È EMP3 Rút gọn vấn tin trên các quan hệ phân mảnh ngang chủ yếu là xác định, sau khi đã tái cấu trúc lại cây con, xem cây nào tạo ra quan hệ rỗng thì bỏ cây con đó đi. Rút gọn với phép chọn: Nếu chọn trên các mảnh có lớp từ mâu thuẫn với lượng từ hoá của qui tắc phân mảnh sẽ sinh ra các quan hệ rỗng. Cho quan hệ R được phân mảnh ngang thành R1, R2,…, Rn trong đó Rj = s Pi(R). Qui tắc 1: s Pi(Rj) = Æ nếu "x Î R: Ø(Pi(x) Ù Pj(x)) Trong đó Pi và Pj là các vị trí chọn x biểu thị cho một bộ, P(x) biểu thị cho “vị từ p đúng với x”. Ví dụ: Vị từ chọn ENO = “E1” mâu thuẫn với các vị trí các mảnh EMP2 và EMP3 (Nghĩa là không có bộ nào trong EMP2 và EMP3 thoả vị từ chọn ENP = “E1”). Ví dụ 8.2.1 – 2. Rút gọn co phân mảnh ngang bằng cách dùng câu vấn tin mẫu sau: SELECT * FROM EMP WHERE ENO = “ES” Hình 8.2.1 – 1. Rút gọn cho phân mảnh ngang (với phép chọn) (b) vấn tin đã rút gọn sENO = “E5” EMP2 (a) vấn tin gốc sENO = “E5” EMP1 EMP3 EMP2 Áp dụng các tiếp cận đơn giản, dễ cục bộ hoá EMP từ EMP1, EMP2 và EMP3 cho ra câu vấn tin gốc (hình 8.2.1 – 1a). Bằng cách hoán vị phép chọn với phép lượng, sinh ra vị từ chọn ENO = “E5” mâu thuẫn với các vị từ phân mảnh EMP1, EMP3 do vậy tạo ra quan hệ rỗng. Câu vấn tin rút gọn chỉ được áp dụng trên EMP2 (như hình 8.2.1 – 1b). Rút gọn và phép nối Nối trên các quan hệ phân mảnh ngang có thể được đơn giản khi các quan hệ nối được phân mảnh theo thuộc tính nối. Đơn giản hoá gồm phân phối các nối trên các hợp rồi bỏ đi các nối vô dụng. Phân phối nối trên hợp có dạng: (R1 È R2) wv S = (R1 wv S) È (R2 wv S) Trong đó, Ri là các mảnh của R, còn S là một quan hệ. Giả sử các mảnh Ri và Rj được định nghĩa tương ứng với các vị từ Pi và Pj trên cùng một quan hệ, qui tắc đơn giản hoá có thể được phát triển như sau: Qui tắc 2: Ri wv Rj = Æ nếu "x Î Ri, "y Î Rj: Ø(P(x) Ù P(x)) Ví dụ 8.2.1 – 3: Giả sử EMP được phân mảnh thành EMP1, EMP2 và EMP3 như ví dụ 8.2.1 – 1 và quan hệ ASG được phân mảnh ngang như sau: ASG1 = sENO £ “E3” (ASG) ASG2 = s ENO > “E3” (ASG) Như vậy EMP1 và ASG1 được định nghĩa bởi cùng một vị từ. Ngoài ra vị từ định nghĩa ASG2 là hợp của các vị từ định nghĩa mảnh EMP2 và EMP3. Bây giờ xét câu vấn tin SELECT * FROM EMP, ASG WHERE EMP.ENO = ASG.ENO Câu vấn tin gốc tương đương được trình bày trong hìn 8.2.1 – 2a. Câu vấn tin rút gọn bằng cách phân phối các nối trên hợp và việc áp dụng qui tắc 2 ở hình 8.2.1 – 2b. Hình 8.2.1 – 2. Rút gọn cho phân mảnh ngang (với nối) wvENO EMP1 EMP2 EMP3 ASG1 ASG2 wv wv wv EMP1 ASG1 EMP2 ASG2 EMP3 ASG2 (a) vấn tin gốc (b) vấn tin đã rút gọn 8.2.2. Rút gọn cho phân mảnh dọc Phân mảnh dọc phân tán một quan hệ dựa trên các thuộc tính chiếu. Toán tử tái xây dựng các mảnh dọc là nối, chương trình cục bộ hoá cho một quan hệ phân mảnh dọc là nối, chương trình cục bộ hoá cho một quan hệ phân mảnh dọc gồm có nối của các mảnh theo thuộc tính chung. Ví dụ 8.2.2 – 1: Giả sử EMP được phân thành hai mảnh dọc như sau, trong đó thuộc tính khoá ENO được nhân đôi: EMP1 = ÕENO,ENAME(EMP) EMP2 = ÕENO,TITLE(EMP) Chương trình cục bộ hoá sẽ là: EMP = EMP1 wvENO EMP2 Qui tắc 3: Cho quan hệ R(A) | A = {A1, …, An} và được phân mảnh thành các mảnh dọc Ri = ÕA’(R) | A’ Í A. Qui tắc phát biểu như sau: ÕD,K(Ri) là vô dụng nếu các thuộc tính chiếu D không thuộc A’. Ví dụ 8.2.2 – 2: Cho câu vấn tin trong SQL: SELECT ENAME FROM EMP Được mảnh EMP1, mảnh còn lại là EMP2 (khi kết hợp với các thuộc tính khoá) câu vấn tin gốc tương đương trên EMP1 và EMP2 được cho trên hình 8.2.2 – 1a, câu vấn tin rút gọn trên hình 8.2.2 – 1b sau khi hoán vị phép chiếu với phép nối (tức là chiếu trên ENO, ENAME), chúng ta thấy EMP2 là vô dụng vì ENAME không thuộc EMP2. ÕENAME ÕENAME wvENO EMP1 EMP2 EMP1 (a) vấn tin gốc (b) vấn tin đã rút gọn Hình 8.2.2 – 1. Rút gọn cho phân mảnh dọc 8.2.3. Rút gọn cho phân mảnh dẫn xuất Chúng ta thấy rằng, nếu quan hệ R phải phan mảnh dẫn xuất theo quan hệ S, thì các mảnh của R và S có giá trị giống nhau ở thuộc tính nối sẽ nằm cùng vị trí. Ngoài ra, S có thể được phân mảnh theo vị trừ chọn. Bởi vì các bộ của R được đặt tuỳ theo các bộ của S, phân mảnh dẫn xuất chỉ sử dụng cho mối liên hệ 1 – n có dạng S à R, trong đó một bộ của S có thể khớp với nhiều bộ của R, nhưng một bộ của R chỉ khớp với một bộ của S. Ví dụ 8.2.3 – 1: Giả sử EMP được phân mảnh ngang (xem chương 3) thành EMP1 và EMP2 như sau: EMP1 = sTITLE = ”programmer”(EMP) EMP1 = sTITLE ¹ ”programmer”(EMP) Phân mảnh dẫn xuất ASG được thực hiện như sau: ASG1 wvENO EMP1 ASG2 wvENO EMP2 Chương trình cục bộ hoá cho quan hệ phân mảnh ngang là hợp của các mảnh. Tức: ASG = ASG1 È ASG2 Các câu vấn tin trên các mảnh dẫn xuất cũng có thể được rút gọn theo Qui tắc 2. Bởi vì qui tắc phân mảnh chỉ rõ các bộ sẽ khớp với nhau, một số nối sẽ sinh ra quan hệ rỗng nếu các vị trí phân mảnh có mâu thuẫn. Ví dụ các vị từ của ASG và EMP2 mâu thuẫn, vì thế: ASG1 wv = Æ Ví dụ 8.2.3 – 2: Rút gọn theo mảnh dẫn xuất được minh hoạ bằng cách dùng câu vấn tin SQL truy xuất tất cả các thuộc tính từ EMP và ASG có cùng giá trị của ENO và chức vụ là: TITLE = “Mech.Eng”. SELECT * FROM EMP, ASG WHERE ASG.ENO = EMP.ENO AND TITLE = “Mech.Eng” Các mảnh EMP1, EMP2, ASG1, ASG2 ở ví dụ 8.2.3 – 1. Câu vấn tin gốc trong hình 8.2.3 – 1a. wvENO ASG1 EMP1 ASG2 (8.2.3 - 1a) vt gốc (EMP1 không có “Mech.Eng” (8.2.3 - 1b) Hình 8.2.2 – 1. Rút gọn cho phân mảnh dọc EMP2 sTITLE = ”Mech.Eng” wvENO ASG1 ASG2 sTITLE = ”Mech.Eng” EMP2 Bằng cách dùng phép chọn (giao hoán) xuống các mảnh EMP1 và EMP2 do vị từ chọn mâu thuẫn với vị từ phân mảnh EMP1 và vì thế loại bỏ EMP1 nên ta có câu vấn tin mới ở hình 8.2.3 – 1b. Để phát hiện các vị trí mâu thuẫn, chúng ta phân phối các nối trên các hợp. Kết quả là cây 8.2.3 – 1c. wvENO wvENO ASG1 EMP2 sTITLE = ”Mech.Eng” ASG2 EMP2 sTITLE = ”Mech.Eng” wvENO sTITLE = ”Mech.Eng” ASG2 EMP2 (8.2.3 – 1c) Cây con bên trái (của 8.2.3 – 1c) nối hai mảnh ASG1 và EMP2 với các lượng từ mâu thuẫn do vị từ TITLE = “programmar” trong ASG1 và TITLE ¹ “programmer” trong EMP2 vì thế ta có thể bỏ qua cây cọn trai. Kết quả cuối cùng ở hình 8.2.3 – 1d. 8.2.4. Rút gọn mảnh hỗn hợp Ví dụ 8.2.4 – 1: Ba mảnh sau được phân mảnh hỗn hợp từ quan hệ EMP EMP1 = sENO £ “E4” (ÕENO,ENAME(EMP)) EMP2 = s ENO > “E4” (ÕENO,ENAME(EMP)) EMP3 = ÕENO,TITLE(EMP) Chương trình cục bộ hoá sẽ là: EMP = (EMP1 È EMP2) wvENO EMP3 Các câu vấn tin trên các mảnh hỗn hợp có thể được rút gọn bằng cách tổ hợp các qui tắc tương ứng đã được dùng trong các phân mảnh ngang, dọc, và ngang dẫn xuất, có thể tóm tắt các qui tắc như sau: 1. Loại bỏ các quan hệ rỗng được tạo ra bởi các phép chọn mâu thuẫn trên các mảnh ngang. 2. Loại bỏ các quan hệ vô dụng được tạo ra bởi các phép chiếu trên các mảnh dọc. 3. Phân phối các nối cho các hợp nhằm cô lập và loại bỏ các nối vô dụng. Ví dụ 8.2.4 – 2: Câu vấn tin SQL sau minh hoạ cách áp dụngÕENO,ENAME sENO = “E5” wvENO EMP3 EMP1 EMP2 Qui tắc 1 và Qui tắc 2 cho phân mảnh ngang - dọc của quan hệ EMP thành EMP1, EMP2 và EMP3 được cho ở trên. SELECT ENAME FROM EMP WHERE ENO = “ES” Câu vấn tin gốc ở hình 8.2.4 – 1(a) có thể được rút gọn bằng cách trước tiên đẩy phép chọn xuống để loại bỏ EMP1, đẩy phép chiếu xuống để loại EMP3. Câu vấn tin rút gọn cuối cùng là: ÕENO,ENAME sENO = “E5” EMP2