Tài liệu Các kỹ thuật phân mảnh, gộp nhóm trong csdl phân tán

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TÔ NGỌC ANH CÁC KỸ THUẬT PHÂN MẢNH, GỘP NHÓM TRONG CSDL PHÂN TÁN LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2013 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ạo ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG TÔ NGỌC ANH CÁC KỸ THUẬT PHÂN MẢNH, GỘP NHÓM TRONG CSDL PHÂN TÁN 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://www.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 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 TÔ NGỌC ANH Số hóa bởi Trung tâm Học liệu http://www.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 12 năm 2013 Tác giả Tô Ngọc Anh Số hóa bởi Trung tâm Học liệu http://www.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 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 ....................................................................................2 1.1. GIỚI THIỆU VỀ LOGIC .....................................................................................2 1.2.TỔNG QUAN VỀ CSDL PHÂN TÁN .................................................................7 1.2.1.Các phƣơng pháp phân mảnh cơ bản. ............................................................8 1.2.2. Các lệnh phân mảnh cơ bản dựa vào câu SQL. ...........................................19 1.3. KẾT LUẬN CHƢƠNG 1. ..................................................................................20 Chƣơng 2: PHÂN MẢNH VÀ GỘP NHÓM TRONG CSDL PHÂN TÁN...............21 2.1. CÁC KỸ THUẬT PHÂN MẢNH DỮ LIỆU TRONG CSDL ..........................21 2.1.1. Loại bỏ dƣ thừa............................................................................................21 2.1.2. Phân mảnh ngang : ......................................................................................21 2.1.3. Phân mảnh dọc ..........................................................................................219 2.1.4. Phân mảnh hỗn hợp .................................................................................2530 2.2. CÁC LỆNH SQL GỘP NHÓM .........................................................................30 2.2.1. Thuật toán trộn tập trung CM (Centralized Merging) .................................46 2.2.2. Thuật toán trộn phân tán DM (Distributed Merging) ..................................51 2.2.3. Thuật toán phân mảnh lại ReF (Refragmentation) ......................................53 2.3. KẾT LUẬN CHƢƠNG 2. ..................................................................................55 3.1. ỨNG DỤNG TẠI CÔNG TY TNHH TM VẠN XUÂN ( DẠNG DEMO). .....56 3.1.1. Giới thiệu CSDL tại công ty TNHH thƣơng mại Vạn Xuân .......................56 Hình 3-1. Sơ đồ kết nối các quan hệ .....................................................................57 3.1.2. Ứng dụng các thuật toán gộp nhóm tại công ty TNHH thƣơng mại Vạn Xuân.......................................................................................................................57 3.2. KẾT LUẬN CHƢƠNG 3. ..................................................................................64 KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN CỦA LUẬN VĂN .....................................65 TÀI LIỆU THAM KHẢO .............................................................................................66 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 MỞ ĐẦU 1. Đặt vấn đề Nhằm giải quyết vấn đề chậm trễ thƣờng gặp trong các hệ CSDL song song, ngoài việc áp dụng một kiến trúc phần cứng thích hợp, ngƣời ta tiến hành phân mảnh dữ liệu một cách hợp lý cho các bộ xử lý. Một chiến lƣợc phân mảnh dữ liệu tốt sẽ tăng mức độ thực hiện song song đồng thời khai thác tốt hơn các hàm gộp nhóm từ các mảnh. Chúng ta sẽ đề cập đến một số kỹ thuật phân mảnh dữ liệu theo chiều ngang phổ biến nhƣ phân mảnh theo vòng tròn Robin, phân mảnh theo hàm băm, phân mảnh theo khoảng, phân mảnh theo chiều dọc, ... và một số hàm gộp nhóm trong CSDL phân tán nhƣ: SUM, COUNT, AVERAGE... 2. Đối tƣợng và phạm vi nghiên cứu Các hàm gộp nhóm trong cơ sở dữ liệu quan hệ Các phƣơng pháp phân mảnh Các hàm gộp nhóm trong trƣờng hợp CSDL phân tán 3. Hƣớng nghiên cứu của đề tài Nghiên cứu các phƣơng pháp phân mảnh. Nghiên cứu các hàm gộp nhóm. Nghiên cứu cách đƣa các hàm gộp nhóm vào các mảnh và ứng dụng 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. Các nội dung cơ bản của luận văn đƣợc trình bày theo cấu trúc nhƣ sau: Mở đầu Chƣơng 1: Cơ sở lý thuyết Chƣơng 2: Phân mảnh và gộp nhóm trong CSDL phân tán Chƣơng 3: Ứng dụng 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://www.lrc-tnu.edu.vn/ 2 Chƣơng 1: CƠ SỞ LÝ THUYẾT 1.1. GIỚI THIỆU VỀ LOGIC 1. Mệnh đề là một phát biểu để diễn tả một ý tƣởng trọn vẹn và chúng ta có thể khẳng định một cách khách quan là đúng hoặc sai, nó không thể vừa đúng lại vừa sai, hay mang tính chất mập mờ. 2. Giá trị trị đúng hay sai của mệnh đề đƣợc gọi là chân trị của mệnh đề. Chân trị đúng của mệnh đề thƣờng đƣợc kí hiệu là 1 hoặc T hoặc True, còn chân trị sai đƣợc kí hiệu là 0 hoặc F hoặc False 3. Mệnh đề logic tuy đơn giản nhƣng rất quan trọng trong khoa học máy tính. Là cơ sở lập luận hàng ngày và trong lập trình. Ví dụ 1.1.1. 1. “12 là số chẵn” là mệnh đề đúng 2. “12 là số nguyên tố” là mệnh đề sai 3. “x + ay = z” không phải mệnh đề Các kí hiệu dùng trong mệnh đề logic ( ) dùng để gom nhóm biểu thức logic Phủ định (NOT) Hội (Conjunction AND) Tuyển (Disjunction OR) Ký hiệu điều kiện (If…Then…) Kéo theo hai chiều (If AND Only If) Chúng ta giả thiết rằng tập các ký tự trong biểu thức logic là hữu hạn hoặc đếm đƣợc, nhƣng hầu hết các kết luận vẫn đúng cho trƣờng hợp không đếm đƣợc. Mệnh đề đƣợc chia làm hai loại cơ bản: mệnh đề sơ cấp (elementary), nó là các nguyên tử (atom)-không thể chia nhỏ đƣợc; mệnh đề phức hợp (compound), mệnh đề đƣợc tạo ra từ một hoặc nhiều mệnh đề khác bằng cách sử dụng các phép toán mệnh Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 3 Để máy tính hiểu đƣợc, chúng ta dùng các kí hiệu cho các mệnh đề, các biến mệnh đề thƣờng đƣợc dùng là các chữ thƣờng. Ví dụ 1.1.2. p = “15 MOD 3 = 0”, là mệnh đề sơ cấp. r = “15 MOD 3 = 0” AND “3 là số nguyên tố”, là mạnh đề phức hợp Các phép toán mệnh đề: trực giao) ; (phủ định) ; (hội) ; (tuyển) ; (hoặc hay tổng (kéo theo hai chiều) (kéo theo) ; 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 to và nó là sự kết hợp của: - Các mệnh đề hay các giá trị hằng - Các biến mệnh đề hoặc các biểu thức logic - Các phép toán logic và các dấu ( ) - Bảng chân trị của các phép toán mệnh đề p q 0 0 1 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 1 0 1 1 p p q p q p q p q p q Bảng chân trị của các phép toán mệnh đề Mức ư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 yếu dần từ trên xuống dƣới, từ trái qua phải theo bảng sau : Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 4 Ký hiệu phép toán , , Nghĩa của phép toán Phủ định Hội, tuyển , Kéo theo, tƣơng đƣơng , Bảng ƣu tiên các phép toán mệnh đề Tương đương của hai biểu thức logic Hai biểu thức logic E và F đƣợc gọi là tƣơng đƣơng với nhau và viết E F khi E và F có cùng chân trị. Các quy tắc thay thế Quy tắc 1: (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. Quy tắc 2: (Tính bất biến đối với biểu thức logic hằng đúng) Cho E là biểu thức hằng đúng, 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 đúng. Tƣơng tự cho biểu thức hằng sai. Các dạng chính tắc 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: F = q1 q2 ... qn ; với qi = pi hoặc qi = pi ( i 1, n ) Biểu thức tuyển cơ bản. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 5 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 = pi ( i 1, 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à dạng tuyển chính tắc, nếu: E = E1 E2 ... En ; trong đó mỗi Ei ( i 1, n ) là những biểu thức hội cơ bản của các pi ( i 1, n ). Định lý 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 là 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. Biểu thức logic 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: F = F1 F2 ... Fn , trong đó mỗi Fi ( i 1, n ) là một biểu thức tuyển cơ bản của các pi ( i 1, n ) Định lý 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 là F (p1, p2, ...pn ) F = F1 F2 ... Fm (duy nhất ) với Fi ( i 1, m ) là các biểu thức tuyển cơ bản. Mộ số luật hay được dùng nhất 1/ Luật phủ định của phủ định: p p 2/ Luật giao hoán: 3/ Luật kết hợp: 4/ Luật phân phối: 5/ Luật Demorgan: Số hóa bởi Trung tâm Học liệu p q q p p q q p p (q r) (p q) r p (q r) (p q) r p (q r) (p q) (p r) p (q r) (p q) (p r) (p q) p q http://www.lrc-tnu.edu.vn/ 6 (p 6/ Luật về phần tử bù: q) p p p 1 p p 0 7/ Luật kéo theo: p q 8/ Luật tƣơng đƣơng: p q 9/ Các luật đơn giản của phép tuyển ( ): p (p p p p p 1 1 p 0 p p (p q) 10/ 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) q) p q q q) (q p) p p Các quy tắc suy diễn cơ bản 1. Quy tắc Modusponents (p q) p q hay (p q 2. Quy tắc Modus Tollens (p q) q p hay (p q) q p 3. Quy tắc chứng minh phản chứng p q (p q) Để chứng minh từ p toàn sai do đó p 0. q ta chứng minh từ p và không q là kết luận hoàn q đúng. 4. Quy tắc chứng minh theo trường hợp (p1 q) (p2 Số hóa bởi Trung tâm Học liệu q) ........(pn q) (p1 p2 .... pn) http://www.lrc-tnu.edu.vn/ q 7 5. Quy tắc tam đoạn luận (p q) (q r) Số hóa bởi Trung tâm Học liệu (p r) hay (p q) (q r) (p http://www.lrc-tnu.edu.vn/ r) 7 1.2.TỔNG QUAN VỀ CSDL PHÂN TÁN Để thuận tiện cho việc nghiên cứu và trình bầy, chúng ta xét quan hệ CSDL của Công ty điện toán sau ( Hình 1) Hình 1: Sơ đồ kết nối các quan hệ. n 1 MaNV 1 TrinhDoCM Luong Kỹ sƣ điện Phân tích và thiết kế hệ thống Kỹ sƣ cơ khí Lập trình viên 4000 3400 2700 2400 Quan hệ TraLuong n MaNV NV1 NV2 NV3 NV4 NV5 NV6 NV7 NV8 ChucVu ThoiGianLV Giám đốc 12 Nhân viên phân tích và thiết kế 24 Nhân viên phân tích và thiết kế 6 Nhân viên tƣ vấn 10 Kỹ sƣ 48 Lập trình viên 18 Giám đốc 24 Giám đốc 48 Kỹ sƣ 36 40 Giám đốc Quan hệ PhanNhiem Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ NV1 NV2 NV2 NV3 NV3 NV4 NV5 NV6 NV7 NV8 DA1 DA1 DA2 DA3 DA4 DA2 DA2 DA4 DA3 DA3 TrinhDoCM Nguyễn Văn Bổng Lê Hồng Ngoc Hoàng Trung Mã Trịnh Kim Thanh Ngô Đình Vinh Trần Mỹ Lệ Lê Hồng Hạnh Nguyễn Trƣờng Tam Kỹ sƣ điện Phân tích và thiết kế hệ thống Kỹ sƣ cơ khí Lập trình viên Phân tích và thiết kế hệ thống Kỹ sƣ điện Kỹ sƣ cơ khí Phân tích và thiết kế hệ thống 1 n MaDuAn TenNV MaDu An DA1 DA2 DA3 DA4 Quan hệ NhanVien TenDuAn Thiết bị đo đạc Phát triển CSDL CAD/ CAM Bảo dƣỡng NganSac h ViTri 150000 135000 250000 310000 Hải Phòng Hà Nội Hà Nội TP.Hồ Chí Minh Quan hệ DuAn 8 1.2.1.Các phƣơng pháp phân mảnh cơ bản. Các kiểu phân mảnh cơ bản là: Phân mảnh ngang, phân mảnh dọc. Ngoài ra còn có các kiểu phân mảnh dựa trên hai cách cơ bản đã nêu là phân mảnh ngang dẫn xuất và phân mảnh hỗn hợp. - Phân mảnh ngang Có hai loại phân mảnh ngang: phân mảnh ngang nguyên thuỷ và phân mảnh ngang dẫn xuất. Các thông tin cần cho phân mảnh ngang: - Thông tin về CSDL. Thông tin về CSDL là thông tin về lƣợc đồ khái niệm toàn cục của CSDL. Tức là chúng ta cần biết đƣợc cách mà quan hệ con sẽ hợp ( ) lại với nhau nhƣ thế nào. Trong mô hình quan hệ, các liên kết giữa các thực thể cũng đƣợc biểu thị bằng quan hệ. Với mục đích thiết kế phân tán, các mối liên kết cũng đƣợc mô hình hoá theo kiểu mô hình quan hệ. Theo cách này, chúng ta sẽ vẽ một đƣờng nối có hƣớng từ quan hệ Parent đến quan hệ Child. Ví dụ hình 2 TraLuong TrinhDoCM. Luong l1 NhanVien MaNV, TenNV, TrinhDoCM l2 DuAn MaDuAn, TenDuAn, NganSach, ViTri l3 PhanNhiem MaNV, MaDuAn, ChucVu, ThoiGianLV Hình 2 : Biểu diễn mối liên hệ giữa các quan hệ nhờ các đường nối Cho đƣờng nối l1 của hình 2, các hàm Nguon và Dich có các giá trị sau: Nguon(l1 ) = TraLuong Dich( l1) = NhanVien Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 9 Thông tin định lƣợng cần có về CSDL là lực lƣợng của các quan hệ, đƣợc ký hiệu là Card(.) - Thông tin về ứng dụng. Chúng ta cần hai loại thông tin: định tính và định lƣợng về các ứng dụng. Thông tin định tính phục vụ phân mảnh, còn thông tin định lƣợng sử dụng cho mô hình cấp phát. Những thông tin định tính gồm có các vị trí đƣợc dùng trong các câu vấn tin. Nếu không thể phân tích đƣợc hết tất cả các ứng dụng thì ít nhất cũng phải nghiên cứu đƣợc các ứng dụng “quan trọng” nhất. + Phân mảnh ngang nguyên thủy Phân mảnh ngang nguyên thuỷ đƣợc định nghĩa bằng một thuật toán chọn trên các quan hệ nguồn của một lƣợc đồ CSDL. Mảnh ngang Ri bao gồm các bộ của R đƣợc chọn ra theo công thức: Ri = Fi(R), 1≤ i ≤ z. Trong đó Fi là công thức chọn. Chú ý rằng chúng ta xét Fi có dạng chuẩn hội, nó là một vị từ hội sơ cấp. Ví dụ 1.2.1-1. Xét hình 1 ta có Phân rã quan hệ DuAn thành các mảnh ngang DuAnH1 và DuAnH2 nhƣ sau: DuAnH1 = DuAnH2 = (DuAn) NganSach > 200000 (DuAn) NganSach 200000 Ví dụ 1.2.1-2. Xét quan hệ DuAn. Chúng ta có thể định nghĩa các mảnh ngang sau đây dựa vào vị trí dự án. DuAnH1 = ViTri = "Hải Phòng")(DuAn) DuAnH2 = ViTri = "Hà Nội" DuAnH3 = ViTri = "TP.Hồ chí Minh" Số hóa bởi Trung tâm Học liệu (DuAn) (DuAn) http://www.lrc-tnu.edu.vn/ 10 Các mảnh thu đƣợc trình bày trong các bảng 1, 2, 3 tƣơng ứng MaDuAn DA1 TenDuAn NganSach ViTri Thiết bị đo đạc 150000 Hải Phòng Bảng 1. Mảnh ngang DuAn H1 MaDuAn TenDuAn NganSach ViTri DA2 Phát triển CSDL 135000 Hà Nội DA3 CAD/CAM 250000 Hà Nội Bảng 2. Mảnh ngang DuAn H2 MaDuAn TenDuAn NganSach ViTri DA4 Bảo dƣỡng 310000 TP.Hồ Chí Minh Bảng 3. Mảnh ngang DuAn H3 Nhận xét: Cho tập các vị M = {mi | mi là vị từ hôi sơ cấp i = 1, 2 ,…} Ký hiệu |M| = Card(M). Vậy thì: (1) Mảnh ngang Ri của quan hệ R là một quan hệ chứa các bộ của R thoả mãn vị từ hội sơ cấp mi . (2) Số lƣợng các mảnh ngang khi phân mảnh theo M sẽ là |M|, mỗi mảnh ngang trong trƣờng hợp này cũng đƣợc gọi là mảnh hội sơ cấp. Do lí luận trên, chúng ta thấy bƣớc đầu tiên của mọi thuật toán phân mảnh ngang là xác định các vị từ đơn giản sẽ tạo ra các vị từ hội sơ cấp. Một số tính chất quan trọng của tập vị từ đơn giản là tinh đầy đủ và tính cực tiểu. Định nghĩa 1. Tập các vị từ đơn giản đầy đủ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 11 Tập các vị từ đơn giản Pr đƣợc gọi là đầy đủ nếu và chỉ nếu xác suất mỗi ứng dụng (vấn tin) truy xuất đến một bộ bất kỳ thuộc một mảnh hội sơ cấp nào đó đƣợc định nghĩa theo Pr đều bằng nhau. Ví dụ 1.2.1-3. Xét quan hệ DuAn và các mảnh ngang DuAnH1, DuAnH2, DuAnH3 trong ví dụ 1.2.1-2. Nếu ứng dụng duy nhất p truy suất đến quan hệ DuAn, chỉ truy suất các bộ theo ViTri trí, thì tập vị từ PDuAn = {p} là đầy đủ, vì các bộ của mảnh DuAnHi điều có sác xuất truy xuất đến các mảnh nhƣ nhau. Tuy nhiên nếu thêm ứng dụng thứ hai q truy xuất các dự án có ngân sách trên 200000 USD thì PDuAn không còn đầy đủ nữa, do một số bộ trong các mảnh DuAnHi có xác xuất đƣợc truy xuất cao hơn (chẳng hạn bộ {DA3, CAD/CAM, 250000, Hà Nội} trong DuAn H2 và {DA4, Bảo dƣỡng, 310000, TP.Hồ Chí Minh} trong DuAn H3 đƣợc đƣợc truy xuất nhiều hơn các bộ còn lại. Để cho tập vị từ PDuAn là đầy đủ, chúng ta cần phải thêm các vị từ (NganSach ≤ 200000, DuAn > 200000) vào P DuAn. Tức là PDuAn = {ViTri = ”Hải Phòng”, ViTri = “Hà Nội”, ViTri = “ TP.Hồ Chí Minh ”, NganSach ≤ 200000, NganSach > 200000} Định nghĩa 2. Vị từ đơn giản liên đới Vị từ đơn giản p đƣợc gọi là liên đới nếu biết đƣợc sự ảnh hƣởng của nó đến cách thực hiện phân mảnh (nghĩa là vị từ p làm cho mảnh F bị phân thành các mảnh Fi và Fj đều khác rỗng, thì vẫn có ít nhất một ứng dụng truy xuất đến Fi và Fj theo những cách khác nhau. Định nghĩa 3. Tập từ đơn giản cực tiểu Nếu tất cả các vị từ của tập Pr đều có liên đới thì Pr đƣợc gọi là cực tiểu. Ví dụ 1.2.1-4 Tập PDuAn đƣợc định nghĩa trong ví dụ 1.2.1-3. là : Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 12 PDuAn = {ViTri = ”Hải Phòng”, ViTri = “Hà Nội”, ViTri = “ TP.Hồ Chí Minh ”, NganSach ≤ 200000, NganSach > 200000} là đầy đủ và cực tiểu, tuy nhiên nếu chúng ta thêm vị từ TenDuAn = "Thiết bị đo đạc" vào Pr, tập kết quả sẽ không còn cực tiểu vì vị từ mới đƣợc thêm vào không có liên đới ứng với PDuAn. Vì không có ứng dụng nào truy xuất khác nhau đến các mảnh tạo ra. Thuật toán lặp sau đây cho ta tập vị từ đầy đủ và cực tiểu P‟R khi đã có tập các vị từ đơn giản PR. Thuật toán này, đƣợc gọi là COM_MIN, nội dung COM_MIN đƣợc trình bày trong thuật toán COM_MIN(R, PR) [2], [3] Qui tắc1 (Thừa nhận). Quy tắc về tính đầy đủ và cực tiểu. Một quan hệ (hoặc một mảnh) đƣợc phân hoạch thành ít nhất hai phần thì chúng phải đƣợc truy xuất khác nhau bởi ít nhất một ứng dụng. + Phân mảnh ngang dẫn xuất Phân mảnh ngang dẫn xuất là phân mảnh ngang trên quan hệ của một đƣờng nối dựa theo phép toán chọn trên quan hệ nguồn của đƣờng nối đó. Nếu cho trƣớc một đƣờng lối L, trong đó Nguon(L) = S và Dich(L) = R, các mảnh ngang dẫn xuất của R đƣợc định nghĩa là: Ri = R╞ Si, 1 Trong đó i là số lƣợng các mảnh đƣợc định nghĩa trên R, và Si = Fi(S) với Fi là công thức định nghĩa mảnh ngang nguyên thuỷ Si. Ví dụ 1.2.1-5. Xét đƣờng nối l1 trong hình 1, trong đó Nguon(l1) = TraLuong và Dich(l1) = NhanVien. Thế thì chúng ta có thể nhóm quan hệ trả TraLuong theo lƣơng: nhóm có lƣơng từ 30000 USD trở xuống và nhóm có trên 30000 USD. Hai mảnh đƣợc sinh ra nhƣ sau: TrinhDoCM, Luong TraLuong1 Số hóa bởi Trung tâm Học liệu TrinhDoCM, Luong TraLuong2 http://www.lrc-tnu.edu.vn/ 13 MaNV, TenNV, TrinhDoCM MaNV, TenNV, TrinhDoCM NhanVien 1 NhanVien Hình 3. Đồ thị nối giữa 2các mảnh Khi đó phân mảnh dẫn xuất sẽ là TraLuong1 = TraLuong2 = Luong 30000 Luong > 30000 (TraLuong) (TraLuong) Trong đó NhanVienDanxxuat1 = NhanVien ╞ TraLuong1 NhanVienDanxxuat2 = NhanVien ╞ TraLuong2 Kết quả phân mảnh đƣợc trình bày trong các bảng 4(a,b) MaNV TenNV TrinhDoCM NV3 Hoàng Trung Mã Kỹ sƣ cơ khí NV4 J.Miller Lập trình viên NV7 Lê Hồng Hạnh Kỹ sƣ cơ khí Bảng 4a. Mảnh dẫn xuất NhanVienDanxuat1 tƣơng ứng TraLuong1 MaNV TenNV TrinhDoCM NV1 Nguyễn Văn Bổng Kỹ sƣ điện NV2 M.Smith Phân tích và thiết kế hệ thống NV5 Ngô Đình Vinh Phân tích và thiết kế hệ thống NV6 Trần Mỹ Lệ Kỹ sƣ điện NV8 Nguyễn Trƣờng Tam Phân tích và thiết kế hệ thống Bảng 4b. Mảnh dẫn xuất NhanVienDanxxuat2 tƣơng ứng TraLuong2 Các thông tin cần cho phân mảnh ngang dẫn xuất Muốn thực hiện phân mảnh ngang dẫn xuất, chúng ta cần ba thông tin vào: tập các mảnh của quan hệ nguồn (chẳng hạn TraLuong1 và TraLuong 2 trong Ví Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 14 dụ 1.2.1-5.), quan hệ đích (chẳng hạn NhanVien), và tập các vị từ nối nửa giữa nguồn và đích (chẳng hạn NhanVien.TrinhDoCM = TraLuong.TrinhDoCM trong Ví dụ 1.2.1-5.). Ví dụ 1.2.1-6. Xét quan hệ PhanNhiem chúng ta phân mảnh ngang theo các mảnh DuAnH1, DuAnH3 , DuAnH4 và DuAnH6 của DuAn. Cần nhớ lại rằng DuAnH1 = ViTri = “Hải Phòng” DuAnH3 = ViTri = “Hà Nội” NganSach DuAnH4 = ViTri = “Hà Nội” NganSach > 200000 (DuAn) DuAnH6 = ViTri = “TP.Hồ Chí Minh ” NganSach 200000 (DuAn) 200000 (DuAn) NganSach > 200000 (DuAn) Vì thế phân mảnh dẫn xuất của PhanNhiem theo { DuAn1,DuAn3, DuAn4, DuAn6} Sẽ cho: PhanNhiemDanxuat1 = PhanNhiem ╞ DuAnH1 PhanNhiemDanxuat2 = PhanNhiem ╞ DuAnH3 PhanNhiemDanxuat3 = PhanNhiem ╞ DuAnH4 PhanNhiemDanxuat4 = PhanNhiem ╞ DuAnH6 Thể hiện của các mảnh này đƣợc trình bày trong các bảng 5(a, b, c, d) MaNV MaDuAn ChucVu ThoiGianLV NV1 DA1 Giám đốc 12 NV2 DA2 Nhân viên phân 24 tích và thiết kế Bảng 5a . Mảnh dẫn xuất PhanNhiemDanxuat1 tƣơng ứng với DuAnH1 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/