markdown:
# Hệ quản trị cơ sở dữ liệu - chương 3 - Lưu trữ và cấu trúc tập tin
Chia sẻ: Danh Ngoc | Ngày: | Loại File: PDF | Số trang:39
lượt xem 344
download
![](http://image.tlvnimg.com/document/thumbnail/2010/20100509/nuoiheocuoivo/80x100/199706_247.jpg)
##
Hệ quản trị cơ sở dữ liệu - chương 3 - Lưu trữ và cấu trúc tập tin
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
MỤC ĐÍCH Chương này trình bày các vấn đề liên quan đến vấn đề lưu trữ dữ liệu (trên lưu trữ ngoài, chủ yếu trên đĩa cứng). Việc lưu trữ dữ liệu phải được tổ chức sao cho có thể cất giữ một lượng lớn, có thể rất lớn dữ liệu nhưng quan trọng hơn cả là sự lưu trữ phải cho phép lấy lại dữ liệu cần thiết mau chóng. Các cấu trúc trợ giúp cho truy xuất nhanh dữ liệu được trình bày là: chỉ mục (indice), B+ cây (B+-tree), băm (hashing) ... Các thiết bị lưu trữ...
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Hệ quản trị cơ sở dữ liệu - chương 3 - Lưu trữ và cấu trúc tập tin
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU CHƯƠNG III LƯU TRỮ VÀ CẤU TRÚC TẬP TIN (Storage and File Structure) MỤC ĐÍCH Chương này trình bày các vấn đề liên quan đến vấn đề lưu trữ dữ liệu (trên lưu trữ ngoài, chủ yếu trên đĩa cứng). Việc lưu trữ dữ liệu phải được tổ chức sao cho có thể cất giữ một lượng lớn, có thể rất lớn dữ liệu nhưng quan trọng hơn cả là sự lưu trữ phải cho phép lấy lại dữ liệu cần thiết mau chóng. Các cấu trúc trợ giúp cho truy xuất nhanh dữ liệu được trình bày là: chỉ mục (indice), B+ cây (B+-tree), băm (hashing) ... Các thiết bị lưu trữ (đĩa) có thể bị hỏng hóc không lường trước, các kỹ thuật RAID cho ra một giải pháp hiệu quả cho vấn đề này. YÊU CẦU Hiểu rõ các đặc điểm của các thiết bị lưu trữ, cách tổ chức lưu trữ, truy xuất đĩa. Hiểu rõ nguyên lý và kỹ thuật của tổ chức hệ thống đĩa RAID Hiểu rõ các kỹ thuật tổ chức các mẩu tin trong file Hiểu rõ các kỹ thuật tổ chức file Hiểu và vận dụng các kỹ thuật hỗ trợ tìm lại nhanh thông tin: chỉ mục (được sắp, B+-cây, băm) CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 34
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU KHÁI QUÁT VỀ PHƯƠNG TIỆN LƯU TRỮ VẬT LÝ Có một số kiểu lưu trữ dữ liệu trong các hệ thống máy tính. Các phương tiện lưu trữ được phân lớp theo tốc độ truy xuất, theo giá cả và theo độ tin cậy của phương tiện. Các phương tiện hiện có là: • Cache: là dạng lưu trữ nhanh nhất và cũng đắt nhất trong các phương tiện lưu trữ. Bộ nhớ cache nhỏ; sự sử dụng nó được quản trị bởi hệ điều hành • Bộ nhớ chính (main memory): Phương tiện lưu trữ dùng để lưu trữ dữ liệu sẵn sàng được thực hiện. Các chỉ thị máy mục đích chung (general-purpose) hoạt động trên bộ nhớ chính. Mặc dầu bộ nhớ chính có thể chứa nhiều megabytes dữ liệu, nó vẫn là quá nhỏ (và quá đắt giá) để lưu trữ toàn bộ một cơ sở dữ liệu. Nội dung trong bộ nhớ chính thường bị mất khi mất cấp nguồn • Bộ nhớ Flash: Được biết như bộ nhớ chỉ đọc có thể lập trình, có thể xoá (EEPROM: Electrically Erasable Programmable Read-Only Memory), Bộ nhớ Flash khác bộ nhớ chính ở chỗ dữ liệu còn tồn tại trong bộ nhớ flash khi mất cấp nguồn. Đọc dữ liệu từ bộ nhớ flash mất ít hơn 100 ns , nhanh như đọc dữ liệu từ bộ nhớ chính. Tuy nhiên, viết dữ liệu vào bộ nhớ flash phức tạp hơn nhiều. Dữ liệu được viết (một lần mất khoảng 4 đến 10 μs) nhưng không thể viết đè trực tiếp. Để viết đè bộ nhớ đã được viết, ta phải xoá trắng toàn bộ bộ nhớ sau đó mới có thể viết lên nó. • Lưu trữ đĩa từ (magnetic-disk): (ở đây, được hiểu là đĩa cứng) Phương tiện căn bản để lưu trữ dữ liệu trực tuyến, lâu dài. Thường toàn bộ cơ sở dữ liệu được lưu trữ trên đĩa từ. Dữ liệu phải được chuyển từ đĩa vào bộ nhớ chính trước khi được truy nhập. Khi dữ liệu trong bộ nhớ chính này bị sửa đổi, nó phải được viết lên đĩa. Lưu trữ đĩa được xem là truy xuất trực tiềp vì có thể đọc dữ liệu trên đĩa theo một thứ tự bất kỳ. Lưu trữ đĩa vẫn tồn tại khi mất cấp nguồn. Lưu trữ đĩa có thể bị hỏng hóc, tuy không thường xuyên. • Lưu trữ quang (Optical storage): Dạng quen thuộc nhất của đĩa quang học là loại đĩa CD-ROM : Compact-Disk Read-Only Memory. Dữ liệu được lưu trữ trên các đĩa quang học được đọc bởi laser. Các đĩa quang học CD-ROM chỉ có thể dọc. Các phiên bản khác của chúng là loại đĩa quang học: viết một lần, đọc nhiều lần (write-once, read-many: WORM) cho phép viết dữ liệu lên đĩa một lần, không cho phép xoá và viết lại, và các đĩa có thể viết lại (rewritable) v..v • Lưu trữ băng từ (tape storage): Lưu trữ băng từ thường dùng để backup dữ liệu. Băng từ rẻ hơn đĩa, truy xuất dữ liệu chậm hơn (vì phải truy xuất tuần tự). Băng từ thường có dung lượng rất lớn. Các phương tiện lưu trữ có thể được tổ chức phân cấp theo tốc độ truy xuất và giá cả. Mức cao nhất là nhanh nhất nhưng cũng là đắt nhất, giảm dần xuống các mức thấp hơn. Các phương tiện lưu trữ nhanh (cache, bộ nhớ chính) được xem như là lưu trữ sơ cấp (primary storage), các thiết bị lưu trữ ở mức thấp hơn như đĩa từ được xem như lưu trữ thứ cấp hay lưu trữ trực tuyến (on-line storage), còn các thiết bị lưu trữ ở mức thấp nhất và gần thấp nhất như đĩa quang học, băng từ kể cả các đĩa mềm được xếp vào lưu trữ tam cấp hay lưu trữ không trực tuyến (off-line). Bên cạnh vấn đề tốc độ và giá cả, ta còn phải xét đến tính lâu bền của các phương tiện lưu trữ. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 35
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU C h M i M Fl h M M i di k O i l di k M i Phân cấp thiết bị lưu trữ ĐĨA TỪ ĐẶC TRƯNG VẬT LÝ CỦA ĐĨA Mỗi tấm đĩa có dạng hình tròn, hai mặt của nó được phủ bởi vật liệu từ tính, thông tin được ghi trên bề mặt đĩa. Đĩa gồm nhiều tấm đĩa. Ta sẽ sử dụng thuật ngữ đĩa để chỉ các đĩa cứng. Khi đĩa được sử dụng, một động cơ ổ đĩa làm quay nó ở một tốc độ không đổi. Một đầu đọc-viết được định vị trên bề mặt của tấm đĩa. Bề mặt tấm đĩa được chia logic thành các rãnh, mỗi rãnh lại được chia thành các sector, một sector là một đơn vị thông tin nhỏ có thể được đọc, viết lên đĩa. Tuỳ thuộc vào kiểu đĩa, sector thay đổi từ 32 bytes đến 4095 bytes, thông thường là 512 bytes. Có từ 4 đến 32 sectors trên một rãnh, từ 20 đén 1500 rãnh trên một bề mặt. Mỗi bề mặt của một tấm đĩa có một đầu đọc viết, nó có thể chạy dọc theo bán kính đĩa để truy cập đến các rãnh khác nhau. Một đĩa gồm nhiều tấm đĩa, các đầu đọc-viết của tất cả các rãnh được gắn vào một bộ được gọi là cánh tay đĩa, di chuyển cùng nhau. Các tấm đĩa được gắn vào một trục quay. Vì các đầu đọc-viết trên các tấm đĩa di chuyển cùng nhau, nên khi đầu đọc-viết trên một tấm đĩa đang ở rãnh thứ i thì các đầu đọc-viết của các tấm đĩa khác cũng ở rãnh thứ i , do vậy các rãnh thứ i của tất cả các tấm đĩa được gọi là trụ (cylinder) thứ i . Một bộ điều khiển đĩa -- giao diện giữa hệ thống máy tính và phần cứng hiện thời của ổ đĩa. Nó chấp nhận các lệnh mức cao để đọc và viết một sector, và khởi động các hành động như di chuyển cánh tay đĩa đến các rãnh đúng và đọc viết dữ liệu. bộ điều khiển đĩa cũng tham gia vào checksum mỗi sector được viết. Checksum được tính từ dữ liệu được viết lên sector. Khi sector được đọc lại, checksum được tính lại từ dữ liệu được lấy ra và so sánh với checksum đã lưu trữ. Nếu dữ liệu bị sai lạc, checksum được tính sẽ không khớp với checksum đã lưu trữ. Nếu lỗi như vậy xảy ra, bộ điều khiển sẽ lặp lại việc đọc vài lần, nếu lỗi vẫn xảy ra, bộ điều khiển sẽ thông báo việc đọc thất bại. Bộ điều khiển đĩa còn có CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 36
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU chức năng tái ánh xạ các sector xấu: ánh xạ các sector xấu đến một vị trí vật lý khác. Hình dưới bày tỏ các đĩa được nối với một hệ thống máy tính: System bus Disk controller Disks Các đĩa được nối với một hệ thống máy tính hoặc một bộ điều khiển đĩa qua một sự hợp nhất tốc độ cao. Hợp nhất hệ thống máy tính nhỏ (Small Computer-System Interconnect: SCSI) thường được sử dụng để nối kết các đĩa với các máy tính cá nhân và workstation. Mainframe và các hệ thống server thường có các bus nhanh hơn và đắt hơn để nối với các đĩa. Các đầu đọc-viết được giữ sát với bề mặt đĩa như có thể để tăng độ dày đặc (density). Đĩa đầu cố định (Fixed-head) có một đầu riêng biệt cho mỗi rãnh, sự sắp xếp này cho phép máy tính chuyển từ rãnh này sang rãnh khác mau chóng, không phải di chuyển đầu đọc-viết. Tuy nhiên, cần một số rất lớn đầu đọc-viết, điều này làm nâng giá của thiết bị. ĐO LƯỜNG HIỆU NĂNG CỦA ĐĨA Các tiêu chuẩn đo lường chất luợng chính của đĩa là dung lượng, thời gian truy xuất, tốc độ truyền dữ liệu và độ tin cậy. - Thời gian truy xuất (access time): là khoảng thời gian từ khi yêu cầu đọc/viết được phát đi đến khi bắt đầu truyền dữ liệu. Để truy xuất dữ liệu trên một sector đã cho của một đĩa, đầu tiên cánh tay đĩa phải di chuyển đến rãnh đúng, sau đó phải chờ sector xuất hiện dưới nó, thời gian để định vị cánh tay được gọi là thời gian tìm kiếm (seek time), nó tỷ lệ với khoảng cách mà cánh tay phải di chuyển, thời gian tìm kiếm nằm trong khoảng 2..30 ms tuỳ thuộc vào rãnh xa hay gần vị trí cánh tay hiện tại. - Thời gian tìm kiếm trung bình (average seek time): Thời gian tìm kiếm trung bình là trung bình của thời gian tìm kiếm, được đo luờng trên một dãy các yêu cầu ngẫu nhiên (phân phối đều), và bằng khoảng 1/3 thời gian tìm kiếm trong trường hợp xấu nhất. - Thời gian tiềm ẩn luân chuyển (rotational latency time): Thời gian chờ sector được truy xuất xuất hiện dưới đầu đọc/viết. Tốc độ quay của đĩa nằm trong khoảng 60..120 vòng quay trên giây, trung bình cần nửa vòng quay để sector cần thiết nằm dưới đầu đọc/viết. Như vậy, thời gian tiềm ẩn trung bình (average latency time) bằng nửa thời gian quay một vòng đĩa. Thời gian truy xuất bằng tổng của thời gian tìm kiếm và thời gian tiềm ẩn và nằm trong khoảng 10..40 ms. - Tốc độ truyền dữ liệu: là tốc độ dữ liệu có thể được lấy ra từ đĩa hoặc được lưu trữ vào đĩa. Hiện nay tốc này vào khoảng1..5 Mbps CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 37
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU - Thời gian trung bình không sự cố (mean time to failure): lượng thời gian trung bình hệ thống chạy liên tục không có bất kỳ sự cố nào. Các đĩa hiện nay có thời gian không sự cố trung bình khoảng 30000 .. 800000 giờ nghĩa là khoảng từ 3,4 đến 91 năm. TỐI ƯU HÓA TRUY XUẤT KHỐI ĐĨA (disk-block) Yêu cầu I/O đĩa được sinh ra cả bởi hệ thống file lẫn bộ quản trị bộ nhớ ảo trong hầu hết các hệ điều hành. Mỗi yêu cầu xác định địa chỉ trên đĩa được tham khảo, địa chỉ này ở dạng số khối. Một khối là một dãy các sector kề nhau trên một rãnh. Kích cỡ khối trong khoảng 512 bytes đến một vài Kbytes. Dữ liệu được truyền giữa đĩa và bộ nhớ chính theo đơn vị khối. Mức thấp hơn của bộ quản trị hệ thống file sẽ chuyển đổi địa chỉ khối sang số của trụ, của mặt và của sector ở mức phần cứng. Truy xuất dữ liệu trên đĩa chậm hơn nhiều so với truy xuất dữ liệu trong bộ nhớ chính, do vậy cần thiết một chiến lược nhằm nâng cao tốc độ truy xuất khối đĩa. Dưới đây ta sẽ thảo luận một vài kỹ thuật nhằm vào mục đích đó. - Scheduling: Nếu một vài khối của một trụ cần được truyền từ đĩa vào bộ nhớ chính, ta có thể tiết kiệm thời gian truy xuất bởi yêu cầu các khối theo thứ tự mà nó chạy qua dưới đầu đọc/viết. Nếu các khối mong muốn ở trên các trụ khác nhau, ta yêu cầu các khối theo thứ tự sao cho làm tối thiểu sự di chuyển cánh tay đĩa. Các thuật toán scheduling cánh tay đĩa (Disk-arm-scheduling) nhằm lập thứ tự truy xuất các rãnh theo cách làm tăng số truy xuất có thể được xử lý. Một thuật toán thường dùng là thuật toán thang máy (elevator algorithm): Giả sử ban đầu cánh tay di chuyển từ rãnh trong nhất hướng ra phía ngoài đĩa, đối với mỗi rãnh có yêu cầu truy xuất, nó dừng lại, phục vụ yêu cầu đối với rãnh này, sau đó tiếp tục di chuyển ra phía ngoài đến tận khi không có yêu cầu nào chờ các rãnh xa hơn phía ngoài. Tại điểm này, cánh tay đổi hướng, di chuyển vào phía trong, lại dừng lại trên các rãnh được yêu cầu, và cứ như vậy đến tận khi không còn rãnh nào ở trong hơn được yêu cầu, rồi lại đổi hướng .. v .. v .. Bộ điều khiển đĩa thường làm nhiệm vụ sắp xếp lại các yêu cầu đọc để cải tiến hiệu năng. - Tổ chức file: Để suy giảm thời gian truy xuất khối, ta có thể tổ chức các khối trên đĩa theo cách tương ứng gần nhất với cách mà dữ liệu được truy xuất. Ví dụ, Nếu ta muốn một file được truy xuất tuần tự, khi đó ta bố trí các khối của file một cách tuần tự trên các trụ kề nhau. Tuy nhiên việc phân bố các khối lưu trữ kề nhau này sẽ bị phá vỡ trong quá trình phát triển của file ⇒ file không thể được phân bố trên các khối kề nhau được nữa, hiện tượng này dược gọi là sự phân mảnh (fragmentation). Nhiều hệ điều hành cung cấp tiện ích giúp suy giảm sự phân mảnh này (Defragmentation) nhằm làm tăng hiệu năng truy xuất file. - Các buffers viết không hay thay đổi: Vì nội dung của bộ nhớ chính bị mất khi mất nguồn, các thông tin về cơ sở dữ liệu cập nhật phải được ghi lên đĩa nhằm đề phòng sự cố. Hiệu năng của các ứng dụng cập nhật cường độ cao phụ thuộc mạnh vào tốc độ viết đĩa. Ta có thể sử dụng bộ nhớ truy xuất ngẫu nhiên không hay thay đổi (nonvolatile RAM) để nâng tốc độ viết đĩa. Nội dung của nonvolatile RAM không bị mất khi mất nguồn. Một phương pháp chung để thực hiện nonvolatile RAM là sử dụng RAM pin dự phòng (battery-back-up RAM). Khi cơ sở dữ liệu yêu cầu viết một khối lên đĩa, bộ điều khiển dĩa viết khối này lên buffer nonvolatile RAM, và thông báo ngay cho hệ điều hành là việc viết đã thành công. Bộ điều khiển sẽ viết dữ liệu đến đích của nó trên đĩa, mỗi khi đĩa rảnh hoặc buffer nonvolatile RAM đầy. Khi hệ cơ sở dữ liệu yêu cầu một viết khối, nó chỉ chịu một khoảng lặng chờ đợi khi buffer nonvolatile RAM đầy. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 38
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU - Đĩa log (log disk): Một cách tiếp cận khác để làm suy giảm tiềm năng viết là sử dụng log-disk: Một đĩa được tận hiến cho việc viết một log tuần tự. Tất cả các truy xuất đến log-disk là tuần tự, nhằm loại bỏ thời gian tìm kiếm, và một vài khối kề có thể được viết một lần, tạo cho viết vào log-disk nhanh hơn viết ngẫu nhiên vài lần. Cũng như trong trường hợp sử dụng nonvolatile RAM, dữ liệu phải được viết vào vị trí hiện thời của chúng trên đĩa, nhưng việc viết này có thể được tiến hành mà hệ cơ sở dữ liệu không cần thiết phải chờ nó hoàn tất. Log-disk có thể được sử dụng để khôi phục dữ liệu. Hệ thống file dựa trên log là một phiên bản của cách tiếp cận log-disk: Dữ liệu không được viết lại lên đích gốc của nó trên đĩa; thay vào đó, hệ thống file lưu vết nơi các khối được viết mới đây nhất trên log-disk, và hoàn lại chúng từ vị trí này. Log-disk được "cô đặc" lại (compacting) theo một định kỳ. Cách tiếp cận này cải tiến hiệu năng viết, song sinh ra sự phân mảnh đối với các file được cập nhật thường xuyên. RAID Trong một hệ thống có nhiều đĩa, ta có thể cải tiến tốc độ đọc viết dữ liệu nếu cho chúng hoạt động song song. Mặt khác, hệ thống nhiều đĩa còn giúp tăng độ tin cậy lưu trữ bằng cách lưu trữ dư thừa thông tin trên các đĩa khác nhau, nếu một đĩa có sự cố dữ liệu cũng không bị mất. Một sự đa dạng các kỹ thuật tổ chức đĩa, được gọi là RAID (Redundant Arrays of Inexpensive Disks), được đề nghị nhằm vào vấn đề tăng cường hiệu năng và độ tin cậy. CẢI TIẾN ĐỘ TIN CẬY THÔNG QUA SỰ DƯ THỪA Giải pháp cho vấn đề độ tin cậy là đưa vào sự dư thừa: lưu trữ thông tin phụ, bình thường không cần thiết, nhưng nó có thể được sử dụng để tái tạo thông tin bị mất khi gặp sự cố hỏng hóc đĩa, như vậy thời gian trung bình không sự cố tăng lên (xét tổng thể trên hệ thống đĩa). Đơn giản nhất, là làm bản sao cho mỗi đĩa. Kỹ thuật này được gọi là mirroring hay shadowing. Một đĩa logic khi đó bao gồm hai đĩa vật lý, và mỗi việc viết được thực hiện trên cả hai đĩa. Nếu một đĩa bị hư, dữ liệu có thể được đọc từ đĩa kia. Thời gian trung bình không sự cố của đĩa mirror phụ thuộc vào thời gian trung bình không sự cố của mỗi đĩa và phụ thuộc vào thời gian trung bình được sửa chữa (mean time to repair): thời gian trung bình để một đĩa bị hư được thay thế và phục hồi dữ liệu trên nó. CẢI TIẾN HIỆU NĂNG THÔNG QUA SONG SONG Với đĩa mirror, tốc độ đọc có thể tăng lên gấp đôi vì yêu cầu đọc có thể được gửi đến cả hai đĩa. Với nhiều đĩa, ta có thể cải tiến tốc độ truyền bởi phân nhỏ (striping data) dữ liệu qua nhiều đĩa. Dạng đơn giản nhất là tách các bít của một byte qua nhiều đĩa, sự phân nhỏ này được gọi là sự phân nhỏ mức bit (bit-level striping). Ví dụ, ta có một dàn 8 đĩa, ta viết bít thứ i của một byte lên đĩa thứ i . dàn 8 đĩa này có thể được xử lý như một đĩa với các sector 8 lần lớn hơn kích cỡ thông thường, quan trọng hơn là tốc dộ truy xuất tăng lên tám lần. Trong một tổ chức như vậy, mỗi đĩa tham gia vào mỗi truy xuất (đọc/viết), như vậy, số các truy xuất có thể được xử lý trong một giây là tương tự như trên một đĩa, nhưng mỗi truy xuất có thể đọc/viết nhiều dữ liệu hơn tám lần. Phân nhỏ mức bit có thể được tổng quát cho số đĩa là bội hoặc ước của 8, Ví dụ, ta có một dàn 4 đĩa, ta sẽ phân phối bít thứ i và bít thứ 4+i vào đĩa thứ i. Hơn nữa, sự phân nhỏ không nhất thiết phải ở mức bit của một byte. Ví dụ, trong sự phân nhỏ mức khối, các khối của một file được phân nhỏ qua nhiều đĩa, với n đĩa, khối thứ i có thể được phân phối qua đĩa (i mod n) + 1. Ta cũng CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 39
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU có thể phân nhỏ ở mức byte, sector hoặc các sector của một khối. Hai đích song song trong một hệ thống đĩa là: 1. Nạp nhiều truy xuất nhỏ cân bằng (truy xuất trang) sao cho lượng dữ liệu được nạp trong một đơn vị thời gian của truy xuất như vậy tăng lên. 2. Song song hoá các truy xuất lớn sao cho thời gian trả lời các truy xuất lớn giảm. CÁC MỨC RAID Mirroring cung cấp độ tin cậy cao, nhưng đắt giá. Phân nhỏ cung cấp tốc độ truyền dữ liệu cao, nhưng không cải tiến được độ tin cậy. Nhiều sơ đồ cung cấp sự dư thừa với giá thấp bằng cách phối hợp ý tưởng của phân nhỏ với "parity" bit. Các sơ đồ này có sự thoả hiệp giá-hiệu năng khác nhau và được phân lớp thành các mức được gọi là các mức RAID. • Mức RAID 0 : Liên quan đến các dàn đĩa với sự phân nhỏ mức khối, nhưng không có một sự dư thừa nào. • Mức RAID 1 : Liên quan đến mirror đĩa • Mức RAID 2 : Cũng được biết dưới cái tên mã sửa lỗi kiểu bộ nhớ (memory-style error-correcting-code : ECC). Hệ thống bộ nhớ thực hiện phát hiện lỗi bằng bit parity. Mỗi byte trong hệ thống bộ nhớ có thể có một bit parity kết hợp với nó. Sơ đồ sửa lỗi lưu hai hoặc nhiều hơn các bit phụ, và có thể dựng lại dữ liệu nếu một bit bị lỗi. ý tưởng của mã sửa lỗi có thể được sử dụng trực tiếp trong dàn đĩa thông qua phân nhỏ byte qua các đĩa. Ví dụ, bít đầu tiên của mỗi byte có thể được lưu trên đĩa 1, bit thứ hai trên đĩa 2, và cứ như vậy, bit thứ 8 trên đĩa 8, các bit sửa lỗi được lưu trên các đĩa thêm vào. Nếu một trong các đĩa bị hư, các bít còn lại của byte và các bit sửa lỗi kết hợp được đọc từ các đĩa khác có thể giúp tái tạo bít bị mất trên đĩa hư, như vậy ta có thể dựng lại dữ liệu. Với một dàn 4 đĩa dữ liệu, RAID mức 2 chỉ cần thêm 3 đĩa để lưu các bit sửa lỗi (các đĩa thêm vào này được gọi là các đĩa overhead), so sánh với RAID mức 1, cần 4 đĩa overhead. • Mức RAID 3 : Còn được gọi là tổ chức parity chen bit (bit-interleaved parity). Bộ điều khiển đĩa có thể phát hiện một sector được đọc đúng hay sai, như vậy có thể sử dụng chỉ một bit parity để sửa lỗi: Nếu một trong các sector bị hư, ta biết chính xác đó là sector nào, Với mỗi bit trong sector này ta có thể hình dung nó là bít 1 hay bit 0 bằng cách tính parity của các bit tương ứng từ các sector trên các đĩa khác. Nếu parity của các bit còn lại bằng với parity được lưu, bit mất sẽ là 0, ngoài ra bit mất là 1. RAID mức 3 tốt như mức 2 nhưng it tốn kém hơn (chỉ cần một đĩa overhead). • Mức RAID 4 : Còn được gọi là tổ chức parity chen khối (Block-interleaved parity), lưu trữ các khối đúng như trong các đĩa chính quy, không phân nhỏ chúng qua các đĩa nhưng lấy một khối parity trên một đĩa riêng biệt đối với các khối tương ứng từ N đĩa khác. Nếu một trong các đĩa bị hư, khối parity có thể được dùng với các khối tương ứng từ các đĩa khác để khôi phục khối của đĩa bị hư. Một đọc khối chỉ truy xuất một đĩa, cho phép các yêu cầu khác được xử lý bởi các đĩa khác. Như vậy, tốc độ truyền dữ liệu đối với mỗi truy xuất chậm, nhưng nhiều truy xuất đọc có thể được xử lý song song, dẫn đến một tốc độ I/O tổng thể cao hơn. Tốc độ truyền đối vớí các đọc dữ liệu lớn (nhiều khối) cao do tất cả các đĩa có thể được đọc song song; các viết dữ liệu lớn (nhiều khối) cũng có tốc độ truyền cao vì dữ liệu và parity có thể được viết song song. Tuy nhiên, viết một khối đơn phải truy xuất đĩa trên đó khối được lưu trữ, và đĩa parity (do khối parity cũng phải được cập nhật). Như vậy, viết một khối đơn yêu cầu 4 truy xuất: hai để đọc hai khối cũ, và hai để viết lại hai khối. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 40
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU • Mức RAID 5 : Còn gọi là parity phân bố chen khối (Block-interleaved Distributed Parity), cải tiến của mức 4 bởi phân hoạch dữ liệu và parity giữa toàn bộ N+1 đĩa, thay vì lưu trữ dữ liệu trên N đĩa và parity trên một đĩa riêng biệt như trong RAID 4. Trong RAID 5, tất cả các đĩa có thể tham gia làm thoả mãn các yêu cầu đọc, như vậy sẽ làm tăng tổng số yêu cầu có thể được đặt ra trong một đơn vị thời gian. Đối với mỗi khối, một đĩa lưu trữ parity, các đĩa khác lưu trữ dữ liệu. Ví dụ, với một dàn năm đĩa, parity đối với khối thứ n được lưu trên đĩa (n mod 5)+1. Các khối thứ n của 4 đĩa khác lưu trữ dữ liệu hiện hành của khối đó. • Mức RAID 6 : Còn được gọi là sơ đồ dư thừa P+Q (P+Q redundancy scheme), nó rất giống RAID 5 nhưng lưu trữ thông tin dư thừa phụ để canh chừng nhiều đĩa bị hư. Thay vì sử dụng parity, người ta sử dụng các mã sửa lỗi. CHỌN MỨC RAID ĐÚNG Nếu đĩa bị hư, Thời gian tái tạo dữ liệu của nó là đáng kể và thay đổi theo mức RAID được dùng. Sự tái tạo dễ dàng nhất đối với mức RAID 1. Đối với các mức khác, ta phải truy xuất tất cả các đĩa khác trong dàn đĩa để tái tạo dữ liệu trên đĩa bị hư. Hiệu năng tái tạo của một một hệ thống RAID có thể là một nhân tố quan trọng nếu việc cung cấp dữ liệu liên tục được yêu cầu (thường xảy ra trong các hệ CSDL hiệu năng cao hoặc trao đổi). Hơn nữa, hiệu năng tái tạo ảnh hưởng đến thời gian trung bình không sự cố. Vì RAID mức 2 và 4 được gộp lại bởi RAID mức 3 và 5, Việc lựa chọn mức RAID thu hẹp lại trên các mức RAID còn lại. Mức RAID 0 được dùng trong các ứng dụng hiệu năng cao ở đó việc mất dữ liệu không có gì là trầm trọng cả. RAID mức 1 là thông dụng cho các ứng dụng lưu trữ các log-file trong hệ CSDL. Do mức 1 có overhead cao, mức 3 và 5 thường được ưa thích hơn đối với việc lưu trữ khối lượng dữ liệu lớn. Sự khác nhau giữa mức 3 và mức 5 là tốc độ truyền dữ liệu đối lại với tốc độ I/O tổng thể. Mức 3 được ưa thích hơn nếu truyền dữ liệu cao được yêu cầu, mức 5 được ưa thích hơn nếu việc đọc ngẫu nhiên là quan trọng. Mức 6, tuy hiện nay ít được áp dụng, nhưng nó có độ tin cậy cao hơn mức 5. MỞ RỘNG Các quan niệm của RAID được khái quát hoá cho các thiết bị lưu trữ khác, bao hàm các dàn băng, thậm chí đối với quảng bá dữ liệu trên các hệ thống không dây. Khi áp dụng RAID cho dàn băng, cấu trúc RAID cho khả năng khôi phục dữ liệu cả khi một trong các băng bị hư hại. Khi áp dụng đối với quảng bá dữ liệu, một khối dữ liệu được phân thành các đơn vị nhỏ và được quảng bá cùng với một đơn vị parity; nếu một trong các đơn vị này không nhận được, nó có thể được dựng lại từ các đơn vị còn lại. LƯU TRỮ TAM CẤP (tertiary storage) ĐĨA QUANG HỌC CR-ROM có ưu điểm là có khả năng lưu trữ lớn, dễ di chuyển (có thể đưa vào và lấy ra khỏi ổ đĩa như đĩa mềm), hơn nữa giá lại rẻ. Tuy nhiên, so với ổ đĩa cứng, thời gian tìm kiếm của ổ CD-ROM chậm hơn nhiều (khoảng 250ms), tốc độ quay chậm hơn (khoảng 400rpm), từ đó dẫn đến độ trễ cao hơn; tốc độ truyền dữ liệu cũng chậm hơn (khoảng 150Kbytes/s). Gần đây, một định dạng mới của đĩa quang học - Digital video disk (DVD) - được chuẩn hoá, các đĩa này có dung lượng trong khoảng 4,7GBytes đến 17 GBytes. Các đĩa WORM, REWRITABLE cũng trở thành phổ biến. Các WORM jukeboxes là các thiết bị có thể lưu trữ một số lớn các đĩa WORM và có thể nạp tự động các đĩa theo yêu cầu đến một hoặc một vài ổ WORM. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 41
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU BĂNG TỪ Băng từ có thể lưu một lượng lớn dữ liệu, tuy nhiên, chậm hơn so với đĩa từ và đĩa quang học. Truy xuất băng buộc phải là truy xuất tuần tự, như vậy nó không thích hợp cho hầu hết các đòi hỏi của lưu trữ thứ cấp. Băng từ được sử dụng chính cho việc backup, cho lưu trữ các thông tin không được sử dụng thường xuyên và như một phương tiện ngoại vi (off-line medium) để truyền thông tin từ một hệ thống đến một hệ thống khác. Thời gian để định vị đoạn băng lưu dữ liệu cần thiết có thể kéo dài đến hàng phút. Jukeboxes băng chứa một lượng lớn băng, với một vài ổ băng và có thể lưu trữ được nhiều TeraBytes (1012 Bytes) TRUY XUẤT LƯU TRỮ Một cơ sở dữ liệu được ánh xạ vào một số các file khác nhau được duy trì bởi hệ điều hành nền. Các file này lưu trú thường trực trên các đĩa với backup trên băng. Mỗi file được phân hoạch thành các đơn vị lưu trữ độ dài cố định được gọi là khối - đơn vị cho cả cấp phát lưu trữ và truyền dữ liệu. Một khối có thể chứa một vài hạng mục dữ liệu (data item). Ta giả thiết không một hạng mục dữ liệu nào trải ra trên hai khối. Mục tiêu nổi trội của hệ CSDL là tối thiểu hoá số khối truyền giữa đĩa và bộ nhớ. Một cách để giảm số truy xuất đĩa là giữ nhiều khối như có thể trong bộ nhớ chính. Mục đích là để khi một khối được truy xuất, nó đã nằm sẵn trong bộ nhớ chính và như vậy không cần một truy xuất đĩa nào cả. Do không thể lưu tất cả các khối trong bộ nhớ chính, ta cần quản trị cấp phát không gian sẵn có trong bộ nhớ chính để lưu trữ các khối. Bộ đệm (Buffer) là một phần của bộ nhớ chính sãn có để lưu trữ bản sao khối đĩa. Luôn có một bản sao trên đĩa cho mỗi khối, song các bản sao trên đĩa của các khối là các phiên bản cũ hơn so với phiên bản trong buffer. Hệ thống con đảm trách cấp phát không gian buffer được gọi là bộ quản trị buffer. BỘ QUẢN TRỊ BUFFER Các chương trình trong một hệ CSDL đưa ra các yêu cầu cho bộ quản trị buffer khi chúng cần một khối đĩa. Nếu khối này đã sẵn sàng trong buffer, địa chỉ khối trong bộ nhớ chính được chuyển cho người yêu cầu. Nếu khối chưa có trong buffer, bộ quản trị buffer đầu tiên cấp phát không gian trong buffer cho khối, rút ra một số khối khác, nếu cần thiết, để lấy không gian cho khối mới. Khối được rút ra chỉ được viết lại trên đĩa khi nó có bị sửa đổi kể từ lần được viết lên đĩa gần nhất. Sau đó bộ quản trị buffer đọc khối từ đĩa vào buffer, và chuyển địa chỉ của khối trong bộ nhớ chính cho người yêu cầu. Bộ quản trị buffer không khác gì nhiều so với bộ quản trị bộ nhớ ảo, một điểm khác biệt là kích cỡ của một CSDL có thể rất lớn không đủ chứa toàn bộ trong bộ nhớ chính do vậy bộ quản trị buffer phải sử dụng các kỹ thuật tinh vi hơn các sơ đồ quản trị bộ nhớ ảo kiểu mẫu. • Chiến luợc thay thế. Khi không có chỗ trong buffer, một khối phải được xoá khỏi buffer trước khi một khối mới được đọc vào. Thông thường, hệ điều hành sử dụng sơ đồ LRU (Least Recently Used) để viết lên đĩa khối ít được dùng gần đây nhất, xoá bỏ nó khỏi buffer. Cách tiếp cận này có thể được cải tiến đối với ứng dụng CSDL. • Khối chốt (pinned blocks). Để hệ CSDL có thể khôi phục sau sự cố, cần thiết phải hạn chế thời gian khi viết lại lên đĩa một khối. Một khối không cho phép viết lại lên đĩa được gọi là khối chốt. • Xuất ra bắt buộc các khối (Forced output of blocks). Có những tình huống trong đó cần phải viết lại một khối lên đĩa, cho dù không gian buffer mà nó chiếm là không cần đến. Việc CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 42
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU viết này được gọi là sự xuất ra bắt buộc của một khối. Lý do ngắn gọn của yêu cầu xuất ra bắt buộc khối là nội dung của bộ nhớ chính bị mất khi có sự cố, ngược lại dữ liệu trên dĩa còn tồn tại sau sự cố. CÁC ĐỐI SÁCH THAY THẾ BUFFER (Buffer-Replacement Policies). Mục đích của chiến lược thay thế khối trong buffer là tối thiểu hoá các truy xuất đĩa. Các hệ điều hành thường sử dụng chiến lược LRU để thay thế khối. Tuy nhiên, một hệ CSDL có thể dự đoán mẫu tham khảo tương lai. Yêu cầu của một người sử dụng đối với hệ CSDL bao gồm một số bước. Hệ CSDL có thể xác định trước những khối nào sẽ là cần thiết bằng cách xem xét mỗi một trong các bước được yêu cầu để thực hiện hoạt động được yêu cầu bởi người sử dụng. Như vậy, khác với hệ điều hành, hệ CSDL có thể có thông tin liên quan đến tương lai, chí ít là tương lai gần. Trong nhiều trường hợp, chiến lược thay thế khối tối ưu cho hệ CSDL lại là MRU (Most Recently Used): Khối bị thay thế sẽ là khối mới được dùng gần đây nhất! Bộ quản trị buffer có thể sử dụng thông tin thống kê liên quan đến xác suất mà một yêu cầu sẽ tham khảo một quan hệ riêng biệt nào đó. Tự điển dữ liệu là một trong những phần được truy xuất thường xuyên nhất của CSDL. Như vậy, bộ quản trị buffer sẽ không nên xoá các khối tự điển dữ liệu khỏi bộ nhớ chính trừ phi các nhân tố khác bức chế làm điều đó. Một chỉ mục (Index) đối với một file được truy xuất thường xuyên hơn chính bản thân file, vậy thì bộ quản trị buffer cũng không nên xoá khối chỉ mục khỏi bộ nhớ chính nếu có sự lựa chọn. Chiến luợc thay thế khối CSDL lý tưởng cần hiểu biết về các hoạt động CSDL đang được thực hiện. Không một chiến lược đơn lẻ nào được biết nắm bắt được toàn bộ các viễn cảnh có thể. Tuy vậy, một điều đáng ngạc nhiên là phần lớn các hệ CSDL sử dụng LRU bất chấp các khuyết điểm của chiến lược đó. Chiến lược được sử dụng bởi bộ quản trị buffer để thay thế khối bị ảnh hưởng bởi các nhân tố khác hơn là nhân tố thời gian tại đó khối được tham khảo trở lại. Nếu hệ thống đang xử lý các yêu cầu của một vài người sử dụng cạnh tranh, hệ thống (con) điều khiển cạnh tranh (concurrency-control subsystem) có thể phải làm trễ một số yêu cầu để đảm bảo tính nhất quán của CSDL. Nếu bộ quản trị buffer được cho các thông tin từ hệ thống điều khiển cạnh tranh mà nó nêu rõ những yêu cầu nào đang bị làm trễ, nó có thể sử dụng các thông tin này để thay đổi chiến lược thay thế khối của nó. Đặc biệt, các khối cần thiết bởi các yêu cầu tích cực (active requests) có thể được giữ lại trong buffer, toàn bộ các bất lợi đổ dồn lên các khối cần thiết bởi các yêu cầu bị làm trễ. Hệ thống (con) khôi phục (crash-recovery subsystem) áp đặt các ràng buộc nghiêm nhặt lên việc thay thế khối. Nếu một khối bị sửa đổi, bộ quản trị buffer không được phép viết lại phiên bản mới của khối trong buffer lên đĩa, vì điều này phá huỷ phiên bản cũ. Thay vào đó, bộ quản trị khối phải tìm kiếm quyền từ hệ thống khôi phục trước khi viết khối. Hệ thống khôi phục có thể đòi hỏi một số khối nhất định khác là xuất bắt buộc (forced output) trước khi cấp quyền cho bộ quản trị buffer để xuất ra khối được yêu cầu. TỔ CHỨC FILE Một file được tổ chức logic như một dãy các mẩu tin (record). Các mẩu tin này được ánh xạ lên các khối đĩa. File được cung cấp như một xây dựng cơ sở trong hệ điều hành, như vậy ta sẽ giả thiết sự tồn tại của hệ thống file nền. Ta cần phải xét những phương pháp biểu diễn các mô hình dữ liệu logic trong thuật ngữ file. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 43
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Các khối có kích cỡ cố định được xác định bởi tính chất vật lý của đĩa và bởi hệ điều hành, song kích cỡ của mẩu tin lại thay đổi. Trong CSDL quan hệ, các bộ của các quan hệ khác nhau nói chung có kích cỡ khác nhau. Một tiếp cận để ánh xạ một CSDL đến các file là sử dụng một số file, và lưu trữ các mẩu tin thuộc chỉ một độ dài cố định vào một file đã cho nào đó. Một cách khác là cấu trúc các file sao cho ta có thể điều tiết nhiều độ dài cho các mẩu tin. Các file của các mẩu tin độ dài cố định dễ dàng thực thi hơn file của các mẩu tin độ dài thay đổi. MẨU TIN ĐỘ DÀI CỐ ĐỊNH (Fixed-Length Records) Xét một file các mẩu tin account đối với CSDL ngân hàng, mỗi mẩu tin của file này được xác định như sau: type depositor = record branch_name: char(20); account_number: char(10); balance:real; end Giả sử mỗi một ký tự chiếm 1 byte và mỗi số thực chiếm 8 byte, như vậy mẩu tin account có độ dài 40 bytes. Một cách tiếp cận đơn giản là sử dụng 40 byte đầu tiên cho mẩu tin thứ nhất, 40 byte kế tiếp cho mẩu tin thứ hai, ... Cách tiếp cận đơn giản này nảy sinh những vấn đề sau; 0 Perryridge A-102 400 0 Perryridge A-102 400 1 Round Hill A-305 350 1 Round Hill A-305 350 2 Mianus A-215 700 3 Downtown A-101 500 3 Downtown A-101 500 4 Redwood A-222 700 4 Redwood A-222 700 5 Perryridge A-201 900 5 Perryridge A-201 900 6 Brighton A-217 750 6 Brighton A-217 750 7 Downtown A-110 600 7 Downtown A-110 600 8 Perryridge A-218 700 8 Perryridge A-218 700 2. File F sau khi xóa mẩu tin 2 và di chuyển các mảu tin sau nó 1. File F chứa các mẩu tin account header 0 Perryridge A-102 400 0 Perryridge A-102 400 1 Round Hill A-305 350 1 8 Perryridge A-218 700 2 Mianus A-215 700 3 Downtown A-101 500 3 Downtown A-101 500 4 Redwood A-222 700 4 5 Perryridge A-201 900 CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN 5 Perryridge A-201 900 trang 44 6 Brighton A-217 750 6 7 Downtown A-110 600 7 Downtown A-110 600 3. File F sau khi xóa mẩu tin 2 và di 8 Perryridge A-218 700 chuyển mẩu tin cuói vào vị chí của
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU 1. Khó khăn khi xoá một mẩu tin từ cấu trúc này. Không gian bị chiếm bởi mẩu tin bị xoá phải được lấp đầy với mẩu tin khác của file hoặc ta phải đánh dấu mẩu tin bị xoá. 2. Trừ khi kích cỡ khối là bội của 40, nếu không một số mẩu tin sẽ bắt chéo qua biên khối, có nghĩa là một phần mẩu tin được lưu trong một khối, một phần khác được lưu trong một khối khác. như vậy đòi hỏi phải truy xuất hai khối để đọc/viết một mẩu tin "bắc cầu" đó. Khi một mẩu tin bị xoá, ta có thể di chuyển mẩu tin kề sau nó vào không gian bị chiếm một cách hình thức bởi mẩu tin bị xoá, rồi mẩu tin kế tiếp vào không gian bị chiếm của mẩu tin vừa được di chuyển, cứ như vậy cho đến khi mỗi mẩu tin đi sau mẩu tin bị xoá được dịch chuyển hướng về đầu. Cách tiếp cận này đòi hỏi phải di chuyển một số lớn các mẩu tin. Một cách tiếp cận khác đơn giản hơn là di chuyển mẩu tin cuối cùng vào không gian bị chiếm bởi mẩu tin bị xoá. Song cách tiếp cận này đòi hỏi phải truy xuất khối bổ xung. Vì hoạt động xen xảy ra thường xuyên hơn hoạt động xoá, ta có thể chấp nhận việc để "ngỏ" không gian bị chiếm bởi mẩu tin bị xoá, và chờ một hoạt động xen đến sau để tái sử dụng không gian đó. Một dấu trên mẩu tin bị xoá là không đủ vì sẽ gây khó khăn cho việc tìm kiếm không gian "tự do" đó khi xen. Như vậy ta cần đưa vào cấu trúc bổ xung. ở đầu của file, ta cấp phát một số byte nhất định làm header của file. Header này sẽ chứa đựng thông tin về file. Header chứa địa chỉ của mẩu tin bị xoá thứ nhất, trong nội dung của mẩu tin này có chứa địa chỉ của mẩu tin bị xoá thứ hai và cứ như vậy. Như vậy, các mẩu tin bị xoá sẽ tạo ra một danh sách liên kết dược gọi là danh sách tự do (free list). Khi xen mẩu tin mới, ta sử dụng con trỏ đầu danh sách được chứa trong header để xác định danh sách, nếu danh sách không rỗng ta xen mẩu tin mới vào vùng được trỏ bởi con trỏ đầu danh sách nếu không ta xen mẩu tin mới vào cuối file. Xen và xoá đối với file mẩu tin độ dài cố định thực hiện đơn giản vì không gian được giải phóng bởi mẩu tin bị xoá đúng bằng không gian cần thiết để xen một mẩu tin. Đối với file của các mẩu tin độ dài thay đổi vấn đề trở nên phức tạp hơn nhiều. MẨU TIN ĐỘ DÀI THAY ĐỔI (Variable-Length Records) Mẩu tin độ dài thay đổi trong CSDL do bởi: o Việc lưu trữ nhiều kiểu mẩu tin trong một file o Kiểu mẩu tin cho phép độ dài trường thay đổi o Kiểu mẩu tin cho phép lặp lại các trường CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 45
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Có nhiều kỹ thuật để thực hiện mẩu tin độ dài thay đổi. Để minh hoạ ta sẽ xét các biểu diễn khác nhau trên các mẩu tin độ dài thay đổi có định dạng sau: Type account_list = record branch_name: char(20) ; account_info: array[ 1.. ∞ ] of record account_number: char(10); balance: real; end; end Biểu diễn chuỗi byte (Byte-String Representation) Một cách đơn giản để thực hiện các mẩu tin độ dài thay đổi là gắn một ký hiệu đặc biệt End-of-record (⊥) vào cuối mỗi record. Khi đó, ta có thể lưu mỗi mẩu tin như một chuỗi byte liên tiếp. Thay vì sử dụng một ký hiệu đặc biệt ở cuối của mỗi mẩu tin, một phiên bản của biểu diễn chuỗi byte lưu trữ độ dài mẩu tin ở bắt đầu của mỗi mẩu tin. 0 Perryridge A-102 400 A-201 900 A210 700 ⊥ 1 Round Hill A-301 350 ⊥ 2 Mianus A-101 800 ⊥ 3 Downtown A-211 500 A-222 600 ⊥ 4 Redwood A-300 650 A-200 1200 A-255 950 ⊥ 5 Brighton A-111 750 ⊥ Biểu diễn chuỗi byte của các mẩu tin độ dài thay đổi Biểu diễn chuỗi byte có các bất lợi sau: - Khó sử dụng không gian bị chiếm hình thức bởi một mẩu tin bị xoá, điều này dẫn đến một số lớn các mảnh nhỏ của lưu trữ đĩa bị lãng phí. - Không có không gian cho sự phát triển các mẩu tin. Nếu một mẩu tin độ dài thay đổi dài ra, nó phải được di chuyển và sự di chuyển này là đắt giá nếu mẩu tin bị chốt. Biểu diễn chuỗi byte không thường được sử dụng để thực hiện mẩu tin độ dài thay đổi, song một dạng sửa đổi của nó được gọi là cấu trúc khe-trang (slotted-page structure) thường được dùng để tổ chức mẩu tin trong một khối đơn. Trong cấu trúc slotted-page, có một header ở bắt đầu của mỗi khối, chứa các thông tin sau: - Số các đầu vào mẩu tin (record entries) trong header - Điểm cuối không gian tự do (End of Free Space) trong khối - Một mảng các đầu vào chứa vị trí và kích cỡ của mỗi mẩu tin Các mẩu tin hiện hành được cấp phát kề nhau trong khối, bắt đàu từ cuối khối, Không gian tự do trong khối là một vùng kề nhau, nằm giữa đầu vào cuối cùng trong mảng header và mẩu tin đàu tiên. Khi một mẩu tin được xen vào, không gian cấp phát cho nó ở cuối của không gian tự do, và đầu vào tương ứng với nó được thêm vào header. Block header Size #entries Free Space location CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 46 End of Free Space
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Nếu một mẩu tin bị xoá, không gian bị chiếm bởi nó được giải phóng, đầu vào ứng với nó được đặt là bị xoá (kích cỡ của nó được đặt chẳng hạn là -1). Sau đó, các mẩu tin trong khối trước mẩu tin bị xoá được di chuyển sao cho không gian tự do của khối lại là phần nằm giữa đầu vào cuối cùng của mảng header và mẩu tin đầu tiên. Con trỏ điểm cuối không gian tự do và các con trỏ ứng với mẩu tin bị di chuyển được cập nhật. Sự lớn lên hay nhỏ đi của mẩu tin cũng sử dụng kỹ thuật tương tự (trong trường hợp khối còn không gian cho sự lớn lên của mẩu tin). Cái giá phải trả cho sự di chuyển không quá cao vì các khối có kích cỡ không lớn ( thường 4Kbytes). Biểu diễn độ dài cố định Một cách khác để thực hiện mẩu tin độ dài thay đổi một cách hiệu quả trong một hệ thống file là sử dụng một hoặc một vài mẩu tin độ dài cố định để biểu diễn một mẩu tin độ dài thay đổi. Hai kỹ thuật thực hiện file của các mẩu tin độ dài thay đổi sử dụng mẩu tin độ dài cố định là: 1. Không gian dự trữ (reserved space). Giả thiết rằng các mẩu tin có độ dài không vượt quá một ngưỡng (độ dài tối đa). Ta có thể sử dụng mảu tin độ dài cố định (có độ dài tối đa), Phần không gian chưa dùng đến được lấp đầy bởi một ký tự đặc biệt: null hoặc End-of-record. 2. Contrỏ (Pointers). Mẩu tin độ dài thay đổi được biểu diễn bởi một danh sách các mẩu tin độ dài cố định, được "móc xích" với nhau bởi các con trỏ. Sự bất lợi của cấu trúc con trỏ là lãng phí không gian trong tất cả các mẩu tin ngoại trừ mẩu tin đầu tiên trong danh sách (mẩu tin đầu tiên cần trường branch_name, các mẩu tin sau trong danh sách không cần thiết có trường này!). Để giải quyết vấn đề này người ta đề nghị phân các khối trong file thành hai loại: • Khối neo (Anchor block). chứa chỉ các mẩu tin đầu tiên trong danh sách • Khối tràn (Overflow block). chứa các mẩu tin còn lại của danh sách Như vậy, tất cả các mẩu tin trong một khối có cùng độ dài, cho dù file có thể chứa các mẩu tin không cùng độ dài. 0 Perryridge A-102 400 A-201 900 A210 700 ⊥ 1 Round Hill A-301 350 ⊥ ⊥ ⊥ ⊥ ⊥ 2 Mianus A-101 800 ⊥ ⊥ ⊥ ⊥ ⊥ 3 Downtown A-211 500 A-222 600 ⊥ ⊥ ⊥ 4 Redwood A-300 650 A-200 1200 A-255 950 ⊥ 5 Brighton A-111 750 ⊥ ⊥ ⊥ ⊥ ⊥ Sử dụng phương pháp không gian dự trữ 0 Perryridge A-102 400 1 A-201 900 2 A-210 700 • CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 47 3 Round Hill A-301 350 • 4 Mianus A-101 800 • 5 Downtown A-211 500 6 Redwood A-300 650
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Perryridge A-102 400 Round Hill A-301 350 • Mianus A-101 800 • Downtown A-211 500 Redwood A-300 650 • Brighton A-111 750 • Khối neo A-201 900 A-210 700 • A-222 600 • A-200 1200 A-255 950 • Khối tràn Cấu trúc khối neo và khối tràn TỔ CHỨC CÁC MẨU TIN TRONG FILE Ta đã xét làm thế nào để biểu diễn các mẩu tin trong một cấu trúc file. Một thể hiện của một quan hệ là một tập hợp các mẩu tin. Đã cho một tập hợp các mẩu tin, vấn đề đặt ra là làm thế nào để tổ chức chúng trong một file. Có một số cách tổ chức sau: • Tổ chức file đống (Heap File Organization). Trong tổ chức này, một mẩu tin bất kỳ có thể được lưu trữ ở bất kỳ nơi nào trong file, ở đó có không gian cho nó. Không có thứ tự nào giữa các mẩu tin. Một file cho một quan hệ. • Tổ chức file tuần tự ( Sequential File Organization). Trong tổ chức này, các mẩu tin được lưu trữ thứ tự tuần tự, dựa trên giá trị của khoá tìm kiếm của mỗi mẩu tin. • Tổ chức file băm (Hashed File Organization). Trong tổ chức này, có một hàm băm được tính toán trên thuộc tính nào đó của mẩu tin. Kết quả của hàm băm xác định mẩu tin được bố trí trong khối nào trong file. Tổ chức này liên hệ chặt chẽ với cấu trúc chỉ mục. CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 48
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU • Tổ chức file cụm (Clustering File Organization). Trong tổ chức này, các mẩu tin của một vài quan hệ khác nhau có thể được lưu trữ trong cùng một file. Các mẩu tin có liên hệ của các quan hệ khác nhau được lưu trữ trên cùng một khối sao cho một hoạt động I/O đem lại các mẩu tin có liên hệ từ tất cả các quan hệ. TỔ CHỨC FILE TUẦN TỰ Tổ chức file tuần tự được thiết kế để xử lý hiệu quả các mẩu tin trong thứ tự được sắp dựa trên một khoá tìm kiếm (search key) nào đó. Để cho phép tìm lại nhanh chóng các mẩu tin theo thứ tự khoá tìm kiếm, ta "xích" các mẩu tin lại bởi các con trỏ. Con trỏ trong mỗi mẩu tin trỏ tới mẩu tin kế theo thứ tự khoá tìm kiếm. Hơn nữa, để tối ưu hoá số khối truy xuất trong xử lý file tuần tự, ta lưu trữ vật lý các mẩu tin theo thứ tự khoá tìm kiếm hoặc gần với khoá tìm kiếm như có thể. Tổ chức file tuần tự cho phép đọc các mẩu tin theo thứ tự được sắp mà nó có thể hưu dụng cho mục đích trình bày cũng như cho các thuật toán xử lý vấn tin (query-processing algorithms). Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 850 Round Hill A-301 550 • Khó khăn gặp phải của tổ chức này là việc duy trì thứ tự tuần tự vật lý của các mẩu tin khi xẩy ra các hoạt động xen, xoá, do cái giá phải trả cho việc di chuyển các mẩu tin khi xen, xoá. Ta có thể quản trị vấn đề xoá bởi dùng dây chuyền các con trỏ như đã trình bày trước đây. Đối với xen, ta có thể áp dụng các quy tắc sau: 1. Định vị mẩu tin trong file mà nó đi trước mẩu tin được xen theo thứ tự khoá tìm kiếm. 2. Nếu có mẩu tin tự do (không gian của mẩu tin bị xoá) trong cùng khối, xen mẩu tin vào khối này. Nếu không, xen mẩu tin mới vào một khối tràn. Trong cả hai trường hợp, điều chỉnh các con trỏ sao cho nó móc xích các mẩu tin theo thứ tự của khoá tìm kiếm. Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 850 CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 49 Round Hill A-301 550 • Khối tràn North Town A_777 1100
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU TỔ CHỨC FILE CỤM Nhiều hệ CSDL quan hệ, mỗi quan hệ được lưu trữ trong một file sao cho có thể lợi dụng được toàn bộ những cái mà hệ thống file của điều hành cung cấp. Thông thường, các bộ của một quan hệ được biểu diễn như các mẩu tin độ dài cố định. Như vậy các quan hệ có thể ánh xạ vào một cấu trúc file. Sự thực hiện đơn giản đó của một hệ CSDL quan hệ rất phù hợp với các hệ CSDL được thiết kế cho các máy tính cá nhân. Trong các hệ thống đó, kích cỡ của CSDL nhỏ. Hơn nữa, trong một số máy tính cá nhân, chủ yếu kích cỡ tổng thể mã đối tượng đối với hệ CSDL là nhỏ. Một cấu trúc file đơn giản làm suy giảm lượng mã cần thiết để thực thi hệ thống. Cách tiếp cận đơn giản này, để thực hiện CSDL quan hệ, không còn phù hợp khi kích cỡ của CSDL tăng lên. Ta sẽ thấy những điểm lợi về mặt hiệu năng từ việc gán một cách thận trọng các mẩu tin với các khối, và từ việc tổ chức kỹ lưỡng chính bản thân các khối. Như vậy, có vẻ như là một cấu trúc file phức tạp hơn lại có lợi hơn, ngay cả trong trường hợp ta giữ nguyên chiến lược lưu trữ mỗi quan hệ trong một file riêng biệt. Tuy nhiên, nhiều hệ CSDL quy mô lớn không nhờ cậy trực tiếp vào hệ điều hành nền để quản trị file. Thay vào đó, một file hệ điều hành được cấp phát cho hệ CSDL. Tất cả các quan hệ được lưu trữ trong một file này, và sự quản trị file này thuộc về hệ CSDL. Để thấy những điểm lợi của việc lưu trữ nhiều quan hệ trong cùng một file, ta xét vấn tin SQL sau: SELECT account_number, customer_number, customer_treet, customer_city FROM depositor, customer WHERE depositor.customer_name = customer.customername; Câu vấn tin này tính một phép nối của các quan hệ depositor và customer. Như vậy, đối với mỗi bộ của depositor, hệ thống phải tìm bộ của customer có cùng giá trị customer_name. Một cách lý tưởng là việc tìm kiếm các mẩu tin này nhờ sự trợ giúp của chỉ mục. Bỏ qua việc tìm kiếm các mẩu tin như thế nào, ta chú ý vào việc truyền từ đĩa vào bộ nhớ. Trong trường hợp xấu nhất, mỗi mẩu tin ở trong một khối khác nhau, điều này buộc ta phải đọc một khối cho một mẩu tin được yêu cầu bởi câu vấn tin. Ta sẽ trình bày một cấu trúc file được thiết kế để thực hiện hiệu quả các câu vấn tin liên quan đến depositor customer. Các bộ depositor đối với mỗi customer_name được lưu trữ gần bộ customer có cùng customer_name. Cấu trúc này trộn các bộ của hai quan hệ với nhau, nhưng cho phép xử lý hiệu quả phép nối. Khi một bộ của của quan hệ customer được đọc, toàn bộ khối chứa bộ này được đọc từ đĩa vào trong bộ nhớ chính. Do các bộ tương ứng của depositor được lưu trữ trên đĩa gần bộ customer, khối chứa bộ customer chứa các bộ của quan hệ depositor cần cho xử lý câu vấn tin. Nếu một customer có nhiều account đến nỗi các mẩu tin depositor không lấp đầy trong một khối, các mẩu tin còn lại xuất hiện trong khối kế cận. Cấu trúc file này, được gọi là gom cụm (clustering), cho phép ta đọc nhiều mẩu tin được yêu cầu chỉ sử dụng một đọc khối, như vậy ta có thể xử lý câu vấn tin đặc biệt này hiệu quả hơn. customer_name customer_street customer_city Hays Main Brooklyn Hays Main Brooklyn Hays A-102 Turner Putnam Stamford Hays A-220 CHƯƠNG customer TRỮ VÀ CẤU TRÚC TẬP TIN Quan hệ III. LƯU Hays A-503 trang 50 Hays Main Brooklyn Turner Putnam Stamford Hays A-102 Turner A-305 Hays A-220 Cấu trúc file cụm
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU Tuy nhiên, cấu trúc gom cụm trên lại tỏ ra không có lợi bằng tổ chức lưu mỗi quan hệ trong một file riêng, đối với một số câu vấn tin, chẳng hạn: SELECT * FROM customer Việc xác định khi nào thì gom cụm thường phụ thuộc vào kiểu câu vấn tin mà người thiết kế CSDL nghĩ rằng nó xẩy ra thường xuyên nhất. Sử dụng thận trọng gom cụm có thể cải thiện hiệu năng đáng kể trong việc xử lý câu vấn tin. LƯU TRỮ TỰ ĐIỂN DỮ LIỆU Một hệ CSDL cần thiết duy trì dữ liệu về các quan hệ, như sơ đồ của các quan hệ. Thông tin này được gọi là tự điển dữ liệu (data dictionary) hay mục lục hệ thống (system catalog). Trong các kiểu thông tin mà hệ thống phải lưu trữ là: ○ Các tên của các quan hệ ○ Các tên của các thuộc tính của mỗi quan hệ ○ Các miền (giá trị) và các độ dài của các thuộc tính ○ Các tên của các View được định nghĩa trên CSDL và định nghĩa của các view này ○ Các ràng buộc toàn vẹn Nhiều hệ thống còn lưu trữ các thông tin liên quan đến người sử dụng hệ thống: ○ Tên của người sử dụng được phép ○ Giải trình thông tin về người sử dụng Các dữ liệu thống kê và mô tả về các quan hệ có thể cũng được lưu trữ: ○ Số bộ trong mỗi quan hệ ○ Phương pháp lưu trữ được sử dụng cho mỗi quan hệ (cụm hay không) Các thông tin về mỗi chỉ mục trên mỗi quan hệ cũng cần được lưu trữ : ○ Tên của chỉ mục ○ Tên của quan hệ được chỉ mục ○ Các thuộc tính trên nó chỉ mục được định nghĩa CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 51
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU ○ Kiểu của chỉ mục được tạo Toàn bộ các thông tin này trong thực tế bao hàm một CSDL nhỏ. Một số hệ CSDL sử dụng những cấu trúc dữ liệu và mã mục đích đặc biệt để lưu trữ các thông tin này. Nói chung, lưu trữ dữ liệu về CSDL trong chính CSDL vẫn được ưa chuộng hơn. Bằng cách sử dụng CSDL để lưu trữ dữ liệu hệ thống, ta đơn giản hoá cấu trúc tổng thể của hệ thống và cho phép sử dụng đầy đủ sức mạnh của CSDL trong việc truy xuất nhanh đến dữ liệu hệ thống. Sự chọn lựa chính xác biểu diễn dữ liệu hệ thống sử dụng các quan hệ như thế nào là do người thiết kế hệ thống quyết định. Như một ví dụ, ta đề nghị sự biểu diễn sau: System_catalog_schema = (relation_name, number_of_attributes) Attribute_schema = (attribute_name, relation_name, domain_type, position, length) User_schema = (user_name, encrypted_password, group) Index_schema = (index_name, relation_name, index_type, index_attributes) View_schema = (view_name, definition) CHỈ MỤC Ta xét hoạt động tìm sách trong một thư viện. Ví dụ ta muốn tìm một cuốn sách của một tác giả nào đó. Đầu tiên ta tra trong mục lục tác giả, một tấm thẻ trong mục lục này sẽ chỉ cho ta biết có thể tìm thấy cuốn sách đó ở đâu. Các thẻ trong một mục lục được thư viện sắp xếp thứ tự theo vần chữ cái , như vậy giúp ta có thể tìm đến thẻ cần tìm nhanh chóng không cần phải duyệt qua tất cả các thẻ. Chỉ mục của một file trong các công việc hệ thống rất giống với một mục lục trong một thư viện. Tuy nhiên, chỉ mục được làm như mục lục được mô tả như trên, trong thực tế, sẽ quá lớn để được quản lý một cách hiệu quả. Thay vào đó, người ta sử dụng các kỹ thuật chỉ mục tinh tế hơn. Có hai kiểu chỉ mục: • Chỉ mục được sắp (Ordered indices). được dựa trên một thứ tự sắp xếp theo các giá trị • Chỉ mục băm (Hash indices). được dựa trên các giá trị được phân phối đều qua các bucket. Bucket mà một giá trị được gán với nó được xác định bởi một hàm, được gọi là hàm băm (hash function) Đối với cả hai kiểu này, ta sẽ nêu ra một vài kỹ thuật, đáng lưu ý là không kỹ thuật nào là tốt nhất. Mỗi kỹ thuật phù hợp với các ứng dụng CSDL riêng biệt. Mỗi kỹ thuật phải được đánh giá trên cơ sở của các nhân tố sau: • Kiểu truy xuất: Các kiểu truy xuất được hỗ trợ hiệu quả. Các kiểu này bao hàm cả tìm kiếm mẩu tin với một giá trị thuộc tính cụ thể hoặc tìm các mẩu tin với giá trị thuộc tính nằm trong một khoảng xác định. • Thời gian truy xuất: Thời gian để tìm kiếm một hạng mục dữ liệu hay một tập các hạng mục. • Thời gian xen: Thời gian để xen một hạng mục dữ liệu mới. giá trị này bao hàm thời gian để tìm vị trí xen thích hợp và thời gian cập nhật cấu trúc chỉ mục. • Thời gian xoá: Thời gian để xoá một hạng mục dữ liệu. giá trị này bao hàm thời gian tìm kiếm hạng mục cần xoá, thời gian cập nhật cấu trúc chỉ mục. • Tổng phí tổn không gian: Không gian phụ bị chiếm bởi một cấu trúc chỉ mục. Một file thường đi kèm với một vài chỉ mục. Thuộc tính hoặc tập hợp các thuộc tính được dùng để tìm kiếm mẩu tin trong một file được gọi là khoá tìm kiếm. Chú ý rằng định nghĩa này CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN trang 52
- HỆ QUẢN TRỊ CƠ SỞ DỮ LIỆU khác với định nghĩa khoá sơ cấp (primary key), khoá dự tuyển (candidate key), và siêu khoá (superkey). Như vậy, nếu có một vài chỉ mục trên một file, có một vài khoá tìm kiếm tương ứng. CHỈ MỤC ĐƯỢC SẮP. Một chỉ mục lưu trữ các giá trị khoá tìm kiếm trong thứ tự được sắp, và kết hợp với mỗi khoá tìm kiếm, các mẩu tin chứa khoá tìm kiếm này. Các mẩu tin trong file được chỉ mục có thể chính nó cũng được sắp. Một file có thể có một vài chỉ mục trên những khoá tìm kiếm khác nhau. Nếu file chứa các mẩu tin được sắp tuần tự, chỉ mục trên khoá tìm kiếm xác định thứ tự này của file được gọi chỉ mục sơ cấp (primary index). Các chỉ mục sơ cấp cũng được gọi là chỉ mục cụm (clustering index). Khoá tìm kiếm của chỉ mục sơ cấp thường là khoá sơ cấp (khoá chính). Các chỉ mục, khoá tìm kiếm của nó xác định một thứ tự khác với thứ tự của file, được gọi là các chỉ mục thứ cấp (secondary indices) hay các chỉ mục không cụm (nonclustering indices). Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 850 Round Hill A-301 550 • Chỉ mục sơ cấp. file tuần tự các mẩu tin account Trong phần này, ta giả thiết rằng tất cả các file được sắp thứ tự tuần tự trên một khoá tìm kiếm nào đó. Các file như vậy, với một chỉ mục sơ cấp trên khoá tìm kiếm này, được gọi là file tuần tự chỉ mục (index-sequential files). Chúng biểu diễn một trong các sơ đồ xưa nhất được dùng trong hệ CSDL. Chúng được thiết kế cho các ứng dụng đòi hỏi cả xử lý tuần tự toàn bộ file lẫn truy xuất ngẫu nhiên đến một mẩu tin. Chỉ mục đặc và chỉ mục thưa (Dense and Sparse Indices) Chỉ mục đặc Brighton Brighton A-217 750 Mianus Downtown A-101 500 Redwood Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 850 Round Hill A-301 550 • Chỉ mục thưa Brighton A-217 750 Brighton Downtown A-101 500 CHƯƠNG III. LƯU TRỮ VÀ CẤU TRÚC TẬP TIN Downtown Downtown A-110 600 trang 53 Mianus Mianus A-215 700 Perryridge Perryridge A-102 400 Redwood Perryridge A-201 900
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Hệ quản trị cơ sở dữ liệu - Chương 1 - Giới thiệu
18 p |
1417 |
530
-
Hệ quản trị cơ sở dữ liệu - Chương 6 - Hệ thống phục hồi
16 p |
455 |
297
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 6 - ThS. Nguyễn Minh Vi
28 p |
65 |
11
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 4 - Phạm Thị Bạch Huệ
26 p |
41 |
11
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 - ThS. Nguyễn Minh Vi
55 p |
41 |
9
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 5 - Phạm Thị Bạch Huệ
13 p |
38 |
9
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 9 - ThS. Nguyễn Minh Vi
97 p |
41 |
8
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 7 - ThS. Nguyễn Minh Vi
50 p |
37 |
8
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 (Phần 2) - Phạm Thị Bạch Huệ
36 p |
16 |
5
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 - Phạm Thị Bạch Huệ
17 p |
28 |
4
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 4 - Nguyễn Nhật Minh
53 p |
11 |
2
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 - Nguyễn Nhật Minh
22 p |
20 |
2
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 2 - ĐH Công nghiệp Thực phẩm
142 p |
12 |
2
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 - ĐH Công nghiệp Thực phẩm
218 p |
7 |
2
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 4 - ĐH Công nghiệp Thực phẩm
92 p |
10 |
2
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 - Huỳnh Học
21 p |
1 |
0
-
Bài giảng Hệ quản trị cơ sở dữ liệu: Chương 3 (tt) - Huỳnh Học
43 p |
0 |
0

Set-Cookie: TLDEVNamespace=dstoj74o1fpfhukrj6j1va0g06; path=/; domain=.tailieu.vn; HttpOnly


markdown:
# Character data types
**Character data types**
-
Oracle allows you to define your own object data types, which you can use for creating objects, discussed in detail in Chapter 21, “Object Relational Interactions with Oracle.” Oracle also includes specialized data types for working with XML, spatial data, and media data, as well as ways to access type descriptions when the data type is not known.
793p
nghianguyenluong
30-06-2009
282
167
Download
-
The collection of built-in data types in a data base system (e.g. integer, floating point number, character string) and built-in operators (e.g. +, -, *, /) were motivated by the needs of business data processing applications. However, in many engineering applications this collection of types is not appropriate. For example, in a geographic application a user typically wants points, lines, line groups and polygons as basic data types and operators which include intersection, distance and containment.
19p
hgiang
11-03-2009
82
3
Download
-
LESSON 1 program development styles and basics of c Program Development Methodologies - Programming Style - Stepwise Refinement and Modularity - Problem Solving Techniques - Algorithm – Flowcharts – Pseudocode – Sequence and Selection - Recursion vs. Iteration - Overview of Compilers and Interpreters - Structure of a C Program - Programming Rules - Executing the Program. 1 LESSON 2 CONSTANTS & VARIABLES Introduction - Character set - C Tokens - Keywords and Identifiers – Constants – Variables.
118p
rose_12
06-12-2012
27
2
Download
-
[Báo cáo khoa học: "Rethinking Chinese Word Segmentation: Tokenization, Character Classiﬁcation, or Wordbreak Identiﬁcation"](http://tailieu.vn/doc/bao-cao-khoa-hoc-rethinking-chinese-word-segmentation-tokenization-character-classi-cation-or-w-1417405.html)
This paper addresses two remaining challenges in Chinese word segmentation. The challenge in HLT is to ﬁnd a robust segmentation method that requires no prior lexical knowledge and no extensive training to adapt to new types of data. The challenge in modelling human cognition and acquisition it to segment words efﬁciently without using knowledge of wordhood. We propose a radical method of word segmentation to meet both challenges.
4p
hongvang_1
16-04-2013
17
1
Download
-
Chapter 9 - Characters and strings. After you have read and studied this chapter, you should be able to: Declare and manipulate data of the char data type; write string processing program, applicable in areas such as bioinformatics, using String, StringBuilder, and StringBuffer objects; differentiate the three string classes and use the correct class for a given task; specify regular expressions for searching a pattern in a string; use the Pattern and Matcher classes; compare the String objects correctly.
42p
tangtuy04
12-03-2016
17
1
Download
-
VB6 không đuợc thiết kế để hổ trợ Unicode. Do đó khi dùng VB6 làm ngôn ngữ lập trình để làm việc với Unicode ta chạm phải những trở ngại vì giới hạn của nó. VB6 gần như không đá động gì đến Unicode. Người ta nói bên trong data type loại String của VB6 thì nó có khả năng chứa Unicode characters, nhưng thế thôi. Có một số nhu cầu ta cần phải giải quyết nếu ta muốn dùng VB6 cho Unicode. Ðó là: 1. 2. 3. 4. Làm sao hiển thị chữ Việt trong Textbox, Listbox .v.v.. Làm...
6p
balanghuyen
11-01-2010
68
21
Download
-
This book is intended as course material for the course Structured Programming with C/C++ at university level. It contains eight chapters, one for each lecture of the course. The chapters are: 1. Introduction to programming. Here we go through general principles about what programming means. You will be introduced to the development tool Microsoft Visual C++ and build your first programs. 2. Variables. Here we start from the beginning and explain all details in the first programs. You will learn what variables are and how they are used for storing of values needed in the program....
246p
tuanloc_do
03-12-2012
31
10
Download
-
Working with Your MySQL Database CHAPTER 9 225 Let’s look at a few of the more common uses of ALTER TABLE. One thing that comes up frequently is the realization that you haven’t made a particular column “big enough” for the data it has to hold. For example, in our Customers table, we have allowed names to be 30 characters long. After we start getting some data, we might notice that some of the names are too long and are being truncated. We can fix this by changing the data type of the column so that it is 45 characters long instead: alter table customers...
10p
yukogaru14
30-11-2010
35
4
Download
-
Functions make the basic query block more powerful and are used to manipulate data values. This is the first of two lessons that explore functions. You will focus on single row character, number, and date functions, as well as those functions that convert data from one type to another, for example, character data to numeric. At the end of this lesson, you should be able to Explain the various types of functions available in SQL. Identify the basic concepts of using functions. Use a variety of character, number, and date functions in SELECT statements.
66p
batoan
12-08-2009
78
3
Download
-
Most of the information that we include for each node and edge is straightforward to obtain from the Twitter stream. However, there are some data processing aspects that require special handling: Mapping user names to IDs: The Twitter stream relates the tweets with internal user identiﬁers, while user mentions are expressed as user names. To match them, we use the Twitter API to resolve the user-id and user-name reference. URL shortening: A tweet is constrained to 140 characters, so most URLs are shortened using a URL shortening service such as http: //bit.ly/.
12p
doipassword
01-02-2013
22
3
Download
-
Magnetic motion capture systems require the real actor to wear a set of sensors, which are capable of measuring their spatial relationship to a centrally located magnetic transmitter. The position and orientation of each sensor is then used to drive an animated character. One problem is the need for synchronizing receivers. The data stream from the receivers to a host computer consists of 3D positions and orientations for each receiver.
49p
hoangphiyeah1tv
24-04-2013
19
3
Download
-
Lecture Java: Chapter 2 (Data and Expressions) presented Character Strings, Variables and Assignment, Primitive Data Types, Expressions, Data Conversion, Interactive Programs, Graphics, Applets, Drawing Shapes.
98p
hoahue91
24-07-2014
17
2
Download
-
On completion of this chapter students will know how to: Declare variables and constants, format output, work with character data, create mathematical expressions, work with mixed data types and casting, use different data types for precision, utilize available math functions.
25p
nhanmotchut_3
19-10-2016
8
1
Download
-
The most basic data structure in MATLAB® is the matrix: a two-dimensional, rectangularly shaped data structure capable of storing multiple elements of data in an easily accessible format. These data elements can be numbers, characters, logical states of true or false, or even other MATLAB structure types.
865p
ngovanquang
06-03-2010
190
113
Download
-
File Concept Access Methods Directory Structure File-System Mounting File Sharing Protection To explain the function of file systems To describe the interfaces to file systems To discuss file-system design tradeoffs, including access methods, file sharing, file locking, and directory structures To explore file-system protection .
42p
perpan
02-09-2012
30
11
Download
-
First, this data does not compare directly with the occupational data derived solely from Field 7 (“Occupation or Type of Business”) on the SAR form. Filers sometimes leave Field 7 blank. Filers also sometimes provide information in narratives that is different from the information they provided in Field 7. Second, the subject(s) for the purposes of these statistics are not necessarily the subject(s) whose information appears in Part I of either the SAR-DI or SAR-SF.
67p
thangbienthai
23-11-2012
24
5
Download
-
Explanation to improve readability of program comments one line /* ... */ comments multiple lines javadoc comments Comments that in form of /** …*/ are used by the javadoc program to produce HTML documentation for the program Example: This is an example of special java doc comments used for \n generating an html documentation. It uses tags like: @author Florence Balagtas @version 1.2
61p
nguyenvanhabk1
04-09-2012
42
3
Download
-
In this chapter, you learn what is input and output devices. The keyboard is presented and different keyboard types are described. You are introduced to various pointing devices, such as the mouse, trackball, touchpad, pointing stick, joystick, touchscreen, and pen input. Scanners and reading devices, including optical scanners, optical readers, magnetic ink character recognition readers, and data collection devices are explained,...
66p
kiepnaybinhyen_04
15-12-2015
14
3
Download

WARC-Type: response

Content-Type: application/http; msgtype=response

Set-Cookie: TLDEVNamespace=ark49gp86cevcm09s7m4mmfh64; path=/; domain=.tailieu.vn; HttpOnly

Connection: close

Server: Apache/2.2.31 (CentOS)

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Pragma: no-cache

Vary: Accept-Encoding

Content-Type: text/html; charset=UTF-8


markdown:
# Lịch sử văn minh thế giới
**Lịch sử văn minh thế giới**chọn lọc sau:
-
Ebook "Lịch sử văn minh thế giới" gồm 8 chương đem lại cho người đọc sự hiểu biết cơ bản và hệ thống về những nền văn minh thời cổ trung đại ở phương Đông và nền văn minh công nghiệp thời cận đại. Sau đây là phần 1 của ebook, trình bày nội dung của 4 chương học đầu tiên. Mời các bạn cùng tham khảo.
223p
maiyeutoni
01-12-2014
646
324
Download
-
Tiếp theo phần 1 của ebook "Lịch sử văn minh thế giới", sau đây là phần 2 của ebook trình bày nội dung của 4 chương cuối: Chương 5 - Văn minh Hy Lạp và La Mã cổ đại, Chương 6 - Văn minh Tây Âu thời trung đại, Chương 7 - Sự xuất hiện văn minh công nghiệp, Chương 8 - Văn minh thế giới thế kỷ XX. Mời các bạn cùng tham khảo nội dung của ebook.
232p
maiyeutoni
01-12-2014
362
237
Download
-
Đề cương ôn tập "Lịch sử văn minh thế giới (145 câu hỏi)". Đây là tài liệu được biên soạn một cách rõ ràng, kỹ lưỡng. Tác giả đã có sự sưu tầm, tổng hợp các dạng câu hỏi liên quan đến môn học Lịch sử văn minh thế giới. Mời các bạn cùng tham khảo tài liệu để củng cố lại kiến thức và chuẩn bị tốt cho kỳ thi.
130p
luckystar_1201
07-11-2013
220
103
Download
-
"Tài liệu ôn tập môn Lịch sử văn minh thế giới" được biên soạn nhằm giúp các bạn sinh viên thuận tiện trong việc ôn tập chuẩn bị cho kỳ thi. Tài liệu gồm có 3 câu hỏi: Cơ sở hình thành và thành tựu cơ bản của văn minh Ai Cập; Quá trình hình thành đạo Hồi, Ảnh hưởng của Việt Nam?; Những thành tựu cơ bản của văn minh Ấn Độ thời cổ trung đại. Sau mỗi câu hỏi có kèm theo đáp án trả lời. Mời các bạn cùng tham khảo.
7p
heavenmaster1997
16-07-2011
558
182
Download
-
Để hiểu rõ hơn về sự xuất hiện văn minh công nghiệp mời các bạn cùng tham khảo tài liệu "Lịch sử văn minh thế giới" do Đoàn Trung biên soạn với các nội dung chính như sau: Điều kiện ra đời của nền văn minh công nghiệp; Cuộc cách mạng công nghiệp.
7p
banglang_ht
11-08-2010
1165
343
Download
-
Để hiểu rõ hơn về những phát minh KHKT và học thuyết chính trị thời cận đại mời các bạn cùng tham khảo tài liệu "Lịch sử văn minh thế giới" do Đoàn Trung biên soạn với các nội dung chính như sau: Những phát minh khoa học tạo nên cuộc cách mạng tri thức thế kỉ XVII-XVIII; Những phát minh khoa học, kĩ thuật nổi bật trong thế kỉ XIX; Những học thuyết chính trị thời cận đại.
8p
banglang_ht
11-08-2010
727
257
Download
-
Để hiểu rõ hơn về những thành tựu về văn học nghệ thuật mời các bạn cùng tham khảo tài liệu "Lịch sử văn minh thế giới" do Đoàn Trung biên soạn với các nội dung chính như sau: Về văn học; Về nghệ thuật.
3p
banglang_ht
11-08-2010
548
222
Download
-
Tài liệu "Trắc nghiệm lịch sử văn minh của thế giới" cung cấp đến các bạn 33 câu hỏi có cả hình thức trắc nghiệm và tự luận. Mời các bạn cùng tham khảo nội dung tài liệu để biết thêm chi tiết.
7p
luckystar_1201
07-11-2013
181
57
Download
-
Nền văn minh Ả Rập là một trong những nền văn minh rực rỡ, huy hoàng của thế giới thời trung đại, được hình thành vào thế kỷ thứ VII trên cơ sở tiếp thu những nền văn minh lớn trước đó của nhân loại. Cuốn sách “Lịch sử văn minh Ả Rập” của nhà bác học, nhà sử học Will Durant – một trong những sử gia lớn thời hiện đại là một trong những công trình nghiên cứu có giá trị.
447p
badao259
11-04-2015
112
68
Download
-
Bài giảng "Văn minh thế giới thế kỷ XX" trình bày các nội dung về: Cách mạng tháng Mười Nga và sự ra đời của Liên Xô; Chiến tranh thế giới và sự phá hoại văn minh nhân loại; Văn minh thế giới nữa sau thế kỷ XX. Mời các bạn cùng tham khảo nội dung bài giảng để nắm bắt kiến thức chi tiết hơn.
39p
nhatrangyeuthuong
10-04-2014
118
29
Download
-
Bài thuyết trình lịch sử văn minh Ai Cập: Thời kỳ Trung Vương Quốc đề cập đến sự phát phát triển của xã hội Ai Cập thời kỳ Trung Vương Quốc. Phần đầu của bài thuyết trình nói về vấn đề phát triển của lịch sử, xã hội, thương mại và sản xuất đã thúc đẩy sự phát triển xã hội.
28p
nhatrangyeuthuong
10-04-2014
97
17
Download
-
Bài giảng "Lịch sử văn minh thế giới" trình bày các nền văn minh khác nhau trên thế giới từ cổ đại đến hiện đại của nền văn minh phương Đông và phương Tây, các thành tựu đạt được, văn hóa và tín ngưỡng. Mời các bạn cùng tham khảo tài liệu để hiểu hơn về quá trình hình thành, phát triển của các nền văn minh cổ đại.
54p
talata_1
22-09-2014
246
85
Download
-
Phần 1 của cuốn sách "Almanach những nền văn minh thế giới (Tập 3) - Khoa học kỹ thuật với nền văn minh nhân loại và dự báo nền văn minh thế kỷ XXI" trình bày các nội dung: Vũ trụ và sự hình thành thế giới thiên hà vô tận, trái đất và lịch sử ra đời của nó, lược sử tiến hóa loài người,... Mời các bạn cùng tham khảo nội dung chi tiết.
182p
tsmttc_002
03-06-2015
67
34
Download
-
Nối tiếp nội dung phần 1 cuốn sách "Almanach những nền văn minh thế giới (Tập 3) - Khoa học kỹ thuật với nền văn minh nhân loại và dự báo nền văn minh thế kỷ XXI", phần 2 trình bày các nội dung: Vũ khí trang bị trong lịch sử nhân loại, những công trình thế kỷ. Mời các bạn cùng tham khảo nội dung chi tiết.
226p
tsmttc_002
03-06-2015
60
35
Download
-
Suốt 5000 năm tồn tại và phát triển, văn minh Trung Quốc không chỉ có ảnh hưởng đến các dân tộc Châu Á, mà còn có những đóng góp lớn cho tiến trình phát triển của văn minh loài người. Những phát minh lớn của Trung Quốc trong lịch sử khoa học - kĩ thuật của thế giới.
21p
sony_12
25-06-2013
335
67
Download
## CHỦ ĐỀ BẠN MUỐN TÌM
[Luận văn lịch sử](http://tailieu.vn/tag/luan-van-lich-su.html) [Ẩm thực thế giới](http://tailieu.vn/tag/am-thuc-the-gioi.html) [Luận văn lịch sử Đảng](http://tailieu.vn/tag/luan-van-lich-su-dang.html) [Lịch sử báo chí thế giới](http://tailieu.vn/tag/lich-su-bao-chi-the-gioi.html) [Lịch sử văn hóa Việt Nam](http://tailieu.vn/tag/lich-su-van-hoa-viet-nam.html) [Lịch sử văn hoá](http://tailieu.vn/tag/lich-su-van-hoa.html) [Lịch sử văn minh](http://tailieu.vn/tag/lich-su-van-minh.html) [Đọc truyện cổ tích thế giới](http://tailieu.vn/tag/doc-truyen-co-tich-the-gioi.html) [Giáo trình lịch sử văn minh thế giới](http://tailieu.vn/tag/giao-trinh-lich-su-van-minh-the-gioi.html) [Lịch sử thế giới hiện đại](http://tailieu.vn/tag/lich-su-the-gioi-hien-dai.html) [Văn minh thế giới](http://tailieu.vn/tag/van-minh-the-gioi.html) [Lịch sử thế giới](http://tailieu.vn/tag/lich-su-the-gioi.html) [Du lịch thế giới](http://tailieu.vn/tag/du-lich-the-gioi.html) [Ô nhiễm môi trường thế giới](http://tailieu.vn/tag/o-nhiem-moi-truong-the-gioi.html) [Thế giới cổ tích](http://tailieu.vn/tag/the-gioi-co-tich.html) [Lịch sử văn học trung quốc](http://tailieu.vn/tag/lich-su-van-hoc-trung-quoc.html) [Truyện ngụ ngôn thế giới](http://tailieu.vn/tag/truyen-ngu-ngon-the-gioi.html) [Di tích lịch sử văn hóa](http://tailieu.vn/tag/di-tich-lich-su-van-hoa.html) [Kì quan thế giới](http://tailieu.vn/tag/ki-quan-the-gioi.html)

Set-Cookie: TLDEVNamespace=m07aovbfltnatp684c3unnpc37; path=/; domain=.tailieu.vn; HttpOnly


markdown:
Tải bản đầy đủ
Thạc sĩ - Cao học
Công nghệ thông tin
Giải pháp tăng tốc độ xử lý thuật toán SmithWaterman (tt)
1
MỞ ĐẦU
Công nghệ thông tin là một trong những ngành khoa học kỹ thuật có
tính phổ dụng rộng rãi, được áp dụng trong nhiều lĩnh vực khác nhau.
Trong đó, không thể không kể đến việc ứng dụng công nghệ thông tin
trong công nghệ sinh học. Và chính sự hội tụ của hai nền khoa học lớn
này đã hình thành một ngành khoa học đã và đang phát triển khá mạnh mẽ
đó chính là ngành Tin sinh học (Bioinformatics). Từ khi Tin sinh học ra
đời, nó đã trở thành một công cụ hỗ trợ đắc lực trong việc nghiên cứu và
ứng dụng các sáng chế, phát minh của ngành công nghệ sinh học vào thực
tiễn.
Trong những năm gần đây, các nhà khoa học trong lĩnh vực sinh học
đã phát hiện ra những cấu trúc sinh học phân tử mới và xây dựng thành
một hệ thống cơ sở dữ liệu sinh học phân tử khá lớn tập trung thành các
ngân hàng dữ liệu (GenBank, EMBL, DDBJ). Tháng 08 năm 2015,
GenBank đã công bố có 199.823.644.287 bases, từ 187.066.846
sequences trong hệ thống ngân hàng dữ liệu của đơn vị này.
Tuy nhiên, Với dữ liệu lớn thì việc tìm kiếm dữ liệu hoặc tìm kiếm
sự tương đồng trong database sẽ tốn rất nhiều chi phí về mặt thời gian, đặc
biệt là bài toán bắt cặp trình tự sinh học. Có nhiều thuật toán được xây
dựng để giải quyết bài toán bắt cặp trình tự sinh học, và mỗi thuật toán lại
có tính ưu việt khác nhau về mặt thời gian hoặc hiệu quả thực hiện. Thuật
toán Smith-Waterman thường được áp dụng để giải quyết bài toán bắt cặp
trình tự sinh học vì thuật toán này cho kết quả có độ chính xác cao, tuy
nhiên giải thuật này lại mất khá nhiều thời gian thực hiện. Để nâng cao
tính hiệu quả của giải thuật Smith-Waterman và góp phần cải thiện thời
2
gian thực hiện của thuật toán này, luận văn sẽ tập trung vào việc đẩy mạnh
thời gian thực hiện của giải thuật dựa trên nền tảng các GPU. Luận văn
được đề xuất với tên như sau: “Giải pháp tăng tốc độ xử lý thuật toán
Smith-Waterman”.
CHƯƠNG 1- CƠ SỞ LÝ THUYẾT
1.1. Tổng quan về GPU:
Trong kiến trúc của máy tính, bộ vi xử lý trung tâm (CPU) là một bộ
phận quan trọng để vận hành máy tính, là khối điều khiển, xử lý các
chương trình và dữ kiện. Tuy nhiên đối với những ứng dụng đòi hỏi tốc
độ xử lý cao thì CPU có thể không thể đáp ứng, đặc biệt là trong lĩnh vực
đồ họa, game 3D. Vì vậy, để tăng tốc độ xử lý và thực thi chương trình,
người ta bổ sung GPU vào hệ thống máy tính, vậy GPU là gì và phương
thức tăng tốc độ xử lý của nó trong hệ thống máy tính như thế nào, những
điều này sẽ được trình bày cụ thể dưới đây.
1.1.1. GPU là gì:
GPU (Graphics Processing Unit) là bộ vi xử lý chuyên dụng có nhiệm
vụ tăng tốc, xử lý đồ họa cho bộ vi xử lý trung tâm CPU nhằm tăng tốc
các ứng dụng đồ họa, ứng dụng khoa học, kỹ thuật và phân tích dữ liệu
lớn. GPU có thể đẩy nhanh tốc độ xử lý ở nhiều môi trường khác nhau:
máy tính (máy tính cá nhân, máy trạm, máy chơi game chuyên dụng), điện
thoại di động, máy tính bảng, robot, …
1.1.2.
Lịch sử phát triển của GPU:
Và trong khoảng 17 năm gần đây, GPU đã phát triển rất mạnh mẽ với
nhiều cải tiến, bổ sung, đặc biệt là những linh kiện phần cứng nhằm tăng
3
tốc độ xử lý của trình điều khiển VGA (Video Graphic Array). Khi GPU
mới xuất hiện thì chưa có khả năng lập trình mở rộng, sau thời gian phát
triển và cải tiến thì việc lập trình mở rộng trở nên khá dễ dàng.
1.1.3. Cấu trúc của GPU và cơ chế song song ứng dụng:
1.2. Tổng quan về OPENCL
1.2.1. Giới thiệu về OPENCL:
OpenCL (Open Computing Language) là một chuẩn lập trình mã
nguồn mở miễn phí sử dụng ngôn ngữ OPENCL-C dựa trên những tiêu
chuẩn của C99 và IEEE-754 (chuẩn dấu chấm động cho số học), do đó,
cấu trúc lệnh của OPENCL hoàn toàn giống với ngôn ngữ lập trình C.
1.2.2. Cấu trúc của OPENCL:
Sự vận hành của OpenCL được mô tả bởi cụm các model có mối liên
hệ với nhau, bao gồm Platform Model (mô hình nền tảng), Execution
Model (mô hình thực thi), Memory Model (mô hình bộ nhớ), và
Programming Model (mô hình lập trình).
a) Platform Model:
b) Execution Model:
c) Memory Model:
d) Programming Model:
1.2.3. Quy trình phát triển một chương trình OPENCL:
1.3. Bài toán bắt cặp trình tự:
Bắt cặp trình tự hay so sánh trình tự nhằm tìm đến sự tương đồng
giữa các trình tự bằng cách đo lường sự giống nhau của các chuỗi trình tự.
Các chuỗi trình tự ở đây chính là các chuỗi trình tự ADN, RNA hoặc các
trình tự amino acid (protein). Và việc bắt cặp trình tự được thực hiện bằng
4
cách thêm “gap” vào những vị trí sao cho các cột tương đồng nhau.
Ví dụ: cho trình tự a: AGTGACT, trình tự b: ATGCT, kết quả của quá
trình bắt cặp trình tự là:
AGTGACT
|
||
||
A– TG– CT
Để đánh giá được mức độ tương đồng của các trình tự, áp dụng công thức
sau:
𝒏𝒂 𝒙 𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒊 𝒙 𝒎𝒊𝒔𝒎𝒂𝒕𝒄𝒉 + 𝒏𝒈 𝒙 𝒈𝒂𝒑
(1.1)
Trong đó: na, ni, ng lần lượt là số các phần tử giống nhau, không giống
nhau và số các gap được thêm vào; match, mismatch và gap lần lượt là
các chỉ số tính toán để tìm ra mức độ tương đồng (match >0).
1.4. Các thuật toán giải quyết bài toán bắt cặp trình tự sinh học:
Có nhiều thuật toán được xây dựng đẻ giải quyết bài toán bắt cặp
trình tự: thuật toán Needleman-Wunsch, Smith-Waterman, Blast, ….
Thuật toán Needleman-Wunsch và Smith-Waterman đều dựa trên cơ chế
quy hoạch động, tuy nhiên mỗi giải thuật lại có một phương pháp xử lý
và tìm kiếm khác nhau.
CHƯƠNG 2 - NGUYÊN LÝ ĐẨY NHANH THUẬT TOÁN
SMITH-WATERMAN TRONG MÔI TRƯỜNG CPU-GPU
2.1. Thuật toán Smith-waterman nguyên thủy:
2.1.1. Giới thiệu:
Thuật toán Smith-Waterman là giải thuật giải quyết bài toán bắt cặp
trình tự cục bộ, nhằm tìm ra những đoạn có điểm tương đồng về cấu trúc
5
hoặc chức năng giữa các trình tự sinh học, nucleotide hoặc các chuỗi
protein.
Thuật toán này được F. Smith và Michael S. Waterman đề xuất vào
năm 1981 dựa trên một thuật toán trước đó được xây dựng bởi Needleman
và Wunsch, được biết đến với tên gọi: thuật toán Needleman-Wunsch.
2.1.2. Nguyên lý hoạt động:
Thuật toán Smith-Waterman là thuật toán sử dụng phương pháp quy
hoạch động để định lượng các điểm số cho quá trình bắt cặp trình tự.
Do áp dụng phương pháp quy hoạch động nên trong quá trình tính
toán, giải thuật sử dụng ma trận để ghi nhận điểm số và áp dụng công thức
sau:
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚
(2.1)
Hij=max(0, 𝐻𝑖−1,𝑗−1 + 𝜎𝑖𝑗 , 𝐻𝑖−1,𝑗 + 𝑑, 𝐻𝑖,𝑗−1 + 𝑑) , ∀𝑖 = 0, 𝑛, ∀𝑗 =
0, 𝑚 (2.2)
𝑚𝑎𝑡𝑐ℎ
và d=gap
𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ
𝜎𝑖𝑗 = {
Trong đó:
- n là độ dài của trình tự Sa,
- m là độ dài trình tự Sb,
- Hij là ma trận điểm số
- d là giá trị của gap
- match và mismatch lần lượt là điểm số trùng khớp và không trùng
khớp của Sai và Sbj, giả sử rằng điểm số match luôn dương (match ≥
0).
6
Để giải quyết bài toán bắt cặp trình tự cục bộ, giải thuật trãi qua các
bước sau:
Bước 1: Khởi tạo ma trận, áp dụng công thức (2.1).
Bước 2: Tính toán điểm số và điền ma trận, áp dụng công thức (2.2).
Bước 3: Tìm điểm số max trong ma trận Hi,j
Bước 4: Tìm dấu vết dựa trên ma trận vừa tính ở trên.
Bước 5: Kết quả bắt cặp trình tự
Để minh họa cho các bước của giải thuật, tìm hiểu ví dụ sau (ví dụ
1): cho trình tự A: CGTGAATTCAT, trình tự B: GACTTAC, cho các giá
trị match = 2, mismatch=-1, gap = -1; n, m: lần lượt là độ dài của chuỗi
trình tự A, B.
2.1.3. Thuật toán và Đánh giá:
Thuật toán Smith-Waterman thực hiện theo trình tự 5 bước:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Điền ma trận:
If (a[i]==b[j])
Delta= match
Else
Delta = mismatch
Hij=max(0, Hi-1,j-1 + delta, hi-1,j+d, Hi,j-1+d)
Bước 3: Tìm Hnmax,mmax:
If(max_H
7
max_H = Hij
imax = i
jmax = j
Bước 4: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 5: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ui và Vj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Vj được ghi vào
– (i,j) →(i,j-1): đi lui Ui và “-” được ghi vào
Thuật toán này giải quyết rất hiệu quả bài toán bắt cặp trình tự cục
bộ với độ chính xác tương đối cao, tuy nhiên thời gian thực hiện thuật toán
thì tốn khá nhiều thời gian, thời gian thuật toán thực thi là O(nm).
2.2. Phương pháp cải tiến thuật toán Smith-Waterman:
Dựa trên thuật toán Smith-Waterman nguyên thủy, phương pháp được
trình bày trong luận văn sẽ cải tiến tốc độ xử lý của thuật toán trong giai
đoạn điền ma trận.
Gọi x, y là đại diện cho điểm bắt đầu và điểm kết thúc của hai đoạn
tương đồng của hai trình tự. Lưu ý, đoạn tương đồng được xác định dựa
trên trình tự ban đầu của chúng. Giả sử rằng [x, y] là phân đoạn tương
đồng trong chuỗi SA, 1 ≤ 𝑥 ≤ 𝑦 ≤ 𝑛, với n là độ dài của chuỗi SA, tương
8
tự [z,w] là phân đoạn tương đồng của trình tự SB, 1 ≤ 𝑧 ≤ 𝑤 ≤ 𝑚, với m
là độ dài của chuỗi trình tự SB.
Ví dụ trên ta có như sau:
Trình tự Sa: C G T G A A T T C A T
Trình tự Sb: G A C T TA CT
Match = 2, mismatch = -1, gap = -1
Bắt cặp trình tự cục bộ giữa hai trình tự và đoạn tương đồng như sau:
Hình 2.1: Ví dụ đoạn tương đồng của hai trình tự
Ta có đoạn tương đồng là [4,9] cho trình tự SA.
2.2.1. Phương pháp cắt tỉa:
Để giải quyết bài toán bắt cặp trình tự cho cặp trình tự r=
cần
phải có kết quả của liên kết cho các trình tự 𝑝 =< 𝑎, 𝑏 >∈ 𝑃, trong đó
[xp, yp] là đoạn tương đồng giữa hai chuỗi trình tự, fp là số mismatch giữa
hai trình tự, gp là số gap được thêm vào. Tương tự, kết quả của liên kết
9
cho các trình tự 𝑞 =< 𝑎, 𝑐 >∈ 𝑃, trong đó [xq, yq] là đoạn tương đồng
giữa hai chuỗi trình tự, fq là số mismatch và gq là số gap.
Từ kết quả trên, phương pháp cắt tỉa được trình bày trong luận văn này
nhằm tăng tốc liên kết của thuật toán Smith – Waterman cho cặp
r=
∈ P và phương pháp cắt tỉa được áp dụng trong giai đoạn điền
ma trận.
Hình 2.2: Mô hình tổng quát biểu diễn trình tự tương đồng (Nguồn
[5])
Trong hình 2.2: (a) bắt cặp trình tự giữa sa và sb, (b) bắt cặp trình tự
giữa sa và sc, (c) phần chung giữa chúng trên chuỗi sa.
Giả sử rằng: p=
và q=
có a
đồng giữa các trình tự khi và chỉ khi 𝑥𝑞 ≤ 𝑦𝑝 𝑣à 𝑥𝑝 ≤ 𝑦𝑞 . Từ đó, suy ra
đoạn tương đồng giữa các trình tự được xác định bằng công thức sau đây:
[Max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )]
(2.3)
Điều kiện để phương pháp cải tiến được thực hiện: khi tồn tại đoạn
tương một đồng giữa các cặp trình tự p và q.
Ví dụ 2: Cho 3 trình tự:
10
Sa: CGTGAATTCAT
Sb: GACTTAC
Sc: GACTTAAATAGGGGC
Match =2, mismatch = -1 và gap = -1;
Kết quả bắt cặp trình tự của các cặp như sau:
Kết quả bắt cặp trình tự của Sa và Sb:
G A A T T
|
|
|
- C
|
|
G A C T T A C
Trong đó ta có đoạn tương đồng của trình tự p=< Sa,Sb> = [4,9] trên trình
tự Sa, fp=1 và gp=1;
Kết quả bắt cặp trình tự của Sa và Sc:
G A A T T C A
|
|
|
|
|
- T
|
G A C T T A A A T
Trong đó ta có đoạn tương đồng của trình tự p=< Sa,Sc> = [4,11] trên trình
tự Sa, fq=2 và gp=1;
Áp dụng công thức (2.3) để kiểm tra có tồn tại điểm tương đồng giữa các
đoạn trình tự trên:
[Max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )] = [𝑀𝑎𝑥(4,4), 𝑀𝑖𝑛(9,11)] = [4,9]
Vậy tồn tại đoạn tương đồng giữa các cặp trình tự => phương pháp cắt
tỉa được áp dụng trên các đoạn trình tự trên. Và đoạn tương đồng được
biểu diễn như sau:
11
7
8
Sa C G T G A A T
1
2
3
T
Sb
4
5
6
9
10
11
- C A T
G A C T T A C
1
2
3
1
2
3
4
5
6
7
4
5
6
7
8
9
10
11
T C A
- T
Sa C G T G A A T
Sc
G A C T T A A A T A G G G G C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Sa C G T G A A T T C A T
1
2
3
4
5
6
7
8
9
10
11
Hình 2.3: Biểu diễn bắt cặp trình tự của ba chuỗi Sa, Sb, Sc trên
chuỗi Sa
2.2.2. Ràng buộc dưới cho tất cả các cặp trong quá trình so sánh:
Ý tưởng của phương pháp này đó chính là sử dụng giới hạn thấp hơn
L1 cho tất cả các điểm số liên kết trong đoạn tương đồng
[max(𝑥𝑝 , 𝑥𝑞 ) , min(𝑦𝑝 , 𝑦𝑞 )] và là giới hạn dưới L cho các điểm liên kết
cho tất cả các cặp r =
. Do đó, một giới hạn thấp hơn L1 cho đoạn
tương đồng trong chuỗi sa được sử dụng như là một ràng buộc thấp hơn
cho những liên kết của những chuỗi con. Vì mỗi dãy làm một phần của
chuỗi sb và sc, điểm số liên kết cho cặp r=
ít nhất là L2 hay L2 có thể
được sử dụng như là một giới hạn dưới L cho tất cả cặp r=
.
12
Hình 2.4: Sự trùng khớp và không trùng khớp của ba trình tự
(Nguồn [5])
Hình 2.5 cho thấy sự trùng khớp và không trùng khớp của ba trình tự
sa, sb, sc khi sắp xếp. Như thể hiện trong hình, giới hạn dưới L2 cho điểm
số liên kết của cặp r có thể tính được bằng cách đến số lượng các biểu
tượng phù hợp mà thường xuất hiện trong ba chuỗi trình tự sa, sb, sc.
Hàm tính giá trị giới hạn dưới cho tất cả các điểm số liên kết trong
đoạn tương đồng được xác định bởi:
𝐿 = 𝑀𝑎𝑥(0, 𝑚𝑎𝑐𝑡𝑐ℎ × 𝑀 − 𝐹 − 𝐺)
(2.4)
Trong đó M là số match của các ký tự tương đồng trong đoạn tương
đồng giữa các trình tự, M được tính bằng cách lấy chiều dài của đoạn
tương đồng trừ đi số mismatch của chúng, được biểu diễn bởi công thức
sau:
𝑀 = min(𝑦𝑝 , 𝑦𝑞 ) − max(𝑥𝑝 , 𝑥𝑞 ) + 1 − (𝑓𝑝 + 𝑓𝑞 )
Công thức tính F: 𝐹 = 𝑚𝑖𝑠𝑚𝑎𝑡𝑐ℎ 𝑥 (𝑓𝑝 + 𝑓𝑞 )
(2.6)
(2.5)
13
Công thức tính G: 𝐺 = 𝑔𝑎𝑝 𝑥 (𝑔𝑝 + 𝑔𝑞 )
(2.7)
Vì đoạn tương đồng được xác định trên các trình tự ban đầu của Sa,
không bao gồm các ký tự GAP, do đó L được xác định bởi công thức (2.3)
là một giới hạn thấp hơn về điểm số của đoạn tương đồng.
Giả định rằng điểm số liên kết của đoạn tương đồng trên trình tự Sa
là L’, giả sử L’ < L, các điểm không phù hợp, GAP nằm trong đoạn tương
đồng và tất cả các biểu tượng còn lại đều phù hợp. Tổng điểm số của các
ký hiệu còn lại như vậy phải có một điểm số tiêu cực để đáp ứng cho L’ <
L, điều này mâu thuẫn với giả định điểm số 𝑚𝑎𝑡𝑐ℎ ≥ 0. Vậy kết luận rằng
L’>L.
Trong quá trình bắt cặp trình tự cục bộ cho ra điểm số liên kết tối đa,
vị trí bắt đầu và kết thúc của đoạn tương đồng là tùy ý, một ràng buộc thấp
hơn về điểm số của đoạn tương đồng là một ràng buộc địa phương về điểm
số cho toàn bộ khu vực.
2.2.3. Tế bào kích hoạt
Giả sử ta có L là một giới hạn thấp hơn trên tất cả các điểm liên kết,
một tế bào kích hoạt là một tế bào trong ma trận (i,j) thỏa mãn điều kiện
sau:
𝐻𝑖,𝑗 + 𝛼 × max(𝑚 − 𝑖, 𝑛 − 𝑘 ) < 𝐿
Phương pháp này sử dụng điểm số cao nhất đã được tính toán trước
đó nhằm tính toán điểm số trong ma trận Hi,j.
Vì vậy, tính toán giá trị của một ô trong ma trận H(i,j) có thể được
cắt tỉa trong giai đoạn điền ma trận nếu tất cả tế bào (i-1,j), (i,j-1), (i-1,j1) được kích hoạt hoặc đã được cắt tỉa.
14
2.2.4. Lý thuyết song song thuật toán Smith- Waterman:
2.3. Thuật toán cải tiến
2.3.1. Thuật toán Smith-Waterman với phương pháp cắt tỉa:
Thuật toán Smith-Waterman sử dụng phương pháp cắt tỉa sẽ giảm
được quá trình tính toán trong giai đoạn điền ma trận. Và thuật toán được
xây dựng như sau:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Xác định giá trị giới hạn dưới:
M =min(yp,yq) – max(xp,xq) +1 – (fp+fq)
F = mismatch x (fp +fq)
G = gap x (gp +gq)
Bound = Max(0, match x M – F – G)
Bước 3: Điền ma trận
Vì giá trị của ma trận luôn lớn dương, do đó, để đánh dấu các tế bào
kích hoạt hoặc tế bào được cắt tỉa chọn các giá trị âm, trong luận văn này,
tác giả chọn giá trị là -1.
If (Hi-1,j-1==-1 && Hi-1,j ==-1 && Hi, j-1 == -1)
Hij=-1
Else
If (a[i]==b[j])
Delta= match
Else
Delta = mismatch
15
Hij=max(0, Hi-1,j-1 + delta, Hi-1,j+d, Hi,j-1+d)
If (Hij + match * max(n-i,m-k) < bound)
Hij=-1
Bước 4: Tìm Hnmax,mmax:
If(max_H
max_H = Hij
imax = i
jmax = j
Bước 5: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 6: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ai và Bj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Bj được ghi vào
– (i,j) →(i,j-1): đi lui Ai và “-” được ghi vào
Thuật toán Smith-Waterman sử dụng phương pháp cắt tỉa giải quyết
bài toán bắt cặp trình tự cục bộ rất hiệu quả với độ chính xác tương đối
cao. Trong giai đoạn điền ma trận, việc bỏ qua tính toán giá trị của từng
tế bào trong ma trận sẽ giúp tăng tốc độ xử lý của thuật toán.
16
2.3.2. Thuật toán kết hợp giữa cắt tỉa và xử lý song song
Việc tính toán song song phụ thuộc vào việc xác định số đường chéo
trong ma trận, có nghĩa là tính được số lần tính toán song song của bài
toán. Gọi L là số đường chéo trong ma trận, công thức tính L được tổng
quát như sau:
𝑛
𝑚
𝑘
𝑘
𝐿= +
−1=
(𝑛+𝑚)
𝑘
-1
(2.9) (Nguồn [3])
Trong đó:
- n là chiều dài của chuỗi trình tự Sa, m là chiều dài của chuỗi trình tự
Sb.
- k là kích thước ma trận con, là ước số chung của chiều dài của hai
chuỗi trình tự n và m, với điều kiện k
Sau khi tính toán được số đường chéo trong ma trận thì cần phải xác
định được số ma trận cần tính toán trên mỗi đường chéo. Gọi Nmatrix là số
ma trận trên mỗi đường chéo Li và được xác định theo công thức sau:
𝑛
𝑚
𝑚
𝑘
𝑘
𝑘
𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿 (2.10)
(Nguồn [3])
Ví dụ: Cho trình tự Sa: ACTACTTAGT (n=10), Sb: ATGCTCTTAG
(m=10), match = 2, mismatch = -1 và gap =-1;
Với n=10 và m=10 => k =2, áp dụng công thức (2.9) ta có L=9.
17
A
A
T
A
C
T
C
A
G
T
0
0
0
0
0
0
0
0
0
0
0
A
0
2
2
1
2
1
0
0
2
1
0
T
0
1
1
4
3
2
3
2
1
1
3
G
0
0
0
3
3
2
2
2
1
3
2
C
0
0
0
2
2
5
4
4
3
2
2
T
0
0
0
2
1
4
7
6
5
4
4
C
0
0
0
1
1
3
6
9
8
7
6
T
0
0
0
2
1
2
5
8
8
7
9
T
0
0
0
2
1
1
4
7
7
7
9
A
0
2
2
1
4
3
3
6
9
8
8
G
0
1
1
1
3
3
2
5
8
11
10
Hình 2.5: Cách song song thuật toán SW trong giai đoạn điền ma
trận
Trong hình 2.7, ta có 9 đường chéo, theo cơ chế song song là lần lượt
tính giá trị cho từng đường chéo từ 1 đến 9. Đồng thời, trên mỗi đường
chéo có số ma trận cần phải tính theo kích thước k; việc tính toán cho từng
điểm số trong ma trận con cũng được thực hiện theo mô hình được miêu
tả trong hình 2.1.
Trước tiên, tính toán cho đường chéo số 1 (các tế bào ma trận màu
vàng): áp dụng công thức 2.10 ta tính được số ma trận là 1.
Tương tự, đường chéo số 2, số ma trận là 2.
Lặp lại quá trình tính toán cho đến khi hoàn tất việc tính toán điểm số
của các tế bào ma trận trên đường chéo số 9 của ma trận.
Từ mô hình trên, song song giải thuật Smith-Waterman được thực hiện
thông qua các bước sau:
18
Bước 1: Khởi tạo giá trị ban đầu cho ma trận
Hi0=0 với ∀𝑖 = 0, 𝑛, H0j=0 với ∀𝑗 = 0, 𝑚
Bước 2: Xác định kích thước k của ma trận con
Bước 3: Tính toán số đường chéo cần phải song song theo công thức:
𝑛
𝑚
𝑘
𝑘
𝐿= +
−1=
(𝑛+𝑚)
𝑘
-1
Bước 4: Tính toán số ma trận con trên đường chéo thứ I, ta thực hiện
song song các ma trận con theo hướng đường chéo:
𝑛
𝑚
𝑚
𝑘
𝑘
𝑘
𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿
(2.10)
Bước 5: Tìm giá trị max trong ma trận
Bước 6: Tìm vết dựa theo kết quả tính toán ở bước điền ma trận
Bước 7: In kết quả.
2.4. Thuật toán cải tiến
2.4.1. Phương pháp kết hợp giữa cắt tỉa và xử lý song song
Việc kết hợp phương pháp cắt tỉa và xử lý song song thuật toán
Smith-Waterman không chỉ cải thiện về mặt thời gian của việc cắt tỉa
những tế bào không tính toán mà còn đẩy nhanh xử lý song song những
giá trị từng tế bào trong từng ma trận trên mỗi đường chéo của ma trận.
Giải thuật kết hợp giữa phương pháp cắt tỉa và xử lý song song thuật toán
Smith-Waterman được trình bày qua các bước như sau:
Bước 1: Khởi tạo ma trận:
H[i][0]=0, 0<=i<=n, n là chiều dài chuỗi trình tự A
H[0][j]=0, 0<=j<=m, m là chiều dài chuỗi trình tự B.
Bước 2: Xác định giá trị giới hạn dưới:
19
M =min(yp,yq) – max(xp,xq) +1 – (fp+fq)
F = mismatch x (fp +fq)
G = gap x (gp +gq)
Bound = Max(0, match x M – F – G)
Bước 3: Xác định kích thước ma trận con và L
- k là ước số chung của n và m
- Tính số đường chéo của ma trận:
𝑛
𝑚
𝑘
𝑘
𝐿= +
−1=
(𝑛+𝑚)
𝑘
-1
Bước 4: Điền ma trận
For I = 0 to L
𝑛
𝑚
𝑚
𝑘
𝑘
𝑘
𝑁𝑚𝑎𝑡𝑟𝑖𝑥 = 𝑚𝑖𝑛 (𝐿, ( − max (0, 𝐿 − )) , ) , 1 ≤ 𝑖 ≤ 𝐿
Mỗi ma trận con ta tính như sau:
If (Hi-1,j-1==-1 && Hi-1,j ==-1 && Hi, j-1 == -1)
Hij=-1
Else
If (a[i]==b[j])
Delta= match
Else
Delta = mismatch
Hij=max(0, Hi-1,j-1 + delta, Hi-1,j+d, Hi,j-1+d)
If (Hij + match * max(n-i,m-k) < bound)
Hij=-1
Bước 5: Tìm Hnmax,mmax:
If(max_H
20
max_H = Hij
imax = i
jmax = j
Bước 6: Tìm dấu vết:
Xuất phát từ Hnmax,mmax,
nếu:
– Hij = Hi-1,j-1 + σij thì vết (i,j) → (i-1,j-1) theo đường chéo
– Hij = Hi,j-1 + d thì vết (i,j) → (i,j-1) đi lui
– Hij = Hi-1,j + d thì vết (i,j) → (i-1,j) đi lên
Bước 7: Kết quả:
Nếu:
– (i,j) →(i-1,j-1): theo đường chéo Ai và Bj được ghi vào
– (i,j) →(i-1,j): đi lên “-” và Bj được ghi vào
– (i,j) →(i,j-1): đi lui Ai và “-” được ghi vào
Phương pháp cắt tỉa kết hợp với xử lý song song thuật toán SmithWaterman đã làm tăng quá trình tính toán của giải thuật Smith-Waterman
trong bài toán bắt cặp trình tự cục bộ.
TIỂU KẾT CHƯƠNG 2
Chương hai đã giới thiệu tổng quan về giải thuật Smith-Waterman
từ lý thuyết cho đến các bước thực hiện giải thuật. Mặc dù, giải thuật
Smith-Waterman giải quyết bài toán bắt cặp trình tự cục bộ với độ chính
xác tương đối cao nhưng thời gian thực hiện giải thuật lại khá tốn nhiều
thời gian. Để tăng tốc thời gian xử lý của giải thuật, trong chương hai cũng
nêu rõ cơ chế tăng tốc bằng việc ứng dụng cắt tỉa các tế bào thỏa mãn một
21
điều kiện nhất định được gọi là tế bào kích hoạt. Đồng thời, ứng dụng việc
cắt tỉa vào quá trình song song trong giai đoạn điền ma trận. Trong chương
hai cũng thể hiện rõ các bước của giải thuật và đánh giá sơ bộ của thuật
toán.
CHƯƠNG 3- KẾT QUẢ THỰC NGHIỆM
3.1. Chương trình thực nghiệm
3.1.1. Chương trình:
Chương trình được xây dựng trên nền tảng C++ trong Visual Studio
Ultimate 2013 và thư viện OPENCL 2.0, kết hợp Intel® SDK for
OPENCL™ 2016. Với việc sử dụng thư viện của OPENCL 2.0 nên trong
chương trình thực thi cần phải khai báo như sau:
#define CL_HPP_TARGET_OPENCL_VERSION 200
Việc khai báo này rất cần thiết cho quá trình phát triển chương trình,
bởi việc sử dụng các hàm thư viện
trong version 2.0 của
OPENCL. Và sau đây là một số hàm được xây dựng trong chương trình:
3.1.1.1.
Hàm quét tìm Platforms:
Hàm được xây dựng nhằm tìm kiếm các Platforms được cài đặt trong
hệ thống và lựa chọn Platforms mặc định. Thông thường, mỗi máy tính
chỉ sử dụng một GPU, tuy nhiên đối với những cấu trúc máy tính mới hoặc
mạnh mẽ thì có thể sử dụng dual-GPU, vì vậy hàm được xây dựng nhằm
tìm kiếm tất cả các platforms có trong hệ thống, ví dụ: Intel® OPENCL,
AMD ® OPENCL, … Đồng thời, hàm sẽ lựa chọn Platform mặc định để
thực thi.
22
void TimPlatforms()
{
cl::Platform::get(&all_platforms);
if (all_platforms.size() == 0){
std::cout << " Khong tim thay platform.!\n";
exit(1);
}
default_platform = all_platforms[0];
std::cout << "Platform su dung: " <<
default_platform.getInfo
() <<
"\t Version: " <<
default_platform.getInfo
()
<< "\n\n";
}
3.1.1.2.
Hàm quét tìm thiết bị:
Cũng giống như hàm tìm kiếm Platform, hàm tìm kiếm thiết bị có mục
đích là sẽ tìm tất cả các GPU được gắn vào hệ thống máy tính, hàm không
chỉ thực thi trên hệ thống dual-GPU mà còn được sử dụng trong hệ thống
chỉ có một GPU duy nhất.
void TimDevices()
{
default_platform.getDevices(CL_DEVICE_TYPE_ALL,
&all_devices);
if (all_devices.size() == 0){
std::cout << " Khong tim thay thiet bi
nao!\n";
exit(1);
}
default_device = all_devices[0];
std::cout << "Device su dung: " <<
default_device.getInfo
() << "\n\n";
}
23
Đối với cấu hình của máy mà tác giả thực nghiệm, trường hợp sử dụng
CPU là thiết bị device của OPENCL giá trị trong mảng all_devices[] là 1
(all_devices[1]), và GPU giá trị là 0 (all_devices[0]).
3.1.1.3.
Hàm tính toán giới hạn thấp hơn:
Hàm xây dựng nhằm tìm ra giới hạn thấp hơn giữa hai chuỗi trình tự,
input đầu vào của hàm là kết quả của liên kết các cặp trước đó p=
,
q=
. Kết quả của hàm sẽ là giá trị giới hạn thấp hơn. Input của hàm
được khai báo dạng typedef struct có dạng như sau:
typedef struct Reinput
{
string strname1;
string strinfo1;
string strname2;
string strinfo2;
long int so_mismatch, so_gaps, start, end;
}Re_input;
Trong đó: Các biến số trong struct là kết quả của quá trình bắt cặp
trình tự của hai chuỗi trình tự.
Và hàm tìm giá trị thấp hơn được xây dựng như sau:
24
int calculateBound(Reinput str1, Reinput str2,
Score score)
{
int bound = 0;
if ((str1.end < str2.start) || (str2.end <
str1.start))
{
bound = 0;
}
else
{
bound = max(0, ((min(str1.end, str2.end) max(str1.start, str2.start) - (str1.so_mismatch +
str2.so_mismatch)) - (str1.so_mismatch +
str2.so_mismatch) * score.mismatch (str1.so_gaps + str2.so_gaps) * score.gap));
}
return bound;
}
3.1.1.4.
Kernel file của phương pháp cắt tỉa kết hợp song song:
Như đã giới thiệu trong chương 1, kernel được thực hiện trên các thiết
bị của OPENCL (CPU đa lõi, GPU, …), device được chọn để thực thi
kernel còn phụ thuộc vào cấu hình máy tính, môi trường thực thi và ý
muốn của người lập trình. Và việc thực thi các kernel cần phải xác định
được id của từng work-item, do đó kernel của phương pháp cắt tỉa kết hợp
song song thuật toán Smith-Waterman được xây dựng như sau:
- Lấy id của work-item:
int x = get_global_id(0);
25
- Lấy giá trị của i và j:
int startI = subIndexes[2*x+0];
int startJ = subIndexes[2*x+1];
-
Nếu i thỏa mãn điều kiện (i >= n / 2) hoặc (i >= m – j) thì kiểm tra
Hi-1,j-1; Hi-1,j; Hi,j-1 có phải là các tế bào kích hoạt hay không, nếu là tế
bào kích hoạt thì bỏ qua tính toán giá trị Hij và ngược lại:
if ((ii >= (n / 2)) ||( ii >= m - jj))
{
if(H[(j-1)*(i-1)*dim]==-1 && H[j+(i-1)*dim]==-1
&& H[(j-1)+i*dim]==-1)
{
H[index]=-1;
T[index]=-1;
}
else
{
if(s1[ii]==s2[jj])
tam = H[(j-1)+(i-1)*dim] + match;
else
tam = H[(j-1)+(i-1)*dim] +
mismatch;
tam1 = H[j+(i-1)*dim] + gap;
tam2 = H[(j-1)+i*dim] + gap;
H[index] = max(max(max(0, tam),
tam1),tam2);
if ((H[index] + match*max(n - ii, m - jj))
< bound)
{
H[index] = -1;
T[index] = 0;
Tài liệu liên quan
Khảo sát và đề xuất biện pháp tăng tốc độ lắng trong qui trình sản xuất bột gạo
Giải pháp hạn chế và xử lý nợ quá hạn tại chi nhánh Ngân hàng NHNN & PTNT Phan Đình Phùng Hà Nội
Giải pháp hạn chế và xử lý nợ quá hạn
Giải pháp hạn chế và xử lý nợ quá hạn tại chi nhánh Ngân hàng NHNN & PTNT Phan Đình Phùng Hà Nội
MỘT SỐ GIẢI PHÁP CÔNG NGHỆ TRONG XỬ LÝ Ô NHIỄM MÔI TRƯỜNG MỎ
Thêm một số phương pháp tăng tốc độ PC
Luận văn giải pháp thu gom và xử lý chất thải rắn trên địa bàn huyện gia viễn, tỉnh ninh bình
Giai phap han che va xu ly no qua han tai NHNN&PTNT CN p PDP HN CQ 442691 PHUNG THI BICH THUY NH
Giai phap han che va xu ly no qua han tai NHNN&PTNT CN p PDP HN CQ 442691 PHUNG THI BICH THUY NH
Tài liệu Giải pháp - Tăng tốc kết nối WAN doc
Tài liệu bạn tìm kiếm đã sẵn sàng tải về
(1.18 MB) - Giải pháp tăng tốc độ xử lý thuật toán SmithWaterman (tt)
Tải bản đầy đủ ngay
×

Server: Apache