Nhắc lại một số khái niệm cơ bản
Miền
Một miền D là tập hợp các giá trị nguyên tố không thể phân chia thành các thành phần nhỏ hơn trong mô hình quan hệ Mỗi miền được xác định bởi một tên miền và một kiểu dữ liệu Mỗi thuộc tính có thể tương ứng với một miền, và các thuộc tính khác nhau không nhất thiết phải có miền riêng biệt.
Quan hệ
Một quan hệ trên (hay xác định trên) tập thuộc tính Ω = {A 1 , A 2 ,…,A n } là một tập con của tích Descartes
Dom(A 1 ) Dom(A 2 ) … Dom(A n ), trong đó Dom(A i ) là miền trị của thuộc tính A i , i = 1, 2,…, n
Cho quan hệ r xác định trên tập thuộc tính Ω = {A 1 , A 2 ,…,A n } Theo định nghĩa, ta có thể viết r dưới dạng sau: r {(a 1 , a 2 ,…,a n ) | a i Dom(A i ), i = 1, 2,…, n}
Các tính chất đặc trưng của một quan hệ
Để làm rõ hơn khái niệm quan hệ trong mô hình dữ liệu quan hệ, ta xem xét các tính chất đặc trưng sau đây của quan hệ:
Mỗi quan hệ có một tên phân biệt
Mỗi ô trong bảng (quan hệ) chứa một giá trị nguyên tố
Mỗi thuộc tính có một tên phân biệt
Các giá trị của một thuộc tính thuộc cùng một miền
Thứ tự của các thuộc tính là không quan trọng
Không có hai bộ trùng nhau trong một quan hệ
Thứ tự của các bộ là không quan trọng
Trong một mô hình dữ liệu quan hệ, mỗi giá trị trong bộ phải là giá trị nguyên tố, không cho phép thuộc tính phức hợp hay thuộc tính đa trị Điều này yêu cầu rằng các thuộc tính đa trị phải được biểu diễn thông qua các quan hệ, trong khi các thuộc tính phức hợp cần được chia nhỏ thành các thành phần đơn lẻ của chúng.
Trong một số trường hợp, có thể có những ô trong bảng quan hệ mà giá trị của chúng chưa được xác định hoặc không có giá trị phù hợp để gán cho thuộc tính của một bộ dữ liệu nào đó Để xử lý tình huống này, giá trị đặc biệt được gọi là giá trị null sẽ được sử dụng cho những ô kiểu này.
Thứ tự của các thuộc tính trong một quan hệ là không quan trọng khi đảm bảo được sự tương ứng giữa các thuộc tính với các giá trị
Các phần tử trong một tập hợp không có thứ tự, vì vậy các bộ không yêu cầu một thứ tự cụ thể trong một quan hệ Hai quan hệ được coi là đồng nhất nếu chúng chứa cùng một tập hợp các bộ, mặc dù thứ tự của các bộ trong chúng có thể khác nhau.
Lược đồ quan hệ
tập hữu hạn các thuộc tính của quan hệ, F là tập các ràng buộc giữa các thuộc tính
Một ràng buộc trên tập thuộc tính {A1, A2,…,An} thể hiện một tính chất của tất cả các quan hệ xác định trong tập thuộc tính này Mỗi ràng buộc được gọi là một phụ thuộc dữ liệu.
Lược đồ quan hệ là công cụ mô tả cấu trúc và ràng buộc của một quan hệ Mặc dù quan hệ có thể thay đổi liên tục theo thời gian, nhưng cấu trúc và các ràng buộc của nó thường ổn định trong một khoảng thời gian nhất định.
Cho lược đồ quan hệ S = với Ω = {A 1 , A 2 ,…,A n } Nếu không quan tâm đến tập các ràng buộc F thì ta sẽ dùng ký hiệu S(A 1 , A 2 ,…,A n ) hoặc S(Ω) thay cho S =
Ký hiệu r(S) được sử dụng để biểu thị một quan hệ r trong lược đồ quan hệ S Đối với một bộ t thuộc r(S) và tập hợp X là một tập con của Ω, ký hiệu t[X] đại diện cho bộ chỉ chứa các giá trị của t tại các thuộc tính trong X.
Một lược đồ cơ sở dữ liệu quan hệ bao gồm một tập hợp các lược đồ quan hệ S’ {S 1 , S 2 ,…,S p } Thể hiện của lược đồ này được biểu diễn bằng tập các thể hiện DB = {r 1 (S 1 ), r 2 (S 2 ),…, r p (S p )} Do đó, một cơ sở dữ liệu quan hệ chính là một thể hiện của lược đồ cơ sở dữ liệu quan hệ.
Cơ sở dữ liệu quan hệ cỡ lớn là loại cơ sở dữ liệu có khả năng lưu trữ một khối lượng dữ liệu khổng lồ, thường bao gồm hàng chục thuộc tính và hàng trăm nghìn bản ghi.
Phụ thuộc hàm
Khái niệm phụ thuộc hàm
Phụ thuộc hàm là một khái niệm quan trọng trong lý thuyết cơ sở dữ liệu Cho tập thuộc tính và lược đồ quan hệ S(), nếu X, Y là các tập con của , thì Y được coi là phụ thuộc hàm vào X trên lược đồ S() ký hiệu là X Y Điều này có nghĩa là trong mọi quan hệ r thuộc lược đồ S(), nếu hai bộ t 1 và t 2 có giá trị thuộc tính X giống nhau (t 1 [X] = t 2 [X]), thì giá trị thuộc tính Y cũng phải giống nhau (t 1 [Y] = t 2 [Y]).
Nếu Y phụ thuộc hàm vào X thì ta cũng nói "X xác định hàm Y" Với mỗi quan hệ r trên lược đồ S(), ta nói r thỏa mãn (hay thỏa) phụ thuộc hàm
X phụ thuộc hàm Y trên r nếu và chỉ nếu với mọi bộ t1, t2 thuộc r, t1[X] = t2[X] dẫn đến t1[Y] = t2[Y] Trong luận án này, chúng tôi giới hạn F của lược đồ S = chỉ bao gồm các phụ thuộc hàm.
Hệ quy tắc suy diễn Armstrong
Với lược đồ quan hệ S = và X, Y , ta ký hiệu XY thay cho
X Y Với mọi X, Y, Z , hệ quy tắc suy diễn Armstrong đối với các phụ thuộc hàm gồm ba quy tắc sau đây:
Q 2 (Gia tăng): Nếu X Y thì XZ YZ
Q 3 (Bắc cầu): Nếu X Y và Y Z thì X Z
Ký hiệu F + đại diện cho tập hợp tất cả các phụ thuộc hàm có thể được suy diễn từ F thông qua việc áp dụng hữu hạn các quy tắc trong hệ quy tắc suy diễn Armstrong.
Bao đóng của một tập thuộc tính
Cho tập phụ thuộc hàm F trên tập thuộc tính , với Y, Z thuộc , và X là một tập con của Bao đóng của tập thuộc tính X đối với F, ký hiệu là X F , bao gồm tất cả các thuộc tính A thuộc sao cho mối quan hệ X A có thể được suy diễn từ F thông qua hệ quy tắc suy diễn Armstrong.
Khóa của lược đồ quan hệ
Một quan hệ là một tập hợp các bộ, trong đó các phần tử là phân biệt, do đó không thể có hai bộ trùng nhau Với mỗi lược đồ quan hệ S = , tồn tại một tập thuộc tính SK ⊆ Ω, đảm bảo rằng với mỗi thể hiện r(S), hai bộ khác nhau t1 và t2 trong r sẽ có giá trị thuộc tính SK khác nhau.
Siêu khóa trong một lược đồ quan hệ S là tập hợp các thuộc tính có khả năng xác định duy nhất một bản ghi trong mỗi thể hiện của lược đồ S.
Cho lược đồ quan hệ S = , siêu khóa SK của S đảm bảo rằng mọi tập con của Ω chứa SK cũng là siêu khóa Siêu khóa "nhỏ nhất" được gọi là khóa.
Khóa của một lược đồ quan hệ S được định nghĩa là một siêu khóa của S, trong đó mọi tập con thực sự của siêu khóa này không phải là siêu khóa của S.
Mỗi lược đồ quan hệ luôn có ít nhất một khóa và có thể có nhiều khóa
Một thuộc tính xuất hiện trong một khóa nào đó được gọi là thuộc tính khóa
Ngược lại, một thuộc tính không xuất hiện trong bất kỳ khóa nào được gọi là thuộc tính không khóa
Sử dụng khái niệm phụ thuộc hàm, khái niệm khóa và siêu khóa của lược đồ quan hệ được định nghĩa lại như sau:
Cho lược đồ quan hệ S = và K Ta nói K là một khóa của
S nếu hai điều kiện sau đây đồng thời được thỏa mãn:
(i) (K ) F + (ii) Nếu K' K thì (K' ) F + Nếu K thỏa mãn điền kiện (i) thì K được gọi là một siêu khóa của
S Như vậy, mọi khóa của S đồng thời cũng là siêu khóa của S.
Phụ thuộc hàm suy rộng
Phụ thuộc hàm xấp xỉ
Phụ thuộc hàm xấp xỉ là các phụ thuộc hàm được thỏa mãn với phần lớn các bộ trong quan hệ Để định nghĩa chính xác thuật ngữ "xấp xỉ", cần sử dụng một độ đo để đánh giá mức độ thỏa mãn hoặc mức độ vi phạm của mỗi phụ thuộc hàm Để xác định mức độ vi phạm của X Y trên quan hệ r, một độ đo lỗi, ký hiệu là e X( Y r, ), sẽ được áp dụng, với một ngưỡng lỗi đã cho.
, 0 1 Ta nói X Y là phụ thuộc hàm xấp xỉ nếu và chỉ nếu
( , ) e X Y r Một độ đo lỗi được sử dụng phổ biến là g 3 [41], dựa trên số bộ tối thiểu cần phải loại bỏ khỏi r để X Y đúng
Trong ví dụ 1.1, với quan hệ cho trong bảng 1.1, Tên xác định xấp xỉ Giới tính Để đảm bảo phụ thuộc hàm Tên Giới tính chính xác, cần loại bỏ bộ có mã số 003 Kết quả là g 3 (Tên Giới tính, Nhân viên) = 1/8 = 0.125.
Trong danh sách nhân sự, có tổng cộng 8 thành viên với mã số, họ tên, giới tính và chức vụ được phân loại rõ ràng Trưởng phòng là Vũ Văn Tuấn (nam), Phó trưởng phòng là Nguyễn Thị Mai (nữ) Bên cạnh đó, có 6 nhân viên khác bao gồm Phạm Thị Hải, Trần Văn Hải, Nguyễn Minh Tuấn, Vũ Thị Linh, Lê Văn Hải và Nguyễn Văn Thắng, trong đó có 3 nam và 3 nữ.
Có nhiều phương pháp đã được đề xuất để tính độ thỏa hoặc độ đo lỗi
Các phương pháp này được tóm tắt và so sánh trong [34] Chẳng hạn, trong
[72], độ thỏa của X Y trên quan hệ r được xác định như sau:
( ( ) trong đó, nếu t i [X] = t j [X] và t i [Y] t j [Y] thì ( , ) ( ) 0 i j
TRUTH t t X Y ; NTP là tổng số cặp bộ trong r và bằng
Ví dụ 1.2 Với quan hệ cho trong bảng 1.1, ta có độ thỏa của phụ thuộc hàm
TRUTH Nhân viên (Tên Giới tính) = 26/28 93%
Một cách khác để tính độ thỏa của X Y trên quan hệ r được giới thiệu trong [56, 57], cụ thể: xây dựng quan hệ tương đương E(X) trên r như sau:
Quan hệ E(X) phân hoạch tập r thành các lớp tương đương, trong đó mỗi lớp tương đương là một tập con của r chứa các bộ giống nhau trên X Ký hiệu cho phân hoạch này là π X.
Với u X , nếu t 1 [X] = t 2 [X] t 1 [Y] = t 2 [Y], t 1 , t 2 u, thì ta nói rằng u thỏa X Y Ngược lại, u không thỏa X Y Thực hiện đoạn chương trình dưới đây để nhận được quan hệ r 1 r 1 : = ;
For each u X do if (u thỏa X Y) then r 1 : = r 1 u; Đặt k = |r 1 | / |r| Khi đó, ta nói r thỏa X Y với độ phụ thuộc k, 0 k 1
Trong ví dụ 1.3, chúng ta xem xét phụ thuộc hàm Tên Giới tính dựa trên dữ liệu từ bảng 1.1 Kết quả cho thấy tập hợp T n ê = {{t 1 , t 5 }, {t 2 }, {t 3 , t 4 , t 7 }, {t 6 }, {t 8 }} Khi kết hợp các phần tử, ta có r 1 = {{t 1 , t 5 } {t 2 } {t 6 } {t 8 }} = {t 1 , t 5 , t 2 , t 6 , t 8 } Từ đó, tỷ lệ k = |r 1 | / |r| = 5/8 = 0.625 Điều này cho thấy rằng r thỏa mãn phụ thuộc hàm Tên Giới tính với độ phụ thuộc là 0.625.
Phụ thuộc hàm mêtric
Khi tích hợp dữ liệu từ nhiều nguồn khác nhau, thường xuất hiện sai lệch nhỏ trong định dạng, như địa chỉ và số điện thoại Những sai lệch này có thể vi phạm các phụ thuộc hàm truyền thống, mặc dù thực tế không có vi phạm về mặt ngữ nghĩa.
Khái niệm phụ thuộc hàm mêtric [42], được định nghĩa dưới đây, sẽ tổng quát hóa khái niệm phụ thuộc hàm truyền thống
Xét phụ thuộc hàm X Y trên quan hệ r Với mỗi bộ t r, ký hiệu [t] X = {u r : u[X] = t[X]} và X = {[t] X : t r}
Với T r, ký hiệu T[Y] = {t[Y] : t T} Khi đó, phụ thuộc hàm X Y đúng trên r nếu
T X max T Y Cho một mêtric d trên tập Y, d: dom(Y) dom(Y) R, và một tham số
0 Một phụ thuộc hàm mêtric, ký hiệu là X Y, được gọi là đúng trên r (hay thỏa r) nếu
Phụ thuộc hàm X → Y đúng trên quan hệ r có nghĩa là nếu hai bộ t 1 và t 2 trong r có t 1[X] = t 2[X], thì nhất định t 1[Y] = t 2[Y] Điều này cho thấy phụ thuộc hàm mêtric là sự mở rộng của phụ thuộc hàm truyền thống, trong đó điều kiện t 1[Y] = t 2[Y] được thay thế bằng điều kiện d(t 1[Y], t 2[Y]) ≤ δ.
The data source reveals information about various films, including their titles and durations Notably, "Aliens" has run times of 110 and 112 minutes on different platforms, while "Clockwork Orange" appears with durations of 137 and 131 minutes Additionally, "A Beautiful Mind" is listed with times of 144 and 145 minutes across different sites.
Ví dụ 1.4 [42] Xét quan hệ Phim cho trong bảng 1.2, với X = Tên phim, Y Thời gian Ta có X = {{t 1 , t 2 }, {t 3 , t 6 }, {t 4 , t 5 }} Với T = {t 1 , t 2 } T[Y] {110, 112} d ( [ ])T Y 2; với T = {t 3 , t 6 } T[Y] = {137, 131}
X 6Y đúng với quan hệ Phim.
Phụ thuộc hàm điều kiện
Phụ thuộc hàm điều kiện [12, 32, 75] được sử dụng trong vấn đề làm sạch dữ liệu Xét quan hệ Q 1 được cho trong bảng 1.3
Mối quan hệ Qh 1 không thỏa mãn phụ thuộc hàm AB → C vì hai bộ t1 và t2 có cùng giá trị trên AB nhưng khác giá trị trên C Tuy nhiên, Qh 1 thỏa mãn ràng buộc φ = {A = 002, B} → {C}, tức là nếu chỉ xem xét các bộ của Qh 1 với giá trị thuộc tính A là 002, thì phụ thuộc hàm AB → C là đúng.
Một phụ thuộc hàm điều kiện có dạng = (X Y, T p ), trong đó X Y là một phụ thuộc hàm và T p là một bảng mẫu với các thuộc tính trong X Y
Bảng mẫu T p chứa các bộ mẫu, trong đó mỗi bộ mẫu t p thuộc T p bao gồm các giá trị hằng và biến không tên "" Biến không tên này có thể nhận giá trị tùy ý trong miền thuộc tính tương ứng Bảng mẫu xác định các bộ của quan hệ phải thỏa mãn phụ thuộc hàm X Y Một cách trực quan, bảng mẫu T p của làm mịn phụ thuộc hàm X Y được nhúng trong thông qua việc áp đặt mối liên kết giữa các giá trị dữ liệu có liên quan về mặt ngữ nghĩa.
Theo định nghĩa về phụ thuộc hàm điều kiện, ràng buộc được xác định là một phụ thuộc hàm điều kiện (AB C, T p), trong đó T p là bảng mẫu chỉ chứa một bộ mẫu cụ thể.
Dưới đây là một số ví dụ về các phụ thuộc hàm điều kiện trong quan hệ Khách hàng (Cust), như được trình bày trong bảng 1.4 Trong đó, CC đại diện cho mã quốc gia, AC là mã vùng, PN là số điện thoại, NM là tên, và STR, CT, ZIP lần lượt là các thông tin về địa chỉ.
Here are the contact details for several individuals located in New York City and Philadelphia: Mike Tree Ave., NYC 07974, phone number 01 908 1111111; Rich Tree Ave., NYC 07974, phone number 01 908 1111111; Joe Elm Str., NYC 01202, phone number 01 212 2222222; Jim Elm Str., NYC 01202, phone number 01 212 2222222; Ben Oak Ave., Philadelphia 02394, phone number 01 215 3333333; and Ian High St., Edinburgh EH4 1DT, phone number 44 131 4444444.
Xét 3 phụ thuộc hàm điều kiện sau đây:
1 = ({CC, ZIP} {STR}, T 1 ) với bảng mẫu T 1
2 = ({CC, AC, PN} {STR, CT, ZIP}, T 2 ) với bảng mẫu T 2
CC AC PN STR CT ZIP
3 = ({CC, AC} {CT}, T 3 ) với bảng mẫu T 3
Quan hệ Cust thỏa mãn điều kiện 1 và 3 nhưng không thỏa mãn điều kiện 2 do bộ t 1 vi phạm bộ mẫu t c = (01, 098, , , MH, ) trong bảng mẫu T 2 của 2 Điều này cho thấy rằng một bộ có thể vi phạm phụ thuộc hàm điều kiện, trong khi sự vi phạm của phụ thuộc hàm cần phải xem xét hai bộ.
Phụ thuộc hàm là trường hợp đặc biệt của phụ thuộc hàm điều kiện
Thật vậy, phụ thuộc hàm X Y chính là phụ thuộc hàm điều kiện (X Y, T p ) với T p chỉ gồm một bộ mẫu t p duy nhất và t p [A] = "" với mọi
Phụ thuộc hàm mờ
Khái niệm phụ thuộc hàm mờ, được đề xuất trong nghiên cứu [3], xuất phát từ dữ liệu thực tế có tính chất mờ tự nhiên Phụ thuộc hàm mờ trong nghiên cứu này được xây dựng bằng cách thay thế quan hệ bằng nhau trong khái niệm phụ thuộc hàm truyền thống bằng quan hệ bằng nhau mờ Thông thường, khi so sánh hai giá trị dữ liệu, chỉ có hai khả năng xảy ra là bằng nhau hoặc khác nhau Tuy nhiên, với lý thuyết tập mờ, hai giá trị dữ liệu có thể được coi là bằng nhau với một mức độ α nhất định.
(0 ≤ ≤ 1), tham số được cung cấp bởi người thiết kế cơ sở dữ liệu
Cho r là một quan hệ xác định trên tập thuộc tính Ω = {A 1 , A 2 ,…,A n } và
X, Y Với mỗi thuộc tính A i Ω, mức độ bằng nhau của các giá trị dữ liệu trong Dom(A i ) được xác định bởi quan hệ (hàm) R i
Cho trước tham số (0 ≤ ≤ 1), ta nói 2 bộ t 1 [X] và t 2 [X] bằng nhau với mức , kí hiệu t 1 [X] E() t 2 [X], nếu R k (t 1 [A k ], t 2 [A k ]) với mọi A k X
Khi đó, X Y được gọi là phụ thuộc hàm mờ mức nếu với mọi t 1 , t 2 r, t 1 [X] E() t 2 [X] t 1 [Y] E() t 2 [Y]
Ví dụ 1.6 [3] Cho Ω = {A 1 , A 2 , A 3 } với Dom(A 1 ) = {a, b, c}, Dom(A 2 ) = {p, q} và Dom(A 3 ) = {x, y, z}
Xét quan hệ Qh 2 tại bảng 1.5 và X = {A 1 , A 2 }, Y = {A 3 } Ta thấy Qh 2 không thỏa phụ thuộc hàm X Y Tuy nhiên, Qh 2 thỏa phụ thuộc hàm mờ
Phụ thuộc sai phân
Khái niệm phụ thuộc sai phân mở rộng quan hệ bằng nhau ở cả hai vế của phụ thuộc hàm X → Y trên quan hệ r Điều kiện t1, t2 bằng nhau trên X và Y được thay thế bằng hai bộ thỏa mãn hàm φL và φR, được gọi là các hàm sai phân Các phép toán trong hàm sai phân bao gồm =, , ≤, ≥, cùng với các toán tử và (∧) và hoặc (∨) Các hàm sai phân sử dụng khoảng cách metric để mở rộng các quan hệ bằng nhau trong khái niệm phụ thuộc hàm.
Trong một hệ thống lưu trữ thông tin về giá vé máy bay, có một ràng buộc quan trọng: "Sự khác biệt về giá giữa hai ngày bất kỳ trong khoảng thời gian một tuần không được vượt quá 100$" Ràng buộc này được thể hiện thông qua phụ thuộc sai phân, đảm bảo tính nhất quán và hợp lý trong việc quản lý giá vé.
Nghĩa là, với hai bộ bất kỳ t 1 , t 2 trong quan hệ đang xét,
Phụ thuộc hàm là một trường hợp đặc biệt của phụ thuộc sai phân, cụ thể khi điều kiện L (t 1 [Date], t 2 [Date]) ≤ 7 dẫn đến R (t 1 [Price], t 2 [Price]) ≤ 100 Trong bối cảnh này, nếu L [t 1 [X], t 2 [X]) = 0 và R [t 1 [Y], t 2 [Y]) = 0, thì phụ thuộc sai phân được xem như một sự mở rộng của phụ thuộc hàm mêtric.
Các loại phụ thuộc hàm suy rộng khác
There are various types of generalized functional dependencies, such as Probability Based Functional Dependencies, Similarity Functional Dependencies, and Approximate Differential Dependencies Each type emerges from practical applications and represents an extension of the traditional concept of functional dependency, relaxing the notion of equality in specific ways.
Phát hiện phụ thuộc hàm
Phương pháp top-down
Phương pháp top-down bắt đầu bằng việc sinh các phụ thuộc hàm ứng viên từ một dàn thuộc tính, kiểm tra sự thỏa mãn của chúng, và sử dụng các phụ thuộc hàm đã được xác nhận để tỉa các ứng viên ở các mức thấp hơn, nhằm thu hẹp không gian tìm kiếm Trong phần này, chúng tôi sẽ trình bày quy trình sinh và tỉa các phụ thuộc hàm ứng viên, cùng với hai phương pháp cài đặt cụ thể: phương pháp phân hoạch với các thuật toán TANE và FD_Mine, và phương pháp tập tự do sử dụng lực lượng của các quan hệ chiếu để kiểm tra sự thỏa mãn của các phụ thuộc hàm thông qua thuật toán FUN.
Phụ thuộc hàm ứng viên là các phụ thuộc hàm có thể tồn tại về mặt cú pháp trong một lược đồ quan hệ, nhưng chưa được kiểm tra sự thỏa mãn của chúng đối với một thể hiện cụ thể của lược đồ đó.
Trong lược đồ S(Ω) với Ω = {A1, A2, , An}, vế trái của các phụ thuộc hàm ứng viên được tạo ra từ tất cả các tổ hợp thuộc tính có thể của Ω Chúng ta chỉ chú trọng đến các phụ thuộc hàm tối thiểu có một thuộc tính ở vế phải, với số lượng thuộc tính ở vế trái tối đa là (n - 1) Ví dụ, các phụ thuộc hàm ứng viên không có thuộc tính ở vế trái bao gồm ∅ → A1, , ∅ → An; trong khi đó, các phụ thuộc hàm ứng viên với một thuộc tính ở vế trái như A1 → A2, A1 → A3, và A1 → An, cùng với các phụ thuộc có hai thuộc tính ở vế trái như A1A2 → A3, A1A2 → dàn thuộc tính.
Dàn thuộc tính là một đồ thị có hướng, trong đó nút gốc (L-0) không mang thuộc tính nào và được ký hiệu bằng ký hiệu Các nút con của nút gốc được gọi là các nút mức 1 (L-1), và mỗi nút này đều có một thuộc tính riêng Tổng số lượng nút ở mức L-1 là
C n n nút Mỗi nút ở mức 2 (L-2) là một tổ hợp gồm hai thuộc tính, do đó có
Cấu trúc của các mức thuộc tính được xây dựng theo quy tắc từ mức L-2 trở đi, với mức cuối cùng L-n chứa tất cả các thuộc tính Kí hiệu n ij đại diện cho nút thứ j ở L-i và cũng biểu thị tập các thuộc tính tại nút đó Một cạnh có hướng được vẽ giữa nút n ij và nút n (i+1)k nếu n ij là tập con của n (i+1)k, thể hiện phụ thuộc hàm ứng viên dạng n ij (n (i+1)k - n ij) Hình 1.1 minh họa dàn thuộc tính với Ω = {A, B, C, D}, trong đó cạnh giữa nút AB và ABC biểu thị phụ thuộc hàm ứng viên AB C.
L-2 AB AC AD BC BD CD AB AC AD BC BD CD
L-3 ABC ABD ACD BCD ABC ABD ACD BCD
Hình 1.1 Minh họa dàn thuộc tính
Như trên đã phân tích, tổng số nút trong dàn thuộc tính là
Trong một dàn thuộc tính, các cạnh có tính đối xứng qua mức giữa nếu số lượng thuộc tính (n) là chẵn, hoặc đối xứng qua hai mức giữa nếu n là số lẻ Tổng số phụ thuộc hàm ứng viên, tương ứng với tổng số cạnh trong dàn, được xác định dựa trên cấu trúc này.
Dấu "=" xảy ra khi n là số chẵn
Kí hiệu |r| đại diện cho số bộ của quan hệ r trên lược đồ Ω = {A1, A2, , An} Trung bình, mỗi phụ thuộc hàm liên quan đến n/2 thuộc tính, dẫn đến độ phức tạp khi kiểm tra tất cả các phụ thuộc hàm ứng viên trong dàn thuộc tính đối với quan hệ r là 2^2.
; độ phức tạp này cũng là độ phức tạp trong trường hợp xấu nhất của tất cả các phương pháp đã được đề xuất
Tỉa trên dàn thuộc tính là quá trình loại bỏ các phụ thuộc hàm ứng viên, giúp giảm thiểu số lượng phụ thuộc hàm cần kiểm tra Do số lượng phụ thuộc hàm ứng viên tăng theo hàm mũ với số lượng thuộc tính, việc này trở nên cực kỳ quan trọng Việc tỉa này giúp tối ưu hóa quá trình phân tích và làm cho việc kiểm tra các phụ thuộc hàm đã được phát hiện trở nên hiệu quả hơn.
C đã được phát hiện là đúng thì không cần phải kiểm tra AB C vì AB C cũng đúng theo hệ quy tắc Armstrong
Các luật tỉa cơ bản sau đây thường được áp dụng và có thể được xác minh thông qua hệ quy tắc Armstrong Gọi là tập hợp các phụ thuộc hàm đã được phát hiện; X và Y là các tập con của Ω; A và B là hai thuộc tính trong Ω; X .
(T1) Nếu X A thì XZ A đúng và không cần phải kiểm tra
Nếu X A thuộc tập hợp và XAY B là một phụ thuộc hàm ứng viên, chúng ta chỉ cần kiểm tra XY B thay vì kiểm tra trực tiếp XAY B Việc kiểm tra từ trên xuống dưới trong dàn thuộc tính cho thấy XY B cần được xác minh trước, do đó không cần thiết phải kiểm tra XAY B.
(T3) Nếu X là một khóa thì mọi nút chứa X đều bị tỉa (xóa)
Các luật tỉa được phân thành hai loại chính: luật tỉa cạnh (T1, T2) và luật tỉa nút (T3) Bên cạnh các luật tỉa cơ bản, một số thuật toán như FD_Mine còn áp dụng các phụ thuộc hàm đối xứng, hay còn gọi là phụ thuộc hàm tương đương, trong đó X và Y có mối quan hệ X Y nếu X Y.
Thuật toán FUN tỉa các tập không tự do (non-free-sets) nhằm giảm kích thước dàn thuộc tính, trong khi thuật toán FastFDs, một phương pháp bottom-up, sử dụng các tập khác nhau để tỉa các nút trên dàn thuộc tính Việc này giúp tối ưu hóa và thu hẹp kích thước tập thuộc tính (chẳng hạn tập Y).
Các luật tỉa cơ bản được áp dụng trong thuật toán 1.1 nhằm tìm một phủ cho tất cả các phụ thuộc hàm đúng trên r Thuật toán này kiểm tra sự thỏa mãn của các phụ thuộc hàm theo một dàn thuộc tính, từ trái sang phải và từ trên xuống dưới Việc duyệt từ trên xuống dưới là hợp lý vì các phụ thuộc hàm ứng viên ở các mức cao hơn thường có ít thuộc tính ở vế trái hơn so với các mức thấp hơn Khi phát hiện A C, các phụ thuộc hàm ứng viên khác như AX C sẽ bị tỉa theo luật tỉa (T1) Duyệt từ dưới lên trên sẽ kém hiệu quả hơn, bởi vì nếu AX C được phát hiện, vẫn cần kiểm tra A C.
Trong thuật toán 1.1, dòng 7 thiết lập luật tỉa (T3), trong khi dòng 11 cài đặt các luật tỉa (T1) và (T2) Tại dòng 12, hàm supp(f, r) kiểm tra sự phụ thuộc của hàm ứng viên f trên quan hệ r; nếu f thỏa mãn, hàm sẽ trả về giá trị true, ngược lại sẽ trả về false.
Dễ thấy rằng thuật toán 1.1 cho kết quả là các phụ thuộc hàm tối tiểu
Theo tiến trình duyệt từng mức một trên dàn thuộc tính của thuật toán, cần chứng minh rằng nếu X A là phụ thuộc hàm bất kỳ thuộc tập (tập các phụ thuộc hàm đã được phát hiện), và không có phụ thuộc hàm nào có dạng f = (XY A) được bổ sung vào , thì các phụ thuộc hàm trong là tối thiểu Điều này có nghĩa là tồn tại điều kiện (X A) sao cho X nằm trong q và XA nằm trong c trên dòng.
11 phát hiện tình huống này Nếu phụ thuộc hàm ứng viên f = (XY A) thì q
= XY và c = XYA Điều này làm cho điều kiện trên dòng 11 đúng, f bị tỉa và không được bổ sung vào
Phương pháp bottom-up
Khác với phương pháp top-down ở trên, phương pháp bottom-up [45] so sánh các bộ của quan hệ để tính các tập bằng nhau và các tập khác nhau
Kỹ thuật bottom-up sử dụng các tập đã được xác định để xác lập các phụ thuộc hàm chính xác trên quan hệ cần xem xét Điểm nổi bật của phương pháp này là không kiểm tra các phụ thuộc hàm ứng viên dựa trên quan hệ mà thay vào đó, dựa vào các tập bằng nhau và khác nhau đã được tính toán.
Phủ âm là một khái niệm quan trọng trong lý thuyết cơ sở dữ liệu, đại diện cho tập hợp tất cả các phụ thuộc hàm có thể vi phạm quan hệ Nó được xác định dựa trên các tập bằng nhau của các bộ thuộc trong quan hệ, giúp xác định các phụ thuộc không cần thiết và tối ưu hóa thiết kế cơ sở dữ liệu.
Tập bằng nhau của hai bộ t và 1 t , kí hiệu 2 ag t t , là tập thuộc tính ( , ) 1 2
X lớn nhất sao cho t X 1 [ ]t X 2 [ ] Tập gồm tất cả các tập bằng nhau trên quan hệ r kí hiệu là ag r( )
Ví dụ 1.9 Quan sát bảng 1.6, ta có
( , ) ag t t BW và ag r ( ) BW B NBS W , , ,
Các tập bằng nhau có thể được xác định từ các phân hoạch thuộc tính Cho phân hoạch A của thuộc tính A và hai bộ t1, t2 thuộc A, nếu tồn tại một tập con c là lớp tương đương trong A sao cho t1, t2 đều thuộc c, thì ta có thể kết luận rằng t1 và t2 bằng nhau Để nâng cao hiệu quả tính toán, việc sử dụng các phân hoạch lược gọn là rất cần thiết.
Tính chất của các tập bằng nhau cho thấy rằng nếu \( t_1 = t_2 \) với \( X \), thì mọi thuộc tính \( A \) không thuộc \( X \) sẽ có giá trị khác nhau, tức là \( t_1[A] \neq t_2[A] \) Điều này có nghĩa là mối quan hệ \( X \rightarrow A \) bị vi phạm bởi \( t_1 \) và \( t_2 \) Đây là nguyên lý cơ bản của phương pháp tiếp cận dựa trên phủ âm.
Tập cực đại của một thuộc tính A , kí hiệu max A( ), được định nghĩa như sau: max(A) = {X | X ag(r), A X, Y ag(r) : X Y}
Do X không chứa A nên X A bị vi phạm bởi ít nhất một cặp bộ
Vì Yag r( ) :X Y nên X là một tập tối đại Ý tưởng sử dụng tập tối đại
X từ ag r( ) chỉ ra rằng nếu XY A bị vi phạm bởi một cặp bộ, thì cả X A và Y A cũng sẽ bị vi phạm bởi cặp bộ đó Để đảm bảo tính hiệu quả, chúng ta chỉ cần xem xét các tập tối đại thay vì tất cả các tập bằng nhau.
Tất cả các tập cực đại của các thuộc tính hình thành một phủ của bao đóng âm, bao gồm tất cả các phụ thuộc hàm vi phạm mối quan hệ đang được xem xét.
Ví dụ 1.10 Từ ví dụ 1.9, ta có:
Các tập cực đại được sử dụng để xác định các phụ thuộc hàm chính xác trên r Những phụ thuộc hàm này có vế phải là A, được ký hiệu là FD A( ), và được xây dựng dựa trên các tập hợp này.
FD 1 (A) = {X A | X ( - A), Y max(X): X Y} (1a) FD(A) = {f | f FD 1 (A), g FD 1 (A): vetrai(g) vetrai(f)} (2a)
Khi xem xét mọi Y thuộc max A(), ta nhận thấy rằng Y → A bị vi phạm bởi ít nhất một cặp bộ của r Nếu một tập thuộc tính V nào đó được thêm vào Y, điều này sẽ tạo ra sự thay đổi trong mối quan hệ giữa Y và A.
Nếu YV là tối đa với A, thì YV dẫn đến A sẽ được thỏa mãn Do đó, vì X không phải là tập con của Y, nên X dẫn đến A cũng phải được thỏa mãn Từ đó, có thể suy ra rằng phụ thuộc hàm A chỉ chứa các phụ thuộc hàm tối thiểu.
Tập FD A( ) được xây dựng bằng cách đầu tiên xác định tập L, chứa tất cả các thuộc tính trong max A( ) Ta kiểm tra từng thuộc tính B thuộc L; nếu B không nằm trong bất kỳ tập nào của max A( ), ta sẽ bổ sung B A vào FD A( ) Tiếp theo, ta xem xét các tập hợp hai thuộc tính từ L, như BC; nếu BC không phải là tập con của bất kỳ tập nào trong max A( ) và không chứa vế trái của phụ thuộc hàm trong FD A( ), ta sẽ thêm BC A vào FD A( ) Quy trình này tiếp tục với các tập hợp ba, bốn thuộc tính cho đến khi hoàn tất, đồng thời áp dụng luật tỉa (T1) để giảm bớt số lượng tổ hợp cần kiểm tra.
Từ ví dụ 1.10, ta xác định rằng max I( ) = {BW, NBS} Tất cả các tập hợp thuộc tính đơn (trừ I) đều nằm trong một phần tử của max I( ), cho thấy không có thuộc tính nào có thể xác định hàm I Khi xem xét các tổ hợp hai thuộc tính như NB, NW, NS, BW, BS, WS, ta nhận thấy rằng NW và WS không có trong bất kỳ phần tử nào của max I( ) Do đó, ta bổ sung NW I và WS I vào tập hợp FD I( ) Tiếp theo, ta sẽ phân tích các tổ hợp ba thuộc tính.
Trong số các thuộc tính NBW, NBS, NWS và BWS, NBS là thuộc tính tối đa trong tập I( ) Các thuộc tính này không chứa vế trái của bất kỳ phụ thuộc hàm nào trong FD I( ), do đó không có phụ thuộc hàm nào được suy ra từ các tập ba thuộc tính Tương tự, cũng không có phụ thuộc hàm nào được suy ra từ các tập bốn thuộc tính Kết quả này cho thấy sự hạn chế trong việc suy diễn phụ thuộc hàm từ các tập thuộc tính đã nêu.
FD I NW I WSI Độ phức tạp của cách tiếp cận phủ âm là hàm mũ theo số thuộc tính của
Trong trường hợp xấu nhất, để tính tập bằng nhau ag r( ), cần thực hiện n r^2 phép so sánh với n = |Ω| Để xác định max A( ) cho mọi A trong Ω, cũng cần n ag r( )^2 phép so sánh Cuối cùng, để nhận được các phụ thuộc hàm từ max A( ) (với mọi A), cần thực hiện ( )^2 phép so sánh.
L L là số các phụ thuộc hàm ứng viên và L là tập tất cả các thuộc tính trong max A( ) Độ phức tạp tổng cộng của phương pháp này là ( 2 ( ) 2 ( ) 2 )
O n r n ag r n max A Trường hợp xấu nhất xảy ra khi L R
Các biến thể khác nhau của cách tiếp cận phủ âm được đề xuất trong
Khác với việc sử dụng tập cực đại để phát hiện trực tiếp các phụ thuộc hàm, nghiên cứu trong [46] áp dụng phần bù của các tập bằng nhau cực đại để xác định các phụ thuộc hàm được thỏa Phương pháp này được trình bày cùng với cách tiếp cận tập khác nhau trong bài viết.
Tập khác nhau, hay còn gọi là tập cần thiết, là một khái niệm quan trọng trong lý thuyết tập hợp Phương pháp này dựa trên tư tưởng đối ngẫu của khái niệm phủ âm Tập khác nhau của thuộc tính A, ký hiệu là dif A( ), bao gồm các tập con thuộc tính mà khi thuộc tính A có giá trị khác nhau trên hai bộ, thì ít nhất một tập con trong dif A( ) cũng sẽ có giá trị khác nhau trên hai bộ đó.
Khi đã tính được dif A( ) thì vế trái của các phụ thuộc hàm được thỏa phải chứa một thuộc tính từ mỗi tập con của dif A( )
Một số chủ đề liên quan đến phát hiện phụ thuộc hàm
Trong phần này, ta sẽ trình bày tóm tắt một số chủ đề liên quan đến phát hiện phụ thuộc hàm [45]
Khi làm việc với các mối quan hệ lớn, chi phí kiểm tra phụ thuộc hàm ứng viên có thể trở nên rất tốn kém Để tiết kiệm thời gian và giảm chi phí kiểm tra, phương pháp lấy mẫu được đề xuất như một giải pháp hiệu quả.
Kí hiệu f là một phụ thuộc hàm ứng viên, s là một mẫu nhỏ của quan hệ r , [0,1]
Tham số tin cậy nhỏ cho thấy rằng nếu điều kiện f được thỏa mãn bởi tập hợp s, thì nó cũng sẽ được thỏa mãn bởi tập hợp r với độ tin cậy (1) Ngược lại, nếu điều kiện f bị vi phạm bởi các phần tử trong s, thì chắc chắn f sẽ không được thỏa mãn bởi r.
Bằng cách áp dụng ý tưởng này, các phụ thuộc hàm của ứng viên không được thỏa mãn bởi quan hệ r có thể được tối ưu hóa hiệu quả Phương pháp lấy mẫu thường được kết hợp với các kỹ thuật khác để đạt được kết quả tốt nhất.
Trong phần này, chúng ta sẽ xem xét cách thức thay đổi của tập phụ thuộc hàm khi thực hiện thao tác chèn hoặc xóa một bộ dữ liệu từ quan hệ r đã được xác định trước Giả sử rằng tất cả các phụ thuộc hàm thỏa mãn bởi r đã được phát hiện và lưu trữ trong tập , việc thêm hoặc loại bỏ một bộ sẽ ảnh hưởng đến các phụ thuộc hàm hiện có.
Khi một bộ t được chèn vào r, các phụ thuộc hàm có thể được duy trì Đối với mỗi phụ thuộc hàm X → A trong tập hợp , kí hiệu X⁺ là bao đóng thuộc tính được tính từ Sau khi thực hiện thao tác chèn, cần tính toán lại các phụ thuộc hàm.
Khi q = 1, việc thêm bộ không làm ảnh hưởng đến tổng Tuy nhiên, nếu q > 1, cần tồn tại B trong X+ với các giá trị khác nhau trong qX[+] Cần tìm Z B trong sao cho Z thuộc X+ và loại bỏ Z B khỏi tổng .
Khi một bộ t bị xóa khỏi quan hệ r, các phụ thuộc hàm đúng trên r vẫn giữ nguyên tính đúng đắn trên (r - t) Tuy nhiên, việc xóa này có thể dẫn đến việc bổ sung các phụ thuộc hàm mới vào tập hợp , vì một số phụ thuộc hàm có thể bị vi phạm do sự loại bỏ bộ t Hiện tại, chưa có phương pháp đơn giản nào để phát hiện các phụ thuộc hàm mới này; do đó, chúng ta cần áp dụng lại các thuật toán phát hiện phụ thuộc hàm cho quan hệ (r - t).
Phát hiện khóa là một trường hợp đặc biệt của phát hiện phụ thuộc hàm, giúp xác định xem một tập thuộc tính có phải là khóa cho quan hệ r hay không Định lý 1.4 cung cấp phương pháp kiểm tra tính chất này.
(1) Cho X là một tập con của và rlà một quan hệ Tập X là một khóa của r nếu và chỉ nếu r X[ ] r [32, 59]
(2) Một thuộc tính AR là một khóa nếu và chỉ nếu A không thuộc bất kỳ tập bằng nhau nào của quan hệ r
Theo (1), điểm mấu chốt của định lý là việc tính lực lượng Lực lượng r có thể nhận được từ các siêu dữ liệu (metadata) của r Lực lượng
Giá trị r X được xác định trong hai trường hợp: nếu X chỉ có một thuộc tính, nó có thể được lấy từ các siêu dữ liệu của r tương tự như r Trong trường hợp X có nhiều thuộc tính, phương pháp phân hoạch có thể được áp dụng để tính toán giá trị r X.
Công trình trong [9] chỉ rõ: cho trước một tập các phụ thuộc hàm, bài
Phát hiện phụ thuộc hàm suy rộng
Phát hiện phụ thuộc hàm xấp xỉ
Thuật ngữ "phụ thuộc hàm xấp xỉ" đề cập đến việc một phụ thuộc hàm thông thường f X: Y được thỏa mãn gần đúng Để đạt được điều này, phụ thuộc hàm thông thường cần được thỏa mãn bởi phần lớn các bộ của quan hệ r Để định nghĩa chính xác hơn về "xấp xỉ", các bộ vi phạm được sử dụng để tính toán độ đo lỗi hoặc độ thỏa mãn của phụ thuộc hàm xấp xỉ.
Có nhiều phương pháp đã được đề xuất để tính độ thỏa hoặc độ đo lỗi
Các phương pháp này được tóm tắt và so sánh trong [34] Dưới đây là một phương pháp được đề xuất trong [41]
Để kiểm tra các phụ thuộc hàm xấp xỉ trên cơ sở dữ liệu r, các phương pháp phát hiện phụ thuộc hàm có thể được điều chỉnh để nhận diện các phụ thuộc hàm xấp xỉ bằng cách bổ sung vào phần tính toán độ thỏa mãn hoặc độ đo lỗi Một ví dụ cụ thể được nêu trong công trình [47] là việc áp dụng phương pháp phủ âm Ý tưởng chính của phương pháp này là nếu có một tập Z thuộc max A( ), thì mối quan hệ Z A sẽ không đúng trên quan hệ r Tuy nhiên, trong trường hợp phát hiện các phụ thuộc hàm xấp xỉ, điều này có thể được điều chỉnh để đạt được kết quả chính xác hơn.
Z A không bị vi phạm bởi nhiều bộ dữ liệu, tức là g Z 3 ( A r, ) nhỏ hơn hoặc bằng một ngưỡng nhất định, cho thấy rằng Z A là một phụ thuộc hàm xấp xỉ đã được xác định.
Phương pháp lấy mẫu được đề xuất trong tài liệu [41] cung cấp một cách tiếp cận mới để phát hiện các phụ thuộc hàm xấp xỉ Phương pháp này sử dụng một lượng nhỏ bộ dữ liệu để xác định xem một phụ thuộc hàm xấp xỉ có được thỏa mãn trên toàn bộ quan hệ r hay không, từ đó làm tăng độ phức tạp của vấn đề Kí hiệu s đại diện cho một mẫu ngẫu nhiên của quan hệ r, và chúng ta sẽ xem xét hai trường hợp cụ thể.
- Nếu f được thỏa mãn hoặc được thỏa mãn xấp xỉ bởi s thì có thể f không thỏa (vi phạm) bởi các bộ trong rs
Nếu hàm f bị vi phạm bởi một số ít bộ trong tập s, thì có khả năng hàm f thỏa xấp xỉ với tập r, vì nó có thể thỏa mãn tất cả các bộ trong r trừ s Để mô tả mối quan hệ xác suất giữa việc thỏa mãn hàm f bởi s và việc thỏa xấp xỉ bởi r, một tham số tin cậy δ được đưa vào Theo tham số này, nếu hàm f được thỏa mãn bởi s, ta có thể nói rằng hàm f được thỏa mãn bởi r với xác suất (1−δ).
Với cùng lập luận, một phủ của các phụ thuộc hàm xấp xỉ đúng trên s trở thành một phủ xác suất trên r
Kích thước mẫu ngẫu nhiên ảnh hưởng đến độ chính xác của việc phủ, mặc dù không hoàn toàn quyết định Một mẫu lớn có thể không bao gồm bất kỳ vi phạm nào, trong khi mẫu nhỏ có thể chứa hầu hết các vi phạm Do đó, việc xác định kích thước mẫu là rất quan trọng, và theo [41], kích thước mẫu cần nằm trong một phạm vi nhất định để đảm bảo độ chính xác.
Trong việc phát hiện các phụ thuộc hàm và phụ thuộc hàm xấp xỉ, có sự khác biệt rõ rệt giữa việc sử dụng mẫu Mẫu được áp dụng hiệu quả để loại bỏ những phụ thuộc hàm không thỏa mãn Nếu một phụ thuộc hàm vi phạm mẫu s của r, thì nó cũng vi phạm r, dẫn đến việc loại bỏ các phụ thuộc hàm ứng viên không thỏa mãn Những phụ thuộc hàm còn lại thỏa mãn, ký hiệu là dep s(), cần được kiểm tra thêm vì có thể một số phụ thuộc trong dep s() không thỏa mãn r Đối với mỗi phụ thuộc hàm f thuộc dep s(), nếu f thỏa mãn r, thì f sẽ được đưa vào dep r() Cuối cùng, dep r() sẽ chứa tất cả các phụ thuộc hàm thỏa mãn r và là một tập hợp bao trùm cho tất cả các phụ thuộc hàm thỏa mãn r.
Trong trường hợp các phụ thuộc hàm xấp xỉ, việc phát hiện một phủ của các phụ thuộc này từ một mẫu sẽ tạo ra một phủ xác suất trên r.
Công trình [40] đề xuất sử dụng độ đo lỗi của các siêu khóa để xác định sự thỏa mãn xấp xỉ của các phụ thuộc hàm Nghiên cứu chứng minh rằng mối quan hệ X A xảy ra nếu và chỉ nếu g X 3 ( ) = g XA 3 ( ), trong đó g Z 3 ( ) = 1 - r Z( ) / r biểu thị phần bộ tối thiểu cần loại bỏ khỏi r để Z trở thành một siêu khóa.
Công trình [37] mở rộng phương pháp phân hoạch để tính sự thỏa mãn xấp xỉ nhờ sử dụng độ đo lỗi g X 3 ( A).
Phát hiện phụ thuộc hàm điều kiện
Các phụ thuộc hàm có điều kiện là một kiểu ràng buộc mới mở rộng phụ thuộc hàm truyền thống dùng cho các mục đích làm sạch dữ liệu [12]
Phụ thuộc hàm điều kiện là một khái niệm mới trong nghiên cứu cơ sở dữ liệu, tuy nhiên, việc phát hiện phụ thuộc hàm điều kiện đã được nghiên cứu từ lâu Bài viết này sẽ tóm tắt định nghĩa và quy trình phát hiện phụ thuộc hàm điều kiện.
Cho hai tập con X và Y của một tập hợp , phụ thuộc hàm có điều kiện được định nghĩa như một phát biểu dưới dạng (X Y S), trong đó S là bảng mẫu trên X ∪ Y Một bộ p thuộc S là một bộ xác định trên tập thuộc tính X ∪ Y, với điều kiện rằng đối với mọi A thuộc X ∪ Y, p[A] có thể là một giá trị a thuộc Dom(A) hoặc là "−", biểu thị cho một biến không tên trong Dom(A) Một bộ t trong quan hệ r trên được coi là tương hợp với bộ mẫu p trong S nếu với mỗi A thuộc X, p[A] bằng "−" hoặc một giá trị cụ thể.
[ ] [ ] p A t A Một phụ thuộc hàm có điều kiện được thỏa bởi quan hệ r trên nếu và chỉ nếu: t t 1 , 2 r, p S, nếu t X 1 [ ]t X 2 [ ] p[X] thì t Y 1 [ ]t Y 2 [ ]
Trong định nghĩa trên, X Y được gọi là một phụ thuộc hàm nhúng
Ví dụ 1.12 [12] Xét một thể hiện của lược đồ quan hệ cust(CC, AC, PN,
NM, STR, CT, ZIP) được cho trong bảng 1.4
Ta thấy các phụ thuộc hàm được thỏa gồm:
1:[ , , ] [ , , ] f CC AC PN STR CT ZIP
Dưới đây là hai phụ thuộc hàm điều kiện được thỏa bởi quan hệ trên:
1:[CC 01,AC 212,PN] [STR CT, NYC ZIP, ]
Sự khác nhau giữa phụ thuộc hàm, phụ thuộc hàm xấp xỉ và phụ thuộc hàm điều kiện nằm ở mức độ thỏa mãn Phụ thuộc hàm yêu cầu mối quan hệ X Y phải được thỏa mãn bởi tất cả các bộ dữ liệu, trong khi phụ thuộc hàm xấp xỉ cho phép một tỷ lệ nhỏ các bộ vi phạm Đối với phụ thuộc hàm điều kiện, ký hiệu (X Y | S) cho thấy sự thỏa mãn chỉ cần áp dụng cho các bộ dữ liệu phù hợp với bảng S Ngoài ra, phụ thuộc hàm là một trường hợp đặc biệt của phụ thuộc hàm điều kiện.
S chứa duy nhất một bộ toàn giá trị '-' Cũng giống như các phụ thuộc hàm, phụ thuộc hàm điều kiện cũng có thể được thỏa mãn xấp xỉ [26]
Phát hiện phụ thuộc hàm điều kiện gặp nhiều khó khăn do hai yếu tố chính Đầu tiên, số lượng phụ thuộc hàm nhúng cần kiểm tra cho các phụ thuộc hàm điều kiện có thể tăng lên theo hàm mũ dựa trên số thuộc tính Thứ hai, bài toán xác định bảng mẫu tối ưu cho một phụ thuộc hàm nhúng được phân loại là NP-C.
Một thuật toán được đề xuất trong nghiên cứu nhằm phát hiện các phụ thuộc hàm điều kiện, với các phụ thuộc hàm ứng viên được lấy từ dàn thuộc tính Thuật toán này dựa vào các tính chất của phân hoạch thuộc tính, trong đó mọi bộ trong một lớp tương đương của phân hoạch có cùng giá trị Nếu một lớp tương đương trong phân hoạch này bằng với lớp tương đương trong phân hoạch khác, thì các bộ của lớp đó cũng sẽ có cùng giá trị trên thuộc tính tương ứng.
Trong một phụ thuộc hàm ứng viên X A, vế trái X được phân chia thành hai tập con Q và W, trong đó Q là tập điều kiện và W là tập biến Thuật toán thực hiện phân hoạch cho các tập Q, X và XA, sau đó tiến hành tính toán để thu được một tập kết quả.
U chứa tất cả các lớp tương đương trong X X, với điều kiện có ít nhất l bộ và được chứa trong một lớp tương đương nào đó của XA Một bộ mẫu trong bảng S của phụ thuộc hàm có điều kiện được phát hiện nếu tồn tại một lớp tương đương z trong Q, sao cho các bộ trong z được chứa trong U Nếu z không phải là một lớp tương đương trong XA, bộ mẫu là X z Q[ ], | ; ngược lại, bộ mẫu là z Q[ ], | [ ] z A.
Bảng 1.7 Minh họa phụ thuộc hàm điều kiện Xét bảng 1.7 và một phụ thuộc hàm ứng viên NBS với X NB và
và U X {{ , }}t t 2 3 Xét lớp tương đương thứ hai z {t ,t } 2 3 trong N ta thấy các bộ của z đều nằm trong U và X z NBS nên bộ mẫu được phát hiện là john, | 1 e
Một thuật toán xấp xỉ (dùng chiến lược tham lam) được đề xuất trong
Để tính một bảng mẫu gần tối ưu cho phụ thuộc hàm điều kiện với phụ thuộc hàm nhúng đã cho, tính chất gần tối ưu được xác định dựa trên hai tham số: độ hỗ trợ và độ tin cậy Với phụ thuộc hàm nhúng X → Y, thuật toán xem xét tất cả các tổ hợp giá trị có thể trong t X[] để tạo ra các mẫu ứng viên, dẫn đến số lượng mẫu ứng viên là hàm mũ theo X: r X[] 2 X Đối với mỗi mẫu ứng viên, thuật toán tính toán độ hỗ trợ và độ tin cậy, sau đó lựa chọn các mẫu có độ hỗ trợ cao nhất vượt ngưỡng hỗ trợ để đưa vào bảng Quy trình này yêu cầu độ phức tạp thời gian là r 2 X.
Công trình [32] đề xuất ba thuật toán CFDMiner, CTANE và FastCFD
Các thuật toán FD_Miner, TANE và FastFD được áp dụng trong việc phát hiện các phụ thuộc hàm CFDMiner chuyên phát hiện các phụ thuộc hàm điều kiện hằng, trong khi CTANE và FastCFD tập trung vào việc phát hiện phụ thuộc hàm điều kiện tổng quát.
Tổng kết chương 1
Trong chương này, chúng ta đã ôn lại các khái niệm quan trọng trong mô hình dữ liệu quan hệ, đặc biệt là các khái niệm liên quan đến phụ thuộc hàm Chúng ta đã trình bày một số loại phụ thuộc hàm suy rộng và xem xét tổng quan các phương pháp phát hiện phụ thuộc hàm, bao gồm phụ thuộc hàm xấp xỉ và phụ thuộc hàm điều kiện trong cơ sở dữ liệu quan hệ.
Phát hiện phụ thuộc dữ liệu là một bài toán có không gian tìm kiếm theo hàm mũ liên quan đến số thuộc tính trong cơ sở dữ liệu Một lợi thế là phần lớn dữ liệu thường tuân theo các phụ thuộc hàm, và nhiều phụ thuộc hàm có thể được xấp xỉ bằng một hoặc một vài thuộc tính ở vế trái Đã có một số thuật toán hiệu quả được đề xuất để giải quyết vấn đề này.
Trong việc phát hiện các phụ thuộc hàm, chúng ta bắt đầu từ các phụ thuộc hàm có ít thuộc tính ở vế trái Sau khi phát hiện các phụ thuộc hàm, chúng sẽ được sử dụng để loại bỏ các phụ thuộc hàm ứng viên trong dàn thuộc tính, giúp thu hẹp không gian tìm kiếm Hai phương pháp phổ biến nhất trong quá trình này là phương pháp phân hoạch và phương pháp phủ âm.
Các phương pháp phát hiện phụ thuộc hàm có thể được điều chỉnh để áp dụng cho việc phát hiện các phụ thuộc hàm suy rộng Một cách để cải thiện là bổ sung việc tính toán độ đo lỗi hoặc độ thỏa, giúp phát hiện các phụ thuộc hàm xấp xỉ Bên cạnh đó, phương pháp lấy mẫu cũng có thể được sử dụng để nhận diện các phụ thuộc hàm xấp xỉ một cách hiệu quả.
Trong lĩnh vực phát hiện các phụ thuộc hàm điều kiện, nhiều thuật toán đã được đề xuất Tuy nhiên, việc tìm bảng S tối ưu cho một phụ thuộc hàm điều kiện là bài toán NP-C, làm cho việc tìm kiếm bảng S tốt trở nên khó khăn Vì vậy, việc phát triển các thuật toán đơn giản và hiệu quả hơn là rất cần thiết.
PHỤ THUỘC HÀM XẤP XỈ VÀ PHỤ THUỘC HÀM ĐIỀU KIỆN
Phụ thuộc hàm (FD: Functional Dependency) là trường hợp riêng của tất cả các loại phụ thuộc hàm suy rộng Phụ thuộc hàm xấp xỉ (AFD:
Approximate Functional Dependency) và phụ thuộc hàm điều kiện (CFD:
Phụ thuộc hàm điều kiện (Conditional Functional Dependency - CFD) và phụ thuộc hàm suy rộng (Relaxed Functional Dependency - RFD) là hai loại phụ thuộc hàm quan trọng, thu hút sự chú ý của nhiều nhà nghiên cứu Chương này sẽ giới thiệu tổng quan về FD, AFD và CFD, cùng với một số kết quả nghiên cứu liên quan.
![Vớ dụ 1.4 [42]. Xột quan hệ Phim cho trong bảng 1.2, với X= Tờn phim, = Thời gian. Ta cú X = {{t1, t2}, {t3, t6}, {t4, t5}} - (LUẬN án TIẾN sĩ) phát hiện phụ thuộc hàm và phụ thuộc hàm suy rộng trong cơ sở dữ liệu](https://media.store123doc.com/figures/002/143/vo-du-xot-phim-bang-ton-phim-thoi-2143334.png)
