Lược đồ cơ sở dữ liệu chuẩn hóa

ĐẠ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Ị MAI LAN

LƯỢC ĐỒ CƠ SỞ DỮ LIỆU CHUẨN HÓA

Ngành: Khoa học máy tính

Mã số: 8.48.01.01

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS TSKH NGUYỄN XUÂN HUY

THÁI NGUYÊN - 2020

i

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn này do bản thân tôi thực hiện dưới sự hướng

dẫn khoa học của PGS TSKH Nguyễn Xuân Huy – Viện Công nghệ thông tin.

Các kết quả nghiên cứu được trình bày trong luận văn là trung thực và chưa

từng công bố trong bất kỳ công trình nào khác. Mọi thông tin trích dẫn trong

luận văn đều đã được chỉ rõ nguồn gốc.

Thái Nguyên, tháng 9 năm 2020

Tác giả

Nguyễn Thị Mai Lan

ii

LỜI CẢM ƠN

Tác giả xin được bày tỏ lòng biết ơn Ban Giám hiệu, giảng viên Trường

Đại học Công nghệ thông tin – truyền thông – Đại học Thái Nguyên đã tận tình

giảng dạy và tạo mọi điều kiện thuận lợi cho tác giả trong suốt quá trình học

tập, nghiên cứu và thực hiện luận văn.

Với tình cảm chân thành, tác giả xin được bày tỏ lòng biết ơn, cảm ơn sâu

sắc tới PGS. TSKH Nguyễn Xuân Huy đã tận tình hướng dẫn, giúp đỡ để luận

văn hoàn thành.

Cuối cùng, tác giả xin được gửi lời cảm ơn tới bạn bè, gia đình và đồng

nghiệp đã luôn động viên, giúp đỡ tác giả hoàn thành khóa học.

Thái Nguyên, tháng 9 năm 2020

Tác giả

Nguyễn Thị Mai Lan

iii

MỤC LỤC

LỜI CAM ĐOAN........................................................................................ i

LỜI CẢM ƠN ............................................................................................ii

MỤC LỤC .................................................................................................iii

CÁC KÍ HIỆU............................................................................................ v

DANH MỤC CÁC BẢNG........................................................................ vi

MỞ ĐẦU..................................................................................................... 1

1. Đặt vấn đề ................................................................................................ 1

2. Đối tượng và phạm vi nghiên cứu ........................................................... 4

3. Hướng nghiên cứu ................................................................................... 4

4. Phương pháp nghiên cứu ......................................................................... 4

5. Ý nghĩa khoa học và thực tiễn................................................................. 5

6. Cấu trúc của luận văn .............................................................................. 5

Chương 1. CÁC KIẾN THỨC CƠ BẢN................................................. 6

1.1.Quan hệ, bộ, thuộc tính.......................................................................... 6

1.2. Phụ thuộc hàm .................................................................................... 12

1.3. Bao đóng của tập thuộc tính ............................................................... 14

1.4. Phủ ...................................................................................................... 17

1.5. Khóa của lược đồ quan hệ .................................................................. 18

1.6. Các dạng chuẩn 1NF, 2NF, 3NF và BCNF........................................ 19

1.7. Bảo toàn 3NF bảo toàn phụ thuộc hàm .............................................. 19

Chương 2. CÁC THUẬT TOÁN VỀ CHUẨN HÓA DỮ LIỆU QUAN

HỆ .............................................................................................................. 20

2.1. Các thuật toán đại số quan hệ ............................................................. 20

2.1.1. Phép chọn......................................................................................... 20

2.1.2. Phép chiếu........................................................................................ 20

2.1.3. Kết nối tự nhiên ............................................................................... 21

2.1.4. Phép hợp .......................................................................................... 22

iv

2.1.5. Phép giao ......................................................................................... 22

2.1.6. Phép trừ............................................................................................ 23

2.1.7. Phép chia.......................................................................................... 24

2.2. Các thuật toán quản lý phụ thuộc hàm................................................ 25

2.2.1. Thuật toán tìm phủ thu gọn tự nhiên của tập PTH F ....................... 25

2.2.2. Thuật toán tìm phủ không dư của tập PTH F................................... 26

2.2.3. Thuật toán tìm phủ thu gọn trái của tập PTH F ............................... 26

2.2.4. Thuật toán tìm phủ thu gọn phải của tập PTH F.............................. 27

2.2.5. Thuật toán tìm phủ thu gọn của tập PTH F...................................... 28

2.3. Các thuật toán tìm bao đóng ............................................................... 29

2.4. Các thuật toán khóa............................................................................. 30

Chương 3. CÀI ĐẶT VÀ ỨNG DỤNG.................................................. 30

3.1. Tiếp cận hướng đối tượng cho thiết kế............................................... 30

3.2. Thiết kế lớp tập hợp Set...................................................................... 30

3.2.1. Các thuộc tính của lớp Set............................................................... 30

3.2.2. Các phương thức của lớp Set........................................................... 30

3.2.3. Các phép toán tập hợp ..................................................................... 33

3.3. Thiết kế lớp lược đồ quan hệ RSC ..................................................... 40

3.3.1. Các thuộc tính của lớp lược đồ quan hệ RSC.................................. 40

3.3.2. Các phương thức của lớp lược đồ quan hệ RSC ............................. 40

KẾT LUẬN............................................................................................... 65

TÀI LIỆU THAM KHẢO....................................................................... 66

v

CÁC KÍ HIỆU

KÍ HIỆU Ý NGHĨA

a  S Phần tử a thuộc tập S

a  S Phần tử a không thuộc tập S

X  Y Tập X là tập con thực sự của tập Y

X  Y Tập X là tập con của tập Y

X  Y Giao của hai tập X và Y

X  Y Hiệu của tập X và Y

X  Y Hợp của hai tập X và Y

 Lượng tử tồn tại

 Lượng tử với mọi

PTH Phụ thuộc hàm

K Khóa

LĐ Lược đồ

vi

DANH MỤC CÁC BẢNG

Bảng 1. Quan hệ Bán hàng với 3 khách hàng đầu tiên................................ 2

Bảng 2. Quan hệ Bán hàng với 4 khách hàng ............................................. 3

Bảng 3. Quan hệ Bán hàng với 4 khách hàng ............................................. 3

Bảng 1.1. Quản lý sinh viên ....................................................................... 8

Bảng 1.2. Bảng quy ước kích thước ............................................................ 8