1
B
Ộ GIÁO DỤC V
À ĐÀO T
ẠO

T
ẬP ĐO
ÀN BƯU CHÍNH VI
ỄN THÔNG VIỆT NAM

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG VIỆT NAM
LÊ THỊ THANH SƠN PHÉP PHÂN RÃ TRONG CƠ SỞ DỮ LIỆU
PHÂN TÁN VÀ ỨNG DỤNG

CHUYÊN NGÀNH: TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
MÃ SỐ: 60.48.15 TÓM TẮT LUẬN VĂN THẠC SỸ KỸ THUẬT HÀ NỘI – 2010


3
CHƯƠNG 1
TỔNG QUAN VỀ CƠ SỞ DỮ LIỆU PHÂN TÁN
1.1. THIẾT KẾ PHÂN TÁN LÀ GÌ
Thiết kế phân tán bao gồm:
- Thiết kế hệ thống mạng máy tính
- Thiết kế các CSDL phân tán cho mạng máy tính đó
Khi thiết kế hệ thống mạng máy tính tức là chúng ta đi
xác định vị trí đặt các máy tính trong mạng như thế nào. Từ đó
xác định vị trí đặt dữ liệu trong mạng máy tính đó. Tiếp theo là
xác định các phần mềm ứng dụng cài đặt trên mạng. Cuối cùng
là cách khai thác dữ liệu trên mạng đó như thế nào.
Thiết kế CSDL phân tán là nghiên cứu cách tổ chức dữ
liệu trên mạng máy tính. Sắp xếp, phân nhóm, chia nhỏ dữ liệu
thành những mảnh và đặt chúng trên mạng máy tính như thế
nào.
1.2. CSDL PHÂN TÁN LÀ GÌ
CSDL phân tán là CSDL được phân thành nhiều mảnh
và cấp phát đến các nút trên hệ thống mạng máy tính.
Trong đó:
CSDL là tập dữ liệu có liên quan với nhau trong cùng một bài
toán quản lý. 4
Phân tán, phân rã hay phân mảnh CSDL là chia nhỏ CSDL
thành các phần mỗi phần mỗi phần gọi là một mảnh con hay
một CSDL con.
1.3. YÊU CẦU DẪN ĐẾN PHÂN TÁN CSDL

i 1
Ui; Fi


πUi(F+)i = 1, 2, , k. Vậy phân rã W = < A, F > là quá trình
phân rã đồng thời tập thuộc tính A và tập phụ thuộc hàm F
thành các Fi.
Phân rã ngang R
Phân rã ngang R là chia ngang quan hệ R thành R1, R2,
…, Rk với Ri là những quan hệ trên A. Ri

Rj =

nếu i


j; R =

k
i
Ri
1

Phân rã ngang R bắt buộc các Ri phải rời nhau Ri

Rj
=

nếu i


k
thì khôi phục R bằng phép nối R
1
|><| R
2
|><|
…|><| R
k
. Trong phép phân tán dọc thì đối với những phép
phân tán tốt mới đảm bảo dấu bằng trong biểu thức: R = R
1
|><|
R
2
|><| …|><| R
k
(1)
1.6. KẾT LUẬN CHƯƠNG
Như vậy khi xây dựng CSDL phân tán thì cần xây dựng dựa
trên sự kết hợp thống nhất giữa hai hướng trong quá trình xử lý
dữ liệu: lý thuyết các hệ CSDL và công nghệ mạng máy tính.
Xây dựng CSDL đảm bảo đầy đủ các yêu cầu, ràng buộc để có
thể phân tán CSDL đó một cách tốt nhất. Quá trình phân tán
CSDL gồm có phân mảnh CSDL và cấp phát các mảnh đó như
thế nào trong hệ thống mạng máy tính để đảm bảo tối ưu quá
trình truy cập và xử lý CSDL. Để giải quyết vấn đề này thì có
một số phương pháp phân mảnh CSDL được đề cập đến trong
chương II.

k
i 1
Ui là một phân rã của W
Output: khẳng định (yes/no) phân rã bảo toàn phụ thuộc hay
không?
Algorithim 8
 X  Y  F nếu XG+

Y ( bao đóng XG+ tính theo
tập phụ thuộc hàm G) thì kết luận yes, phân rã bảo toàn phụ
thuộc. Ngược lại nếu tồn tại chỉ một phụ thuộc hàm X  Y của
F mà XG+ không chứa Y thì kết luận no, phân rã không bảo
toàn phụ thuộc.
2.1.4. Phân rã thành các BCNF
Thuật toán kiểm tra phép phân rã thành các BCNF hay
không?
Input: W = < A, F > = < A, {Xi Yi}>; i =
k,1

Phép phân rã W | > {W1, W2, , Wk}; Wi = < Ui,
Fi > ; Ri = R[Ui].
Fi

ðUi(F+) và A =

k

W2 = < X2Y2, X2  Y2> = < U2, F2 >
Wk = < XkYk, Xk  Yk > = <Uk, Fk >
Nếu A



k
i 1
Xi Yi đặt X = A -

k
i 1
Xi Yi và phân rã
W thành k+ 1 sơ đồ con như sau:
W1 = < X1Y1, X1  Y1> = < U1, F1 >
W2 = < X2Y2, X2  Y2> = < U2, F2 >
Wk = < XkYk, Xk  Yk > = <Uk, Fk >
Wk+1 = < X,

>.
Ta dễ dàng thử lại rằng các sơ đồ quan hệ con được phân rã
trong thuật toán là những sơ đồ quan hệ dạng BCNF.
2.1.5. Phân rã thành các BCNF, bảo toàn phụ thuộc, có nối
không tổn thất
Thuật toán kiểm tra phép phân rã thành các BCNF, bảo toàn
phụ thuộc, có nối không tổn thất?
Input: W = < A, F > = < A, {Xi Yi}>; i =
k,1

Phép phân rã W | > {W1, W2, , Wk}; Wi = < Ui,

Bước 2. Phân rã W thành k+1 sơ đồ con như sau:
W1 = < X1Y1, X1  Y1> = < U1, F1 >
W2 = < X2Y2, X2  Y2> = < U2, F2 >
Wk = < XkYk, Xk  Yk > = <Uk, Fk >
Wk+1 = < key,

>.
Ta dễ dàng thử lại rằng các sơ đồ quan hệ con được phân rã
trong thuật toán là những sơ đồ BCNF, phép phân rã bảo toàn
phụ thuộc vì mỗi phụ thuộc hàm được cho vào một sơ đồ con,
phân rã có nối không tổn thất vì có một sơ đồ con chứa key, ta
đã chứng minh trong bổ đề 5.2
2.1.6. Phân rã dọc theo độ liên đới của các thuộc tính
Trong hầu hết các bài toán quản lý đều được phân rã thành
các bài toán con. Mỗi bài toán con có chứa các thuộc tính liên
đới (liên kết) với nhau. Độ liên đới của các thuộc tính phụ thuộc
vào bản chất, độ ứng dụng và độ truy xuất của các thuộc tính 11
đó. Sự gắn kết của các thuộc tính trong các truy xuất, vấn tin thể
hiện lực liên đới giữa chúng.
Gọi Q = {q1, q2, . . . . .qq} là tập các vấn tin của người
dùng sẽ truy vấn trên tập thuộc tính A = {A1, A2, . . . . An}.
Mỗi câu vấn tin qi và mỗi thuộc tính Aj sẽ có một giá trị sử
dụng thuộc tính (attribute usage value), ký hiệu là use (qi, Aj)
Bảng AQ = ( use (qi, Aj)) với j = 1, 2, n và i = 1, 2,
q gọi là bảng giá trị sử dụng.
2.2. MỘT SỐ Ý TƯỞNG PHÂN RÃ LƯỢC ĐỒ QUAN HỆ
THEO LỰC LIÊN ĐỚI

Khi cần chia A thành 4 nhóm. Ta lấy 4 thuộc tính làm 4
đại diện cho bốn nhóm, đó là SoHD, Manv, Masp, MaKH. Mỗi
thuộc tính b khác bốn thuộc tính trên ta tính lần lượt có 4 độ
thuộc cf(SoHD,b), cf(Manv,b), cf(Masp,b), cf(MaKH,b). So 12
sánh và cho cùng vào nhóm với thuộc tính mà b có độ thuộc lớn
nhất, trong trường hợp không phân nhóm được ta xét thêm điều
kiện cho b vào nhóm mà trong đó đã có nhiều thuộc tính a mà
cf(a,b) lớn.
2.2.2. Phương pháp dùng khoảng cách
Giả sử ta có bảng giá trị sử dụng như trong Bảng 2.9
Biến đổi hàng thành cột ta được bảng
Bảng 2.11: Bảng giá trị sử dụng
q
1
q
2
q
2
q
4
q
5
q
6
q
7
q


Hình 2.1. Sơ đồ thuật toán K-means clustering
Begin
Input:

- n objects
- k clusters

Initial k cluster centerscalculate



objects
-
centers

grouping based on



D ). Ta giả sử thuộc tính
D có k giá trị khác nhau Domain(D) = {d1, d2, d3, , dk}.
Ta thấy trong hệ quyết định S các thuộc tính điều kiện C
thường quyết định giá trị thuộc tính D. Theo thuật toán Quinlan
chúng ta có thể tìm được tập luật, với những thuộc tính C như
thế nào thì thuộc tính quyết định là d1 hay d2 v.v.
2.4. KẾT LUẬN CHƯƠNG
Như vậy trong quá trình phân mảnh CSDL thì có thể sử
dụng phép phân mảnh dọc hoặc phép phân mảnh ngang. Tùy
theo từng bài toán mà sử dụng phương pháp nào cho thích hợp;
đôi khi có thể sử dụng kết hợp cả hai phương pháp này. Thông
thường khi thiết kế CSDL phân tán thì sử dụng phép phân tán
dọc để thiết kế các quan hệ thành các chuẩn, sau đó sử dụng các
phép phân rã ngang để phân mảnh dữ liệu trong quá trình khai
thác CSDL. Sau khi phân mảnh thì việc cấp phát các mảnh trên
các nút cũng là vấn đề cần phải giải quyết, nó trở thành bài toán
cấp phát các mảnh trên mạng. 15

CHƯƠNG 3
ỨNG DỤNG PHÉP PHÂN RÃ ĐỂ PHÂN TÍCH DỮ LIỆU
SINH VIÊN TRONG TRƯỜNG CAO ĐẲNG KINH TẾ -
KỸ THUẬT THƯƠNG MẠI
3.1. GIỚI THIỆU BÀI TOÁN ỨNG DỤNG
Trong tất cả các trường học hiện nay công việc quản lý
sinh viên, quản lý điểm, quản lý giảng dạy đã được tin học hóa.
Điều này đã giúp quá trình quản lý được nhanh chóng, đơn

cần xếp loại.
Yêu cầu: Phân tích để xếp điểm của n sinh viên theo k nhóm.
3.2.2. Giải quyết bài toán
Để thực hiện các yêu cầu bài toán, sử dụng thuật toán K-
Mean để gom cụm dữ liệu điểm của n sinh viên theo k nhóm.
Bước 1: Thực hiện kết nối đến CSDL phân tán trên hệ thống
mạng cục bộ để lấy danh sách điểm sinh viên và số nhóm k cần
xếp nhóm.
Bước 2: Khởi tạo k điểm làm trung tâm cho từng nhóm 17
Bước 3: Tính tổng khoảng cách đến k điểm trung tâm
Bước 4: Nhóm các sinh viên vào k nhóm.
Bước 5: Đặt lại k điểm trung tâm là điểm trung bình trong nhóm
Bước 6: Quay lên bước 3
Bước 7: Đưa danh sách điểm sinh viên đã được xếp theo k
nhóm
3.3. LỰA CHỌN NGÔN NGỮ VÀ MÔI TRƯỜNG CÀI
ĐẶT
3.3.1. Giới thiệu hệ quản trị CSDL SQL SERVER 2008
Microsoft SQL server là một hệ quản trị cơ sở dữ liệu
quan hệ (Relational Database Management System – RDBMS)
do Microsoft phát triển. SQL Server là một hệ quản trị cơ sở dữ
liệu quan hệ mạng máy tính hoạt động theo mô hình khách chủ
cho phép đồng thời cùng lúc có nhiều người dùng truy xuất đến
dữ liệu, quản lý việc truy nhập hợp lệ và các quyền hạn của
từng người dùng trên mạng.
3.3.2. Giới thiệu ngôn ngữ lập trình VB.NET 2008
Visual Basic.NET (VB.NET) là ngôn ngữ lập trình

Sau khi thực hiện xong ứng dụng phép phân rã để phân
tích dữ liệu sinh viên trong trường Cao đẳng Kinh tế - Kỹ thuật
Thương Mại. Kết quả đã đạt được:
Kết nối đến SQL Server để lấy CSDL phân tán trên mạng
cục bộ của Nhà trường. Đây chính là việc truy xuất dữ liệu và
truyền trên mạng. Sử dụng phân rã ngang để lấy một phần dữ
liệu sinh viên.
Ứng dụng đã sử dụng thuật toán K-Mean về để gom cụm
điểm của n sinh viên theo k nhóm. Số nhóm ở đây có thể thay
đổi theo từng loại hình đào tạo: niên chế và tín chỉ trong Nhà
Trường.
Tuy nhiên ứng dụng chỉ dừng lại ở mức còn đơn giản số
điểm của từng sinh viên còn ít. Bài toán còn có thể giải quyết ở
mức phức tạp hơn, số lượng điểm của từng sinh viên nhiều hơn.
CSDL sinh viên có thể phát triển nhiều hơn thế nữa. Đây chính
là hướng phát triển của chương trình sau này. 21
KẾT LUẬN
Đối với một hệ CSDL vấn đề thiết kế CSDL là một vấn
đề quan trọng và có ảnh hưởng trực tiếp đến hiệu quả của hệ
thống. Thiết kế dữ liệu là vấn đề đầu tiên cần được quan tâm.
Mục đích của thiết kế CSDL quan hệ là sinh ra một tập các sơ
đồ quan hệ cho phép lưu trữ thông tin không bị dư thừa, đồng
thời cho phép thực hiện các thao tác một cách dễ dàng. Các
thuật toán phân rã nhằm ứng dụng trong vấn đề loại trừ các dị
thường về dữ liệu, giải quyết vấn đề vẹn toàn dữ liệu và bảo
mật thông tin, ngoài ra nó còn tránh được các dư thừa về dữ liệu
cũng như tiết kiệm bộ nhớ. Đối với phân rã ngang thì ứng dụng