




Preview text:
**Nội dung ôn thi cuối kì môn Cơ sở dữ liệu**
### 1. Phụ thuộc hàm - **Khái niệm**:
- Phụ thuộc hàm (Functional Dependency - FD) là mối quan hệ giữa các thuộctính trong một lược đồ quan hệ.
- Ký hiệu: X → Y (nếu biết giá trị của X, có thể suy ra giá trị của Y).
- **Chứng minh bằng Armstrong**:
- Ba luật cơ bản:
- Luật phản xạ (Đống dưỡng): X → Y và Y ⊆ ⇒ X X → X.
- Luật bào đóng (Phản xạ bổ sung): X → Y, X → Z ⇒ X → YZ.
- Luật bài trừ (Phân rã): X → YZ ⇒ X → Y và X → Z.
- Kết hợp các luật Armstrong để chứng minh phụ thuộc hàm dựa trên tập FD được cho.
- **Chứng minh bằng bao đóng (Closure)**:
- Các bước tính bao đóng của tập thuộc tính X (định nghĩa X+):
- Khởi tạo X+ = X.
- Đối chiếu các phụ thuộc hàm trong FD:
- Nếu tạp thuộc tính vế phái tồn tại trong X+, thêm vế phải vào X+.
3. Lập lại đến khi không thể mở rộng X+ được nữa.
### 2. Tìm tất cả các khóa - **Khái niệm khóa**:
- Khóa là tập thuộc tính tối thiểu có thể xác định duy nhất các bộ dữ liệu trongquan hệ.
- **Các bước xác định khóa**:
- Tính bao đóng của tập thuộc tính.
- Kiểm tra tính bao hàm toàn bộ (bao hàm tất cả các thuộc tính trong lược đồ).
- Loại bỏ các thuộc tính thừa.
### 3. Tìm dạng chuẩn cao nhất - **Các dạng chuẩn**:
- **1NF** (First Normal Form): Không có tập hợp lặp.
- **2NF** (Second Normal Form): Thoả 1NF và không có phụ thuộc hàm mỗi phần.
- **3NF** (Third Normal Form): Thoả 2NF và không có phụ thuộc hàm chuyển tiếp.
- **BCNF** (Boyce-Codd Normal Form): Thoả 3NF và mọi phụ thuộc hàm X → Y, X phải là khóa.
- **Các bước chuẩn hóa**:
- Kiểm tra dạng chuẩn hiện tại của lược đồ.
- Phát hiện và xử lý vi phạm.
- Chuyển sang dạng chuẩn cao hơn.
### 4. Tìm phủ tối thiểu - **Khái niệm**:
- Phủ tối thiểu là tập phụ thuộc hàm có số lượng phụ thuộc hàm tính tối thiểu và bảo tòan tính bao hàm của tập gốc.
- **Các bước tìm phủ tối thiểu**:
- Chuẩn hóa vế phải có dạng đơn (Y là một thuộc tính).
- Loại bỏ các phụ thuộc hàm thừa.
- Loại bỏ thuộc tính thừa trong vế trái.
### 5. Phân rã
- **Nguyên tắc phân rã**:
- Giữ tính bảo toàn thông tin.
- Bảo toàn tính bao hàm.
- Hạn chế tối đa vi phạm dạng chuẩn.
- **Các bước phân rã**:
- Xác định các vi phạm dạng chuẩn (nếu có).
- Tách quan hệ thành các quan hệ nhỏ sao cho đáp ứng dạng chuẩn mong muốn.
- Kiểm tra tính bảo toàn thông tin và tính bao hàm.
**Đề thi môn Cơ sở dữ liệu**
### Phần 1: Lý thuyết (5 điểm)
- (1 điểm) Trình bày khái niệm phụ thuộc hàm và các luật Armstrong. Cho ví dụ minh hoạ.
- (1 điểm) Giải thích quy trình tính bao đóng của tập thuộc tính X (X+). Tại sao quy trình này lại quan trọng trong phân tích phụ thuộc hàm?
- (1 điểm) Khái niệm khóa chính trong lược đồ quan hệ là gì? Mô tả các bước để tìm tất cả các khóa.
- (1 điểm) Trình bày các dạng chuẩn của một lược đồ quan hệ. Lê ví dụ minh hoạ cho dạng 3NF và BCNF.
- (1 điểm) Thế nào là phủ tối thiểu? Mô tả quy trình tìm phủ tối thiểu từ tập FD ban đầu.
---
### Phần 2: Thực hành (5 điểm)
**Bài tập 1 (2 điểm): Phụ thuộc hàm**
Cho lược đồ quan hệ R(A, B, C, D, E) và tập phụ thuộc hàm F = {A → BC, B → D, C → E, D → A}.
- Tính bao đóng A+.
- Chứng minh C → E bằng luật Armstrong.
- Kiểm tra R đã ở dạng chuẩn BCNF hay chưa. Nếu chưa, hãy phân rã R.
**Bài tập 2 (1.5 điểm): Tìm khóa**
Cho lược đồ quan hệ R(X, Y, Z, W, V) và tập phụ thuộc hàm F = {X → Y, Y → Z, ZW → V, W → X}.
- Tìm tật cả các khóa của R.
- Lược đồ này đảm bảo dạng chuẩn 3NF hay chưa? Hãy châu chuẩn hóa nếu cần.
**Bài tập 3 (1.5 điểm): Tìm phủ tối thiểu**
Cho lược đồ quan hệ R(P, Q, R, S) và tập phụ thuộc hàm F = {P → QR, Q → RS, PR → S}.
- Rút gọn F để tìm phủ tối thiểu.
- Kiểm tra tính bao hàm của phủ tối thiểu với F ban đầu.
**Giải đề thi môn Cơ sở dữ liệu**
### Phần 1: Lý thuyết (5 điểm)
1. **Khái niệm phụ thuộc hàm và luật Armstrong**
- **Khái niệm**: Phụ thuộc hàm là một quan hệ giữa hai tập thuộc tính trongmột lược đồ quan hệ, được biểu diễn bằng F: X → Y, nghĩa là nếu hai bộ dòng trong quan hệ giống nhau về giá trị của tập X, thì chúng phải giống nhau về giá trị của tập Y.
- **Luật Armstrong**:
- Phép bổ sung: Nếu X → Y và X → Z thì X → YZ.
- Phép suy diễn: Nếu X → Y và Y → Z thì X → Z.
- Phép phân rã: Nếu X → YZ thì X → Y và X → Z.
- **Ví dụ**: Cho R(A, B, C), F = {A → B, B → C}. Từ đây suy ra A → C bằng phép suy diễn.
2. **Quy trình tính bao đóng X+**:
- Khởi tạo X+ = X.
- Lặp: Thêm Y vào X+ nếu X+ đầy đủ điều kiện của một phụ thuộc hàm trong F.
- Dừng khi không thêm được thuộc tính nào.
- **Tầm quan trọng**: Quy trình này giúp tìm khóa và phân tích quan hệ.
3. **Khái niệm khóa chính và các bước tìm tất cả khóa**:
- **Khóa chính**: Tập thuộc tính nhỏ nhất có khả năng xác định duy nhất bộdòng.
- **Quy trình**:
- Tính X+ với X là tập con bất kỳ.
- Kiểm tra xem X+ bao gồm tất cả các thuộc tính trong R hay không.
- Loại bỏ thuộc tính dư thừa trong X.
- **Các dạng chuẩn**:
- 1NF: Loại bỏ tính lập lại, các thuộc tính có dạng đơn.
- 2NF: Ở 1NF và không có phụ thuộc hàm bị phụ thuộc bởi tập con không là khóa.
- 3NF: Ở 2NF và không có phụ thuộc hàm bị phụ thuộc bởi thuộc tính không là khóa.
- BCNF: Ở 3NF và mọi phụ thuộc hàm có vế phải là khóa.
5. **Phủ tối thiểu**:
- Phủ tối thiểu là tập phụ thuộc hàm tính chắc chắn nhất nhưng không làm mất tính bao hàm.
- Quy trình:
- Rút gọn vế phải.
- Loại bỏ các phụ thuộc hàm dư thừa.
---
### Phần 2: Thực hành (5 điểm)
**Bài tập 1**
1. **Tính A+**:
- Khởi tạo: A+ = {A}.
- A → BC → A+ = {A, B, C}.
- B → D → A+ = {A, B, C, D}.
- C → E → A+ = {A, B, C, D, E}.
⇒ A+ = {A, B, C, D, E}.
2. **Chứng minh C → E**:
- Phép bổ sung: C → E đã có trực tiếp trong F.
3. **Kiểm tra BCNF**:
- Phụ thuộc hàm A → BC: A không là khóa.
⇒ Phân rã R thành: R1(A, B, C), R2(A, D, E).
**Bài tập 2**
1. **Tìm tất cả khóa**:
- Tính X+ = {X, Y, Z, W, V}, khóa = {X, W}.
2. **Kiểm tra 3NF**:
- Phụ thuộc hàm Y → Z: Y không là khóa.
⇒ Phân rã thành: R1(X, Y), R2(Y, Z), R3(Z, W, V).
**Bài tập 3**
1. **Tìm phủ tối thiểu**:
- Bước 1: Rút gọn F = {P → Q, Q → R, PR → S}.
2. **Kiểm tra tính bao hàm**:
- Tính PR+ từ F rút gọn và so sánh với F ban đầu. Kết luận: Tính bao hàm được bảo toàn.