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

     
Một số hướng dẫn khi xây cất cơ sở dữ liệu quan hệ

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

Để đọc hơn về câu hỏi tại sao phải xây cất một cơ sở tài liệu tốt, họ hãy cùng mày mò ví; dụ sau

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

Quan hệ RESULT( kết quả học tập) có những 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ị chức năng học trình) với Mark (điểm thi của sv trong môn học).Bạn đã xem: nhờ vào hàm là gì

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


*

Minh họa dữ liệu của tình dục RESULT

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

Dư thừa tài liệu (Redundancy): thông tin về sinh viên với môn học tập bị lặp lại nhiều lần. Nếu như 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ị tái diễn 10 lần, tương tự so với môn học bao gồm mã Sub04, nếu bao gồm 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 đồng bộ (Inconsistency):Là hệ quả của dư thừa dữ liệu. Mang sử sửa phiên bản ghi lắp thêm nhất, tên sv được trị thành Nga thì dữ liệu đó lại không đồng hóa với bản ghi thứ 2 và 3 (vẫn có tên là Mai). Dị thường xuyên khi thêm bộ (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 quan hệ giới tính thì không được do khoá chí;nh của tình dục trên bao gồm 2 nằm trong tí;nh StNo và SubNo. Dị thường xuyên khi xoá bộ (Deletion anomalies): giả sử xoá đi phiên bản ghi cuối cùng, thì tin tức 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 bọn họ nên tra cứu cách tách quan hệ trên thành những quan hệ nhỏ dại hơn.Bạn vẫn xem: phụ thuộc hàm tương đối đầy đủ là gì

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

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

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

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

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

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

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

(Có nghĩa là: ví như hai bộ gồm cùng trị X thì gồm cùng trị Y)

Phụ nằm trong hàm được suy ra từ hầu như quy tắc tài liệu khi ta điều tra yêu mong của bài bác toán.

Từ mã số bảo hiểm xã hội, ta rất có thể suy ra được tên của nhân viên (Ssn→ Ename)Từ mã dự án, ta rất 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 đồ vật quan hệ EMP_DEPT cùng EMP_PROJ

Hệ tiên đề Armstrong

Cho lược thứ quan hệ r(U), U là tập thuộc tí;nh, F là tập các nhờ vào hàm được quan niệm trên quan hệ nam nữ r.

Ta có phụ thuộc hàm A → B được suy diễn lô ghích từ F nếu quan hệ tình dục r trênU thỏa các nhờ 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 hàm: F = A → B, B → C

Ta có nhờ vào hàm A → C là dựa vào hàm được suy từ bỏ F.

Hệ tiên đề Armstrong được áp dụng để tìm thấy các nhờ vào hàm suy diễn từ bỏ F.

Hệ định đề 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 cùng Y → Z thì X → Z

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

5. Luật hợp: nếu như 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 qui định trên thì a4, a5, a6 suy được từ a1, a2, a3.

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

Ta hotline f là một phụ thuộc vào hàm được suy dẫn tự F, cam kết hiệu là F ├ f ví như tồn trên một chuỗi phụ thuộc vào hàm: f1, f2,…., fn thế nào cho fn=f cùng mỗi fi là một trong những thành viên của F tốt được suy dẫn từ những dựa vào hàm j=1,…,i-1 trước đó phụ thuộc vào luật dẫn. Bao đóng góp 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 dựa vào hệ tiên đề Armstrong. F+ được định nghĩa:

F + = F X →Y

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

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

X + = F X →Y

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

X+ := X;repeat oldX+ := X+; for (mỗi nhờ vào hàm Y →Z vào F) bởi vì if Y ⊆ X+ then X+ ∪Zuntil (oldX+ = X+ ); đến tập dựa 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 tình dục r(R), tập K R được gọi là khóa của quan hệ nam nữ r nếu: K+=R và nếu bớt 1 phần tử ngoài K thì bao đóng của nó sẽ khác R.

Xem thêm: Chia Sẻ Caav Là Gì ? Viết Tắt Của Từ Gì? Cục Hàng Không Việt Nam Có Mẫu Biểu Trưng Mới

Như cầm tập K R là khoá của quan hệ giới tính nếu K+=R với ( K A )+ ≠R , A R.

ChoR = A, B, C, D, E, G và 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 nằm trong 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 lại hệ.

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

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

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

Thuật toán

Input: Lược đồ gia dụng 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 cần tìm những khóa, ta thay đổi trật tự sa thải các phần tử của K. Chúng ta 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 cách 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 dựa vào hàm)

Cho lược vật dụng quan hệ R = A,B,C,D,E,G,H,I và tập nhờ 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 thuộc 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

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

Nếu ao ước tìm toàn bộ các khoá của R, ta cần thay đổi trật tự nhiều loại bỏ phần tử của khoá K.

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

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

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

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

Nếu F cùng G là tương đương thì ta nói F lấp G tốt G bao phủ F.

Xem thêm: Tìm Hiểu Chicken Stock Là Gì, Từ Điển Anh Việt Chicken Stock

Vì thế, thuật toán dưới đây sẽ khám nghiệm sự tương đương của hai tập dựa vào hàm:

F phủ E: X Y ∈ E, tí;nh X+ từ bỏ F, tiếp đến kiểm tra coi Y∈ X+ E lấp F: X Y ∈ F, tí;nh X+ trường đoản cú E, tiếp đến kiểm tra coi 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 như nó thoả mãn những điều khiếu nại sau:

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

Nhận xét:

tất cả các tập nhờ vào hàm đều sở hữu phụ thuộc hàm về tối thiểu tương tự với nó. Gồm thể có tương đối nhiều phụ trực thuộc hàm về tối thiểu

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

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

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

Định nghĩa

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