Phụ thuộc hàm đầy đủ là gì

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

Để đọc hơn về thắc mắc tại sao phải thi công một cơ sở tài liệu tốt, bọn họ hãy cùng khám phá ví; dụ sau

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

Quan hệ RESULT( tác 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 vào hàm là gì

Sau đó là minh hoạ tài liệu của quan hệ nam nữ RESULT


*

Minh họa tài liệu của quan hệ giới tính RESULT

Quan hệ trên xây đắp chưa tốt vì

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

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

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


Table of Contents


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

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

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

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

Bạn đã xem: nhờ vào Hàm ĐầY Đủ Là Gì

Cho A, B U, nhờ vào hàm X → Y (đọc là X xác định Y) được quan niệm là:

t, t’ ∈ r trường hợp t.X = t’.X thì t.Y = t’.Y

(Có nghĩa là: giả dụ hai bộ gồm cùng trị X thì bao gồm cùng trị Y)

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

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



màn biểu diễn FDs của 2 lược thiết bị quan hệ EMP_DEPT cùng EMP_PROJ

Hệ tiên đề Armstrong

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

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

Tập nhờ vào hàm: F = A → B, B → C

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

Hệ tiên đề Armstrong được sử dụng để đưa ra các nhờ vào hàm suy diễn từ bỏ 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 cùng 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 cùng 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 pháp trên thì a4, a5, a6 suy được trường đoản cú a1, a2, a3.

Bao đóng của tập dựa vào hàm

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

F + = X →Y

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

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

X + = Y

Thuật toán khẳng định bao đóng góp của tập ở trong tí;nh X+

X+ := X;repeat oldX+ := X+; for (mỗi nhờ vào hàm Y →Z trong F) vì if Y ⊆ X+ then X+ ∪Zuntil (oldX+ = X+ ); cho 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 dục tình r(R), tập K R được điện thoại tư vấn là khóa của dục tình r nếu: K+=R cùng nếu bớt một trong những phần tử khỏi K thì bao đóng của chính nó sẽ không giống R.

Xem thêm: Từ Tiamo Nghĩa Là Gì ? Giải Đáp Tiamo Có Nghĩa Là Gì

Như nạm tập K R là khoá của quan hệ tình dục nếu K+=R và ( K A )+ ≠R , A R.

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

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

Ta vẫn 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 rất nhiều là khóa của quan hệ.

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

Thuật toán tìm kiếm khoá

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

Thuật toán

Input: Lược vật quan hệ r(U), tập phụ thuộc vào hàm F. Output: Khoá K bước 1: Gán K = U Buớc 2: Lặp lại công việc sau: Loại bộ phận A ngoài K nhưng Closure( K -A, F ) =U Nhận xét

Thuật toán trên chỉ tìm kiếm được một khóa. Nếu buộc phải tìm những khóa, ta thay đổi trật tự thải trừ các thành phần 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 thành phần có bên 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 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 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 trực thuộc tí;nhABCDEGHIGhi chú
ABCHEGxxxxxxxx
xxxxxxxxLoại A
CHEGxxxxxxxxLoại B
CHGxxxxxxxxLoại E

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

Nếu ước ao tìm toàn bộ các khoá của R, ta cần biến hóa trật tự các loại bỏ thành phần của khoá K.

Tập nhờ 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 phụ thuộc vào hàm vào F hoàn toàn có thể được suy ra từ bỏ G, và tất cả các nhờ vào hàm vào G có thể suy ra trường đoản cú F.

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

Vì thế, thuật toán sau đây sẽ đánh giá sự tương đương của nhị tập nhờ vào hàm:

F che E: X Y ∈ E, tí;nh X+ từ F, tiếp nối kiểm tra coi Y∈ X+ E lấp F: X Y ∈ F, tí;nh X+ trường đoản cú E, kế tiếp kiểm tra xem Y∈X+

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

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

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

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

1. Đặt G:﹦F. 2. Thay thế sửa chữa 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. Cùng với mỗi phụ thuộc vào hàm X → A trong G, với từng thuộc tí;nh B trong X giả dụ ((G-X → A) ∪ ( X -B) →A ) là tương đương với G, thì thay thế sửa chữa X→ A bởi (X - B) → A vào G. (Loại vứt thuộc tí;nh dư vượt trong nhờ vào hàm) 4. Với mỗi phụ thuộc vào hàm X → A trong G, nếu (G-X → A) tương tự với G, thì loại bỏ phụ ở trong 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ệ nam nữ ở dạng chuẩn 1 nếu các giá trị của toàn bộ thuộc tí;nh trong quan hệ là nguyên tử (tức là chỉ có 1 giá trị tại 1 thời điểm).