Xem mẫu
- CHƯƠNG 4: LÝ THUYẾT THIẾT KẾ CSDL QUAN HỆ
GV: Hoàng Thị Hà
Email: htha@vnua.edu.vn
- Nội dung
1. Giới thiệu
2. Phụ thuộc hàm
3. Khóa tối thiểu
4. Chuẩn hóa cơ sở dữ liệu
Hoang Thi Ha
- Bài 1: Giới thiệu
I. Đặt vấn đề
Hoang Thi Ha
- Xét ví dụ:
S# SNAME STATUS CITY P#, PNAME COLOR WEIGHT PRICE QTY
S1 A1 17 Paris P1 B1 do 23 100 200
S1 A1 17 Paris P2 B2 Xanh 11 150 300
S2 A2 20 Lond P2 B2 Xanh 17 150 250
on
Hoang Thi Ha
- Câu hỏi?
Vậy làm thế nào để thiết kế một CSDL cho
tốt?
Hoang Thi Ha
- Nhận xét
Ưu điểm: Khi thực hiện truy vấn SQL chỉ cần
thực hiện các phép toán một ngôi do đó biếu diễn
câu hỏi dễ dàng, thời gian chi phí đáp ứng nhỏ.
Hoang Thi Ha
- Nhận xét (cont)
Nhược điểm:
Dư thừa dữ liệu (Redundancy): Dễ dàng thấy rằng mỗi khi xuất hiện
tên nhà cung cấp thì địa chỉ của ông ta lại lặp lại trong mối quan hệ.
Không nhất quán (Inconsistency) (dị thường xuất hiện khi sửa dữ
liệu): Là hệ quả của việc dư thừa dữ liệu. VD: khi sửa đổi địa chỉ của
nhà cung cấp ở bộ nào đó còn các bộ khác giữ nguyên thì một nhà
cung cấp có nhiều địa chỉ.
Dị thường khi thêm bộ (Insertion anomalies): Nếu một nhà cung cấp
chưa cung cấp một mặt hàng nào cả, khi đó ta không thể đưa thông tin
về nhà cung cấp đó vì …sẽ phải đưa giá trị nào vào các thuộc tính còn
lại.
Dị thường khi xoá bộ (Deletion anomalies): Là vấn đề ngược lại của
vấn đề trên. Nếu vô tình một nhà cung cấp chỉ mới cung cấp một mặt
hàng duy nhất (giả sử S2, P2) thì sẽ bị mất thông tin về nhà cung cấp
đó.
Hoang Thi Ha
- Cách giải quyết thế nào?.
Để khắc phục những nhược điểm trên thì cần
tách quan hệ trên thành các quan hệ khác nhau
ta được một lược đồ CSDL (tập các lược đồ quan
hệ) sao cho tốt hơn.
Hoang Thi Ha
- Lược đồ VT có thể tách thành 3 lược đồ như
sau
S (S#, SNAME, STATUS, CITY)
P (p#, PNAME, COLOR, WEIGHT, PRICE)
SP (S#, P#, QTY)
Hoang Thi Ha
- Nhận xét
Ưu điểm:
Khắc phục được sự dư thừa dữ liệu
Tránh dị thường
Nhược điểm:
Biểu diễn câu hỏi phức tạp hơn.
Thời gian và chi phí tính toán các phép tính toán kết nối
tăng lên.
Hoang Thi Ha
- II. Các bước thiết kế một Cơ sở dữ liệu
Bước 1: Phân tích toàn bộ các yêu cầu
Bước 2: Nhận diện những thực thế và tìm các
thuộc tính cần lưu trữ của nó.
Bước 3: Nhận diện các mối liên quan giữa các thực
thể
Bước 4: Xác đinh khoá chính
Bước 5: Nhận diện khoá ngoại lai
Bước 6: Thêm các thuộc tính không phải khoá vào
bảng dữ liệu
Bước 7: Xây dựng mạng dữ liệu
Bước 8: Khai báo phạm vi của mỗi thuộc tính
Bước 9: Kiểm tra tính chuẩn của các quan hệ(3NF)
Hoang Thi Ha
- BÀI 2: PHỤ THUỘC HÀM.
Hoang Thi Ha
- I. Khái niệm PTH
Định nghĩa: Cho R(U) là một sơ đồ quan hệ với
U= {A1, A2, …, An} là tập các thuộc tính. X,Y U.
Ta nói rằng X xác định Y (hay Y phụ thuộc hàm vào
X) nếu với hai bộ t1, t2 bất kỳ chúng bằng nhau
trên tập X thì cũng bằng nhau trên tập Y( t1[X] =
t2[X] thì t1[Y] = t2[Y] ).
Ký hiệu: XY
Ví dụ: Trong quan hệ NCC ở trên, SID SNAME, SID
SNAME, SID SADDR
Hoang Thi Ha
- II. Hệ tiên đề Amstrong đối với các phụ thuộc
hàm
2. Hệ tiên đề Amstrong đối với các phụ thuộc hàm.
Cho R(U) là một sơ đồ quan hệ với U = {A1, A2,
…, An} là tập các thuộc tính. X,Y, Z, W U.
Ta ký hiệu XY= X Y
Hệ tiên đề Amstrong:
A1: Phản xạ(reflexivity): Nếu Y X U thì X Y
A2: Tăng trưởng(augmentation): Nếu X Y, Z U thì
XZ YZ
A3: Bắc cầu (transitivity): Nếu X Y, Y Z thì X Z
Hoang Thi Ha
- Định lý:
Hệ tiên đề Amstrong là đúng và đầy đủ(đã được
chứng minh)
Hoang Thi Ha
- Từ hệ tiên đề Armstrong suy ra một số luật
sau đây:
Với X,Y, Z, W U:
a. Luật hợp (Union rule): Nếu X Y, X Z thì X YZ
b. Luật tựa bắc cầu (pseudotransitivity rule): Nếu X Y,
WY Z thì WX Z
c. Luật tách(decomposition): Nếu X Y, Z Y thì X Z
Hoang Thi Ha
- III. Bao đóng(closures of attribute sets)
Đặt vấn đề: Cho quan hệ r, tập PTH F, và tập
phụ thuộc tính X,Y U. Hỏi rằng X Y có thõa
mãn trong r?.
Để trả lời được câu hỏi trên có 2 cách:
Cách 1: Tính F+ và xem X Y F+ hay không?. Như
vậy, ta phải tính F+ , nhưng việc tính F+ là rất khó.
Cách 2: Tính bao đóng của X . Cách thứ 2 này đơn giản
hơn so với cách thức nhất.
Hoang Thi Ha
- Bao đóng(cont)
Bao đóng của tập thuộc tính X
Định nghĩa: Bao đóng của tập thuộc tính X (ký
hiệu X+) bao gồm các thuộc tính A U sao cho
X A F+.
Vậy, bao đóng của 1 tập thuộc tính X cho ta biết được các
thuộc tính mà X xác định nó.
Hoang Thi Ha
- Thuật toán tìm bao đóng của tập thuộc tính
X:
Input: Tập hữu hạn các thuộc tính U, tập các
PTH F trên U và X U
Output: Bao đóng của X đối với F (XF+)
Thuật toán:Tính liên tiếp X0, X1, X2, …X(k) theo
các bước sau:
Bước 1: Đặt X0 = X
Bước 2: Lần lượt xét các phụ thuộc hàm trong F, nếu
Y Z F mà Y Xi ; A Xi và A Z thì Xi+1 = Xi A.
Bước 3: Nếu Xi+1 = Xi , khi đó ta có: XF+ = Xi+1
Hoang Thi Ha
- Ví dụ
Ví dụ: Cho lược đồ R(U, F) , U= {A, B, C, D,E}
F= {A BC, C DE, E A}
Hãy tính CF+
Đặt X0 = C
X 1 = CDE vì (C DE)
X2 = CDEA vì ( E A)
X3 = CDEAB vì (A BC)
X4 = X 3
Vậy : CF+ = CDEAB
Hoang Thi Ha
nguon tai.lieu . vn
