Đồ án mô hình thiết kế csdl quan hệ mức logic dựa trên phương pháp “blanpre” và ứng dụng
- 72 trang
- file .pdf
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
-------------------------------
ĐỒ ÁN TỐT NGHIỆP
NGÀNH : CÔNG NGHỆ THÔNG TIN
Sinh viên : Bùi Đình Tuấn Đạt
Giảng viên hướng dẫn: TS. Lê Văn Phùng
HẢI PHÒNG – 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
-----------------------------------
MÔ HÌNH THIẾT KẾ CSDL QUAN HỆ MỨC LOGIC
DỰA TRÊN PHƯƠNG PHÁP “BLANPRE”
VÀ ỨNG DỤNG
ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
NGÀNH: CÔNG NGHỆ THÔNG TIN
Sinh viên : Bùi Đình Tuấn Đạt
Giảng viên hướng dẫn: TS. Lê Văn Phùng
HẢI PHÒNG – 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
--------------------------------------
NHIỆM VỤ ĐỀ TÀI TỐT NGHIỆP
Sinh viên: Bùi Đình Tuấn Đạt Mã SV: 1612111010
Lớp : CT2001C
Ngành : Công nghệ thông tin
Tên đề tài: Mô hình thiết kế CSDL quan hệ mức logic dựa trên phương pháp
“Blanpre” và ứng dụng
NHIỆM VỤ ĐỀ TÀI
1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp
- Tìm hiểu về Mô hình thiết kế CSDL quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre”
- Xây dựng CSDL áp dụng phương pháp “Blanpre” và ứng dụng quản lý các cung
đường bộ trên địa bàn TP. Hải Phòng
2. Các tài liệu, số liệu cần thiết
- Tài liệu tham khảo về CSDL
- Tài liệu tham khảo về phương pháp phân tích và thiết kế hệ thống thông tin
- Tài liệu tham khảo về quản lý thông tin các cung đường
3. Địa điểm thực tập tốt nghiệp
- Công ty Cổ Phần Thiết Bị Điện, Điện Tử - Bách Khoa
CÁN BỘ HƯỚNG DẪN ĐỀ TÀI TỐT NGHIỆP
Họ và tên : Lê Văn Phùng
Học hàm, học vị : Tiến sĩ
Cơ quan công tác : Viện Công nghệ Thông tin,
Viện Hàn lâm Khoa học và Công nghệ Việt Nam.
Nội dung hướng dẫn:
- Tìm hiểu về Mô hình thiết kế cơ sở dữ liệu quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre” để thiết kế cơ sở dữ liệu quan hệ cho một
ứng dụng.
- Xây dựng cơ sở dữ liệu theo phương pháp “Blanpre” và viết chương trình thử
nghiệm ứng dụng quản lý các cung đường bộ trên địa bàn TP. Hải Phòng.
Đề tài tốt nghiệp được giao ngày 18 tháng 10 năm 2021
Yêu cầu phải hoàn thành xong trước ngày 30 tháng 12 năm 2021
Đã nhận nhiệm vụ ĐTTN Đã giao nhiệm vụ ĐTTN
Sinh viên Giảng viên hướng dẫn
TS.Lê Văn Phùng
Hải Phòng, ngày tháng năm 2021
TRƯỞNG KHOA
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN TỐT NGHIỆP
Họ và tên giảng viên: Lê Văn Phùng
Đơn vị công tác: Viện Công nghệ Thông tin,
Viện Hàn lâm Khoa học và Công nghệ Việt Nam.
Họ và tên sinh viên : Bùi Đình Tuấn Đạt
Ngành: Công nghệ Thông tin
Nội dung hướng dẫn:
- Tìm hiểu về Mô hình thiết kế cơ sở dữ liệu quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre” để thiết kế cơ sở dữ liệu quan hệ cho
một ứng dụng.
- Xây dựng cơ sở dữ liệu theo phương pháp “Blanpre” và viết chương trình
thử nghiệm ứng dụng quản lý các cung đường bộ trên địa bàn TP. Hải
Phòng.
1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp
- Học sinh có tinh thần cố gắng cao trong quá trình làm đồ án tốt nghiệp, từ sưu tập
tài liệu, tìm hiểu tài liệu, tổng hợp tư liệu, phân tích số liệu thực tế tại nơi ứng
dụng.
- Đảm bảo đúng tiến độ thực hiện đồ án theo quy định của nhà trường và hướng
dẫn của giáo viên hướng dẫn.
2. Đánh giá chất lượng của đồ án/khóa luận (so với nội dung yêu cầu đó đề ra trong
nhiệm vụ Đ.T. T.N trên các mặt lý luận, thực tiễn, tính toán số liệu…)
- Đồ án tốt nghiệp của sinh viên đã đáp ứng đầy đủ những vấn đề cốt yếu nhất của
nội dung đề tài theo yêu cầu đề cương đồ án tốt nghiệp đã đặt ra.
- Phần lý thuyết đã cơ bản đáp ứng được yêu cầu tổng quan kiến thức chung và
tìm hiểu sâu về kiến thức hẹp để áp dụng thực tế.
- Phần thực hành thử nghiệm lập trình tuy còn đơn giản nhưng đã thể hiện được
khả năng vận dụng những kiến thức học được vào giải quyết bài toán thực tế.
3. Ý kiến của giảng viên hướng dẫn tốt nghiệp
Đạt V Không đạt Điểm:……………...
Hải Phòng, ngày 22 tháng 12 năm 2021
Giảng viên hướng dẫn
TS. Lê Văn Phùng
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN CHẤM PHẢN BIỆN
Họ và tên giảng viên:
……………………………………………………………………
Đơn vị công tác:
………………………………………………………………………..
Họ và tên sinh viên: ……………………………… Ngành:
……………………………
Đề tài tốt
nghiệp:………………………………………………………………………..
………………………………………………………………………………………
…..
1. Phần nhận xét của giảng viên chấm phản biện
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
2. Những mặt còn hạn chế
.............................................................................................................................
....
vi
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
3. Ý kiến của giảng viên chấm phản biện
Đạt Không đạt Điểm:……………...
Hải Phòng, ngày … thỏng … năm 2021
Giảng viên chấm phản biện
vii
LỜI CẢM ƠN
Em xin cảm ơn chân thành đến toàn thể thầy cô trong trường Đại Học Quản
lý và Công nghệ nói chung và các thầy cô trong khoa Công nghệ thông tin nói
riêng, những người đã tận tình hướng dẫn, dạy dỗ và trang bị cho em những kiến
thức bổ ích trong năm vừa qua.
Em xin chân thành gửi lời cảm ơn sâu sắc đến các thầy cô khoa công nghệ
thông tin đặc biệt là thầy giáo Ts Lê Văn Phùng, người đã tận tình hướng dẫn, trực
tiếp chỉ bảo và tạo mọi điều kiện giúp đỡ em trong suốt quá trình làm đồ án tốt
nghiệp.
Sau cùng em xin gửi lời cảm ơn chân thành tới những ngƣời bạn đã động
viên, cổ vũ và đóng góp ý kiến trong quá trình học tập, nghiên cứu cũng như quá
trình làm đồ án tốt nghiệp.
Bên cạnh đó, do còn nhiều hạn chế về kiến thức và kinh nghiệm nên trong
đồ án không tránh khỏi những thiếu sót, kính mong quý thầy cô, anh chị, bạn bè chỉ
bảo thêm.
Em xin chân thành cảm ơn!
Hải Phòng, ngày tháng năm 2021
Sinh viên
Bùi Đình Tuấn Đạt
1
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................................ 1
CHƯƠNG 1 ........................................................................................................................... 6
TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ ......................................... 6
1.1. Cơ sở dữ liệu ..........................................................................................................................6
1.1.1. Các khái niệm chung ................................................................................6
1.1.2. Mô hình dữ liệu và mô hình dữ liệu quan hệ ...........................................6
1.2. Phụ thuộc hàm và thiết kế logic cơ sở dữ liệu quan hệ ......................................................8
1.2.1. Khái niệm về phụ thuộc hàm ...................................................................8
1.2.2. Các thuật toán xác định bao đóng và khóa trong sơ đồ quan hệ s=
............................................................................................................................ 9
1.2.3. Các dạng chuẩn và các thuật toán liêu quan ...........................................12
1.2.4. Chiến lược thiết kế logic cơ sở dữ liệu quan hệ .....................................14
CHƯƠNG 2 ......................................................................................................................... 20
MÔ HÌNH THIẾT KẾ CSDL QUAN HỆ MỨC LOGIC DỰA TRÊN PHƯƠNG PHÁP
BLANPRE ........................................................................................................................... 20
2.1. Ý nghĩa của thiết kế CSDL mức logic ...............................................................................20
2.2. Khuôn cảnh chung các bước thiết kế CSDL mức logic ...................................................20
2.3. Xây dựng mô hình khái niệm dữ liệu bằng phương pháp Blanpre ................................22
2.3.1. Ý tưởng của mô hình ..............................................................................22
2.3.2. Quy trình thiết kế .................................................................................... 22
2.3.3. Ví dụ .......................................................................................................23
2.4. Chuyển mô hình khái niệm dữ liệu sang mô hình dữ liệu mức logic .............................31
2.4.1. Kỹ thuật chuyển mô hình khái niệm dữ liệu về hệ lược đồ quan hệ ......31
2.4.2. Kỹ thuật chuẩn hóa .................................................................................31
2.4.3. Kỹ thuật chuyển từ hệ lược đồ quan hệ sang sơ đồ E_R (ERD - mô hình
dữ liệu mức logic) ............................................................................................. 33
CHƯƠNG 3 ......................................................................................................................... 35
ỨNG DỤNG THIẾT KẾ CSDL VỀ THÔNG TIN CÁC CUNG ĐƯỜNG BỘ TRÊN ĐỊA
BÀN TP. HẢI PHÒNG ....................................................................................................... 35
3.1. Bài toán quản lý thông tin các cung đường bộ trên địa bàn TP. Hải Phòng .................35
3.2. Những phần mềm hỗ trợ ....................................................................................................35
2
3.3. Thuật toán sử dụng và xác định dữ liệu đầu vào .............................................................36
3.3.1. Thuật toán sử dụng .................................................................................36
3.3.2. Dữ liệu đầu vào....................................................................................... 36
3.4. Nội dung và kết quả thử nghiệm........................................................................................38
3.4.1. Nội dung thiết kế cơ sở dữ liệu các cung đường TP. Hải Phòng ..........38
3.4.2. Giới thiệu chương trình ..........................................................................55
KẾT LUẬN .......................................................................................................................... 62
1. Kết quả đạt được của đồ án ....................................................................................................62
2. Những hạn chế........................................................................................................................62
3. Hướng phát triển.....................................................................................................................62
TÀI LIỆU THAM KHẢO ................................................................................................... 63
3
DANH SÁCH HÌNH VẼ
Hình 1.1. Phân lớp các dạng chuẩn ......................................................................14
Hình 2.1. Sơ đồ khuôn cảnh chung các bước thiết kế CSDL mức logic [3] .............22
Hình 2.2. Mô hình khái niệm dữ liệu ........................................................................30
Hình 3.1. Mô hình khái niệm dữ liệu bài toán quản lý cung đường giao thông .......47
Hình 3.2. Mô hình Thực thể- Mối quan hệ (Mô hình E_R) bài toán quản lý cung
đường giao thông: .....................................................................................................50
Hình 3.3. Giao diện form đăng nhập ........................................................................57
Hình 3.4. Giao diện form quản lý thông tin cung đường ..........................................58
Hình 3.5. Giao diện form quản lý thông tin bảo trì ..................................................59
Hình 3.6. Giao diện form quản lý thông tin người dùng...........................................60
Hình 3.7. Giao diện form tìm kiếm thông tin cung đường ........................................60
4
DANH SÁCH BẢNG
Bảng 1.1. Quan hệ THISINH ...................................................................................... 8
Bảng 1.2. Quan hệ trình độ ngoại ngữ......................................................................12
Bảng 2.1. Ma trận Blanpre ....................................................................................... 24
Bảng 2.2. Ma trận Blanpre rút gọn ...........................................................................25
Bảng 2.3. Ma trận phụ thuộc hàm Blanpre............................................................... 27
Bảng 3.1. Cấu trúc bảng QUAN ...............................................................................52
Bảng 3.2. Cấu trúc bảng DUONG ............................................................................52
Bảng 3.3. Cấu trúc bảng LOAIMADUONG ............................................................. 53
Bảng 3.4. Cấu trúc bảng KIEUDUONG ...................................................................53
Bảng 3.5. Cấu trúc bảng TOCHUCGIAOTHONG ...................................................53
Bảng 3.6. Cấu trúc bảng MUCDOHUHONG .......................................................... 54
Bảng 3.7. Cấu trúc bảng LOAIBAOTRI ...................................................................54
Bảng 3.8. Cấu trúc bảng DONVITHICONG ............................................................ 54
Bảng 3.9. Cấu trúc bảng THONGTINBAOTRI......................................................... 55
5
CHƯƠNG 1
TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ
1.1. Cơ sở dữ liệu
1.1.1. Các khái niệm chung
Dữ liệu bao gồm số, kí tự, văn bản, hình ảnh, đồ họa, âm thanh, đoạn phim,...
có một giá trị nào đó đối với người sử dụng chúng và được lưu trữ, xử lý trong máy
tính [5].
Cơ sở dữ liệu được xác định như một bộ sưu tập các dữ liệu có liên quan
logic với nhau; nó được tổ chức sắp xếp theo một cách nào đó và được các hệ ứng
dụng của một đơn vị/cơ quan cụ thể nào đó sử dụng.
1.1.2. Mô hình dữ liệu và mô hình dữ liệu quan hệ
1.1.2.1. Mô hình dữ liệu
Mô hình dữ liệu là cách biểu diễu các cấu trúc dữ liệu cho một cơ sở dữ liệu
dưới dạng các khái niệm. Các cấu trúc dữ liệu bao gồm các đối tượng dữ liệu, mối
liên hệ giữa các dữ liệu, ngữ nghĩa của dữ liệu và các ràng buộc trên đối tượng dữ
liệu đó [5].
Có 3 loại mô hình cơ sở dữ liệu:
1. Mô hình cơ sở dữ liệu mức quan niệm
- Là mô hình mô tả dữ liệu của thế giới thực gắn với hoạt động nghiệp vụ
của tổ chức sử dụng nó.
- Mô tả các cấu trúc và mối liên hệ giữa các đơn vị thông tin cơ bản.
- Là phương tiện để giao tiếp với người sử dụng nhằm xác định đúng đắn và
đầy đủ các yêu cầu thông tin của hệ thống.
- Hoàn toàn độc lập với mọi hệ quản trị dữ liệu và cách thức sử dụng nó.
- Cung cấp các khái niệm gắn liền với cách cảm nhận dữ liệu của người sử
dụng. Nó tập trung vào bản chất logic của biểu diễn dữ liệu, quan tâm đến cái được
biểu diễn, chứ không quan tâm đến cách biểu diễn.
6
- Mô hình khái niệm cơ bản như mô hình E_R. Mô hình E_R dùng để mô tả
cấu trúc logic tổng thể (lược đồ) của một cơ sở dữ liệu bằng hình ảnh (đặc tả).
Người ta quan niệm thế giới thực bao gồm tập các E và R. Trong đó, E là “sự vật”/
“đối tượng” tức là thực thể trong thế giới thực và phải phân biệt được, còn R là mối
quan hệ (relationship) giữa một nhóm thực thể [6].
2. Mô hình cơ sở dữ liệu mức logic:
- Cung cấp khái niệm cho người sử dụng có thể được và không xa so với
cách tổ chức dữ liệu trong máy tính. Chúng che dấu một số chi tiết về việc lưu trữ
dữ liệu nhưng có thể cài đặt trực tiếp trên hệ thống máy tính. Mô hình dữ liệu logic
cho một hệ quản trị cơ sở dữ liệu:
- Mô tả các dữ liệu bằng cách sử dụng các ký hiệu tương ứng với mô hình dữ
liệu mà 1 hệ quản trị cơ sở dữ liệu xây dựng trên nó.
- Có 4 loại mô hình dữ liệu logic: mô hình dữ liệu phân cấp, mạng, quan hệ,
hướng đối tượng.
- Hiện nay, được tổ chức theo mô hình dữ liệu quan hệ là chủ yếu.
3. Mô hình cơ sở dữ liệu mức vật lý:
- Cung cấp các khái niệm mô tả chi tiết về việc các dữ liệu được lưu trữ trong
máy như thế nào.
1.1.2.2. Mô hình dữ liệu quan hệ
Mô hình dữ liệu quan hệ được Cold đề xuất năm 1970. Nó đã tạo ra một
cuộc cách mạng mới trong lĩnh vực cơ sở dữ liệu và nhanh chóng thay thế các mô
hình dữ liệu trước đó [5].
Mô hình dữ liệu quan hệ tương đối đơn giản và dễ hiểu. Mô hình dữ liệu
quan hệ là mô hình dữ liệu mà cốt lõi của nó là cơ sở dữ liệu quan hệ. Một cơ sở dữ
liệu quan hệ là một tập của một hoặc nhiều quan hệ, trong đó mỗi một quan hệ là
một bảng. Mô hình quan hệ sử dụng một tập các bảng để biểu diễn cả dữ liệu và các
mối liên hệ giữa những dữ liệu này. Bảng có n cột và mỗi cột có một tên duy nhất.
Những cơ sở dữ liệu quan hệ thông dụng nhất đều có thể sử dụng ngôn ngữ
SQL (Structured Query Language)
7
1.2. Phụ thuộc hàm và thiết kế logic cơ sở dữ liệu quan hệ
1.2.1. Khái niệm về phụ thuộc hàm
Khái niệm về phụ thuộc hàm trong một quan hệ là rất quan trọng trong việc
thiết kế mô hình dữ liệu. Năm 1970, E.F Cold đã mô tả phụ thuộc hàm trong mô
hình dữ liệu quan hệ, nhằm giải quyết việc phân rã không mất thông tin [1,5].
Cho R = {a1, a2,....., an} là tập thuộc tính, r = {h1, h2 ,..., hm} là một quan hệ
trên R, và A,B R (A, B là tập cột hay tập thuộc tính). Khi đó ta nói A xác định
hàm cho B hay B phụ thuộc hàm vào A trong r ( ký pháp A ⎯⎯ → B) nếu: ( h , h
f
r i j
r) (( a A) ( hi (a) = hj (b)) ( b B) ( hi(b) = hj(b))) nghĩa là đối số trùng
nhau thì hàm có cùng giá trị. Đặt Fr= {(A,B) : A, B R, A ⎯⎯ → B}. Lúc đó F
f
r r
được gọi là họ đầy đủ các phụ thuộc hàm của r.
Nhận xét :
Ta có thể thấy rằng B mà phụ thuộc hàm vào A, nếu hai dòng bất kì mà các
giá trị của tập thuộc tính A mà bằng nhau từng cặp một, thì kéo theo các giá trị trên
tập thuộc tính B cũng phải bằng nhau từng cặp một.
Ví dụ: Xét quan hệ [4]:
Bảng 1.1. Quan hệ THISINH
SBD Hoten Diachi Tinh Khuvuc
PD711001 Nguyễn Thái Bình 12 Bản Nhàn Lạng Sơn 0
PD711002 Trần Nam Ninh 3 Kim mã Hà Nội 3
PD711003 Lê Thanh Hoa 53 Hai Bà Trưng Hà Nội 3
PD711004 Vũ Thúy Hồng 89 Đồng Đăng Lạng Sơn 0
PD711005 Phạm Như Thúy 40 Trần Hưng Đạo Hải Dương 2
Trong quan hệ THISINH, dựa vào định nghĩa phụ thuộc hàm của quan hệ ta
có: {tinh} ->{khuvuc}; {sbd}-> {hoten, diachi, tinh, khuvuc}
Ý nghĩa: Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ
liệu) xảy ra tự nhiên nhất giữa các tập thuộc tính.
8
1.2.2. Các thuật toán xác định bao đóng và khóa trong sơ đồ quan hệ s=
1. Một số thuật toán liên quan đến bao đóng
Một vấn đề thường xuyên xảy ra đối với một sơ đồ quan hệ cho trước (s
=), và một phụ thuộc hàm A-> B, chúng ta muốn biết A-> B có là phần tử
của F+ hay không. Để trả lời câu hỏi này chúng ta cần tính bao đóng F+ của tập các
phụ thuộc hàm F.
Tuy nhiên tính F+ trong trường hợp tổng quát là rất khác nhau và tốn kém
thời gian vì các tập phụ thuộc hàm F+ là rất lớn cho dù F có thể là nhỏ. Chẳng hạn,
F ={A-> B1, A-> B2, ...A ->Bn}, khi đó F+ bao gồm cả những phụ thuộc hàm A->Y
với Y {B1 B2 .... Bn}, như vậy ta sẽ có 2n tập con Y. Trong khi đó việc tính
bao đóng của tập thuộc tính A lại không khó. Theo kết quả đã trình bay ở trên thì
việc kiểm tra A->B F+ sẽ được thế bởi tính A+ [1,5,6].
Thuật toán Tính bao đóng của một tập các thuộc tính đối với tập các phụ thuộc
hàm trên sơ đồ quan hệ
Vào: s = là một sơ đồ quan hệ
Trong đó:
R= (a1, a2,...an) là tập hữu hạn các thuộc tính.
F là tập các phụ thuộc hàm và A R
Ra: A+ là bao đóng của A đối với F.
Nhớ rằng A+ = {a: A->{a} F+}.
A->B F+ nếu và chỉ nếu B A+.
Phương pháp :
Lần lượt tính các tập thuộc tính A0, A1 như sau:
1.A0 = A
2.Ai = Ai-1 {a} nếu (C->D) F, {a} D và C Ai-1
3.Rõ ràng A = A0 A1 ... Ai và R hữu hạn nên tồn tại i sao cho:
Ai = Ai+1. Khi ấy thuật toán dừng và Ai chính là A+
Ví dụ:
9
Xét sơ đồ quan hệ s=
Trong đó :
{c} → {t}
{h,r} → {c}
{h,t} → {r}
{c,s} → {g}
F= {h,s} → {r} R = {c, t, h, r, s, g}
Tính {h, r}+ ?
A0 = {h, r}
A1 = {h, r, c} do {h, r} -> {c} F
A2 = {h, r, c, t} do {c}-> {t} F
A3 = {h, r, c, t} = A2
Vậy {h, r}+ = {h, r, c, t}
2. Một số thuật toán liên quan đến khóa
Khi giải quyết các bài toán thông tin quản lý, người ta thường sử dụng các hệ
quản trị cơ sở dữ liệu mà trong đó chứa cơ sở dữ liệu quan hệ. Các phép xử lý đối
với bài bài toán này thường là tìm kiếm bản ghi sau đó thêm bản ghi mới, thay đổi
nội dung bản ghi hoặc xóa bản ghi. Trong các thao tác trên, việc tìm kiếm bản ghi là
rất quan trọng. Muốn tìm được bản ghi trong file dữ liệu thì chúng ta phải xây dựng
khóa của file dữ liệu đó. Việc tìm khóa ở đây chính là tìm khóa tối thiểu.
Thuật toán tìm khóa tối thiểu cho một sơ đồ quan hệ [3]:
Input: Sơ đồ quan hệ s =
Trong đó : F là tập các phụ thuộc hàm
R = {a1,...an} là tập các thuộc tính
Output: K là tối thiểu của s
Phương pháp:
Tìm liên tiếp các tập thuộc tính K0, K1,...Kn như sau:
K0 = R = {a1, ... an}
10
K i−1 Ki-1 nếu Ki-1 – {ai} R F+
Ki-1 – {ai} nếu ngược lại
K − {a i }
Ki = i−1
K = Kn là khóa tối thiểu
Ta có thể dùng công thức tương đương:
Nếu {Ki-1 - ai}+ = R
Nếu ngược lại.
Nhận xét:
- Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên chúng ta có thể
tìm được một khóa tối thiểu khác.
- Nếu như đã biết A là một khóa nào đó thì có thể đặt K0 = A, ta vẫn tìm ra
được khóa tối thiểu và thời giàn tìm nhanh hơn.
Ví dụ : Giả sử s = là một lược đồ quan hệ trong đó:
R = {a, b, c, d}
F = {{a,b} {d}, {c} }
Tìm khóa tối thiểu của sơ đồ quan hệ.
Áp dụng thuật toán trên ta có:
+ K0 = R = {a, b, c, d}
+ Tính K1
Xét K1 = K0 – {a} = {b, c, d}
{b, c, d}+ = {b, c, d} R
Vậy K1 = {a, b, c, d}. (K1 = K0)
+ Tính K2
Xét K2 = K1 – {b} = {a, c,d}
{a, c,d}+ = {a, b, c, d} = R
Vậy K2 = {a, c, d}
+ Tính K3
Xét K3 = K2 – {c} = {a,d}
{a,d}+ = {a, d} R
11
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
-------------------------------
ĐỒ ÁN TỐT NGHIỆP
NGÀNH : CÔNG NGHỆ THÔNG TIN
Sinh viên : Bùi Đình Tuấn Đạt
Giảng viên hướng dẫn: TS. Lê Văn Phùng
HẢI PHÒNG – 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
-----------------------------------
MÔ HÌNH THIẾT KẾ CSDL QUAN HỆ MỨC LOGIC
DỰA TRÊN PHƯƠNG PHÁP “BLANPRE”
VÀ ỨNG DỤNG
ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
NGÀNH: CÔNG NGHỆ THÔNG TIN
Sinh viên : Bùi Đình Tuấn Đạt
Giảng viên hướng dẫn: TS. Lê Văn Phùng
HẢI PHÒNG – 2021
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC QUẢN LÝ VÀ CÔNG NGHỆ HẢI PHÒNG
--------------------------------------
NHIỆM VỤ ĐỀ TÀI TỐT NGHIỆP
Sinh viên: Bùi Đình Tuấn Đạt Mã SV: 1612111010
Lớp : CT2001C
Ngành : Công nghệ thông tin
Tên đề tài: Mô hình thiết kế CSDL quan hệ mức logic dựa trên phương pháp
“Blanpre” và ứng dụng
NHIỆM VỤ ĐỀ TÀI
1. Nội dung và các yêu cầu cần giải quyết trong nhiệm vụ đề tài tốt nghiệp
- Tìm hiểu về Mô hình thiết kế CSDL quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre”
- Xây dựng CSDL áp dụng phương pháp “Blanpre” và ứng dụng quản lý các cung
đường bộ trên địa bàn TP. Hải Phòng
2. Các tài liệu, số liệu cần thiết
- Tài liệu tham khảo về CSDL
- Tài liệu tham khảo về phương pháp phân tích và thiết kế hệ thống thông tin
- Tài liệu tham khảo về quản lý thông tin các cung đường
3. Địa điểm thực tập tốt nghiệp
- Công ty Cổ Phần Thiết Bị Điện, Điện Tử - Bách Khoa
CÁN BỘ HƯỚNG DẪN ĐỀ TÀI TỐT NGHIỆP
Họ và tên : Lê Văn Phùng
Học hàm, học vị : Tiến sĩ
Cơ quan công tác : Viện Công nghệ Thông tin,
Viện Hàn lâm Khoa học và Công nghệ Việt Nam.
Nội dung hướng dẫn:
- Tìm hiểu về Mô hình thiết kế cơ sở dữ liệu quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre” để thiết kế cơ sở dữ liệu quan hệ cho một
ứng dụng.
- Xây dựng cơ sở dữ liệu theo phương pháp “Blanpre” và viết chương trình thử
nghiệm ứng dụng quản lý các cung đường bộ trên địa bàn TP. Hải Phòng.
Đề tài tốt nghiệp được giao ngày 18 tháng 10 năm 2021
Yêu cầu phải hoàn thành xong trước ngày 30 tháng 12 năm 2021
Đã nhận nhiệm vụ ĐTTN Đã giao nhiệm vụ ĐTTN
Sinh viên Giảng viên hướng dẫn
TS.Lê Văn Phùng
Hải Phòng, ngày tháng năm 2021
TRƯỞNG KHOA
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN TỐT NGHIỆP
Họ và tên giảng viên: Lê Văn Phùng
Đơn vị công tác: Viện Công nghệ Thông tin,
Viện Hàn lâm Khoa học và Công nghệ Việt Nam.
Họ và tên sinh viên : Bùi Đình Tuấn Đạt
Ngành: Công nghệ Thông tin
Nội dung hướng dẫn:
- Tìm hiểu về Mô hình thiết kế cơ sở dữ liệu quan hệ mức logic
- Tìm hiểu về phương pháp “Blanpre” để thiết kế cơ sở dữ liệu quan hệ cho
một ứng dụng.
- Xây dựng cơ sở dữ liệu theo phương pháp “Blanpre” và viết chương trình
thử nghiệm ứng dụng quản lý các cung đường bộ trên địa bàn TP. Hải
Phòng.
1. Tinh thần thái độ của sinh viên trong quá trình làm đề tài tốt nghiệp
- Học sinh có tinh thần cố gắng cao trong quá trình làm đồ án tốt nghiệp, từ sưu tập
tài liệu, tìm hiểu tài liệu, tổng hợp tư liệu, phân tích số liệu thực tế tại nơi ứng
dụng.
- Đảm bảo đúng tiến độ thực hiện đồ án theo quy định của nhà trường và hướng
dẫn của giáo viên hướng dẫn.
2. Đánh giá chất lượng của đồ án/khóa luận (so với nội dung yêu cầu đó đề ra trong
nhiệm vụ Đ.T. T.N trên các mặt lý luận, thực tiễn, tính toán số liệu…)
- Đồ án tốt nghiệp của sinh viên đã đáp ứng đầy đủ những vấn đề cốt yếu nhất của
nội dung đề tài theo yêu cầu đề cương đồ án tốt nghiệp đã đặt ra.
- Phần lý thuyết đã cơ bản đáp ứng được yêu cầu tổng quan kiến thức chung và
tìm hiểu sâu về kiến thức hẹp để áp dụng thực tế.
- Phần thực hành thử nghiệm lập trình tuy còn đơn giản nhưng đã thể hiện được
khả năng vận dụng những kiến thức học được vào giải quyết bài toán thực tế.
3. Ý kiến của giảng viên hướng dẫn tốt nghiệp
Đạt V Không đạt Điểm:……………...
Hải Phòng, ngày 22 tháng 12 năm 2021
Giảng viên hướng dẫn
TS. Lê Văn Phùng
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
PHIẾU NHẬN XÉT CỦA GIẢNG VIÊN CHẤM PHẢN BIỆN
Họ và tên giảng viên:
……………………………………………………………………
Đơn vị công tác:
………………………………………………………………………..
Họ và tên sinh viên: ……………………………… Ngành:
……………………………
Đề tài tốt
nghiệp:………………………………………………………………………..
………………………………………………………………………………………
…..
1. Phần nhận xét của giảng viên chấm phản biện
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
2. Những mặt còn hạn chế
.............................................................................................................................
....
vi
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
.............................................................................................................................
....
3. Ý kiến của giảng viên chấm phản biện
Đạt Không đạt Điểm:……………...
Hải Phòng, ngày … thỏng … năm 2021
Giảng viên chấm phản biện
vii
LỜI CẢM ƠN
Em xin cảm ơn chân thành đến toàn thể thầy cô trong trường Đại Học Quản
lý và Công nghệ nói chung và các thầy cô trong khoa Công nghệ thông tin nói
riêng, những người đã tận tình hướng dẫn, dạy dỗ và trang bị cho em những kiến
thức bổ ích trong năm vừa qua.
Em xin chân thành gửi lời cảm ơn sâu sắc đến các thầy cô khoa công nghệ
thông tin đặc biệt là thầy giáo Ts Lê Văn Phùng, người đã tận tình hướng dẫn, trực
tiếp chỉ bảo và tạo mọi điều kiện giúp đỡ em trong suốt quá trình làm đồ án tốt
nghiệp.
Sau cùng em xin gửi lời cảm ơn chân thành tới những ngƣời bạn đã động
viên, cổ vũ và đóng góp ý kiến trong quá trình học tập, nghiên cứu cũng như quá
trình làm đồ án tốt nghiệp.
Bên cạnh đó, do còn nhiều hạn chế về kiến thức và kinh nghiệm nên trong
đồ án không tránh khỏi những thiếu sót, kính mong quý thầy cô, anh chị, bạn bè chỉ
bảo thêm.
Em xin chân thành cảm ơn!
Hải Phòng, ngày tháng năm 2021
Sinh viên
Bùi Đình Tuấn Đạt
1
MỤC LỤC
LỜI CẢM ƠN ........................................................................................................................ 1
CHƯƠNG 1 ........................................................................................................................... 6
TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ ......................................... 6
1.1. Cơ sở dữ liệu ..........................................................................................................................6
1.1.1. Các khái niệm chung ................................................................................6
1.1.2. Mô hình dữ liệu và mô hình dữ liệu quan hệ ...........................................6
1.2. Phụ thuộc hàm và thiết kế logic cơ sở dữ liệu quan hệ ......................................................8
1.2.1. Khái niệm về phụ thuộc hàm ...................................................................8
1.2.2. Các thuật toán xác định bao đóng và khóa trong sơ đồ quan hệ s=
............................................................................................................................ 9
1.2.3. Các dạng chuẩn và các thuật toán liêu quan ...........................................12
1.2.4. Chiến lược thiết kế logic cơ sở dữ liệu quan hệ .....................................14
CHƯƠNG 2 ......................................................................................................................... 20
MÔ HÌNH THIẾT KẾ CSDL QUAN HỆ MỨC LOGIC DỰA TRÊN PHƯƠNG PHÁP
BLANPRE ........................................................................................................................... 20
2.1. Ý nghĩa của thiết kế CSDL mức logic ...............................................................................20
2.2. Khuôn cảnh chung các bước thiết kế CSDL mức logic ...................................................20
2.3. Xây dựng mô hình khái niệm dữ liệu bằng phương pháp Blanpre ................................22
2.3.1. Ý tưởng của mô hình ..............................................................................22
2.3.2. Quy trình thiết kế .................................................................................... 22
2.3.3. Ví dụ .......................................................................................................23
2.4. Chuyển mô hình khái niệm dữ liệu sang mô hình dữ liệu mức logic .............................31
2.4.1. Kỹ thuật chuyển mô hình khái niệm dữ liệu về hệ lược đồ quan hệ ......31
2.4.2. Kỹ thuật chuẩn hóa .................................................................................31
2.4.3. Kỹ thuật chuyển từ hệ lược đồ quan hệ sang sơ đồ E_R (ERD - mô hình
dữ liệu mức logic) ............................................................................................. 33
CHƯƠNG 3 ......................................................................................................................... 35
ỨNG DỤNG THIẾT KẾ CSDL VỀ THÔNG TIN CÁC CUNG ĐƯỜNG BỘ TRÊN ĐỊA
BÀN TP. HẢI PHÒNG ....................................................................................................... 35
3.1. Bài toán quản lý thông tin các cung đường bộ trên địa bàn TP. Hải Phòng .................35
3.2. Những phần mềm hỗ trợ ....................................................................................................35
2
3.3. Thuật toán sử dụng và xác định dữ liệu đầu vào .............................................................36
3.3.1. Thuật toán sử dụng .................................................................................36
3.3.2. Dữ liệu đầu vào....................................................................................... 36
3.4. Nội dung và kết quả thử nghiệm........................................................................................38
3.4.1. Nội dung thiết kế cơ sở dữ liệu các cung đường TP. Hải Phòng ..........38
3.4.2. Giới thiệu chương trình ..........................................................................55
KẾT LUẬN .......................................................................................................................... 62
1. Kết quả đạt được của đồ án ....................................................................................................62
2. Những hạn chế........................................................................................................................62
3. Hướng phát triển.....................................................................................................................62
TÀI LIỆU THAM KHẢO ................................................................................................... 63
3
DANH SÁCH HÌNH VẼ
Hình 1.1. Phân lớp các dạng chuẩn ......................................................................14
Hình 2.1. Sơ đồ khuôn cảnh chung các bước thiết kế CSDL mức logic [3] .............22
Hình 2.2. Mô hình khái niệm dữ liệu ........................................................................30
Hình 3.1. Mô hình khái niệm dữ liệu bài toán quản lý cung đường giao thông .......47
Hình 3.2. Mô hình Thực thể- Mối quan hệ (Mô hình E_R) bài toán quản lý cung
đường giao thông: .....................................................................................................50
Hình 3.3. Giao diện form đăng nhập ........................................................................57
Hình 3.4. Giao diện form quản lý thông tin cung đường ..........................................58
Hình 3.5. Giao diện form quản lý thông tin bảo trì ..................................................59
Hình 3.6. Giao diện form quản lý thông tin người dùng...........................................60
Hình 3.7. Giao diện form tìm kiếm thông tin cung đường ........................................60
4
DANH SÁCH BẢNG
Bảng 1.1. Quan hệ THISINH ...................................................................................... 8
Bảng 1.2. Quan hệ trình độ ngoại ngữ......................................................................12
Bảng 2.1. Ma trận Blanpre ....................................................................................... 24
Bảng 2.2. Ma trận Blanpre rút gọn ...........................................................................25
Bảng 2.3. Ma trận phụ thuộc hàm Blanpre............................................................... 27
Bảng 3.1. Cấu trúc bảng QUAN ...............................................................................52
Bảng 3.2. Cấu trúc bảng DUONG ............................................................................52
Bảng 3.3. Cấu trúc bảng LOAIMADUONG ............................................................. 53
Bảng 3.4. Cấu trúc bảng KIEUDUONG ...................................................................53
Bảng 3.5. Cấu trúc bảng TOCHUCGIAOTHONG ...................................................53
Bảng 3.6. Cấu trúc bảng MUCDOHUHONG .......................................................... 54
Bảng 3.7. Cấu trúc bảng LOAIBAOTRI ...................................................................54
Bảng 3.8. Cấu trúc bảng DONVITHICONG ............................................................ 54
Bảng 3.9. Cấu trúc bảng THONGTINBAOTRI......................................................... 55
5
CHƯƠNG 1
TỔNG QUAN VỀ LÝ THUYẾT CƠ SỞ DỮ LIỆU QUAN HỆ
1.1. Cơ sở dữ liệu
1.1.1. Các khái niệm chung
Dữ liệu bao gồm số, kí tự, văn bản, hình ảnh, đồ họa, âm thanh, đoạn phim,...
có một giá trị nào đó đối với người sử dụng chúng và được lưu trữ, xử lý trong máy
tính [5].
Cơ sở dữ liệu được xác định như một bộ sưu tập các dữ liệu có liên quan
logic với nhau; nó được tổ chức sắp xếp theo một cách nào đó và được các hệ ứng
dụng của một đơn vị/cơ quan cụ thể nào đó sử dụng.
1.1.2. Mô hình dữ liệu và mô hình dữ liệu quan hệ
1.1.2.1. Mô hình dữ liệu
Mô hình dữ liệu là cách biểu diễu các cấu trúc dữ liệu cho một cơ sở dữ liệu
dưới dạng các khái niệm. Các cấu trúc dữ liệu bao gồm các đối tượng dữ liệu, mối
liên hệ giữa các dữ liệu, ngữ nghĩa của dữ liệu và các ràng buộc trên đối tượng dữ
liệu đó [5].
Có 3 loại mô hình cơ sở dữ liệu:
1. Mô hình cơ sở dữ liệu mức quan niệm
- Là mô hình mô tả dữ liệu của thế giới thực gắn với hoạt động nghiệp vụ
của tổ chức sử dụng nó.
- Mô tả các cấu trúc và mối liên hệ giữa các đơn vị thông tin cơ bản.
- Là phương tiện để giao tiếp với người sử dụng nhằm xác định đúng đắn và
đầy đủ các yêu cầu thông tin của hệ thống.
- Hoàn toàn độc lập với mọi hệ quản trị dữ liệu và cách thức sử dụng nó.
- Cung cấp các khái niệm gắn liền với cách cảm nhận dữ liệu của người sử
dụng. Nó tập trung vào bản chất logic của biểu diễn dữ liệu, quan tâm đến cái được
biểu diễn, chứ không quan tâm đến cách biểu diễn.
6
- Mô hình khái niệm cơ bản như mô hình E_R. Mô hình E_R dùng để mô tả
cấu trúc logic tổng thể (lược đồ) của một cơ sở dữ liệu bằng hình ảnh (đặc tả).
Người ta quan niệm thế giới thực bao gồm tập các E và R. Trong đó, E là “sự vật”/
“đối tượng” tức là thực thể trong thế giới thực và phải phân biệt được, còn R là mối
quan hệ (relationship) giữa một nhóm thực thể [6].
2. Mô hình cơ sở dữ liệu mức logic:
- Cung cấp khái niệm cho người sử dụng có thể được và không xa so với
cách tổ chức dữ liệu trong máy tính. Chúng che dấu một số chi tiết về việc lưu trữ
dữ liệu nhưng có thể cài đặt trực tiếp trên hệ thống máy tính. Mô hình dữ liệu logic
cho một hệ quản trị cơ sở dữ liệu:
- Mô tả các dữ liệu bằng cách sử dụng các ký hiệu tương ứng với mô hình dữ
liệu mà 1 hệ quản trị cơ sở dữ liệu xây dựng trên nó.
- Có 4 loại mô hình dữ liệu logic: mô hình dữ liệu phân cấp, mạng, quan hệ,
hướng đối tượng.
- Hiện nay, được tổ chức theo mô hình dữ liệu quan hệ là chủ yếu.
3. Mô hình cơ sở dữ liệu mức vật lý:
- Cung cấp các khái niệm mô tả chi tiết về việc các dữ liệu được lưu trữ trong
máy như thế nào.
1.1.2.2. Mô hình dữ liệu quan hệ
Mô hình dữ liệu quan hệ được Cold đề xuất năm 1970. Nó đã tạo ra một
cuộc cách mạng mới trong lĩnh vực cơ sở dữ liệu và nhanh chóng thay thế các mô
hình dữ liệu trước đó [5].
Mô hình dữ liệu quan hệ tương đối đơn giản và dễ hiểu. Mô hình dữ liệu
quan hệ là mô hình dữ liệu mà cốt lõi của nó là cơ sở dữ liệu quan hệ. Một cơ sở dữ
liệu quan hệ là một tập của một hoặc nhiều quan hệ, trong đó mỗi một quan hệ là
một bảng. Mô hình quan hệ sử dụng một tập các bảng để biểu diễn cả dữ liệu và các
mối liên hệ giữa những dữ liệu này. Bảng có n cột và mỗi cột có một tên duy nhất.
Những cơ sở dữ liệu quan hệ thông dụng nhất đều có thể sử dụng ngôn ngữ
SQL (Structured Query Language)
7
1.2. Phụ thuộc hàm và thiết kế logic cơ sở dữ liệu quan hệ
1.2.1. Khái niệm về phụ thuộc hàm
Khái niệm về phụ thuộc hàm trong một quan hệ là rất quan trọng trong việc
thiết kế mô hình dữ liệu. Năm 1970, E.F Cold đã mô tả phụ thuộc hàm trong mô
hình dữ liệu quan hệ, nhằm giải quyết việc phân rã không mất thông tin [1,5].
Cho R = {a1, a2,....., an} là tập thuộc tính, r = {h1, h2 ,..., hm} là một quan hệ
trên R, và A,B R (A, B là tập cột hay tập thuộc tính). Khi đó ta nói A xác định
hàm cho B hay B phụ thuộc hàm vào A trong r ( ký pháp A ⎯⎯ → B) nếu: ( h , h
f
r i j
r) (( a A) ( hi (a) = hj (b)) ( b B) ( hi(b) = hj(b))) nghĩa là đối số trùng
nhau thì hàm có cùng giá trị. Đặt Fr= {(A,B) : A, B R, A ⎯⎯ → B}. Lúc đó F
f
r r
được gọi là họ đầy đủ các phụ thuộc hàm của r.
Nhận xét :
Ta có thể thấy rằng B mà phụ thuộc hàm vào A, nếu hai dòng bất kì mà các
giá trị của tập thuộc tính A mà bằng nhau từng cặp một, thì kéo theo các giá trị trên
tập thuộc tính B cũng phải bằng nhau từng cặp một.
Ví dụ: Xét quan hệ [4]:
Bảng 1.1. Quan hệ THISINH
SBD Hoten Diachi Tinh Khuvuc
PD711001 Nguyễn Thái Bình 12 Bản Nhàn Lạng Sơn 0
PD711002 Trần Nam Ninh 3 Kim mã Hà Nội 3
PD711003 Lê Thanh Hoa 53 Hai Bà Trưng Hà Nội 3
PD711004 Vũ Thúy Hồng 89 Đồng Đăng Lạng Sơn 0
PD711005 Phạm Như Thúy 40 Trần Hưng Đạo Hải Dương 2
Trong quan hệ THISINH, dựa vào định nghĩa phụ thuộc hàm của quan hệ ta
có: {tinh} ->{khuvuc}; {sbd}-> {hoten, diachi, tinh, khuvuc}
Ý nghĩa: Khái niệm phụ thuộc hàm miêu tả một loại ràng buộc (phụ thuộc dữ
liệu) xảy ra tự nhiên nhất giữa các tập thuộc tính.
8
1.2.2. Các thuật toán xác định bao đóng và khóa trong sơ đồ quan hệ s=
1. Một số thuật toán liên quan đến bao đóng
Một vấn đề thường xuyên xảy ra đối với một sơ đồ quan hệ cho trước (s
=
của F+ hay không. Để trả lời câu hỏi này chúng ta cần tính bao đóng F+ của tập các
phụ thuộc hàm F.
Tuy nhiên tính F+ trong trường hợp tổng quát là rất khác nhau và tốn kém
thời gian vì các tập phụ thuộc hàm F+ là rất lớn cho dù F có thể là nhỏ. Chẳng hạn,
F ={A-> B1, A-> B2, ...A ->Bn}, khi đó F+ bao gồm cả những phụ thuộc hàm A->Y
với Y {B1 B2 .... Bn}, như vậy ta sẽ có 2n tập con Y. Trong khi đó việc tính
bao đóng của tập thuộc tính A lại không khó. Theo kết quả đã trình bay ở trên thì
việc kiểm tra A->B F+ sẽ được thế bởi tính A+ [1,5,6].
Thuật toán Tính bao đóng của một tập các thuộc tính đối với tập các phụ thuộc
hàm trên sơ đồ quan hệ
Vào: s =
Trong đó:
R= (a1, a2,...an) là tập hữu hạn các thuộc tính.
F là tập các phụ thuộc hàm và A R
Ra: A+ là bao đóng của A đối với F.
Nhớ rằng A+ = {a: A->{a} F+}.
A->B F+ nếu và chỉ nếu B A+.
Phương pháp :
Lần lượt tính các tập thuộc tính A0, A1 như sau:
1.A0 = A
2.Ai = Ai-1 {a} nếu (C->D) F, {a} D và C Ai-1
3.Rõ ràng A = A0 A1 ... Ai và R hữu hạn nên tồn tại i sao cho:
Ai = Ai+1. Khi ấy thuật toán dừng và Ai chính là A+
Ví dụ:
9
Xét sơ đồ quan hệ s=
Trong đó :
{c} → {t}
{h,r} → {c}
{h,t} → {r}
{c,s} → {g}
F= {h,s} → {r} R = {c, t, h, r, s, g}
Tính {h, r}+ ?
A0 = {h, r}
A1 = {h, r, c} do {h, r} -> {c} F
A2 = {h, r, c, t} do {c}-> {t} F
A3 = {h, r, c, t} = A2
Vậy {h, r}+ = {h, r, c, t}
2. Một số thuật toán liên quan đến khóa
Khi giải quyết các bài toán thông tin quản lý, người ta thường sử dụng các hệ
quản trị cơ sở dữ liệu mà trong đó chứa cơ sở dữ liệu quan hệ. Các phép xử lý đối
với bài bài toán này thường là tìm kiếm bản ghi sau đó thêm bản ghi mới, thay đổi
nội dung bản ghi hoặc xóa bản ghi. Trong các thao tác trên, việc tìm kiếm bản ghi là
rất quan trọng. Muốn tìm được bản ghi trong file dữ liệu thì chúng ta phải xây dựng
khóa của file dữ liệu đó. Việc tìm khóa ở đây chính là tìm khóa tối thiểu.
Thuật toán tìm khóa tối thiểu cho một sơ đồ quan hệ [3]:
Input: Sơ đồ quan hệ s =
Trong đó : F là tập các phụ thuộc hàm
R = {a1,...an} là tập các thuộc tính
Output: K là tối thiểu của s
Phương pháp:
Tìm liên tiếp các tập thuộc tính K0, K1,...Kn như sau:
K0 = R = {a1, ... an}
10
K i−1 Ki-1 nếu Ki-1 – {ai} R F+
Ki-1 – {ai} nếu ngược lại
K − {a i }
Ki = i−1
K = Kn là khóa tối thiểu
Ta có thể dùng công thức tương đương:
Nếu {Ki-1 - ai}+ = R
Nếu ngược lại.
Nhận xét:
- Thay đổi thứ tự các thuộc tính của R bằng thuật toán trên chúng ta có thể
tìm được một khóa tối thiểu khác.
- Nếu như đã biết A là một khóa nào đó thì có thể đặt K0 = A, ta vẫn tìm ra
được khóa tối thiểu và thời giàn tìm nhanh hơn.
Ví dụ : Giả sử s =
R = {a, b, c, d}
F = {{a,b} {d}, {c} }
Tìm khóa tối thiểu của sơ đồ quan hệ.
Áp dụng thuật toán trên ta có:
+ K0 = R = {a, b, c, d}
+ Tính K1
Xét K1 = K0 – {a} = {b, c, d}
{b, c, d}+ = {b, c, d} R
Vậy K1 = {a, b, c, d}. (K1 = K0)
+ Tính K2
Xét K2 = K1 – {b} = {a, c,d}
{a, c,d}+ = {a, b, c, d} = R
Vậy K2 = {a, c, d}
+ Tính K3
Xét K3 = K2 – {c} = {a,d}
{a,d}+ = {a, d} R
11