- i -
Số hóa bởi Trung tâm Học liệu

ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

NGUYỄN THỊ LAN ANH
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN ĐỂ TỔ CHỨC
KHAI THÁC THÔNG TIN VỀ GIAO THÔNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2014
Thái Nguyên - 2014

- iii -
Số hóa bởi Trung tâm Học liệu

Lời cảm ơn
Để hoàn thành chƣơng trình cao học và viết luận văn này, em đã nhận đƣợc sự
giúp đỡ và đóng góp nhiệt tình của các thầy cô trƣờng Đại học Công nghệ Thông tin
và Truyền Thông, Đại học Thái Nguyên.
Trƣớc hết, em xin chân thành cảm ơn các thầy cô trong bộ phận Đào tạo sau
đại học, Đại học Công nghệ thông tin và Truyền thông, trƣờng Đại học Thái
Nguyên đã tận tình giảng dạy, trang bị cho em những kiến thức quý báu trong suốt
những năm học qua. Em xin gửi lời biết ơn sâu sắc tới PGS. TS Đỗ Trung Tuấn đã
dành rất nhiều thời gian và tâm huyết hƣớng dẫn, chỉ bảo em trong suốt quá trình
thực hiện đề tài.
Xin chân thành cảm ơn gia đình, bạn bè đã nhiệt tình ủng hộ, giúp đỡ, động
viên cả về vật chất lẫn tinh thần trong thời gian học tập và nghiên cứu.
Trong quá trình thực hiện luận văn, mặc dù đã rất cố gắng nhƣng cũng không
tránh khỏi những thiếu sót. Kính mong nhận đƣợc sự cảm thông và tận tình chỉ bảo
của các thầy cô và các bạn.
- iv -
Số hóa bởi Trung tâm Học liệu


1.2.5. Kiến trúc cơ bản của CSDL phân tán 6
1.3. So sánh cơ sở dữ liệu phân tán và cơ sở dữ liệu tập trung 9
1.4. Sự cần thiết của cơ sở dữ liệu phân tán 12
1.5. Kết luận chƣơng 14
CHƢƠNG 2. 15
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN 15
2.1. Các vấn đề về phân mảnh dữ liệu 15
2.1.1. Lý do phân mảnh 15
2.1.2. Các kiểu phân mảnh 16
2.1.3. Mức độ phân mảnh 16
2.1.4. Các quy tắc phân mảnh 17
2.1.5. Các kiểu cấp phát 17
2.1.6. Các yêu cầu thông tin 18
2.2. Các phƣơng pháp phân mảnh 19
2.2.1. Phân mảnh dữ liệu ngang 19
2.2.2. Phân mảnh dọc 24
2.2.3. Phân mảnh hỗn hợp 27
2.3. Cấp phát
27
2.3.1. Bài toán cấp phát 27
2.3.2. Yêu cầu về thông tin 28
2.3.3. Mô hình cấp phát 29
2.4. Truy vấn trong cơ sở dữ liệu phân tán 31
2.4.1. Mục đích của xử lý truy vấn 31
2.4.2. Các tầng của quá trình xử lý truy vấn 32
2.5. Kĩ thuật thực hiện phép nối và phép hợp của đại số quan hệ 33
2.5.1. Phép chọn 35
2.5.2. Phép nối 36
2.5.3. Phân mảnh 38



Danh mục hình vẽ
Hình 1.1. Mô hình CSDL phân tán 4
Hình 1.2. Mô hình Peer-to-peer 4
Hình 1.3. Mô hình File Server 5
Hình 1.4. Mô hình Client Server 5
Hình 1.5. Kiến trúc cơ bản của CSDL phân tán 6
Hình 1.6. Các phân mảnh và mô hình vật lý cho một quan hệ toàn cục 8
Hình 2.1 So sánh các phƣơng pháp nhân bản 18
Hình 2.1. Lƣợc đồ phân tầng tổng quát để xử lý truy vấn phân tán 33
Hình 2.2. Rút gọn phân mảnh ngang với phép chọn 35
Hình 2.3a. Cây đại số quan hệ truy vấn gốc 37
Hình 2.3b. Rút gọn phân mảnh ngang với phép kết nối 38
Hình 2.5. Rút gọn cho phân mảnh gián tiếp 42
Hình 2.6. Rút gọn phân mảnh hỗn hợp 43
Hình 3.1. Tỉnh Thái Nguyên 44
Hình 3.2. Cần thiết an toàn giao thông 45
Bảng 1. Cấu trúc bảng HUYEN 46
Bảng 2. Cấu trúc bảng DUONG 47
Bảng 3. Cấu trúc bảng LOAIMADUONG 47
Bảng 4. Cấu trúc bảng KIEUDUONG 48
Bảng 5. Cấu trúc bảng TOCHUCGIAOTHONG 48
Bảng 6. Cấu trúc bảng MUCDOHUHONG 49
Bảng 7. Cấu trúc bảng LOAIBAOTRI 49
Bảng 8. Cấu trúc bảng DONVITHICONG 50
Bảng 9. Cấu trúc bảng THONGTINBAOTRI 51
Hình 3.3. Sơ đồ về mối quan hệ 51
Hình 3.3. Sơ đồ định vị của các mảnh tại các vị trí 54
Hình 3.3. Các mảnh và hình ảnh vật lý của một quan hệ tổng thể 55
Hình 3.3. Mô hình mạng của hệ thống quản lí các cung đƣờng 56

Extract Transform Load
IMS
Information Management System
LAN
Local Area Network
Mainframe
Máy tính mainframe
MDX
Multidimensional eXpressions
MSIL
MicroSoft Intermediate Language
MSSQL
Microsoft SQL Server
NT
Network Technology
ORACLE
Hệ quản trị cơ sở dữ liệu ORACLE
Partition
Phân đoạn
PC
Máy vi tính, máy cá nhân
SQL
Structured Query Language
XML
Extensible Markup Language - 1 -
Số hóa bởi Trung tâm Học liệu


hiểu, thu thập các thông tin về giao thông. Từ những thông tin thu thập đƣợc phân
tích, thiết kế CSDL phân tán để quản lý các thông tin đó
Phƣơng pháp nghiên cứu : Để thực hiện đƣợc mục tiêu và nhiệm vụ đặt ra
trong đề tài, tôi áp dụng hai phƣơng pháp nghiên cứu đó là: phƣơng pháp nghiên
cứu lý thuyết và phƣơng pháp nghiên cứu thực nghiệm. Đối với phƣơng pháp
nghiên cứu lý thuyết: tôi tiến hành nghiên cứu và thu thập các tài liệu liên quan đến
CSDL phân tán, thiết kế CSDL phân tán, các công cụ có thể triển khai quản trị
CSDL phân tán. Tiếp đến tôi thu thập các tài liệu liên quan đến thông tin về hệ
thống các cung đƣờng. Đối với phƣơng pháp thực nghiệm: tôi phân tích yêu cầu
thực tế của hệ thống và để xác định đƣợc các chức năng, quy trình hoạt động của hệ
thống. Tiếp theo vận dụng cơ sở lý thuyết liên quan nhƣ CSDL phân tán, thiết kế
CSDL phân tán vào thiết kế hệ thống, sử dụng công cụ SQL Server và Visual
Studio để quản trị CSDL phân tán và công cụ thiết kế giao diện và cuối cùng đánh
giá kết quả đạt đƣợc.
Ý nghĩa khoa học của đề tài : Việc ứng dụng CSDL phân tán để quản lý dữ
liệu về các cung đƣờng hiện nay là vấn đề quan trọng và cần thiết cho những ngƣời
làm công tác quản lý giao thông vận tải có cái nhìn chính xác, và đƣa ra quyết định
kịp thời.
Bố cục của luận văn
Luận văn chia thành các chƣơng:
1. Chƣơng 1: Tổng quan về cơ sở dữ liệu phân tán
2. Chƣơng 2: Thiết kế cơ sở dữ liệu phân tán
3. Chƣơng 3: Thiết kế, xây dựng cơ sở dữ liệu các cung đƣờng tại Thái
Nguyên
Cuối luận văn là phần kết luận và tài liệu tham khảo.

- 3 -
Số hóa bởi Trung tâm Học liệu

CHƢƠNG 1.

tệp cƣ trú tại các vị trí khác nhau trong một mạng máy tính [03]. Hình 1.1. Mô hình CSDL phân tán
Trong hệ thống cơ sở dữ liệu phân tán gồm nhiều trạm, mỗi trạm có thể khai
thác các giao tác truy nhập dữ liệu trên nhiều trạm khác.
1.2.3. Các hình thức tổ chức hệ thống phân tán
a)Mô hình Peer-to-peer
Các máy tính cá nhân và máy trạm có thể đƣợc sử dụng nhƣ một hệ thống độc
lập trợ giúp các ứng dụng địa phƣơng. Mỗi thành viên trong mạng có vai trò ngang
nhau, tự quản lý tài nguyên của chính mình và chia sẻ tài nguyên cho các máy tính
khác trên mạng. Mỗi một máy tính trên mạng vừa đóng vai trò máy chủ (Server),
vừa đóng vai trò là máy khách (Client).
Đây là mô hình mạng đơn giản, phù hợp với những hệ thống mạng nhỏ không
có yêu cầu cao về bảo mật.

Hình 1.2. Mô hình Peer-to-peer

- 5 -
Số hóa bởi Trung tâm Học liệu

b) Mô hình File Server
Máy chủ tệp một số máy dịch vụ tệp đƣợc gán trực tiếp vào mạng LAN, máy
chủ tệp là một thiết bị quản lý các hoạt động tệp và phục vụ các máy tính cá nhân
đƣợc kết nối trong mạng LAN. Mỗi máy cá nhân đƣợc phân chia một dung lƣợng
cố định trên ổ cứng của máy chủ tệp, chƣơng trình ở các máy tính cá nhân có thể
tham chiếu đến các tệp trên phần đĩa tƣơng ứng của nó bằng một đặc tả đƣờng dẫn.
Những hạn chế của máy chủ tệp nhƣ: dữ liệu di chuyển trên mạng quá nhiều, việc
kiểm soát dữ liệu là phi tập trung, các máy trạm phải đủ mạnh.


Hình 1.5. Kiến trúc cơ bản của CSDL phân tán
Ngƣời ta xét các khái niệm sau [2] Sơ đồ tổng thể
Sơ đồ phân đoạn
Sơ đồ định vị
Sơ đồ ánh xạ địa phƣơng 2
Sơ đồ ánh xạ địa phƣơng 1
DBMS của vị trí 1
CSDL địa phƣơng tại vị trí 1
Các vị trí khác…
DBMS của vị trí 2
CSDL địa phƣơng tại vị trí 2

- 7 -
Số hóa bởi Trung tâm Học liệu

(1) Lược đồ toàn cục
Lƣợc đồ toàn cục định nghĩa tất cả dữ liệu đƣợc chứa trong cơ sở dữ liệu phân
tán nhƣ trong cơ sở dữ liệu tập trung. Vì vậy, lƣợc đồ toàn cục đƣợc định nghĩa
chính xác nhƣ định nghĩa lƣợc đồ cơ sở dữ liệu tập trung. Tuy nhiên, mô hình dữ
liệu lƣợc đồ toàn cục cần phải tƣơng thích với việc định nghĩa các ánh xạ tới các
mức của cơ sở dữ liệu phân tán. Vì vậy mô hình dữ liệu quan hệ sẽ đƣợc sử dụng

Có thể định nghĩa một bản sao của một phân mảnh tại một trạm cho trƣớc và
kí hiệu bằng tên Quan hệ toàn cục R và hai chỉ số. Ví dụ R
3
2
để chỉ bản sao của
phân mảnh R
2
đƣợc chứa ở trạm 3. Hai mô hình vật lý có thể giống nhau, ví là bản
sao của nhau.
Lƣợc đồ các trạm phụ thuộc: gồm lƣợc đồ ánh xạ cục bộ, DBMS của các trạm
cục bộ, cơ sở dữ liệu ở trạm đó. Hình 1.6. Các phân mảnh và mô hình vật lý cho một quan hệ toàn cục
(4) Lược đồ ánh xạ cục bộ
Do ba mức đầu các trạm độc lập, nên chúng không phụ thuộc vào mô hình dữ
liệu của DBMS cục bộ. Ở mức thấp hơn, nó cần phải ánh xạ mô hình vật lý thành
các đối tƣợng đƣợc thao tác bởi các DBMS cục bộ. Ánh xạ này đƣợc gọi là lƣợc đồ
ánh xạ cục bộ và phụ thuộc vào kiểu của DBMS cục bộ. Trong hệ thống không
đồng nhất có các kiểu khác nhau của ánh xạ cục bộ tại các trạm khác nhau. Yếu tố
quan trọng nhất để thiết kế kiến trúc này là:
Phân mảnh và cấp phát dữ liệu;
Quản lí dƣ thừa dữ liệu;
Quan hệ toàn cục
Phân mảnh
Mô hình vật lý
R
1
trạm 1
R

vấn đề điều khiển tập trung. Ngƣời quản trị cơ sở dữ liệu chung phân quyền cho
ngƣời quản trị cơ sở dữ liệu địa phƣơng.
b) Độc lập dữ liệu
Độc lập dữ liệu là một trong những nhân tố tác động đến cấu trúc cơ sở dữ liệu
để tổ chức dữ liệu chuyển cho chƣơng trình ứng dụng. Tiện lợi chính của độc lập dữ
liệu là các chƣơng trình ứng dụng không bị ảnh hƣởng khi thay đổi cấu trúc vật lý

- 10 -
Số hóa bởi Trung tâm Học liệu

của dữ liệu. Trong cơ sở dữ liệu phân tán, độc lập dữ liệu có tầm quan trọng cũng
nhƣ trong cơ sở dữ liệu truyền thống. Khái niệm cơ sở dữ liệu trong suốt mô tả hoạt
động chƣơng trình trên cơ sở dữ liệu phân tán đƣợc viết nhƣ làm việc trên cơ sở dữ
liệu tập trung. Hay nói cách khác tính đúng đắn của chƣơng trình không bị ảnh
hƣởng bởi việc di chuyển dữ liệu từ nơi này sang nơi khác trong mạng máy tính.
Tuy nhiên tốc độ làm việc bị ảnh hƣởng do có thời gian di chuyển dữ liệu [03].
c) Giảm dư thừa dữ liệu
Trong CSDL tập trung, tính dƣ thừa hạn chế đƣợc càng nhiều càng tốt vì:
Dữ liệu không đồng nhất khi có vài bản sao của cùng cơ sở dữ liệu logic; để
tránh đƣợc nhƣợc điểm này giải pháp là chỉ có một bản sao duy nhất.
Giảm không gian lƣu trữ. Giảm dƣ thừa có nghĩa là cho phép nhiều ứng dụng
cùng truy cập đến một cơ sở dữ liệu mà không cần đến nhiều bản sao ở những nơi
chƣơng trình ứng dụng cần.
Trong cơ sở dữ liệu truyền thống tính dƣ thừa dữ liệu cũng cần quan tâm vì:
Tính cục bộ của chƣơng trình ứng dụng sẽ tăng nếu dữ liệu đặt ở mọi
nơi mà chƣơng trình ứng dụng cần.
Khả năng sẵn sàng của hệ thống cao bởi vì khi có lỗi ở một nơi nào đó
trong hệ thống thì không cản trở hoạt động của chƣơng trình ứng dụng.
Nói chung, nguyên nhân đối lập với tính dƣ thừa đƣa ra trong môi trƣờng truyền
thống vẫn còn đúng cho hệ thống phân tán và vì vậy công việc định giá mức độ tốt

1. Thứ nhất, trong cơ sở dữ liệu phân tán với cấp độ tự trị cao ở mỗi điểm,
ngƣời có dữ liệu địa phƣơng sẽ cảm thấy an toàn hơn vì họ có thể tự bảo vệ
dữ liệu của mình thay vì phụ thuộc vào ngƣời quản trị hệ thống tập trung.
2. Thứ hai, vấn đề an toàn thực chất với hệ thống phân tán không giống nhƣ
các hệ thống thông thƣờng khác mà còn liên quan đến mạng truyền thông.
Nhƣ vậy trong cơ sở dữ liệu phân tán vấn đề an toàn cơ sở dữ liệu phức tạp hơn.

- 12 -
Số hóa bởi Trung tâm Học liệu

f) Tính biệt lập và an toàn: trong CSDL truyền thống, ngƣời quản trị hệ thống
có quyền điều khiển tập trung, ngƣời sử dụng có chắc chắn đƣợc phân quyền mới
truy cập vào đƣợc dữ liệu. Điểm quan trọng là trong cách tiếp cận cơ sở dữ liệu tập
trung, không cần thủ tục điều khiển chuyên biệt.
Trong CSDL phân tán, những ngƣời quản trị địa phƣơng cũng phải giải quyết
vấn đề tƣơng tự nhƣ ngƣời quản trị cơ sở dữ liệu truyền thống.
1.4. Sự cần thiết của cơ sở dữ liệu phân tán
a) Sự phát triển của các cơ cấu tổ chức
Cùng với sự phát triển của xã hội, nhiều cơ quan, xí nghiệp có cơ cấu tổ chức
không tập trung, hoạt động phân tán trên phạm vi rộng. Vì vậy thiết kế và cài đặt cơ
sở dữ liệu phân tán là phù hợp, đáp ứng mọi nhu cầu truy cập và khai thác dữ liệu.
Cùng với sự phát triển của công nghệ viễn thông, tin học, động cơ thúc đẩy kinh tế,
việc tổ chức các trung tâm máy tính lớn và tập trung trở thành vấn đề cần nghiên cứu.
Cơ cấu tổ chức và vấn đề kinh tế là một trong những nguyên nhân quan trọng
nhất của sự phát triển cơ sở dữ liệu phân tán.
b) Giảm chi phí truyền thông
Trong thực tế, sử dụng một số ứng dụng mang tính địa phƣơng sẽ làm giảm
chi phí truyền thông. Bởi vậy, việc tối ƣu hoá tính địa phƣơng của các ứng dụng là
một trong những mục tiêu chính của việc thiết kế và cài đặt một CSDL phân tán.
c) Hiệu quả công việc

Phần mềm phức tạp và kinh phí tốn kém;
Phải xử lý các thay đổi thông báo trong mọi địa điểm;
Khó kiểm soát tính toàn vẹn dữ liệu với nhiều bản sao dữ liệu đƣợc
phân bố khắp mọi nơi;
Nói chung, kỹ thuật thiết kế cơ sở dữ liệu phân tán phức tạp nhƣng hệ cơ sở
dữ liệu phân tán cũng cần thiết cho xu hƣớng phát triển kinh tế hiện nay.

- 14 -
Số hóa bởi Trung tâm Học liệu

1.5. Kết luận chƣơng
Cơ sở dữ liệu phân tán rất quan trọng vì nhiều lý do khác nhau, nó có thể đƣợc
cài đặt trên các mạng máy tính diện rộng và các mạng cục bộ nhỏ. Có hai lý do về
tổ chức và kỹ thuật đối với sự phát triển cơ sở dữ liệu phân tán đó là: Cơ sở dữ liệu
phân tán đƣợc xây dựng để khắc phục các thiếu sót của cơ sở dữ liệu tập trung và nó
phù hợp hơn trong cấu trúc phân quyền của nhiều tổ chức. Kỹ thuật cơ sở dữ liệu
phân tán đƣợc mở rộng và phát triển từ kỹ thuật của cơ sở dữ liệu truyền thống.
Trong môi trƣờng mới này, một số vấn đề kỹ thuật đòi hỏi các giải pháp khác, và
một số giải pháp hoàn toàn mới. - 15 -
Số hóa bởi Trung tâm Học liệu

CHƢƠNG 2.
THIẾT KẾ CƠ SỞ DỮ LIỆU PHÂN TÁN
2.1. Các vấn đề về phân mảnh dữ liệu
Phần lớn các hệ cơ sở dữ liệu phân tán đƣợc thiết kế theo hƣớng từ trên xuống
(TopDown). Thiết kế phân mảnh dữ liệu là công việc đầu tiên phải thực hiện. Mục
đích của việc phân mảnh dữ liệu là tạo ra các đơn vị cấp phát logic, sao cho chi phí

cập dữ liệu đến các mảnh và tăng chi phí kết nối các mảnh
5. Việc kiểm soát ngữ nghĩa, đặc biệt là vấn đề kiểm tra tính toàn vẹn sẽ khó
khăn hơn
2.1.2. Các kiểu phân mảnh
Các quan hệ cơ sở dữ liệu thƣờng đƣợc biểu diễn dƣới dạng bảng. Việc phân
mảnh một quan hệ thành nhiều quan hệ con khác nhau theo các cách khác nhau, sẽ
có các cách phân mảnh tƣơng ứng. Có hai kiểu phân mảnh tƣơng ứng với việc chia
quan hệ theo chiều dọc và chia quan hệ theo chiều ngang .
Phân mảnh theo chiều dọc: Các quan hệ đƣợc chia theo chiều dọc. Nghĩa là
thiết lập một quan hệ mới chỉ có một số thuộc tính từ quan hệ gốc. Thực chất đây là
phép chiếu trên tập con các thuộc tính của quan hệ.
2.1.3. Mức độ phân mảnh
Phân mảnh cơ sở dữ liệu đến mức độ nào là đủ, không làm ảnh hƣởng đến
hiệu năng của việc thực hiện truy vấn. Mức độ phân mảnh có thể là phân mảnh một
quan hệ chƣa đƣợc phân mảnh, có thể phân mản các quan hệ đã đƣợc phân mảnh.
Có thể phân mảnh theo chiều dọc (theo từng thuộc tính) hoặc theo chiều ngang
(theo từng bộ trong quan hệ).
Một mức độ ứng phân mảnh thích hợp sao cho tránh đƣợc các hạn chế khi
phân mảnh chỉ đƣợc định nghĩa ứng với các ứng dụng sẽ chạy trên cơ sở dữ liệu.

- 17 -
Số hóa bởi Trung tâm Học liệu

2.1.4. Các quy tắc phân mảnh
Các nguyên tắc để đảm bảo cơ sở dữ liệu khi phân mảnh sẽ đảm bảo tính
không thay đổi về ngữ nghĩa. Dƣới đây là ba qui tắc phải tuân thủ khi phân mảnh cơ
sở dữ liệu quan hệ.
1. Tính đầy đủ: Quan hệ R đƣợc phân rã thành các mảnh R1, R2…Rn, thì mỗi
mục dữ liệu có trong quan hệ R sẽ đƣợc chứa trong ít nhất một mảnh Ri (i=1, ,n).
Quy tắc này đảm bảo cho các mục dữ liệu trong R đƣợc ánh xạ hoàn toàn vào các