Tóm tắt luận văn Nghiên cứu các giải pháp công nghệ phân tán dữ liệu và ứng dụng quản lý nhân sự phân tán trong cơ quan nhà nước Lào

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG ---------------------------------------- KHOUANETHEVA PHOLSENA NGHIÊN CỨU CÁC GIẢI PHÁP CÔNG NGHỆ PHÂN TÁN DỮ LIỆU VÀ ỨNG DỤNG QUẢN LÝ NHÂN SỰ PHÂN TÁN TRONG CƠ QUAN NHÀ NƯỚC LÀO Chuyên ngành: Khoa học máy tính Mã số: 60.48.01.01 TÓM TẮT LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: TS PHẠM THẾ QUẾ HÀ NỘI – 2013 1 MỞ ĐẦU Ở Lào, s ự liên k ết xã h ội ngày càng tr ở nên ch ặt ch ẽ hơn, s ự phát tri ển c ủa m ỗi ngành không th ể thi ếu thông tin v ề các ngành khác. H ơn n ữa s ự phát tri ển c ủa các t ổ ch ức xã h ội không còn t ập trung trong ph ạm vi thành ph ố, ho ặc m ột s ố tỉnh thành, mà phân b ố trên di ện r ộng, v ề mặt địa lý tr ải dài trên nhi ều qu ốc gia trên th ế gi ới. Th ực t ế các h ệ th ống t ập trung đã bộc l ộ nh ững nh ược điểm nh ư vi ệc t ăng kh ả năng l ưu tr ữ thông tin là khó kh ăn và b ị gi ới h ạn b ởi kh ả năng t ối đa c ủa m ột máy cụ th ể, kh ả năng ph ục v ụ không đảm b ảo khi s ố lượng ng ười dùng t ăng lên đáng k ể. C ơ s ở dữ li ệu b ị ng ưng tr ệ ph ục v ụ khi có s ự cố xảy ra, có ngh ĩa là độ sẵn sàng ph ục v ụ của c ơ s ở dữ li ệu không còn n ữa, kh ả năng tính toán c ủa các máy tính đơ n lẻ đang tri ến d ần t ới gi ới h ạn v ật lý, tính đa qu ốc gia c ủa các t ổ ch ức kinh t ế xã h ội làm cho t ổ ch ức d ữ li ệu t ập trung đang g ặp nhi ều khó kh ăn trong l ưu tr ữ cũng nh ư x ử lý. Nh ững nh ược điểm này đã được kh ắc ph ục trong các h ệ c ơ sở d ữ li ệu phân tán, vì vi ệc qu ản lý thông tin ở kh ắp m ọi n ơi là một yêu c ầu c ấp thi ết đố i v ới nhà qu ản lý c ơ s ở d ữ li ệu. Ví d ụ nh ư b ộ máy qu ản lý nhà n ước s ẽ qu ản lý d ữ li ệu n ằm ở các tỉnh, trong ngân hàng khi g ửi ti ền m ột n ơi s ẽ rút ti ền ở các n ơi khác, trong kinh doanh có th ể áp d ụng vào vi ệc qu ản lý các doanh nghi ệp v ề doanh s ố và doanh thu. Nh ững s ản ph ẩm c ủa các h ệ th ống phân tán đã xu ất hi ện nhi ều trên th ị tr ường và từng b ước ch ứng minh tính ưu vi ệt c ủa nó h ơn h ẳn các h ệ 2 th ống t ập trung truy ền th ống. Trên th ực t ế, các h ệ th ống phân tán đã thay thế d ần các h ệ th ống t ập trung. Nhu c ầu thu th ập, l ưu tr ữ, x ử lý và trao đổi thông tin của các ho ạt độ ng xã h ội và kinh t ế ngày càng cao. Yêu c ầu t ổ ch ức các h ệ x ử lý phân tán là yêu c ầu b ức thi ết. Vậy, để hi ểu thêm v ề v ấn đề này em ch ọn đề tài “Nghiên c ứu các gi ải pháp công ngh ệ phân tán d ữ li ệu và ứng d ụng qu ản lý nhân s ự phân tán trong c ơ quan Nhà n ước Lào ”. Cấu trúc c ủa lu ận v ăn được t ổ ch ức thành 3 ch ươ ng: • Ch ươ ng 1, tôi trình bày các v ấn đề liên quan đến c ơ s ở dữ li ệu phân tán, đặ c bi ệt làm rõ ưu và nh ược điểm c ủa cơ s ở d ữ li ệu phân tán, các mô hình có th ể tri ển khai h ệ th ống phân tán, các lo ại truy xu ất, các m ức trong su ốt của c ơ s ở d ữ li ệu phân tán. • Ch ươ ng 2, trình bày các chi ến l ược phân tán, các ph ươ ng pháp thi ết k ế, các v ấn đề thi ết k ế, các ph ươ ng pháp phân m ảnh, phân b ố cho các m ảnh. • Ch ươ ng 3, trình bày v ề bài toán, các mô hình và các yêu c ầu qu ản lý c ủa h ệ th ống qu ản lý nhân s ự trong Qu ốc H ội n ước C ộng hòa Dân ch ủ Nhân dân Lào ; trình bày quy trình thi ết k ế c ơ s ở d ữ li ệu phân tán và tri ển khai th ử nghi ệm. 3 CH ƯƠ NG 1 TỔNG QUAN V Ề CƠ S Ở DỮ LI ỆU PHÂN TÁN 1.1 Khái ni ệm và định ngh ĩa c ơ s ở d ữ li ệu phân tán 1.1.1 Mở đầ u Hệ cơ s ở dữ li ệu phân tán được xây d ựng d ựa trên s ự hợp nh ất c ủa hai h ướng ti ếp c ận quá trình x ử lý d ữ li ệu, là lý thuy ết các h ệ CSDL và công ngh ệ mạng máy tính. Cung cấp đa d ạng các lo ại hình d ịch v ụ và các d ịch v ụ đa ph ươ ng ti ện cho ng ười s ử dụng. Kết nối các máy tính thành mạng v ới m ục tiêu chia s ẻ tài nguyên thông tin chung cho nhi ều ng ười cùng s ử dụng, có hi ệu qu ả tài nguyên thông tin, nâng cao kh ả năng tích h ợp và trao đổi các lo ại d ữ li ệu gi ữa các thành ph ần trên m ạng. 1.1.2 Khái ni ệm x ử lý phân tán Có hai khái ni ệm x ử lý phân tán liên quan v ới nhau. • Khái ni ệm vi ệc tính toán trên Client/Server. Ứng d ụng đượ c chia ra thành hai ph ần, Server và Client và đượ c vận hành ở hai n ơi. Dữ li ệu được phép truy nh ập tr ực ti ếp và xử lý d ữ li ệu trên Server và Client. • Khái ni ệm vi ệc th ực hi ện các giao d ịch được x ử lý ph ức tạp trên nhi ều h ệ th ống. Không gian nh ớ và b ộ x ử lý của nhi ều máy cùng chia nhau giao d ịch x ử lý. Máy trung tâm s ẽ giám sát và qu ản lý các ti ến trình. Hàng nghìn máy cùng x ử lý m ột giao d ịch trên m ạng Internet. 4 1.2.2 Gi ảm chi phí truy ền thông 1.2.3 Hi ệu qu ả công vi ệc Sự tồn t ại m ột s ố hệ th ống x ử lý điạ ph ươ ng đạt được thông quan vi ệc x ử lý song song. Có thu ận l ợi trong vi ệc phân tích d ữ li ệu ph ản ánh điều ki ện ph ụ thu ộc c ủa các ứng d ụng, cực đại hoá tính địa ph ươ ng c ủa ứng d ụng. Trao đổi thông tin qua l ại gi ữa các b ộ xử lý có chi phí cức ti ểu. Công vi ệc x ử lý được phân chia cho các b ộ xử lý khác nhau và tránh được các tắc ngh ẽn thông tin trên m ạng ho ặc các dịch v ụ chung c ủa toàn h ệ th ống. 1.2.4 Độ tin c ậy và tính s ẵn sàng Cho phép truy nh ập có độ tin c ậy và tính s ẵn sàng cao hơn so v ới truy nh ập t ập trung. Đòi h ỏi k ỹ thu ật ph ức t ạp. Lỗi xu ất hi ện trong m ột c ơ s ở dữ li ệu phân tán có th ể xảy ra nhi ều hơn, vì s ố các thành ph ần c ấu thành l ớn h ơn, nh ưng ảnh h ưởng của l ỗi ch ỉ ảnh h ưởng t ới các ứng d ụng s ử dụng các v ị trí-site lỗi. S ự hỏng hóc c ủa toàn h ệ th ống ít khi x ảy ra. Công ngh ệ cơ s ở dữ li ệu phân tán là s ự kết h ợp gi ữa hai v ấn đề phân tán và h ợp nh ất: • Phân tán: phân tán d ữ li ệu trên các site c ủa m ạng • Hợp nh ất: h ợp nh ất v ề mặt logic các d ữ li ệu phân tán sao cho chúng xu ất hi ện v ới ng ười s ử dụng gi ống nh ư với c ơ s ở dữ li ệu đơ n l ẻ duy nh ất. Công ngh ệ cơ s ở dữ li ệu phân tán được phát tri ển d ủa trên s ự phát tri ển c ủa k ỹ thu ật tính toán, k ỹ thu ật truy ền thông và m ạng máy tính. 5 1.3 Đặc tr ưng c ơ b ản c ủa c ơ s ở d ữ li ệu phân tán Ph ần này so sánh c ơ s ở dữ li ệu phân tán v ới c ơ s ở dữ li ệu t ập trung ở một s ố đặc điểm: điều khi ển t ập trung, s ự độc lập d ữ li ệu, s ự gi ảm d ư th ừa d ữ li ệu, các c ấu trúc v ật lý ph ức tạp để truy xu ất hi ệu qu ả. 1.3.1 Điểu khi ển t ập trung Toàn b ộ dữ li ệu được t ập trung l ại nh ằm để tránh s ự dư th ừa d ữ li ệu, đảm b ảo được tính độc l ập c ủa d ữ li ệu. Dữ li ệu được qu ản lý t ập trung b ởi ng ười qu ản tr ị cơ s ở dữ li ệu. Ch ức n ăng c ơ b ản là b ảo đảm s ự an toàn c ủa d ữ li ệu. Vấn đề điều khi ển t ập trung không được nh ấn m ạnh. Sự điều khi ển được th ực hi ện theo m ột c ấu trúc điều khi ển phân c ấp bao g ồm hai lo ại ng ười qu ản tr ị cơ s ở dữ li ệu: • Ng ười qu ản tr ị cơ s ở dữ li ệu toàn c ục. • Ng ười qu ản tr ị cơ s ở dữ li ệu địa ph ươ ng-cục b ộ. Người qu ản tr ị cơ s ở dữ li ệu c ục b ộ cần ph ải có nh ững quy ền độc l ập riêng v ề cơ s ở dữ li ệu c ục b ộ của mình mà ng ười qu ản tr ị cơ s ở dữ li ệu toàn c ục hoàn toàn không có nh ững quy ền này. Đặc điểm này được g ọi là s ự độc l ập v ị trí. T ừ sự độc l ập v ị trí hoàn toàn đến s ự điều khi ển t ập trung hoàn toàn. 1.3.2 Độc l ập d ữ li ệu Là t ổ ch ức l ưu tr ữ dữ li ệu là trong su ốt đối v ới ng ười lập trình ứng d ụng. Ưu điểm là các ch ươ ng trình không b ị ảnh hưởng b ởi nh ững thay đổi v ề tổ ch ức l ưu tr ữ vật lý c ủa d ữ li ệu. Tính đúng đắn c ủa các ch ươ ng trình ứng d ụng không b ị ảnh h ưởng b ởi s ự di chuy ển d ữ li ệu t ừ một v ị trí này đến m ột v ị trí khác. 6 1.3.3 Gi ảm d ư th ừa dữ li ệu Các cơ s ở dữ li ệu phân tán được dư th ừa d ữ li ệu vì: • Làm t ăng tính c ục b ộ của các ứng d ụng. Các ứng dụng c ục b ộ được th ực hi ện nhanh h ơn, không c ần ph ải truy xu ất d ữ li ệu t ừ xa. • Làm t ăng tính s ẵn sàng c ủa h ệ th ống ứng d ụng, n ếu dữ li ệu t ại v ị trí bị hỏng được nhân b ản t ại các v ị trí khác. 1.3.4 Độ tin c ậy qua các giao d ịch phân tán Hệ qu ản tr ị cơ s ở dữ li ệu phân tán c ải thi ện độ tin c ậy qua các giao d ịch phân tán, vì các thành ph ần được nhân b ản hạn ch ế được các v ị trí l ỗi riêng l ẻ. L ỗi c ủa tr ạm riêng, ho ặc l ỗi của truy ền thông làm cho m ột ho ặc nhi ều tr ạm m ất liên l ạc, không đủ để phá v ỡ toàn b ộ hệ th ống. Nếu bi ết cách h ỗ tr ợ cho các giao d ịch phân tán và các giao th ức ứng d ụng, thì ng ười s ử dụng v ẫn có th ể truy nh ập được t ới ph ần khác trong cơ s ở dữ li ệu phân tán. 1.3.5 C ải ti ến hi ệu n ăng Được c ải ti ến d ựa vào hai điểm: a) H ệ qu ản tr ị cơ s ở dữ li ệu phân tán có kh ả năng phân mảnh cơ s ở dữ li ệu khái ni ệm và cho phép c ục b ộ hoá d ữ li ệu. b) Tính song song c ủa các h ệ th ống phân tán có thể được khai thác để th ực hi ện song song liên truy v ấn và nội b ộ. 1.3.6 D ễ dàng m ở r ộng h ệ th ống Th ực hi ện b ằng cách t ăng kh ả năng l ưu tr ữ và x ử lý c ủa mạng. Kh ả năng m ở rộng h ệ th ống d ễ dàng mang tính kinh t ế, chi phí gi ảm. 7 1.3.7 Tính toàn v ẹn, ph ục h ồi và điều khi ển t ươ ng tranh Các ph ươ ng pháp cung c ấp các giao tác. M ỗi m ột giao tác là m ột nguyên t ố. Giao tác nguyên t ố là ph ươ ng ti ện để đạt được tính toàn v ẹn d ữ li ệu. Sự ph ục h ồi liên quan đến v ấn đề đảm b ảo tính nguyên tố của giao tác khi có sự sự cố về mặt k ỹ thu ật. Điều khi ển t ươ ng tranh nh ằm đảm b ảo tính nguyên t ố của giao tác khi xu ất hi ện s ự tươ ng tranh giao tác. 1.4 Các mô hình c ơ s ở d ữ li ệu phân tán Mọi ứng d ụng CSDL g ồm 3 ph ần:
Thành ph ần x ử lý ứng d ụng
Thành ph ần ph ần m ềm CSDL
CSDL (database) 1.4.1 Mô hình CSDL Client/Server Cơ s ở dữ li ệu được cài đặt trên Server, phần m ềm c ơ sở dữ li ệu trên Server s ẽ truy nh ập vào c ơ s ở dữ li ệu và x ử lý theo yêu c ầu và g ửi tr ả kết qu ả cho máy Client. Application Network Tow er System Application Databas Application Hình 1.1 Mô hình Client-Server 8
Server – điều khi ển, l ưu tr ữ CSDL, x ử lý các truy vấn và qu ản lý vi ệc khai thác tài nguyên trên m ạng của các Clients.
Client – Khai thác tài nguyên qua Server Mô hình CSDL client/server gi ống v ới mô hình CSDL file-server nh ưng trên th ực t ề mô hình CSDL Client/Server có nhi ều thu ận l ợi h ơn mô hình file-server. 1.4.2 Mô hình CSDL phân tán -Hai mô hình CSDL File-Server và Client/Server:d ữ li ệu và ch ươ ng trình ứng d ụng truy nh ập d ữ li ệu n ằm trên 2 b ộ xử lý khác nhau. -Mô hình CSDL phân tán:CSDL ở trên nhi ều máy khác nhau. Hình 1.3 Distributed database model 9 CH ƯƠ NG II KỸ THU ẬT PHÂN TÁN D Ữ LI ỆU 2.1 Khái ni ệm và s ự cần thi ết phân m ảnh d ữ liê ụ Phân m ảnh là chia CSDL thành các mảnh d ữ li ệu nh ỏ hơn và x ử lý m ỗi m ảnh nh ận được nh ư m ột CSDL độc l ập, ch ỉ được th ực hi ện khi nó t ăng hi ệu qu ả, và có độ tin c ậy. Có 2 ki ểu phân m ảnh: - 1. Phân m ảnh ngang: CSDL được phân ho ạch thành các CSDL con, m ỗi CSDL con là m ột t ập h ợp các b ộ th ỏa mãn một s ố tính ch ất nào đó. - 2. Phân m ảnh d ọc: chia CSDL thành các CSDL con gồm m ột t ập h ợp con các thu ộc tính cùng v ới các giá tr ị của chúng có trong t ập các thu ộc tính c ủa CSDL đã cho. Khi CSDL được phân m ảnh, ph ải d ịch câu truy v ấn toàn c ục thành nhi ều câu truy v ấn theo các m ảnh. 2.2 Các quy t ắc phân m ảnh Các nguyên t ắc để đảm b ảo c ơ s ở dữ li ệu khi phân mảnh s ẽ đảm b ảo tính không thay đổi v ề ng ữ ngh ĩa, toàn v ẹn dữ liệu và đảm b ảo tính độc l ập d ữ li ệu. Có 3 qui tắc ph ải tuân th ủ phân mảnh c ơ s ở dữ li ệu quan h ệ: 2.2.1 Tính đầy đủ 2.2.2 Tính ph ục h ồi 2.2.3 Tính tách bi ệt 10 2.3 Kỹ thu ật phân m ảnh ngang d ữ li ệu 2.3.1 Khái ni ệm Là vi ệc chia quan h ệ thành nhi ều mảnh quan h ệ kh ả hợp. M ỗi m ảnh quan h ệ bao g ồm nhóm b ộ dữ li ệu th ỏa m ột điều ki ện logic. Là th ực hi ện các phép ch ọn quan h ệ th ỏa mãn một bi ểu th ức điều kiên cho tr ước. Có 2 lo ại ph ươ ng pháp phân m ảnh ngang: • Phân m ảnh ngang nguyên th ủy. • Phân m ảnh ngang d ẫn xu ất. 2.3.2 Thông tin c ần thi ết c ủa phân m ảnh ngang a) Thông tin v ề cơ s ở dữ li ệu: Là các thông tin v ề lược đồ khái ni ệm toàn c ục c ủa h ệ cơ s ở dữ li ệu. b) Thông tin v ề ứng d ụng: Để th ực hi ện vi ệc phân mảnh m ột quan h ệ, c ần ph ải có thông tin định tính và thông tin định l ượng. c) Thông tin định tính v ề các ứng d ụng c ần ph ải có: • Độ tuy ển h ội s ơ c ấp (Minterm Selectivity): là s ố bộ của quan h ệ sẽ được ch ọn theo v ị từ hội s ơ c ấp cho tr ước. • Tần s ố ứng d ụng ng ười s ử dụng truy xu ất d ữ li ệu. N ếu Q = {q 1, q 2, … , q q} là t ập truy v ấn, ký hi ệu acc(q i) là tần s ố truy xu ất c ủa truy v ấn q i trong m ột kho ảng th ời gian đã cho. • Tần s ố truy xu ất h ội s ơ c ấp là t ần s ố truy xu ất c ủa h ội sơ c ấp m, ký hi ệu là acc(m). 11 2.3.3 Phân m ảnh ngang nguyên th ủy Phân m ảnh ngang nguyên th ủy được định ngh ĩa b ằng một phép ch ọn trên quan h ệ ch ủ của l ược đồ cơ s ở dữ li ệu. R = σ (R) , i=1 ...n i Fi Fi là bi ểu th ức đại s ố quan h ệ hội s ơ c ấp có d ạng chu ẩn hội. Nếu F i có d ạng chu ẩn h ội, thì nó là v ị từ hội s ơ c ấp (m i). Thu ật toán s ẽ th ảo lu ận kh ẳng định F i là v ị từ hội s ơ c ấp. Một mảnh ngang R i của quan h ệ R g ồm t ất c ả các b ộ của R tho ả một v ị từ hội s ơ cấp m i. Trong các thu ật toán phân m ảnh ngang , tr ước tiên c ần ph ải xác định các v ị từ đơ n gi ản s ẽ tạo ra v ị từ hội s ơ c ấp. 2.3.4 Tính đầy đủ và tính c ực ti ểu c ủa v ị t ừ đơn gi ản a) Tính đầy đủ: T ập các v ị từ đơ n gi ản Pr được g ọi là đầy đủ khi và ch ỉ khi xác su ất truy xu ất 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. V ị từ đầy đủ sẽ đảm b ảo cho các m ảnh tho ả mãn các v ị từ sơ c ấp, nh ất quán v ề mặt logic. Sử dụng m ột t ập vị từ đầy đủ làm c ơ s ở cho vi ệc phân m ảnh ngang c ơ s ở. b) Tính tính c ực ti ểu: Đặc tính th ứ 2 của t ập các v ị từ có tính c ực ti ểu. Đây là m ột đặc tính c ảm tính.Nếu m ột v ị từ đơ n gi ản có liên đới đến vi ệc phân m ảnh , ph ải có tính liên đới (relevant) trong vi ệc xác định m ột phân m ảnh. Gọi m i và m j là hai v ị từ hội s ơ c ấp. G ọi f i và f j là hai mảnh t ươ ng ứng được định ngh ĩa theo m i và m j. acc (m) acc (m) Khi đó p i là có liên đới khi và ch ỉ khi: ≠ card ( fi ) card ( f j ) 12 2.3.5 Phân mảnh ngang d ẫn xu ất Là phân chia quan h ệ thành viên thành các m ảnh quan hệ theo phân m ảnh c ủa quan h ệ ch ủ, các m ảnh thu được ch ỉ được định ngh ĩa trên các thu ộc tính c ủa quan h ệ thành viên. Có th ể tồn t ại m ột s ố kết n ối r ỗng khi phân tán d ữ li ệu và các thu ộc tính k ết n ối tách r ời nhau. Kết n ối phân tán được bi ểu di ễn bằng hai d ạng đồ th ị rút g ọn: Đồ th ị rút g ọn là tách (Partitioned) và Đồ th ị nối rút g ọn là đơ n gi ản (Simple). R R R S1 S1 S1 R2 R2 R2 S2 S S2 2 R R S3 R S3 R S3 S3 R R R S4 a) Đồ th ị kết n ối a) Đồ th ị c) Đồ th ị kết n ối hoàn toàn kết n ối tách Đơ n gi ản Hình 2.2 Đồ th ị kết n ối 2.4 Kỹ thu ật phân m ảnh d ọc dữ li ệu 2.4.1 Khái ni ệm phân m ảnh d ọc Là phân chia quan h ệ R thành t ập các quan h ệ nh ỏ hơn để có nhi ều ứng d ụng có th ể ch ỉ cần th ực hi ện trên m ột m ảnh. Mảnh t ối ưu sinh ra m ột l ược đồ phân m ảnh cho phép gi ảm t ối thi ểu th ời gian th ực hi ện c ủa ứng d ụng trên m ảnh đó. Sử dụng hai ph ươ ng pháp Heuristic: Nhóm thu ộc tính và Tách m ảnh. 13 2.4.2 Thông tin c ần thi ết c ủa phân m ảnh d ọc a) Ma tr ận giá tr ị sử dụng thu ộc tính: Ký hi ệu ma tr ận giá tr ị sử dụng thu ộc tính là use(q i, Aj), Q={q 1, q 2,.., q q} là t ập các câu truy v ấn c ủa ng ười s ử dụng. Các câu truy v ấn Q s ẽ ch ạy trên quan h ệ R(A 1, A 2,…, A n). 1 Nếu thu ộc tính A j được v ấn tin qi tham chi ếu Use(q i,A j) = i=1..q và j=1..n 0 Ng ược l ại Các vector Use(q i,*) được hi ểu là câu truy v ấn q i được ch ạy trên c ơ s ở dữ li ệu. b) Ma tr ận l ực hút AA( Attribute Affinity Matrix) c ủa thu ộc tính: R(A 1,A 2,…,A n) là m ột quan h ệ trên t ập các thu ộc tính Ω={A 1,A 2,…,A n}. K là s ố mảnh c ủa quan h ệ R c ần ph ải được phân tán trên m ạng máy tính, t ức là: R = R 1∪R2∪…∪Rk. = aff (Ai ,A j ) ∑ ∑ref l (qk )acc l (qk ) ∧ ∀ k[( use (qk ,Ai ) use (qk ,Aj )l Sl ref l (q k) là s ố lần truy xu ất các thu ộc tính(Ai,Aj) cho q k tại v ị trí Sl và acc l (q k) là s ố đo t ần s ố truy xu ất ứng d ụng q k tại v ị trí S l. 2.4.3 Thu ật toán t ụ nhóm Thu ật toán th ực hi ện b ằng cách nhóm các thu ộc tính của m ột quan h ệ dựa trên các giá tr ị lực hút thu ộc tính trong ma tr ận AA đầu vào. Số đo l ực hút chung lớn nh ất là AM (Global Affinity Measure). Ma tr ận l ực hút t ụ CA (Cluster Affinity) là Kết qu ả, gồm có 3 b ước : 14 2.4.4 Thu ật toán phân m ảnh Là xác định các t ập thu ộc tính được truy xu ất b ởi các tập ứng d ụng. Trong ma tr ận t ụ lực hút CA c ủa quan h ệ, trong hình 2.4 n ếu m ột điểm trên đường chéo chính được ch ọn, hai tập thu ộc tính s ẽ được xác định. M ột t ập {A 1,A 2,.....,A i} ở góc trái cao nh ất, g ọi là t ập đỉnh TA (Top) và t ập th ứ hai {A i+1 ,...,A n} ở góc ph ải th ấp nh ất, g ọi là t ập đáy BA (Bottom). A A .... A A ...... A 1 2 i i+1 n A1 .... TA A2 .Ai A .... i+1 BA . Hình 2.4 C ấp phát điểm tách 2.5 Bài toán phân b ố dữ li ệu 2.5.1 Khái ni ệm Là bài toán để gi ải quy ết các vấn đề không thu ận l ợi nhu là: các m ảnh được mô hình hóa không thích h ợp hoàn toàn nh ư các t ệp riêng, s ố mảnh nhi ều h ơn so v ới các quan h ệ toàn cục... Nh ững vấn đề đặt ra này là phân b ố dữ li ệu sao cho t ối ưu đối v ới các ứng d ụng. 15 2.5.2 Bài toán phân b ố Ký hi ệu x j là bi ến quy ết định (Decisio Variable) ch ọn vị trí để đặt sao l ưu: 1 N ếu m ảnh F k được đặt t ại v ị trí S j xj = 0 Trong tr ường h ợp ng ược l ại. Khi đó đặc t ả chính xác nh ư sau:  m   ' + +  min ∑( ∑ x ju jcij t j min cij ) ∑ x jd j j S ∈I  i=1 ∈ j ∈   j S j I j S j I  Trong đó x j bằng 0 ho ặc 1. 2.5.3 Thông tin c ần thi ết cho bài toán phân b ố Các thông tin c ần cho bài toán phân bố có th ể phân chia thành b ốn lo ại: thông tin CSDL, thông tin ứng d ụng, thông tin về vị trí và thông tin v ề mạng. 2.5.4 Mô hình phân b ố d ữ li ệu Là mô hình để gi ảm t ối thi ểu tổng chi phí x ử lý và l ưu tr ữ, đáp ứng được các đòi h ỏi v ề th ời gian đáp ứng. 2.6 Xử lý truy v ấn phân tán d ữ li ệu Xử lý truy v ấn phân tán là quá trình chuy ển đổi câu truy vấn ngôn ng ữ bậc cao trên c ơ s ở dữ li ệu phân tán thành m ột chu ỗi các thao tác c ủa đại s ố quan h ệ trên các m ảnh phân tán. Bao g ồm nhi ều b ước th ực hi ện cụ th ể nh ư sau: • Câu truy v ấn phân tán ph ải được phân rã thành m ột chu ỗi các thao tác d ựa trên các phép tính đại s ố quan h ệ. 16 • Dữ li ệu được truy nh ập b ởi truy v ấn là nh ững m ảnh dữ li ệu được phân rã, được g ọi là d ữ li ệu c ục b ộ. • Phép truy v ấn đại s ố trên các m ảnh ph ải được m ở rộng v ới các thao tác truy ền thông và t ối ưu hoá ch ức n ăng tham chi ếu các ngu ồn tài nguyên. 2.6.1 V ấn đề x ử lý truy v ấn Vì có nhi ều gi ải pháp bi ến đổi, m ỗi gi ải pháp khác nhau có th ể tiêu th ụ tài nguyên c ủa m ạng máy tính khác nhau. Vậy, cần ph ải l ựa ch ọn m ột gi ải pháp khi th ực hi ện, nó tiêu th ụ tài nguyên c ủa m ạng là t ối thi ểu. Có hai ph ươ ng pháp t ối ưu hóa truy v ấn c ơ b ản: ph ươ ng pháp bi ến đổi m ột câu truy v ấn phép tính đại s ố quan h ệ thành câu