Tìm Phủ Tối Thiểu Của Tập Phụ Thuộc Hàm, Phụ Thuộc Hàm Phụ Thuộc Hàm Phụ Thuộc Hàm

Một số hướng dẫn khi thiết kế cơ sở dữ liệu quan hệ

Việc quan trọng nhất khi thiết kế cơ sở dữ liệu quan hệ là ta phải chọn ra tập các lược đồ quan hệ tốt nhất dựa trên một số tiêu chí; nào đó. Và để có được lựa chọn tốt, thì chúng ta cần đặc biệt quan tâm đến mối ràng buộc giữa các dữ liệu trong quan hệ, đó chí;nh là các phụ thuộc hàm.

Phụ thuộc hàm là gì

Để hiểu hơn về câu hỏi tại sao phải thiết kế một cơ sở dữ liệu tốt, chúng ta hãy cùng tìm hiểu ví; dụ sau

RESULT(StNo, StName, SubNo,SubName, Credit, Mark)

Quan hệ RESULT( Kết quả học tập) có các thuộc tí;nh: StNo(Mã sinh viên), StName(Tên sinh viên), SubNo(Mã môn học), SubName(Tên môn học), Credit (Số đơn vị học trình) và Mark (điểm thi của sinh viên trong môn học).Bạn đang xem: Phụ thuộc hàm là gì

Sau đây là minh hoạ dữ liệu của quan hệ RESULT

Minh họa dữ liệu của quan hệ RESULT

Quan hệ trên thiết kế chưa tốt vì

Phụ thuộc hàm

Phụ thuộc hàm trong hệ quản trị cơ sở dữ liệu, có tên tiếng anh là Functional Dependency và viết tắt là FD ,xác định mối quan hệ của một thuộc tính này với một thuộc tính khác trong hệ quản trị cơ sở dữ liệu. Sự phụ thuộc hàm giúp đảm bảo chất lượng dữ liệu trong cơ sở dữ liệu. Sự phụ thuộc hàm có vai trò quan trọng để nhận biết được chất lượng của thiết kế cơ sở dữ liệu. Một phụ thuộc hàm được biểu thị bằng một mũi tên →, Y phụ thuộc vào X được biểu diễn X → Y.

Ví dụ: Bảng nhân viên của công ty tek4

Trong ví dụ này, nếu ta biết giá trị của số ID của Nhân viên, thì có thể lấy được trường tên nhân viên, nơi sống của họ và mức lương. Do vậy, ta có thể nói rằng các trường nơi sống, tên nhân viên và mức lương phụ thuộc vào trường ID Nhân viên.

Các thuật ngữ chính của phụ thuộc hàm

Quy tắc của phụ thuộc hàm

1. Quy tắc ánh xạ: Nếu X là một tập hợp các thuộc tính và Y là tập con của X, thì X giữ một giá trị của Y.
2. Quy tắc mở rộng: Khi x → y và c là tập thuộc tính, thì ac → bc. Việc thêm các thuộc tính sẽ không thay đổi các phụ thuộc hàm căn bản.
3. Quy tắc chuyển đổi: Quy tắc này rất giống với quy tắc bắc cầu trong đại số. Nếu x → y và y → z thì x → z.

Các loại phụ thuộc hàm

1. Phụ thuộc đa giá trị
2. Phụ thuộc không đáng kể
3. Phụ thuộc có đáng kể
4. Phụ thuộc bắc cầu

Phụ thuộc đa giá trị

Dư thừa dữ liệu (Redundancy): Thông tin về sinh viên và môn học bị lặp lại nhiều lần. Nếu sinh viên có mã St01 thi 10 môn học thì thông tin về sinh viên này bị lặp lại 10 lần, tương tự đối với môn học có mã Sub04, nếu có 1000 sinh viên thi thì thông tin về môn học cũng lặp lại 1000 lần Không nhất quán (Inconsistency):Là hệ quả của dư thừa dữ liệu. Giả sử sửa bản ghi thứ nhất, tên sinh viên được chữa thành Nga thì dữ liệu này lại không nhất quán với bản ghi thứ 2 và 3 (vẫn có tên là Mai). Dị thường khi thêm bộ (Insertion anomalies): Nếu muốn thêm thông tin một sinh viên mới nhập trường (chưa có điểm môn học nào) vào quan hệ thì không được vì khoá chí;nh của quan hệ trên gồm 2 thuộc tí;nh StNo và SubNo. Dị thường khi xoá bộ (Deletion anomalies): Giả sử xoá đi bản ghi cuối cùng, thì thông tin về môn học có mã môn học là SubNo=Sub07 cũng mất.

Nhận xét: Qua phân tí;ch trên, ta thấy chúng ta nên tìm cách tách quan hệ trên thành các quan hệ nhỏ hơn.

Bạn đang xem: Phụ thuộc hàm

Trong chương này chúng ta sẽ nghiên cứu về những khái niệm và các thuật toán để có thể thiết kế được những lược đồ quan hệ tốt.

Phụ thuộc hàm(Functional Dependencies) Phụ thuộc hàm (FDs) được sử dụng làm thước đo để đánh giá một quan hệ tốt. FDs và khoá được sử dụng để định nghĩa các dạng chuẩn của quan hệ. FDs là những ràng buộc dữ liệu được suy ra từ ý nghĩa và các mối liên quan giữa các thuộc tí;nh.

Định nghĩa phụ thuộc hàm

Cho r(U), với r là quan hệ và U là tập thuộc tí;nh.

Cho A,B ⊆ U, phụ thuộc hàm X → Y (đọc là X xác định Y) được định nghĩa là:

∀ t, t’ ∈ r nếu t.X = t’.X thì t.Y = t’.Y

(Có nghĩa là: Nếu hai bộ có cùng trị X thì có cùng trị Y)

Phụ thuộc hàm được suy ra từ những quy tắc dữ liệu khi ta khảo sát yêu cầu của bài toán.

Từ mã số bảo hiểm xã hội, ta có thể suy ra được tên của nhân viên (Ssn→ Ename)Từ mã dự án, ta có thể suy ra tên và vị trí; của dự án (PNumber→{PName, PLcation})

Biểu diễn FDs của 2 lược đồ quan hệ EMP_DEPT và EMP_PROJ

Hệ tiên đề Armstrong

Cho lược đồ quan hệ r(U), U là tập thuộc tí;nh, F là tập các phụ thuộc hàm được định nghĩa trên quan hệ r.

Ta có phụ thuộc hàm A → B được suy diễn logic từ F nếu quan hệ r trênU thỏa các phụ thuộc hàm trong F thì cũng thỏa phụ thuộc hàm A → B.

Tập phụ thuộc hàm: F = { A → B, B → C}

Ta có phụ thuộc hàm A → C là phụ thuộc hàm được suy từ F.

Hệ tiên đề Armstrong được sử dụng để tìm ra các phụ thuộc hàm suy diễn từ F.

Hệ tiên đề Armstrong bao gồm:n

1. Phản xạ: Nếu Y → X thì X → Y

2. Tăng trưởng: Nếu Z → U và X → Y thì XZ → YZ (Ký hiệuXZ là X∪Z)

3. Bắc cầu: Nếu X → Y và Y → Z thì X → Z

4. Giả bắc cầu: Nếu X → Y và WY → Z thì XW → Z

5. Luật hợp: Nếu X → Y và X → Z thì X →YZ

6. Luật phân rã: Nếu X → Y và Z → Y thì X → Z

Trong sáu luật trên thì a4, a5, a6 suy được từ a1, a2, a3.

Bao đóng của tập phụ thuộc hàm

Ta gọi f là một phụ thuộc hàm được suy dẫn từ F, ký hiệu là F ├ f nếu tồn tại một chuỗi phụ thuộc hàm: f1, f2,…., fn sao cho fn=f và mỗi fi là một thành viên của F hay được suy dẫn từ những phụ thuộc hàm j=1,…,i-1 trước đó nhờ vào luật dẫn. Bao đóng của F: ký hiệu là F+ là tập tất cả các phụ thuộc hàm được suy từ F nhờ vào hệ tiên đề Armstrong. F+ được định nghĩa:

F + = { X →Y | F X →Y }

Bao đóng của tập thuộc tí;nh X trên F

Bao đóng của tập thuộc tí;nh X xác định trên tập phụ thuộc hàm F ký hiệu là X+ là tập hợp tất cả các thuộc tí;nh có thể suy ra từ X. Ký hiệu:

X + = { Y | F ㅑ X →Y }

X+ có thể được tí;nh toán thông qua việc lặp đi lặp lại cá quy tắc 1, 2, 3 của hệ tiên đề Armstrong.

Xem thêm: Cách Hủy Tất Cả Các Dịch Vụ Ingw Vinaphone Là Gì Vậy Các Bạn? Tự Nhiên Bị

Thuật toán xác định bao đóng của tập thuộc tí;nh X+

X+ := X;repeat oldX+ := X+; for (mỗi phụ thuộc hàm Y →Z trong F) do if Y ⊆ X+ then X+ ∪Zuntil (oldX+ = X+ ); Cho tập phụ thuộc hàm

F = { SSN→ENAME, PNUMBER→{PNAME, PLOCATION},{SSN, PNUMBER} → HOURS} Suy ra: {SSN}+ = {SSN, ENAME}{PNUMBER}+ = {PNUMBER, PNAME, PLOCATION}{SSN, PNUMBER}+ = {SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS}

Khoá của quan hệ

Cho quan hệ r(R), tập K ⊂ R được gọi là khóa của quan hệ r nếu: K+=R và nếu bớt một phần tử khỏi K thì bao đóng của nó sẽ khác R.

Như thế tập K ⊂ R là khoá của quan hệ nếu K+=R và ( K A )+ ≠R , ∀ A ⊂ R.

ChoR = { A, B, C, D, E, G } và tập phụ thuộc hàm:

F= { AB → C , D → EG , BE → C , BC → D , CG → BD, ACD → B, CE → AG}

Ta sẽ thấy các tập thuộc tí;nh

K1 = { A, B } , K2 = {B,E} , K3={C,G} , K4={C,E} , K5 = {C,D}, K6={B,C} đều là khóa của quan hệ.

Như vậy, một quan hệ có thể có nhiều khóa.

Thuật toán tìm khoá

Ý tưởng: Bắt đầu từ tập U vì Closure(U+,F) = U. Sau đó ta bớt dần các phần tử của U để nhận được tập bé nhất mà bao đóng của nó vẫn bằng U.

Thuật toán

Input: Lược đồ quan hệ r(U), tập phụ thuộc hàm F. Output: Khoá K Bước 1: Gán K = U Buớc 2: Lặp lại các bước sau: Loại phần tử A khỏi K mà Closure( K -A,F ) =U Nhận xét

Thuật toán trên chỉ tìm được một khóa. Nếu cần tìm nhiều khóa, ta thay đổi trật tự loại bỏ các phần tử của K. Chúng ta có thể cải thiện tốc độ thực hiện thuật toán trên bằng cách: Trong bước 1 ta chỉ gán K=Left (là tập các phần tử có bên tay trái của các phụ thuộc hàm)

Cho lược đồ quan hệ R = { A,B,C,D,E,G,H,I} và tập phụ thuộc hàm:

F= { AC → B, BI → ACD, ABC → D , H → I , ACE → BCG , CG → AE }

Tìm khoá K?

Ta có Left={A,B,C,H,E,G}

Bước 1: K=Left={A,B,C,H,E,G}

Bước 2

Bước 2BCHEG

Như vậy, {C,H,G} là một khoá của R.

Nếu muốn tìm tất cả các khoá của R, ta cần thay đổi trật tự loại bỏ phần tử của khoá K.

Tập phụ thuộc hàm tương đương

Hai tập phụ thuộc hàm F và G là tương đương nếu

Tất cả các phụ thuộc hàm trong F có thể được suy ra từ G, và Tất cả các phụ thuộc hàm trong G có thể suy ra từ F.

Vì thế, F và G là tương đương nếu F+ = G+

Nếu F và G là tương đương thì ta nói F phủ G hay G phủ F.

Vì thế, thuật toán sau đây sẽ kiểm tra sự tương đương của hai tập phụ thuộc hàm:

F phủ E: ∀ X → Y ∈ E, tí;nh X+ từ F, sau đó kiểm tra xem Y∈ X+ E phủ F: ∀ X → Y ∈ F, tí;nh X+ từ E, sau đó kiểm tra xem Y∈X+

Tập phụ thuộc hàm tối thiểu

Tập phụ thuộc hàm là tối thiểu nếu nó thoả mãn các điều kiện sau:

Chỉ có một thuộc tí;nh nằm ở phí;a bên tay trái của tất cả các phụ thuộc hàm trong F. Không thể bỏ đi bất kỳ một phụ thuộc hàm nào trong F mà vẫn có được một tập phụ thuộc hàm tương đương với F (tức là, không có phụ thuộc hàm dư thừa). Không thể thay thế bất kỳ phụ thuộc hàm X→A nào trong F bằng phụ thuộc hàm Y→A, với Y⊂X mà vẫn có được một tập phụ thuộc hàm tương đương với F (tức là, không có thuộc tí;nh dư thừa trong phụ thuộc hàm)

Nhận xét:

Tất cả các tập phụ thuộc hàm đều có phụ thuộc hàm tối thiểu tương đương với nó. Có thể có nhiều phụ thuộc hàm tối thiểu

Thuật toán: Tìm tập phụ thuộc hàm tối thiểu G của F

1. Đặt G:﹦F. 2. Thay thế tất cả các phụ thuộc hàm X→{A1,A2,…,An} trong G bằng n phụ thuộc hàm: X →A1, X →A2,…, X →An. 3. Với mỗi phụ thuộc hàm X → A trong G,với mỗi thuộc tí;nh B trong X nếu ((G－{X → A}) ∪ {( X －{B}) →A} ) là tương đương với G, thì thay thế X→ A bằng (X － {B}) → A trong G. (Loại bỏ thuộc tí;nh dư thừa trong phụ thuộc hàm) 4. Với mỗi phụ thuộc hàm X → A trong G, nếu (G－{X → A}) tương đương với G, thì loại bỏ phụ thuộc hàm X → A ra khỏi G.(Loại bỏ phụ thuộc hàm dư thừa)

Dạng chuẩn 1(First Normal Form)

Định nghĩa

Một quan hệ ở dạng chuẩn 1 nếu các giá trị của tất cả thuộc tí;nh trong quan hệ là nguyên tử (tức là chỉ có 1 giá trị tại một thời điểm).