R3
2.4. Phụ thuộc hàm
Như bạn đã biết, một trong những nguyên tắc chính của khái niệm cơ sở dữ liệu là để phấn đấu cho một nhân bản tối thiểu của dữ liệu. Để đạt được mục tiêu này có thể là lợi ích lớn cho bất kỳ thông tin về tất cả các loại hạn chế đối với các tập dữ liệu. Một cách chính thức hóa các thông tin này là xác định mối quan hệ giữa các dữ liệu. Sử dụng thành thạo thiết kế phụ thuộc cho phép cơ sở dữ liệu, tức là nhận mạch với các thuộc tính cần thiết.
Trong phần này chúng ta chỉ xem xét một trong những loại có thể phụ thuộc giữa các dữ liệu - phụ thuộc chức năng, mà thường được gọi là F-phụ thuộc (từ chức năng tiếng Anh). Phụ thuộc khác, chúng tôi sẽ xem xét sau.
. Nói một cách lỏng lẻo, F-phụ thuộc xảy ra khi giá trị của tuple thuộc tính trong một bộ được xác định duy nhất bởi các giá trị thiết lập các thuộc tính khác.
Bây giờ chúng tôi cung cấp cho một định nghĩa nghiêm ngặt, sử dụng toán tử quan hệ. Cho r - tỷ lệ của chương trình R và X và Y - một tập hợp con của R. Tỷ lệ r thỏa mãn sự phụ thuộc chức năng X Y, nếu Y ( X = x (r)) không có nhiều hơn một tuple cho mỗi X-giá trị x. Một cách để giải thích định nghĩa này - xem hai bộ t1 và t2 liên quan đến r. Nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y). Trong F-phụ thuộc của X Y tập hợp con của các thuộc tính X được gọi là phần bên trái, và các tập con Y - bên phải.
Một giải thích của sự phụ thuộc chức năng như nền tảng đáp ứng thuật toán, kiểm tra xem các đáp ứng tỷ lệ r F-tùy thuộc X Y.
Thuật toán 2.1. Đáp ứng.
Đăng nhập: r tỷ lệ và F-phụ thuộc của X Y.
Đầu ra: đúng nếu đáp ứng r X Y, sai - nếu không.
Đáp ứng (r, X Y).
1. Mối quan hệ Peresortiruem r trên X-cột để thu thập các dữ liệu với bằng X-giá trị với nhau.
. 2 Nếu mỗi bộ dữ liệu với bằng X-giá trị cũng bằng với Y-giá trị, sản lượng chúng tôi nhận được sự thật, nếu không - sai.
2.4.1. Tiên đề O
Đối với mỗi quan hệ r (R) bất cứ lúc nào có một gia đình của chức năng phụ thuộc F giữa các thuộc tính của tỷ lệ này, đó là đáp ứng tỷ lệ. Trong F gia đình này luôn luôn là hữu hạn, vì chỉ có một số hữu hạn các tập con của R. Do đó chương trình này, bạn luôn có thể tìm thấy tất cả các F-phụ thuộc, có đủ r, một điều tra đơn giản của tất cả các tập con có thể sử dụng các thuật toán đáp ứng. Tuy nhiên, phương pháp này đòi hỏi một lượng lớn thời gian.
Nếu bạn biết một số F-phụ thuộc của F, chúng ta có thể lấy được từ họ với phần còn lại phụ thuộc chức năng, và vốn có để xem xét mối quan hệ với một bộ quy tắc hợp lý, được gọi là tiên đề đầu ra. Tiên đề đầu ra - quy tắc này quy định rằng nếu mối quan hệ nhất định đáp ứng F-phụ thuộc, thì nó cũng phải đáp ứng một số khác F-phụ thuộc.
Chúng tôi xây dựng sáu tiên đề O F-phụ thuộc. Trong việc xây dựng, chúng tôi sử dụng các ký hiệu r cho tỉ R trên các thuộc tính và các chữ cái W, X, Y, Z cho các tập con của R.
F1. Phản xạ. Từ định nghĩa của F-phụ thuộc trực tiếp sau đó tỷ lệ X (X = x (r)) luôn luôn có ít nhất một tuple, phụ thuộc vì vậy bất kỳ mối quan hệ thỏa mãn tầm thường X X.
Tầm thường sẽ gọi như F-tùy thuộc X Y, trong đó X Y, tức là thuộc tính trong phần bên phải của biểu hiện của các thuộc tính chứa bên hoàn toàn trái của biểu thức. Nếu X Y là phụ thuộc F-tầm thường trên R, sau đó bất kỳ mối quan hệ r (R) đáp ứng X Y.
F2. Nạp tiền. Để đáp ứng r X Y, tức là Y ( X = x (r)) có ít nhất một tuple cho bất kỳ X-giá trị x. Nếu Z là bất kỳ tập hợp con của R, sau đó XZ = xz (r) X = x (r) và do đó
Y ( XZ = xz (r)) Y ( X = x (r)).
Do đó, Y ( XZ = xz (r)) là nhiều nhất một bộ và r phải đáp ứng các XZ F-tùy Y.
Tiên đề này cho phép mở rộng phía bên trái của F-phụ thuộc.
Ví dụ 2.17. Trình bày dưới đây các đáp ứng tỷ lệ phụ thuộc F-A B,
r (ABCD), và do đó của Tiên đề F2, các mối quan hệ:
a1 b1 c1 d1 AB B, AC B, AD B;
a2 b2 c1 d1 ABC B, ABD B, ACD B;
a1 b1 c1 d2 ABCD B.
a3 b3 c2 d3
F3. Additivity. Nếu đáp ứng tỷ lệ r X Y và X Z, sau đó cả hai dự Y ( X = x (r)) và Z ( X = x (r)) không có nhiều hơn một tuple cho bất kỳ X-giá trị x. Nếu tỷ lệ YZ ( X = x (r)) có nhiều hơn một tuple, thì ít nhất một trong những tỷ lệ Y ( X = x (r)) hoặc Z ( X = x (r)) được có nhiều hơn một tuple. Như vậy, đáp ứng r phụ thuộc F-X YZ.
Tiên đề này cho phép bạn kết hợp phụ thuộc với các bên tay trái cùng nhau.
Ví dụ 2.18. Tỷ lệ trình bày trong Ví dụ 2.17 Một đáp ứng B và A C. tiên đề F3 tỷ lệ r cũng phải đáp ứng một BC.
F4. Xạ ảnh. Nếu đáp ứng tỷ lệ r X YZ, sau đó YZ ( X = x (r)) là, theo định nghĩa, không nhiều hơn một tuple cho bất kỳ X-giá trị x. Từ Y ( YZ ( X = x (r))) = Y ( X = x (r)), và sau đó Y ( X = x (r)) cũng có thể không nhiều hơn một tuple . Do đó, r thỏa mãn X Y.
Tiên đề này là tiền đề của phụ nghịch đảo, theo nghĩa là nó cho phép sự phân hủy của F-phụ thuộc.
Ví dụ 2.19. Ví dụ tỷ lệ 2,17 đáp ứng Một busing. Theo tiên đề F4, tỷ lệ r cũng phải đáp ứng một B và A C.
F5. Bắc. Cho r thỏa mãn F-phụ thuộc X Y và Y Z. Hãy xem xét bộ dữ liệu t1 và t2 trong r. Nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y), và từ t1 (Y) = t2 (Y) mà t1 (Z) = t2 (Z). Vì vậy, nếu t1 (X) = t2 (X), sau đó t1 (Z) = t2 (Z), nghĩa là chống lại r cũng nắm giữ một chức năng phụ thuộc X Z.
Ví dụ 2.20. Trình bày dưới đây tỷ lệ r đáp ứng các mối quan hệ A B và B C.
r (ABCD) Như sau nguồn từ tiền đề F5, tỷ lệ r cũng thỏa mãn Một C.
Này và các tiên đề sau đây là mạnh nhất trong số các tiên đề nguồn gốc.
a1 b1 c2 d1
a2 b2 c1 d2
a3 b1 c2 d1
a4 b1 c2 d3
F6. Psevdotranzitivnost. Để đáp ứng r F-phụ thuộc X Y và YZ W, và t1 và t2 là bộ dữ liệu trong r. Bởi giả thuyết, nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y), và tương tự, nếu t1 (YZ) = t2 (YZ), sau đó t1 (W) = t2 (W). Từ t1 (XZ) = t2 (XZ) cũng có mà t1 (X) = t2 (X), có nghĩa là trên t1 trước (Y) = t2 (Y) và ngoài ra, t1 (YZ) = t2 (YZ ), có nghĩa là t1 (W) = t2 (W). Do đó, r thỏa mãn XZ W.
Vì vậy, nếu W, X, Y, Z là các tập con của R, sau đó cho bất kỳ mối quan hệ r với chương trình R thỏa mãn các tiên đề sau đây O:
F1. Phản xạ: X X.
F2. Nạp tiền: X Y Y. đòi hỏi XZ
F3. Additivity: X Y và X Z đòi hỏi X YZ.
F4. Xạ ảnh: X YZ đáp ứng: X Y.
F5. Bắc: X Y và Y Z đòi hỏi X Z.
F6. Psevdotranzitivnost: X Y và YZ W đòi hỏi XZ W.
Một tập hợp con của ba tiên đề đầu ra F1, F2 và F6 hoàn tất. Điều này có nghĩa rằng nếu một tiên đề cho F1, F2 và F6, nó có thể lấy được từ họ với phần còn lại. Ví dụ, bắc là một trường hợp đặc biệt F5 F6 psevdotranzitivnosti tại Z = 0. Nếu có X Y và X Z, sau đó sử dụng F1, được YZ YZ và hai lần sử dụng F6, có được đầu tiên XZ YZ, sau đó X YZ. Vì vậy F3 sau từ F1 và F6. Để chứng minh F4, giả định rằng X YZ. F1 có Y Y, và từ F2 được YZ Y. Ứng dụng F6 cho X Y.
Tiên đề F1, F2 và F6 cũng là độc lập: không có những tiên đề không thể được lấy từ hai người kia. Ba tiên đề được gọi là tiên đề Armstrong.
Cho F - F-bộ phụ thuộc cho quan hệ r (R). Đóng cửa của F, ký hiệu là F +, - là nhỏ nhất có chứa F thiết lập như vậy mà khi áp dụng cho ông tiên đề Armstrong không thể nhận được bất kỳ F-phụ thuộc, không thuộc F. Nói cách khác, F + - là tập hợp đầy đủ tối thiểu phụ thuộc chức năng là hợp lý có thể để có được F. Vì F + phải là hữu hạn, sau đó nó có thể được tính bắt đầu từ F bằng cách áp dụng F1, F2 và F6 và thêm vào thu được F-phụ thuộc vào F miễn là không còn nhận được phụ thuộc mới. F mạch đầu ra phụ thuộc vào R. mạch
Trong tương lai chúng tôi sẽ xem xét nhiều cách nhỏ gọn của đại diện F +, nhưng nhìn vào hai định nghĩa liên quan đến việc đóng cửa của F.
Nếu G là tập hợp của tất cả các thể F-phụ thuộc của R, và F là một tập hợp con của F-phụ thuộc vào R, chúng ta có thể viết: F-= G - F +. F-bộ được gọi là bên ngoài của tập F.
Nếu F là tập hợp F-phụ thuộc của R và X là một tập hợp con của R, tồn tại F-phụ thuộc X Y trong F +, như vậy là một tập hợp con của Y càng nhiều càng tốt theo ý nghĩa là Y Z cho bất kỳ X F-tùy Z trong F +. Kết quả này xuất phát từ tiền đề của additivity. Bộ Y được gọi là đóng cửa của X và ký hiệu là X +. Theo phản xạ, việc đóng cửa của X luôn chứa X.
Ví dụ 2.22. Cho F = {A D, AB DE, CE G, E H}. Sau đó (AB) + = ABDEH.
2.4.2. Đầu ra chuỗi
Tính thống nhất của các tiên đề và kết quả F-phụ thuộc được gọi là thiết bị đầu cuối X Y của F. Để mô tả sản lượng chúng ta cần một số định nghĩa mới.
Chuỗi P F-phụ thuộc về một chương trình R được gọi là một đầu ra thứ tự trên tập F, nếu mỗi F-phụ thuộc vào P hoặc là thành viên của F, hoặc thuộc về nên F F-phụ thuộc sau khi áp dụng chúng tiên đề nguồn gốc. P còn được gọi là một chuỗi các O X Y, nếu X Y là một trong những F-phụ thuộc P. sử dụng đã được thiết lập trong P là tập hợp của tất cả các F-phụ thuộc thuộc P.
Ví dụ 2.23. Cho F = {AB E, AG J, BE I, E G, GI H}. Trình tự sau đây là một chuỗi các O AB GH.
1. AB E (cho)
2. AB AB (phản xạ)
3. AB B (xạ ảnh của 2)
4. AB BE (additivity của 1 và 3)
5. BE I (cho)
6. AB I (tranzitivn. 4,5)
7. E G (cho)
8. AB G (tranzitivn. 1 và 7)
9. AB GI (additivity của 6and 8)
10. GI H (cho)
11. AB H (tranzitivn. của 9 và 10)
12. GI GI (phản xạ)
13. GI I (xạ ảnh của 12)
14. AB GH (additivity của 8.11)
Trình tự này chứa không mong muốn (không cần thiết) F-phụ thuộc như 12 và 13 và trình tự cũng là đầu ra cho khác F-phụ thuộc, ví dụ AB GI.
Trước đây người ta thấy rằng một tập hợp con của các tiên đề O F1, F2 và F6 hoàn tất. Ngoài ra còn có một bộ hoàn chỉnh hơn của tiên đề O, mà là một tập hợp con của F1-F6. Các tiên đề được gọi là B-tiên đề.
Đối với tỷ lệ r (R), tập hợp con của W, X, Y, Z và giản đồ R thuộc tính C, ta có:
B1. Phản xạ: X X.
B2. Tích lũy: X YZ và Z CW nghĩa X YZC.
B3. Xạ ảnh: X YZ nghĩa X Y.
Chúng tôi thấy rằng Armstrong tiên đề xuất phát từ B-tiên đề. Hậu quả của việc này là sự viên mãn của B-tiên đề.
F1. Phản xạ: trùng c B1.
F2. Ngoài ra: Nếu X Y, sau đó bằng B1 có XZ XZ, nhờ B2 có được XZ XYZ, và cuối cùng, việc sử dụng B3 cho XZ Y.
F6. Psevdotranzitivnost Hãy để thỏa mãn r X Y và YZ W. B1 được XZ XZ. Áp dụng thống nhất cho B2 XZ XYZ và XZ WXYZ. Một ứng dụng cung cấp cho B3 XZ W.
Kể từ khi B-hệ thống tiên đề hoàn tất, bạn luôn luôn có thể tìm thấy một chuỗi các đầu ra, chỉ sử dụng B-tiên đề.
Tiếp theo chúng ta xem xét trình tự O X Y tập các phụ thuộc F-F sử dụng B-tiên đề, đáp ứng các điều kiện sau đây:
1.Pervy F-phụ thuộc - là X X.
2.Poslednyaya F-phụ thuộc - là X Y.
3.Kazhdaya F-phụ thuộc, mà khác với lần đầu tiên hoặc cuối cùng, hoặc thuộc về F, hoặc có dạng X Z và thu được từ các tiên đề B2.
Một chuỗi như vậy sản lượng đầu ra được gọi là RAP-tự (chữ cái đầu tiên của tên của B-tiên đề: phản xạ, tích lũy, xạ ảnh).
Ví dụ 2.25. Cho F - chẳng hạn như một đa số của F-phụ thuộc như trong ví dụ 2.23. Sau đó, chúng tôi có trình tự sau đây của RAP-O từ F đến AB GH:
1. AB AB (B1)
2. AB E (cho)
3. AB ABE (B2)
4. BE I (cho)
5. AB ABEI (B2)
6. E G (cho)
7. AB ABEGI (B2)
8. GI H (cho)
9. AB ABEGHI (B2)
10. AB GH (B3).
Như vậy, sự phụ thuộc của X Y có thể được bắt nguồn chỉ sử dụng B2 tiên đề (ngoại trừ phụ thuộc đầu tiên và cuối cùng trong P), và kết quả duy nhất của việc sử dụng B2 tiên đề có thể có được F-phụ thuộc với phía bên phải lớn hơn so với bản gốc F-phụ thuộc và thay thế F-phụ thuộc với bên tay phải lớn được thực hiện thông qua toàn bộ sản lượng trình tự.
2.4.3. Đạo mạch hở đồ thị đầu ra
Đạo diễn đồ thị mạch hở (DA-Count) - là một đồ thị có hướng mà không có chu kỳ trong bất kỳ đầu. DA-dán nhãn đồ thị - đây DA-đồ thị, mỗi đỉnh trong số đó là ánh xạ tới một phần tử của tập hợp các nhãn L.
Cho F - phụ thuộc F-bộ trên lược đồ R. DA-đồ thị hiển thị của F - là một đồ thị acyclic đạo diễn đánh dấu với các thuộc tính của R và xây dựng theo các quy tắc sau:
R1. Bất kỳ tập các đỉnh cô lập với các nhãn của DA-R là một đồ thị của sản lượng trên F.
R2. Giả sử H là một màn hình DA-đồ thị của F, có chứa đỉnh 1, 2, , k có nhãn A1, A2, , Ak, và A1, A2, , Ak CZ là một F-phụ thuộc trong F. Chúng tôi xây dựng H ', thêm vào đầu của H u, có nhãn C, và vòng cung ( 1, u), (2 , u), , ( k, u). H 'là màn hình hiển thị DA-đồ thị trên F.
R3. Không có đồ thị khác không phải là DA-đồ thị hiển thị trên F.
Sau đó hiển thị DA-đồ thị trên F sẽ được gọi là DDA-đồ thị trên F. Bất kỳ DDA-đồ thị của F được xây dựng bằng cách sử dụng một ứng dụng duy nhất các quy tắc R1 và một số ứng dụng nhất định trong các quy định R2.
Nếu H là một đồ thị của DDA-, sau đó các hàng đầu trong H được gọi là đỉnh đầu nếu không có vòng cung đến trong đó. Bất kỳ đỉnh ban đầu được thêm vào H bởi các quy tắc R1.
Giả sử H là một DDA-đồ thị H trên F. Graf gọi là DDA-đồ thị cho X Y, trong đó:
D1. X là tập hợp của các nhãn của các đỉnh ban đầu.
D2. Mỗi thuộc tính trong Y là nhãn của bất kỳ đỉnh trong H.
Sử dụng nhiều DDA-đồ thị H hơn F (ký hiệu là U (H)) là tập hợp của tất cả các F-phụ thuộc trong F, được sử dụng trong việc áp dụng các quy tắc R2 trong khi xây dựng DDA-đồ thị.
Dán nhãn hướng đồ thị mạch hở một cách hình học của mô tả trình tự của RAP-O, tức là nếu chúng ta đưa ra một chuỗi các RAP-O X Y, sau đó chúng ta có thể xây dựng một đồ thị của DDA-F cho X Y và ngược lại.
Nói cách khác, có một sự tương ứng tự nhiên giữa B-tiên đề, các quy tắc xây dựng DDA-đồ thị trên F và xác định các điều khoản của DDA-đồ thị F cho X Y. Tiên đề B1 tương ứng với quy tắc R1 xây dựng DDA-đồ thị. Tiên đề B2 tương ứng với quy tắc R2. Tiên đề B3 có trong định nghĩa của điều kiện D2 DDA-đồ thị cho X Y.
Tiên đề B2 và R2 thường có thể được tăng cường bằng phương pháp tương tự. Phiên bản nâng cao của B2 có thể được diễn tả như sau:
B2. X YZ và Z VW nên X VYZ,
trong đó V cũng là một tập hợp con của tập R.
2.4.4. Kiểm tra thuộc F +
Để xác định xem các thiết lập F ngụ ý sự phụ thuộc X Y, nó cũng đủ để kiểm tra xem một X Y F +. Tuy nhiên, F + có thể lớn hơn nhiều so với F (xem Ví dụ 2.21), vì vậy nó là tốt hơn để sử dụng một phương pháp khác kiểm tra xem X Y F +, mà không yêu cầu việc xây dựng tất cả phụ thuộc của F. Phương pháp này dựa trên việc xây dựng các mạch X trên F. Sau khi như tìm thấy X +, bạn có thể kiểm tra xem sự phụ thuộc của X Y F.
Thuật toán 2.2. ĐÓNG CỬA.
Đầu vào: một tập hợp các thuộc tính X và tập F-phụ thuộc F.
Năng suất: việc đóng cửa của X trên F.
CHỨC NĂNG ĐÓNG CỬA
THÔNG SỐ X, F
olddep = 0
newdep = X
DO KHI newdep # olddep
olddep = newdep
CHO mỗi F-phụ thuộc của W Z trong F
NẾU newdep W
newdep = newdep Z
ENDIF
ENDFOR
ENDDO
RETURN newdep
Thuật toán này xây dựng một đồ thị của DDA-F cho X X +, sử dụng một phiên bản nâng cao của các quy tắc trong việc xác định R2 DDA-đồ thị, khi được bổ sung trong một lần chạy nhiều hơn một đỉnh.
Sử dụng các thuật toán rất dễ dàng để xây dựng một thuật toán ĐÓNG CỬA thành viên, kiểm tra xem sự phụ thuộc của X Y F.
Thuật toán 2.3. Thành viên.
Đầu vào: tập các phụ thuộc F-F và F-phụ thuộc của X Y.
Đầu ra: đúng nếu F sau từ X Y, sai khác.
CHỨC NĂNG THÀNH VIÊN
THÔNG SỐ F, X Y
NẾU Y ĐÓNG CỬA (X, F)
RETURN. T.
Khác
RETURN. F.
ENDIF
Như bạn đã biết, một trong những nguyên tắc chính của khái niệm cơ sở dữ liệu là để phấn đấu cho một nhân bản tối thiểu của dữ liệu. Để đạt được mục tiêu này có thể là lợi ích lớn cho bất kỳ thông tin về tất cả các loại hạn chế đối với các tập dữ liệu. Một cách chính thức hóa các thông tin này là xác định mối quan hệ giữa các dữ liệu. Sử dụng thành thạo thiết kế phụ thuộc cho phép cơ sở dữ liệu, tức là nhận mạch với các thuộc tính cần thiết.
Trong phần này chúng ta chỉ xem xét một trong những loại có thể phụ thuộc giữa các dữ liệu - phụ thuộc chức năng, mà thường được gọi là F-phụ thuộc (từ chức năng tiếng Anh). Phụ thuộc khác, chúng tôi sẽ xem xét sau.
. Nói một cách lỏng lẻo, F-phụ thuộc xảy ra khi giá trị của tuple thuộc tính trong một bộ được xác định duy nhất bởi các giá trị thiết lập các thuộc tính khác.
Bây giờ chúng tôi cung cấp cho một định nghĩa nghiêm ngặt, sử dụng toán tử quan hệ. Cho r - tỷ lệ của chương trình R và X và Y - một tập hợp con của R. Tỷ lệ r thỏa mãn sự phụ thuộc chức năng X Y, nếu Y ( X = x (r)) không có nhiều hơn một tuple cho mỗi X-giá trị x. Một cách để giải thích định nghĩa này - xem hai bộ t1 và t2 liên quan đến r. Nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y). Trong F-phụ thuộc của X Y tập hợp con của các thuộc tính X được gọi là phần bên trái, và các tập con Y - bên phải.
Một giải thích của sự phụ thuộc chức năng như nền tảng đáp ứng thuật toán, kiểm tra xem các đáp ứng tỷ lệ r F-tùy thuộc X Y.
Thuật toán 2.1. Đáp ứng.
Đăng nhập: r tỷ lệ và F-phụ thuộc của X Y.
Đầu ra: đúng nếu đáp ứng r X Y, sai - nếu không.
Đáp ứng (r, X Y).
1. Mối quan hệ Peresortiruem r trên X-cột để thu thập các dữ liệu với bằng X-giá trị với nhau.
. 2 Nếu mỗi bộ dữ liệu với bằng X-giá trị cũng bằng với Y-giá trị, sản lượng chúng tôi nhận được sự thật, nếu không - sai.
2.4.1. Tiên đề O
Đối với mỗi quan hệ r (R) bất cứ lúc nào có một gia đình của chức năng phụ thuộc F giữa các thuộc tính của tỷ lệ này, đó là đáp ứng tỷ lệ. Trong F gia đình này luôn luôn là hữu hạn, vì chỉ có một số hữu hạn các tập con của R. Do đó chương trình này, bạn luôn có thể tìm thấy tất cả các F-phụ thuộc, có đủ r, một điều tra đơn giản của tất cả các tập con có thể sử dụng các thuật toán đáp ứng. Tuy nhiên, phương pháp này đòi hỏi một lượng lớn thời gian.
Nếu bạn biết một số F-phụ thuộc của F, chúng ta có thể lấy được từ họ với phần còn lại phụ thuộc chức năng, và vốn có để xem xét mối quan hệ với một bộ quy tắc hợp lý, được gọi là tiên đề đầu ra. Tiên đề đầu ra - quy tắc này quy định rằng nếu mối quan hệ nhất định đáp ứng F-phụ thuộc, thì nó cũng phải đáp ứng một số khác F-phụ thuộc.
Chúng tôi xây dựng sáu tiên đề O F-phụ thuộc. Trong việc xây dựng, chúng tôi sử dụng các ký hiệu r cho tỉ R trên các thuộc tính và các chữ cái W, X, Y, Z cho các tập con của R.
F1. Phản xạ. Từ định nghĩa của F-phụ thuộc trực tiếp sau đó tỷ lệ X (X = x (r)) luôn luôn có ít nhất một tuple, phụ thuộc vì vậy bất kỳ mối quan hệ thỏa mãn tầm thường X X.
Tầm thường sẽ gọi như F-tùy thuộc X Y, trong đó X Y, tức là thuộc tính trong phần bên phải của biểu hiện của các thuộc tính chứa bên hoàn toàn trái của biểu thức. Nếu X Y là phụ thuộc F-tầm thường trên R, sau đó bất kỳ mối quan hệ r (R) đáp ứng X Y.
F2. Nạp tiền. Để đáp ứng r X Y, tức là Y ( X = x (r)) có ít nhất một tuple cho bất kỳ X-giá trị x. Nếu Z là bất kỳ tập hợp con của R, sau đó XZ = xz (r) X = x (r) và do đó
Y ( XZ = xz (r)) Y ( X = x (r)).
Do đó, Y ( XZ = xz (r)) là nhiều nhất một bộ và r phải đáp ứng các XZ F-tùy Y.
Tiên đề này cho phép mở rộng phía bên trái của F-phụ thuộc.
Ví dụ 2.17. Trình bày dưới đây các đáp ứng tỷ lệ phụ thuộc F-A B,
r (ABCD), và do đó của Tiên đề F2, các mối quan hệ:
a1 b1 c1 d1 AB B, AC B, AD B;
a2 b2 c1 d1 ABC B, ABD B, ACD B;
a1 b1 c1 d2 ABCD B.
a3 b3 c2 d3
F3. Additivity. Nếu đáp ứng tỷ lệ r X Y và X Z, sau đó cả hai dự Y ( X = x (r)) và Z ( X = x (r)) không có nhiều hơn một tuple cho bất kỳ X-giá trị x. Nếu tỷ lệ YZ ( X = x (r)) có nhiều hơn một tuple, thì ít nhất một trong những tỷ lệ Y ( X = x (r)) hoặc Z ( X = x (r)) được có nhiều hơn một tuple. Như vậy, đáp ứng r phụ thuộc F-X YZ.
Tiên đề này cho phép bạn kết hợp phụ thuộc với các bên tay trái cùng nhau.
Ví dụ 2.18. Tỷ lệ trình bày trong Ví dụ 2.17 Một đáp ứng B và A C. tiên đề F3 tỷ lệ r cũng phải đáp ứng một BC.
F4. Xạ ảnh. Nếu đáp ứng tỷ lệ r X YZ, sau đó YZ ( X = x (r)) là, theo định nghĩa, không nhiều hơn một tuple cho bất kỳ X-giá trị x. Từ Y ( YZ ( X = x (r))) = Y ( X = x (r)), và sau đó Y ( X = x (r)) cũng có thể không nhiều hơn một tuple . Do đó, r thỏa mãn X Y.
Tiên đề này là tiền đề của phụ nghịch đảo, theo nghĩa là nó cho phép sự phân hủy của F-phụ thuộc.
Ví dụ 2.19. Ví dụ tỷ lệ 2,17 đáp ứng Một busing. Theo tiên đề F4, tỷ lệ r cũng phải đáp ứng một B và A C.
F5. Bắc. Cho r thỏa mãn F-phụ thuộc X Y và Y Z. Hãy xem xét bộ dữ liệu t1 và t2 trong r. Nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y), và từ t1 (Y) = t2 (Y) mà t1 (Z) = t2 (Z). Vì vậy, nếu t1 (X) = t2 (X), sau đó t1 (Z) = t2 (Z), nghĩa là chống lại r cũng nắm giữ một chức năng phụ thuộc X Z.
Ví dụ 2.20. Trình bày dưới đây tỷ lệ r đáp ứng các mối quan hệ A B và B C.
r (ABCD) Như sau nguồn từ tiền đề F5, tỷ lệ r cũng thỏa mãn Một C.
Này và các tiên đề sau đây là mạnh nhất trong số các tiên đề nguồn gốc.
a1 b1 c2 d1
a2 b2 c1 d2
a3 b1 c2 d1
a4 b1 c2 d3
F6. Psevdotranzitivnost. Để đáp ứng r F-phụ thuộc X Y và YZ W, và t1 và t2 là bộ dữ liệu trong r. Bởi giả thuyết, nếu t1 (X) = t2 (X), sau đó t1 (Y) = t2 (Y), và tương tự, nếu t1 (YZ) = t2 (YZ), sau đó t1 (W) = t2 (W). Từ t1 (XZ) = t2 (XZ) cũng có mà t1 (X) = t2 (X), có nghĩa là trên t1 trước (Y) = t2 (Y) và ngoài ra, t1 (YZ) = t2 (YZ ), có nghĩa là t1 (W) = t2 (W). Do đó, r thỏa mãn XZ W.
Vì vậy, nếu W, X, Y, Z là các tập con của R, sau đó cho bất kỳ mối quan hệ r với chương trình R thỏa mãn các tiên đề sau đây O:
F1. Phản xạ: X X.
F2. Nạp tiền: X Y Y. đòi hỏi XZ
F3. Additivity: X Y và X Z đòi hỏi X YZ.
F4. Xạ ảnh: X YZ đáp ứng: X Y.
F5. Bắc: X Y và Y Z đòi hỏi X Z.
F6. Psevdotranzitivnost: X Y và YZ W đòi hỏi XZ W.
Một tập hợp con của ba tiên đề đầu ra F1, F2 và F6 hoàn tất. Điều này có nghĩa rằng nếu một tiên đề cho F1, F2 và F6, nó có thể lấy được từ họ với phần còn lại. Ví dụ, bắc là một trường hợp đặc biệt F5 F6 psevdotranzitivnosti tại Z = 0. Nếu có X Y và X Z, sau đó sử dụng F1, được YZ YZ và hai lần sử dụng F6, có được đầu tiên XZ YZ, sau đó X YZ. Vì vậy F3 sau từ F1 và F6. Để chứng minh F4, giả định rằng X YZ. F1 có Y Y, và từ F2 được YZ Y. Ứng dụng F6 cho X Y.
Tiên đề F1, F2 và F6 cũng là độc lập: không có những tiên đề không thể được lấy từ hai người kia. Ba tiên đề được gọi là tiên đề Armstrong.
Cho F - F-bộ phụ thuộc cho quan hệ r (R). Đóng cửa của F, ký hiệu là F +, - là nhỏ nhất có chứa F thiết lập như vậy mà khi áp dụng cho ông tiên đề Armstrong không thể nhận được bất kỳ F-phụ thuộc, không thuộc F. Nói cách khác, F + - là tập hợp đầy đủ tối thiểu phụ thuộc chức năng là hợp lý có thể để có được F. Vì F + phải là hữu hạn, sau đó nó có thể được tính bắt đầu từ F bằng cách áp dụng F1, F2 và F6 và thêm vào thu được F-phụ thuộc vào F miễn là không còn nhận được phụ thuộc mới. F mạch đầu ra phụ thuộc vào R. mạch
Trong tương lai chúng tôi sẽ xem xét nhiều cách nhỏ gọn của đại diện F +, nhưng nhìn vào hai định nghĩa liên quan đến việc đóng cửa của F.
Nếu G là tập hợp của tất cả các thể F-phụ thuộc của R, và F là một tập hợp con của F-phụ thuộc vào R, chúng ta có thể viết: F-= G - F +. F-bộ được gọi là bên ngoài của tập F.
Nếu F là tập hợp F-phụ thuộc của R và X là một tập hợp con của R, tồn tại F-phụ thuộc X Y trong F +, như vậy là một tập hợp con của Y càng nhiều càng tốt theo ý nghĩa là Y Z cho bất kỳ X F-tùy Z trong F +. Kết quả này xuất phát từ tiền đề của additivity. Bộ Y được gọi là đóng cửa của X và ký hiệu là X +. Theo phản xạ, việc đóng cửa của X luôn chứa X.
Ví dụ 2.22. Cho F = {A D, AB DE, CE G, E H}. Sau đó (AB) + = ABDEH.
2.4.2. Đầu ra chuỗi
Tính thống nhất của các tiên đề và kết quả F-phụ thuộc được gọi là thiết bị đầu cuối X Y của F. Để mô tả sản lượng chúng ta cần một số định nghĩa mới.
Chuỗi P F-phụ thuộc về một chương trình R được gọi là một đầu ra thứ tự trên tập F, nếu mỗi F-phụ thuộc vào P hoặc là thành viên của F, hoặc thuộc về nên F F-phụ thuộc sau khi áp dụng chúng tiên đề nguồn gốc. P còn được gọi là một chuỗi các O X Y, nếu X Y là một trong những F-phụ thuộc P. sử dụng đã được thiết lập trong P là tập hợp của tất cả các F-phụ thuộc thuộc P.
Ví dụ 2.23. Cho F = {AB E, AG J, BE I, E G, GI H}. Trình tự sau đây là một chuỗi các O AB GH.
1. AB E (cho)
2. AB AB (phản xạ)
3. AB B (xạ ảnh của 2)
4. AB BE (additivity của 1 và 3)
5. BE I (cho)
6. AB I (tranzitivn. 4,5)
7. E G (cho)
8. AB G (tranzitivn. 1 và 7)
9. AB GI (additivity của 6and 8)
10. GI H (cho)
11. AB H (tranzitivn. của 9 và 10)
12. GI GI (phản xạ)
13. GI I (xạ ảnh của 12)
14. AB GH (additivity của 8.11)
Trình tự này chứa không mong muốn (không cần thiết) F-phụ thuộc như 12 và 13 và trình tự cũng là đầu ra cho khác F-phụ thuộc, ví dụ AB GI.
Trước đây người ta thấy rằng một tập hợp con của các tiên đề O F1, F2 và F6 hoàn tất. Ngoài ra còn có một bộ hoàn chỉnh hơn của tiên đề O, mà là một tập hợp con của F1-F6. Các tiên đề được gọi là B-tiên đề.
Đối với tỷ lệ r (R), tập hợp con của W, X, Y, Z và giản đồ R thuộc tính C, ta có:
B1. Phản xạ: X X.
B2. Tích lũy: X YZ và Z CW nghĩa X YZC.
B3. Xạ ảnh: X YZ nghĩa X Y.
Chúng tôi thấy rằng Armstrong tiên đề xuất phát từ B-tiên đề. Hậu quả của việc này là sự viên mãn của B-tiên đề.
F1. Phản xạ: trùng c B1.
F2. Ngoài ra: Nếu X Y, sau đó bằng B1 có XZ XZ, nhờ B2 có được XZ XYZ, và cuối cùng, việc sử dụng B3 cho XZ Y.
F6. Psevdotranzitivnost Hãy để thỏa mãn r X Y và YZ W. B1 được XZ XZ. Áp dụng thống nhất cho B2 XZ XYZ và XZ WXYZ. Một ứng dụng cung cấp cho B3 XZ W.
Kể từ khi B-hệ thống tiên đề hoàn tất, bạn luôn luôn có thể tìm thấy một chuỗi các đầu ra, chỉ sử dụng B-tiên đề.
Tiếp theo chúng ta xem xét trình tự O X Y tập các phụ thuộc F-F sử dụng B-tiên đề, đáp ứng các điều kiện sau đây:
1.Pervy F-phụ thuộc - là X X.
2.Poslednyaya F-phụ thuộc - là X Y.
3.Kazhdaya F-phụ thuộc, mà khác với lần đầu tiên hoặc cuối cùng, hoặc thuộc về F, hoặc có dạng X Z và thu được từ các tiên đề B2.
Một chuỗi như vậy sản lượng đầu ra được gọi là RAP-tự (chữ cái đầu tiên của tên của B-tiên đề: phản xạ, tích lũy, xạ ảnh).
Ví dụ 2.25. Cho F - chẳng hạn như một đa số của F-phụ thuộc như trong ví dụ 2.23. Sau đó, chúng tôi có trình tự sau đây của RAP-O từ F đến AB GH:
1. AB AB (B1)
2. AB E (cho)
3. AB ABE (B2)
4. BE I (cho)
5. AB ABEI (B2)
6. E G (cho)
7. AB ABEGI (B2)
8. GI H (cho)
9. AB ABEGHI (B2)
10. AB GH (B3).
Như vậy, sự phụ thuộc của X Y có thể được bắt nguồn chỉ sử dụng B2 tiên đề (ngoại trừ phụ thuộc đầu tiên và cuối cùng trong P), và kết quả duy nhất của việc sử dụng B2 tiên đề có thể có được F-phụ thuộc với phía bên phải lớn hơn so với bản gốc F-phụ thuộc và thay thế F-phụ thuộc với bên tay phải lớn được thực hiện thông qua toàn bộ sản lượng trình tự.
2.4.3. Đạo mạch hở đồ thị đầu ra
Đạo diễn đồ thị mạch hở (DA-Count) - là một đồ thị có hướng mà không có chu kỳ trong bất kỳ đầu. DA-dán nhãn đồ thị - đây DA-đồ thị, mỗi đỉnh trong số đó là ánh xạ tới một phần tử của tập hợp các nhãn L.
Cho F - phụ thuộc F-bộ trên lược đồ R. DA-đồ thị hiển thị của F - là một đồ thị acyclic đạo diễn đánh dấu với các thuộc tính của R và xây dựng theo các quy tắc sau:
R1. Bất kỳ tập các đỉnh cô lập với các nhãn của DA-R là một đồ thị của sản lượng trên F.
R2. Giả sử H là một màn hình DA-đồ thị của F, có chứa đỉnh 1, 2, , k có nhãn A1, A2, , Ak, và A1, A2, , Ak CZ là một F-phụ thuộc trong F. Chúng tôi xây dựng H ', thêm vào đầu của H u, có nhãn C, và vòng cung ( 1, u), (2 , u), , ( k, u). H 'là màn hình hiển thị DA-đồ thị trên F.
R3. Không có đồ thị khác không phải là DA-đồ thị hiển thị trên F.
Sau đó hiển thị DA-đồ thị trên F sẽ được gọi là DDA-đồ thị trên F. Bất kỳ DDA-đồ thị của F được xây dựng bằng cách sử dụng một ứng dụng duy nhất các quy tắc R1 và một số ứng dụng nhất định trong các quy định R2.
Nếu H là một đồ thị của DDA-, sau đó các hàng đầu trong H được gọi là đỉnh đầu nếu không có vòng cung đến trong đó. Bất kỳ đỉnh ban đầu được thêm vào H bởi các quy tắc R1.
Giả sử H là một DDA-đồ thị H trên F. Graf gọi là DDA-đồ thị cho X Y, trong đó:
D1. X là tập hợp của các nhãn của các đỉnh ban đầu.
D2. Mỗi thuộc tính trong Y là nhãn của bất kỳ đỉnh trong H.
Sử dụng nhiều DDA-đồ thị H hơn F (ký hiệu là U (H)) là tập hợp của tất cả các F-phụ thuộc trong F, được sử dụng trong việc áp dụng các quy tắc R2 trong khi xây dựng DDA-đồ thị.
Dán nhãn hướng đồ thị mạch hở một cách hình học của mô tả trình tự của RAP-O, tức là nếu chúng ta đưa ra một chuỗi các RAP-O X Y, sau đó chúng ta có thể xây dựng một đồ thị của DDA-F cho X Y và ngược lại.
Nói cách khác, có một sự tương ứng tự nhiên giữa B-tiên đề, các quy tắc xây dựng DDA-đồ thị trên F và xác định các điều khoản của DDA-đồ thị F cho X Y. Tiên đề B1 tương ứng với quy tắc R1 xây dựng DDA-đồ thị. Tiên đề B2 tương ứng với quy tắc R2. Tiên đề B3 có trong định nghĩa của điều kiện D2 DDA-đồ thị cho X Y.
Tiên đề B2 và R2 thường có thể được tăng cường bằng phương pháp tương tự. Phiên bản nâng cao của B2 có thể được diễn tả như sau:
B2. X YZ và Z VW nên X VYZ,
trong đó V cũng là một tập hợp con của tập R.
2.4.4. Kiểm tra thuộc F +
Để xác định xem các thiết lập F ngụ ý sự phụ thuộc X Y, nó cũng đủ để kiểm tra xem một X Y F +. Tuy nhiên, F + có thể lớn hơn nhiều so với F (xem Ví dụ 2.21), vì vậy nó là tốt hơn để sử dụng một phương pháp khác kiểm tra xem X Y F +, mà không yêu cầu việc xây dựng tất cả phụ thuộc của F. Phương pháp này dựa trên việc xây dựng các mạch X trên F. Sau khi như tìm thấy X +, bạn có thể kiểm tra xem sự phụ thuộc của X Y F.
Thuật toán 2.2. ĐÓNG CỬA.
Đầu vào: một tập hợp các thuộc tính X và tập F-phụ thuộc F.
Năng suất: việc đóng cửa của X trên F.
CHỨC NĂNG ĐÓNG CỬA
THÔNG SỐ X, F
olddep = 0
newdep = X
DO KHI newdep # olddep
olddep = newdep
CHO mỗi F-phụ thuộc của W Z trong F
NẾU newdep W
newdep = newdep Z
ENDIF
ENDFOR
ENDDO
RETURN newdep
Thuật toán này xây dựng một đồ thị của DDA-F cho X X +, sử dụng một phiên bản nâng cao của các quy tắc trong việc xác định R2 DDA-đồ thị, khi được bổ sung trong một lần chạy nhiều hơn một đỉnh.
Sử dụng các thuật toán rất dễ dàng để xây dựng một thuật toán ĐÓNG CỬA thành viên, kiểm tra xem sự phụ thuộc của X Y F.
Thuật toán 2.3. Thành viên.
Đầu vào: tập các phụ thuộc F-F và F-phụ thuộc của X Y.
Đầu ra: đúng nếu F sau từ X Y, sai khác.
CHỨC NĂNG THÀNH VIÊN
THÔNG SỐ F, X Y
NẾU Y ĐÓNG CỬA (X, F)
RETURN. T.
Khác
RETURN. F.
ENDIF
