Bài tập về các khóa

NHẬP MÔN CSDL QUAN HỆ Soạn bởi bộ môn Công nghệ phần mềm - 2007

http://www.ebook.edu.vn Trang 1

3. BμI TËP VÒ kho¸

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC

¾ Phân biệt các loại khoá

¾ Các thuật toán tìm một khoá, nhiều khoá.

¾ Ứng dụng giải quyết các bài toán về khoá.

A/ NHẮC LẠI LÝ THUYẾT

I. CÁC ĐỊNH NGHĨA, TÍNH CHẤT, THUẬT TOÁN

1. Họ Sperner

Nếu gọi Kα là tập tất c các khoá của lược đồ α=(U,F), như vậy mỗi phần tử của Kα là một tập

thuộc tính và các tập hợp đó là không bao nhau.

Định nghĩa: Họ Sperner trên U là họ M={ X | X⊆U } sao cho hai phần tử của M là không bao

nhau.

Nhận xét: Tập hợp Kα tất cả các khoá của lược đồ là một họ Sperner trên U.

2. Siêu khoá và khoá

Định nghĩa: Cho lược đồ quan hệ α=(U,F) , K⊆U n ếu K+

= U, thì ta nói K là một siêu khoá.

Chú ý: Điều kiện K+

=U có thể thay bằng KÆU hoặc KÆU \ K

Định nghĩa: Cho lược đồ quan hệ α=(U,F) , K⊆U n ếu K+

= U, thì ta nói K là một siêu khoá.

Chú ý: Điều kiện K+

=U có thể thay bằng KÆU hoặc KÆU \ K

Định nghĩa: Cho lược đồ quan hệ α=(U,F), tập K ⊆U được gọi là khoá của lược đồ (nếu như

nó thoả mãn:

- K là một siêu khoá

- ∀ K1 ⊂ K thì K1 Không là siêu khoá tức K+

1 ≠ U

Chú ý: định nghĩa này là tương đương với định nghĩa

Cho lược đồ quan hệ α=(U,F), tập K ⊆U được gọi là khoá của lược đồ ( nếu như nó thoả

mãn:

- K ÆU ∈ F+

- ∀ K1 ⊂ K thì K1 Æ U ∉ F+ (K+ ≠ U)

Tập hợp Kα tất cả các khoá của lược đồ là một họ Sperner trên U.

Bài toán: Cho M là một họ Sperner trên U thì có tồn tại hay không một lược đồ quan hệ

α=(U,F) sao cho Kα =M ( lược đồ có các khoá là các phần tử của họ M).

Trả lời: Có tồn tại một lược đồ α=(U,F) được xây dựng như sau:

Xây dựng F, giả sử M={X1, X2,..., Xn} ta xây dựng F như sau:

F={ XiÆ U\ Xi ∀ i=1, .., n }

Khi đó lược đồ α=(U,F) có Kα =M

2. Một số vấn đề về khoá

Cho α=(U,F) ta cần quan tâm một số vấn đề sau:

Bài toán 1:

Cho K ⊆U hỏi rằng K có phải là khoá hay không?

Cách làm: Tính K+

, nếu K+ ≠ U thì K không là khoá của lược đồ