Đồ án xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc biệt trong cơ sở dữ liệu quan hệ và ứng dụng
- 57 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 : Lưu Thế Dũng
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
-----------------------------------
XÁC ĐỊNH PHẦN TỬ NGOẠI LAI DỰA VÀO PHỤ
THUỘC HÀM ĐẶC BIỆT TRONG CƠ SỞ DỮ LIỆU
QUAN HỆ 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 : Lưu Thế Dũng
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 : Lưu Thế Dũng Mã SV: 1512101007
Lớp : CT2001C
Ngành : CÔNG NGHỆ THÔNG TIN
Tên đề tài: Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc biệt
trong cơ sở dữ liệu quan hệ 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ề phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu
quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh
hiệu cho học sinh trường THPT ở Hải Phòng.
2. Các tài liệu, số liệu cần thiết
- Số liệu: Bảng điểm của lớp học trường THPT Kiến Thụy.
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ề phụ thuộc hàm;
- Tìm hiểu về phát hiện phần tử ngoại lai;
- Ứng dụng phần tử ngoại lai.
Đề 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 HÒA 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 : Lưu Thế Dũng
Ngành: Công nghệ Thông tin
Nội dung hướng dẫn:
- Tìm hiểu về phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu
quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng phần tử ngoại lai đối với phụ thuộc hàm dạng đặc biệt để
kiểm tra xếp loại học lực và danh hiệu cho học sinh trường THPT ở
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 Không Điểm:……………………………………...
đạt
Hải Phòng, ngày 22 tháng 12 năm 2021
Giảng viên hướng dẫn
(Ký và ghi rõ họ tên)
TS. Lê Văn Phùng
CỘNG HÒA 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: Lương Thanh Nhạn
Đơn vị công tác: Trường Đại học Y Dược Hải Phòng
Họ và tên sinh viên: Lưu Thế Dũng Ngành: Công nghệ thông tin
Đề tài tốt nghiệp: Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc
biệt trong cơ sở dữ liệu quan hệ và ứng dụng.
1. Phần nhận xét của giảng viên chấm phản biện
Đồ án đã thực hiện được các nội dung sau:
- Trình bày tổng quan về phụ thuộc hàm và phần tử ngoại lai trong cơ sở
dữ liệu quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh
hiệu cho học sinh trường THPT Kiến Thụy ở Hải Phòng.
- Sử dụng ngôn ngữ lập trình PHP, hệ quản trị cơ sở dữ liệu MySQL, tác
giả đã xây dựng phần mềm kiểm tra kết quả xếp loại học lực, danh
hiệu học sinh của giáo viên chủ nhiệm so với qui định của Bộ giáo dục
và đào tạo.
Như vậy, sinh viên đã biết vận dụng các kiến thức đã học để giải quyết
bài toán thực tế. Đồ án tốt nghiệp cơ bản đã đáp ứng đầy đủ các yêu
cầu đề ra trong đề cương đã phê duyệt.
2. Những mặt còn hạn chế
- Tên đề mục 1.4: Mô hình phát hiện các phần tử ngoại lai trong dữ liệu
và trong CSDL quan hệ nên sửa lại vì trong nội dung này không trình
bày về mô hình mà chỉ đưa ra định nghĩa, phân loại và ứng dụng.
- Phần mềm chưa áp dụng được cho các lớp chuyên và còn tình huống
chưa giải quyết triệt để(không hiển thị chú thích lỗi khi có 2 tính toán
sai của một học sinh)
- Dữ liệu thực của hệ thống còn hạn chế, khóa luận chưa thực hiện đánh
giá kết quả thực nghiệm.
- Lỗi chính tả(trang 17, 22, 23, ...)
- Nhiều câu viết chưa rõ nghĩa, thiếu chủ ngữ(trang 12, 48, ...)
- Định dạng toàn khóa luận chưa đồng nhất.
3. Ý kiến của giảng viên chấm phản biện
Được bảo vệ Không được bảo vệ Điểm:
Hải Phòng, ngày …… tháng ….. năm 2022
Giảng viên chấm phản biện
(Ký và ghi rõ họ tên)
TS. Lương Thanh Nhạn
LỜI CẢM ƠN
Lời đầu tiên em xin chân thành cảm ơn các Thầy, Cô trong khoa Công
nghệ Thông tin cùng toàn thể các Thầy, Cô trường Đại học Quản lý và Công
nghệ Hải Phòng đã giảng dạy, truyền đạt cho em những kiến thức quý báu và tạo
điều kiện thuận lợi cho em trong suốt quá trình học tập tại trường cũng như
trong thời gian thực hiện đồ án tốt nghiệp.
Đặc biệt, em muốn gửi lời cảm ơn tới Tiến Sỹ– Lê Văn Phùng giảng viên
trực tiếp hướng dẫn tận tình chỉ bảo giúp em khắc phục những khó khăn, thiếu
sót để có thể hoàn thành các phần trong đồ án tốt nghiệp từ tìm hiểu lý thuyết
cho tới thực hành sử dụng công cụ.
Xin cảm ơn các bạn bè, người thân đã luôn đồng hành cùng tôi trong suốt
thời gian qua và cho tôi chỗ dựa vững chắc để tôi đạt được những kết quả như
ngày hôm nay.
Với hiểu biết tìm tòi của bản thân và sự chỉ bảo hướng dẫn tận tình của
giảng viên, em đã cố gắng hoàn thành đồ án một cách tốt nhất có thể nhưng
cũng không thể tránh được thiếu sót. Kính mong nhận được sự đóng góp ý kiến
từ thầy cô để em có thể nâng cao cũng như bổ sung thêm kiến thức cho bản thân,
hoàn thiện đồ án với một kết quả tốt và hoàn chỉnh hơn.
Em xin chân thành cảm ơn!
Hải Phòng, ngày tháng năm 2021.
Sinh viên thực hiện
Lưu Thế Dũng
Mục Lục
DANH SÁCH HÌNH VẼ .....................................................................................4
DANH SÁCH BẢNG ..........................................................................................5
MỞ ĐẦU ..............................................................................................................6
Chương 1 ..............................................................................................................7
Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ ...........7
1.1. Phụ thuộc hàm...........................................................................................7
1.1.1 Định nghĩa phụ thuộc hàm ..................................................................7
1.1.2 Hệ tiên đề Armstrong ..........................................................................9
1.2. Các dạng phụ thuộc hàm đặc biệt loại đơn giản .................................... 10
1.2.1. Dạng các phụ thuộc hàm dạng bằng nhau ...................................... 10
1.2.2. Dạng phụ thuộc hàm dạng tỉ lệ ....................................................... 11
1.3 Phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu ........ 11
1.3.1 Khái niệm về phần tử ngoại lai ........................................................ 11
Vai trò của phần tử ngoại lai trong mô hình CSDL quan hệ: ................... 12
1.3.2 Mối quan hệ giữa phần tử ngoại lai với khai phá dữ liệu ................ 15
1.4. Mô hình phát hiện các phần tử ngoại lai trong dữ liệu và trong CSDL
quan hệ .......................................................................................................... 16
1.4.1 Định nghĩa ........................................................................................ 16
1.4.2 Phân loại các phần tử ngoại lai trong CSDL quan hệ ...................... 17
1.4.3. Ứng dụng của các phần tử ngoại lai ............................................... 17
Chương 2 ........................................................................................................... 20
1
Phát hiện phần tử ngoại lai đối với phụ thuộc hàm trong CSDL quan hệ ........ 20
2.1 Phần tử ngoại lai đối với phụ thuộc hàm ................................................ 20
2.1.1 Khái niệm phần tử ngoại lai đối với phụ thuộc hàm ....................... 20
2.1.2 Định lý nhận biết cặp ngoại lai đối với phụ thuộc hàm ................... 20
Thuật toán xác định các cặp ngoại lai đối với tập các phụ thuộc hàm: .... 22
2.2 Phần tử ngoại lai đối với một số dạng phụ thuộc hàm đặc biệt ............. 22
2.2.1. Phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau.............. 23
2.2.2 Phần tử ngoại lai đối với phụ thuộc hàm dạng tỉ lệ ......................... 25
Chương 3 ........................................................................................................... 29
Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu cho
học sinh trường THPT Kiến Thụy ở Hải Phòng .............................................. 29
3.1 Bài toán đặt ra và mục tiêu chương trình ................................................ 29
3.1.1 Bài toán đặt ra .................................................................................. 29
3.1.2. Mục tiêu chương trình.................................................................... 29
3.2 Chọn thuật toán thử nghiệm .................................................................... 31
3.3 Dữ liệu vào và yêu cầu kết quả ra ........................................................... 36
3.4 Môi trường thử nghiệm và quy trình thực hiện ...................................... 36
3.4.1 Hệ quản trị dữ liệu ........................................................................... 36
3.4.3. Quy trình thực hiện ......................................................................... 36
3.5 Một số giao diện chính ............................................................................ 38
3.5.1 Giao diện trang chủ: ......................................................................... 38
3.5.2 Giao diện nhập liệu vào hệ thống : .................................................. 38
2
3.5.3 Giao diện xem dữ liệu báo cáo ......................................................... 39
3.5.4 Giao diện tính toán trung gian (tệp 3):............................................. 40
3.5.5 Giao diện phát hiện phần tử ngoại lai: ............................................. 41
3.6. Đánh giá kết quả và hướng mở rộng.................................................. 43
Phụ lục 1- Phép nối 2 file dữ liệu (Join) ................................................... 46
3
DANH SÁCH HÌNH VẼ
Hình 1 Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị
tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp ..............................................12
Hình 2 Giao diện tệp đầu vào ..................................................................................37
Hình 3 Giao diện trang chủ ......................................................................................38
Hình 4 Giao diện nhập File Excel ............................................................................38
Hình 5 Giao diện xem dữ liệu báo cáo ....................................................................39
Hình 6 Giao diện tính toán trung gian .....................................................................40
Hình 8 Trường hợp không phát hiện phần tử ngoại lai ...........................................41
Hình 9 Trường hợp phát hiện phần tử ngoại lai.......................................................42
4
DANH SÁCH BẢNG
Bảng 1 Bảng quan hệ THÍ SINH ...............................................................................8
Bảng 2 ......................................................................................................................21
Bảng 3 Bảng kê các hợp đồng nhập khẩu hàng hóa của một công ty .....................24
Bảng 4 Bảng dữ liệu.................................................................................................27
Bảng 5 Bảng tính tỉ lệ thực tế ..................................................................................27
5
MỞ ĐẦU
Thế kỷ XXI được xem là một kỷ nguyên của nền kinh tế tri thức. Các công
nghệ khám phá tri thức được áp dụng rộng rãi trong nhiều lĩnh vực và đã đem lại
những thành tựu to lớn. Nhưng các công nghệ khám phá tri thức thường nhằm mục
đích tìm kiếm, khám phá các dạng và mẫu thường gặp. Chủ yếu tập trung vào các
hướng: Tìm kiếm các luật kết hợp, nhận dạng và phân lớp mẫu…Còn lĩnh vực
khám phá phần tử ngoại lai mới bước đầu được sự quan tâm nghiên cứu. Mặc dù
nó được ứng dụng trong nhiều lĩnh vực của cuộc sống: như phát hiện những thẻ bất
thường trong hệ thống ngân hàng, những tuyến đường bất ổn không hợp lý trong
giao thông, ứng dụng trong hệ thống an ninh, dự báo thời tiết, trong thị trường
chứng khoán, trong lĩnh vực thể thao,...
Đồ án này thực hiện những công việc như sau:
- Tìm hiểu về phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu quan
hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ thuộc
hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu
cho học sinh trường THPT ở Hải Phòng.
6
Chương 1
Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong
CSDL quan hệ
1.1. Phụ thuộc hàm
1.1.1 Định nghĩa phụ thuộc hàm
Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn
một cách hình thức các ràng buộc. Phương pháp biểu diễn này có rất nhiều ưu
điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ
sở dữ liệu (CSDL).
Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa,
tìm phủ tối thiểu và chuẩn hóa CSDL.
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 Codd đã 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.
Định nghĩa:
Cho R = {a1, a2,.., an} là tập các 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
f
(ký pháp A ⎯⎯
r → B) nếu:
( hi, hj r) ((a A) ( hi(a) = hj(a)) (b B) ( hi(b) = hj(b) ))
nghĩa là đối số trùng nhau thì hàm có cùng giá trị [2].
f
Người ta còn viết (A, B) hay A → B thay cho ⎯⎯
r→ B
7
Lúc đó tập hợp tất cả (A, B) như thế xác định một họ f trên 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.
Ý 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.
Ví dụ :
Xét một quan hệ :
THISINH
SBD Họtên Điạchỉ Tỉnh Khu
vực
HP0001 Bùi văn An 14 Kiến Hải 3
An Phòng
HP0002 Nguyễn Hải 15 Cát Hải
Đăng Hải Phòng 3
HP0003 Nguyễn vân Văn Lạng
Anh Lãng Sơn 1
HP0004 Vũ thúy Liên 52 Quang Nam
Trung Định 2
Bảng 1 Bảng quan hệ THÍ SINH
Trong quan hệ THISINH dựa vào định nghĩa phụ thuộc hàm của quan hệ ,
có thể kết luận:
8
f
{Tỉnh} ⎯⎯
r → { Khuvực}
f
r → { Họtên, Địachỉ, Tỉnh, Khuvực}
{SBD} ⎯⎯
1.1.2 Hệ tiên đề Armstrong
Gọi F là tập xác định các phụ thuộc hàm đối với lược đồ quan hệ R và X →
Y là một phụ thuộc hàm. X, Y R. Nói rằng X → Y được suy diễn logic từ F nếu
mối quan hệ r trên R đều thoả mãn phụ thuộc hàm của F thì cũng thoả mãn X → Y.
Chẳng hạn F ={A → B, B → C} thì A → C suy ra từ F. Gọi F+ là bao đóng
(closure) của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Nếu
F = F+ thì F là họ đầy đủ (full family) của các phụ thuộc hàm [3].
Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa
các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có các hệ
tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, được gọi là
hệ tiên đề Armstrong.
Định nghĩa:
Cho R = {a1,...,an} là tập các thuộc tính.
X, Y, Z R. Hệ tiên đề Armstrong bao gồm 3 tính chất cơ bản sau:
➢ A1 (phản xạ) : Nếu Y X thì X → Y
➢ A2 (tăng trưởng) : Nếu Z R và X → Y thì XZ → YZ.
9
Trong đó ký hiệu XZ là hợp của hai tập X và Z thay cho ký hiệu X Z.
➢ A3 (bắc cầu ) : Nếu X → Y và Y → Z thì X → Z.
Nhận xét:
➢ Việc nghiên cứu phụ thuộc hàm không lệ thuộc vào các quan hệ (bảng)
cụ thể. Vì vậy, áp dụng được các công cụ toán nhằm sáng tỏ cấu trúc
logic của mô hình dữ liệu quan hệ
➢ Có nhiều quan hệ khác nhau nhưng các họ đầy đủ các phụ thuộc hàm
của chúng lại như nhau
Ví dụ:
Cho r1, r2 là các quan hệ:
A B A B
0 0 0 0
r1 = 1 1 r2 = 1 1
2 1 2 1
3 2 3 1
Có thể thấy rằng r1 và r2 khác nhau nhưng Fr1 = Fr2 vì chỉ có A → B
1.2. Các dạng phụ thuộc hàm đặc biệt loại đơn giản
Có một số phụ thuộc hàm có dạng rất đặc biệt. Chúng ta sẽ xét ở đây hai
dạng rất đặc biệt trong số đó [4].
1.2.1. Dạng các phụ thuộc hàm dạng bằng nhau
Cho bảng dữ liệu r trên R = (A1, A2, .....An). Giả sử với Ap, Aq nào đó thuộc
R, mà với mọi ti r ta có: ti(Ap) = ti(Aq). Khi đó ta dễ thấy có phụ thuộc hàm: Ap
→ Aq ( cũng đồng thời có Aq → Ap). Người ta gọi các phụ thuộc hàm dạng này là
các phụ thuộc hàm dạng bằng nhau [2].
10
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 : Lưu Thế Dũng
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
-----------------------------------
XÁC ĐỊNH PHẦN TỬ NGOẠI LAI DỰA VÀO PHỤ
THUỘC HÀM ĐẶC BIỆT TRONG CƠ SỞ DỮ LIỆU
QUAN HỆ 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 : Lưu Thế Dũng
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 : Lưu Thế Dũng Mã SV: 1512101007
Lớp : CT2001C
Ngành : CÔNG NGHỆ THÔNG TIN
Tên đề tài: Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc biệt
trong cơ sở dữ liệu quan hệ 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ề phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu
quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh
hiệu cho học sinh trường THPT ở Hải Phòng.
2. Các tài liệu, số liệu cần thiết
- Số liệu: Bảng điểm của lớp học trường THPT Kiến Thụy.
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ề phụ thuộc hàm;
- Tìm hiểu về phát hiện phần tử ngoại lai;
- Ứng dụng phần tử ngoại lai.
Đề 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 HÒA 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 : Lưu Thế Dũng
Ngành: Công nghệ Thông tin
Nội dung hướng dẫn:
- Tìm hiểu về phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu
quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng phần tử ngoại lai đối với phụ thuộc hàm dạng đặc biệt để
kiểm tra xếp loại học lực và danh hiệu cho học sinh trường THPT ở
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 Không Điểm:……………………………………...
đạt
Hải Phòng, ngày 22 tháng 12 năm 2021
Giảng viên hướng dẫn
(Ký và ghi rõ họ tên)
TS. Lê Văn Phùng
CỘNG HÒA 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: Lương Thanh Nhạn
Đơn vị công tác: Trường Đại học Y Dược Hải Phòng
Họ và tên sinh viên: Lưu Thế Dũng Ngành: Công nghệ thông tin
Đề tài tốt nghiệp: Xác định phần tử ngoại lai dựa vào phụ thuộc hàm đặc
biệt trong cơ sở dữ liệu quan hệ và ứng dụng.
1. Phần nhận xét của giảng viên chấm phản biện
Đồ án đã thực hiện được các nội dung sau:
- Trình bày tổng quan về phụ thuộc hàm và phần tử ngoại lai trong cơ sở
dữ liệu quan hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ
thuộc hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh
hiệu cho học sinh trường THPT Kiến Thụy ở Hải Phòng.
- Sử dụng ngôn ngữ lập trình PHP, hệ quản trị cơ sở dữ liệu MySQL, tác
giả đã xây dựng phần mềm kiểm tra kết quả xếp loại học lực, danh
hiệu học sinh của giáo viên chủ nhiệm so với qui định của Bộ giáo dục
và đào tạo.
Như vậy, sinh viên đã biết vận dụng các kiến thức đã học để giải quyết
bài toán thực tế. Đồ án tốt nghiệp cơ bản đã đáp ứng đầy đủ các yêu
cầu đề ra trong đề cương đã phê duyệt.
2. Những mặt còn hạn chế
- Tên đề mục 1.4: Mô hình phát hiện các phần tử ngoại lai trong dữ liệu
và trong CSDL quan hệ nên sửa lại vì trong nội dung này không trình
bày về mô hình mà chỉ đưa ra định nghĩa, phân loại và ứng dụng.
- Phần mềm chưa áp dụng được cho các lớp chuyên và còn tình huống
chưa giải quyết triệt để(không hiển thị chú thích lỗi khi có 2 tính toán
sai của một học sinh)
- Dữ liệu thực của hệ thống còn hạn chế, khóa luận chưa thực hiện đánh
giá kết quả thực nghiệm.
- Lỗi chính tả(trang 17, 22, 23, ...)
- Nhiều câu viết chưa rõ nghĩa, thiếu chủ ngữ(trang 12, 48, ...)
- Định dạng toàn khóa luận chưa đồng nhất.
3. Ý kiến của giảng viên chấm phản biện
Được bảo vệ Không được bảo vệ Điểm:
Hải Phòng, ngày …… tháng ….. năm 2022
Giảng viên chấm phản biện
(Ký và ghi rõ họ tên)
TS. Lương Thanh Nhạn
LỜI CẢM ƠN
Lời đầu tiên em xin chân thành cảm ơn các Thầy, Cô trong khoa Công
nghệ Thông tin cùng toàn thể các Thầy, Cô trường Đại học Quản lý và Công
nghệ Hải Phòng đã giảng dạy, truyền đạt cho em những kiến thức quý báu và tạo
điều kiện thuận lợi cho em trong suốt quá trình học tập tại trường cũng như
trong thời gian thực hiện đồ án tốt nghiệp.
Đặc biệt, em muốn gửi lời cảm ơn tới Tiến Sỹ– Lê Văn Phùng giảng viên
trực tiếp hướng dẫn tận tình chỉ bảo giúp em khắc phục những khó khăn, thiếu
sót để có thể hoàn thành các phần trong đồ án tốt nghiệp từ tìm hiểu lý thuyết
cho tới thực hành sử dụng công cụ.
Xin cảm ơn các bạn bè, người thân đã luôn đồng hành cùng tôi trong suốt
thời gian qua và cho tôi chỗ dựa vững chắc để tôi đạt được những kết quả như
ngày hôm nay.
Với hiểu biết tìm tòi của bản thân và sự chỉ bảo hướng dẫn tận tình của
giảng viên, em đã cố gắng hoàn thành đồ án một cách tốt nhất có thể nhưng
cũng không thể tránh được thiếu sót. Kính mong nhận được sự đóng góp ý kiến
từ thầy cô để em có thể nâng cao cũng như bổ sung thêm kiến thức cho bản thân,
hoàn thiện đồ án với một kết quả tốt và hoàn chỉnh hơn.
Em xin chân thành cảm ơn!
Hải Phòng, ngày tháng năm 2021.
Sinh viên thực hiện
Lưu Thế Dũng
Mục Lục
DANH SÁCH HÌNH VẼ .....................................................................................4
DANH SÁCH BẢNG ..........................................................................................5
MỞ ĐẦU ..............................................................................................................6
Chương 1 ..............................................................................................................7
Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong CSDL quan hệ ...........7
1.1. Phụ thuộc hàm...........................................................................................7
1.1.1 Định nghĩa phụ thuộc hàm ..................................................................7
1.1.2 Hệ tiên đề Armstrong ..........................................................................9
1.2. Các dạng phụ thuộc hàm đặc biệt loại đơn giản .................................... 10
1.2.1. Dạng các phụ thuộc hàm dạng bằng nhau ...................................... 10
1.2.2. Dạng phụ thuộc hàm dạng tỉ lệ ....................................................... 11
1.3 Phần tử ngoại lai và mối quan hệ giữa chúng với khai phá dữ liệu ........ 11
1.3.1 Khái niệm về phần tử ngoại lai ........................................................ 11
Vai trò của phần tử ngoại lai trong mô hình CSDL quan hệ: ................... 12
1.3.2 Mối quan hệ giữa phần tử ngoại lai với khai phá dữ liệu ................ 15
1.4. Mô hình phát hiện các phần tử ngoại lai trong dữ liệu và trong CSDL
quan hệ .......................................................................................................... 16
1.4.1 Định nghĩa ........................................................................................ 16
1.4.2 Phân loại các phần tử ngoại lai trong CSDL quan hệ ...................... 17
1.4.3. Ứng dụng của các phần tử ngoại lai ............................................... 17
Chương 2 ........................................................................................................... 20
1
Phát hiện phần tử ngoại lai đối với phụ thuộc hàm trong CSDL quan hệ ........ 20
2.1 Phần tử ngoại lai đối với phụ thuộc hàm ................................................ 20
2.1.1 Khái niệm phần tử ngoại lai đối với phụ thuộc hàm ....................... 20
2.1.2 Định lý nhận biết cặp ngoại lai đối với phụ thuộc hàm ................... 20
Thuật toán xác định các cặp ngoại lai đối với tập các phụ thuộc hàm: .... 22
2.2 Phần tử ngoại lai đối với một số dạng phụ thuộc hàm đặc biệt ............. 22
2.2.1. Phần tử ngoại lai đối với phụ thuộc hàm dạng bằng nhau.............. 23
2.2.2 Phần tử ngoại lai đối với phụ thuộc hàm dạng tỉ lệ ......................... 25
Chương 3 ........................................................................................................... 29
Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu cho
học sinh trường THPT Kiến Thụy ở Hải Phòng .............................................. 29
3.1 Bài toán đặt ra và mục tiêu chương trình ................................................ 29
3.1.1 Bài toán đặt ra .................................................................................. 29
3.1.2. Mục tiêu chương trình.................................................................... 29
3.2 Chọn thuật toán thử nghiệm .................................................................... 31
3.3 Dữ liệu vào và yêu cầu kết quả ra ........................................................... 36
3.4 Môi trường thử nghiệm và quy trình thực hiện ...................................... 36
3.4.1 Hệ quản trị dữ liệu ........................................................................... 36
3.4.3. Quy trình thực hiện ......................................................................... 36
3.5 Một số giao diện chính ............................................................................ 38
3.5.1 Giao diện trang chủ: ......................................................................... 38
3.5.2 Giao diện nhập liệu vào hệ thống : .................................................. 38
2
3.5.3 Giao diện xem dữ liệu báo cáo ......................................................... 39
3.5.4 Giao diện tính toán trung gian (tệp 3):............................................. 40
3.5.5 Giao diện phát hiện phần tử ngoại lai: ............................................. 41
3.6. Đánh giá kết quả và hướng mở rộng.................................................. 43
Phụ lục 1- Phép nối 2 file dữ liệu (Join) ................................................... 46
3
DANH SÁCH HÌNH VẼ
Hình 1 Phần tử ngoại lai trong tập điểm có tọa độ (x,y) trên mặt phẳng có giá trị
tung độ y nhỏ hơn hẳn các phần tử khác của tập hợp ..............................................12
Hình 2 Giao diện tệp đầu vào ..................................................................................37
Hình 3 Giao diện trang chủ ......................................................................................38
Hình 4 Giao diện nhập File Excel ............................................................................38
Hình 5 Giao diện xem dữ liệu báo cáo ....................................................................39
Hình 6 Giao diện tính toán trung gian .....................................................................40
Hình 8 Trường hợp không phát hiện phần tử ngoại lai ...........................................41
Hình 9 Trường hợp phát hiện phần tử ngoại lai.......................................................42
4
DANH SÁCH BẢNG
Bảng 1 Bảng quan hệ THÍ SINH ...............................................................................8
Bảng 2 ......................................................................................................................21
Bảng 3 Bảng kê các hợp đồng nhập khẩu hàng hóa của một công ty .....................24
Bảng 4 Bảng dữ liệu.................................................................................................27
Bảng 5 Bảng tính tỉ lệ thực tế ..................................................................................27
5
MỞ ĐẦU
Thế kỷ XXI được xem là một kỷ nguyên của nền kinh tế tri thức. Các công
nghệ khám phá tri thức được áp dụng rộng rãi trong nhiều lĩnh vực và đã đem lại
những thành tựu to lớn. Nhưng các công nghệ khám phá tri thức thường nhằm mục
đích tìm kiếm, khám phá các dạng và mẫu thường gặp. Chủ yếu tập trung vào các
hướng: Tìm kiếm các luật kết hợp, nhận dạng và phân lớp mẫu…Còn lĩnh vực
khám phá phần tử ngoại lai mới bước đầu được sự quan tâm nghiên cứu. Mặc dù
nó được ứng dụng trong nhiều lĩnh vực của cuộc sống: như phát hiện những thẻ bất
thường trong hệ thống ngân hàng, những tuyến đường bất ổn không hợp lý trong
giao thông, ứng dụng trong hệ thống an ninh, dự báo thời tiết, trong thị trường
chứng khoán, trong lĩnh vực thể thao,...
Đồ án này thực hiện những công việc như sau:
- Tìm hiểu về phụ thuộc hàm và phần tử ngoại lai trong cơ sở dữ liệu quan
hệ.
- Tìm hiểu về phương pháp phát hiện phần tử ngoại lai đối với phụ thuộc
hàm trong cơ sở dữ liệu quan hệ.
- Ứng dụng tìm phần tử ngoại lai để kiểm tra xếp loại học lực và danh hiệu
cho học sinh trường THPT ở Hải Phòng.
6
Chương 1
Tổng quan về phụ thuộc hàm và phần tử ngoại lai trong
CSDL quan hệ
1.1. Phụ thuộc hàm
1.1.1 Định nghĩa phụ thuộc hàm
Phụ thuộc hàm (functional dependency) là một công cụ dùng để biểu diễn
một cách hình thức các ràng buộc. Phương pháp biểu diễn này có rất nhiều ưu
điểm, và đây là một công cụ cực kỳ quan trọng, gắn chặt với lý thuyết thiết kế cơ
sở dữ liệu (CSDL).
Phụ thuộc hàm được ứng dụng trong việc giải quyết các bài toán tìm khóa,
tìm phủ tối thiểu và chuẩn hóa CSDL.
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 Codd đã 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.
Định nghĩa:
Cho R = {a1, a2,.., an} là tập các 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
f
(ký pháp A ⎯⎯
r → B) nếu:
( hi, hj r) ((a A) ( hi(a) = hj(a)) (b B) ( hi(b) = hj(b) ))
nghĩa là đối số trùng nhau thì hàm có cùng giá trị [2].
f
Người ta còn viết (A, B) hay A → B thay cho ⎯⎯
r→ B
7
Lúc đó tập hợp tất cả (A, B) như thế xác định một họ f trên 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.
Ý 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.
Ví dụ :
Xét một quan hệ :
THISINH
SBD Họtên Điạchỉ Tỉnh Khu
vực
HP0001 Bùi văn An 14 Kiến Hải 3
An Phòng
HP0002 Nguyễn Hải 15 Cát Hải
Đăng Hải Phòng 3
HP0003 Nguyễn vân Văn Lạng
Anh Lãng Sơn 1
HP0004 Vũ thúy Liên 52 Quang Nam
Trung Định 2
Bảng 1 Bảng quan hệ THÍ SINH
Trong quan hệ THISINH dựa vào định nghĩa phụ thuộc hàm của quan hệ ,
có thể kết luận:
8
f
{Tỉnh} ⎯⎯
r → { Khuvực}
f
r → { Họtên, Địachỉ, Tỉnh, Khuvực}
{SBD} ⎯⎯
1.1.2 Hệ tiên đề Armstrong
Gọi F là tập xác định các phụ thuộc hàm đối với lược đồ quan hệ R và X →
Y là một phụ thuộc hàm. X, Y R. Nói rằng X → Y được suy diễn logic từ F nếu
mối quan hệ r trên R đều thoả mãn phụ thuộc hàm của F thì cũng thoả mãn X → Y.
Chẳng hạn F ={A → B, B → C} thì A → C suy ra từ F. Gọi F+ là bao đóng
(closure) của F, tức là tập tất cả các phụ thuộc hàm được suy diễn logic từ F. Nếu
F = F+ thì F là họ đầy đủ (full family) của các phụ thuộc hàm [3].
Để có thể xác định khoá của một lược đồ quan hệ và các suy diễn logic giữa
các phụ thuộc hàm cần thiết phải tính được F+ từ F. Do đó đòi hỏi phải có các hệ
tiên đề. Tập các quy tắc của hệ tiên đề được Armstrong (1974) đưa ra, được gọi là
hệ tiên đề Armstrong.
Định nghĩa:
Cho R = {a1,...,an} là tập các thuộc tính.
X, Y, Z R. Hệ tiên đề Armstrong bao gồm 3 tính chất cơ bản sau:
➢ A1 (phản xạ) : Nếu Y X thì X → Y
➢ A2 (tăng trưởng) : Nếu Z R và X → Y thì XZ → YZ.
9
Trong đó ký hiệu XZ là hợp của hai tập X và Z thay cho ký hiệu X Z.
➢ A3 (bắc cầu ) : Nếu X → Y và Y → Z thì X → Z.
Nhận xét:
➢ Việc nghiên cứu phụ thuộc hàm không lệ thuộc vào các quan hệ (bảng)
cụ thể. Vì vậy, áp dụng được các công cụ toán nhằm sáng tỏ cấu trúc
logic của mô hình dữ liệu quan hệ
➢ Có nhiều quan hệ khác nhau nhưng các họ đầy đủ các phụ thuộc hàm
của chúng lại như nhau
Ví dụ:
Cho r1, r2 là các quan hệ:
A B A B
0 0 0 0
r1 = 1 1 r2 = 1 1
2 1 2 1
3 2 3 1
Có thể thấy rằng r1 và r2 khác nhau nhưng Fr1 = Fr2 vì chỉ có A → B
1.2. Các dạng phụ thuộc hàm đặc biệt loại đơn giản
Có một số phụ thuộc hàm có dạng rất đặc biệt. Chúng ta sẽ xét ở đây hai
dạng rất đặc biệt trong số đó [4].
1.2.1. Dạng các phụ thuộc hàm dạng bằng nhau
Cho bảng dữ liệu r trên R = (A1, A2, .....An). Giả sử với Ap, Aq nào đó thuộc
R, mà với mọi ti r ta có: ti(Ap) = ti(Aq). Khi đó ta dễ thấy có phụ thuộc hàm: Ap
→ Aq ( cũng đồng thời có Aq → Ap). Người ta gọi các phụ thuộc hàm dạng này là
các phụ thuộc hàm dạng bằng nhau [2].
10