Luận văn thạc sĩ: Tối ưu hóa truy vấn cơ sở dữ liệu song song

Chia sẻ: Sdfas Vfdtg | Ngày: | Loại File: PDF | Số trang:13

Thêm vào BST

Báo xấu

181
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tối ưu hóa truy vấn cơ sở dữ liệu song song nhằm nghiên cứu một số kiến trúc CSDL song song các phương pháp song song hóa dữ liệu.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn thạc sĩ: Tối ưu hóa truy vấn cơ sở dữ liệu song song

1 2 Công trình ñư c hoàn thành t i B GIÁO D C VÀ ĐÀO T O Đ I H C ĐÀ N NG Đ I H C ĐÀ N NG BÙI TH L A Ngư i hư ng d n khoa h c: PGS.TSKH. TR N QU C CHI N T I ƯU HOÁ TRUY V N Ph n bi n 1: TS. NGUY N M U HÂN CƠ S D LI U SONG SONG Ph n bi n 2: TS. NGUY N TR N QUANG VINH Chuyên ngành: KHOA H C MÁY TÍNH Mã s : 60.48.01 Lu n văn ñư c b o v t i H i ñ ng ch m Lu n văn t t nghi p th c sĩ K thu t h p t i Đ i h c Đà N ng vào ngày 14 tháng 10 năm 2010. TÓM T T LU N VĂN TH C SĨ K THU T Có th tìm hi u lu n văn t i: - Trung tâm Thông tin-H c li u, Đ i h c Đà N ng ĐÀ N NG – Năm 2010 - Trung tâm h c li u, Đ i h c Đà N ng
3 4 - Thu th p và phân tích các tài li u và thông tin liên quan ñ n ñ tài. M Đ U - L a ch n, ñ xu t phương hư ng gi i quy t v n ñ . - Ki m tra, th nghi m và ñánh giá k t qu 1. Lý do ch n ñ tài Đ khai thác các kh năng c a các máy CSDL song song nh m 5. Ý nghĩa khoa h c và th c ti n c a ñ tài ñ t ñư c hi u qu t t nh t có th . Cùng v i vi c x lý các truy v n, - T i ưu hoá truy v n song song quy t ñ nh t c ñ h i ñáp t i ưu hoá truy v n trên môi trư ng ña x lý là m t v n ñ quan tr ng nhanh nh t có th có cho các truy v n, qua ñó giúp vi c t ch c và d n t i s thành công trong k thu t CSDL song song. Nó quy t ñ nh khai thác các cơ s d li u trên môi trư ng ña x lý có hi u qu t t t c ñ h i ñáp nhanh nh t có th cho các truy v n, ñó là lý do chính hơn. y u ñ s d ng các h th ng song song. - Các thu t toán ñư c nghiên c u d a trên k thu t quy ho ch ñ ng, có tính ñ n các chi phí phân b l i, là m t ñóng góp cho giai 2. M c ñích nghiên c u ño n t i ưu hoá truy v n song song. - Nghiên c u m t s ki n trúc CSDL song song, các phương pháp song song hoá d li u nh m gi i quy t v n ñ b t c vào ra 6. C u trúc c a lu n văn thư ng g p trong các h CSDL song song. Lu n văn g m 4 chương: - Nghiên c u phương pháp t i ưu hoá hai pha và các thu t toán Chương 1: Chương này s gi i thi u qua m t s ho t ñ ng c a bài trong giai ño n ñ u c a mô hình t i ưu hoá hai pha nh m bi u di n toán t i ưu hoá truy v n trong các môi trư ng: T p trung, phân tán và l i câu truy v n thành cây truy v n có chú gi i. song song. Chương 2: Trình bày nh ng v n ñ v các ki n trúc CSDL 3. Đ i tư ng và ph m vi nghiên c u song song và các chi n lư c song song hoá d li u. - Nghiên c u m t s ki n trúc CSDL song song và các chi n Chương 3: Trình bày m t mô hình t i ưu hoá truy v n cho lư c song song hoá d li u. CSDL song song ñ th y s khác nhau gi a t i ưu hoá truy v n cho - Nghiên c u quá trình t i ưu hoá truy v n song song: Nghiên CSDL song song và CSDL tu n t c ñi n. c u mô hình t i ưu hoá truy v n cho CSDL song song, và các thu t Chương 4: Trình bày m t s minh ho cho các thu t toán ñã ñư c toán liên quan ñ n bài toán t i ưu hoá truy v n trên môi trư ng x lý trình bày trong chương 3. song song. K t thúc lu n văn này là ph n k t lu n, tóm lư c l i nh ng v n 4. Phương pháp nghiên c u ñ ñã trình bày và m t s hư ng phát tri n trong tương lai.
5 6 CHƯƠNG 1: T I ƯU HOÁ TRUY V N TRONG 1.2.3.4. S d ng các n i n a CÁC MÔI TRƯ NG: T P TRUNG, PHÂN TÁN 1.2.4. Các t ng x lý v n tin VÀ SONG SONG 1.2.4.1. Phân rã v n tin 1.1. T I ƯU HOÁ TRUY V N TRONG CƠ S D LI U T P TRUNG 1.2.4.2. C c b hoá d li u 1.1.1. Bài toán x lý v n tin t p trung 1.2.4.3. T i ưu hoá v n tin toàn c c 1.1.2. Ngôn ng 1.2.4.4. T i ưu hoá v n tin c c b 1.1.3. Các ki u t i ưu hoá 1.3. T I ƯU HOÁ TRUY V N SONG SONG M t y u t d n ñ n s thành công c a các h cơ s d li u ña 1.1.4. Th i ñi m t i ưu hoá x lý này là tính hi u qu c a b t i ưu hoá. Ch c năng chính c a b 1.1.5. S li u th ng kê t i ưu là tìm m t chi n lư c th c thi t t nh t cho câu truy v n SQL ñ u vào. Đ u ra c a b t i ưu là m t l ch trình bao g m các truy v n 1.2. T I ƯU HOÁ TRUY V N TRONG CƠ S D LI U ñ i s và th t th c hi n c a chúng ñư c xác ñ nh trên các m nh d PHÂN TÁN li u các nút cùng v i các phép toán truy n thông có s n. Các 1.2.1. Bài toán x lý v n tin phân tán phương pháp t i ưu truy v n trong môi trư ng ña x lý dư i d ng 1.2.2. Mô hình chi phí phân tán nh ng thu t gi i Heuristic ñã ñư c áp d ng trong các h CSDL song song. 1.2.3. Mô t ñ c trưng c a th x lý v n tin phân tán - Phương pháp c ñi n Th x lý v n tin phân tán cũng có các ñ c trưng như ñ i v i - Phương pháp quy ho ch ñ ng x lý v n tin t p trung như ngôn ng , các ki u t i ưu hoá, th i ñi m - Phương pháp t i ưu hoá hai pha: K th a nh ng ưu ñi m t i ưu hoá, s li u th ng kê. c a chi n lư c t i ưu trong x lý tu n t , phương pháp này ñư c chia Ngoài ra, th x lý v n tin phân tán còn có các ñ c trưng thành hai nhi m v con: Đ u tiên, ñưa ra m t phương án th c hi n sau: mà chưa ph i chú ý ñ n cách phân ph i công vi c cho các b x lý. 1.2.3.1. V trí quy t ñ nh Sau ñó, ñưa ra m t l ch bi u và phương án t i ưu th c hi n song song 1.2.3.2. T n d ng c u hình m ng các phép toán có ñư c t nhi m v th nh t. Đi u thu n ti n c a chi n lư c t i ưu hoá hai pha là m m d o, ñơn gi n và t n d ng ñư c 1.2.3.3. T n d ng các m nh nhân b n nh ng k t qu v t i ưu hoá trong môi trư ng x lý tu n t .
7 8 CHƯƠNG 2: KI N TRÚC CÁC 2.1.3. Ki n trúc không chia s (shared nothing) H CƠ S D LI U SONG SONG M ng truy n thông Ký hi u 2.1. CÁC KI N TRÚC C A H TH NG MÁY TÍNH SONG SONG M : B nh 2.1.1. Ki n trúc m i th dùng chung (shared everything) P P …..... P P : B x lý Ký hi u M M …..... M M : B nh M M …..... M D : Đĩa D M ng truy n thông P : B x lý D D D …..... D D : Đĩa P P …..... P Hình 2.3: Ki n trúc không chia s 2.1.4. Ki n trúc phân c p Hình 2.1: Ki n trúc m i th dùng chung M ng truy n thông 2.1.2. Ki n trúc dùng chung ñĩa (shared disk) D Ký hi u Ký hi u P P P P P P M ng truy n thông D M : B nh M : B nh BUS ............ BUS P : B x lý P P …..... P P : B x lý M M D : Đĩa D : Đĩa D D M M …..... M C m1 C mn Hình 2.4: Ki n trúc phân c p Hình 2.2: Ki n trúc dùng chung ñĩa
9 10 2.2. CÁC K THU T PHÂN HO CH D LI U TRONG 2.3.1.2. L p l ch theo phương án CSDL SONG SONG 2.3.2. Song song n i truy v n Nh m gi i quy t v n ñ b t c vào ra thư ng g p trong các Song song n i truy v n là d ng song song hoá thi hành song h CSDL song song, ngoài vi c áp d ng m t ki n trúc ph n c ng song m t truy v n ñơn trên nhi u b x lý và ñĩa. thích h p, ngư i ta còn ph i ti n hành phân ho ch d li u m t cách h p lý cho các b x lý. 2.3.2.1. Song song ñ c l p 2.2.1. Phân ho ch theo vòng tròn Robin 2.3.2.2. Song song ñư ng ng 2.2.2. Phân ho ch theo hàm băm 2.3.3. Song song n i toán t Song song n i toán t là th c hi n m t phép toán quan h 2.2.3. Phân ho ch theo kho ng b ng cách dùng nhi u b x lý. 2.2.4. Phân ho ch theo m ng nhi u chi u 2.4. CÁC PHÉP TOÁN SONG SONG 2.3. CÁC CƠ CH X LÝ SONG SONG 2.4.1. Phép ghép Các phép truy v n trong mô hình quan h th c s phù h p Phép ghép dùng ñ k t h p nhi u dòng d li u song song v i vi c th c hi n song song. Truy v n quan h th c ch t là các phép thành m t dòng d li u ñơn. toán quan h th c hi n trên các dòng d li u có cùng c u trúc. Hơn n a, k t qu c a m i phép toán là m t quan h nên ta có th k t h p 2.4.2. Phép tách các phép toán thành các dòng d li u song song. Có hai lo i dòng d Khi th c hi n m t quy trình song song nhi u giai ño n, m t li u song song: song song ñư ng ng và song song phân ho ch. dòng d li u ñơn ph i ñư c tách thành nhi u dòng d li u ñ c l p. Phương pháp ti p c n dòng d li u song song cho phép s d ng các th t c tu n t s n có ñ th c hi n các phép toán ñã có m t cách song các C ng các song mà không ph i xây d ng các phép toán song song m i. dòng vào Quá trình th c C ng dòng d hi n phép toán Phép 2.3.1. Song song liên truy v n tách d li u Phép Song song liên truy v n là th c hi n nhi u truy v n cùng m t li u vào ghép C ng lúc b ng cách l p l ch th c hi n cho các toán t c a các truy v n ñó. ra vào 2.3.1.1. L p l ch trên cơ s c nh tranh Hình 2.7: Ghép các dòng d li u vào và tách các dòng d li u ra c a m t phép toán
11 12 2.4.3. Các thu t toán x lý các phép g p nhóm 3.1.2.4. Phép n a k t n i M t hàm g p nhóm SQL là m t hàm thao tác trên các nhóm 3.1.2.5. Phép h p m u tin có cùng m t tính ch t nào ñó. 3.1.2.6. Phép tr 2.4.3.1. Thu t toán tr n t p trung CM (Centralized Merging) 3.1.3. Chi phí song song 2.4.3.2. Thu t toán tr n phân tán DM (Distributed Merging) 3.1.4. Chi phí kh i ñ ng 2.4.3.3. Thu t toán phân ho ch l i Rep (Repartitioning) 3.1.5. Chi phí truy n thông 2.4.3.4. Các thu t toán th c hi n phép k t n i t nhiên 3.1.6. Ư c lư ng chi phí song song 3.2. MÔ HÌNH T I ƯU HOÁ TRUY V N CHO CSDL CHƯƠNG 3: T I ƯU HOÁ TRUY V N SONG SONG SONG SONG Trong ph n trình bày này, chúng ta s mô t chi ti t quá trình t i ưu hoá truy v n song song b ng mô hình t i ưu hoá truy v n hai 3.1. MÔ HÌNH CHI PHÍ C A B T I ƯU HOÁ TRUY pha ñ c c ti u hoá th i gian h i ñáp. Pha ñ u tiên áp d ng th thu t V N c c ti u hoá t ng kh i lư ng công vi c, trong pha sau s d ng hai th Chi phí th c hi n m t phương án t i ưu c a m t câu truy v n thu t phân chia công vi c lên nhi u b x lý. Vi c chia bài toán thành song song ñư c xác ñ nh b i ba thành ph n: t ng công vi c TW hai pha cho phép gi m ñ ph c t p khi t i ưu hoá câu truy v n song (Total Work), th i gian tr l i RT (Response Time) và chi phí không song. gian nh MC (Memory Consumption). Hàm chi phí là t h p c a hai thành ph n ñ u, thành ph n th ba cho bi t kích thư c b nh c n T I ƯU HOÁ TRUY V N cho vi c th c thi phương án. JOQR (Join Ordering and Query Rewriting) Song song hoá 3.1.1. Các th ng kê CSDL S p x p th t Câu truy v n phép n i SQL Trích cây Đi u ph i K ho ch 3.1.2. L c lư ng c a các k t qu trung gian & Bi u di n l i cây truy v n cây toán thi hành toán t song song truy v n có chú gi i t 3.1.2.1. Phép ch n 3.1.2.2. Phép chi u 3.1.2.3. Phép k t n i Hình 3.2: Các giai ño n c a quá trình t i ưu hoá truy v n hai pha
13 14 3.2.1. Cây truy v n có chú gi i Đ nh nghĩa 3.2: Toán t m t ngôi f là kh năng phân ho ch Cây truy v n có chú gi i là d ng trình bày truy n th ng c a ng v i phân ho ch α n u f ( S ) = f ( S0 ) ∪ f ( S1 ) ∪ ... ∪ f ( S k ) . Toán t hai phương án thi hành m t câu truy v n SQL. Nó mã hoá nh ng l a ngôi f là kh năng phân ho ch ng v i phân ho ch α nu f ( S , T ) = f ( S 0 , T0 ) ∪ f ( S1 , T1 ) ∪ ... ∪ f ( S k , Tk ) ch n mang tính th t c như th t th c hi n m i phép toán, phương . pháp tính toán m i toán t . M i nút c a cây ñ i di n cho m t (hay Đ nh nghĩa 3.3: M t phép toán ñư c g i là c m thu c tính nhi u) phép toán quan h , m i nút lá ñ i di n cho m t quan h toán n u nó ch kh phân ho ch trên các phân ho ch s d ng m t thu c h ng. Nh ng ghi chú trên m i nút mô t cách th c nó ñư c th c hi n tính nh t ñ nh. Ngư c l i, n u phép toán kh phân ho ch trên m i chi ti t như th nào. phân ho ch thì g i là b t c m thu c tính. 3.2.2. Cây toán t 3.3.1.2. Chi phí phân ho ch l i Cây toán t dùng ñ mô t các phép toán song song th c hi n Trư ng h p các toán t s d ng các phân ho ch khác nhau, cây truy v n cũng như các ràng bu c v th i gian gi a chúng. Các các b ñ u ra c a toán t này là ñ u vào c a toán t kia thì d li u nút c a m t cây toán t bi u di n các toán t và các ño n mã l nh c n ñư c phân ho ch l i theo ñúng yêu c u c a toán t sau. Chúng ta ñơn. Các c nh tư ng trưng cho các dòng d li u, hư ng ch c a m i nh n th y r ng, m t y u t quan tr ng nh hư ng ñ n chi phí th c c nh th hi n ràng bu c th i gian gi a các toán t . hi n truy v n là thu c tính ñư c s d ng ñ phân ho ch. 3.3. C C TI U HOÁ KH I LƯ NG TRUY V N SONG 3.3.1.3. Bài toán t i ưu hoá SONG Đ nh nghĩa 3.4: Màu c a m t nút trên cây truy v n là m t 3.3.1. Mô hình c c ti u phí t n truy n thông thu c tính ñư c s d ng cho vi c phân ho ch d li u t i nút ñó. M t Các phương pháp song song hoá phân ho ch v n khai thác c nh gi a nút i và j ñư c g i là c nh ña màu n u i và j ñư c gán hai s phân ho ch các quan h theo chi u ngang, các phương pháp này màu khác nhau. thư ng ñòi h i d li u ph i ñư c phân ho ch l i, do ñó s làm phát sinh thêm chi phí truy n thông. Trong m t cây truy v n, các nút là toán t c m thu c tính ho c b ng n n thì ñư c tô màu trư c, chúng ta t do n ñ nh màu cho 3.3.1.1. Phân ho ch các nút không màu còn l i. Đ nh nghĩa 3.1: M t phân ho ch là m t c p (a, h), trong ñó a là m t thu c tính và h là m t hàm, hàm này ánh x m t giá tr c a a M i c nh e c a cây truy v n chúng ta gán m t tr ng s Ce ñ thành m t giá tr không âm. tư ng trưng cho chi phí phân ho ch l i. Chi phí này ch ñư c tính khi c nh này là ña màu do ñó t ng chi phí phân ho ch l i chính là t ng
15 16 tr ng s c a các c nh ña màu. Bài toán t i ưu ñư c phát bi u dư i B ñ 3.1: T n t i m t phép tô màu t i ưu c t các c nh d ng bài toán tô màu như sau: e1 , e2 ,..., ed −1 . B ñ 3.2: T n t i phép tô màu t i ưu trong ñó có thu g n e2. “Cho trư c m t cây truy v n T=(V, E), g i Ce là tr ng s c a Lưu ý: Ch có các nút lá ñư c tô màu luôn ñư c gi v ng c nh e ∈ E, gi s m t s nút trong c a V ñư c tô màu trư c. Hãy tô sau m i khi áp d ng các b ñ c t/thu c nh. Do ñó, các b ñ này có màu cho các nút còn l i ñ c c ti u hoá t ng tr ng s c a các c nh th áp d ng cho b t kỳ m t cây không t m thư ng nào. Do vi c áp ña màu”. d ng b ñ làm gi m s c nh, vi c áp d ng l p l i nhi u l n s d n 3.3.2. Các thu t toán tô màu t i ưu cho m t cây truy v n ñ n t p nh ng cây t m thư ng. Nh n xét này d n ñ n thu t toán Tô 3.3.2.1. Bài toán tô màu ñơn gi n Màu dư i ñây trong vi c tìm phép tô màu t i ưu. Bài toán tô màu cho m t cây nói chung có th thu l i thành Thu t toán 3.2. Thu t toán ToMau bài toán tô màu m t t p các cây ñơn gi n, trong ñó t t c các nút Input Cây truy v n ñơn gi n, các nút lá tô màu trư c trong là chưa tô màu và t t c các nút lá là ñã ñư c tô màu trư c. Th khác nhau. t c Đơn Gi n Hoá sau ñây th c hi n ñơn gi n hoá cây truy v n. Output Cây ñư c tô màu. Thu t toán 3.1. Th t c ĐonGianHoa (Simplify) 1. While t n t i nút m m có b c t i thi u là 2 do Input Cây truy v n 2. Cho các c nh t nút m m ñ n d nút con là e1 ,..., ed Output Cây truy v n thu g n các lá không màu sao cho ; 1. While t n t i nút lá không màu l v i nút cha m do 3. If d>1 Then c t e1 ,..., ed −1 2. Thu g n l v m; 4. Else G i ep là c nh t m ñ n nút cha c a nó; 3. While t n t i nút trong có màu m b c d do 5. If Then thu g n e1 Else thu g n ep; 4. Tách m thành d nút b n sao, m i nút b n sao ñư c 6. End While; liên thông v i ph n còn l i b ng m t c nh; 7. Tô màu các cây t m thư ng; Do m i vòng l p làm gi m s c nh, th i gian th c hi n thu t 3.3.2.2. Thu t toán tham lam trong trư ng h p các màu tô toán là tuy n tính theo s c nh. trư c khác nhau Đ nh nghĩa 3.5: M t nút là nút m n u và ch n u t t c các 3.3.2.3. Thu t toán tách màu nút k là nút lá v i t i ña m t ngo i l . Trong trư ng h p này, nút lá Các ký hi u: ñư c g i là nút con c a nút m . G i Optc(i, A) là chi phí c c ti u c a phép tô màu cây con g c i sao cho i ñư c tô màu A.
17 18 G i Opt(i) là chi phí c c ti u ñ tô màu cây con g c i, b t 9. If Optc(αj, Màu(i)) ≤ cj +Opt(αj) then Màu(αj) = ch p màu c a i trư c ñó. Nghĩa là, Opt(i) = mina Optc(i, a), a là m t Màu(i) màu b t kỳ. 10. Else Màu(αj) = a ∈ C sao cho Optc(αj, B ñ 3.3: Chi phí c c ti u c a phép tô màu cây con g c i a)=Opt(αj); sao cho i có màu A ñư c xác ñ nh b i: End. Thu t toán Tách Màu không yêu c u t t c các nút lá c a cây ñ u vào ph i tô màu trư c mà ñi tìm phép tô màu t i ưu cho m i cây. Thu t toán này có th i gian th c hi n O(n|C|). B ñ 3.4: N u i nh n màu A trong m t phép tô màu t i ưu 3.3.2.4. Các m r ng: s d ng t p màu nào ñó, thì cũng t n t i m t phép tô màu t i ưu khác sao cho nút con B ñ 3.5: Chi phí c c ti u Optc(i, A) c a phép tô màu cây αj c a i có màu A n u Optc(αj, A)≤ cj +Opt(αj), trong trư ng h p con g c i sao cho i nh n màu A ñư c xác ñ nh b i công th c. ngư c l i thì s có màu a b t kỳ n u Optc(αj, a) = Opt(αj). Các b ñ 3.3 và 3.4 d n ñ n thu t toán Tách Màu dư i ñây. G i C là t p màu ñã ñư c dùng cho các nút ñư c tô màu trư c. Thu t toán 3.3. Thu t toán TachMau (Color Split) Input Cây truy v n T, t p màu C. 3.3.3. Mô hình cho các phương pháp và ñ c tính v t lý Output Phép tô màu t i ưu. 3.3.3.1. Chi phí c a cây truy v n có chú gi i 1. For m i nút i theo th t h u t do bư c 2 Các ký hi u: 2. For m i màu a ∈ C do bư c 3 và bư c 4 Rs là b ng R v i tính ch t th ng kê s. 3. Tính Optc(i, a) b ng cách s d ng b ñ 3.3; recolor(Rs, cold, cnew) là chi phí tô màu l i b ng R t màu cold 4. Opt(i) = mina Optc(i, a); thành màu cnew. 5. Tìm a∈C sao cho Optc(r, a) = Opt(r), trong ñó r là g c. inpCol(s, A, j) là m u màu c n cho chi n lư c s v i ñ u vào 6. Màu(r)=a; th j ñ ñư c k t xu t m u màu A. 7. For m i nút αj không ph i là g c theo th t ti n t do StrategyCost(s, R1s ,..., Rks ) là chi phí th c hi n chi n lư c tính bư c 8 ñ n bư c 10. toán s trên các b ng Ri. 8. G i i là nút cha c a αj; cj là tr ng s c a c nh n i i Gi s g c c a cây truy v n T s d ng chi n lư c s có màu và αj; c'j =inpCol(s, a, j) là ñ u ra là a. G i màu c a ñ u vào th j mà
19 20 chi n lư c s ñòi h i. Gi s T có k cây con T1, T2, …, Tk sao cho Tj màu mà các cây con g c t i α j có th nh n. StrategyCost(s, R1s,..., Rks ) t o ra b ng Rj v i màu cj. Khi ñó chi phí c a cây truy v n chú gi T là chi phí th c hi n chi n lư c tính toán s trên các b ng Ri. Thu t ñư c xác ñ nh như sau: toán Tách Màu M R ng dư i ñây ñ tính Optc và OptcStrategy. Công th c (3.8): Thu t toán 3.4. Thu t toán TachMauMoRong (Extended Color Split) Input Cây truy v n T v i màu c a các nút lá, t p màu C. 3.3.3.2. Thu t toán tách màu m r ng Output Cây v i chi n lư c tô màu có chi phí t i thi u. Đ nh nghĩa 3.6: OptcStrategy(i, A) là chi n lư c th c hi n 1. For m i nút i theo th t h u t do bư c 2 chi phí c c ti u Optc(i, A) (n u có nhi u chi n lư c thì ch n l y m t 2. For m i màu a ∈ C do dùng b ñ 3.6 ñ tính chi n lư c). OptcStrategy(i, A) không ñ nh nghĩa cho nút lá. Optc(i,a) và OptcStrategy(i,a) ; Đ nh nghĩa 3.7: Strategies(i, A) là t p h p nh ng chi n lư c 3. Xem r là g c và a là màu sao cho Optc(r, a)≤ Optc(r, c) có th áp d ng cho phép toán ñư c bi u di n b i nút i và ràng bu c v i m i màu c∈C; v ñ u vào-ñ u ra c a nó cho phép A như m t màu ñ u ra. 4. Màu t i ưu cho r là a và chi n lư c t i ưu là B ñ dư i ñây là trư ng h p t ng quát c a b ñ 3.5. OptcStrategy(r,a); B ñ 3.6: Cho cây truy v n T, i là m t nút trên T. Chi phí tô 5. For m i nút không là nút g c theo th t ti n t do bư c 6 màu t i thi u c a cây con g c i sao cho i có màu ñ u ra A, ký hi u 6. Tính màu t i ưu và các chi n lư c b ng cách áp d ng Optc(i, A), ñư c xác ñ nh b i các công th c dư i ñây. b ñ 3.6 “ngư c”; Trư ng h p i là nút lá, End. Thu t toán này có th i gian th c hi n trong trư ng h p x u nh t là nS|C|2 trong ñó S là s chi n lư c, |C| là s màu ñư c phép, còn n là s nút c a cây. Trư ng h p i không ph i là nút lá, Optc(i, A) ñư c tính theo 3.3.4. Mô hình cho th t phép k t n i công th c truy h i: 3.3.4.1. Th t th c hi n k t n i b qua các tính ch t v t lý Đ nh nghĩa 3.8: Cây k t n i (join tree) là m t cây truy v n có chú gi i, trong ñó, t t c các nút trong bi u di n các phép k t n i Trong ñó, S=Strategies(i, A) và OptcStrategy(i, A) là chi n và các nút lá bi u di n các b ng. lư c nào ñó mà th c hi n chi phí c c ti u Optc(i, A). C là m t t p
21 22 B ñ 3.7: N u OptPlan(Q)=[s, Tl, Tr] và Q = Ql ∪ Qr thì OptPlan(Ql)=Tl và OptPlan(Qr)=Tr, trong ñó Tl và Tr l n lư t là k t qu thu ñư c t nhánh truy v n Ql và Qr. Thu t toán 3.5. Thu t toán ĐinhThuTuPhepKet (Join Ordering) Trong ñó, Ql và Qr là t t c các t p sao cho Q=Ql ∪ Qr , Ql # Ø, Input Câu truy v n SPJ (ch n-chi u-k t n i) trên các Qr # Ø , S là t p t t c các chi n lư c t o nên tính ch t v t lý a. b ng T={T1, T2, …, Tn}. Thu t toán 3.6. Thu t toán ThuTuPhepKetVatLy (Join Ordering Output Cây k t n i t i ưu. With Physical Properties) 1. For i:=1 to n do OptPlan({Ti})=Ti; Input Câu truy v n SPJ (ch n-chi u-k t n i) trên các 2. For i:=2 to n do bư c 3 b ng T={T1, T2, …, Tn}. 3. For m i Q ⊆ T sao cho |Q|=i do bư c 4 và bư c 5 Output Cây k t n i t i ưu. 4. BestCost = ∞ ; 1. For i:=1 to n do bư c 2 5. For m i Ql ≠ Ø và Qr ≠ Ø sao cho 2. Tính Optc(Ti, a) theo công th c: Q = Qr ∪ Ql do bư c 6 và bư c 7 6. G i Rls và Rrs là các th ng kê c a các b ng ñư c tính t các truy v n Ql và Qr; 7. For m i chi n lư c k t n i s do bư c 8 ñ n 11 3. For i:= 2 to n do bư c 4 8. If StrategyCo st ( s , R , R ) < BestCost then l s s r 4. For m i Q ⊆ T sao cho Q = i do bư c 5 và 6 9. BestCost = StrategyCo st ( s , Rls , Rrs ) ; 5. Đ t Optc(Q, a) = ∞ cho m i tính ch t v t lý a ∈ C ; 10. OptPlan(Q)=[s,OptPlan(Ql),OptPlan(Qr)]; 6. For m i Ql ≠ Ø và Qr ≠ Ø sao cho Q = Q r ∪ Ql 11. End if do bư c 7 và 8 End. 7. G i Rls, Rrs là các tính ch t th ng kê c a các b ng Thu t toán này có ñ ph c t p O(3n). ñư c tính t các truy v n Ql, Qr; 3.3.4.2. Th t th c hi n phép k t n i v i các tính ch t v t lý 8. For m i tính ch t v t lý a ∈ C do bư c 9 9. For m i chi n lư c s có th t o ra tính ch t a B ñ 3.8: Optc(Q, a) tho mãn h th c truy h i sau: do bư c 10 và 11 10. Đ t s cos t = StrategyCo st ( s , Rls , Rrs ), al' = inpCol ( s, a,1) và ar' = inpCol ( s, a,2) ;
23 24 11. For m i tính ch t v t lý al ∈ C , ar ∈ C 4.2. MINH HO THU T TOÁN TÁCH MÀU M R NG do bư c 12 ñ n bư c 16 4.2.1. Bài toán 12. Đ t Đ u vào: Cho cây truy v n T=(V, E), trong ñó V là t p ñ nh và E là t p c nh. Các nút lá trong V ñã ñư c tô màu trư c. Cho O là t p các phép toán t i các nút trong. M i phép toán f∈O có m t t p các chi n lư c th c hi n Sf. D là tình tr ng v t lý c a CSDL. 13. If NewCost < Optc(Q, a) then Đ u ra: Chi n lư c th c hi n có phí t n ít nh t, màu ñ u ra 14. Optc(Q, a) = NewCost; và các ñ u vào cho m i nút trong. 15. OptPlan(Q, a) = [s, OptPlan(Ql , al ), OptPlan(Qr , ar )]; 16. End if 4.2.2. Các gi i thích 17. Return min a∈C OptPlan(T , a ); 4.2.3. Cơ s tính toán 3.3.5. Tóm L i 4.2.4. K t qu cài ñ t 4.3. MINH HO THU T TOÁN TH T PHÉP K T V T CHƯƠNG 4: CÀI Đ T MINH HO LÝ CÁC THU T TOÁN 4.3.1. Bài toán 4.1. MINH HO THU T TOÁN TÁCH MÀU Đ u vào: Cho cây truy v n k t n i-ch n-chi u lên trên t p 4.1.1. Bài toán tô màu cây truy v n các b ng T = {T1, T2, …, Tn}. Cho O là t p các phép toán t i các nút Đ u vào: Cho trư c m t cây truy v n T=(V, E), trong ñó V trong. M i phép toán f∈ O có m t t p các chi n lư c th c hi n Sf. D là t p ñ nh và E là t p c nh. M i c nh e∈E có m t tr ng s Ce, m t là tình tr ng v t lý c a CSDL T. s nút trong V ñư c tô màu trư c. Đ u ra: Cây k t n i t i ưu Đ u ra: Cây truy v n ñư c tô màu sao cho t ng tr ng s các 4.3.2. Cơ s tính toán c nh nhi u màu là nh nh t. 4.3.2. K t qu cài ñ t 4.1.2. Cơ s tính toán 4.4. CÔNG TH C TÍNH CHI PHÍ 4.1.3. K t qu cài ñ t
25 26 K T LU N VÀ HƯ NG PHÁT TRI N cách ti p c n hai giai ño n do W. Hong ñ xu t ñã ñư c nhi u nhà tin h c quan tâm phát tri n. Lu n văn này ñã dành ph n l n trình bày ñ 1. K t lu n kh o sát giai ño n ñ u c a cách ti p c n này nh m: c c ti u hoá kh i CSDL trên các máy tính song song cho phép gi m th i gian lư ng truy v n. Các thu t toán ñư c trình bày, d a trên k thu t quy thi hành các truy v n và gia tăng lư ng giao tác ñư c th c hi n. Hi n ho ch ñ ng, có tính ñ n các chi phí phân b l i, là m t ñóng góp b nay, có các ki n trúc máy song song ñư c s d ng: ki n trúc m i th sung cho giai ño n t i ưu hoá truy v n. Thu t toán Tách Màu cho dùng chung, ki n trúc dùng chung ñĩa, ki n trúc không chia s , ki n phép xác ñ nh thu c tính phân b t i t ng nút c a cây truy v n. Thu t trúc phân c p là s pha tr n gi a các ki n trúc trên. Nh m gi i quy t toán Tách Màu M R ng cho phép xác ñ nh các chi n lư c th c hi n v n ñ b t c vào ra thư ng g p trong các h CSDL song song, ngoài t i ưu cho t ng phép toán trên cây. Thu t toán Th T Phép K t V t vi c áp d ng m t ki n trúc ph n c ng thích h p thì chúng ta ph i ti n Lý cho phép xác ñ nh th t các phép k t n i t t nh t cho m t câu hành phân ho ch d li u m t cách h p lý cho các b x lý, các H truy v n k t n i-ch n-chi u. Các thu t toán này có th có hai cách s qu n tr CSDL trên các máy nhi u b x lý thư ng s d ng các k d ng: thu t phân ho ch d li u: phân ho ch theo vòng tròn Robin, phân - K t h p v i b t i ưu hoá quy ư c cho B t i ưu hoá trong ho ch theo hàm băm, phân ho ch theo kho ng, phân ho ch theo các máy song song. m ng nhi u chi u. Vi c khai thác ti m năng x lý song song có th - Tích h p c 3 thu t toán ñ thay th cho b T i ưu hoá qui ñư c th c hi n theo các cơ ch khác nhau: song song liên truy v n, ư c. song song n i truy v n, song song n i toán t . Song song liên truy Đ minh ho cho các thu t toán trên, lu n văn trình bày m t v n là th c hi n nhi u truy v n cùng m t lúc b ng cách l p l ch th c cài ñ t trên Visual Basic. Các cài ñ t ch y u ñ ch ng minh tính kh hi n cho các toán t c a các truy v n ñó. Đi u này cho phép gia tăng thi c a thu t toán. thông lư ng h th ng. Song song n i truy v n là d ng song song hoá thi hành song song m t truy v n ñơn trên nhi u b x lý và ñĩa. 2. Hư ng phát tri n Nghĩa là, nó th c hi n t ng truy v n m t và cho phép th c hi n ñ ng Hư ng phát tri n c a lu n văn: tìm hi u v v n ñ “l p l ch th i các phép toán trên truy v n ñó. Song song m t truy v n cho phép t i ưu cho cây truy v n song song”. Nghĩa là, chúng ta s ti p c n bài gia tăng t c ñ th c hi n truy v n ñó. Song song n i toán t là th c toán l p l ch t i ưu cho cây toán t nh n ñư c t giai ño n JOQR, hi n m t phép toán quan h b ng cách dùng nhi u b x lý. nh m tìm ki m m t s phân chia h p lý các nút c a cây toán t cho M t v n ñ mà t t c các H qu n tr CSDL cho phép các các b x lý ñ th i gian tr l i truy v n là nh nh t. truy v n khai báo ph i gi i quy t là bài toán T i ưu hoá truy v n. Trên môi trư ng song song, m t mô hình t i ưu hoá truy v n d a trên