Bài Tập Mẫu Cơ Sở Dữ Liệu: Tổng Hợp Mới Nhất

MỤC LỤC

Lời mở đầu............................................................................................................7 Chương 1: .............................................................................................................8 Mô hình quan hệ- chuyển mô hình E-R sang mô hình quan hệ......................8 A/Nhắc lại lí thuyết ..............................................................................................8 I. Các khái niệm của mô hình quan hệ..............................................................8 1. Quan hệ ..............................................................................................................8 2. Lược đồ ..............................................................................................................8 3. Bộ .......................................................................................................................9 4. Miền giá trị.........................................................................................................9 5. Khóa ngoại .......................................................................................................12 6. Biểu diễn ràng buộc tham chiếu ......................................................................14 III. Các đặc trưng của quan hệ.........................................................................14 IV. Chuyển lược đồ E-R sang lược đồ quan hệ...............................................14 B/ Bài tập mẫu....................................................................................................16 C/ Bài tập tự giải ................................................................................................20 Bài số1: Chuyển đổi từ mô hình dữ liệu mô hình dữ liệu quan hệ sang ER .......20 Bài số 2: Chuyển đổi từ mô hình dữ liệu mô hình dữ liệu quan hệ sang ER ......20 Bài số 3: Vẽ lược đồ quản lý đề án công ty.........................................................20 Chương 2: ...........................................................................................................22 Đại số quan hệ ....................................................................................................22 A. Nhắc lại lí thuyết ...........................................................................................22 I. Các phép toán đại số quan hệ .......................................................................22 1. Phép hợp: .........................................................................................................22 2. Phép giao:.........................................................................................................22 3. Phép hiệu:.........................................................................................................22 II. Các ví dụ ........................................................................................................23 Ví dụ 1: Đây là phép chiếu trên quan hệ R..........................................................23 Ví dụ 2: Đây là phép kết nối trên hai quan hệ .....................................................24 Ví dụ 3: Đây là phép nối tự nhiên trên hai quan hệ.............................................25 Ví dụ 4: Đây là phép tích đề các trên hai quan hệ ...............................................25 Ví dụ 5: Đây là phép chia quan hệ R cho quan hê S ...........................................25 Ví dụ 6: Đây là phép chọn trên quan hệ R, biểuthức chọn là E = B≥ C khi đó: .26 III. Một số lưu ý .................................................................................................26 1

B.Bài tập giải mẫu .............................................................................................26 Bài số 1: Thực hiện phép chọn trên quan hệ SV(Hoten, namsinh, CSDL, FOX).27 Bài tập 2: Kết hợp các phép toán của ngôn ngữ đại số quan hệ..........................27 C. Bài tập tự giải ................................................................................................29 Bài số 3: Phép chia giữa hai quan hệ. ..............................................................30 Bài số 5: Tổng hợp các phép toán đại số quan hệ. ..............................................31 Bài số 6: Thao tác trên một cơ sở dữ liệu. ...........................................................32 Bài số 7: Thao tác trên một cơ sở dữ liệu. ...........................................................33 Bài số 8: Thao tác trên một cơ sở dữ liệu. ...........................................................34 Bài tập9: Tổng hợp các phép toán đại số quan hệ. ..............................................35 Bài số 10: Tổng hợp các phép toán đại số quan hệ. ............................................36 Bài số 11: .............................................................................................................36 Bài số 12: .............................................................................................................36 Bài số 13: .............................................................................................................37 Bài số 14: .............................................................................................................37 Chương 3: ...........................................................................................................38 Các vấn đề về phụ thuộc hàm...........................................................................38 A/ Nhắc lại lí thuyết ...........................................................................................38 I. Một số định nghĩa, tính chất..........................................................................38 1. Định nghĩa phụ thuộc hàm...............................................................................38 2. Một số tính chất của phụ thuộc hàm:...............................................................39 3. Hệ tiên đề Amstrong ........................................................................................39 4. Định nghĩa suy dẫn theo hệ tiên đề..................................................................40 5. Định nghĩa suy dẫn theo quan hệ.....................................................................40 6. Bao đóng của tập thuộc tính ............................................................................41 Thuật toán 1 .........................................................................................................42 7. Phụ thuộc hàm dư thừa ....................................................................................43 8. Phủ không dư và thuật toán tìm phủ không dư................................................43 9. Phủ thu gọn ......................................................................................................44 10. Phủ tối thiểu ...................................................................................................45 II. Các ví dụ ........................................................................................................47 B/ Bài tập giải mẫu.............................................................................................48 Bài số 1: ...............................................................................................................48 Bài số 2: ...............................................................................................................48 Bài tập 3:Tìm bao đóng. ......................................................................................49 Bài tập 4: Cho lược đồ quan hệ R = (U, F)..........................................................51

Bài tập 5: Phụ thuộc hàm dư thừa........................................................................51 Bài tập 6: Tìm phủ tối thiểu của tập phụ thuộc hàm T sau đây...........................52 C/ Bài tập tự giải ................................................................................................53 Bài tập 1: ..............................................................................................................53 Bài tập 2: ..............................................................................................................53 Bài tập 3 ...............................................................................................................54 Bài tập 4 ...............................................................................................................54 Bài tập 5 ...............................................................................................................54 Bài tập 6 ...............................................................................................................54 Bài tập 7 ...............................................................................................................54 Bài tập 8 ...............................................................................................................54 Bài tập 9 ...............................................................................................................54 Bài tập 10 .............................................................................................................55 Bài tập 11 .............................................................................................................55 Bài tập 12 .............................................................................................................55 Bài tập 13 .............................................................................................................55 Bài tập 15 .............................................................................................................55 Bài tập 16 .............................................................................................................55 Bài tập 17 .............................................................................................................56 Bài tập 18 .............................................................................................................56 Bài tập 19 .............................................................................................................56 Bài tập 20 .............................................................................................................56 Bài tập 22 .............................................................................................................57 Bài tập 23 .............................................................................................................57 Bài tập 24 .............................................................................................................57 Chương 4: ...........................................................................................................58 Các vấn đề về khóa của lược đồ quan hệ........................................................ 50 A/ Nhắc lại lí thuyết ...........................................................................................58 I. Các định nghĩa, tính chất, thuật toán...........................................................58 1. Họ Sperner .......................................................................................................58 2. Siêu khoá và khoá ............................................................................................58 II. Một số vấn đề về khóa ..................................................................................59 Bài toán 1: Cho K ˝ U hỏi rằng K có phải là khoá hay không? .........................59 Bài toán 2: Tìm một khoá của lược đồ. ...............................................................59 .........................................................60 Bài toán 3: Tìm giao của tất cả các khoá Ia

Bài toán 4: Cho lược đồ quan hệ a = (U, F). Hỏi rằng lược đồ có bao nhiêu khoá......................................................................................................................60 Bài toán 5: Cho lược đồ a = (U, F). Hãy tìm các khoá của lược đồ. ..................60 B/ Bài tập giải mẫu.............................................................................................62 Bài số 1: Kiểm tra một tập thuộc tính có phải là khoá của một lược đồ không? 62 Bài số 2:Tìm một khoá của lược đồ.....................................................................62 Bài số 3: Hãy tìm giao của tấp cả các khoá của lược đồ a = (U, F)....................62 Bài số 4: ...............................................................................................................63 C/ Bài tập tự giải ................................................................................................63 Bài tập 1: ..............................................................................................................63 Bài tập 2: ..............................................................................................................63 Bài tập 3: ..............................................................................................................63 Bài tập 4 ...............................................................................................................63 Bài tập 5: ..............................................................................................................64 Bài tập 6: ..............................................................................................................64 Bài tập 7: ..............................................................................................................64 Bài tập 8: ..............................................................................................................64 Bài tập 9: ..............................................................................................................65 Bài tập 10: ............................................................................................................65 Bài tập 11: ............................................................................................................65 Bài tập 12: ............................................................................................................65 Bài tập 13: ............................................................................................................65 Bài tập 14: ............................................................................................................66 Bài tập 15: ............................................................................................................66 Bài tập 16: ............................................................................................................66 Bài tập 17: ............................................................................................................66 Bài tập 18: ............................................................................................................67 Bài tập 19: ............................................................................................................67 Chương 5: ...........................................................................................................68 Chuẩn hóa lược đồ quan hệ ..............................................................................68 A/ Nhắc lại lí thuyết ...........................................................................................68 I. Các định nghĩa, tính chất...............................................................................68 1. Dạng chuẩn 1 (1NF - first normal form) .........................................................68 2. Dạng chuẩn 2 (2NF- Second normal form) .....................................................68 3. Dạng chuẩn 3 (3NF- Second normal form) .....................................................69 4. Dạng chuẩn Boyce Codd (BCNF- Boyce Codd normal form)........................70 4

5. Tách lược đồ quan hệ.......................................................................................71 6. Thuật toán kiểm tra phép tách kết nối có mất thông tin hay không? ..............71 7. Phương pháp chuẩn hóa dữ liệu.......................................................................72 II. Một số lưu ý ...................................................................................................74 B/ Bài tập giải mẫu.............................................................................................75 Bài số 1: Kiểm tra lược đồ (U, F) có ở dạng chuẩn 2NF hoặc 3NF hay không? 75 Bài số 2: Kiểm tra phép tách có mất thông tin hay không?.................................75 C/ Bài tập tự giải ................................................................................................76 Bài tập 1: ..............................................................................................................76 Bài tập 2: ..............................................................................................................77 Bài tập 3: ..............................................................................................................77 Bài tập 4: ..............................................................................................................77 Bài tập 5: ..............................................................................................................77 Bài tập 6: ..............................................................................................................77 Bài tập 7: ..............................................................................................................77 Bài tập 8: ..............................................................................................................78 Bài tập 11: ............................................................................................................78 Bài tập 12: ............................................................................................................78 Bài tập 13: ............................................................................................................78 Bài tập 14: ............................................................................................................79 Chương 6: ...........................................................................................................79 Ngôn ngữ SQL....................................................................................................79 A/ Nhắc lại lí thuyết ..........................................................................................79 I. Các nhóm lệnh của ngôn ngữ cơ sở dữ liệu.................................................79 1. Các lệnh DDL: CREATE, ALTER, DROP...................................................79 2. Các lệnh DML: SELECT, UPDATE, INSERT, DELETE, …........................81 II. Các ví dụ ........................................................................................................83 Ví dụ 1: ................................................................................................................83 Ví dụ 2: ................................................................................................................83 III. Một số lưu ý .................................................................................................84 B/ Bài tập giải mẫu.............................................................................................84 Bài số 1: ...............................................................................................................84 Bài số 2: ...............................................................................................................84 Bài số 3: ...............................................................................................................86 C/ Bài tập tự giải ................................................................................................87 Bài tập 1: ..............................................................................................................87

Bài tập 2: ..............................................................................................................88 Bài số 3 ................................................................................................................89 Bài số 4 ................................................................................................................89 Bài số 5 ................................................................................................................90 Bài số 6 ................................................................................................................90 Bài số 7 ................................................................................................................90 Bài số 8 ................................................................................................................90 Bài số 9 ................................................................................................................92 Bài số 10 ..............................................................................................................94 Bài số 11 ..............................................................................................................95 Bài số 12 ..............................................................................................................96 Bài số 13 ..............................................................................................................97 Bài số 14 ..............................................................................................................98 Tài liệu tham khảo .............................................................................................99

LỜI MỞ ĐẦU

Cơ sở dữ liệu là một lĩnh vực quan trọng của Công nghệ thông tin. Cùng với sự phát triển CNTT nước ta, việc sử dụng các kiến thức về cơ sở dữ liệu ngày càng cần thiết.

Thật là thiệt thòi cho sinh viên và các bạn tự học, khi trong tủ sách nhà trường chỉ thấy đại đa số các sách bài tập về lập trình. Cuốn bài tập CSDL này là một tài liệu nhằm trợ giúp các bạn trẻ một phương thức tự kiểm tra kiến thức của mình về một lĩnh vực đang chiếm một vị trí quan trọng trong quá trình phát triển CNTT.

Trong cuốn sách này, chúng tôi chọn lọc và đưa ra các bài tập với các nội dung được phân bố theo 5 chương: Chương 1. Đại số quan hệ; Chương 2. Các vấn đề về phụ thuộc hàm; Chương 3. Khóa của lược đồ quan hệ; Chương 4: Các vấn đề về chuẩn hóa lược đồ quan hệ; Chương 5: Ngôn ngữ SQL. Mỗi chương được trình bày thành 3 phần chính:

Phần thứ nhất: Tóm tắt lý thuyết.

Phần thứ hai: Bài tập giải mẫu.

Phần thứ ba: Bài tập tự giải.

Mục tiêu cuối cùng của cuốn sách này là cung cấp toàn bộ những kiến thức cơ bản về lý thuyết thiết kế CSDL và các ngôn ngữ thao tác CSDL. Phần cuối của mỗi chương là các bài tập tự giải giúp cho người học hiểu sâu và kỹ hơn các kiến thức đã học.

Để đạt được điều mong muốn bạn đừng bỏ qua bài tập nào. Chúng tôi

tin rằng bạn sẽ hoàn toàn làm chủ về các vấn đề có liên quan đến CSDL.

Trong quá trình viết cuốn sách này, chắc chắn không tránh khỏi thiếu

sót, mong các bạn hãy đóng góp ý kiến cho chúng tôi.

Xin trân thành cảm ơn!

CHƯƠNG 1: MÔ HÌNH QUAN HỆ - CHUYỂN MÔ HÌNH E-R SANG MÔ HÌNH QUAN HỆ

A/NHẮC LẠI LÝ THUYẾT I. CÁC KHÁI NIỆM CỦA MÔ HÌNH QUAN HỆ 1. Quan hệ

Một quan hệ (hoặc trạng thái quan hệ) r của lược đồ quan hệ R (A1, A2, ..., An) được kí hiệu là r (R), là tập hợp các n-bộ r= { t1, t2, ..., tn}. Mỗi n - bộ t là một danh sách có thứ tự của n giá trị, t = < v1, v2, ..., vn >, trong đó mỗi vi, 1 <= i <= n, là một phần tử của DOM (Ai) hoặc là một giá trị không xác định (null value).

PHAI

Ví dụ về quan hệ SINHVIEN:

MaSV HONV DCHI

Nam

Nam NGAYSIN H 12/08/1955 Hưng Yên

Nữ

Nguyễn Văn Hưng Bùi Tuấn Minh 07/19/1985 Hà Nội

Nam

Lê Thu Hà 06/20/1988 Hải Dương

09/15/1963 Lạng Sơn Nguyễn Mạnh Linh 1010912 0 1010912 1 1010912 2 1010912 3

2. Lược đồ - Lược đồ quan hệ + Tên của quan hệ. + Tên của tập thuộc tính. - Lược đồ CSDL

Gồm nhiều lược đồ quan hệ.

Ví dụ lược đồ CSDL

NHANVIEN (MANV, TENNV, HONV, NS, DIACHI, GT, LUONG, PHG) PHONGBAN (MAPHG, TENPHG, TRPHG, NG_NHANCHUC) DIADIEM_PHG (MAPHG, DIADIEM) THANNHAN (MANV, TENTN, GT, NS, QUANHE) DEAN (TENDA, MADA, DIADIEM, PHG)

3. Bộ - Là các dòng của quan hệ (trừ dòng tiêu đề- tên của các thuộc tính). - Thể hiện dữ liệu cụ thể của các thuộc tính trong quan hệ.

Dữ liệu cụ thể của thuộc tính

4. Miền giá trị Là tập các giá trị nguyên tố gắn liền với một thuộc tính. Kiểu dữ liệu cơ sở: - Chuỗi ký tự(string) - Số(integer) Các kiểu dữ liệu phức tạp: - Tập hợp(set) - Danh sách(list) - Mảng(array) - Bản ghi(record) 5. Định nghĩa hình thức - Lược đồ quan hệ Cho A1, A2, ..., An là các thuộc tính Có các miền giá trị D1, D2,..., Dn tương ứng

Ký hiệu R (A1: D1, A2: D2, ..., An: Dn) là một lược đồ quan hệ

Bậc của lược đồ quan hệ là số lượng thuộc tính trong lược đồ:

TENNV

HONV

NGAYSINH DCHI

PHAI

Nguyễn Bùi Lê

12/08/1955 07/19/1985 06/20/1988

HVH

LUON G 40000 25000 43000

Tùng Hằng Như

Hùng

09/15/1963

638 NVC Q5 Nam 332 NTH Q1 Nữ Nữ 291 QPN Null

Nam

38000

Nguyễn

NHANVIEN (MANV: integer, TENNV: string, HONV: string, NGSINH: date, DCHI: string, LUONG: integer, GT: string, DONVI: integer) NHANVIEN là một lược đồ bậc 8 mô tả đối tượng nhân viên MANV là một thuộc tính có miền giá trị là số nguyên TENNV là một thuộc tính có miền giá trị là chuỗi ký tự - Quan hệ (hay thể hiện quan hệ) Một quan hệ r của lược đồ quan hệ R (A1, A2,..., An), ký hiệu r(R), là một tập các bộ r = {t1, t2,...,tk} Trong đó mỗi ti là một danh sách có thứ tự của n giá trị ti= Mỗi vi là một phần tử của miền giá trị DOM (Ai) hoặc giá trị rỗng.

Thể hiện mô hình quan hệ

hình

Mô quan hệ

Các quan hệ

Sự kiện về liên kết Sự kiện về thực thể

Tóm tắt các ký hiệu - Lược đồ quan hệ R (A1, A2,..., An)

- Tập thuộc tính của R

R+

- Quan hệ (hay thể hiện quan hệ)

R, S, P, Q

- Bộ

t, u, v

- Miền giá trị của thuộc tính A

DOM (A) hay MGT (A)

- Giá trị của thuộc tính A tại bộ thứ t

t.A hay t[A]

II. RÀNG BUỘC TOÀN VẸN - RBTV (Integrity Constraint): Là những quy tắc, điều kiện, ràng buộc cần được

thỏa mãn trong một thể hiện của CSDL quan hệ. - RBTV được mô tả khi định nghĩa lược đồ quan hệ. - RBTV được kiểm tra khi các quan hệ có thay đổi. 1. Siêu khóa Các bộ trong quan hệ phải khác nhau từng đôi một. Siêu khóa (Super Key) - Gọi SK là một tập con khác rỗng các thuộc tính của R - SK là siêu khóa khi

" r, " t1, t2 Є r, t1 ≠ t2 => t1[SK] ≠ t2[SK]

- Siêu khóa là tập các thuộc tính dùng để xác định tính duy nhất của mỗi bộ

trong quan hệ.

- Mọi lược đồ quan hệ có tối thiểu một siêu khóa. 2. Khóa Định nghĩa: - Gọi K là một tập con khác rỗng các thuộc tính của R - K là khóa nếu thỏa mãn đồng thời 2 điều kiện

K là một siêu khóa của R " K’ là tập con của K, K’ ≠ K, K’ không phải là siêu khóa của R

Nhận xét: - Giá trị của khóa dùng để nhận biết một bộ trong quan hệ. - Khóa là một đặc trưng của lược đồ quan hệ, không phụ thuộc vào thể hiện

quan hệ.

- Khóa được xây dựng dựa vào ý nghĩa của một số thuộc tính trong quan hệ.

- Lược đồ quan hệ có thể có nhiều khóa 3. Khóa chính Xét quan hệ:

NHANVIEN (MAVN, TENNV, HONV, NS, DCHI, GT, LUONG, PHG)

Có 2 khóa: MANV HONV, TENNV, NS

Khi cài đặt quan hệ thành bảng (table) chọn một khóa làm cơ sở để nhận biết các bộ: - Khóa có ít thuộc tính hơn - Khóa được chọn làm khóa chính (PK_primary key) - Các thuộc tính khóa chính phải có giá trị khác null. - Các thuộc tính khóa chính thường được gạch dưới.

NHANVIEN (MANV, TENNV, HONV, NS, DCHI, GT, LUONG, PHG)

4. Tham chiếu - Một bộ trong quan hệ R, tại thuộc tính A nếu nhận một giá trị từ một thuộc tính

B của quan hệ S, ta gọi R tham chiếu S. - Bộ được tham chiếu phải tồn tại trước.

MAPHG 5 4 1 TENPHG Nghiên cứu Điều hành Quản lý

5 4 4 5

TÊNNV HONV NGAYSINH DCHI LUONG PHG

Tùng Hằng Như Hùng 12/08/1955 07/19/1985 06/20/1988 09/15/1963 638 NVC Q5 40000 332 NTH Q1 25000 291 HTV Q6 43000 38000 Null Nguyễn Bùi Lê Nguyễn

5. Khóa ngoại Xét hai lược đồ R và S - Gọi FK là tập thuộc tính khác rỗng của R - FK là khóa ngoại (Foreign Key) của R khi

- Các thuộc tính trong FK phải có cùng miền giá trị với các thuộc tính khóa

chỉnh của S

- Giá trị FK của một bộ t1 Є R

+ Hoặc bằng giá trị tại khóa chính của một bộ t2 Є R + Hoặc bằng giá trị rỗng

Ví dụ : Quan hệ tham chiếu:

NHANVIEN (MANV, TENNV, HONV, NS, DCHI, GT, LUONG, PHG)

PHONGBAN (TENPHG, MAPHG)

Khóa ngoại

Khóa chính

Quan hệ bị tham chiếu

Nhận xét: - Trong một lược đồ quan hệ, một thuộc tính vừa có thể tham gia vào khóa

chính, vừa tham gia vào khóa ngoại.

- Khóa ngoại có thể tham chiếu đến khóa chính trên cùng một lược đồ quan hệ. - Có thể có nhiều khóa ngoại tham chiếu đến cùng một khóa chính.

Ràng buộc tham chiếu = ràng buộc khóa ngoại.

- Khóa ngoại bao gồm nhiều thuộc tính, nó không phải là khóa chính của bộ này

nhưng là khóa chính của bộ kia.

6. Biểu diễn ràng buộc tham chiếu

HONV

TENLOT TENNV MANV NS DCHI GT LUONG MA_NQL PHG

NHANVIEN

TENPHG

MAPHG

TRPHG NG_NHANCHUC

PHONGBAN

DIADIEM_PHG

MAPHG DIADIEM

TENDA

SODA

DIADIEM_DEAN

PHG

DEAN

MANV MADA THOIGIAN

PHANCONG

MANV TENTN

NS GT QUANHE

THANNHAN

III. CÁC ĐẶC TRƯNG CỦA QUAN HỆ - Thứ tự các bộ trong quan hệ là không quan trọng. - Thứ tự giữa các giá trị trong một bộ là quan trọng. - Mỗi giá trị trong một bộ:

+ Hoặc là một giá trị nguyên tố. + Hoặc là một giá trị rỗng (null).

- Không có bộ nào trùng nhau. IV. CHUYỂN LƯỢC ĐỒ E-R SANG LƯỢC ĐỒ QUAN HỆ Các quy tắc chuyển đổi 1. Tập thực thể

Các tập thực thể (trừ tập thực thể yếu) chuyển thành các quan hệ có cùng tên và tập thuộc tính. 2. Mối quan hệ a.Một –Một

Hoặc thêm vào quan hệ này thuộc tính khóa của quan hệ kia hoặc thêm thuộc

tính khóa vào cả hai quan hệ

b.Một – Nhiều

Thêm vào quan hệ một thuộc tính khóa của quan hệ nhiều.

c.Nhiều – Nhiều

Tạo ra một quan hệ mới có:

- Tên quan hệ là tên của mối quan hệ. - Thuộc tính là những thuộc tính khóa của các tập thực thể liên quan. 3. Thực thể yếu Chuyển thành một quan hệ có: - Cùng tên với thực thể yếu. - Thêm vào thuộc tính khóa của quan hệ liên quan. 4. Thuộc tính đa trị Chuyển thành một quan hệ: - Có cùng tên với thuộc tính đa trị. - Thuộc tính khóa của quan hệ này là khóa ngoại của quan hệ chứa thuộc tính đa

trị.

5. Liên kết đa ngôi (n>2) Chuyển thành một quan hệ: - Có cùng tên với tên mối liên kết đa ngôi. - Khóa chính là tổ hợp các khóa của tập các thực thể tham gia liên kết.

Mô hình quan hệ

Tổng kết: E-R - Loại thực thể - Quan hệ 1 ÷1, 1÷N - Quan hệ N÷M - Quan hệ đa ngôi - Thuộc tính - Quan hệ thực thể - Khóa ngoài - Quan hệ với 2 khóa ngoài - Quan hệ với n khóa ngoài - Thuộc tính

- Thuộc tính phức hợp - Thuộc tính đa trị - Tập các giá trị - Thuộc tính khóa - Tập các thuộc tính đơn - Quan hệ với khóa ngoài - Miền giá trị - Khóa chính (khóa dự tuyển)

B/ BÀI TẬP GIẢI MẪU Bài số1: Chuyển đổi một mô hình công ty sang ER

Giả sử chúng ta có kiểu liên kết ĐẠILÝ VẬTTƯ DỰÁN.

Đây là một kiểu liên kết cấp ba. Giả sử rằng kiểu thực thể ĐẠILÝ có thuộc tính

khoá là MãsốĐL, kiểu thực thể VẬTTƯ có thuộc tính khoá là MãsốVT, kiểu thực

thể DỰÁN có thuộc tính khoá là MãsốDA còn kiểu liên kết có thuộc

tính là Sốlượng để lưu số lượng vật tư mà một đai lý cung cấp cho môt dự án. Khi

đó kiểu liên kết sẽ được chuyển thành một quan hệ có tên là

CUNGCẤP với các thuộc tính MãsốĐL, MãsốVT , MãsốDA, Sốlượng và khoá

chính gồm ba thuộc tính MãsốĐL, MãsốVT , MãsốDA.

Trong những bài trước chúng ta đã phân tích và thiết kế mô hình ER cho bài

toán CÔNGTY.

Giả sử ta có kiểu thực thể ĐƠNVỊ với các thuộc tính là MãsốĐV, TênĐV,

ĐịađiểmĐV trong đó các thuộc tính khoá là MãsốĐV, TênĐV (do mỗi đơn vị có

một tên duy nhất), và ĐịađiểmĐV là một thuộc tính đa trị (do mỗi đơn vị có nhiều

địa điểm). Khi đó kiểu thực thể ĐƠNVỊ được chuyển thành quan hệ ĐƠNVI với

các thuộc tính MãsốĐV, TênĐV. Khoá chính của quan hệ là MãsốĐV (chọn một

trong hai thuộc tính khoá của kiểu thực thể).

Giả sử ta có kiểu liên kết NHÂNVIÊN CON trong đó NHÂNVIÊN là

kiểu thực thể chủ với các thuộc tính MãsốNV, Họđệm, Tên, Ngàysinh, Giớitính.

Thuộc tính khoá của NHÂNVIÊN là MãsốNV. CON là kiểu thực thể phụ thuộc

(vào thực thể NHÂNVIÊN) với các thuộc tính là Họtêncon, Ngàysinh, Giớitính.

Kiểu thực thể này không có thuộc tính khoá. Khi đó kiểu thực thể NHÂNVIÊN

được chuyển thành quan hệ NHÂNVIÊN với các thuộc tính như trên. Kiểu thực

thể CON được chuyển thành quan hệ CON với các thuộc tính MãsốNV, Họtêncon,

Ngàysinh, Giớitính. Quan hệ này có khoá ngoài là MãsốNV, khoá chính là Mã

sốNV, Họtêncon

Giả sử ta có kiểu liên kết NHÂNVIÊN ĐƠNVỊ, với các thuộc tính

của các kiểu thực thể giống như ở trên. Kiểu liên kết là một kiểu liên kết

1:1, đồng thời sự tham gia của NHÂNVIÊN vào kiểu liên kết là bộ phận (không

phải nhân viên nào cũng quản lý đơn vị), sự tham gia của ĐƠNVỊ là đầy đủ (một

đơn vị luôn luôn phải có một người quản lý). Khi đó, kiểu thực thể NHÂNVIÊN sẽ

được chuyển thành quan hệ NHÂNVIÊN với các thuộc tính của nó, còn kiểu thực

thể ĐƠNVỊ sẽ được chuyển thành quan hệ ĐƠNVỊ với các thuộc tính của kiểu

thực thể ĐƠNVỊ cộng thêm với thuộc tính MãsốNV và thuộc tính của kiểu liên kết

, nếu có. Thuộc tính MãsốNV sẽ là khoá ngoài cho quan hệ ĐƠNVỊ. Để

làm rõ vai trò người quản lý, khi chuyển sang quan hệ ĐƠNVỊ, người ta đổi tên

thuộc tính MãsốNV thành MãsốNQL (Mã số người quản lý). Ngoài ra, kiểu liên kết

có một thuộc tính là Ngàybắtđầu, thuộc tính này cũng được đưa vào quan

hệ ĐƠNVỊ

Giả sử ta có kiểu liên kết NHÂNVIÊN ĐƠNVỊ, trong đó

các kiểu thực thể NHÂNVIÊN, ĐƠNVỊ là các kiểu thực thể ở trên. Kiểu liên kết

là kiểu liên kết N:1 (một nhân viên chỉ làm việc cho một đơn vị và

mỗi đơn vị có nhiều nhân viên làm việc cho). Khi đó, Kiểu thực thể ĐƠNVỊ sẽ

được chuyển thành quan hệ ĐƠNVỊ với các thuộc tính của kiểu thực thể ĐƠNVỊ

còn kiểu thực thể NHÂNVIÊN sẽ được chuyển thành quan hệ NHÂNVIÊN với

các thuộc tính của kiểu thực thể NHÂNVIÊN cộng thêm với thuộc tính MãsốĐV

(là khoá chính của quan hệ ĐƠNVỊ). Thuộc tính MãsốĐV sẽ là thuộc tính khoá

ngoài của quan hệ NHÂNVIÊN.

Giả sử ta có kiểu liên kết NHÂNVIÊN DỰÁN. Kiểu thực thể

NHÂNVIÊN có các thuộc tính như trên với thuộc tính khoá là MãsốNV. Kiểu thực

thể DỰÁN có các thuộc tính là MãsốDA, TênDA, ĐịađiểmDA trong đó thuộc tính

khoá là MãsốDA. Kiểu liên kết < làm việc với> là một kiểu liên kết N:M (một

nhân viên có thể làm việc với nhiều dự án và mỗi dự án có nhiều nhân viên làm

việc với). Kiểu liên kết này có một thuộc tính là Sốgiờ để lưu số giờ mà mỗi nhân

viên làm việc cho một dự án. Khi đó kiểu liên kết sẽ được chuyển

thành một quan hệ có tên là NHÂNVIÊN_DỰ ÁN với các thuộc tính MãsốNV,

MãsốDA, Sốgiờ trong đó hai thuộc tính MãsốNV, MãsốDA tạo thành khoá chính

(phức hợp) cho quan hệ.

Xét kiểu thực thể ĐƠNVỊ ở trên. Thuộc tính ĐịađiểmĐV là một thuộc tính đa

trị. Khi chuyển thành mô hình quan hệ nó sẽ được chuyển thành một quan hệ có

khoá chính là MãsốĐV, Địa điểm và có thể có thêm một số thuộc tính khác lưu

thông tin về địa điểm.

Giả sử chúng ta có kiểu liên kết ĐẠILÝ VẬTTƯ DỰÁN.

Đây là một kiểu liên kết cấp ba. Giả sử rằng kiểu thực thể ĐẠILÝ có thuộc tính

khoá là MãsốĐL, kiểu thực thể VẬTTƯ có thuộc tính khoá là MãsốVT, kiểu thực

thể DỰÁN có thuộc tính khoá là MãsốDA còn kiểu liên kết có thuộc

tính là Sốlượng để lưu số lượng vật tư mà một đai lý cung cấp cho môt dự án. Khi

đó kiểu liên kết sẽ được chuyển thành một quan hệ có tên là

CUNGCẤP với các thuộc tính MãsốĐL, MãsốVT , MãsốDA, Sốlượng và khoá

chính gồm ba thuộc tính MãsốĐL, MãsốVT , MãsốDA.

Trong những bài trước chúng ta đã phân tích và thiết kế mô hình ER cho bài

toán CÔNGT.

Áp dụng các bước của thuật toán ở trên, chúng ta có mô hình quan hệ cho bài

toán CÔNGTY như sau:

NHÂNVIÊN (Họđệm, Tên, MãsốNV, Ngàysinh, Địachỉ, Giớitính, Lương,

MãsôNGS, MãsốĐV)

ĐƠNVỊ (TênĐV, MãsốĐV, MãsốNQL, Ngàybắtđầu)

ĐƠNVỊ_ĐỊAĐIỂM (MãsốĐV, ĐịađiểmĐV)

DỰÁN (TênDA, MãsốDA, ĐịađiểmDA, MãsốĐV)

NHÂNVIÊN_DỰÁN (MãsốNV, MãsốDA, Sốgiờ)

PHỤTHUỘC (MãsốNV, Têncon, Giớitính, Ngàysinh)

Dưới đây là mô hình quan hệ thể hiện liên kết giữa các quan hệ trên:

C/ BÀI TẬP TỰ GIẢI Bài số1 Chuyển đổi từ mô hình dữ liệu mô hình dữ liệu quan hệ sang ER DOCGIA (ma_docgia, ho, tenlot, ten, hinh). THEODOCGIA (ma_docg ia, ngaylapthe, ngayhethan) NGUOILON (ma_docgia, sonha, duong, quan, dienthoai, ngaysinh) TREEM (ma_docgia, ma_docgia_nguoilon, ngaysinh) TUSACH (ma_tuasach, tuasach, tacgia, tomtat) DAUSACH (isbn, ma_tuasach, ngonngu, bia, trangthai) CUONSACH (ma_cuonsach, isbn, tinhtrang) DANGKI (isbn, ma_docgia, ngay_dk, ghichu) PHIEUMUON (isbn, ma_cuonsach, ma_docgia , ngaymuon , ngaytra) PHIEUTRA (isbn, ma_cuonsach, ma_docgia , ngaymuon, ngaytrathatsu, tienphat) Bài số 2 Chuyển đổi từ mô hình dữ liệu mô hình dữ liệu quan hệ sang ER KHACH_HANG (SHKH, HOTEN, LOAI) RUOU_VANG (SHRV, VUNGNHO, NAMSX, DORUOU) NHA_SX (SHNSX, HOTEN, THANHPHO) SAN_PHAM (SHRV, SHNSX) (SHKH: số hiệu khách hàng SHRV: số hiệu rượu vang SHNSX: số hiệu nhà sản xuất ) Bài số 3 Vẽ lược đồ quản lý đề án công ty: CSDL đề án công ty theo dõi các thông tin liên quan đến nhân viên, phòng ban và đề án - Cty có nhiều phòng ban, mỗi phòng ban có tên duy nhất, mã phòng duy nhất, một trưởng phòng và ngày nhận chức. Mỗi phòng ban có thể ở nhiều địa điểm khác nhau.

- Đề án có tên duy nhất, mã duy nhất, do 1 một phòng ban chủ trì và được triển

khai ở 1 địa điểm.

- Nhân viên có mã số, tên, địa chỉ, ngày sinh, phái và lương. Mỗi nhân viên làm việc ở 1 phòng ban, tham gia vào các đề án với số giờ làm việc khác nhau. Mỗi nhân viên đều có một người quản lý trực tiếp.

- Một nhân viên có thể có nhiều thân nhân. Mỗi thân nhân có tên, phái, ngày sinh

và mối quan hệ với nhân viên đó. Bài số4 Vẽ lược đồ quản lí trường học.

- Một nhà trường có nhiều khoa, mỗi khoa có nhiều giáo viên, mỗi giáo viên có thể

dạy nhiều lớp.

- Mỗi lớp có nhiều sinh viên, mỗi sinh viên có masv, hoten, quequan, diemthi. - Mỗi khoa có nhiều giáo viên, mỗi giáo viên có magv, têngv, quequan - Mỗi giáo viên có thân nhân, thân nhân có matn, hoten, tuoi. - Mỗi môn có nhiều tiết học, mỗi tiết học có matiet, tentiet, sotiet, sotc. - Mỗi lớp có malop, tenlop.

CHƯƠNG 2 ĐẠI SỐ QUAN HỆ

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC  Phân biệt các phép toán trên quan hệ, các tính chất của đại số quan hệ.  Kết hợp các phép toán để giải quyết các yêu cầu cụ thể. A. NHẮC LẠI LÝ THUYẾT I. CÁC PHÉP TOÁN ĐẠI SỐ QUAN HỆ 1. Phép hợp

Cho hai quan hệ R và S có cùng tập thuộc tính là U, f „ X ˝ U là một tập con các thuộc tính của U, phép chiếu của quan hệ R lên thuộc tính X, được ký hiệu là R[X], đó là một quan hệ trên tập thuộc tính X, và được ký hiệu như sau:

R + S = {t | t € R hoặc t € S}

2. Phép giao

Cho hai quan hệ R và S, có cùng tập thuộc tính U, giao của hai quan hệ R và S, kí hiệu R.S, là một quan hệ trên tập thuộc tính U và chỉ gồm tất cả các bộ t vừa thuộc R vừa thuộc S, tức là:

R.S = {t | t € R và t € S}

3. Phép hiệu

Cho R và S là hai quan hệ trên tập thuộc tính U, hiệu hai quan hệ R và S, kí hiệu R\S, là một quan hệ trên tập thuộc tính U, và được xác định như sau:

R – S = {t | t € R và tS}

4. Phép chọn

Cho quan hệ R trên tập thuộc tính U và E là biểu thức chọn trên tập thuộc tính U, phép chọn quan hệ R theo biểu thức chọn E được ký hiệu là R(E), đó là một quan hệ trên tập thuộc tính U, và được xác định như sau:

R (E) = {t | t € R và t (E)}

5. Phép chiếu

„ X ˝ U là một tập con các thuộc tính của Cho quan hệ R trên tập thuộc tính U, f U, phép chiếu trên quan R lên tập thuộc tính X, được ký hiệu là R[X], đó là một quan hệ trên tập thuộc tính X, và được xác định như sau:

R[X] = { t[X] | t € R }

6. Phép chia

Cho lược đồ quan hệ R = {A1, A2, ... , An}. Cho quan hệ R(U), và S(V), với ˘ „ V ˝ U, đặt X=U\V. Phép chia quan hệ R cho quan hệ S, ký hiệu là R÷S là một quan hệ trên tập thuộc tính X và được xác định:

R÷S = {t[X] \ t € và V € S và V>€R}

Trong định nghĩa trên chú ý rằng ký hiệu là sự ghép vào đúng vị trí của hai xâu t và u. 7. Phép kết nối θ - Sau đây ta sẽ xét phép kết nối theo toán tử θ, với θ là một toán tử so sánh số học

hai ngôi (=, <, >, ≤, ≥, ≠).

- Cho thuôc tính A € U, B € V, t1, t2 lần lượt là hai bộ trên tập thuộc tính U và V. Khi đó, t1, t2, có thể kết nối với nhau nếu t1[A] θ t2[B], ký hiệu là t= là kết quả của kết nối t1, t2.

- Cho hai quan hệ R(U) và S(V), θ là phép so sánh, A € U, B € V. Phép kết nối

quan hệ R và S theo điều kiện A θ B được ký hiệu là:

 S = { t | t1 R, t2 S, t= sao cho t1[A] t2[B] } BA θ

*/ Phép kết nối tự nhiên Định nghĩa: cho hai quan hệ R (U), S (V), đặt X = U X, phép kết nối tự nhiên của quan hệ R và S, ký hiệu là R*S, được xác định như sau:

R*S = { t\ $ t1 ˛ R, t2 ˛ S để t1[X] = t2[X]}

II. CÁC VÍ DỤ Ví dụ 1 Đây là phép chiếu trên quan hệ R

R A B C D A C R[A C]

a1 c1 d1 a1 b3 c1

a2 c1 d3 a2 b2 c1

c1 d2 a1 b1 a3 c2

c2 d5 a3 b1

c1 d6 a1 b3

Ví dụ 2 Đây là phép kết nối trên hai quan hệ Giả sử R và S là là các quan hệ như sau:

R A B C S D E

1 2 3 3 1

4 5 6 6 2

7 8 9

 S D

Khi đó ta có R

A B C D E

1 2 3 3 1

1 2 3 6 2

4 5 6 6 2

Ví dụ 3 Đây là phép nối tự nhiên trên hai quan hệ Cho hai quan hệ R và S như sau: R C D A C B S R*S A B C D

a1 b1 c1 a1 b1 c1 d1 c1 d1

a2 b2 c2 a1 b1 c1 d2 c1 d2

a1 b1 c3 a2 b2 c2 d3 c2 d3

a3 b3 c4 a1 b1 c3 d4 c3 d4

Ví dụ 4 Đây là phép tích đề các trên hai quan hệ S R C D A B R*S A B C D

a1 b1 c1 d1 A1 b1 c1 d1

a2 b2 c2 d2 A1 b1 c2 d2

a1 b3 A2 b2 c1 d1

A2 b2 c2 d2

A1 b3 c1 d1

A1 b3 c2 d2

Ví dụ 5 Đây là phép chia quan hệ R cho quan hê S

R S R S

C D C d f E A B a1 b1 a2 b2

A B C D d a1 b1 c f a1 b1 e d a2 b2 c f a2 b2 e f a3 b1 e e a4 b2 d

R(E) A B C

7 5 a2

6 6 a1

8 5 a3

Ví dụ 6 Đây là phép chọn trên quan hệ R, biểuthức chọn là E = B≥ C khi đó:

R B C A

1 3 a1

7 5 a2

6 6 a1

8 5 a3

III. MỘT SỐ LƯU Ý  Khi bài toán cần sử dụng nhiều phép toán cần phải kết hợp các phép toán sao

cho hạn chế dung lượng nhớ cho các kết quả trung gian.

 Khi bài toán có sử dụng phép chiếu, chọn, kết nối nên thực hiện phép toán

chiếu, chọn xuống dưới nhất (gốc của cây đại số quan hệ) có thể.

B. BÀI TẬP GIẢI MẪU

Bài số 1 Thực hiện phép chọn trên quan hệ SV(Hoten, namsinh, CSDL, FOX). Xét hồ sơ kết quả thi của sinh viên. Quan hệ này gọi là SV. Giả sử có quan hệ SV như sau: TT Hoten namsinh CSDL FOX

1 1983 7 5 Tuấn Anh

2 Huy Công 1982 8 3

3 1984 8 9 Thanh Hương

4 Bình Minh 1986 2 3

Giả sử, điều kiện E là sinh viên có ít nhất một điểm kém. Vậy SV(E), E=(CSDL<5 v FOX<5 ). Khi đó kết quả SV(CSDL<5 v FOX <5):

TT Hoten namsinh CSDL FOX

2 Huy Công 1982 8 3

4 Bình Minh 1986 2 3

Bài tập 2

Kết hợp các phép toán của ngôn ngữ đại số quan hệ. Cho CSDL gồm có ba quan hệ như sau: NCC (MaNCC, TenNCC, DCNCC, DT) SP (MaSP, TenSP, Loai) SP_NCC (MaNCC, MaSP, SL) Giải thích một số từ viết tắt: - MaNCC là mã số nhà cung cấp. - TenNCC là tên nhà cung cấp có mã số tương ứng. - DCNCC là địa chỉ của nhà cung cấp. - DT là điện thoại nhà cung cấp. - MaSP là mã số sản phẩm. - TenSP là tên của sản phẩm. - Loai là chủng loại của mặt hàng.

- SL là số lượng đã cung cấp. - Quan hệ NCC(nhà cung cấp) dùng để lưu trữ một số thông tin về các nhà cung

cấp.

- Quan hệ SP(sản phẩm) dùng để lưu trữ một số thông tin của các mặt hàng. - Quan hệ SP_NCC dùng để lưu trữ một số thông tin về việc cung ứng sản phẩm

của NCC.

Hãy viết biểu thức đại số quan hệ cho biết: a. Cho biết tên của nhà cung cấp có địa chỉ là Hưng Yên. b. Cho biết tên của các sản phẩm đã cung ứng bởi nhà cung cấp có mã số là KC. c. Cho biết tên, địa chỉ của các nhà cung cấp đã cung ứng các sản phẩm có số lượng là 50 d. Cho biết tên, địa chỉ của các nhà cung cấp không cung ứng sản phẩm nào. e. Cho biết tên, địa chỉ, số điện thoại của các nhà cung cấp đã cung ứng ít nhất một sản phẩm. f. Cho biết tên nhà của các nhà cung cấp đã cung ứng tất cả các sản phẩm. Hướng dẫn: a. Ta cần chiếu để lấy tên nhà cung cấp kết hợp với phép chọn với điều kiện chọn là DCNCC = ’Hưng Yên’, các thông tin này lấy trong quan hệ NCC, ta thực hiện như sau: NCC(DCNCC=’Hưng Yên’)[TenNCC] b. Các thông tin lấy trong hai quan hệ là SP và SP_NCC, với yêu cầu này cần thực hiện ba phép toán là kết nối, chọn, chiếu. Có hai cách để thực hiện yêu cầu này:

+/ C1: thực hiện phép toán kết nối hai quan hệ SP, SP_NCC, phép chọn, phép chiếu.

(SP*SP_NCC)(MaNCC=’KC’)[TenSP]

Thực hiện phép chọn trên quan hệ SP_NCC, sau đó thực hiện phép kết nối giữa hai quan hệ kết quả trên với quan hệ trung gian, cuối cùng là chiếu lấy tên sản phẩm thỏa mãn trên quan hệ vừa thu được.

(SP_NCC(MaNCC=’KC’)*SP)[TenSP]

c. Thực hiện phép kết nối giữa hai quan hệ NCC và SP_NCC, biểu thức chọn SL=50 sau đó chiếu trên TenNCC, DCNCC.

(NCC*SP_NCC(SL=50))[TenNCC, DCNCC]

d. Nhà cung ứng không cung cấp một sản phẩm nào tức là MaNCC đó không xuất hiện ở trong quan hệ SP_NCC.

NCC[TenNCC, DCNCC]-(NCC*SP_NCC)[TenNCC, DCNCC]

e. Nhà cung cấp cung ứng ít nhất một sản phẩm là MaNCC đó xuất hiện ít nhất một lần trong quan hệ SP_NCC.

(NCC*SP_NCC)[TenNCC, DCNCC, DT]

f. Để tìm nhà cung cấp đã cung ứng tất cả các sản phẩm, chúng ta sử dụng phép chia giữa hai quan hệ: (NCC*SP_NCC)[TenNCC, MaSP] và SP[MaSP]

(NCC*SP_NCC)[TenNCC, MaSP] ÷ SP[MaSP]

C. BÀI TẬP TỰ GIẢI Bài tập 1 Các phép toán trên hai quan hệ. Cho hai quan hệ R và S như sau:

R S

C B A D B A C D

0 0 1 0 1 2 1 1

0 1 1 0 2 2 1 1

1 1 1 0 1 1 1 0

1 1 1 1 y X z v

a. Tính R-S và S-R. b. Tính R÷S. c. Tính R*S. d. Giả sử X = {A, B, C}, Y = {A, C, D}, tính các quan hệ chiếu R[X], R[Y] và

S[Y], (R÷S)[X], (R÷S)[X U Y].

e. Chứng minh rằng với mọi quan hệ R, S, Q thì ta luôn có:

R*S=S*R và R÷S=S÷R (Tính giao hoán) R*(Q+S) = (R*Q) + (R*S) (Tính kết hợp) (R+S)[X] = R[X] + S[X] (R*S)[X] = R[X]*S[X]

Bài số 2 Tích đề các giữa hai quan hệ. Tính R*S của hai quan hệ R và S như sau:

S R

A B C D A B C D

0 0 0 0 a b C d

0 0 1 1 x y Z v

0 1 1 1

Bài số 3 Phép chia giữa hai quan hệ. Cho biết kêt quả của phép chia hai quan hệ R và S.

R S

A B C D E

A B 0 0 0 0 1

1 1 0 0 1 1 0

1 0 1 1 1 1 1

1 0 1 1 1

Bài số 4 Hợp dữ liệu của hai quan hệ. Cho hai quan hệ R và S như sau:

R S

TT Ten NS GT Que NH DIEM

77 1 Linh Nu HN Anh 18

76 2 Quyen Nu HP Hoa 20

75 3 Nam Nam SG Toan 22

74 4 Tuan Nam VP Tin hoc 22

Hãy viết các phép toán quan hệ để viết biểu thức quan hệ cho kết quả sau:

NS TT Ten GT Que NH DIEM

77 1 Linh Nu HN Anh 18

76 2 Quyen Nu HP Hoa 20

75 3 Nam Nam SG Toan 22

74 4 Tuan Nam VP Tin hoc 22

Bài số 5 Tổng hợp các phép toán đại số quan hệ. Cho cơ sở dữ liệu gồm 3 quan hệ: SV (MSV, HT, NS, QUE)

ĐT (MĐT, TĐT, GV, KP) TT (MSV, MĐT, NTT, KQ)

Trong đó: MSV: mã sinh viên

HT: họ tên sinh viên QUE: quê quán TĐT: tên đề tài KP: kinh phí KQ: kết quả

NS: năm sinh MĐT: mã đề tài GV: giáo viên NTT: nơi thực tập Hãy trả lời các câu hỏi sau dưới dạng biểu thức quan hệ:

a. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Hà Tây và có kết

quả thực tập khá (KQ>=7).

b. Cho biết tên của các sịnh viên có kết quả thực tập khá và thực tập tại quê hoặc

thực tập tại Hưng Yên.

c. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Thái Bình và

thực tập đề tài có kinh phí lớn hơn 3 triệu.

d. Cho biết tên của các sinh viên có kết quả thực tập khá và thực tập đề tài có

kinh phí lớn hơn 6 triệu.

e. Danh sách sinh viên thực tập tại quê nhà. f. Thông tin về các đề tài có sinh viên thực tập. g. Cho biết mã của các đề tài không có sinh viên nào tham gia. h. Cho biết mã của các đề tài có kinh phí nằm trong khoảng 1 đến 2,5 triệu. i. Cho biết mã của sinh viên sinh trước năm 1988 và có kết quả thực tập khá

(KQ>=7).

Bài số 6 Thao tác trên một cơ sở dữ liệu. Cho cơ sở dữ liệu gồm các quan hệ sau: Quan hệ SV:

Mô tả Mã sinh viên

Họ tên sinh viên Giới tính (‘M’-nam, ‘F’-nu)

Tên thuộc tính MASV HOTEN GT NGAYSINH Ngày sinh MALOP TINH HOCBONG Mã lớp Tỉnh Học bổng

Quan hệ LOP:

Tên thuộc tính MALOP TENLOP SISO MAKHOA Mô tả Mã lớp Tên lớp Sĩ số Mã khoa

Mô tả Mã khoa Tên khoa Số cán bộ giảng dạy

Tên môn học Số tiết

Quan hệ KH (Khoa): Tên thuộc tính MAKHOA TENKHOA SOCBGD Quan hệ MH (Môn học) Mô tả Tên thuộc tính MAMH Mã môn học TENMH SOTIET Quan hệ KQ (Kết quả):

Mã sinh viên Mã môn học

Tên thuộc tính Mô tả MASV MAMH DIEMTHI Điểm thi

Hãy trả lời các câu hỏi sau dưới dạng biểu thức quan hệ: a. Cho biết mã, tên sinh viên có ngày sinh trước ngày ’20/02/1985’ và thuộc tỉnh

Thái Nguyên.

b. Cho biết tên sinh viên nữ thuộc lớp ‘TK2’ được học bổng 180 nghìn. c. Cho biết sĩ số của lớp có mã ‘TK1’. d. Cho biết mã, tên của các lớp thuộc khoa có mã ‘CNTT’. e. Cho biết tên khoa có số cán bộ giảng dạy lớn hơn 20. f. Cho biết tên môn có số tiết lớn hơn 30. g. Cho biết tên môn, số tiết ứng với sinh viên có mã là ‘101041010’. h. Cho biết danh sách gồm tên sinh viên, tên lớp của các sinh viên có điểm thi

<5.

i. Cho biêt tên sinh viên thuộc lớp có mã là ‘TK2’ không có điểm thi môn nào

<5. Bài số 7 Thao tác trên một cơ sở dữ liệu. Cho lược đồ CSDL dùng để quản lý lao động bao gồm các lược đồ quan hệ sau: - Nhanvien (MANV, HOTEN, NGAYSINH, PHAI, DIACHI, MAPB)

Mỗi nhân viên có một mã số nhân viên (MANV) duy nhất. Một mã số nhân viên xác định các thông tin như họ tên (HOTEN), ngày sinh(NGAYSINH), phái (PHAI), địa chỉ(DIACHI), và phòng ban(MAPB) nơi quản lý nhân viên.

- Phongban (MAPB, TENPB)

Mỗi phòng ban có một mã phòng ban (MAPB) duy nhất, mã phòng ban xác định tên phòng ban (TENPB).

- Cong (MACT, MANV, SLNGAYCONG) Lược đồ quan hệ Cong ghi nhận số lượng ngày công(SLNGAYCONG) của một nhân viên(MANV) tham gia vào công trình(MACT).

- Congtrinh(MACT, TENCT, DIADIEM, NGAYCAPGP, NGAYKC,

NGAYHT) Mỗi công trình có một mã công trình (MACT) duy nhất. Mã số công trình xác đinh các thông tin như tên công trình(TENCT), địa điểm(DIADIEM), ngày công trình được cấp giấy phép xây dựng(NGAYCAPGP), ngày khởi công(NGAYKC), ngày hoàn thành(NGAYHT). Hãy thực hiện các câu hỏi sau bằng ngôn ngữ đại số quan hệ: a. Danh sách những nhân viên có tham gia vào công trình có mã công trình là X. Yêu cầu các thông tin: MANV, HOTEN, SLNGAYCONG, trong đó mã nhân viên được sắp tăng dần.

b. Đếm số lượng ngày công của mỗi công trình. Yêu cầu các thông tin: MACT, TENCT, TONGNGAYCONG (TONGNGAYCONG là thuộc tính tự đặt). c. Danh sách những nhân viên có sinh nhật trong tháng 8. Yêu cầu các thông tin: MANV, TENNV, NGAYSINH, DIACHI, TENPB, sắp xếp quan hệ kết quả theo thứ tự tuổi giảm dần.

d. Đếm số lượng nhân viên của mỗi phòng ban. Yêu cầu các thông tin: MAPB,

TENPB, SOLUONG (SOLUONG là thuộc tính tự đặt).

Bài số 8 Thao tác trên một cơ sở dữ liệu. Cho các quan hệ sau: Monhoc (MSMH, TENMH, SOTINCHI, TINHCHAT) MSMH: mã số môn học TENMH: tên môn học

SOTINCHI: số lượng tín chỉ TINHCHAT bằng 1 nếu đó là môn học bắt buộc, bằng 0 nếu đó là môn học không bắt buộc Sinhvien (MSSV, HOTEN, NGAYSINH, LOP)

MSSV: mã số sinh viên HOTEN: họ tên sinh viên NGAYSINH: ngày sinh LOP: lớp

Diem (MSSV, MSMH, DIEMTHI) DIEMTHI: điểm thi

Hãy thực hiện câu hỏi sau bằng ngôn ngữ đại số quan hệ: a. Hãy liệt kê danh sách gồm: MSSV, HOTEN, LOP, DIEMTHI của những sinh

viên thi môn CSDL, theo thứ tự LOP, DIEMTHI.

b. Hãy cho biết phiếu điểm của sinh viên có mã sô là 10109119. c. Hãy liệt kê danh sách gồm MSSV, HOTEN, LOP, DIEMTRUNGBINH của những sinh viên có điểm trung bình các môn dưới 5, theo thứ tự LOP, HOTEN.

Bài tập9 Tổng hợp các phép toán đại số quan hệ. Dựa vào lược đồ cơ sở dữ liệu. Khach (MAKH, HOTEN, DIACHI, DIENTHOAI) Hoadon (SOHD, NGAYLAPHD, NGAYBAN, MAKH) DongHoaDon (SOHD, MAHANG, SLBAN) Hang (MAHANG, TENHANG, DONGIA, DVT, MANHOM) Nhom (MANHOM, TENNHOM) Hãy thực hiện các câu hỏi sau bằng ngôn ngữ đại số quan hệ: a. Danh sách các khách hàng đã mua hàng trong ngày d. Yêu cầu các thông tin:

MAKH, HOTEN, DIACHI, DIENTHOAI.

b. Danh sách các mặt hàng trong số hóa đơn(SOHD) là x. Yêu cầu các thông tin: MAHANG, TENHANG, SLBAN, DONGIA, THANHTIEN(THANHTIEN là thuộc tính tự đặt, THANHTIEN=SLBAN*DONGIA). Yêu cầu sắp xếp theo cột TENHANG.

c. Danh sách các mặt hàng thuộc mã nhóm hàng là A có đơn giá cao nhất. Yêu

cầu các thông tin: MAHANG, TENHANG, DONGIA.

d. Danh sách các khách hàng đã mua các mặt hàng có mã nhóm hàng là A trong ngày e. Yêu cầu các thông tin: MAKH, HOTEN, DIACHI, DIENTHOAI, TENHANG.

e. Thống kê việc mua hàng trong năm 2002 của khách hàng có mã khách hàng là KH01 (theo từng hóa đơn). Yêu cầu các thông tin: MAKH, HOTEN, SOHD, TRIGIAHD trong đó TRIGIAHD là tổng số tiền trong một hóa đơn (TRIGIAHD là thuộc tính tự đặt).

(MALICH, TUTIET, DENTIET, BAIDAY, GHICHU,

Bài số 10 Tổng hợp các phép toán đại số quan hệ. Dựa vào lược đồ cơ sở dữ liệu. Giaovien (MAGV, HOTEN, DTGV, MAKHOA) Khoa (MAKHOA, TENKHOA, DTKHOA) Lop (MALOP, TENLOP, SISO, MAKHOA) Monhoc (MAMH, TENMH) Phonghoc (SOPHONG, CHUCNANG) Lichbaogiang (MALICH, NGAYDAY, MAGV) Dongbaogiang LYTHUYET, MAMH, MALO, SOPHONG) Hãy thực hiện các câu hỏi sau bằng ngôn ngữ đại số quan hệ: a. Xem lịch báo giảng tuần từ ngày 16/09/2002 đến 23/09/2002 của giáo viên có MAGV là TH3A040. Yêu cầu các thông tin: MAGV, HOTEN, TENLOP, TENMH, SOPHONG.

b. Xem lịch báo giảng ngày 23/09/2002 của các giáo viên có mã khoa CNTT. Yêu cầu các thông tin: MAGV, HOTEN, TENLOP, TENMH, SOPHONG, NGAYDAY, TUTIET, DENTIET, BAIDAY, GHICHU.

Bài số 11 Tìm ví dụ chứng tỏ các phép toán trừ và chia không có tính kết hợp. Bài số 12 Chứng tỏ rằng với mọi cặp quan hệ tương thích R và S ta có: R - (R - S) = R & S.

Bài số 13 Chứng minh rằng với mọi quan hệ R (U) ta có:

R * R = R R + R = R R & R = R R – R = R R : R = ø, Attr (R: R) = ø

Bài số 14 Chứng minh rằng phép chia có thể được biểu diễn qua các phép chiếu, kết nối và trừ như sau:

R: S = R [M]-(R [M]*S-R) [M]

Trong đó, M=Attr (R)-Attr (S).

CHƯƠNG 3: CÁC VẤN ĐỀ VỀ PHỤ THUỘC HÀM

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC  Hiểu được tầm quan trọng của lý thuyết của phụ thuộc hàm  Vận dụng các thuật toán tính bao đóng, định nghĩa suy diễn theo tiên đề, theo quan hệ, tìm phủ tối thiểu, bài toán thành viên để giải quyết các bài tập cụ thể.

 Áp dụng các thuật toán để giải quyết các bài tập liên quan: Tìm bao đóng, chứng minh một phụ thuộc hàm có dư thừa trong tập các phụ thuộc hàm không,...

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

I. MỘT SỐ ĐỊNH NGHĨA, TÍNH CHẤT

1. Định nghĩa phụ thuộc hàm Định nghĩa 1: cho U là một tập thuộc tính, một phụ thuộc hàm trên U là một phát biểu có dạng X→Y, trong đó X,Y˝ U. Cho R là quan hệ trên tập thuộc tính U, nói rằng quan hệ R thoả mãn phụ thuộc hàm X→Y, nếu với 2 bộ bất kì trong R mà chúng giống nhau trên tập thuộc tính X thì chúng cũng giống nhau trên tập thuộc tính Y, nghĩa là " u,v ˛ R, nếu u.X=v.X thì u.Y=v.Y. Nếu f = X→Y là một phụ thuộc hàm trên U thì ta nói tập thuộc tính Y phụ thuộc hàm vào tập thuộc tính X (Y functional dependent on X ) hoặc tập thuộc tính X xác định hàm tập thuộc tính Y (X functional determines Y). Cho f = X→Y là một phụ thuộc hàm trên U, nếu quan hệ R thoả mãn phụ thuộc hàm f thì ta ký hiệu R(f), nếu R không thoả mãn phụ thuộc hàm thì ta ký hiệu ø R(f).Như vậy nếu R(X→Y) ↔" u,v ˛ R, nếu u.X=v.X thì u.Y=v.Y. Cho F là một tập các phụ thuộc hàm trên U, nói rằng quan hệ R thoả mãn tập f ˛ F thì R(f) hay nói phụ thuộc hàm F, ký hiệu là R(F) nếu và chỉ nếu với "

f ˛ F thì R(f).

một cách tương đương quan hệ R thoả mãn tập phụ thuộc hàm F nếu như nó thoả mãn từng phụ thuộc hàm trong tập đó,hay R(F) ↔" Định nghĩa 2: Lược đồ quan hệ là một cặp a =(U, F) trong đó U là tập hữu hạn các thuộc tính còn F là tập các phụ thuộc hàm trên U. Định nghĩa 3: Cho U là một tập thuộc tính X, Y ˝ U,nếu Y˝ X thì phụ thuộc hàm X→Y được gọi là phụ thuộc hàm hiển nhiên. Nhận xét : 1. Cho U là một tập thuộc tính, kí hiệu n=| U| ,suy ra số các tập con của U là 2n

(tính cả tập rỗng)

2. Nếu X ˝ U thì phụ thuộc hàm X→ Ø đúng trên mọi quan hệ R của U. 3. Phụ thuộc hàm Ø → X ( X ˝ U) chỉ đúng trên các quan hệ có cùng giá trị

trên tập thuộc tính X.

4. Số các phụ thuộc hàm trên U có thể có là 2n *2n =22n (tính cả phụ thuộc hàm

X→ Ø và Ø → X )

X→Y

X→Z

2. Một số tính chất của phụ thuộc hàm 1) Tính chất phản xạ: X, YU, YX, thì X→Y 2) Tính chất bắc cầu: X, Y, ZU, nếu có X→Y và Y→Z thì X→Z 3) Tính chất gia tăng: X, YU, nếu X→ Y và ZU thì XZ→YZ 4) Tính chất tựa bắc cầu: X, Y, Z, W U, nếu X→Y, YZ→ W thì XZ→W 5) Tính chất phản xạ chặt: XU thì X→X

6) Luật tách: X, Y, Z U, nếu có X→YZ thì có: 7) Luật hợp: X, Y, Z U, nếu có X→ Y và X→Z thì có X→YZ Tính chất cộng tính: X, Y, Z, W U, nếu X→Y, Z→ W thì XZ→YW

3. Hệ tiên đề Amstrong

F1 - Luật phản xạ X,YU, nếu XY thì Y→ X F2 - Bắc cầu X, Y, Z U nếu

X→Y Y →Z

thì X→Z

Y →Z

F3 - Luật gia tăng X, Y, Z U, nếu có X→Y thì XZ→YZ

4. Định nghĩa suy dẫn theo hệ tiên đề

Cho F là tập phụ thuộc hàm trên U, f là một phụ thuộc hàm trên U ( f có thể không thuộc F), nói rằng f suy dẫn được từ F theo hệ tiên đề Amstrong và kí hiệu là F├ f nếu như f có thể nhận được từ tập F sau một số hữu hạn lần áp dụng các luật của hệ tiên đề Amstrong. Nhận xét: Với " f ˛ F thì F├ f

Kí hiệu F+ là tập tất cả các phụ thuộc hàm được suy dẫn từ tập F theo hệ tiên đề Amstrong. Ta thấy F˝ F+ F+ được gọi là bao đóng của tập phụ thuộc hàm F, nếu F+ =F thì ta nói F là một tập đầy đủ các phụ thuộc hàm, đôi khi ta còn nói F là tập đóng.

5. Định nghĩa suy dẫn theo quan hệ

Cho F là một tập các phụ thuộc hàm trên tập thuộc tính U, f là một phụ thuộc hàm trên U, (f có thể không thuộc F), nói rằng f được suy dẫn từ tập F theo quan hệ và ký hiệu F ╞f, nếu và chỉ nếu với mọi quan hệ R trên U, nếu R thoả mãn F thì R cũng thoả mãn f.

f ˛ F thì F ╞f từ đây ta suy ra F ˝ F*.

Ký hiệu F* là tập tất cả các phụ thuộc hàm được suy dẫn từ tập F theo quan hệ. F*={f:X→Y | X,Y˝ U, F╞f} Tính chất của F*: Cho F và G là hai tập phụ hàm trên tập thuộc tính U khi đó ta có: 1. Tính phản xạ: Với " 2. Tính đơn điệu: Nếu F˝ G thì F* ˝ G*.

3. Tính luỹ đẳng: Với mọi tập phụ thuộc hàm F thì ta luôn có (F*)*=F*.

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

Cho tập phụ thuộc hàm F trên U, X˝ U, bao đóng của tập thuộc tính X, kí

hiệu là X+ được xác định như sau:

X+= { A | AU và X→AF+ }

f F thì fF*,suy ra FF* f F thì fF+ ,suy ra FF+,tương tự "

1. Phản xạ " X˝ U thì X →X+ 2. Tính đơn điệu " X,Y ˝ U,nếu Y ˝ U thì X+˝ Y+ 3. X+→X F+ và X→X+F+ 4. Tính lũy đẳng ((X+))=X+ 5. (X+ Y+)=(XY+)+ 6. X→YF+ khi và chỉ khi Y˝ X+hay X→Y suy dẫn được từ F khi và chỉ khi

Nhận xét: Với một tập F cho trước ta luôn có: - X+ ˝ U - " X,Y ˝ U,Y˝ X,thì X→YF+ - " - " X,Y,Z ˝ U,nếu X→YF+ và Y→ZF+ thì X→ZF+ - X ˝ U,A F+khi và chỉ khi X→AF+ Một số tính chất của bao đóng tập thuộc tính

Y˝ X+

7. X+ =Y+ khi và chỉ khi X→YF+ và Y →XF+

Thuật toán tìm bao đóng của một tập thuộc tính Input a = (U,F), X˝ U Output X+ =? Thuật toán Ta xác định dãy X(0), X(1), X(2),... theo quy nạp như sau 1. Đặt X(0)=X 2. Giả sử rằng đã xây dựng được đến bước thứ i tức là đã biết X(i) (i>=0) 3. Xây dựng tiếp bước i+1 như sau X(i+1)= X(i) ¨ Z(i) trong đó

˛ F (1)

Xj→Yj

˝ Xi

(2)

¸ X(i)

(3)

Z(i) = ¨ Yj với điều kiện :

¸ X+ thì kết

ﬁ b ˝ X+ và b , nếu a

b . Vì vậy Z(i) chính là hợp của các vế phải của các phụ thuộc hàm trong tập F mà có vế trái là tập con của tập trước mà có vế phải chưa được thêm vào. Điều kiện (3) chỉ có tác dụng tăng tốc độ tính toán Nhận xét: X(0), X(1), X(2),... là một dãy không giảm và bị chặn trên bởi U, do đó tồn tại chỉ số i nào đó để X(i)= X(i+1) (*), gọi i là chỉ số nhỏ nhất khi đó X+ = X(i) hay khi X(i) = U thì X+ = X(i) = U. Thuật toán bằng ngôn ngữ tựa Pascal Input: Tập thuộc tính X cần tính bao đóng trên lược đồ quan hệ R=(U,F). Output: Tập thuộc tính X+ + Phương pháp: Kiểm tra lần lượt từng phụ thuộc hàm fi = a nạp vế phải (tức b ) vào vào X+: X+ := X+ ¨

Lặp lại cho đến khi nào X+ = Const.

Thuật toán 1

CònThayĐổi := True; X+ := X; While Còn_Thay_Đổi Do Begin

ﬁ b Do

Còn_Thay_Đổi := False; For mỗi fi = a Begin

˝ X+ Then

If a Begin

X+ := X+ ¨ b ; Còn_Thay_Đổi := True;

End;

7. Phụ thuộc hàm dư thừa

Cho F là một tập các phụ thuộc hàm trên U, f là một phụ thuộc hàm của F tức

f ˛ F, f được gọi là dư thừa trong F nếu như (F –f )+= F+

Hay có thể nói tương đương f được gọi là dư thừa trong F nếu nó suy dẫn

+ thì f là dư thừa trong F còn ngược lại f

được từ tập F sau khi đã bỏ đi phụ thuộc hàm f.

Thuật toán thành viên Input: - Tập phụ thuộc hàm F - f ˛ F Output: - True nếu như f là dư thừa trong F - False nếu như f là không dư thừa trong F Method: 1) Tạm xoá f khỏi F, gọi G là tập thu được G=F-f, nếu G thì chuyển qua bước 2, còn không thì kết thúc thuật toán và kết luận f là không dư thừa trong F 2) Giả sử f=X→Y nếu G├ f tức Y X G là không dư thừa. Như vậy, ta chỉ cần tính X+ và so sánh với tập con Y ta có ngay câu trả lời X ﬁ Y có thuộc vào F+ hay không.

+ „

8. Phủ không dư và thuật toán tìm phủ không dư Cho F và G là hai tập phụ thuộc hàm trên U, F được gọi là phủ không dư của G khi và chỉ khi

thì

)

- ˛ " - F+ = G+ (F là phủ của G) - ( F (tức mọi phụ thuộc hàm trong F đều không dư

thừa) Định lý: Mọi tập phụ thuộc hàm đều tồn tại phủ không dư

+ „

Thuật toán tìm phủ không dư Input - Tập phụ thuộc hàm G Output - Tập phụ thuộc hàm F là phủ không dư của G tức là

thìFf

)

- ˛ " + F+ = G+ (F là phủ của G) + ( F (tức mọi phụ thuộc hàm trong F đều không dư

thừa) Method: b1) Gán F := G b2) For each f in G Do

If (F-f)+ = F+ Then F := F-f

End If

End For b3) Return F Về mặt thực tế ta hay bước 2 trong thuật toán trên bởi b2) For each FD f : L -> R in G Do

If R ˝ L+

F - { f } Then

F:= F- {f}

EndIf

EndFor

+ „

9. Phủ thu gọn Cho F và G là hai tập phụ thuộc hàm trên tập thuộc tính U. a. Phủ thu gọn trái: F được gọi là phủ thu gọn trái của G nếu như

thìXA

ﬁ ¨ ﬁ - ˛ " ˛ ﬁ "

{ } )YX

{ ( YAX

} ))

- F+ = G+ (F là phủ của G) - , (( F ( mọi thuộc tính ở vế

trái của các phụ thuộc hàm trong F đều là không dư thừa) b. Phủ thu gọn phải: F được gọi là phủ thu gọn phải của G nếu như

- F+ = G+ (F là phủ của G)

+ „

thìYA

((

ﬁ ¨ ﬁ - ˛ " ˛ ﬁ "

{ } )YX

(

} { \ AY ))

- (mọi thuộc tính ở vế

phải của các phụ thuộc hàm trong F đều là không dư thừa)

c. Phủ thu gọn F được gọi là phủ thu gọn phải của G nếu như F vừa là phủ thu gọn trái vừa là phủ thu gọn phải của G. Định lý: Mọi tập phụ thuộc hàm đều tồn tại phủ thu gọn (phủ thu gọn trái, phủ thu gọn phải)

Thuật toán tìm phủ thu gọn trái (Algorithm Left_Reduced)

Input:

Tập phụ thuộc hàm G

+ „

Output: Một phủ thu gọn trái F của G tức là:

thìXA

((

ﬁ ¨ ﬁ - ˛ " ˛ ﬁ "

{ } )YX

{ ( YAX

} ))

- F+ = G+ (F là phủ của G) - , F

If R ˝

Method: F:= G; For each FD f =L ﬁ R in G Do X:= L; For each attribute A in X Do (L-{A})+ Then Delete A from L in F;

EndIf;

EndFor; EndFor; Return F; End Left_Reduced 10. Phủ tối thiểu Bổ đề: Mọi tập phụ thuộc hàm F đều được phủ bởi một tập các phụ thuộc hàm G sao cho các phụ thuộc hàm trong G đều có vế phi chỉ có một thuộc tính. Cho F và G là hai tập phụ thuộc hàm trên tập thuộc tính U, F được gọi là phủ tối thiểu của G nếu như:  Mọi phụ thuộc hàm trong F đều có vế phải chỉ có một thuộc tính

 F+ = G+ (F là phủ của G)  f ˛ F thì (F-f)+ „ F+ ( tức mọi phụ thuộc hàm trong F đều không dư thừa)  X→Y ˛ F , " A ˛ X thì ((F- {X→Y}) ¨ ({X \ A }→Y))+ „ F+ ( tức là các

thuộc tính ở vế trái của các phụ thuộc hàm trong F là không dư thừa) Hay nói một cách khác F được gọi là phủ không dư của G nếu như

 Các phụ thuộc hàm trong F đều có vế phi chỉ có một thuộc tính  F là phủ không dư của G  F là phủ thu gọn trái của G Định lý: Mọi tập phụ thuộc hàm F đều được phủ bởi một phủ tối thiểu G nào đó. Phương pháp tìm phủ tối thiểu: Bước 1: Tách mỗi phụ thuộc hàm trong F có dạng X → A1A2A3… An thành các phụ thuộc hàm mà vế phải (RH – Right Hand) chỉ có một thuộc tính: X → A1 X → A2 ……… X → An Bước 2: Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm. Bước 3: Duyệt từng phụ thuộc hàm và kiểm tra xem có dư thừa không, nếu dư thừa thì thì xoá đi. Thuật toán tìm phủ tối thiểu Input Tập phụ thuộc hàm G Output Tập phụ thuộc hàm F là phủ tối thiểu của G Method 1 – F = {X→A | " X→Y ˛ G, " A˛ Y}

{Loại bỏ các thuộc tính dư thừa ở vế trái của các phụ thuộc hàm}

2 – For each FD f =L →A in F Do

X:= L;

3 – For each attribute B in X Do

If A ˛

(L-{B})+ Then Delete B from L in F;

EndIf; EndFor;

EndFor;

{Loại bỏ các phụ thuộc hàm dư thừa}

4 – For each FD f: L→A in F Do

F-{f} Then F:= F- {f}

If A˛ L+

F =BD

EndIf EndFor 5 – Return F; II. CÁC VÍ DỤ Ví dụ 1 Tìm bao đóng của một tập thuộc tính. Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH F = {BC→ ADE, AC→ BDG, BE→ ABC, CD→ BDH, BCH→ ACG} Hãy tính X+ trong các trường hợp a) X=BD b) X=ABE c) X=CDG Giải a) đặt X(0)=BD (=X) X(1) = X(0) ¨ Z(0) =BD ¨ Suy ra X(0)= X(1) vậy X+ =X=BD b) đặt X(0)=ABE (=X) X(1) = X(0) ¨ Z(0) =ABE ¨ ABC=ABCE (ADE ¨ BDG)=ABCDEG X(2) = X(1) ¨ Z(1) =ABCE ¨ X(3) = X(2) ¨ Z(2) = ABCDEG ¨ BDH=ABCDEGH=U Vậy X+=U Ví dụ 2 Áp dụng bài toán thành viên, chứng minh một phụ thuộc hàm có được suy dẫn từ một tập các phụ thuộc hàm không?

Giả sử có tập F={X→YW, XW→Z, Z→Y, XY→Z}

G ( bao đóng của XY trong tập G)

Hãy cho biết XY→Z có dư thừa trong F hay không?

G= XYWZ thế nên Z˝

G hay G├ (XY→Z) thế nên phụ thuộc

(XY)+

Giải 1) Tạm thời xoá XY→Z ra khỏi F G:=F-{XY→Z}={X→YW, XW→Z, Z→Y} 2) Tính (XY)+ ta có (XY)+ hàm XY→Z là dư thừa trong F.

B/ BÀI TẬP GIẢI MẪU Bài số 1 Cho tập thuộc tính U=ABCDEGH Cho tập phụ thuộc hàm F={ AB→CD, ACE→BG, BCD→ AE, CH→ DG} f=BCDH →AG, hỏi rằng F├ f hay không (f ˛ F+) ?

Hướng dẫn:

Áp dụng hệ tiên đề Amstrong để chứng minh, đầu tiên cần làm xuất hiện vế trái của phụ thuộc hàm cần chứng minh sau đó lần lượt áp dụng 3 tiên đề để suy ra ĐPCM. Giải BCDH→ BCD (1) ( tính chất phản xạ ) BCD→AE ( gt) (2) BCD→ACE ( gia tăng) (3) ACE→ A (phản xạ) (4) Suy ra BCDH→ A theo tính chất bắc cầu(5) ACE→ BG (6) giả thiết BG→G (7) phản xạ Suy ra ACE→ G (8) bắc cầu Suy ra BCDH→ G (9) bắc cầu Từ (5) và (9) theo luật cộng tính (luật ghép) Suy ra BCDH→AG F+ (đpcm)

Bài số 2 Cho a = (U, F); U=ABCDEGH

F= {AB→BCP, E→BGH, ACD →BG, D→AEH} Hãy tính X+ trong các trường hợp a. X=AC b. X=CD c. X=ABG

Hướng dẫn: Áp dụng lần lượt các bước của thuật toán tính bao đóng.

f = X(0) nên X+=AC

( BGH ¨ BG) = ACDEH ¨ ( BGH ¨ BG) = ABCDEGH =U

(BCD ¨ BG ¨ AEH)= ABCDEGH =U

Giải a. Vì X=AC X(0)= X=AC X(1) = X(0) ¨ b. Vì X=CD X(0)=X=CD X(1) = X(0) ¨ AEH =ACDEH X(2)= X(1) ¨ Do X(2) =U nên X+ =U c. Vì X =ABG X(0 )=X =ABG X(1) = ABG ¨ BCD=ABCDG X(2) = ABCDG ¨ Do X(2) =U nên X(3) = X(2) hay X(3) =U

Bài tập 3 Tìm bao đóng. Cho lược đồ quan hệ R = (U, F) U= {A,B,C,D,E,G,H} F= {AB→C, D→EG, ACD→B, C→A, BE→C, CE→AG, BC→D, CG→BD, G→ H} a. Tính (D)+ b. Tính (DE)+ c. Tính (BE)+

d. Tính (CG)+

Hướng dẫn: a. Tính (D)+ X0 = D 1) X1 = DEG (áp dụng D→EG) 2) X2 = DEGH (áp dụng G→H) (= Constant) Vậy (D)+ = DEGH

b. Tính (DE) + X0 = DE 1) X1 = DEG (áp dụng D→EG) 2) X2 = DEGH (áp dụng G→H) (= Constant) Vậy (DE)+ = DEGH

c. Tính (BE)+ X0 = BE 1) X1 = BEC (áp dụng BE→C) 2) X2 = BECAG (áp dụng CE→AG) 3) X3 = BECAGD (áp dụng BC→D) 4) X4 = BECAGDH (áp dụng G→H) (= Constant) Vậy (BE)+ = ABCDEGH

d. Tính (CG)+ X0 = CG 1) X1 = CGA (áp dụng C→A) 2) X2 = CGABD (áp dụng CG→BD) 3) X3 = CGABDH (áp dụng G→H) 4) X4 = CGABDHE (áp dụng D→EG) (= Constant) Vậy (CG)+ = ABCDEGH

Bài tập 4 Cho lược đồ quan hệ R = (U, F) U = {A, B, C, D, E, G} F = {C→G, BG → CD, AEG → BC, CG →AE, B → CG} a. Tính C+ b. Tính (B)+ c. Tính (AEG)+

Hướng dẫn: a. Tính C + X0 = C 1) X1 = CG (áp dụng C→G) 2) X2 = CGAE (áp dụng CG→AE) 3) X3 = CGAEB (áp dụng AEG→BC) 4) X4 = CGAEBD (áp dụng BG→CD) (= Constant) Vậy (C)+ = ABCDEG b. Tính (B)+ X0 = B 1) X1 = BCG (áp dụng B→CG) 2) X2 = BCGD (áp dụng BG→CD) 3) X3 = BCGDAE (áp dụng CG→AE) (= Constant) Vậy (B)+ = ABCDEG c. Tính (AEG)+ X0 = AEG 1) X1 = AEGBC (áp dụng AEG→BC) 2) X2 = AEGBCD (áp dụng BG→CD) (= Constant) Vậy (AEG)+ = ABCDEG Bài tập 5 Phụ thuộc hàm dư thừa. Cho F = {AC → B, C → B, ABDE → GH, A → E, A → D} + Xét phụ thuộc hàm AC→B: Rõ ràng thuộc tính A trong AC → B là dư thừa vì C+ = (CB) (cid:201) B. + Xét phụ thuộc hàm ABDE → GH

- Thuộc tính A : Không dư thừa vì (BDE)+ = BDE không chứa GH - Thuộc tính B : Không dư thừa vì (ADE)+ = ADE không chứa GH - Thuộc tính D: Dư thừa vì (ABE)+ = ABDE có chứa ABDE ( Loại thuộc tính D khỏi phụ thuộc hàm ABDE → GH ta được ABE → GH + Xét phụ thuộc hàm ABE → GH - Thuộc tính E: Dư thừa vì (AB)+ = ABDE (cid:201) ABE + Các thuộc tính trong các phụ thuộc hàm còn lại đều không dư thừa. Cuối cùng ta được tập phụ thuộc hàm không có thuộc tính dư thừa gồm: F = {C → B, AB → GH, A → E, A → D} Bài tập 6 Tìm phủ tối thiểu của tập phụ thuộc hàm T sau đây T = {ABH → CK, A → D, C →E, BGH → F, F →AD, E → F, BH → E} • Bước 1: Chuyển vế phải của mỗi phụ thuộc hàm thành các thuộc tính đơn lẻ, ta được: - ABH → C - ABH → K - A → D - BGH → F - F → A - F → D - E → F - BH → E • Bước 2: Loại bỏ các thuộc tính dư thừa bên phía trái của mỗi phụ thuộc hàm (Sử dụng phương pháp loại giống như bài tập 5). + Xét phụ thuộc hàm ABH→C - A dư thừa vì (BH)+ = {BHEFDAKC} có chứa C. - B Không dư thừa vì (AH)+ = {AHD} không chứa C - H không dư thừa vì (AB)+ = {ABD} không chứa C  Kết quả sau lần thứ nhất: T = {BH → C, ABH → K, A → D, BGH → F, F → A, F → D, E → F, BH → E}

+ = {E} không chứa F => Không dư thừa.

+ = {BHCK} không chứa E nên không dư thừa.

+ Tương tự: A dư thừa trong ABH→K vì (BH)+ = {BHCEFDAK} chứa K và G dư thừa trong BGH→F vì (BH)+ = {BHEFDAKC} có chứa F.  Kết quả cuối cùng: T = {BH → C, BH → K, A → D, BH → F, F → A, F → D, E → F, BH → E} Đển đây ta không thể loại thêm được thuộc tính nào nữa. • Bước 3: Loại bỏ các phụ thuộc hàm dư thừa Hiện tại T = {BH→C, BH→K, A→D, BH→F, F→A, F→D, E→F, BH→E} + Thử loại BH → C, Ta có (BH)+ = {BHFADEK} không chứa C => không dư thừa. + Thử loại BH→K, Ta có (BH)+ = {BHCFADE} không chứa K => không dư thừa. + Thử loại A→ D, Ta có (A)+ = {A} không chứa D => không dư thừa. + Thử loại BH→ F, Ta có (BH)+ = {BHCKEFAD} có chứa F => luật này dư thừa, loại ra khỏi T, ta được: T = {BH→C, BH→K, A→D, F→A, F→D, E→F, BH→E} + Thử loại F→A, Ta có F+ = {FD} không chứa A => không dư thừa + Thử loại F→ D, ta có F+ = {FAD} có chứa D nên luật này dư thừa. Loại khỏi T ta được: T = {BH→C, BH→K, A→D, F→A, E→F, BH→E} + Thử loại E + Thử loại BH Đến đây ta đã thử xong tất cả các phụ thuộc hàm trong lược đồ. Kết quả cuối cùng ta có phủ tối thiểu T = {BH→C, BH→ K, A→D, F→A, E→F, BH→E}.

C/ BÀI TẬP TỰ GIẢI Bài tập 1 Cho lược đồ quan hệ a =(u, F) với U =ABCDEGH và tập phụ thộc hàm E, CEﬁ GH, Gﬁ A} F = {AB ﬁ C, Bﬁ D, CDﬁ F = ABﬁ E, chứng minh rằng với mọi quan hệ R trên U nếu R thoả F thì R cũng thoả f. Bài tập 2 Cho lược đồ quan hệ (= (U, F) với

J, BEﬁ E, AGﬁ I, Eﬁ G, GIﬁ H}

I, BEﬁ I, Eﬁ G, GIﬁ H}

U = ABCDEGHIJ và tập phụ thộc hàm F={ABﬁ f =ABﬁ GH, chứng minh rằng f suy dẫn được từ F Bài tập 3 Cho lược đồ quan hệ (=(u, F) với U=ABCDEGH và tập phụ thộc hàm F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A} Hãy chứng minh ABﬁ E BGﬁ C ABﬁ G Bài tập 4 Cho lược đồ quan hệ (=(u, F) và tập phụ thộc hàm F={ABﬁ E, AGﬁ Chứng minh rằng ABﬁ GH suy dẫn được từ F Bài tập 5 Cho lược đồ quan hệ (=(u, F) và tập phụ thộc hàm F={ABﬁ C, Bﬁ D, CDﬁ E, CEﬁ GH, Gﬁ A} Chứng minh rằng ABﬁ E v à ABﬁ G suy dẫn được từ F Bài tập 6 Tìm phủ không dư của tập phụ thuộc hàm F={Aﬁ C, ABﬁ C, Cﬁ DI, ECﬁ AB, EIﬁ C} Bài tập 7 Cho F={Aﬁ B, Cﬁ D} với C(cid:204) B, hãy chứng minh Aﬁ D suy dẫn được từ F Bài tập 8 Một phụ thuộc hàm Xﬁ Y được gọi là dư thừa trong tập phụ thuộc hàm F nếu như F+= (F-{Xﬁ Y})+ cho F={Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z} hãy cho biết phụ thuộc hàm XYﬁ Z có dư thừa trong F hay không Bài tập 9 Tìm phủ không dư của

F={ Xﬁ YZ, ZWﬁ P, Pﬁ Z, Wﬁ XPQ, XYQﬁ YW, WQﬁ YZ} Bài tập 10 Cho lược đồ quan hệ R(ABCD) v à F={Aﬁ B, BCﬁ D} hãy cho biết các phụ thộc hàm nào dưới đây có thể suy dẫn được từ F ACﬁ D Bﬁ D ADﬁ B Bài tập 11 F = {XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ QR, Qﬁ X} Chứng minh rằng XYﬁ P suy dẫn được từ F Bài tập 12 Loại bỏ các phụ thuộc hàm dư thừa trong tập F={Xﬁ Y, Yﬁ X, Yﬁ Z. Zﬁ Y, Xﬁ Z, Zﬁ X} Bài tập 13 Cho F = {XYﬁ W, Yﬁ Z, WZﬁ P, WPﬁ QR, Qﬁ X}. Chứng minh rằng XY ﬁ Q suy dẫn được từ F. Bài tập 14 Cho F = {Aﬁ BC, Eﬁ C, Dﬁ AEF, AFﬁ B, AFﬁ D} Phụ thuộc hàm AF ﬁ B có dư thừa trong F không ? Bài tập 15 Nếu Xﬁ Y ˛ F, A˛ X, thuộc tính A được gọi là dư thừa nếu {X - A} ﬁ Y ˛ F+ Hãy loại bỏ các thuộc tính dư thừa trong các tập sau: a. F = {Xﬁ YW, XWﬁ Z, Zﬁ Y, XYﬁ Z} b. F = {Aﬁ BC, Eﬁ C, Dﬁ AEF, ABFﬁ BD} Bài tập 16 Sử dụng các luật của hệ tiên đề Amstrong chứng minh các tính chất sau: a. Tính tựa bắc cầu: Nếu Xﬁ Y và YZﬁ W thì XZﬁ W b. Tính phản xạ chặt Xﬁ X c. Tính cộng tính: Nếu Xﬁ Y và Zﬁ W thì XZﬁ YW d. Tính chất hợp: Nếu Xﬁ Y và Xﬁ Z thì Xﬁ YZ

e. Tính tách: Nếu Xﬁ YZ thì Xﬁ Y v à Xﬁ Z f. Tính tích luỹ: Nếu Xﬁ YZ, Zﬁ VW thì Xﬁ YVW Bài tập 17 Cho lược đồ quan hệ a = (U, F) với U = ABCDEG và F = {Aﬁ C, BCﬁ D, Dﬁ E, Eﬁ A}. Hãy tính (AB)+ ((DE)+A)+ Bài tập 18 Cho lược đồ quan hệ a =(U, F) với U=ABCDEG và F={Bﬁ C, ACﬁ D, Dﬁ G, AGﬁ E} hãy cho biết ABﬁ G˛ F+ BDﬁ AD˛ F+ Bài tập 19 Cho lược đồ quan hệ a =(U, F) với U=ABCDEGH F = {ABﬁ GH, GDﬁ AHE, Cﬁ AGH, HEﬁ BC } a. Tính (CE)+ b. Tính (CD)+ c. Chứng minh rằng ABEﬁ DH không suy dẫn được từ F. d. Chứng minh rằng với mọi quan hệ R trên U Nếu R thoả F thì R cũng thoả ACDﬁ BHE. e. Chứng minh rằng F├ ABE. Bài tập 20 Hãy tìm phủ cực tiểu của a. F={ABﬁ C, Aﬁ D, BDﬁ C}

b. F={ABﬁ C, Aﬁ B} Bài tập 21 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH và F = {B ﬁ AEG, ABE ﬁ CH, ACD ﬁ BEG}. Bằng các luật của hệ tiên đề Armstrong hãy chứng tỏ phụ thuộc hàm f = BD ﬁ CGH suy dẫn được từ tập các phụ thuộc hàm F.

Bài tập 22 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH và F = {AE ﬁ BEG, CEH ﬁ BD, DG ﬁ BCD, ABC ﬁ DE} và một phụ thuộc hàm f = ACE ﬁ DEG. Hãy chỉ ra rằng f có thể dẫn được từ tập F theo các luật của hệ tiên đề Armstrong. Bài tập 23 Cho lược đồ quan hệ a = (U, F) và X,Y,Z là các tập con của tập thuộc tính U. Dựa vào các luật của hệ tiên đề Armstrong hãy chứng minh rằng phụ thuộc hàm X ﬁ YZ được suy dẫn từ tập F khi và chỉ khi các phụ thuộc hàm X ﬁ Y và X

ﬁ Z cũng suy dẫn được từ tập F.

Bài tập 24 Cho lược đồ quan hệ a = (U,F) với U = ABCDEGH và F = {AE ﬁ BEG, CEH ﬁ BD, DG ﬁ BCD, ABC ﬁ DE}. và một phụ thuộc hàm f = ACE ﬁ DEG. Hãy chỉ ra rằng f dẫn được từ tập F bằng việc ứng dụng các luật của hệ tiên đề Armstrong.

CHƯƠNG 4: CÁC VẤN ĐỂ VỀ KHÓA CỦA LƯỢC ĐỒ QUAN HỆ

là tập tất c các khoá của lược đồ a = (U, F), như vậy mỗi phần tử

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

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC  Các thuật toán tìm một khoá, nhiều khoá.  Phân biệt các loại 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 Ka của Ka Đị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.

1 „ U

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

Nhận xét: Tập hợp Ka 2. Siêu khoá và khoá Định nghĩa: Cho lược đồ quan hệ a = (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ệ a = (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ệ a =(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 (cid:204) K thì K1 Không là siêu khoá tức K+ Chú ý: định nghĩa này là tương đương với định nghĩa Cho lược đồ quan hệ a =(U,F), tập K ˝ U được gọi là khoá của lược đồ ( nếu như nó thoả mãn:

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

i=1, .., n }

- K U ˛ F+ - " K1 (cid:204) K thì K1  U ˇ F+ (K+ „ U) Tập hợp Ka 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ệ a = (U, F) sao cho Ka =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 đồ a = (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 " Khi đó lược đồ a = (U,F) có Ka II. MỘT SỐ VẤN ĐỀ VỀ KHOÁ Cho a = (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 đồ nếu K+ = U chứng tỏ K là một siêu khoá, để kiểm tra K có phải là khoá không ta lấy mọi tập con thực sự của K, nếu tất cả các tập con thực sự của K đều không là siêu khoá thì chứng tỏ K là khoá, nếu tồn tai một tập con thực sự của K là siêu khoá thì chứng tỏ K không là khoá Bài toán 2 Tìm một khoá của lược đồ. Cho một lược đồ a = (U, F), hãy tìm một khoá K. Phương pháp: b1) Trước hết chọn một siêu khoá K b2) Từ siêu khoá đó kiểm tra xem nó có phải là khoá không b3) Nếu K là khoá thì dừng thuật toán, ngựơc lại chuyển bước tiếp theo. b3) Nếu K chưa phải là khoá thì có K1 là tập con thực sự của và lớn nhất của K và K1 là siêu khoá, thay K bằng K1 và quay trở lại bước b2. Mô tả thuật toán (bằng ngôn ngữ tựa Pascal): (Thuật toán 1) - Chọn một siêu khoá K của lược đồ chẳng hạn có thể chọn K=U hoặc K= (U\ R) ¨ L với L= ¨ Li | " Li ﬁ Ri ˛ F,R= ¨ Ri | " Li ﬁ Ri ˛ F

Thuật toán: Begin For each A in K do if (K-A)+ = U then K:= K- A; end; Nhận xét: Thuật toán này cho ta tìm được một khóa của lược đồ quan hệ a . Nếu muốn tìm các khóa khác (nếu có) của lược đồ quan hệ ta có thể thay đổi thứ tự loại bỏ các phần tử của khóa. Bài toán 3

là

là tập mà mỗi phần tử của nó không tham gia vào bất cứ một khoá

Tìm giao của tất cả các khoá I Kí hiệu a = (U, F) với F = {Li  Ri, i=1,..n} Là tập mà mỗi phần tử của nó tham gia vào tất cả các khoá của lược đồ hay Ia giao của tất cả các khoá của lược đồ. Kí hiệu Na nào của lược đồ

i 1=

(Ri – Li) | " Li  Ri ˛ F } Kí hiệu Sa ={ U \ 

i 1=

(Ri – Li) | " Li  Ri ˛ F} Khi đó: Ia =Sa = { U \ 

Bài toán 4

Cho lược đồ quan hệ  = (U, F). Hỏi rằng lược đồ có bao nhiêu khoá. Phương pháp kiểm tra một lược đồ đã cho có một hay nhiều khoá: - Tính Ia - Nếu (Ia )+ = U thì lược đồ đã cho có duy nhất một khoá - Nếu (Ia )+ „ U thì lược đồ có nhiều khoá Trong ví dụ trên ta có Ia = AH do vậy ( Ia )+ „ U do vậy lược đồ đã cho có nhiều khoá.

Bài toán 5

Cho lược đồ  = (U, F). Hãy tìm các khoá của lược đồ. Thuật toán 2: - Xác định Ia

Ia } ( Ri -Li ) sao cho Li ˝

" Li ﬁ Ri ˛ F}

Ia }

" Li ﬁ Ri ˛ F}

\ Ia

Ia . Ia )+ = U thì đặt Mi = Bi ¨ Ia )+ ( i =1..n), nếu (Bi ¨

„

. - Xác định N = { ¨ - Đặt N’= (Ia N)+ \ - Tính N’’= {R\L | L= ¨ Li ,R = ¨ Ri - Đặt NK = N’ ¨ N’’ - Chọn siêu khoá K = U\NK - Đặt TMP = K\ Ia Begin For each A in TMP do if (TMP - A)+ = U then TMP := TMP- {A}; end; - Return TMP. Thuật toán tìm tất cả các khoá của lược đồ quan hệ (Thuật toán 3) Cho lược đồ quan hệ a = (U, F) hãy tìm tất cả các khoá của lược đồ quan hệ a b1) Xác định Ia b2) Nếu (Ia )+ = U thì kết luận lược đồ có một khoá duy nhất là Ia ( và kết thúc thuật toán. Ngược lại (Ia )+ „ U thì chuyển sang bước tiếp theo. (Ri -Li ) sao cho Li ˝ b3) Xác định N = {¨ - đặt N’= (Ia N)+ \ Ia b4) Tính N’’ = {R\L | L= ¨ Li ,R = ¨ Ri b5) Na = N ¨ N’ ¨ N’’ - Đặt B = U \ Na b6) Nếu | B | = 2 (tập B chỉ gồm có hai thuộc tính), giả sử B=B1B2 khi đó lược đồ chỉ có hai khoá là Ia B1 và Ia B2, kết thúc thuật toán. Ngược lại nếu | B |>2 thì chuyển sang bước tiếp theo. b7) Tìm tất cả các tập con khác rỗng của B, ký hiệu các tập con đó là {B1, B2, .. Bn}. Tính (Bi ¨ b8) Khi đó M = {M1, M2, …, Mh} là họ tất cả các siêu khoá của lược đồ a b9) Loại bỏ các siêu khoá không tối tiểu ra khỏi M, tức là nếu $ Mi ˝ Mj (*)( i j, i, j = 1..h) thì loại Mj ra khỏi M. Tập M thu được sau khi loại bỏ tất các phần tử thoả mãn biểu thức (*) chính là họ tất cả các khoá của lược đồ a

B/ BÀI TẬP GIẢI MẪU Bài số 1 Kiểm tra một tập thuộc tính có phải là khoá của một lược đồ không? Cho lược đồ quan hệ: a = (U,F) V ới U = ABCDEGH F={AB  CDE, AC  BCG, BDG, ACHHE, CG  BDE } và K = ACGH Hỏi rằng K có là khoá của lược đồ hay không? K+ = ACGH ¨ BCG ¨ HE ¨ BDE = U suy ra K là siêu khoá Các tập con thực sự lớn nhất của U là ACG, CGH, ACH, AGH dễ dàng kiểm tra các tập ACG có (ACH)+ = U vậy K không là khoá. Bài số 2 Tìm một khoá của lược đồ. Cho lược đồ quan hệ a = (U, F) với U = ABCDEGHK F = {ADHﬁ BC, GHﬁ BE, Dﬁ CG, CHﬁ K} Hãy tìm một khoá của lược đồ (sử dụng thuật toán 1) - Chọn siêu khoá K = ACDGH (K= (U\ R) ¨ L) - Loại A ta có (K - A)+ = (CDGH)+ = BCDEGHK „ U nên A không thể loai đựơc. - Loại C ta có (K - C)+ = (ADGH)+ = ABCDEGHK = U nên gán K :=K – {C} = ADGH

- Loại D ta có (K-D)+ = (AGH)+ = ABEGH „ U nên không loại được D

- Loại G ta có (K-G)+ = (ADH)+ = ABCDEGHK = U Nên gán K= K- {G} = ADH. - Loại H ta có (K - H)+ = (AD)+ =ACDG „ U nên không loại được D Vậy khoá K = ADH Bài số 3 Hãy tìm giao của tấp cả các khoá của lược đồ  = (U, F) Với U = ABCDEGH F={AB  CDE, AC  BCG, BDG, ACHHE, CG  BDE } (BCG – AC) ¨ Ia = U \ ((CDE – AB) ¨ (G – BD) ¨ (HE – ACH) ¨ (BDE –

Ia ) (Ri -Li ) = ABC (Ri -Li ) = DH ( vì Li ˝

" Li ﬁ Ri ˛ F} = ADEHG \ ABCEG = DEH

CG) ) =U \ ( CDE ¨ BG ¨ G ¨ E ¨ BDE ) =U \ BCDEG=AH Bài số 4 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH, F = {ABCﬁ ADH, ABGﬁ AEH, AEﬁ DG} Hãy tìm một khoá của lược đồ. (sử dụng thuật toán 2) Ia = U \ ¨ N = ¨ N’ = (Ia N)+ \ Ia = (ABCDH)+ \ ABC = DH ˝ Na N’’= {R\L | L= ¨ Li ,R = ¨ Ri Na = N ¨ N’ ¨ N’’ = DEH \ Na =EG B= U\ Ia

Do (Ia

¨ G = ABCG

)+ „ U nên lược đồ đã cho có nhiều khoá, do vậy lược đồ này có hai khoá ¨ E = ABCE và Ia là Ia C/ BÀI TẬP TỰ GIẢI Bài tập 1 Xây dựng lược đồ quan hệ có các khoá là ADE, BCH, CG, AHE Bài tập 2 Cho lược đồ quan hệ a = (U, F) với U= ABCDEGHK F= { ADHﬁ BC, GHﬁ BE, Dﬁ CG, CHﬁ K} Hãy tìm giao của tất của các khoá a) Lược đồ đã cho có một hay nhiều khoá b) Hãy tìm tất của các khoá của lược đồ c) Một số các phần tử không khoá Bài tập 3 Tìm các thuộc tính khoá của lược đồ a =(U, F)với U=ABCDE F={ ABﬁ C, ADﬁ B, Bﬁ D } Hãy tìm các phần tử khoá của lược đồ trên Bài tập 4 Các mệnh đề trên mệnh đề nào đúng/ sai

= (U, F) với

không? vì sao ?

(K+ -Y) trong đó X = CD , Y = CH , K là một siêu khoá

a. K˝ U là một khoá khi và chỉ khi Kﬁ U b. K˝ U là một khoá thì Kﬁ U c. Hai khoá bất kỳ là không giao nhau d. Hai khoá bất kỳ là không bao nhau e. Mọi lược đồ quan hệ đều có ít nhất một khoá f. bản thân U cũng có thể là một khoá g. tồn tại một lược đồ quan hệ không có khoá nào h. U không thể là khoá của lược đồ i. Hợp của hai khoá phân biệt là một khoá j. Hợp của hai khoá là một siêu khoá Bài tập 5 Cho lược đồ quan hệ a U = ABCDEGH F = { ABCﬁ DE, BCDﬁ G, ABHﬁ EG, CEﬁ GH} Hãy tìm một khóa của lược đồ Bài tập 6 Cho lược đồ quan hệ a =(U, F) với U = ABCDEGH F = {CDﬁ H, Eﬁ B, Dﬁ G, BHﬁ E, CHﬁ DG, Cﬁ A } a. Tìm giao của tất của các khoá b. Lược đồ có một hay nhiều khoá c. Tập ABD có phải là khoá của a d. Tập CH có phải là khoá của a không? vì sao ? e. Tính Z = (X+Y)+ ˙ bất kỳ nào đó của a

Bài tập 7 Cho lược đồ quan hệ a = (U, F) với U = ABCD, F = {ADﬁ BC, Bﬁ A, Dﬁ C} a. Tìm các khoá của lược đồ b. Cho biết C có phải là thuộc tính khoá hay không? Bài tập 8

a = (U, F) với U = ABCDEGHIK. Sao cho lược đồ có ít

AEH , BC ﬁ ADE , AC ﬁ CDEH ,

Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH, F = { DEﬁ G, Hﬁ C, Eﬁ A, CGﬁ H, DGﬁ AE, Dﬁ B} Tìm giao của tất của các khoá a. Lược đồ có một hay nhiều khoá b. Tìm một khoá của lược đồ Tập BCE có phải là khoá của a không? vì sao ? Hãy thêm hoặc bớt một phụ thộc hàm trong F để lược đồ có duy nhất một khoá Bài tập 9 Cho lược đồ quan hệ a = (U, F) với U = ABCDEH, F = { BCﬁ E, Dﬁ A, Cﬁ A, AEﬁ D, BEﬁ CH} Tìm một khoá K của lược đồ a. Ngoài khoá K lược đồ a còn có khoá nào khác không? Vì sao? b. Tập BCH có phải là khoá của a không? vì sao ? c. Tập BD có phải là khoá của a không? vì sao ? Bài tập 10 Cho lược đồ a = (U, F) có U = ABCDE và F = {AB ﬁ C, BD ﬁ CE, D ﬁ AC, A ﬁ DC, CE ﬁ A} Lược đồ có một hay nhiều khoá? Hãy tìm một khoá của lược đồ a Bài tập 11 Xây dựng lược đồ nhất 3 khoá và các thuộc tính A, B, C không tham gia vào bất kỳ một khoá nào Bài tập 12 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH và F = { BDG ﬁ AG ﬁ CDE, CG ﬁ BDE } a. Lược đồ đã cho có một hay nhiều khoá ? b. Hãy tìm một khoá của lược đồ trên. c. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không? Vì

sao? Bài tập 13

trên U thoả mãn các

Cho U = ABCDEGH. Hãy xây dựng một lược đồ quan hệ a điều kiện sau : a. Lược đồ a có ít nhất 4 khoá b. Có hai thuộc tính C, D không tham gia vào bất kỳ một khoá nào c. Hợp tất cả các khoá của lược đồ là tập lớn nhất . Hãy giải thích điều đó. Bài tập 14 Xây dựng lược đồ quan hệ a = (U, F) với U = ABCDEGHIK sao cho lược đồ có 3 khoá và giao của các khoá là DG và hai thuộc tính E,H không tham gia vào bất kỳ một khoá nào . Bài tập 15 Xây dựng lược đồ quan hệ a = (U, F) với U = ABCDEGH sao cho lược đồ có 3 khoá và giao của các khoá là CDE. Bài tập 16 Cho lược đồ a = (U, F) có U = ABCDEGH và F = { AB ﬁ CE, BCD ﬁ CH, DG ﬁ ACE, AD ﬁ DCH, BC ﬁ AEG } a. Hãy tìm một khoá của lược đồ. b. Xây dựng một lược đồ quan hệ a có tập thuộc tính U đã cho ở trên sao cho

thoả mãn 3 điều sau :

có tập thuộc tính U đã cho ở trên sao cho

1. Lược đồ có it nhất ba khoá. 2. Hai khoá bất kỳ có giao khác trống. 3. Các thuộc tính B và H là các thuộc tính không khoá Bài tập 17 Cho lược đồ a = (U, F) có U = ABCDEGH và F = { AB ﬁ CE, BCD ﬁ CH, DG ﬁ ACE, AD ﬁ DCH, BC ﬁ AEG } a. Hãy tìm một khoá của lược đồ. b. Xây dựng một lược đồ quan hệ a thoả mãn 3 điều sau:

1. Lược đồ có it nhất ba khoá. 2. Hai khoá bất kỳ có giao khác trống. 3. Các thuộc tính B và H là các thuộc tính không khoá

CDE, BD ﬁ CGE, DG ﬁ ACE, AD ﬁ CDEH, BCG ﬁ AEH}

Hãy giải thích. Bài tập 18 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH và F={AB ﬁ a. Lược đồ đã cho có một hay nhiều khoá ? b. Hãy tìm một khoá của lược đồ trên. Liệu có thuộc tính nào không tham gia vào bất kỳ một khoá nào không? Vì sao? c. Cho U = ABCDEGH. Hãy xây dựng một lược đồ quan hệ a trên U thoả mãn

các điều kiện sau :

. - Lược đồ a có ít nhất 4 khoá - Có hai thuộc tính C, D không tham gia vào bất kỳ một khoá nào - Hợp tất cả các khoá của lược đồ là tập lớn nhất. Hãy chứng minh điều đó. Bài tập 19 Cho lược đồ quan hệ a = (U, F) với U = ABCDEGH và F = {CDE ﬁ CDH, ABH ﬁ BC, BDK ﬁ CD, ADGE ﬁ CDE} a. Tập F có suy dẫn ra phụ thuộc hàm ABCH ﬁ CDK theo quan hệ hay không ? b. Lược đồ có một hay nhiều khoá. c. Hãy tìm một khoá của lược đồ a

CHƯƠNG 5: CHUẨN HOÁ LƯỢC ĐỒ QUAN HỆ

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC  Phân biệt các dạng chuẩn của quan hệ.  Kiểm tra một lược đồ ở dạng chuẩn nào.  Vận dụng giải các bài tập về chuẩn hóa quan hệ (Đưa các lược đồ quan hệ

(quan hệ) từ dạng chuẩn thấp lên dạng chuẩn cao hơn).

- X  Y (Y phụ thuộc hàm X)

- " X’  X thì X’  Y (mọi tập con thực sự của X đều không thể xác định hàm Y)

 Kiểm tra được một phép tách lược đồ quan hệ có mất thông tin không. A/ NHẮC LẠI LÝ THUYẾT I. CÁC ĐỊNH NGHĨA, TÍNH CHẤT 1. Dạng chuẩn 1 (1NF - first normal form) Định nghĩa 1: Một lược đồ quan hệ a = (U, F) được gọi là ở dạng chuẩn một (1NF) nếu và chỉ nếu tất cả miền giá trị của các thuộc tính của R đều nguyên tố (không thể phân chia được). Chú ý: Tính không thể phân chia được chỉ có tính chất tương đối. Định nghĩa này cho thấy ngay rằng bất kỳ quan hệ chuẩn hóa nào cũng ở 1NF. 2. Dạng chuẩn 2 (2NF- Second normal form) Định nghĩa 2: Cho lược đồ quan hệ (cid:181) =(U, F) với X, Y ˝ U tập thuộc tính Y được gọi là phụ thuộc hàm đầy đủ vào tập thuộc tính X nếu như Y phụ thuộc hàm vào X nhưng không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X tức là:

, từ tập tất cả các khoá này ta suy ra . Ký hiệu tập thuộc tính không khoá

i =1..n thì lược đồ (cid:181) ở dạng chuẩn 2NF, ngược lại với "

˘ thì lược đồ (cid:181) không ở dạng chuẩn 2NF.

- XY

- YA

- YX

- A ˇ XY

Định nghĩa 3: Cho lược đồ quan hệ (cid:181) = (U, F), lược đồ (cid:181) được gọi là ở dạng chuẩn 2, ký hiệu là 2NF nếu như lược đồ ở dạng chuẩn 1NF và các thuộc tính không khoá của (là phụ thuộc đầy đủ vào khoá chính. Thuật toán kiểm tra lược đồ có ở dạng chuẩn 2NF hay không? Bài toán: Cho lược đồ quan hệ (cid:181) = (U, F), hỏi rằng lược đồ có ở dạng chuẩn 2NF hay không? Thuật toán: b1) Tìm tất cả các khoá của của lược đồ (cid:181) các thuộc tính không khoá của lược đồ (cid:181) này là NK. b2) Với mỗi khoá Ki ta tìm tất cả các tập con thực sự của Ki, ký hiệu họ các tập con thực sự của Ki kà {S1, S2, ...,Ski}, ký hiệu Q={Q1, Q2, .., Qn} là họ tất cả các tập con thực sự của các khoá Ki. b3) Tìm bao đóng Q+ = {Q1+, Q2+, .., Qn+} b4) Nếu Qi+ ˙ NK = ˘ nếu $ Qi+ ˙ NK „ 3. Dạng chuẩn 3 (3NF- Second normal form) Định nghĩa 4: Cho lược đồ quan hệ (cid:181) =(U, F) với X˝ U, A ˛ U. Thuộc tính A được gọi là phụ thuộc hàm bắc cầu vào tập thuộc tính X nếu như $ Y ˝ U để

Nếu X  Y và Y không phụ thuộc bắc cầu vào X thì ta nói Y phụ thuộc trực tiếp vào X. Định nghĩa 5: Cho lược đồ quan hệ a = (U, F), lược đồ a được gọi là ở dạng chuẩn 3, kí hiệu là 3NF, nếu như lược đồ ở dạng chuẩn 1NF và các thuộc tính không khoá của a là không phụ thuộc hàm bắc cầu vào khoá chính.

Nhận xét: Lược đồ quan hệ a = (U, F), với F là tập các phụ thuộc hàm có vế phải chỉ gồm một thuộc tính. Khi đó lược đồ a ở dạng chuẩn 3NF khi và chỉ khi mọi phụ thuộc hàm X ﬁ A ˛ F với A ˇ X đều có:

- Hoặc X là siêu khóa - Hoặc A là thuộc tính khóa

đạt chuẩn 3NF ngược lại a

Thuật toán kiểm tra lược đồ ở dạng chuẩn 3NF hay không? Từ nhận xét trên ta có thuật toán kiểm tra xem một lược đồ có ở dạng chuẩn 3NF hay không như sau: Input: lược đồ quan hệ a =(U, F). Output: khẳng định a đạt chuẩn 3NF hay không. Method: Bước 1: Tìm tất cả khóa của lược đồ a Bước 2: Từ F tìm tập phụ thuộc hàm tương đương F’, mà vế phải của các phụ thuộc hàm trong F’ chỉ có một thuộc tính. Bước 3: Nếu mọi phụ thuộc hàm X ﬁ A ˛ F với A ˇ X đều có hoặc X là siêu khóa hoặc A là thuộc tính khóa thì a không đạt chuẩn 3NF. 4. Dạng chuẩn Boyce Codd (BCNF- Boyce Codd normal form) Định nghĩa 6: Cho lược đồ quan hệ a =(U, F), lược đồ a được gọi là ở dạng chuẩn Boyce Codd, kí hiệu là BCNF, nếu như lược đồ ở dạng chuẩn 1NF và nếu XY ˛ F+ ( Y ¸ X ) thì X phải là siêu khoá của lược đồ. Thuật toán kiểm tra lược đồ ở dạng chuẩn BCNF hay không? Từ định nghĩa về dạng chuẩn BCNF trên ta có thuật toán kiểm tra xem một lược đồ có ở dạng chuẩn BCNF hay không như sau: Input: lược đồ quan hệ a = (U, F). Output: khẳng định a đạt chuẩn BCNF hay không. Method 1: b1. Từ F tìm tập phụ thuộc hàm tương đương F’, mà vế phải của các phụ thuộc hàm trong F’ chỉ có một thuộc tính.

f " i = (Ui, Fi), i = 1, ..., k với điều kiện i=1, ..., k , ¨ Ui = U, Fi= F/Ui, Fi là hình chiếu của F lên tập thuộc tính

là phép tách mất thông tin.

b2. Nếu mọi phụ thuộc hàm X ﬁ A ˛ F’ với A ˇ X đều có X là siêu khóa thì a đạt chuẩn BCNF ngược lại a không đạt chuẩn BCNF. 5. Tách lược đồ quan hệ Định nghĩa: Phép tách lược đồ quan hệ a = (U, F) là phép thay thế nó bằng một tập các lược đồ con a Ui „ Ui Phép tách đó được ký hiệu là s = {U1, U2, … , Uk} Kí hiệu a = (U, F), s = {U1, U2, … , Uk} là một phép tách khi đó R là một quan hệ trên U, kí hiệu Md (R) = R [U1] * R [U2] * ... * R [Uk] Định nghĩaphép tách kết nối không mất thông tin: Cho lược đồ quan hệ a = (U, F) và phép tách d = {U1, U2,.., Uk} đối với lược đồ đó. Phép tách d được gọi là phép tách kết nối không mất thông tin nếu mọi quan hệ R trên U thì ta có md (R) = R, ngược lại nếu md (R) „ R thì ta nói phép tách d 6. Thuật toán kiểm tra phép tách kết nối có mất thông tin hay không? Dữ liệu vào:

- Tập thuộc tính U - Tập phụ thuộc hàm F - Phép tách d = {U1, U2,.., Uk}

Ra:

Xác định liệu phép tách d có mất thông tin hay không?

Phương pháp: Giả sử U={A1, A2,.., An}, ta xây dựng một bảng gồm k dòng n cột (n=| U | , k=| |), cột thứ i của bảng ứng với thuộc tính Ai, hàng thứ j của bảng ứng với lược đồ con a i = (Ui, Fi), tại hàng i và cột j ta điền kí hiệu aj ( ta gọi kí hiệu aj là tín hiệu chính) nếu thuộc tính Aj˛ Ui, nếu không ta điền bịj ( ta gọi bij là tín hiệu phụ). Bây giờ ta biến đổi bảng như sau:

Với mỗi phụ thuộc hàm XY ˛ F, nếu trong bảng có hai hàng giống nhau trên tập thuộc tính X thi ta cần làm chúng giống nhau trên tập thuộc tính Y theo quy tắc sau: - Nếu một trong hai giá trị là tín hiệu phụ thì ta sửa lại tính hịêu phụ thành tín hiệu chính tức là sửa bij thành aj -Nếu cả hai là tín hịêu phụ thì ta sửa lại hai tín hiệu đó bằng một trong các kí hiệu bij, tức là sửa lại chỉ số cho giống nhau. Tiếp tục áp dụng các phụ thuộc hàm trong bảng ( kể cả các phụ thuộc hàm đã được sử dụng) cho tới khi không còn áp dụng được nữa.

Quan sát trong bảng cuối cùng: nếu xuất hiện ít nhất một hàng gồm toàn tín hiệu chính (hàng gồm toàn kí hiệu a) thì phép tách kết nối là không mất thông tin, trường hợp ngược lại là kết nối mất thông tin. Định lý: Cho lược đồ a = (U, F), phép tách d ={U1, U2 } nếu U1 ˙ U2 ﬁ U1 \ U2 (1) hoặc U1 ˙ U2 ﬁ U2 \ U1 (2) thì phép tách d là phép tách kết nối không mất thông tin.

7. Phương pháp chuẩn hóa dữ liệu 7.1. Thuật toán tách lược đồ thành 3NF Input: Lược đồ quan hệ  = (U, F) Output: Các lược đồ ở dạng 3NF

(U1, K1), (U2, K2), …., (Un, Kn) thỏa mãn: a) Quan hệ R trên U thì R[U1]*R[U2]* … * R[Un]=R b) K1, K2, …, Kn là các khoá của lược đồ con tương ứng Phương pháp: 1. Tìm một khóa K của lược đồ  2. Tìm một phủ G tối thiểu của F G={K1A1, K2A2, …, KpAp} 3. Ghép các phụ thuộc hàm có cùng vế trái trong G để thu được phủ G={K1X1, K2X2, …, KnXn} 4. Phép tách ={K1X1, K2X2, …, KnXn} nếu khoá K không có mặt trong thành phần nào của thì thêm thành phần K vào .

là phép tách kết nối không mất thông tin

i = (Ui, Fi) đều ở dạng BCNF

5. Return  7.2. Tách không mất thông tin thành các lược đồ ở dạng BCNF Cho lược đồ a = (U, F), và phép tách d ={U1, U2,.., Uk}, phép tách một lược đồ thành một tập các lược đồ ở dạng BCNF là phép tách thỏa mãn: - Phép tách d - Tất cả các lược đồ con a Phương pháp: Xuất phát từ một phụ thuộc hàm X A nào đó của F, phụ thuộc hàm X A này vi phạm điều kiện BCNF, ta xây dựng phép tách d ={U1, U2}, tương ứng với lược đồ a 1 và a 2 sao cho: - Phép tách đó là phép tách kết nối không mất thông tin - Phụ thuộc hàm X A là phụ thuộc hàm của lược đồ a 1 và nó thỏa mãn điều kiện cua BCNF trong lược đồ này - Nếu như các lược đồ a 1 và a 2 vẫn chưa ở dạng BCNF thì tiếp tục quá trình đó, thì các điều vi phạm BCNF đều bị loại bỏ, cuối cùng ta thu được một tập các lược đồ con đều ở dạng BCNF và quá trình tách luôn luôn đm bo phép tách kết nối không mất thông tin. Cơ sở của thuật toán trên là do giả thiết lược đồ a = (U, F) chưa ở dạng BCNF do đó tồn tại phụ thuộc hàm X A, Aˇ X, X không phải là siêu khoá U1=XA, U2 =U \ A Nhận xét X=U1 ˙ U2, U1 \ U2 =A, đã có X A do đó U1 ˙ U2  U1 \ U2 theo định lý ở phần trên thì phép tách d ={U1 , U2} là phép tách có kết nối không mất thông tin. Vì U1 =XA và phụ thuộc hàm X A là duy nhất trên lược đồ a 1 = (U1, F1) nên X là siêu khoá. Nếu a 1 , a 2 chưa ở dạng BCNF thì ta áp dụng quá trình tách tương tự. Cuối cùng ta thu được một tập các lược đồ ở dạng BCNF và quá trình tách là không mất thông tin. Ví dụ: Cho lược đồ a = (U, F) với U = CRHTSG (C: Course, T: Teacher, H Hour, R: Room, S: Student, G: Group).

a = (U, F)

U1 = CSG

U2 = CTHRS

F1 = {CSG}

F2 = {CT, HRC, CHR, HSR}

K=CS

K=HS

U3 =CT

U4 = CHSR

F3={CT}

F4 = {HRC, CHR, HSR}

K=C

K=HS

U5 = CHR

U6 = CHS

F5 = {HRC, HRC}

F6 = {HSC}

K=HS

K=HR, K=HC

F ={CT, HR  C, CH  R, CS G, HS R} Nhận xét - Lược đồ này có duy nhất một khoá là HS - Lược đồ này chưa ở dạng BCNF - Ta thấy trong lược đồ a = (U, F) có phụ thuộc hàm CS G vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U1 = CGS, U2 = CTHRS - Ta thấy trong lược đồ a 2 = (U2, F2) có phụ thuộc hàm C T vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U3 = CT, U4 = CHRS - Ta thấy trong lược đồ a 4 = (U4, F4) có phụ thuộc hàm CH R vi phạm điều kiện BCNF nên ta tách lược đồ thành các lược U5 = CHR, U6 = CHS

Như vậy phép tách cuối cùng là d = {CSG, CT, CHR, CHS} II. MỘT SỐ LƯU Ý  Tầm quan trọng của việc chuẩn hóa dữ liệu.  Phân biệt các dạng chuẩn, phương pháp tách quan hệ ở dạng chuẩn thấp lên

dạng chuẩn cao hơn.

 Thuật toán kiểm tra phép tách có mất thông tin không

B/ BÀI TẬP GIẢI MẪU Bài số 1 Kiểm tra lược đồ (U, F) có ở dạng chuẩn 2NF hoặc 3NF hay không? Cho lược đồ quan hệ a = (U, F) với U={A1, A2, A3, A4, A5} F={ A1  A2 A3 , A2 A4 A5 , A2 A3} Kiểm tra 2NF: Bước 1: Tìm tất cả các khoá của lược đồ

i 1=

(Ri – Li) | " Li  Ri ˛ F} + Tìm giao của tất cả các khoá Ia ={ U \ 

Ia = U \ A2A3A5 = A1A4

+} = {A1A2A3, A4}, do Q1

trên có kết nối không mất thông tin không?

Bước 2: Tính bao đóng của Ia Áp dụng thuật toán tính bao đóng ta có (Ia )+ = A1A2A3A4A5 = U Vậy lược đồ có duy nhất một khoá là A1A4, suy ra NK = A2A3A5 +, Bước 3: Các tập con thực sự của khoá A1A4 là { A1, A4} và ta có Q+ = { Q1 + ˙ NK = A2A3 „ Q2 , nên lược đồ không ở dạng 2NF Kiểm tra 3NF: Bước 1: Các khoá của lược đồ là : A1A4 Bước 2: Tìm F’ = { A1  A2, A1  A3 , A2 A4 A5 , A2 A3} Bước 3: Xét phụ thuộc hàm A1  A2 và A1  A3 có A2 ˇ A1, A3 ˇ A1mà A1 là thuộc tính khoá, xét A2 A3 do A3 ˇ A2 và A3+ „ U do vậy lược đồ đã cho không ở dạng 3NF. Bài số 2 Kiểm tra phép tách có mất thông tin hay không? Cho lược đồ quan hệ a = (U, F) với U={A1, A2, A3, A4, A5} F={ A1  A2 A3 , A2 A4 A5 , A2 A3} d ={ A1 A2 A4, A2 A3, A1 A4 A5} Hỏi rằng phép tách d Hướng dẫn:

Áp dụng thuật toán kiểm tra phép tách có mất thông tin không, ta tiến hành từng bước. Giải: Xây dựng bảng gồm 3 dòng 5 cột - Điền các tín hiệu vào bảng

A1 A2 A3 A4 A5

a1 U1 a2 b13 a4 b15

b13 U2 a2 a3 b24 b25

a1 U3 b32 b33 a4 a5

- Biến đổi bảng trên dựa vào tập phụ thuộc hàm F + Sử dụng phụ thuộc hàm A1  A2 A3 ta thấy bảng không có gì thay đổi + Sử dụng phụ thuộc hàm A2 A4  A5 ta có bảng mới như sau:

A1 A2 A3 A4 A5

a1 U1 a2 b13 a4 a5

b13 U2 a2 a3 b24 b25

a1 U3 a2 b13 a4 a5

+ Sử dụng phụ thuộc hàm A2 A3

A1 A2 A3 A4 A5

a1 U1 a2 a3 a4 a5

b13 U2 a2 a3 b24 b25

a1 U3 a2 a3 a4 a5

là phép tách kết nối không mất thông tin.

Trong bảng này có hàng cuối cùng gồm toàn các tín hiệu chính, do vậy phép tách d C/ BÀI TẬP TỰ GIẢI Bài tập 1 Dùng kỹ thuật bảng kiểm tra phép tách sau có mất thông tin không a. a = (U, F) với U = ABCD, F = {Aﬁ B, ACﬁ D}, d = {AB, ACD}

a = (U, F) với U = ABCDE, F = {Aﬁ C, Bﬁ C, Cﬁ D, DEﬁ C, CEﬁ A},

b. d = {AD, AB, BE, CDE} c. Xác định và giải thích dạng chuẩn cao nhất của lược đồ quan hệ a =(U, F) với U = ABCD, F = {Aﬁ C, Dﬁ B, Cﬁ ABD} Bài tập 2 Cho lược đồ quan hệ a = (U, F) với U=ABCDEGH F = {CDﬁ H, Eﬁ B, Dﬁ G, BHﬁ E, CHﬁ DG, Cﬁ A } Hỏi rằng phép tách d =(ABCDE, BCH, CDEGH) có kết nối mất thông tin không. Bài tập 3 Cho lược đồ quan hệ a = (U, F) với U = ABCD, F = {Dﬁ B, Cﬁ A, Bﬁ ACD } Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên Bài tập 4 Cho lược đồ quan hệ a = (U, F) với U = ABCD, F={CDﬁ B, Aﬁ C, Bﬁ ACD } Xác định dạng chuẩn cao nhất của lược đồ quan hệ trên Bài tập 5 Cho a = (u, F) với U = ABCDE và F = {Aﬁ C, Bﬁ C, Aﬁ D, DEﬁ C, CEﬁ A} kiểm tra tính kết nối không mất thông tin đối với phép tách d = {AD, AB, BE, CDE, AE} Bài tập 6 Cho a = (u, F) với U = ABCDEF và F = {ABﬁ C, Cﬁ B, ABDﬁ E, Fﬁ A} Kiểm tra tính kết nối không mất thông tin đối với phép tách d = {BC, AC, ABDE, ABDF} Bài tập 7 Cho a = (u, F) với

U=ABCDEG F={Dﬁ G, Cﬁ A, CDﬁ E, Aﬁ B} kiểm tra tính kết nối không mất thông tin đối với phép tách d ={DG, AC, SCE, AB } Bài tập 8 Cho a =(u, F) với U=ABCDE và F={Aﬁ C, Bﬁ C, Cﬁ D, DEﬁ C, CEﬁ A} kiểm tra tính kết nối không mất thông tin đối với phép tách d = {AC, CD, BE, BC, AE} Bài tập 9 Cho (= (U, F) với U = XYZW và tập F = {Yﬁ W, Wﬁ Y, XYﬁ Z} Dạng chuẩn cao nhất của lược đồ là gì? Bài tập 10 Cho (= (U, F) với U = ABCDEG và tập phụ thuộc hàm và F={ ABﬁ C, ACﬁ E, EGﬁ D, ABﬁ G} d = {DEG, ABDEG } Phép tách trên có mất thông tin không? Hãy chứng minh mọi quan hệ chỉ có 2 thuộc tính đề ở dạng chuẩn BCNF? Bài tập 11 Xét quan hệ R(ABCDE) và tập phụ thuộc hàm F = { ABﬁ CE, Eﬁ AB, Cﬁ D } Hãy tìm dạng chuẩn cao nhất của lược đồ? Bài tập 12 Xét quan hệ R(ABCDEG) và tập phụ thuộc hàm F = { Aﬁ B, Cﬁ DG , ACﬁ E, Dﬁ G } - Hãy tìm khoá của lược đồ - Hãy tìm dạng chuẩn cao nhất của lược đồ Bài tập 13 Xét quan hệ R(ABCD) và tập phụ thuộc hàm F = { ABﬁ D, ACﬁ BD, Bﬁ C }

Hãy tìm dạng chuẩn cao nhất của lược đồ Bài tập 14 Cho a = (u, F) với U = ABCDEF F = {ABﬁ C, Cﬁ B, ABDﬁ E, Fﬁ A} Lược đồ có ở dạng BCNF không

CHƯƠNG 6: NGÔN NGỮ SQL

MỤC TIÊU CỦA BÀI NÀY GIÚP NGƯỜI HỌC  Hiểu và phân biệt 3 nhóm lệnh của ngôn ngữ SQL  Giải một số bài tập thao tác trên quan hệ có sử dụng 3 nhóm lệnh trên.  Vận dụng giải quyết các bài toán tổng hợp. A/ NHẮC LẠI LÝ THUYẾT I. Các nhóm lệnh của ngôn ngữ cơ sở dữ liệu. 1. Các lệnh DDL: CREATE, ALTER, DROP. a. Lệnh CREATE Lệnh này dùng để tạo ra bảng TABLE, khung nhìn VIEW và chỉ mục INDEX, CREATE TABLE Cú pháp:

CREATE TABLE tên_bảng (tên_cột kiểu_dữliêụ(size)[,..n])

Khi tạo ra bảng chúng ta phải chỉ ra kiểu dữ liệu của cột và mỗi cột chỉ có thể có

môt kiểu dữ liệu duy nhất. Khi tạo bảng ta có thể đưa ra các ràng buộc.

Các ràng buộc của các trường có thể là: primary key, foreign key, unique, not

null...

VD: Tạo bảng nhân viên

CREATE TABLE NHAN_VIEN (MANV varchar(8) primary key, ho_ten Varchar(50),Ngay_sinh date, chuc_vu varchar(20), dia_chi varchar(50), luong number(7));

Trong VD trên ta tạo ra một ràng buộc primary key trên trường MANV Ta cũng có thể tạo ra bảng mới với cấu trúc và dữ liệu từ 1 bảng khác. Cú pháp:

SELECT into FROM WHERE <điều kiện>

VD: Tạo ra 1 bảng mới có tên là NVN (MANV, ho_ten) từ bảng NHAN_VIEN

đã tồn tại: SELECT Manv, ho_ten into NVN FROM NHAN_VIEN;

b. Lệnh ALTER - Dùng để thêm một hay nhiều trường vào bảng hoặc sửa đổi một cột hiện tại. SQL ANSI chuẩn không cho phép huỷ bỏ các cột. Cú pháp:

ALTER TABLE tên_bảng ADD | ALTER | DROP option (tên_cột kiểu_dữ_liệu…) + ADD: thêm cột mới + ALTER: sửa đổi cột + DROP option: xoá bỏ các ràng buộc VD1: Thêm trường gia_dinh kiểu char (1) vào R1 ALTER TABLE R1 ADD gia_dinh char (1);

VD2: Thay đổi trường Dia_chi varchar (30) trong R1 thành Dia_Chi (20):

ALTER TABLE R1 ALTER COLUMN Dia_Chi varchar (20);

c. Lệnh DROP - Dùng để xoá bỏ một quan hệ, khi ta xoá bỏ một bảng cơ sở thì tất các VIEW,

INDEX được định nghĩa trên bảng đó sẽ bị xoá bỏ.

- Cú pháp:

DROP TABLE/VIEW/INDEX Name;

VD1: Xoá bỏ Index Nhan_vien_id; DROP INDEX Nhan_vien_id; VD2: Xóa bỏ bảng NHANVIEN DROP TABLE NHANVIEN;

2. Các lệnh DML: SELECT, UPDATE, INSERT, DELETE, … a. Lệnh SELECT Mệnh đề SELECT tương ứng với toán tử project (phép chiếu p) của đại số quan

hệ. Khối lệnh SELECT gồm có ba mệnh đề chính: + SELEC: xác định nội dung của các cột cấn đưa ra. + FROM: danh sách các quan hệ được quét qua. + WHERE: ứng với một khẳng định lựa chọn của đại số quan hệ.

- Lệnh SELECT thường có dạng:

SELECT [distinct]*/A1 .. An FROM R1, R2 ..., Rm [WHERE <Điều_kiện>] [GROUP BY ] [HAVING <Điều_kiện theo nhóm>] [ORDER BY [ASC/DESC]]

Trong đó: A i là các thuộc tính R j là các quan hệ (có thể là các TABLEs, VIEWs…) Ta có thể dùng các bí

danh cho các Ai, Rj.

Đkiện: là điều kiện ràng buộc. Ở đây WHERE có thể có hoặc không. Dùng * để chỉ tất cả các thuộc tính của các quan hệ được chọn - Để loại bỏ các bộ giá trị (các hàng) trùng nhau ta thêm từ khoá Distinct vào

sau SELECT

-Trong khẳng định Điều_kiện: ta có thể dùng các liên từ logic and, or, not khi

kết hợp nhiều điều kiện.

- Mệnh đề GROUP BY dùng để nhóm các hàng có cùng giá trị, để thực hiện

tính toán

- Mệnh đề HAVING bao chỉ xuất hiện sau GROUP BY, dùng để đặt điều kiện

sau khi GROUP BY

VD1: Để hiện các thông tin về một nhân viên nào đó gồm (Manv, Ho_ten,

Ngay_sinh, Chuc_vụ, dia_chi, luong) SELECT Distinct * FROM R1;

Đưa ra (Manv, Ho_ten, Ngay_sinh, Chuc_vụ, dia_chi, luong) với điều kiện

lương = 500.000 và dia_chi không ở Hà nội SELECT Ho_ten, Ngay_sinh, Chuc_vụ, dia_chi, luong, ten_phong FROM Nhanvien R1, Lienket R2, Phong R3 WHERE (R1.luong = 500.000) and (not R1.dia_chi = ’Hà nội’) and

(R1.Manv = R2.Manv) and (R2.MP = R3.MP);

-Trong lệnh trên ta đã dùng R1,R2,R3 làm bí danh cho Nhanvien, Lienket,

Phong.

Các bí danh đó chỉ có tác dụng trong một câu lệnh. b. Nhóm lệnh INSERT,UPDATE,DELETE: - Thêm một bộ vào quan hệ Cú pháp:

INSERT INTO Tên_Bảng (Danh sách tên cột) VALUES (Danh sách các trị) [câu hỏi con]

VD1: Chèn 1 hàng (‘020’, ’Nguyễn Trọng Nghĩa’, ’Bảo vệ’, ’Hà nội’,

’800.000’) vào R1.

INSERT INTO R1 VALUES (‘020’, ’Nguyễn Trọng Nghĩa’, ’Bảo vệ’, ’Hà

nội’, ’800.000’);

VD2: Cho bảng: PHIEUMUON (Sophieu, Sothe, Masach, Ngaymuon, Ngaytra). Chèn 1 hàng (’P001’, ’M001’, ’S001’, ’11/03/2010’, ’11/05/2010’) vào

bảng PHIEUMUON.

INSERT INTO PHIEUMUON VALUES (’P001’, ’M001’, ’S001’,

’11/03/2010’, ’11/05/2010’) Chú ý:

Khi thêm một bộ vào quan hệ mà trong bộ đó có trường là kiểu Datetime thì ta cần chú ý giá trị của trường đó phải được định dạng đúng theo thời gian trên máy tính của người sử dụng.

Chẳng hạn: ở ví dụ 2, khi thêm một bộ vào quan hệ PHIEUMUON thì có trường Ngaymuon và Ngaytra là kiểu Datetime. Nếu máy tính có định dạng thời

gian là: day – month – year thì Ngaymuon sẽ là ngày 11/03/2010 nhưng nếu máy tính có định dạng thời gian là: month – day – year thì Ngaymuon sẽ là ngày 03/11/2010. - Xóa các bảng Dùng để xoá bỏ 1 hoặc nhiều bộ trong quan hệ Cú pháp:

DELETE FROM R [WHERE P]

Những bộ nào thỏa mãn đk P thì mới bị huỷ bỏ khỏi quan hệ R VD: DELETE FROM R1 WHERE ngay_sinh = ’01-01-1935’; Xoá bỏ tất cả các nhân viên ta dùng lệnh:

DELETE FROM R1;

- Sửa dữ liệu Cú pháp:

UPDATE [Tên_bảng] SET [Tên_cột=Biểu thức ...] [FROM Tên_Bảng] [WHERE btđk]

II. CÁC VÍ DỤ Ví dụ 1

Cho quan hệ: SINHVIEN (masv char (10), hoten char (25), ngaysinh

datetime, d1 double, d2 double, d3 double).

Trong đó masv là thuộc tính khóa của quan hệ trên.

a. Hãy tạo lập cấu trúc trên. b. Chèn một cột gioi_tinh kiểu dữ liệu char (1) vào bảng trên. Lời giải: a. CREATE TABLE SINHVIEN (MaSV Char(10), Hoten Char(25) not null, Ngaysinh Date, d1 double, d2 double, d3 double, CONSTRAINT khoa_sv Primary Key (MaSV))

b. ALTER TABLE SINHVIEN ADD gioi_tinh char (1) ; Ví dụ 2 Cho CSDL gồm 2 quan hệ:

LOP (Malop char (10), tenlop char (20)) SINHVIEN (malop char (10), masv char (10), hoten char (20), ngaysinh

datetime, d1 double, d2 double, d3 double)

a. Hãy đưa ra các thông tin của các sinh viên bao gồm: tenlop, masv, hoten, dtb

của mỗi sinh viên.

b. Đưa ra tổng số sinh viên của mỗi lớp. Lời giải: a. SELECT lop.tenlop, sv.masv, ([d1] + [d2] + [d3])/3 AS dtb

FROM lop, sv WHERE lop.malop = sv.malop;

b. SELECT lop.tenlop, Count (sv.masv) AS CountOfmasv

FROM LOP, SINHVEN sv WHERE lop.malop = sv.malop GROUP BY lop.tenlop;

III. MỘT SỐ LƯU Ý  Các câu lệnh này có thể thử nghiệm trên một số hệ quản trị CSDL như SQL,

Access…

 Phân biệt điều kiện sau mệnh đề WHERE và sau mệnh đề HAVING.  Nguyên tắc hoạt động của câu lệnh SELECT B/ BÀI TẬP GIẢI MẪU Bài số 1 Cho CSDL của hệ thống Quản lý nhân sự: DONVI (MaDV char (3), TenDV char (20), Diachi char (20), MaNPT C(4)) NHANVIEN (MaNV char (4), Hoten char (20), NHVu char (20), Luong N(8), Phucap N(6), MaDV char (3)) Hãy đưa ra danh sách tất cả các đơn vị có trong tổ chức này. Hướng dẫn: Ta thấy các thông tin lấy trong bảng đơn vị và câu lệnh thuộc nhóm khai thác dữ liệu. Lời giải: SELECT TenDV, Diachi FROM DONVI Bài số 2 Để quản lý kinh doanh dùng các bảng sau:

+ HH (hàng hoá): MaHH char (3), TenHH char (20), Qcach char (20), DVT char

(5), DGIA Number (10)

+ CH (cửa hàng): MaCH char (3), TenCH char (20), DDiem char (20), PTrach

char (4)

+ KH (khách hàng): MaKH char (4), TenKH char (20), Loai char (2), Diachi

char (20).

+ CT(chứng từ): Sohieu char (12), Ngay Date, LoaiCT Char(1), MaKH char (4),

MaCH char (3), MaHH char (3), SoLuong Number (6). a. Xem trong bng CT có những loại hàng hoá nào được xuất. Hướng dẫn:

Ta thấy trong bảng CT, mỗi chứng từ có thể bao gồm nhiều MaHH khác nhau, như vậy trong bảng CT sẽ có nhiều MaHH giống nhau, với yêu cầu trên ta chỉ cần đưa ra các MaHH khác nhau. Lời giải: a. SELECT DISTINCT MaHH FROM CT SELECT DISTINCT CT.MaHH, TenHH FROM CT, HH WHERE

CT.MaHH = HH.MaHH

b. Đưa ra danh sách các nhân viên có lương >=200000 SELECT * FROM NHANVIEN WHERE Luong >= 200000 c. Cho xem danh sách gồm 3 cột Mã đơn vị, họ tên, nhiệm vụ từ bảng nhân viên

và được sắp xếp theo mã đơn vị, cùng đơn vị theo nhiệm vụ:

SELECT MaDV, Hoten, NHVu FROM NHANVIEN ORDER BY MaDV, NHVu Mã đơn vị, họ tên, lương từ bảng NHANVIEN được sắp xếp theo mã đơn vị,

cùng đơn vị theo lương giảm dần:

SELECT MaDV, Hoten, Luong FROM NHANVIEN ORDER BY MaDV, Luong DESC

Chú ý: 1. Tên các cột trong <điều kiện ràng buộc> sau WHERE không nhất thiết phải có sau SELECT, các cột này không nhất thiết phải có trong bảng kết quả. 2. Tên các cột sau ORDER BY… bắt buộc phải có sau SELECT, tức là các cột

này bắt buộc phải có trong bảng kết quả.

+ GROUP BY : Nếu có dùng để nhóm các hàng có cùng giá trị của tên cột đối với mỗi nhóm thì cùng thực hiện một thao tác tính toán nào đó. 3. Cho xem mã hàng hoá, tên hàng hoá và tổng số tiền bán được của từng mặt

hàng:

SELECT MaCT, MaHH, TenHH, SUM (Soluong*Dongia) FROM CT, HH WHERE CT.MaHH = HH.MaHH and Loai = “X” GROUP BY CT.MaHH Cho xem mã đơn vị, tên đơn vị, mức lương bình quân và số nhân viên của từng đơn vị: SELECT b.MaDV, b.TenDV, AVG (Luong), COUNT (a.manv) FROM NHANVIEN a, DONVI b WHERE a.MaDV = b.MaDV GROUP BY b.MaDV, b.TenDV + Phần HAVING <điều kiện ràng buộc> chỉ phục vụ cho GROUP BY Bài số 3 R1 = Nhân viên (NV, Ho_ten, Nsinh, nghe_nghiep, Dia_chi, luong) R2 = Liên kết (NV, MP) R3 = Phòng (Mp, Ten_phong, tel)

1. Để hiện các thông tin về một nhân viên nào đó gồm( NV , Ho_ten,

Ngay_sinh, Chuc_vu, dia_chi, luong) SELECT Distinct * FROM R1;

2. Đưa ra (Ho_ten, Ngay_sinh, Chuc_vu, dia_chi, luong, ten_phong) với điều

kiện lương. 500.000 và đia_chỉ không ở Hà nội. SELECT Ho_ten, Ngay_sinh, Chuc_vụ, dia_chi, luong, ten_phong.

FROM Nhanvien R1, Lienket R2, Phong R3

WHERE (R1.luong = 500.000) AND (not R1.dia_chi = ’Hà nội’) AND

(R1.Manv = R2.Manv) AND (R2.MP = R3.MP);

- Trong lệnh trên ta đã dùng R1,R2,R3 làm bí danh cho Nhanvien, Lienket,

Phong.

Các bí danh đó chỉ có tác dụng trong một câu lệnh Các ví dụ sau này ta dùng R1,R2,R3 để thay cho các bảng trên cho gọn Có 4 toán tử hay được dùng với các kiểu dữ liệu.Trong mệnh đề WHERE là:

In (not in).

Between… and … (not between ...). Like (not like). Is null (not is Null).

+ Toán tử in (not in): Dùng để kiểm tra giá trị trong (không nằm trong) một danh

sách được chỉ ra.

3. Đưa ra những người có dia_chi ở Hà nội và Hà tây.

SELECT * FROM R1 WHERE dia_chi in (‘Hà nội’,’Hà tây’); +Toán tử between ... and ... (not …): kiểm tra giá trị nằm giữa (không nằm giữa) một phạm vi được chỉ ra.

4. Đưa ra những người có lương nằm trong khong (500.000 đến 1.000.000). SELECT * FROM R1 WHERE luong between 500.000 and 1.000.000; + Toán tử like (not like): Dùng để kiểm tra những giá trị giống (không giống) với giá tri sau like, thường sử dụng với xâu ký tự và khi ta không biết chính xác giá trị cần tìm kiếm hoặc giá trị cần tìm kiếm giống một mẫu nào đó. Trong SQL người ta sử dụng ký hiệu % cho xâu con và ‘_’cho 1 ký tự bất kỳ. 5. Tìm những người có tên mà có ký tự đầu tiên bất kỳ, ký tự tiếp theo là OA và

tiếp theo là dãy ký tự bất kỳ: SELECT * FROM R1 WHERE hoten=’_OA%’; + Toán tử Is Null (not is Null): kiểm tra cho các giá trị rỗng (không rỗng);

C/ BÀI TẬP TỰ GIẢI Bài tập 1 Cho CSDL gồm có ba quan hệ như sau: NCC (MaNCC, TenNCC, DCNCC, DT) SP (MaSP, TenSP, Loai) SP_NCC (MaNCC, MaSP, SL) Giải thích một số từ viết tắt: - MaNCC là mã số nhà cung cấp - TenNCC là tên nhà cung cấp có mã số tương ứng - DCNCC là địa chỉ của nhà cung cấp - DT là điện thoại nhà cung cấp - MaSP là mã số sản phẩm - TenSP là tên của sản phẩm

- Loại là chủng loại của mặt hàng - SL là số lượng đã cung cấp - Quan hệ NCC ( nhà cung cấp ) dùng để lưu trữ một số thông tin về các nhà

cung cấp

- Quan hệ SP ( sản phẩm ) dùng để lưu trữ một số thông tin của các mặt hàng - Quan hệ SPỴNCC dùng để lưu trữ một số thông tin về việc cung ứng sản

phẩm của NCC

Hãy viết biểu thức SQL: a. Cho biết tên của nhà cung cấp có địa chỉ là Hà Nôi b. Cho biết tên của các sản phẩm đã cung ứng bởi nhà cung cấp có mã số là HP. c. Cho biết tên của các nhà cung ứng đã cung ứng các sản phẩm với số lượng

20.

d. Cho biết tên của các nhà cung cấp đã cung ứng các sản phẩm Bài tập 2 Cho cơ sở dữ liệu gồm 3 quan hệ SV(MSV, HT, NS, QUE)

ĐT(MĐT, TĐT, GV, KP) TT(MSV, MĐT, NTT, KQ)

Trong đó : MSV : Mã sinh viên HT : Họ tên sinh viên NS : Năm sinh QUE : Quê quán MĐT : Mã đề tài TĐT : Tên đề tài GV : Giáo viên KP : Kinh phí NTT : Nơi thực tập KQ : Kết quả

Hãy trả lời các câu hỏi sau dưới dạng biểu thức SQL: a. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Hà nội và có kết

quả thực tập khá ( KQ >= 7)

b. Cho biết tên của các sinh viên có kết quả thực tập khá và thực tập tại quê

hoặc thực tập tại Quảng ninh.

c. Cho biết tên của các giáo viên hướng dẫn sinh viên có quê ở Hà nội và thực

tập đề tài có kinh phí lơn hơn 5 triệu

d. Cho biết tên của các sinh viên có kết quả thực tập khá và thực tập đề tài có

kinh phí lớn hơn 4 triệu.

e. Danh sách sinh viên thực tập tại quê nhà f. Thông tin về các đề tài có sinh viên thực tập g. Cho biết mã của các đề tài không có sinh viên nào tham gia h. Cho biết mã của các đề tài có kinh phí nằm trong khoảng 1.5 đến 2 triệu i. Cho biết mã của sinh viên có tuổi nhỏ hơn 20 và kết qủa thực tập là khá

( KQ>7)

Bài số 3 Có CSDL thống kê về mối quan hệ giữa các quán bia (BAR) và những người

uống (DRINKER) bia (BEER) như sau:

R(DRINKER, BAR) là quan hệ cho biết quán bia và những khách uống bia tại quán đó. S(BAR, BEER) Là quan hệ cho biết các loại bia thường bán ở các quán. Còn T( DRINKER, BEER) cho biết những loại bia mà một khách hàng ưa thích.

Hãy viết các câu vấn tin sau bằng ngôn ngữ SQL: a. Cho biết các quán bia có loại bia mà khách hàng có tên “Hùng” thích. b. Cho biết những khách hàng thường đi uống ít nhất một quán có bia họ thích. c. Cho biết những khách hàng không đến uống ít nhất tại một quán có bia họ ưa

thích.

d. Xoá tất cả loại bia tiger ra khỏi quan hệ S(DRINKER, BEER) e. Chèn thêm thông tin khách hàng có tên “Minh” thích bia Tiger. f. Chèn tất cả thông tin mà khách hàng có tên “Hải” thích tất cả các loại bia bán

ở quán "Viet tiep"

Bài số 4 Giả sử trong CSDL bia ở trên ta có thêm quan hệ BAN (BAR, BEER, SL) quan hệ cho biết số lượng từng loại bia đã bán ở các quán. Hãy viết bằng SQL các vấn tin sau:

a. Tổng số bia của mỗi loại bia đã bán. b. Số lượng trung bình mỗi loại bia được bán ở các quán. c. Số lượng loại bia được bán ra nhiều nhất (bán chạy nhất).

Bài số 5 Giả sử có quan hệ S(F, H, O) với ý nghĩa là tập tin F có kích thước H thuộc chủ nhân O và quan hệ FTD(F, T, D) với ý nghĩa F có kiểu T và nằm trong thư mục D.

Hãy dùng ngôn ngữ SQL để viết các câu vấn tin sau: a. Cho biết chủ nhân và kiểu tin của tất cả các tập tin có kích thước tối thiểu là

10.000

b. Cho biết tất cả các tập tin được ông Tomax sở hữu c. Cho biết kích thước trung bình của các tập tin có trong thư mục BIN. d. Cho biết tất cả các tập tin có trong thư mục f với tên chứa chuỗi con abc. Bài số 6 Hãy dịch câu vấn tin sau sang đại số quan hệ. SELECT OWNER FROM S WHERE FILE IN

(SELECT FILE FROM FTD WHERE TYPE = 'TEX'

Bài số 7 Hãy dùng ngôn ngữ SQL: a. Tạo bảng danh sách các sinh viên vừa thi vào trường của bạn, các thuộc tính ở

đây là mã số (số báo danh), tên, năm sinh, quê, điểm thi. b. Cho biết danh sách học sinh đậu vào trường (>=20 điểm) c. Cho biết những sinh viên quê ở Sơn La, Lai Châu, Ninh Bình. Bài số 8 Cho cơ sở dữ liệu như sau: HANGHOA (MA_HANG, TEN_HG): Mỗi mặt hàng sẽ có một mã hàng, và một tên hàng.

STT FIELD NAME TYPE WIDTH DIỄN GIẢI

1 MA_HANG Character 3 Mã hàng

2 TEN_HG Character 20 Tên hàng

DAILY (STT_DL, TEN_DL, DCHI_DL): Mỗi đại lý có một số thứ tự, tên và một địa chỉ.

STT FIELD NAME TYPE WIDTH DIỄN GIẢI

STT_DL Number 3 1 Số thứ tự đại lý

TEN_DL Character 20 2 Tên đại lý

DCHI_DL Character 20 3 Ðịa chỉ đại lý

MUA (STT_DL, MA_HANG, NGAY_MUA, SOLG_MUA, TRIGIA_MUA): Mỗi một ngày, đại lý sẽ tổng kết xem đã mua những mặt hàng nào với số lượng và trị giá bao nhiêu. STT FIELD NAME WIDTH TYPE DIỄN GIẢI

STT_DL Number 3 1 Số thứ tự đại lý

MA_HANG Character 3 Mã hàng 2

NGAY_MUA Date Ngày mua 3 8

SOLG_MUA Number 4 6 Số lượng mua

TRIGIA_MUA Number 10 5 Trị giá mua

BAN (STT_DL, MA_HANG, NGAY_BAN, SOLG_BAN, TRI GIA_BAN): Sau mỗi ngày, đại lý sẽ tổng kết xem đã bán được những mặt hàng nào với số lượng và trị giá bán là bao nhiêu.

STT FIELD NAME TYPE WIDTH DIỄN GIẢI

STT_DL Number 1 3 Số thứ tự đại lý

MA_HANG Character Mã hàng 2 3

NGAY_BAN Date Ngày bán 3 8

4 SOLG_BAN Number 6 Số lượng bán

5 TRIGIA_BAN Number 10 Trị giá bán

Yêu cầu: Viết các câu hỏi sau dưới dạng ngôn ngữ hỏi SQL 1. Tìm những mặt hàng đã bán trong tháng 1/2005 tại đại lý số 5. 2. Tìm những mặt hàng đã mua trước năm 2003 và có trị giá mua > 540000. 3. Tìm tên và địa chỉ đại lý có mua bia Heineken. 4. Tìm tất cả các mặt hàng mà đại lý số 3 đã bán trong năm 2000. 5. Tìm tên những mặt hàng mà đại lý có tên “Hồng hà” đã mua trước

01/01/2003 và có số lượng mua lớn hơn 170.

6. Tìm những mặt hàng đã được mua và bán trong cùng một ngày ở cùng một

đại lý.

7. Tìm tên và địa chỉ đại lý có tổng giá trị mua trong một ngày lớn hơn 700000. 8. Tìm tổng giá trị mua và tổng giá trị bán của mặt hàng Coca Cola ở đại lý có

tên là “Phố nối1”.

9. Tìm đơn giá mua trung bình của bia Hà nội trên các đại lý. 10. Tìm dơn giá mua trung bình của bia Đại việt trên các đại lý. 11. Tìm tên, địa chỉ của đại lý và những mặt hàng có số lượng mua và số lượng

bán bằng nhau trong cùng một ngày.

12. Tìm tổng thu nhập từng ngày trên từng đại lý. 13. Tìm tổng giá trị mua trong tháng 2/2001 tại đại lý “Hồng hà”. 14. Tìm số mặt hàng có bán ở từng đại lý.

Bài số 9 Cho CSDL NORTHWIND trong Microsoft Office Access gồm các quan hệ sau:

Bảng : Shippers : Phân phối Mô tả Tên cột Mã phân phối ShipperID Tên công ty CompanyName Số điện thoại Phone Bảng : Categories: Loại hàng Tên cột CategoryID CategoryName Description Mô tả Mã Loại Tên loại Mô tả

Picture ảnh

Mã sản phẩm

Giá

Bảng : Orderdetails : Hoá đơn chi tiết Tên cột Mô tả OrderID Số hoá đơn ProductI D UnitPric e Quantity Số lượng

Mô tả

Bảng : Products : sản phẩm Mô tả Tên cột Mã sản phẩm ProductID Tên sản phẩm ProductName Mã cung cấp SupplierID Mã loại CategoryID Giá cả UnitPrice

Bảng : Employees : Nhân viên Tên cột EmployeeID Mã nhân viên LastName FirstName Title BirthDate HireDate Address City Country Bảng : Customers : Khách hàng Tên cột CustomerID CompanyName

HomePhone ContactName thoại giao Họ Tên Chức vụ Ngày sinh Ngày hợp đồng Địa chỉ Thành phố Tên nước Điện thoại nhà riêng Số điện phòng Extension

ContactTitle Address City Country Phone Mô tả Mã khách hàng Tên công ty Tên giao dịch của khách hàng Chức vụ dịch Địa chỉ Thành phố Nước Số Điện thoại

Mô tả Mã cung cấp

Công ty cung cấp

Mô tả Số hoá đơn

Bảng : Suppliers : Cung cấp Tên cột SupplierID CompanyNa me ContactNam e ContactTitle Address City Country Phone Tên giao dịch Lĩnh vực Địa chỉ Tên thành phố Tên nước Số Điện thoại Ngày hoá đơn

Bảng : Orders : Hoá đơn Tên cột OrderID CustomerID Mã khách hàng EmployeeID Mã nhân viên OrderDate RequiredDate Ngày giao ShippedDate Ngày nhập Freight Phí vận chuyển Dùng câu lệnh SQL để trả lời các câu hỏi sau: a. Cho biết tên giao dịch, địa chỉ của

tất cả khách hàng thuộc thành phố Lyon.

b. Cho biết tên giao dịch, số điện thoại của các khách hàng thuộc nước mỹ

(USA)

c. Cho biết tên, số điện thoại của các nhà phân phối. d. Cho biết họ, tên và địa chỉ của các nhân viên thuộc thành phố london. e. Cho biết họ, tên và địa chỉ của các nhân viên sinh trước ngày 14 tháng 2 năm

1970.

f. Cho biết tên, địa chỉ của các công ty cung cấp thuộc thành phố Berlin g. Cho biết tên các sản phẩm có giá lớn hơn 10 $. h. Cho tên, số lượng các sản phẩm mà khách hàng có mã là “BOTTM” đã mua. i. Cho biết tên khách hàng, địa chỉ và tổng số tiền mà các khách hàng đã mua

và sắp xếp theo chiều giảm của tổng số tiền.

j. Cho tên sản phẩm và tổng số lượng đã bán ứng với các sản phẩm đó. Bài số 10 Cho lược đồ CSDL dùng để quản lý lao động bao gồm các lược đồ quan hệ sau: - Nhanvien (MANV, HOTEN, NGAYSINH, PHAI, DIACHI, MAPB) Tân từ: Mỗi nhân viên có một mã số nhân viên (MANV) duy nhất. Một mã số nhân viên xác định các thông tin như họ tên (HOTEN), ngày sinh

(NGAYSINH), phái (PHAI), địa chỉ (DIACHI) và phòng ban (MAPB) nơi quản lý nhân viên.

- Phongban (MAPB, TENPB) Tân từ: Mỗi phòng ban có một mã phòng ban (MAPB) duy nhất, mã phòng ban

xác định tên phòng ban (TENPB)

- Cong (MACT, MANV, SLNGAYCONG) Tân từ: Lược đồ quan hệ Cong ghi nhận số lượng ngày công (SLNGAYCONG)

của một nhân

viên (MANV) tham gia vào công trình (MACT). - Congtrinh (MACT, TENCT, DIADIEM, NGAYCAPGP, NGAYKC, NGAYHT) Tân từ: Mỗi công trình có một mã số công trình (MACT) duy nhất. Mã số công trình xác định các thông tin như tên gọi công trình (TENCT), địa điểm (DIADIEM), ngày công trình được cấp giấy phép xây dựng (NGAYCAPGP), ngày khởi công (NGAYKC), ngày hoàn thành (NGAYHT).

Hãy thực hiện các câu hỏi sau bằng SQL : a. Danh sách những nhân viên có tham gia vào công trình có mã công trình (MACT) là X. Yêu cầu các thông tin: MANV, HOTEN, SLNGAYCONG, trong đó MANV được sắp tăng dần.

b. Đếm số lượng ngày công của mỗi công trình. Yêu cầu các thông tin: MACT,

TENCT, TONGNGAYCONG (TONGNGAYCONG là thuộc tính tự đặt) c. Danh sách những nhân viên có sinh nhật trong tháng 8. Yêu cầu các thông tin: MANV, TENNV, NGAYSINH, ĐIACHI, TENPB, sắp xếp quan hệ kết quả theo thứ tự tuổi giảm dần.

d. Đếm số lượng nhân viên của mỗi phòng ban. Yêu cầu các thông tin: MAPB,

TENPB, SOLUONG (SOLUONG là thuộc tính tự đặt.)

Bài số 11 Cho các quan hệ sau: - Monhoc (MSMH, TENMH, SOTINCHI, TINHCHAT) MSMH: mã số môn học, TENMH: tên môn học, SOTINCHI: số lượng tín chỉ,

TÍNH CHẤT: bằng 1 nếu đó là môn học bắt buộc, bằng 0 nếu đó là môn học không bắt buộc Sinhvien (MSSV, HOTEN, NGAYSINH, LOP) MSSV: mã số sinh viên, HOTEN: họ tên sinh viên NGAYSINH: ngày sinh, LOP (C, 4, 0): lớp - Diem (MSSV, MSMH, DIEMTHI) DIEMTHI: điểm thi Hãy dùng lệnh SQL để thực hiện các câu lệnh sau: a. Hãy cho biết những môn học bắt buộc có SOTINCHI cao nhất. b. Hãy liệt kê danh sách gồm MSSV, HOTEN, LOP, DIEMTHI của những sinh

viên thi môn học CSDL, theo thứ tự LOP, DIEMTHI.

c. Hãy cho biết các sinh viên có điểm thi cao nhất về môn học có mã là CSDL d. Hãy cho biết phiếu điểm của sinh viên có mã số là 9900277 e. Hãy liệt kê danh sách gồm MSSV, HOTEN, LOP, ĐIỂM TRUNG BÌNH của những sinh viên có điểm trung bình các môn dưới 5, theo thứ tự LOP, HOTEN.

f. Hãy liệt kê danh sách điểm trung bình của sinh viên theo thứ tự: lớp, tên. g. Hãy cho biết điểm của sinh viên theo từng môn.

Bài số 12 Dựa vào lược đồ cơ sở dữ liệu Docgia (MADG, HOTEN, NGAYSINH, DIACHI, NGHENGHIEP) Phieumuon (SOPM, NGAYMUON, MADG) Chitietmuon (SOPM, MADAUSACH, NGAYTRA) Dausach (MADAUSACH, BAN, TAP, MASH) Sach (MASH, TENSACH, TACGIA, NHAXB, NAMXB) Hãy thực hiện các câu hỏi sau đây bằng SQL a. Danh sách các đọc giả đã đăng ký mượn sách trong ngày d. Yêu cầu các thông

tin: MAĐG, HOTEN, ĐIACHI.

b. Các quyển sách của phiếu mượn có SOPM là x. Yêu cầu các thông tin

MASH, TENSACH, TACGIA, NGAYMUON, NGAYTRA.

c. Tổng số lượt mà mỗi đọc giả đến mượn sách trong năm 2001. Yêu cầu thông

tin MAĐG, HOTEN, SOLANMUON (SOLANMUON là thuộc tính tự đặt)

d. Danh sách các đọc giả cao tuổi nhất đã mượn sách trong ngày d. Yêu cầu các

thông tin MAĐG, HOTEN, NGAYSINH, ĐIACHI, NGHENGHIEP.

Bài số 13 Dựa vào lược đồ cơ sở dữ liệu: Khach (MAKH, HOTEN, DIACHI, DIENTHOAI) Hoadon (SOHD, NGAYLAPHD, NGAYBAN, MAKH) DongHoaDon (SOHD, MAHANG, SLBAN) Hang (MAHANG, TENHANG, DONGIA, DVT, MANHOM) Nhom (MANHOM, TENNHOM) Hãy thực hiện các câu hỏi sau bằng SQL. a. Danh sách các khách hàng đã mua hàng trong ngày d. Yêu cầu các thông tin

MAKH, HOTEN, ĐIACHI, ĐIENTHOAI.

b. Danh sách các mặt hàng trong số hóa đơn (SOHĐ) là x. Yêu cầu các thông tin: MATHANG, TENHANG, SLBAN, DONGIA,

THANHTIEN.

(THANHTIEN= SLBAN*ĐONGIA; THANHTIEN là thuộc tính tự đặt). Yêu

cầu sắp xếp tăng dần theo cột TENHANG.

c. Danh sách các mặt hàng thuộc mã nhóm hàng là A có đơn giá cao nhất. Yêu

cầu các thông tin : MAHANG, TENHANG,ĐONGIA

d. Đế số lượng mặt hàng của mỗi nhóm hàng. Yêu cầu các thông tin : MANHOM, TENNHOM, SOLUONG. (trong đó SOLUONG là thuộc tính tự đặt) (0,75đ)

e. Danh sách các khách hàng đã mua các mặt hàng có mã nhóm hàng là A trong

ngày.

Yêu cầu các thông tin MAKH, HOTEN, ĐIACHI, ĐIENTHOAI,TENHANG. f. Thống kê việc mua hàng trong năm 2002 của khách hàng có mã khách hàng là

Kh01(theo từng hóa đơn).

Yêu cầu các thông tin MAKH, HOTEN, SOHĐ, TRIGIAHĐ trong đó

TRIGIAHĐ là tổng số tiền trong một hóa đơn (TRIGIAHĐ là thuộc tính tự đặt)

Bài số 14 Dựa vào lược đồ cơ sở dữ liệu Giaovien (MAGV,HOTEN,DTGV,MAKHOA) Khoa (MAKHOA,TENKHOA,DTKHOA) Lop (MALOP,TENLOP,SISO,MAKHOA) Monhoc (MAMH,TENMH) Phonghoc (SOPHONG,CHUCNANG) Lichbaogiang (MALICH,NGAYDAY,MAGV) Dongbaogiang

(MALICH,TUTIET,DENTIET,BAIDAY,GHICHU,LYTHUYET,MAMH,M ALOP,SOPHONG)

Hãy thực hiện các câu hỏi sau bằng SQL a. Xem lịch báo giảng tuần từ ngày 16/09/2002 đến ngày 23/09/2002 của giáo

viên có MGV(mã giáo viên) là TH3A040. Yêu cầu: AVG, HOTEN, TENLOP, TENMH, SOPHONG, NGAYDAY, TUTIET, DENTIET, BAIDAY, GHICHU.

b. Xem lịch báo giảng ngày 23/09/2002 của các giáo viên có mã khoa là CNTT. Yêucầu: MAGV, HOTEN, TENLOP, TENMH, PHONG, NGAYDAY,

TUTIET, DENTIET, BAIDAY, GHICHU)

c. Cho biết số lượng giáo viên (SOLUONGGV) của mỗi khoa, kết quả cần sắp

xếp tăng dần theo cột tên khoa. Yêu cầu: TENKHOA, SOLUONGGV( SOLUONGGV là thuộc tính tự đặt)

TÀI LIỆU THAM KHẢO

1. Các hệ CSDL – Lý thuyết & Thực hành (Tập 1, 2)

Tác giả: Hồ Thuần – Hồ Cẩm Hà

2. CSDL – Lý thuyết & Thực hành - Tác giả: Nguyễn Bá Tường 3. Nhập môn CSDL quan hệ - Tác giả: Lê Tiến Vương 4. CSDL – Tác giả: Đỗ Trung Tuấn 5. Bài tập CSDL – Tác giả: Nguyễn Xuân Huy – Lê Hoài Bắc 6. CSDL – Kiến thức & Thực hành – Tác giả: Vũ Đức Thi 7. Garcia – Molina H., Ulman J., Widom J., Database System: The Complete

Book, Prentice Hall