Phân đoạn bảng trong SQL Server (Table partitioning in SQL Server)

<Lưu lại, cần dùng sau này>

<Nguồn: http://www.sqlviet.com/blog/table-partitioning-trong-sql-server#more-2377>

Table partitioning là kỹ thuật phân chia bảng thành từng đoạn nhằm quản lý hiệu quả cơ sở dữ liệu với dung lượng lớn. Đây là tính năng mới được đưa vào SQL Server 2005 và tiếp tục được tăng cường ở phiên bản 2008. Đối với các ứng dụng truy cập từ bên ngoài, bảng (table) vẫn là một bảng duy nhất, chỉ có cấu trúc vật lý của nó là khác so với các bảng không phân đoạn.
Bảng được phân đoạn dựa vào giá trị một trường của nó (trường được chọn gọi là partition key). Ví dụ bạn có dữ liệu về các giao dịch bán hàng chứa trong bảng BanHang, bạn có thể phân đoạn theo năm của trường NgayGiaoDich (ngày giao dịch): các giao dịch xảy ra trong năm 2009 được nằm trong một đoạn riêng, tương tự với các giao dịch của năm 2010… Kỹ thuật này làm tăng khả năng mở rộng của SQL Server lên rất nhiều, và giúp cho việc quản trị các cơ sở dữ liệu lớn trở nên dễ dàng hơn. Thử hình dung với một bảng dữ liệu chứa vài trăm triệu bản ghi thường xuyên được cập nhật, các tác vụ như backup/restore, hoặc create/rebuild index đều rất tốn kém thời gian. Việc truy vấn hoặc sửa đổi dữ liệu cũng rất vất vả. Table partitioning nhằm giải quyết các trở ngại đó, nó có các ưu điểm chính sau:

1. Tiện lợi về quản trị

– Bạn có thể backup/restore một đoạn mà không ảnh hưởng đến các đoạn còn lại: ví dụ tại thời điểm năm 2010 thì các đoạn chứa dữ liệu của 2009 và các năm trước không còn tiếp nhận dữ liệu mới nữa, bạn không cần phải thường xuyên backup các đoạn này và chỉ cần backup đoạn 2010.

– Bạn cũng có thể REBUILD lại index trên từng đoạn (những đoạn cần phải REBUILD do có nhiều thao tác xóa, sửa) thay vì trên toàn bộ bảng.

– Nó cũng cho phép nhanh chóng loại bỏ dữ liệu nguyên một đoạn ra khỏi bảng thay vì phải dùng lệnh DELETE (thao tác này gọi là SWITCH-OUT). Tương tự nó cũng cho phép “nạp” dữ liệu từ một bảng khác vào thành một đoạn mới (SWITCH-IN). Tính năng này rất có giá trị đối với các ứng dụng ETL và Datawarehouse.
Ví dụ bạn cần import dữ liệu của năm 2008, bạn có thể import vào một bảng riêng và sau đó switch-in bảng này vào bảng chính một cách tức thì. Trước khi có partitioning, bạn phải dùng lệnh INSERT để chuyển dữ liệu từ bảng riêng vào bảng chính. Quá trình này mất nhiều thời gian hơn và trong suốt quá trình đó bảng bị khóa và không thể truy cập được.

2. Cải tiến về hiệu năng

– Khi một câu lệnh chỉ cần lấy dữ liệu ở một đoạn nào đó thì hệ thống chỉ cần truy nhập vào đoạn đó và bỏ qua các đoạn còn lại (tính năng này gọi là partition elimination)
– Khi các đoạn dữ liệu được lưu trữ ở các ổ cứng khác nhau sẽ làm giảm tranh chấp vào/ra giữa các câu lệnh. Ví dụ hai câu lệnh SELECT và UPDATE hoạt động trên cùng một bảng nhưng ở hai đoạn khác nhau có thể thực hiện hoàn toàn song song với nhau.

Việc phân đoạn bảng dựa trên hai khái niệm mới sau đây:

· Partition function: qui định giá trị biên cho các đoạn. Hệ thống dựa vào hàm này để xác định đoạn mà mỗi bản ghi thuộc vào.

· Partition scheme: ánh xạ các đoạn khai báo trong partition function vào các filegroup (mỗi đoạn được lưu trữ tại một filegroup).

Dưới đây tôi sẽ đi qua từng bước thiết lập việc phân đoạn thông qua một ví dụ cụ thể.
Bạn có bảng BanHang gồm các cột BangHang_ID, NgayGiaoDich, MaSP, SoLuong, ThanhTien. Bạn muốn phân đoạn bảng theo từng năm của NgayGiaoDich: để cho đơn giản, giả sử bạn muốn lưu các giao dịch của năm 2009 trở về trước vào một đoạn, trong năm 2010 vào một đoạn, và từ 2011 trở đi vào một đoạn (về sau bạn vẫn luôn luôn có thể sửa đổi để giành riêng một đoạn cho 2011 và bổ sung các đoạn mới cho 2012, 2013…). Như vậy với cấu hình ở trên, bảng sẽ có 3 đoạn: 2009 trở về trước, 2010, và 2011 trở về sau. Do đó bạn cũng cần 3 filegroup.

Bước 1: Tạo database và filegroup

CREATE DATABASE PartTest
GO
USE PartTest
GO
-- tạo filegroup
ALTER DATABASE PartTest ADD FILEGROUP FG2009AndBefore 
ALTER DATABASE PartTest ADD FILEGROUP FG2010 
ALTER DATABASE PartTest ADD FILEGROUP FG2011AndAfter

– thêm data file vào mỗi filegroup

ALTER DATABASE PartTest ADD FILE (NAME = N'FY2009AndBefore', FILENAME = N'D:\DATA\PartTest\FY2009AndBefore.ndf') TO FILEGROUP FG2009AndBefore 
ALTER DATABASE PartTest ADD FILE (NAME = N'FY2010', FILENAME = N'D:\DATA\PartTest\FY2010.ndf') TO FILEGROUP FG2010 
ALTER DATABASE PartTest ADD FILE (NAME = N'FY2011AndAfter', FILENAME = N'D:\DATA\PartTest\FY201AndAfter.ndf') TO FILEGROUP FG2011AndAfter

Bước 2: Tạo partition function và partition scheme

USE PartTest
GO
CREATE PARTITION FUNCTION PFunc_NGD(DATETIME) AS RANGE RIGHT FOR VALUES ('2010-01-01', '2011-01-01') 
GO 
CREATE PARTITION SCHEME PScheme_NGD AS PARTITION PFunc_NGD TO (FG2009AndBefore, FG2010, FG2011AndAfter)

Hàm partition function có tên PFunc_NGD định nghĩa giá trị biên cho các đoạn, là ngày đầu tiên của năm 2010 và ngày đầu tiên của 2011. Giống như khi bạn cắt một sợi dây, chỉ cần 2 nhát cắt để chia sợi dây làm 3 đoạn, ở đây cũng chỉ có 2 giá trị biên. Do vậy dải giá trị của các đoạn sẽ như sau:

Đoạn 1: từ trước đến 2009-12-31 23:59:59

Đoạn 2: 2010-01-01 00:00:00 đến 2010-12-31 23:59:59

Đoạn 3: 2011-01-01 00:00:00 về sau

Sau đó partition scheme PScheme_NGD dùng hàm PFunc_NGD để “gắn” các đoạn vào từng filegroup. Như vậy đoạn 1 sẽ đến FG2009AndBefore, đoạn 2 đến FG2010 và đoạn 3 đến FG2011AndAfter.

Lưu ý là partition function không giống với các user-defined function. Trong Management Studio, bạn thấy partition function và partition scheme ở mục Database/Storage.

Một lưu ý nữa là một partition function có thể được dùng cho nhiều partition scheme, và cả hai là các đối tượng chung trong database chứ không gắn liền với một bảng cụ thể. Khi định nghĩa bảng (xem bước 4) bạn cần chỉ định dùng partition scheme nào.

Bước 4: Tạo bảng dùng partition scheme

USE PartTest
GO
CREATE TABLE dbo.BanHang(
BangHang_ID INT IDENTITY,
NgayGiaoDich DATETIME,
MaSP INT,
SoLuong INT,
ThanhTien INT
) ON PScheme_NGD(NgayGiaoDich)
GO
CREATE CLUSTERED INDEX CI_BanHang_NGD ON dbo.BanHang(NgayGiaoDich) ON PScheme_NGD(NgayGiaoDich)

Mệnh đề “ON PScheme_NGD(NgayGiaoDich)” trong hai lệnh tạo bảng và tạo index ở trên chỉ định bảng BanHang và index CI_BanHang_NGD được tạo trên partition scheme PScheme_NGD, có nghĩa là để cho nó quản lý việc phân bổ dữ liệu. Vậy là bảng BanHang đã được phân đoạn. Bạn có thể kiểm tra xem dữ liệu được ghi vào đoạn nào:

SELECT $PARTITION.PFunc_NGD('2008-07-24')
SELECT $PARTITION.PFunc_NGD('2009-12-31')
SELECT $PARTITION.PFunc_NGD('2010-01-01')
SELECT $PARTITION.PFunc_NGD('2010-11-25')
SELECT $PARTITION.PFunc_NGD('2011-03-16')

Về Đồ thị khái niệm – Conceptual Graph

Đồ thị khái niệm (Conceptual Graph – CG) là một hình thức biểu diễn tri thức. Trong báo cáo đầu tiên công bố về CG, John.F.Sowa đã sử dụng chúng để biểu diễn các lược đồ khái niệm được sử dụng trong các hệ thống cơ sở dữ liệu. Các sách đầu tiên về CG (Sowa 1984) áp dụng một loạt các chủ đề trong trí thông minh nhân tạo , khoa học máy tính , và khoa học nhận thức .

Từ năm 1984, mô hình đã được phát triển theo ba hướng chính

 

Một giao diện đồ họa cho logic bậc nhất

Trong phương pháp này , một công thức trong logic bậc nhất (vị từ tính toán) được biểu diễn bởi một đồ thị có gán nhãn .
Một ký hiệu tuyến tính, được gọi là Conceptual Graph Interchange Format (CGIF) , đã được chuẩn hóa  trong chuẩn ISO cho Common Logic.

Sơ đồ bên dưới là một ví dụ về các hình thức hiển thị cho một đồ thị khái niệm .

 

Mỗi hộp được gọi là một nút khái niệm, và một hình oval được gọi là một nút quan hệ . Trong CGIF, CG này sẽ được biểu diễn bởi câu sau đây :

[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)

 

Trong CGIF, các dấu ngoặc vuông kèm theo thông tin bên trong các nút khái niệm , và dấu ngoặc đơn kèm theo thông tin bên trong các nút quan hệ . Các chữ x và y, được gọi là nhãn coreference , biểu diễn cách các nút khái niệm và các nút quan hệ được nối với nhau như thế nào . Trong Common Interchange Format Logic ( CLIF ) , những kí tự được ánh xạ vào các biến , như trong các câu sau đây :

(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))

 

Như ví dụ này cho thấy , các dấu sao trên các nhãn coreference * x * y trong CGIF ánh xạ đến các biến lượng từ tồn tại trong CLIF, và các dấu chấm hỏi trên ?y ?x ánh xạ đến các biến ràng buộc trong CLIF . Một lượng từ với mọi, biểu diễn bởi @every* z trong CGIF , sẽ được biểu diễn là forall ( z) trong CLIF.
Sự suy luận có thể được thực hiện bằng cách chuyển đổi  đồ thị thành các công thức logic , sau đó áp dụng một động cơ suy luận logic .

Simulated Annealing – Thuật toán mô phỏng luyện kim

Tổng quan thuật toán mô phỏng luyện kim (Simulated Annealing (SA))

Giới thiệu chung về thuật toán SA

SA là một thuật toán tìm kiếm xác suất di truyền, là phương pháp tối ưu hoá có thể áp dụng để tìm kiếm tối ưu hoá toàn cục của hàm chi phí và tránh tối ưu hoá địa phương bằng việc chấp nhận một lời giải tồi hơn với một xác suất phụ thuộc nhiệt độ T.

Tiền thân của SA là thuật toán Monte Carlo năm 1953 của nhóm Metropolis. Thuật toán SA được đề xuất bởi S. Kirk _ partrick năm 1982 và được công bố trước công chúng năm 1983.

SA có nguồn gốc từ cơ học hệ thống. SA thực thi đơn giản và tương tự quá trình luyện kim vật lý. Trong luyện kim vật lý kim loại được đốt nóng tới nhiệt độ cao và làm lạnh từ từ để nó kết tinh ở cấu hình năng lượng thấp (tăng kích thước của tinh thể và làm giảm những khuyết điểm của chúng). Nếu việc làm lạnh không xảy ra từ từ thì chất rắn không đạt được trạng thái có cấu hình năng lượng thấp sẽ đông lạnh đến một trạng thái không ổn định (cấu trúc tối ưu địa phương)

Gọi E là năng lượng của trạng thái s, E’ là trạng thái năng lượng của trạng thái s’ và ∆E = E’ – E là sự chệnh lệch nhiệt độ giữa trạng thái s’ và trạng thái s. Nếu ∆E ≤ 0 thì sự thay đổi kết quả được chấp nhận với xác suất  trong  đó T  là nhiệt  độ, kB là một hằng số vật lý được gọi là hằng số Boltzmann.

SA sử dụng một biến điều khiển toàn cục là biến nhiệt độ T. Ban đầu T ở giá trị rất cao và sau đó được giảm dần xuống. Trong quá trình tìm kiếm SA thay lời giải hiện thời bằng cách chọn ngẫu nhiên lời giải láng giềng với một xác suất phụ thuộc vào sự chênh lệch giữa giá trị hàm mục tiêu và tham số điều khiển T.

Quá trình tối ưu hoá được tiếp tục cho tới khi cực tiểu toàn cục được tìm thấy hoặc tổng số bước chuyển vượt quá một số tối đa các bước chuyển đã được định trước. Sự chuyển tiếp ở một nhiệt độ kết thúc khi đạt tới trạng thái cân bằng nhiệt. Sau khi đạt tới trạng thái cân bằng nhiệt thì nhiệt độ được giảm thấp hơn. Nếu hệ thống không đông lạnh và cũng không tìm được cực tiểu toàn cục thì vòng lặp vẫn tiếp tục và chỉ số k tăng. Hệ thống đông lạnh khi T tiến tới nhiệt độ Tcuối do người dùng đưa ra.

Mã giả thuật toán:

 
s ← s0; e ← E(s) // Initial state, energy.
sbest ← s; ebest ← e // Initial "best" solution
k ← 0 // Energy evaluation count. 
while k < kmax and e > emax // While time left & not good enough: 
T ← temperature(k/kmax) // Temperature calculation. 
snew ← neighbour(s) // Pick some neighbour. 
enew ← E(snew) // Compute its energy. 
if P(e, enew, T) > random() then // Should we move to it? 
s ← snew; e ← enew // Yes, change state. 
if e < ebest then // Is this a new best? 
sbest ← snew; ebest ← enew // Save 'new neighbour' to 'best found'. 
k ← k + 1 // One more evaluation done 
return sbest // Return the best solution found.

Xem thêm tại: http://en.wikipedia.org/wiki/Simulated_annealing
 

Kĩ thuật nhánh cận

<Just type to remember>

<Theo “Kỹ thuật thiết kế giải thuật” – Nguyễn Văn Linh >

Với các bài toán tìm phương án tối ưu, nếu chúng ta xét hết tất cả phương án thì mất rất nhiều thời gian, nhưng nếu sử dụng phương pháp tham ăn thì phương án tìm được chưa hẳn đã tối ưu. Nhánh cận là kĩ thuật xây dựng cây tìm kiếm phương án tối ưu, nhưng không xây dựng toàn bộ cây mà sử dụng giá trị cận để hạn chế bớt các nhánh.

Cây tìm kiếm phương án có nút gốc biểu diễn cho tập tất cả các phương án có thể có, mỗi nút lá biểu diễn cho một phương án nào đó. Nút n có các nút con tương ứng với các khả năng có thể lựa chọn tập phương án xuất phát từ n.Kĩ thuật này gọi là phân nhánh.

Với mỗi nút trên cây ta sẽ xác định một giá trị cận. Giá trị cận là một giá trị gần với giá của các phương án.Với bài toán tìm min ta sẽ xác định cận dưới còn với bài toán tìm max ta sẽ xác định cận trên. Cận dưới là giá trị nhỏ hơn hoặc bằng giá của phương án, ngược lại cận trên là giá trị lớn hơn hoặc bằng giá của phương án.

Bài toán đường đi người giao hàng

Phân nhánh

Cây tìm kiếm phương án là cây nhị phân trong đó:

  • Nút gốc là nút biểu diễn cho cấu hình bao gồm tất cả các phương án.
  • Mỗi nút sẽ có 2 con, con trái biểu diễn cho cấu hình bao gồm tất cả các phương án chứa một cạnh nào đó, con phải biểu diễn cho cấu hình bao gồm tất cả các phương án không chứa cạnh đó (các cạnh để xét phân nhánh được lập tuân theo một thứ tự nào đó, chẳng hạn thứ tự từ điển).
  • Mỗi nút sẽ kế thừa các thuộc tính của tổ tiên của nó và có thêm một thuộc tính mới (chứa hay không chứa một cạnh nào đó).
  • Nút lá biểu diễn cho một cấu hình chỉ bao gồm một phương án.
  • Để quá trình phân nhánh mau chóng tới nút lá, tại mỗi nút ta cần có một quyết định bổ sung dựa trên nguyên tắc là mọi đỉnh trong chu trình đều có cấp 2 và không tạo ra một chu trình thiếu.

Dynamic Programming (Kĩ thuật quy hoạch động)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

Nội dung kĩ thuật:

Như trong https://vuonghienuit.wordpress.com/2012/04/10/divide-and-conquer-ki-thu%E1%BA%ADt-chia-d%E1%BB%83-tr%E1%BB%8B/ đã nói, kĩ thuật chia để trị thường dẫn chúng ta đến một giải thuật đệ quy. Trong các giải thuật đó, có thể có một số giải thuật có độ phức tạp thời gian mũ. Tuy nhiên, thường chỉ có một số đa thức các bài toán con, điều đó có nghĩa là chúng ta đã phải giải bài toán con nào đó nhiều lần. Để tránh việc giải dư thừa một số bài toán con, chúng ta tạo ra một bảng để lưu trữ kết quả của các bài toán con và khi cần chúng ta sẽ sử dụng kết quả đã được lưu trữ trong bảng mà không cần phải giải lại bài toán đó. Lấp đầy bảng kết quả của bài toán con theo một quy luật nào đó để nhận được kết quả của bài toán ban đầu (cũng đã được lưu trong một số ô nào đó của bảng) được gọi là quy hoạch động (dynamic programming). Trong một số trường hợp để tiết kiệm ô nhớ, thay vì dùng một bảng, ta chỉ dùng 1 vectơ.

Có thể tóm tắt giải thuật quy hoạch động như sau:

1. Tạo bảng bằng 2 cách:

    • Gán giá trị cho một số ô nào đó.
    • Gán giá trị cho các ô khác nhờ vào giá trị của các ô trước đó.

2. Tra bảng và xác định kết quả của bài toán ban đầu.

Ưu điểm của phương pháp quy hoạch động là chương trình thực hiện nhanh do không phải tốn thời gian giải lại một bài toán con đã được giải.

Kỹ thuật quy hoạch động có thể dùng để giải các bài toán tối ưu, các bài toán có công thức truy hồi.

Phương pháp quy hoạch động sẽ không đem lại hiệu quả trong các trường hợp sau:

  • Không tìm được công thức truy hồi.
  • Số lượng các bài toán con cần giải quyết và lưu giữ kết quả lả rất lớn.
  • Sự  kết hợp lời giải của bài toán con chưa chắc cho ta lời giải của bài toán ban đầu.

 

Một số bài toán có thể giải bằng quy hoạch động: “Bài toán tính số tổ hợp”, “Bài toán cái ba lô”, “Bài toán đường đi người giao hàng”,…

 

Greedy algorithm (Kĩ thuật tham lam)

<Just Type to Remember>

<Theo “Kỹ thuật thiết kế giải thuật – Nguyễn Văn Linh”>

 

1. Bài toán tối ưu tổ hợp:

Là một dạng của bài toán tối ưu, nó có dạng tổng quát như sau:

  • Cho hàm f(X) xác định trên một tập hữu hạn các phần tử D. Hàm f(X) được gọi là hàm mục tiêu.
  • Mỗi phần tử X thuộc D có dạng X = (x1, x2,…xn) được gọi là một phương án.
  • Cần tìm một phương án X thuộc D sao cho hàm  f(X) đạt min (max). Phương án X như vậy gọi là tối ưu.

Ta có thể tìm thấy phương án tối ưu bằng “vét cạn” nghĩa là xét tất cả các phương án trong tập D (hữu hạn) để tìm phương án tốt nhất. Mặc dù tập D là hữu hạn nhưng để tìm phương án tối ưu cho một bài toán kích thước n bằng vét cạn ta có thể cần một thời gian hàm mũ.

2. Nội dung kĩ thuật tham lam (tham ăn):

Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang ăn món ngon thứ hai, lại ăn hết món ngon thứ hai và chuyển sang món ngon thứ 3..

Kĩ thuật tham lam thường được vận dụng để giải bài toán tối ưu tổ hợp bẳng cách xây dựng một phương án X. Phương án X này được xây dựng bằng cách lựa chọn từng thành phần  Xi của X cho đến khi hoàn chỉnh (đủ n thành phần). Với mỗi Xi, ta sẽ chọn Xi tối ưu. Với cách này thì có thể ở bước cuối cùng ta sẽ phải chấp nhận giá trị cuối cùng còn lại.

Áp dụng kĩ thuật tham lam sẽ cho ta một giải thuật thời gian đa thức, tuy nhiên nói chung chúng ta chỉ đạt được một phương án tốt chứ chưa hẳn là tối ưu.

Có rất nhiều bài toán mà ta có thể giải bằng kĩ thuật này.

Các bài toán ví dụ: Các bạn tìm hiểu các bài toán như: “Bài toán trả tiền của máy rút tiền tự động ATM”, “Bài toán cái balô”, “Bài toán đường đi của người giao hàng”, …