Nghiên cứu về phụ thuộc hàm và ứng dụng

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT&TT

Nguyễn Thị Việt Hà

NGHIÊN CỨU VỀ PHỤ THUỘC HÀM

VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CNTT&TT

Nguyễn Thị Việt Hà

NGHIÊN CỨU VỀ PHỤ THUỘC HÀM

VÀ ỨNG DỤNG

Chuyên ngành: KHOA HỌC MÁY TÍNH

Mã số: 60.48.01

LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TS Vũ Đức Thi

Thái Nguyên - 2011

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

i

LỜI CẢM ƠN

Tôi xin đƣợc bày tỏ lòng biết ơn sâu sắc tới GS.TS Vũ Đức Thi, ngƣời

đã rất tận tình hƣớng dẫn, truyền đạt kiến thức cùng những kinh nghiệm quý

báu và giúp đỡ tôi trong suốt quá trình nghiên cứu, thực hiện và hoàn thành

luận văn này.

Tôi cũng xin đƣợc bày tỏ lòng biết ơn sâu sắc tới các thầy cô giáo Viện

Công nghệ Thông tin, những ngƣời đã truyền đạt kiến thức, kinh nghiệm quý

báu cho tôi. Và tôi xin trân trọng cảm ơn tập thể cán bộ, 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ạo

mọi điều kiện thuận lợi cho tôi hoàn thành tốt khóa học.

Cuối cùng, tôi xin cảm ơn các bạn bè đồng nghiệp và gia đình đã giúp

đỡ, động viên tôi trong suốt quá trình học tập và làm luận văn tốt nghiệp.

Thái Nguyên, tháng 10 năm 2011

Ngƣời viết

Nguyễn Thị Việt Hà

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

ii

LỜI CAM ĐOAN

Tôi xin cam đoan nội dung trong luận văn là do tôi tìm hiểu, nghiên

cứu và thực hiện đúng theo đề cƣơng đã đƣợc hội đồng khoa học Trƣờng Đại

học Công nghệ thông tin & truyền thông - Đại học Thái Nguyên duyệt, đƣợc

Thầy giáo hƣớng dẫn kiểm tra và kiểm soát. Nội dung luận văn, các phần

trích lục các tài liệu hoàn toàn chính xác. Nếu có sai sót tôi hoàn toàn chịu

trách nhiệm.

Tác giả

Nguyễn Thị Việt Hà

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iii

MỤC LỤC

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

LỜI CAM ĐOAN .............................................................................................ii

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

DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT..................................... v

DANH MỤC CÁC HÌNH................................................................................vi

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

Chƣơng 1: CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU ..................... 3

1.1. Khái quát về mô hình dữ liệu quan hệ ................................................... 3

1.2. Phụ thuộc hàm, khóa, hệ tiên đề Armstrong.......................................... 5

1.3. Phụ thuộc đa trị và phụ thuộc kết nối .................................................. 16

1.4. Mô tả tƣơng đƣơng của họ các phụ thuộc hàm.................................... 19

1.5. Xây dựng các thuật toán liên quan đến khoá ....................................... 21

1.5.1. Thuật toán tìm một khoá tối tiểu của một quan hệ ....................... 21

1.5.2 Thuật toán tìm một khoá tối tiểu của một lƣợc đồ của quan hệ..... 22

1.5.3. Xây dựng thuật toán tìm mọi khoá tối tiểu của lƣợc đồ quan hệ.. 23

1.6. Mối quan hệ giữa quan hệ Armstrong và lƣợc đồ quan hệ.................. 25

1.6.1. Xây dựng thuật toán tìm quan hệ Armstrong dựa trên LQHĐ ..... 25

1.6.2. Xây dựng thuật toán tìm lƣợc đồ quan hệ dựa trên quan hệ

Armstrong................................................................................................ 29

Chƣơng 2: CÁC DẠNG CHUẨN VÀ CÁC THUẬT TOÁN LIÊN QUAN. 33

2.1. Các khái niệm cơ bản........................................................................... 33

2.2. Các dạng chuẩn .................................................................................... 36

2.2.1. Dạng chuẩn 1NF ........................................................................... 36

2.2.2. Dạng chuẩn 2NF ........................................................................... 36

2.2.3. Dạng chuẩn 3NF ........................................................................... 38

2.2.4. Dạng chuẩn Boyce - Codd ............................................................ 40

2.3. Các thuật toán liên quan....................................................................... 41

2.3.1. Thuật toán kiểm tra một quan hệ ở 3NF ....................................... 41

2.3.2. Thuật toán phân tách 3NF bảo toàn thuộc tính và PTH................ 42

2.3.3. Thuật toán kiểm tra xem một quan hệ có ở BCNF không............ 43

2.3.4. Thuật toán tách một lƣợc đồ quan hệ thành BCNF ...................... 44

2.3.5. Thuật toán kiểm tra một quan hệ cho trƣớc đã ở dạng chuẩn BCNF

hay chƣa .................................................................................................. 45

2.3.6. Thuật toán kiểm tra phép tách kết nối không mất mát thông tin .. 46

2.3.7. Thuật toán kiểm tra phép tách nối không mất thông tin trong

trƣờng hợp có phụ thuộc đa trị................................................................ 47

2.3.8. Thuật toán tính bao đóng của một tập các thuộc tính trên tập các

phụ thuộc hàm đối với sơ đồ quan hệ ..................................................... 48

2.4. Dạng chuẩn của các hệ khóa ................................................................ 48

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

iv

Chƣơng 3: MỘT SỐ PHÉP TOÁN XỬ LÝ BẢNG....................................... 51

3.1. Phép chiếu ............................................................................................ 51

3.2. Phép chọn ............................................................................................. 52

3.3. Phép hợp............................................................................................... 53

3.4. Phép giao.............................................................................................. 54

3.5. Phép trừ ................................................................................................ 55

3.6. Tích Đề các của hai quan hệ ................................................................ 56

3.7. Phép chia hai quan hệ........................................................................... 57

3.8. Phép kết nối.......................................................................................... 58

Chƣơng 4: XÂY DỰNG CHƢƠNG TRÌNH ỨNG DỤNG........................... 60

4.1. Giới thiệu chƣơng trình........................................................................ 60

4.2. Các chức năng của chƣơng trình.......................................................... 60

4.3. Giao diện chƣơng trình ........................................................................ 61

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ...................................................... 68

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

Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc-tnu.edu.vn

v

DANH MỤC CÁC KÝ HIỆU, CHỮ CÁI VIẾT TẮT

CSDL Cơ sở dữ liệu

LĐQH Lƣợc đồ quan hệ

PTH Phụ thuộc hàm

1NF 1

st normal form - Dạng chuẩn 1

2NF 2

nd normal form - Dạng chuẩn 2

3NF 3

rd normal form - Dạng chuẩn 3

BCNF Dạng chuẩn Boyce –Codd

 Tồn tại

 Không tồn tại

 Là con

 Chứa

 Thuộc

 Không thuộc

 Với mọi

X

+ Bao đóng của tập thuộc tính X

 Rỗng

 Phép giao

 Phép hợp

 Không thuộc tập con