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

Một số hướng dẫn khi phong cách thiết kế cơ sở tài liệu quan hệViệc quan trọng nhất khi phong cách thiết kế cơ sở tài liệu quan hệ là ta phải chọn ra tập những lược đồ quan hệ tốt nhất dựa trên một số ít tiêu chuẩn ; nào đó. Và để có được lựa chọn tốt, thì tất cả chúng ta cần đặc biệt quan trọng chăm sóc đến mối ràng buộc giữa những tài liệu trong quan hệ, đó chí ; nh là những phụ thuộc hàm. Để hiểu hơn về câu hỏi tại sao phải phong cách thiết kế một cơ sở tài liệu tốt, tất cả chúng ta hãy cùng tìm hiểu và khám phá 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ạ tài liệu của quan hệ RESULT Minh họa tài liệu của quan hệ RESULTQuan hệ trên phong cách thiết kế chưa tốt vì 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. tin tức 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ựa như so 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ầnLà hệ quả của dư thừa tài liệu. Giả sử sửa bản ghi thứ nhất, tên sinh viên được chữa thành Nga thì tài liệu này lại không đồng nhất với bản ghi thứ 2 và 3 ( vẫn có tên là Mai ). 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. Giả sử xoá đi bản ghi sau cuối, 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.

Trong chương này tất cả chúng ta sẽ nghiên cứu và điều tra về những khái niệm và những thuật toán để hoàn toàn có thể phong cách 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

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

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 tài liệu khi ta khảo sát nhu yếu của bài toán.
Từ mã số bảo hiểm xã hội, ta hoàn toàn có thể suy ra được tên của nhân viên cấp dưới ( Ssn → Ename ) Từ mã dự án Bất Động Sản, ta hoàn toàn có thể suy ra tên và vị trí ; của dự án Bất Động Sản ( PNumber → { PName, PLcation } )

Hệ tiên đề Armstrong

Biểu diễn FDs của 2 lược đồ quan hệ EMP_DEPT và EMP_PROJCho lược đồ quan hệ r ( U ), U là tập thuộc tí ; nh, F là tập những 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: 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 sống sót 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. ký hiệu là F + là tập toàn bộ những 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 lập trên tập phụ thuộc hàm F ký hiệu là X + là tập hợp toàn bộ những thuộc tí ; nh hoàn toàn có thể suy ra từ X. Ký hiệu :

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

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

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 những 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 những thành phần 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)
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 đổi khác trật tự vô hiệu những thành phần của K. Chúng ta hoàn toàn có thể cải tổ vận tốc thực thi thuật toán trên bằng cách : Trong bước 1 ta chỉ gán K = Left ( là tập những thành phần có bên tay trái của những 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 2 Tập thuộc tí;nh A B C D E G H I Ghi chú ABCHEG x x x x x x x x BCHEG x x x x x x x x Loại A CHEG x x x x x x x x Loại B CHG x x x x x x x x Loại E 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. Tất cả những phụ thuộc hàm trong F hoàn toàn có thể được suy ra từ G, và Tất cả những phụ thuộc hàm trong G hoàn toàn có thể suy ra từ F .Vì thế, F và G là tương tự 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 tự 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 những điều kiện kèm theo 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) Chỉ có một thuộc tí ; nh nằm ở phí ; a bên tay trái của tổng thể những 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 tự với F ( tức là, không có phụ thuộc hàm dư thừa ). Không thể sửa chữa thay thế bất kể phụ thuộc hàmnào trong F bằng phụ thuộc hàm, vớimà vẫn có được một tập phụ thuộc hàm tương tự 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 Tất cả những tập phụ thuộc hàm đều có phụ thuộc hàm tối thiểu tương tự 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).

Ví; dụ

Quan hệ sau đây không phải ở dạng chuẩn 1 Quan hệ sau đây không phải ở dạng chuẩn 1D ữ liệu của quan hệ DEPARTMENT vi phạm 1NF Chuyển quan hệ trên thành dạng chuẩn 1 ( bằng cách xác lập tập thuộc tí ; nh { DNumber, DLocation } là khoá chí ; nh ), ta có :

Nhận xét

Quan hệ ở dạng chuẩn 1 có tồn tại sự dư thừa dữ liệu, trong quan hệ DEPARTMENT, nếu như một phòng có nhiều địa điểm khác nhau thì dữ liệu của 3 thuộc tí;nh (DName, DNumber, DMgrSsn) bị lặp lại nhiều lần. Chúng ta có thể tách quan hệ DEPARTMENT thành 2 quan hệ: Quan hệ ở dạng chuẩn 1 có sống sót sự dư thừa tài liệu, trong quan hệ DEPARTMENT, nếu như một phòng có nhiều khu vực khác nhau thì tài liệu của 3 thuộc tí ; nh ( DName, DNumber, DMgrSsn ) bị lặp lại nhiều lần. Chúng ta hoàn toàn có thể tách quan hệ DEPARTMENT thành 2 quan hệ :Quan hệ DEPARTMENT được tách thành 2 quan hệMô tả tài liệu của 2 quan hệ này

Dạng chuẩn 2(Second Normal Form_2NF)

Minh họa tài liệu của DEPARTMENT và DEPT_LOCATIONS

Định nghĩa

Một quan hệ ở dạng chuẩn 2 nếu Quan hệ đó ở dạng chuẩn 1 Tất cả các thuộc tí;nh không phải là khóa phụ thuộc đầy đủvào khóa. Phụ thuộc đầy đủ: Phụ thuộc hàm Y →Z là phụ thuộc hàm đầy đủ nếu: ∀ A∈Y, ( Y－{A}) →Z Quan hệ đó ở dạng chuẩn 1 Tất cả những thuộc tí ; nh không phải là khóavào khóa. Phụ thuộc khá đầy đủ : Phụ thuộc hàm Y → Z là phụ thuộc hàm không thiếu nếu :

Sơ đồ mô tả

Sơ đồ diễn đạt NF2

Ví; dụ

Quan hệ EMP_PROJ không phải ở dạng chuẩn 2 vì tồn tại 2 phụ thuộc hàm FD2, FD3 là phụ thuộc hàm bộ phận (trái với phụ thuộc hàm đầy đủ)

Quan hệ Emp_projQuan hệ EMP_DEPT ở dạng chuẩn 2
Minh hoạ tài liệu của quan hệ EMP_DEPTMinh hoạ tài liệu của quan hệ THESIS

Nhận xét

Quan hệ ở dạng chuẩn 2 có sự dư thừa thông tin. Dạng chuẩn 2 có thể bị vi phạm khi quan hệ có khóa gồm hơn một thuộc tí;nh.

Xem thêm: Litigation Là Gì – Strategic Litigation

Dạng chuẩn 3 (Third Normal Form)

Quan hệ ở dạng chuẩn 2 có sự dư thừa thông tin. Dạng chuẩn 2 hoàn toàn có thể bị vi phạm khi quan hệ có khóa

Định nghĩa

Một quan hệ ở dạng chuẩn 3 nếu Quan hệ ở dạng chuẩn 2 Và không có chứa các phụ thuộc hàm phụ thuộc bắc cầu vào khoá. Phụ thuộc hàm phụ thuộc bắc cầu: Phụ thuộc hàm Y→Z là phụ thuộc hàm bắc cầu nếu tồn tại hai phụ thuộc hàm:Y→X và X →Z. Quan hệ ở dạng chuẩn 2 Và không có chứa những phụ thuộc hàmPhụ thuộc hàmlà phụ thuộc hàm bắc cầu nếu sống sót hai phụ thuộc hàm :

Biểu diễn bằng sơ đồ

Dạng chuẩn 3NF

Ví; dụ

Quan hệ EMP_DEPT không phải ở dạng chuẩn 3 vì còn tồn tại phụ thuộc hàm DNumber→DName, DMgrSsn là phụ thuộc hàm phụ thuộc bắc cầu vào khoá.

Quan hệ EMP_DEPT không phải ở dạng chuẩn 3Tách quan hệ trên thành 2 quan hệ : EMPLOYEE và DEPARTMENT. 2 quan hệ sau đều ở dạng chuẩn 3 Mô tả tài liệu của quan hệ EMPLOYEE và DEPARTMET

Nhận xét

Trong một cơ sở dữ liệu tốt, các quan hệ nên được chuyển về dạng chuẩn 3. Tuy nhiên, dữ liệu vẫn có khả năng dư thừa khi quan hệ có hai tập khóa dự tuyển gối lẫn nhau, hoặc quan hệ có thuộc tí;nh không khóa xác định một thuộc tí;nh khóa.

Dạng chuẩn Boyce _Codd(Boyce-Codd Normal Form)

Trong một cơ sở tài liệu tốt, những quan hệ nên được chuyển về dạng chuẩn 3. Tuy nhiên, tài liệu vẫn có năng lực dư thừa khi quan hệ có hai tập khóa dự tuyển gối lẫn nhau, hoặc quan hệ có thuộc tí ; nh không khóa xác lập một thuộc tí ; nh khóa .

Định nghĩa

Quan hệ R ở dạng chuẩn BCNF khi toàn bộ những phụ thuộc hàm X → A trong R đều phải có X là khoá của R.

Ví; dụ

Quan hệ sau ở dạng 3NF nhưng không phải BCNF. Minh hoạ tài liệu của quan hệ TEACH vi phạm chuẩn Boyce – CoddĐể nhận được quan hệ ở BCNF, ta hoàn toàn có thể tách quan hệ trên : Cách 1 : R1 ( Student, Instructor ) và R2 ( Student, Course ) Cách 2 : R1 ( Couse, Instructor } và R2 ( Course, Student ) Cách 3 : R1 ( Instructor, Course } và R2 ( Instructor, Student ) Việc tách quan hệ như trên sẽ làm mất đi phụ thuộc hàm FD1.

Định nghĩa

Việc tách quan hệ như trên sẽ làm mất đi phụ thuộc hàm FD1 .

Phép phân rã các lược đồ quan hệ R={A1, A2,. .., An}là việc thay thế lược đồ quan hệ R thành các lược đồ con {R1,. .., Rk}, trong đó Ri⊆R và R=R1 ∪ R2…∪ Rk

Lược đồ quan hệ R

Ta có thể phân rã thành 3 lược đồ R1(MaSV, TenSV, Lop) và Phép phân rã không mất mát thông tin

Cho R là một lược đồ quan hệ, phép rã ρ = ( R1, R2 ,. .., Rn ) và D là tập những phụ thuộc tài liệu. Phép phân rã ρ không mất mát thông tin nếu khi thực thi phép toán liên kết tự nhiên những quan hệ thành phần R1, R2, …, Rn ta vẫn nhận được tác dụng của quan hệ bắt đầu. Ví ; dụ về một phép phân rã có mất mát thông tin : Cho quan hệ Quan hệ mẫu MaSV MaMH Điem 1 A 3 2 A 5 3 A 6 4 B 6 5 C 9 Nếu ta phân rã quan hệ trên thành 2 quan hệ : R1 ( MaSV, MaMH ) và R2 ( MaMH, Điem ) như sau : R1 R2 : R1 MaSV MaMH 1 A 2 A 3 A 4 B 5 C R2 MaMH Điem A 3 A 5 A 6 B 6 C 9 Thực hiện phép liên kết tự nhiên 2 quan hệ R1 và R2 : R1 * R2 = R1*R2 MaSV MaMH Điem 1 A 3 1 A 5 1 A 6 2 A 3 2 A 5 2 A 6 3 A 3 3 A 5 3 A 6 4 B 6 5 C 9 Như vậy, khi nối tự nhiên 2 bảng, ta nhận được quan hệ không giống quan hệ bắt đầu → Phép phân rã trên là mất mát thông tin. Vấn đề đặt ra so với người phong cách thiết kế là phải tìm ra những phép phân rã không làm mất mát thông tin ( chi tiết cụ thể sẽ được trình diễn ở phần sau ). Bây giờ tất cả chúng ta sẽ khám phá một thuật toán để kiểm tra một phép phân rã có mất mát thông tin hay không.

Thuật toán kiểm tra phép phân rã không mất mát thông tin

Input

Lược đồ quan hệ R={A1, A2,. .., An} Tập các phụ thuộc hàm F Phép tách ρ(R1, R2,. .., Rk) Lược đồ quan hệ R = { A1, A2 ,. .., An } Tập những phụ thuộc hàm F Phép tách ρ ( R1, R2 ,. .., Rk )

OutputKết luận phép tách ρ không mất mát thông tin.

Các bước của thuật toán

Bước 1

Thiết lập một bảng với n cột (tương ứng với n thuộc tí;nh) và k dòng (tương ứng với k quan hệ), trong đó cột thứ j ứng với thuộc tí;nh Aj, dòng thứ i ứng với lược đồ Ri. Tại dòng i và cột j, ta điền ký hiệu aj nếu thuộc tinh Aj∈Ri.Ngược lại ta điền ký hiệu bij. Thiết lập một bảng với n cột ( tương ứng với n thuộc tí ; nh ) và k dòng ( tương ứng với k quan hệ ), trong đó cột thứ j ứng với thuộc tí ; nh Aj, dòng thứ i ứng với lược đồ Ri. Tại dòng i và cột j, ta điền ký hiệu aj nếu thuộc tinh Aj ∈ Ri. trái lại ta điền ký hiệu bij .

Bước 2

Xét các phụ thuộc hàm trong F và áp dụng cho bảng trên. Giả sử ta có phụ thuộc hàm X→Y∈F, xét các dòng có giá trị bằng nhau trên thuộc tí;nh X thì làm bằngcác giá trị của chúng trên Y. Ngược lại làm bằng chúng bằng ký hiệu bij. Tiếp tục áp dụng các pth cho bảng (kể cả việc lặp lại các phụ thuộc hàm đã áp dụng) cho tới khi không còn áp dụng được nữa. Xét những phụ thuộc hàm trong F và vận dụng cho bảng trên. Giả sử ta có phụ thuộc hàm X → Y ∈ F, xét những dòng có giá trị bằng nhau trên thuộc tí ; nh Xcác giá trị của chúng trên Y. trái lại làm bằng chúng bằng ký hiệu bij. Tiếp tục vận dụng những pth cho bảng ( kể cả việc lặp lại những phụ thuộc hàm đã vận dụng ) cho tới khi không còn vận dụng được nữa .

Bước 3

Xem xét bảng kết quả. Nếu xuất hiện một dòng chứa toàn giá trị a1, a2 ,…,an thì kết luận phép tách ρ không mất mát thông tin.

Minh họa tài liệu của quan hệ EMP_DEPTTách quan hệ trên thành 2 quan hệ Quan hệ EMPLOYEE được phân rã ( tách ) thành 2 quan hệTập phụ thuộc hàm F Tập phụ thuộc hàm FKiểm tra phép tách trên là không mất mát thông tin : Bước 1 Bước 1 EName SSN BDate Address DNumber DName DMgrSsn EMPLOYEE a1 a2 a3 a4 a5 b16 b17 DEPARTMENT b21 b22 b23 b24 a5 a6 a7 Bước 2 : Xét phụ thuộc hàm DNumber → DName, DMgrSsn. Ta nhận thấy có giá trị a5 ở dòng thứ 2, nên ta sẽ làm bằng giá trị a6, a7 cho dòng thứ 1. Bước 3 : Tồn tại một dòng chứa giá trị a1, a2, .. a7. Kết luận, phép phân rã trên không mất mát thông tin. Bước 3 EName SSN BDate Address DNumber DName DMgrSsn EMPLOYEE a1 a2 a3 a4 a5 a6 a7 DEPARTMENT b21 b22 b23 b24 a5 a6 a7 Sinh viên thực hiện phép nối tự nhiên 2 quan hệ EMPLOYEE và DEPARTMENT trên để kiểm tra có bằng quan hệ ban đầu EMP_DEPT

Thuật toán phân rã lược đồ quan hệ thành các lược đồ quan hệ con ở BCNF

Sinh viên thực thi phép nối tự nhiên 2 quan hệ EMPLOYEE và DEPARTMENT trên để kiểm tra có bằng quan hệ bắt đầu EMP_DEPT

Input

Lược đồ quan hệ R Tập phụ thuộc hàm F Lược đồ quan hệ R Tập phụ thuộc hàm F

Output

Phép phân rã của R không mất thông tin và mỗi lược đồ quan hệ trong phép tách đều ở dạng BCNF so với phép chiếu của F trên lược đồ đó.

Các bước của thuật toán

Ban đầu phép tách ρ chỉ bao gồm R. Nếu S là một lược đồ thuộc ρ và S chưa ở dạng BCNF thì chọn phụ thuộc hàm X → A thỏa trong S, trong đó X không chứa khóa của S và A∉X. {phụ thuộc hàm vi phạm định nghĩa dạng chuẩn BCNF}. Thay thế S trong ρ bởi S1 và S2 như sau S1 = XA, S2 = S\A. Quá trình trên tiếp tục cho đến khi tất cả các lược đồ quan hệ đều ở dạng BCNF Ban đầu phép tách ρ chỉ gồm có R. Nếu S là một lược đồ thuộc ρ và S chưa ở dạng BCNF thì chọn phụ thuộc hàm X → A thỏa trong S, trong đó X không chứa khóa của S và. { phụ thuộc hàm vi phạm định nghĩa dạng chuẩn BCNF }. Thay thế S trong ρ bởi S1 và S2 như sau S1 = XA, S2 = S \ A. Quá trình trên liên tục cho đến khi tổng thể những lược đồ quan hệ đều ở dạng BCNF

Ví; dụ

Cho lược đồ quan hệ R ( CTHRSG ). Trong đó : C: Course; T: Teacher; H: Hour; R: Room; S: Student; G:Group). Và tập các phụ thuộc hàm FC → T: Mỗi khoá học (course) có một thầy (teacher) duy nhất.HR →C: Tại một thời điểm (Hour) ở tại phòng học (room) chỉ có một khoá học duy nhất.HT→ R: Tại một thời điểm và một giáo viên chỉ ở một phòng duy nhấtCS→G: Một sinh viên học một course thì chỉ ở một lớp duy nhất.HS → R: Một sinh viên, ở một thời điểm nhất định chỉ ở trong một phòng duy nhất. C : Course ; T : Teacher ; H : Hour ; R : Room ; S : Student ; G : Group ). Và tập những phụ thuộc hàm FC → T : Mỗi khoá học ( course ) có một thầy ( teacher ) duy nhất. HR → C : Tại một thời gian ( Hour ) ở tại phòng học ( room ) chỉ có một khoá học duy nhất. HT → R : Tại một thời gian và một giáo viên chỉ ở một phòng duy nhấtCS → G : Một sinh viên học một course thì chỉ ở một lớp duy nhất. HS → R : Một sinh viên, ở một thời gian nhất định chỉ ở trong một phòng duy nhất .

Dựa vào thuật toán tìm khoá→Khóa của R là HS.

Yêu cầu : Tách lược đồ R thành những lược đồ con ở dạng BCNF.
Biểu diễn quy trình tách quan hệ R thành những quan hệ ở BCNFNhư vậy, quan hệ R được tách thành 4 quan hệ R1, R21, R221, R222 đều ở BCNF.

Thuật toán phân rã một lược đồ quan hệ thành các lược đồ con ở 3NF.

Input

Lược đồ quan hệ R Tập các phụ thuộc hàm F, không làm mất tí;nh tổng quát giả sử đó là phủ tối thiểu. Lược đồ quan hệ R Tập những phụ thuộc hàm F, không làm mất tí ; nh tổng quát giả sử đó là phủ tối thiểu .

Output

Phép tách không mất mát thông tin trên R thành những lược đồ con ở dạng chuẩn 3 sao cho vẫn bảo toàn những phụ thuộc hàm.

Các bước của thuật toán

Bước 1: Loại bỏ các thuộc tí;nh của R nếu thuộc tí;nh đó không liên quan đến phụ thuộc hàm nào của F.(không có mặt ở cả hai vế của phụ thuộc hàm). Bước 2: Nếu có một phụ thuộc hàm của F liên quan đến tất cả các thuộc tí;nh của R thì kết quả chí;nh là R. Bước 3: Ngoài ra, phép tách ρ đưa ra các lược đồ gồm các thuộc tí;nh XA ứng với phụ thuộc hàm X→A ∈F. Nếu tồn tại các phụ thuộc hàm X→A1, X→A2, …,X→An thuộc F thì thay thế XAi (1 Chú ý: Tại mỗi bước kiểm tra lược đồ R, nếu mỗi thuộc tí;nh không khóa không phụ thuộc bắc cầu vào khóa chí;nh, thì R đã ở dạng 3NF, ngược lại cần áp dụng bước 3 để tách tiếp. Bước 1 : Loại bỏ những thuộc tí ; nh của R nếu thuộc tí ; nh đó không tương quan đến phụ thuộc hàm nào của F. ( không xuất hiện ở cả hai vế của phụ thuộc hàm ). Bước 2 : Nếu có một phụ thuộc hàm của F tương quan đến tổng thể những thuộc tí ; nh của R thì tác dụng chí ; nh là R. Bước 3 : Ngoài ra, phép tách ρ đưa ra những lược đồ gồm những thuộc tí ; nh XA ứng với phụ thuộc hàm X → A ∈ F. Nếu sống sót những phụ thuộc hàm X → A1, X → A2, …, X → An thuộc F thì sửa chữa thay thế XAi ( 1 Chú ý : Tại mỗi bước kiểm tra lược đồ R, thì R đã ở dạng 3NF, ngược lại cần vận dụng bước 3 để tách tiếp .

Ví; dụ

Cho lược đồ quan hệ R ( C, T, H, R, S, G ) với tập phụ thuộc hàm tối thiểu F C → T, HR → C, HT → R, CS → G, HS → R.

Yêu cầu: Phân rã lược đồ quan hệ trên thành các quan hệ con đều ở dạng 3NF.

Xem thêm: Tiền Lương Là Gì – Quy định Pháp Luật Về Tiền Lương

Sử dụng thuật toán tìm khoá→ Khoá chí;nh của R là HS. Thực hiện thuật toán:Bước 1: Không có thuộc tí;nh bị loại bỏBước 2: Không có phụ thuộc hàm nào liên quan tới tất cả các thuộc tí;nhBước 3: Phụ thuộc hàm C→ T vi phạm 3NF (phụ thuộc bắc cầu vào khoá), vì vậy tách R thành R1(C,T) và R2(C,H,R,S,G).Phụ thuộc hàm CS→G vi phạm 3NF(phụ thuộc bộ phận vào khoá), tách R2 thành R21(C,S,G) và R22(C,H,R,S).Phụ thuộc hàm HR→C vi phạm 3NF, tách R22 thành R221(H,R,C) và R222(H,S,R) Sử dụng thuật toán tìm khoá → Khoá chí ; nh của R là HS. Thực hiện thuật toán : Bước 1 : Không có thuộc tí ; nh bị loại bỏBước 2 : Không có phụ thuộc hàm nào tương quan tới tổng thể những thuộc tí ; nhBước 3 : Phụ thuộc hàm C → T vi phạm 3NF ( phụ thuộc bắc cầu vào khoá ), vì thế tách R thành R1 ( C, T ) và R2 ( C, H, R, S, G ). Phụ thuộc hàm CS → G vi phạm 3NF ( phụ thuộc bộ phận vào khoá ), tách R2 thành R21 ( C, S, G ) và R22 ( C, H, R, S ). Phụ thuộc hàm HR → C vi phạm 3NF, tách R22 thành R221 ( H, R, C ) và R222 ( H, S, R )Như vậy, quan hệ R được tách thành những quan hệ sau : R1, R21, R221, R222 Kết quả của phép tách có thể khác nhau phụ thuộc vào thứ tự áp dụng các phụ thuộc hàm khi thực hiện thuật toán. Sinh viên tự kiểm tra xem việc tách quan hệ như trên có mất mát thông tin không. Kết quả của phép tách hoàn toàn có thể khác nhau phụ thuộc vào thứ tự vận dụng những phụ thuộc hàm khi thực thi thuật toán. Sinh viên tự kiểm tra xem việc tách quan hệ như trên có mất mát thông tin không .

Bài tập

Cho một quan hệ R = { A, B, C, D, E, F, G, H, I, J } và tập phụ thuộc hàmF = { A, B → C A → D, E B → F F → G, H D → I, J } Yêu cầu : – Tìm { A } + = { D, E, I, J } – Tìm khóa của quan hệ R. – Tách quan hệ R thành BCNF. – Kiểm tra xem việc tách trên có mất mát thông tin không ?
Cho một quan hệ R = { CourseNo, SecNo, OfferingDept, Credit_Hours, CourseLevel, InstructorSSN, Semester, Year, Days_Hours, RoomNo, NoOfStudents } và tập phụ thuộc hàm : F = { CourseNo → OfferingDept, Credit_Hours, CourseLevel ;

CourseNo, SecNo, Semester, Year →Days_Hours, RoomNo, NoOfStudents, InstructorSSN;

RoomNo, Days_Hours, Semester, Year → InstructorSSN, CourseNo, SecNo }

Yêu cầu

Tìm khóa của quan hệ R. Quan hệ trên thuộc dạng chuẩn mấy? Tách quan hệ về dạng 3NF. Kiểm tra xem việc tách trên có mất mát thông tin không?

Chuyên mục: Tìm khóa của quan hệ R. Quan hệ trên thuộc dạng chuẩn mấy ? Tách quan hệ về dạng 3NF. Kiểm tra xem việc tách trên có mất mát thông tin không ? Chuyên mục : Hỏi Đáp

Source: http://wp.ftn61.com
Category: Sức khỏe