Phân mảnh - phân mảnh ngang
Đề tài: Phân mảnh – Phân mảnh ngang Giảng viên hướng dẫn: TS Phạm Thế Quế Sinh viên thực hiện: Nhóm – Lớp D07CNTT3 LOGO Nội dung Phân mảnh Phân mảnh ngang Kết luận Company Logo I Phân mảnh Phân mảnh gì? Là việc chia quan hệ thành nhiều quan hệ nhỏ gọi phân mảnh quan hệ MASP D1 D2 D3 D4 MASP D1 D4 TenSP Bút bi Bút mực Vở Sách MASP TenSP TenSP GiaTien ChatLuong D1 Bút bi D2 Bút mực Vở BútD3 bi 1.000 Tốt D4 Sách Sách 9.000 Tốt GiaTien ChatLuong 1.000 2.000 8.000 9.000 Tốt xấu TB Tốt MASP GiaTien MASP D1 D2 D2 D3 D3 D4 TenSP 1.000 2.000 Bút mực 8.000 Vở 9.000 ChatLuong GiaTien Tốt xấu 2.000 TB 8.000 Tốt ChatLuong xấu TB Company Logo Lý phân mảnh: - Việc phân rã quan hệ thành mảnh cho phép giao dịch đồng thời mảnh - Tăng hiệu hệ thống; câu truy vấn chia nhỏ thành câu truy vấn thực song song MASP D1 D2 TenSP Bút bi Bút mực MASP D3 D4 TenSP Vở Sách Giá tiền Chất lượng 1.000 2.000 Tốt xấu Giá tiền Chất lượng 8.000 9.000 TB Tốt Company Logo Các quy tắc phân mảnh Company Logo Tính đầy đủ: Nếu quan hệ R phân rã thành mảnh R1, R2, , Rk mục liệu có R phải có mảnh Ri Phân mảnh ngang: mục liệu (1 hàng) Phân mảnh dọc: mục liệu thuộc tính (1 cột) Company Logo Tính tái thiết lập: Nếu quan hệ R phân rã thành mảnh R1, R2, , Rk phải tồn toán tử θ cho R = θ(Ri), ∀i Toán tử θ thay đổi tùy theo loại phân mảnh Ví dụ: SanPham1=σ ChatLuong=’Tốt’ (SanPham) SanPham2=σ ChatLuong=’Xấu’ (SanPham) SanPham3= σ ChatLuong=’TB’ (SanPham) SanPham4=Π MaSP,TenSP (SanPham) SanPham5=ΠMaSP,GiaTien,ChatLuong(SanPham) SanPham=SanPham1 ∪ SanPham2 ∪ SanPham3 SanPham=SanPham4 SanPham5 Company Logo Tính tách biệt: Cho tập R phân rã thành mảnh R1, R2, , Rk Nếu phân mảnh ngang: ∀u ∈Ri,∀ i≠ kvà i, k∈[1, n]: u∉ Rk Nếu phân mảnh dọc: Thuộc tính chung (khóa) phải lặp lại, thuộc tính riêng tồn tại mảnh Company Logo Các kiểu phân mảnh Các kiểu phân mảnh Phân Mảnh Dọc Phân Mảnh Ngang Phân Mảnh Hỗn Hợp Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.1 Vị từ: — Là biểu thức có giá trị logic Ví dụ: Giá tiền > 8000 ˄ Chất lượng = ‘Tốt’ Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.2 Vị từ hội sơ cấp Định nghĩa: Cho R Pr={p1, p2, …,pm} ta định nghĩa Mi={m i1,m i2,…,m iz} sau: m i={ mij|mij = ∧pik∈Pr pik* }, 1≤k≤m, 1≤j≤z pik* = pjk or pjk* = ¬(pjk) ⇒Ý nghĩa: Vị từ hội sơ cấp hội vị từ đơn giản hay phủ định vị từ đơn giản Ví dụ: m1: TENSP=“Bút bi“ ˄ Giá tiền≤5000 m2: NOT(TENSP=“Bút bi") ˄ Giá tiền≤5000 Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.3 Liên đới • Xét thực thể • Xét thuộc tính: – Sự ràng buộc thuộc tính • Xét mảnh: – Mảnh f phân thành mảnh nhỏ f1 f2 – Mảnh f liên đới tồn ứng dụng truy cập đến f1 f2 theo cách khác Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.4 Vị từ đơn giản có tính đầy đủ Tập vị từ đơn giản Pr đầy đủ xác suất truy nhập ứng dụng tới mảnh hội sơ cấp định nghĩa theo Pr MASP TenSP GiaTien ChatLuong D1 D4 Bút bi Sách 1.000 9.000 Tốt Tốt MASP TenSP GiaTien ChatLuong D2 Bút mực 2.000 xấu MASP TenSP GiaTien ChatLuong D3 Vở 8.000 TB Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.5 Vị từ đơn giản có tính cực tiểu Nếu tất vị từ tập Pr có liên đới tập Pr gọi cực tiểu Company Logo Các bước thực phân mảnh: Tìm tập vị từ đơn giản Tìm hội vị từ sơ cấp Loại bỏ mảnh vô nghĩa Xác Định Tập Vị Từ Đầy Đủ Và Cực Tiểu COM_MIN Input: R: quan hệ; Pr : Tập vị từ đơn giản Output : Pr’ : tập vị từ đầy đủ cực tiểu Begin Tìm vị từ pi Pr cho pi phân hoạch R theo quy tắc ∈ ∈ Pr’ pi Pr pr – pi F fi ∈ Do Begin Tim p∈j Pr cho pj phân hoạch mảnh fk Pr’ theo quy tắc If∃ p∈ Pr’ , vị từ liên đới then k Begin Pr’ Pr’ – pk F F- fk End_if End_begin Until Pr’ đầy đủ Tìm tập vị từ hội sơ cấp loại mảnh vô nghĩa PHORIZONTAL Đầu vào: R quan hệ, Pr tập vị từ đơn giản Đầu : M tập vị từ hội sơ cấp Begin PR’ = COM_MIN(R,Pr) Tính tập M vị từ hội sơ cấp từ Pr’ Tính tập I phép kéo theo Pi ∈ Pr’∈ For mi ∈ ∈ M Do If mi mâu thuẫn với I then M = M – {mi} End – if End Ví dụ: SanPham( MaSP, TenSP,GiaTien,ChatLuong) MASP TenSP GiaTien ChatLuong D1 Bút bi 1.000 Tốt D2 Bút mực 2.000 Xấu D3 Vở 8.000 TB D4 Sách 9.000 Tốt Giả sử có ứng dụng tìm tên sản phẩm theo chất lượng theo giá sản phẩm Ta có vị từ đơn giản p1: ChatLuong = “Tốt” p2: ChatLuong = “TB” p3: ChatLuong = “Xấu” p4: GiaTien>=8000 p5:GiaTien=8000 MASP D1 TenSP Bút bi GiaTien ChatLuong MASP 1.000 Tốt D4 TenSP Sách GiaTien ChatLuong 9.000 Tốt Company Logo Ta thấy: Pr’= {p1,p2,p4} Pr={p3,p5} F chứa mảnh tách Kiểm tra lại Pr’ thấy tất vị từ liên đới đầy đủ ⇒ Các mảnh hội sơ cấp sinh ra: m1=(p1∧ ¬p4) m2=(p1∧ p4) m3=(¬p1∧¬p2∧¬ p4) m4=(p2∧ p4) Company Logo m1=(p1∧ ¬p4) (sản phẩm tốt NOT >=8000) MASP m2=(p1∧ p4) D1 TenSP Bút bi (sản phẩm tốt >=8000) m3=(¬p1∧¬p2∧¬ p4) (NOT tốt,NOT TB, NOT>=8000) MASP D4 TenSP Sách GiaTien ChatLuong 1.000 Tốt GiaTien ChatLuong 9.000 Tốt m4=(p2∧ p4) (Sản phẩm TB, Giá >=8000) MASP TenSP GiaTien D2 Bút mực 2.000 MASP D3 TenSP Vở GiaTien 8.000 ChatLuong xấu ChatLuong TB Company Logo Thuật toán dừng Pr’={p1, p2, p4} Company Logo LOGO [...]... Company Logo II Phân mảnh ngang 1 Các khái niệm liên quan đến phân mảnh ngang: 1.3 Liên đới • Xét các thực thể • Xét các thuộc tính: – Sự ràng buộc giữa các thuộc tính • Xét trên các mảnh: – Mảnh f phân thành mảnh nhỏ f1 và f2 – Mảnh f liên đới khi tồn tại ứng dụng truy cập đến f1 và f2 theo các cách khác nhau Company Logo II Phân mảnh ngang 1 Các khái niệm liên quan đến phân mảnh ngang: 1.4 Vị từ...II Phân mảnh ngang 1 Các khái niệm liên quan đến phân mảnh ngang: 1.1 Vị từ đơn giản Là biểu thức gồm: – Toán hạng 1: là một thuộc tính Ai ∈ R – Toán hạng 2: là giá trị của Ai của thuộc Di – Toán tử: =,,≥,≠ Ví dụ: P1={ TENSP=‘Bút mực’} P2={ GiaTien < 5.000} P3={ ChatLuong=‘Tốt’} Company Logo II Phân mảnh ngang 1 Các khái niệm liên quan đến phân mảnh ngang: 1.2 Vị từ hội sơ... suất truy nhập bởi mỗi ứng dụng tới bộ bất kỳ của một mảnh hội sơ cấp bất kỳ được định nghĩa theo Pr là như nhau MASP TenSP GiaTien ChatLuong D1 D4 Bút bi Sách 1.000 9.000 Tốt Tốt MASP TenSP GiaTien ChatLuong D2 Bút mực 2.000 xấu MASP TenSP GiaTien ChatLuong D3 Vở 8.000 TB Company Logo II Phân mảnh ngang 1 Các khái niệm liên quan đến phân mảnh ngang: 1.5 Vị từ đơn giản có tính cực tiểu Nếu tất cả các... bước thực hiện phân mảnh: Tìm tập vị từ đơn giản Tìm các hội vị từ sơ cấp Loại bỏ các mảnh vô nghĩa Xác Định Tập Vị Từ Đầy Đủ Và Cực Tiểu COM_MIN Input: R: quan hệ; Pr : Tập các vị từ đơn giản Output : Pr’ : tập vị từ đầy đủ và cực tiểu Begin Tìm một vị từ pi Pr sao cho pi phân hoạch R theo quy tắc 1 ∈ ∈ Pr’ pi Pr pr – pi F fi ∈ Do Begin Tim một p∈j Pr sao cho pj phân hoạch một mảnh fk của Pr’... thuật toán COM_MIN: Khởi tạo: Pr={p1,p2,p3,p4,p5} Pr’= Ø F=Ø Quan hệ R là bảng Bắt đầu: p1 phân hoạch R theo quy tắc 1 Pr’={p1} Pr={p2, p3, p4, p5} Vòng lặp: Vòng 1: Ta có các mảnh hội sơ cấp Company Logo MASP D1 D4 MASP D2 TenSP GiaTien ChatLuong MASP Bút bi 1.000 Tốt D2 Sách 9.000 Tốt D3 Xét p2: ChatLuong = “TB”, p2 phân hoạch được TenSP Ta có: Bút mực GiaTien ChatLuong Pr’={p1,p2}xấu 2.000 TenSP GiaTien... fi ∈ Do Begin Tim một p∈j Pr sao cho pj phân hoạch một mảnh fk của Pr’ theo quy tắc 1 If∃ p∈ Pr’ , một vị từ không có liên đới then k Begin Pr’ Pr’ – pk F F- fk End_if End_begin Until Pr’ đầy đủ Tìm tập các vị từ hội sơ cấp và loại đi các mảnh vô nghĩa PHORIZONTAL Đầu vào: R là một quan hệ, Pr tập vị từ đơn giản Đầu ra : M là tập các vị từ hội sơ cấp Begin PR’ = COM_MIN(R,Pr) Tính tập M các vị từ... 2.000 8.000 xấu TB MASP TenSP GiaTien ChatLuong D3 Vở 8.000 TB Pr={p3, p4, p5} F các mảnh đã được tách Nhận thấy: tập Pr’thấy tất cả đều liên đới nhưng Pr’ chưa đầy đủ Company Logo Vòng 2: Pr’={p1,p2} MASP D1 D4 MASP D2 TenSP GiaTien TenSP Bút bi Sách ChatLuong GiaTien ChatLuong 1.000 9.000 Tốt Tốt MASP p3: ChatLuong không phân hoạch BútXét mực 2.000 = “Xấu” ; p3 xấu D3 TenSP GiaTien ChatLuong Vở 8.000... GiaTien>=8000 MASP D1 TenSP Bút bi GiaTien ChatLuong MASP 1.000 Tốt D4 TenSP Sách GiaTien ChatLuong 9.000 Tốt Company Logo Ta thấy: Pr’= {p1,p2,p4} Pr={p3,p5} F chứa các mảnh đã được tách Kiểm tra lại Pr’ thấy tất cả các vị từ đều liên đới và đầy đủ ⇒ Các mảnh hội sơ cấp được sinh ra: m1=(p1∧ ¬p4) m2=(p1∧ p4) m3=(¬p1∧¬p2∧¬ p4) m4=(p2∧ p4) Company Logo m1=(p1∧ ¬p4) (sản phẩm tốt và NOT >=8000) MASP m2=(p1∧ p4) D1 ... Company Logo Các kiểu phân mảnh Các kiểu phân mảnh Phân Mảnh Dọc Phân Mảnh Ngang Phân Mảnh Hỗn Hợp Company Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.1 Vị từ: — Là...Nội dung Phân mảnh Phân mảnh ngang Kết luận Company Logo I Phân mảnh Phân mảnh gì? Là việc chia quan hệ thành nhiều quan hệ nhỏ gọi phân mảnh quan hệ MASP D1 D2 D3 D4 MASP... Logo II Phân mảnh ngang Các khái niệm liên quan đến phân mảnh ngang: 1.3 Liên đới • Xét thực thể • Xét thuộc tính: – Sự ràng buộc thuộc tính • Xét mảnh: – Mảnh f phân thành mảnh nhỏ f1 f2 – Mảnh