Nội dung
Một số khái niệm
Các vấn đề trong thiết kế sơ đồ quan hệ
Chuẩn hóa
1NF
2NF
3NF
Boyce Codd (BCNF)
47 trang |
Chia sẻ: phuongt97 | Lượt xem: 663 | Lượt tải: 0
Bạn đang xem trước 20 trang nội dung tài liệu Bài giảng Cơ sở dữ liệu (Database) - Chương 4: Phụ thuộc hàm và chuẩn hóa cơ sở dữ liệu quan hệ - Lê Thị Lan, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CHƯƠNG 4:
Phụ thuộc hàm và chuẩn hóa
cơ sở dữ liệu quan hệ
Nội dung
Một số khái niệm
Các vấn đề trong thiết kế sơ đồ quan hệ
Chuẩn hóa
1NF
2NF
3NF
Boyce Codd (BCNF)
Nội dung
Một số khái niệm
Các vấn đề trong thiết kế sơ đồ quan hệ
Chuẩn hóa
1NF
2NF
3NF
Boyce Codd (BCNF)
Một số khái niệm
Phụ thuộc hàm
Luật của phụ thuộc hàm
Bao đóng của tập phụ thuộc hàm
Các loại khóa
Thuộc tính thuộc khóa
Phụ thuộc hàm
Phụ thuộc hàm (functional dependency) được
sử dụng như 1 độ đo để đánh giá chất lượng
của tập sơ đồ quan hệ được thiết kế
Các phụ thuộc hàm và các khóa được dùng
để xác định các chuẩn của quan hệ
Phụ thuộc hàm là các ràng buộc được xác
định từ ngữ nghĩa và mối quan hệ bên trong
của các thuộc tính
Phụ thuộc hàm
Một tập thuộc tính X xác định tập thuộc tính Y nếu giá trị
trong X cho phép xác định một giá trị duy nhất trong Y
Y phụ thuộc hàm vào X
X Y là đúng nếu bất cứ hai bộ nào có cùng giá trị X thì
phải có cùng giá trị Y
Nếu t1[X]=t2[X], thì t1[Y]=t2[Y] với mọi bộ r(R)
X Y trong R xác định một ràng buộc cho tất cả các thể
hiện r(R)
Phụ thuộc hàm chính là các ràng buộc trên dữ liệu
Ví dụ về phụ thuộc hàm
Mã số bảo hiểm cho phép xác định tên nhân viên
SSN ENAME
Mã dự án cho phép xác định tên dự án và địa điểm
dự án
PNUMBER {PNAME, PLOCATION}
Mã số bảo hiểm của nhân viên SSN và mã dự án
xác định số giờ mà nhân viên phải làm trong dự án
{SSN, PNUMBER} HOURS
Phụ thuộc hàm
Một phụ thuộc hàm là một tính chất của các
thuộc tính trong lược đồ quan hệ R
Một ràng buộc phải đúng cho tất cả các thể
hiện của lược đồ quan hệ r(R)
Các luật cho phụ thuộc hàm
Với một tập phụ thuộc hàm F, ta có thể suy ra các phụ
thuộc hàm mới
Luật Armstrong
A1. (Phản xạ - Reflexive) Nếu Y là tập con của X thì X Y
A2. (Tăng trưởng - Augmentation) Nếu X Y, thì XZ
YZ (Chú ý: XZ có nghĩa là X U Z)
A3. (Bắc cầu - Transitive) Nếu X Y và Y Z, thì X Z
A1, A2, A3 tạo một tập các luật đúng và đầy đủ
Các luật cho phụ thuộc hàm
Luật tách - Decomposition
If X YZ, then X Y and X Z
Luật hợp
If X Y and X Z, then X YZ
Luật tựa bắc cầu - Psuedotransitivity
If X Y and WY Z, then WX Z
Bao đóng của F cho tập phụ thuộc hàm là tập F+
của các phụ thuộc hàm suy diễn từ F
Phụ thuộc hàm đầy đủ
Phụ thuộc hàm đầy đủ (Full functional
dependency): Y Z là phụ thuộc hàm đầy
đủ nếu bỏ đi bất cứ một thuộc tính nào trong
Y thì phụ thuộc hàm này không còn đúng
{SSN, PNUMBER} HOURS là một phụ thuộc hàm đầy đủ bởi
vì SSN HOURS hoặc PNUMBER HOURS không còn đúng
{SSN, PNUMBER} ENAME không phải là phụ thuộc hàm
đầy đủ (gọi là phụ thuộc hàm bộ phận) bởi vì SSN ENAME
Một số khái niệm khác
Phụ thuộc hàm tầm thường (Trivial
functional dependency)
{Employee ID, Employee Address} →
{Employee Address} là phụ thuộc hàm tầm
thường vì {Employee Address} → {Employee
Address}.
Khóa
• Siêu khóa (Superkey)
K R
• Khóa (Candidate Key)
K R
Không tồn tại K’ K, sao cho K’ R (tối thiểu)
• Khóa chính (Primary Key) Khóa chính
Khóa
Siêu khóa
• Thuộc tính thuộc khóa (Prime attribute) là 1 thuộc tính
trong khóa chính K
Khóa - ví dụ
Bảng employee (employeeID, name, job, và
departmentID)
Siêu khóa: {employeeID }, {employeeID,
Name}, {employeeID, Name, job}, và
{employeeID, Name, job, departmentID}.
employeeID là một khóa
Bao đóng của tập thuộc tính
Định nghĩa:
X, Y là các thuộc tính của R:
X Y nằm trong F+ Y X+
Algorithm:
•X(0) := X
•Repeat
X(i+1) := X(i) Z,
where Z is the set of
attributes such that there
exists YZ in F, and Y X(i)
•Until X(i+1) := X(i)
•Return X(i+1)
Bao đóng của tập thuộc tính
R = (A, B, C, D, E)
F = {ABC, CDE, BD, EA}
Tính A+ và B+:
A+ := {A}
:= {A, B, C} ABC và {A} A+
:= {A, B, C, D} BD và {B} A+
:= {A, B, C, D, E}CDE và {C, D}
A+ không thay đổi
Bao đóng của tập thuộc tính
B+ := {B}
:= {B, D} BD và {B} B+
dừng giải thuật vì B+ không thay đổi nữa
Bao đóng của tập thuộc tính
A+ là bao đóng của tập thuộc tính
Nếu A+ = R, thì A là một siêu khóa của quan
hệ R
Tính khóa dựa trên bao đóng
tập thuộc tính
R = (A, B, C, D, E)
F = {ABC, CDE, BD, EA}
Liệt kê tất cả các khóa của R
• A+ = {A, B, C, D, E}do đó AABCDE, thì
A là khóa của quan hệ R.
• Vì EA, nên EABCDE. (bắc cầu)
• Vì CDE, nên CDABCDE. (bắc cầu)
• Vì BD, nên BCCD, BCABCDE. (tăng
trưởng, bắc cầu)
Thuộc tính khóa - Ví dụ
Cho lược đồ quan hệ R trên tập thuộc tính U={A, B, C,
D} với các phụ thuộc hàm AB->C và B->D và BC->A.
Xác định thuộc tính khóa và thuộc tính không khóa
Nội dung
Một số khái niệm
Các vấn đề trong thiết kế sơ đồ quan hệ
Chuẩn hóa
1NF
2NF
3NF
Boyce Codd (BCNF)
Các quy tắc cho thiết kế cơ sở
dữ liệu quan hệ
Thiết kế cơ sở dữ liệu quan hệ: cách nhóm các
thuộc tính đề tạo thành các lược đồ quan hệ
Các chuẩn 1NF 2NF 3NF BCNF
Dư thừa dữ liệu và các dị
thường khi cập nhật
Dư thừa dữ liệu
Các dị thường:
Dị thường khi thêm bộ
Dị thường khi xóa bộ
Dị thường khi thay đổi
Ví dụ về các dị thường
Ví dụ quan hệ:
EMP_PROJ ( Emp#, Proj#, Ename, Pname, No_hours)
Dị thường khi cập nhật
Chuyển tên của dự án từ P1 từ “Billing” thành “Customer-
Accounting” phải cập nhật nhiều lần do 100 nhân viên đang làm
trong dự án P1
Dị thường khi thêm bộ
Không thể thêm một dự án không có nhân viên.
Không thể thêm một nhân viên nếu nhân viên đó chưa được chỉ
định vào 1 dự án cụ thể.
Ví dụ về các dị thường
Dị thường xóa bộ
Khi xóa 1 dự án thì toàn bộ nhân viên làm cho dự án bị xóa
Khi xóa một nhân viên của dự án chi bao gồm 1 nhân viên thì kết
quả là dự án bị xóa theo
Dư thừa dữ liệu
Không nhất quán
Đảm bảo cơ sở dữ liệu thiết kế không chứa các dị
thường thêm, xóa và cập nhật
Giá trị Null trong các bộ
Các quan hệ phải được thiết kế sao cho các bộ của
nó có giá trị NULL ít nhất có thể
Các thuộc tính thường có giá trị NULL có thể được đặt
trong 1 quan hệ riêng
Giá trị NULL xảy ra do:
thuộc tính không hợp lệ
giá trị của thuộc tính không biết (có thể tồn tại)
giá trị của thuộc tính tồn tại nhưng không chưa xác định
được
Bộ giả
Thiết kế không tốt có thể sinh ra lỗi khi thực hiện
các thao tác kết nối
Các quan hệ phải được thiết kế để đảm bảo không
có bộ giả nào được sinh ra khi thực hiện kết nối tự
nhiên
Nội dung
Một số khái niệm
Các vấn đề trong thiết kế sơ đồ quan hệ
Chuẩn hóa
1NF
2NF
3NF
Boyce Codd (BCNF)
Chuẩn hóa
Chuẩn hóa: Là một quá trình chia nhỏ quan hệ
thiết kế không tốt thành tập các quan hệ nhỏ hơn
Các chuẩn: dùng khóa và các phụ thuộc hàm để
xác định dạng chuẩn của quan hệ
Chuẩn 2, chuẩn 3, chuẩn Boyce-Codd dựa vào khóa và
các phụ thuộc hàm
Chuẩn 4 dựa vào khóa và các ràng buộc đa trị
Chuẩn 1
Không cho phép các thuộc tính đa trị, thuộc
tính không nguyên tố
Bài tập: xác định quan hệ nào là
1NF
Chuẩn 2
Một quan hệ R ở dạng chuẩn 2 nếu tất cả thuộc tính
không khóa A trong R là phụ thuộc đầy đủ vào khóa
chính
R có thể chia thành các quan hệ ở dạng chuẩn 2 thông qua
quá trình chuẩn hóa dạng chuẩn 2
Chuẩn 2: Ví dụ
FIRST (supplier_no, status, city, part_no,
quantity)
Phụ thuộc hàm:
(supplier_no, part_no) -> quantity
(supplier_no) -> status
(supplier_no) -> city
city -> status
Chuẩn 2
Hai thuộc tính city và status chỉ phụ thuộc
một phần vào khóa chính (supplier_no và
part_no)
INSERT: Không thể thêm một nhà cung cấp (supplier) ở một thành phố
nào đó nếu nhà cung cấp đó chưa tham gia cung cấp.
DELETE: Nếu xóa hàng cuối cùng của một nhà cung cấp thì thông tin
về địa chỉ của nhà cung cấp bị xóa.
UPDATE: Thông tin về thành phố (city) xuất hiện nhiều lần cho cùng
một nhà cung cấp->không đồng nhất khi thay đổi thông tin.
Phân rã quan hệ thành 2 quan hệ dạng
chuẩn 2NF:
SECOND (supplier_no, status, city)
SUPPLIER_PART (supplier_no, part_no,
quantity)
Chuẩn 3
Định nghĩa
Phụ thuộc hàm bắc cầu (Transitive functional
dependency): Tập thuộc tính Z không phải là khóa và
tồn tại X Y và Y Z
Ví dụ
SSN DMGRSSN là một phụ thuộc hàm bắc cầu vì
SSN DNUMBER và DNUMBER DMGRSSN
SSN ENAME không phải là phụ thuộc hàm bắc cầu
vì không tồn tại tập thuộc tính X sao cho SSN X và X
ENAME
Chuẩn 3
Một quan hệ R ở dạng chuẩn 3 nếu nó :
ở dạng chuẩn 2 và
không có thuộc tính không khóa A trong R phụ
thuộc bắc cầu vào khóa chính
Chuân 3NF
SECOND (supplier_no, status, city)
supplier_no -> status
supplier_no ->city
city -> status
SUPPLIER_CITY (supplier_no, city)
CITY_STATUS (city, status)
Chuẩn Boyce-Codd
(Boyce-Codd Normal Form)
Một quan hệ R là ở dạng chuẩn Boyce-Codd nếu có
một phụ thuộc hàm X A trong R thì X là một
khóa của R
Chuẩn sau luôn luôn mạnh hơn chuẩn trước:
Tất cả các quan hệ ở dạng chuẩn 2 đều ở dạng chuẩn 1
Tất cả các quan hệ ở dạng chuẩn 3 đều ở dạng chuẩn 2
Tất cả các quan hệ ở dạng chuẩn Boyce-Codd đều ở dạng chuẩn
3
Tuy nhiên có một số quan hệ ở dạng chuẩn 3 nhưng
không ở dạng chuẩn Boyce-Codd.
Mục đích là chuẩn hóa để quan hệ ở dạng chuẩn 3 hoặc
dạng chuẩn Boyce-Codd
Ví dụ
title year length filmType studioNam starName
e
Star Wars 1977 124 color Fox Fisher
Star Wars 1977 124 color Fox Hamill
Star Wars 1977 124 color Fox Ford
Mighty Ducks 1991 104 color Disney Esteves
Wayne’s World 1992 95 color Paramount Carvey
Wayne’s World 1992 95 color Paramount Meyers
Ví dụ
{title, year, starName} là candidate key
title, year length, filmType, studioName
Ví dụ
Chia quan hệ Movies thành 2 quan hệ
Quan hệ chứa tất cả các thuộc tính xuất hiện trong phụ
thuộc hàm
{title, year, length, filmType, studioName}
Quan hệ chứa khóa và thuộc tính ở phía bên trái của phụ
thuộc hàm
{title, year, starName}
Bài tập
Customer-schema = (cname, street, ccity)
cname ->street, ccity
Branch-schema = (bname, assets, bcity)
bname ->assets, bcity
Loan-info-schema = (bname, cname, loan#,
amount)
loan# ->amount, bname
Bài tập
Cho quan hệ
Book(Book_title, Authorname, Book_type,
Listprice, Author_affil, Publisher)
Và các ràng buộc
Book_title Publisher, Book_type
Book_type Listprice
Authorname Author_affil
Xác định quan hệ ở dạng chuẩn nào?
Bài tập: Xác định dạng chuẩn
của quan hệ
R=(A, B, C, D, E, F)
FD = {AB, BCD, CE, BF}
• Xác định dạng chuẩn của quan hệ
Các file đính kèm theo tài liệu này:
- bai_giang_co_so_du_lieu_database_chuong_4_phu_thuoc_ham_va_c.pdf