Nghiên cứu phụ thuộc hàm trên cơ sở siêu đồ thị và tập trù mật

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

1

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

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

HÀ MỸ TRINH

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

CƠ SỞ SIÊU ĐỒ THỊ VÀ TẬP TRÙ MẬT

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

THÁI NGUYÊN – 2014

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

2

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

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

HÀ MỸ TRINH

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

CƠ SỞ SIÊU ĐỒ THỊ VÀ TẬP TRÙ MẬT

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 01

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

Ngƣời hƣớng dẫn khoa học:

GS.TS VŨ ĐỨC THI

THÁI NGUYÊN – 2014

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

3

LỜI CAM ĐOAN

Học viên xin cam đoan đây là công trình tổng hợp và nghiên cứu của riêng học

viên. Các kết quả nêu trong luận văn là trung thực và rõ ràng đƣợc tìm hiểu trong

cac tài liệu tham khảo.

Xác nhận của giáo viên hƣớng dẫn

GS.TS Vũ Đức Thi

Học viên

Hà Mỹ Trinh

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

4

MỤC LỤC

CHƢƠNG 1: KHÁI NIỆM CHUNG.............................................................. 10

1.1 Một số ký hiệu và quy ƣớc ................................................................. 10

1.2 Quan hệ và một số khái niệm cơ bản ................................................. 13

1.2.1 Quan hệ ............................................................................................ 13

1.2.2 Cơ sở dữ liệu quan hệ ...................................................................... 15

1.2.3 Đại số quan hệ.................................................................................. 15

1.3 Phụ thuộc hàm .................................................................................... 15

1.3.1 Định nghĩa........................................................................................ 15

1.3.2 Hệ tiên đề Arsmtrong....................................................................... 16

1.3.3 Bao đóng của tập phụ thuộc hàm và tập thuộc tính......................... 16

1.3.4 Khóa tối tiểu của sơ đồ quan hệ và quan hệ ................................... 19

1.3.5 Các dạng chuẩn............................................................................... 20

1.3.6. Hệ Sperner ...................................................................................... 22

1.3.7 Các dạng tƣơng đƣơng của họ phụ thuộc hàm ................................ 28

CHƢƠNG 2: MỘT SỐ THUẬT TOÁN SIÊU ĐỒ THỊ VÀ TẬP TRÙ MẬT

......................................................................................................................... 30

2.1. Siêu đồ thị ............................................................................................. 30

2.1.1. Định nghĩa....................................................................................... 30

2.1.2 Siêu đồ thị transversal...................................................................... 33

2.2 Tập độc lập............................................................................................. 37

2.3 Tập trù mật............................................................................................. 39

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

5

2.3.1. Tập trù mật của quan hệ.................................................................. 39

2.3.2. Tập trù mật của sơ đồ quan hệ........................................................ 42

2.4 Khóa tối tiểu đối với phụ thuộc hàm.................................................. 46

CHƢƠNG 3: ỨNG DỤNG TÌM KHÓA TỐI THIỂU TRONG MỘT FILE DỮ

LIỆU................................................................................................................ 53

3.1 Mô tả bài toán ........................................................................................ 53

3.2 Cài đặt. ................................................................................................... 53

3.2.1 Yêu cầu hệ thống ............................................................................. 53

3.2.2 Cấu trúc các lớp chƣơng trình.......................................................... 54

3.3Thử nghiệm chƣơng trình ....................................................................... 54

KẾT LUẬN..................................................................................................... 57

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

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

6

DANH MỤC KÝ HIỆU VÀ CHỮ VIẾT TẮT

Trong suốt luận văn, học viên sử dụng các quy ƣớc về ký hiệu và chữ viết tắt

sau:

- s = (U,F): Sơ đồ quan hệ, với U là tập các thuộc tính và F là tập các phụ

thuộc hàm.

- R: Quan hệ trên tập thuộc tính.

- FR: Tập tất cả các phụ thuộc hàm đúng trên quan hệ R.

- F

+

: Bao đóng của tập phụ thuộc hàm.

- :Tập tất cả các khóa tối tiểu của sơ đồ quan hệ s.

- : Tập phản khóa .

- Fn: Tập tất cả các thuộc tính không cơ bản

- Dn: Tập tất cả các thuộc tính phụ thuộc.

- : Hệ bằng nhau.

- NR: Hệ không bằng nhau.

- Trs(H): Họ tất cả các transversal của siêu đồ thị H.

- Tr(H): Siêu đồ thị transversal của siêu đồ thị H.

- Is

: Họ các tập độc lập tối thiểu của sơ đồ quan hệ s.

- Ls

: Họ tất cả các bao đóng của tập thuộc tính của sơ đồ quan hệ s.

- CSDL: Cơ sở dữ liệu.

- Relation scheme: Sơ đồ quan hệ.

- Strong scheme: Sơ đồ mạnh.

- Minimal key: Khóa tối tiểu.