Thu gọn lược đồ quan hệ và ứng dụng

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

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

KHOA CÔNG NGHỆ THÔNG TIN

NGUYỄN THỊ XUÂN THU

THU GỌN LƢỢC ĐỒ QUAN HỆ VÀ ỨNG DỤNG

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

Thái Nguyên - 2010

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

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

KHOA CÔNG NGHỆ THÔNG TIN

NGUYỄN THỊ XUÂN THU

THU GỌN LƢỢC ĐỒ QUAN HỆ 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:

PGS.TSKH NGUYỄN XUÂN HUY

Thái Nguyên – 2010

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

LỜI CAM ĐOAN

Tôi xin cam đoan, luận văn là kết quả của tự bản thân tôi tìm hiểu, nghiên cứu.

Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ.

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

LỜI CẢM ƠN

Lời đầu tiên, em xin chân thành bày tỏ lòng cảm ơn và kính trọng sâu

sắc đối với PGS.TS Nguyễn Xuân Huy, người đã tận tình hướng dẫn em

trong suốt quá trình hoàn thành luận văn này. Thầy đã mở ra cho em những

vấn đề khoa học rất lý thú, hướng em vào nghiên cứu các lĩnh vực hết sức

thiết thực và vô cùng bổ ích, đồng thời tạo điều kiện thuận lợi cho em học tập

và nghiên cứu. Em đã học hỏi được rất nhiều ở Thầy phong cách làm việc,

cũng như phương pháp nghiên cứu khoa học… Em luôn được Thầy cung cấp

các tài liệu, các chỉ dẫn hết sức quý báu khi cần thiết trong suốt thời gian

thực hiện luận văn.

Em cũng xin thể hiện sự kính trọng và lòng biết ơn đến Quý Thầy Cô

trong Khoa Công nghệ thông tin - ĐHTN, những người đã trang bị cho em

rất nhiều kiến thức chuyên ngành, cũng như sự chỉ bảo, giúp đỡ tận tình của

quý Thầy cô đối với em trong suốt quá trình học tập. Tất cả các kiến thức mà

em lĩnh hội được từ bài giảng của các Thầy cô là vô cùng quý giá.

Cuối cùng, em xin được cảm ơn các bạn học viên trong lớp Cao học

K7, những người đã cung cấp và chia sẻ những tài liệu, thông tin quý báu

trong suốt quá trình học tập, nghiên cứu để hoàn thành luận văn này.

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

Học viên

Nguyễn Thị Xuân Thu

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

MỤC LỤC

Trang

Trang phụ bìa ...........................................................................................

Lời cam đoan ...........................................................................................

Lời cảm ơn ...............................................................................................

Mục lục .................................................................................................... i

Danh mục các ký hiệu, chữ cái viết tắt ..................................................... ii

Danh mục hình vẽ .................................................................................... iii

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

Chƣơng 1

CÁC KIẾN THỨC CƠ BẢN VỀ CƠ SỞ DỮ LIỆU

1.1. Khái quát về cơ sở dữ liệu ................................................................ 2

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

1.3. Lược đồ quan hệ ............................................................................... 7

1.4. Bao đóng của tập thuộc tính .............................................................. 7

1.5. Phủ của tập phụ thuộc hàm................................................................ 9

1.6. Khoá của lược đồ quan hệ ................................................................. 14

1.7. Chuẩn hoá LĐQH trên cơ sở PTH..................................................... 20

Chƣơng 2

KỸ THUẬT THU GỌN LƢỢC ĐỒ QUAN HỆ

2.1. Định nghĩa kỹ thuật thu gọn LĐQH................................................... 25

2.2. Thuật toán thu gọn LĐQH ................................................................ 25

2.3. Định lý thiết lập công thức biểu diễn bao đóng ................................. 29

2.4. Bổ đề về siêu khoá trong phép thu gọn ............................................. 32

2.5. Hệ quả về siêu khoá trong phép thu gọn ........................................... 33

2.6. Bổ đề về khoá trong phép thu gọn ..................................................... 34

2.7. Định lý thứ nhất về cách biểu diễn khoá ............................................ 35

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.8. Định lý thứ hai về cách biểu diễn khoá .............................................. 38

2.9. Lược đồ cân bằng .............................................................................. 45

Chƣơng 3

CÀI ĐẶT CHƢƠNG TRÌNH

ỨNG DỤNG KỸ THUẬT THU GỌN LƢỢC ĐỒ QUAN HỆ TRONG

THIẾT KẾ CƠ SỞ DỮ LIỆU

3.1. Giới thiệu .......................................................................................... 52

3.2. Một số giao diện của chương trình..................................................... 53

3.3. Hướng dẫn sử dụng ........................................................................... 59

KẾT LUẬN VÀ KIẾN NGHỊ

1. Kết luận................................................................................................ 61

2. Kiến nghị.............................................................................................. 61

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

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

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ệ

LĐCB Lược đồ cân bằng

PTH Phụ thuộc hàm

LS(F) Tập các vế trái của phụ thuộc hàm

RS(F) Tập các vế phải của 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

FD Phụ thuộc hàm

╞ Suy dẫn lgic

├ Suy dẫn theo quan hệ

 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

 Tương đương

! Không tương đương

 Phép giao

 Phép hợp