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

      92

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

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

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

Quan hệ RESULT( công dụng 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ới 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ệ nam nữ RESULT


*

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

Quan hệ trên kiến tạo chưa tốt vì

Dư thừa dữ liệu (Redundancy): tin tức về sinh viên và môn học tập bị lặp lại nhiều lần. Trường hợp sinh viên tất cả mã St01 thi 10 môn học thì tin tức về sv này bị lặp lại 10 lần, tương tự đối với môn học gồm mã Sub04, nếu có 1000 sv thi thì tin tức về môn học tập cũng lặp lại 1000 lần Không nhất quán (Inconsistency):Là hệ trái của dư thừa dữ liệu. Giả sử sửa bản ghi lắp thêm nhất, tên sv được chữa thành Nga thì dữ liệu này lại không đồng điệu với bản ghi thứ hai và 3 (vẫn mang tên là Mai). Dị thường xuyên khi thêm bộ (Insertion anomalies): nếu còn muốn thêm tin tức một sinh viên new nhập trường (chưa bao gồm điểm môn học nào) vào tình dục thì ko được vì chưng khoá chí;nh của quan hệ giới tính trên có 2 thuộc tí;nh StNo và SubNo. Dị hay khi xoá cỗ (Deletion anomalies): giả sử xoá đi phiên bản ghi cuối cùng, thì tin tức về môn học bao gồm 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 bọn họ nên search cách tách bóc quan hệ bên trên thành những quan hệ bé dại hơn.

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

phụ thuộc hàm(Functional Dependencies) phụ thuộc vào hàm (FDs) được thực hiện làm thước đo để reviews một quan hệ giới tính tốt. FDs cùng khoá được áp dụng để định nghĩa các dạng chuẩn của quan tiền hệ. FDs là phần nhiều ràng buộc tài liệu được suy ra từ ý nghĩa sâu sắc và những mối tương quan giữa những thuộc tí;nh.

Định nghĩa nhờ vào hàm

Cho r(U), cùng với r là quan liêu hệ với 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à: trường hợp hai bộ tất cả cùng trị X thì bao gồm cùng trị Y)

Phụ trực thuộc hàm được suy ra từ hồ hết quy tắc tài liệu khi ta khảo sát điều tra yêu cầu của bài bác toán.

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


*

màn trình diễn FDs của 2 lược trang bị quan hệ EMP_DEPT với EMP_PROJ

Hệ định đề Armstrong

Cho lược đồ vật quan hệ r(U), U là tập nằm trong tí;nh, F là tập các phụ thuộc hàm được tư tưởng trên quan hệ nam nữ r.

Ta có phụ thuộc hàm A → B được suy diễn xúc tích và ngắn gọn từ F nếu tình dục r trênU thỏa các dựa vào hàm vào F thì cũng thỏa phụ thuộc vào hàm A → B.

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

Ta có phụ thuộc vào hàm A → C là dựa vào hàm được suy tự F.

Hệ định đề Armstrong được áp dụng để tìm ra các dựa vào 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ới X → Y thì XZ → YZ (Ký hiệuXZ là X∪Z)

3. Bắc cầu: Nếu X → Y với 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: giả dụ X → Y và X → Z thì X →YZ

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

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

Bao đóng góp của tập nhờ vào hàm

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

F + = F X →Y

Bao đóng của tập ở trong tí;nh X bên trên F

Bao đóng của tập trực thuộc tí;nh X xác minh trên tập phụ thuộc vào hàm F cam kết hiệu là X+ là tập hợp tất cả các ở trong tí;nh hoàn toàn có thể suy ra trường đoản cú X. Ký hiệu:

X + = Y

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

Xem thêm: 36 Cách Nói Cảm Ơn Và Đáp Lại Lời Cảm Ơn Tiếng Anh Là Gì, 16 Cách Nói Lời Cảm Ơn

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

X+ := X;repeat oldX+ := X+; for (mỗi phụ thuộc vào hàm Y →Z vào F) vì chưng if Y ⊆ X+ then X+ ∪Zuntil (oldX+ = X+ ); mang lại tập phụ thuộc vào hàm

F = SSN→ENAME, PNUMBER→PNAME, PLOCATION,SSN, PNUMBER → HOURS Suy ra: SSN+ = SSN, ENAMEPNUMBER+ = PNUMBER, PNAME, PLOCATIONSSN, PNUMBER+ = SSN, PNUMBER, ENAME, PNAME, PLOCATION, HOURS

Khoá của quan tiền hệ

Cho quan hệ r(R), tập K R được điện thoại tư vấn là khóa của quan hệ nam nữ r nếu: K+=R cùng nếu bớt một phần tử ngoài K thì bao đóng của chính nó sẽ khác R.

Như nuốm tập K R là khoá của dục tình nếu K+=R với ( K A )+ ≠R , A R.

ChoR = A, B, C, D, E, G cùng tập dựa vào 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 trực thuộc tí;nh

K1 = A, B , K2 = B,E , K3=C,G , K4=C,E , K5 = C,D, K6=B,C mọi là khóa của quan liêu hệ.

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

Thuật toán tìm khoá

Ý tưởng: bước đầu từ tập U do Closure(U+,F) = U. Tiếp nối ta sút dần các thành phần của U để cảm nhận tập bé bỏng nhất nhưng bao đóng của chính nó vẫn bằng U.

Thuật toán

Input: Lược vật dụng 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 quá trình sau: Loại bộ phận A khỏi K nhưng Closure( K -A,F ) =U Nhận xét

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

Cho lược vật dụng quan hệ R = A,B,C,D,E,G,H,I và tập dựa vào hàm:

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

Tìm khoá K?

Ta tất 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 BCHEG
Tập nằm trong tí;nhABCDEGHIGhi chú
ABCHEGxxxxxxxx
xxxxxxxxLoại A
CHEGxxxxxxxxLoại B
CHGxxxxxxxxLoại E

Như vậy, C,H,G là 1 trong khoá của R.

Nếu mong mỏi tìm tất cả các khoá của R, ta cần chuyển đổi trật tự loại bỏ thành phần của khoá K.

Tập dựa vào hàm tương đương

Hai tập dựa vào hàm F với G là tương đương nếu

toàn bộ các nhờ vào hàm vào F hoàn toàn có thể được suy ra tự G, và toàn bộ các dựa vào hàm vào G rất có thể suy ra trường đoản cú F.

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

Nếu F và G là tương tự thì ta nói F che G giỏi G lấp F.

Vì thế, thuật toán dưới đây sẽ chất vấn sự tương tự của hai tập phụ thuộc hàm:

F che E: X Y ∈ E, tí;nh X+ trường đoản cú F, tiếp đến kiểm tra coi Y∈ X+ E đậy F: X Y ∈ F, tí;nh X+ tự E, sau đó kiểm tra coi Y∈X+

Tập dựa vào hàm về tối thiểu

Tập phụ thuộc vào hàm là về tối thiểu nếu nó thoả mãn những điều khiếu nại sau:

Chỉ có một trực thuộc tí;nh nằm ở phí;a mặt tay trái của toàn bộ các nhờ vào hàm trong F. Ko thể quăng quật đi ngẫu nhiên một phụ thuộc hàm nào trong F cơ mà vẫn đã đạt được một tập nhờ vào hàm tương đương với F (tức là, không có dựa vào hàm dư thừa). Không thể ráng thế ngẫu nhiên phụ trực thuộc hàm XA nào trong F bằng dựa vào hàm YA, cùng với YX mà vẫn đã đạt được một tập nhờ vào hàm tương tự với F (tức là, không có thuộc tí;nh dư quá trong dựa vào hàm)

Nhận xét:

tất cả các tập dựa vào hàm đều phải sở hữu phụ thuộc hàm buổi tối thiểu tương tự với nó. Tất cả thể có rất nhiều phụ trực thuộc hàm buổi tối thiểu

Thuật toán: search tập nhờ vào hàm buổi tối thiểu G của F

1. Đặt G:﹦F. 2. Sửa chữa tất cả các nhờ vào hàm X→A1,A2,…,An vào G bằng n nhờ vào hàm: X →A1, X →A2,…, X →An. 3. Cùng với mỗi phụ thuộc vào hàm X → A trong G,với mỗi thuộc tí;nh B trong X nếu như ((G-X → A) ∪ ( X -B) →A ) là tương đương với G, thì sửa chữa X→ A bằng (X - B) → A vào G. (Loại bỏ thuộc tí;nh dư thừa trong dựa vào hàm) 4. Cùng với mỗi phụ thuộc vào hàm X → A trong G, giả dụ (G-X → A) tương đương với G, thì vứt bỏ phụ thuộc hàm X → A thoát khỏi G.(Loại bỏ phụ thuộc hàm dư thừa)

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

Định nghĩa

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