Phụ Thuộc Hàm Đầy Đủ Là Gì

Một số gợi ý lúc thi công cửa hàng dữ liệu quan hệ

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

Để đọc hơn về câu hỏi tại vì sao yêu cầu thiết kế một các đại lý dữ liệu xuất sắc, bọn họ hãy thuộc tò mò ví; dụ sau

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

Quan hệ RESULT( Kết quả học tập) gồm những ở trong tí;nh: StNo(Mã sinc viên), StName(Tên sinc viên), SubNo(Mã môn học), SubName(Tên môn học), Credit (Số đơn vị học tập trình) cùng Mark (điểm thi của sinch viên trong môn học).quý khách sẽ xem: Prúc thuộc hàm là gì

Sau đấy là minc hoạ dữ liệu của tình dục RESULT


*

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

Quan hệ trên xây dựng chưa giỏi vì

Dư thừa tài liệu (Redundancy): tin tức về sinh viên và môn học bị tái diễn những lần. Nếu sinch viên có mã St01 thi 10 môn học thì lên tiếng về sinch viên này bị tái diễn 10 lần, giống như đối với môn học tập bao gồm mã Sub04, giả dụ gồm 1000 sinc viên thi thì biết tin về môn học cũng lặp lại 1000 lần Không đồng điệu (Inconsistency):Là hệ trái của dư thừa dữ liệu. Giả sử sửa bản ghi đầu tiên, thương hiệu sinh viên được chữa thành Nga thì tài liệu này lại ko nhất quán với bạn dạng ghi thứ 2 với 3 (vẫn có tên là Mai). Dị thường xuyên lúc thêm cỗ (Insertion anomalies): Nếu ước ao thêm công bố một sinh viên bắt đầu nhập ngôi trường (chưa tồn tại điểm môn học nào) vào dục tình thì ko được vì khoá chí;nh của dục tình trên gồm 2 ở trong tí;nh StNo và SubNo. Dị thường xuyên lúc xoá bộ (Deletion anomalies): Giả sử xoá đi bạn dạng ghi ở đầu cuối, thì lên tiếng về môn học gồm mã môn học tập là SubNo=Sub07 cũng mất.

Nhận xét: Qua phân tí;ch trên, ta thấy họ buộc phải kiếm tìm biện pháp bóc tình dục trên thành các quan hệ tình dục bé dại hơn.

Bạn đang xem: Phụ thuộc hàm đầy đủ là gì

Trong cmùi hương này chúng ta đang phân tích về hồ hết định nghĩa cùng những thuật toán để có thể xây dựng được số đông lược đồ vật quan hệ tốt.

Prúc trực thuộc hàm(Functional Dependencies) Prúc trực thuộc hàm (FDs) được sử dụng làm thước đo để reviews một dục tình tốt. FDs cùng khoá được sử dụng nhằm khái niệm các dạng chuẩn của quan hệ giới tính. FDs là hầu hết ràng buộc dữ liệu được suy ra từ ý nghĩa sâu sắc với các mối tương quan giữa những thuộc tí;nh.

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

Cho r(U), với r là quan hệ nam nữ với U là tập nằm trong tí;nh.

Cho A,B U, nhờ vào hàm X → Y (phát âm là X xác định Y) được định nghĩa là:

t, t’ ∈ r ví như t.X = t’.X thì t.Y = t’.Y

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

Phú nằm trong hàm được suy ra tự phần nhiều phép tắc dữ liệu Khi ta khảo sát yên cầu của bài toán.

Từ mã số bảo đảm làng 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, ta rất có thể suy ra tên cùng vị trí; của dự án công trình (PNumber→PName, PLcation)


*

Biểu diễn FDs của 2 lược đồ tình dục EMP_DEPT cùng EMP_PROJ

Hệ định đề Armstrong

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

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

Tập dựa vào hàm: F = A → B, B → C

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

Hệ định đề Armsvào được thực hiện nhằm đưa ra những nhờ vào hàm diễn dịch trường đoản cú 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 cùng 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 cùng Z → Y thì X → Z

Trong sáu qui định bên trên thì a4, a5, a6 suy được trường đoản cú a1, a2, a3.

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

Ta Call f là một phụ thuộc hàm được suy dẫn từ F, cam kết hiệu là F ├ f ví như mãi mãi một chuỗi phụ thuộc hàm: f1, f2,…., fn thế nào cho fn=f cùng từng fi là 1 trong member của F tuyệt được suy dẫn từ bỏ số đông dựa vào hàm j=1,…,i-1 trước đó phụ thuộc vào quy định dẫn. Bao đóng góp của F: cam kết hiệu là F+ là tập tất cả những phụ thuộc hàm được suy tự F phụ thuộc hệ định đề Armstrong. F+ được định nghĩa:

F + = X →Y

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

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

X + = Y

X+ hoàn toàn có thể được tí;nh toán thông qua Việc lặp đi lặp lại cá phép tắc 1, 2, 3 của hệ định đề Armstrong.

Xem thêm: Anino - Pinoy Có Nghĩa Là Gì

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

X+ := X;repeat oldX+ := X+; for (từng nhờ vào hàm Y →Z trong F) vì chưng if Y ⊆ X+ then X+ ∪Zuntil (oldX+ = X+ ); Cho tập nhờ 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 liêu hệ

Cho quan hệ r(R), tập K R được gọi là khóa của dục tình r nếu: K+=R và trường hợp bớt một phần tử ngoài K thì bao đóng góp của chính nó sẽ không giống R.

Nhỏng vắt tập K R là khoá của quan hệ giới tính nếu như 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 đang 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 hệ nam nữ.

Như vậy, một quan hệ nam nữ hoàn toàn có thể có khá nhiều khóa.

Thuật tân oán kiếm tìm khoá

Ý tưởng: Bắt đầu từ bỏ tập U vày Closure(U+,F) = U. Sau đó ta sút dần dần các phần tử của U nhằm nhận được tập nhỏ nhắn tốt nhất mà lại bao đóng góp của chính nó vẫn bằng U.

Thuật toán

Input: Lược đồ dùng quan hệ r(U), tập nhờ vào 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 phần tử A khỏi K cơ mà Closure( K -A,F ) =U Nhận xét

Thuật toán thù trên chỉ tìm được một khóa. Nếu nên search những khóa, ta biến đổi cô đơn từ bỏ sa thải những bộ phận của K. Chúng ta hoàn toàn có thể nâng cao tốc độ tiến hành thuật tân oán bê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 tất cả mặt tay trái của những phụ thuộc vào hàm)

Cho lược đồ dùng quan hệ giới tính R = A,B,C,D,E,G,H,I cùng 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 gồm Left=A,B,C,H,E,G

Cách 1: K=Left=A,B,C,H,E,G

Cách 2

Cách 2 BCHEG
Tập nằm trong tí;nh A B C D E G H I Ghi chú
ABCHEG x x x x x x x x
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

Bởi vậy, C,H,G là một trong những khoá của R.

Nếu hy vọng tra cứu tất cả những khoá của R, ta cần biến hóa riêng biệt từ bỏ loại trừ phần tử của khoá K.

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

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

Tất cả các phụ thuộc vào hàm trong F có thể được suy ra trường đoản cú G, cùng Tất cả những phụ thuộc vào hàm vào G hoàn toàn có thể suy ra trường đoản cú F.

Vì nỗ lực, F cùng G là tương đương trường hợp F+ = G+

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

Vì cố kỉnh, thuật tân oán dưới đây vẫn kiểm soát sự tương đương của nhị tập phụ thuộc vào hàm:

F đậy E: X Y ∈ E, tí;nh X+ từ bỏ F, sau đó khám nghiệm xem Y∈ X+ E đậy F: X Y ∈ F, tí;nh X+ trường đoản cú E, sau đó bình chọn xem Y∈X+

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

Tập phụ thuộc vào hàm là buổi tối thiểu trường hợp nó chấp thuận các điều kiện sau:

Chỉ tất cả một trực thuộc tí;nh nằm ở phí;a bên tay trái của toàn bộ những phụ thuộc hàm trong F. Không thể vứt đi ngẫu nhiên một phụ thuộc hàm như thế nào vào F cơ mà vẫn đạt được một tập phụ thuộc hàm tương đương với F (Tức là, không tồn tại phụ thuộc vào hàm dư thừa). Không thể thay thế sửa chữa bất kỳ nhờ vào hàm XA làm sao trong F bằng nhờ vào hàm YA, với YX nhưng 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ó trực thuộc tí;nh dư vượt trong dựa vào hàm)

Nhận xét:

Tất cả những tập dựa vào hàm đều sở hữu nhờ vào hàm buổi tối tđọc tương đương với nó. Có thể có rất nhiều nhờ vào hàm về tối tphát âm

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

1. Đặt G:﹦F. 2. Txuất xắc cố tất cả các nhờ vào hàm X→A1,A2,…,An trong G bằng n phụ thuộc vào hàm: X →A1, X →A2,…, X →An. 3. Với mỗi dựa vào hàm X → A trong G,với mỗi thuộc tí;nh B vào 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ởi (X - B) → A vào G. (Loại bỏ trực thuộc tí;nh dư quá vào dựa vào hàm) 4. Với mỗi nhờ vào hàm X → A vào G, nếu như (G-X → A) tương đương cùng với G, thì thải trừ nhờ vào hàm X → A thoát ra khỏi G.(Loại vứt phụ thuộc vào hàm dư thừa)

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

Định nghĩa

Một quan hệ ở dạng chuẩn chỉnh 1 trường hợp các cực hiếm của tất cả ở trong tí;nh vào quan hệ nam nữ là ngulặng tử (Tức là chỉ có 1 giá trị trên 1 thời điểm).