Mở rộng phụ thuộc hàm phụ thuộc đa trị

Ta.p ch´ı Tin ho. c va` Die`ˆu khieˆ’n ho. c, T.23, S.2 (2007), 121—
MO
.’
ROˆ. NG PHU. THUOˆ. C HA`M VA` PHU. THUOˆ. C DA TRI.
HOˆ` THUA`ˆN1, HOA`NG THI. LAN GIAO
2
1Vieˆ. n Coˆng ngheˆ. thoˆng tin, Vieˆ. n Khoa ho. c va` Coˆng ngheˆ. Vieˆ. t Nam
2Khoa Coˆng Ngheˆ. Thoˆng Tin, Da. i ho. c Khoa ho. c Hueˆ´
Abstract. The aim of the paper is to give a generalization of functional and multivalued dependencies
in an information system. The definitions are established under the assumption that there are some
similarity relations between values of attributes. By using the so-called generalized dependency
matrices we develop a necessary and sufficient condition for an extension dependency to be hold.
Besides, some computational examples are given for illustration too.
To´m ta˘´t. Ba`i ba´o da˜ xaˆy du.. ng ca´c di.nh ngh˜ıa mo
.’ roˆ.ng ve`ˆ phu. thuoˆ.c ha`m va` phu. thuoˆ.c da tri.trong
heˆ. thoˆ´ng thoˆng tin. Ca´c di.nh ngh˜ıa mo´
.i na`y du.o.. c thieˆ´t laˆ.p treˆn co
. so.’ thu`.a nhaˆ.n vieˆ.c toˆ`n ta. i ca´c
quan heˆ. tu
.o.ng tu.. giu˜
.a ca´c gia´ tri. cu’a nhu˜
.ng thuoˆ.c t´ınh. Ba˘`ng ca´ch su
.’ du. ng ca´c ma traˆ. n phu. thuoˆ. c
mo.’ roˆ. ng chu´ng toˆi da ra du
.o.. c moˆ. t die`ˆu kieˆ.n ca`ˆn va` du’deˆ’ moˆ.t phu. thuoˆ.c mo
.’ roˆ.ng thoa’ ma˜n. Moˆ.t
soˆ´ v´ı du. minh hoa. cu˜ng du
.o.. c tr`ınh ba`y trong ba`i ba´o.
1. MO
.’ DA`ˆU
Cho A = (U,A) la` moˆ. t heˆ. thoˆ´ng thoˆng tin vo´
.i U la` taˆ.p ca´c doˆ´i tu
.o.. ng va` A la`taˆ.p ca´c
thuoˆ.c t´ınh. Vo´
.i moˆ˜i u ∈ U va` a ∈ A ta ky´ hieˆ.u u(a) la` gia´ tri. thuoˆ.c t´ınh a cu’a doˆ´i tu
.o.. ng u.
Neˆ´u X ⊆ A la` moˆ. t taˆ.p ca´c thuoˆ.c t´ınh ta ky´ hieˆ.u u(X) la` boˆ. goˆ`m ca´c gia´ tri. u(a) vo´
.i a ∈ X.
Vı` vaˆ.y, neˆ´u u va` v la` hai doˆ´i tu
.o.. ng thuoˆ.c U , ta se˜ no´i u(X) = v(X) neˆ´u u(a) = v(a) vo´
.i mo.i
thuoˆ.c t´ınh a ∈ X .
Nha˘´c la. i ra`˘ng, neˆ´u X, Y la` ca´c taˆ.p thuoˆ.c t´ınh, th`ı Y du
.o.. c go. i la` phu. thuoˆ.c ha`m va`o X
treˆn U va` ky´ hieˆ.u X → Y neˆ´u
∀u, v ∈ U : u(X) = v(X)⇒ u(Y ) = v(Y ). (1)
Ho.n nu˜.a, ba`˘ng ca´ch da˘. t Z = A \ (X ∪ Y ), ta no´i Y la` phu. thuoˆ.c da tri. va`o X treˆn U va`
ky´ hieˆ.u X →→ Y neˆ´u
∀u, v ∈ U : u(X) = v(X)⇒ ∃t ∈ U :


t(X) = u(X),
t(Y ) = u(Y ),
t(Z) = v(Z).
(2)
Tuy nhieˆn, trong thu.. c teˆ´, co´ nhu˜
.ng phu. thuoˆ.c ha`m va` phu. thuoˆ.c da tri. ma` ca´c da˘’ ng thu´
.c
trong (1) va` (2) khoˆng do`i ho’ i thu.. c su
.
. nghieˆm nga˘. t nh vaˆ.y. Cha˘’ ng ha.n, cho ba’ng du˜
. lieˆ.u
sinh vieˆn, da`o ta.o theo nieˆn cheˆ´, vo´
.i ba thuoˆ.c t´ınh lo´
.p, ho. teˆn, moˆn ho. c. De˜ˆ thaˆ´y thuoˆ.c t´ınh
ho. teˆn la` phu. thuoˆ.c da tri. va`o thuoˆ.c t´ınh lo´
.p, ngh˜ıa la` mo. i sinh vieˆn trong cu`ng moˆ.t lo´
.p se˜
122 HOˆ` THUA`ˆN, HOA`NG THI. LAN GIAO
pha’i ho.c ca´c moˆn nh nhau. Baˆy gio`
., neˆ´u nha` tru.`o.ng da ra moˆ.t soˆ´ ho.c pha`ˆn tu
.
. cho.n, va` vo´
.i
moˆ˜i ho.c pha`ˆn nh vaˆ.y ca´c sinh vieˆn trong moˆ.t lo´
.p co´ theˆ’ ho.c ca´c moˆn kha´c nhau (nhng du
.o.. c
xem la` Tu.o.ng du.o.ng), th`ı chu´ng ta vaˆ˜n co´ ly´ do deˆ’ no´i ra`˘ng thuoˆ.c t´ınh ho. teˆn phu. thuoˆ.c da
tri. va`o thuoˆ.c t´ınh lo´
.p, ma˘.c du` lu´c na`y die`ˆu kieˆ.n (2) khoˆng co`n du´ng nu˜
.a. Ro˜ra`ng la` trong
tru.`o.ng ho.. p na`y ca´c di.nh ngh˜ıa nh treˆn khoˆng co`n phu` ho
.
. p. Ma˘.t kha´c, trong thu
.
. c teˆ´ khoˆng
hieˆ´m khi nhu˜.ng du˜. lieˆ.u thu nhaˆ.n du
.o.. c khoˆng co`n ch´ınh xa´c nh voˆ´n co´. Die`ˆu na`y cha˘´c cha˘´n
cu˜ng la`m cho chu´ng ta khoˆng pha´t hieˆ.n heˆ´t mo. i phu. thuoˆ.c tu`
. co. so.’ du˜. lieˆ.u.
Deˆ’ go´p pha`ˆn pha´t hieˆ.n ca´c phu. thuoˆ.c tie`ˆm aˆ’n trong du˜
. lieˆ.u, trong ba`i na`y chu´ng toˆi se˜
coˆ´ga˘´ng da ra moˆ.t ca´ch tieˆ´p caˆ.n mo
.’ roˆ.ng cu’a ca´c kha´i nieˆ.m phu. thuoˆ.c ha`m va` phu. thuoˆ.c da
tri.. Ca´c kha´i nieˆ.m mo
.’ roˆ.ng na`y du
.o.. c thieˆ´t laˆ.p du
.
. a treˆn moˆ.t ha`m da´nh gia´ doˆ. Tu
.o.ng tu.. giu˜
.a
ca´c gia´ tri. trong ba’ng du˜
. lieˆ.u. Khi su
.
. Tu
.o.ng tu.. giu˜
.a hai gia´ tri. da.t deˆ´n moˆ.t mu´
.c doˆ. nhaˆ´t
di.nh, chu´ng ta co´ theˆ’ xem hai gia´ tri. na`y la` “doˆ`ng nhaˆ´t”. Vo´
.i ca´ch tieˆ´p caˆ.n na`y, ca´c phu.
thuoˆ.c thu
.
. c ra la` phu. thuoˆ.c xaˆ´p xı’. Deˆ’ kieˆ’m chu´
.ng moˆ.t phu. thuoˆ.c xaˆ´p xı’ na`o do´, chu´ng toˆi
cu˜ng se˜ su.’ du. ng moˆ.t ma traˆ.n Tu
.o.ng tu.. ma traˆ. n phu. thuoˆ. c du
.o.. c su
.’ du. ng trong [?].
2. CA´C KHA´I NIEˆ.M
Cho heˆ. thoˆ´ng thoˆng tin A = (U,A). Vo´
.i moˆ˜i V ⊆ U va` X ⊆ A, ta go. i mie`ˆn gia´ tri. cu’a
V treˆn X la` taˆ.p ho
.
. p
dom(V,X) := {u(X) | u ∈ V }.
Khi V = U ta vieˆ´t dom(X) thay cho dom(U,X) va` ho.n nu˜.a, neˆ´u X = {a}, ta chı’vieˆ´t moˆ. t
ca´ch do.n gia’n: Va = dom({a}).
Deˆ’ mo.’ roˆ.ng ca´c kha´i nieˆ.m phu. thuoˆ.c, treˆn ca´c taˆ.p gia´ tri. Va, ngoa`i quan heˆ. ba`˘ng nhau
thoˆng tho`.ng ta gia’ di.nh la` toˆ`n ta. i moˆ.t ha`m Tu
.o.ng tu.. , pha’n a´nh doˆ. ga`ˆn nhau giu˜
.a ca´c gia´
tri.. Moˆ.t ca´ch ch´ınh xa´c, moˆ. t a´nh xa. s : Va × Va → [0, 1] du
.o.. c go. i la` ha`m tu
.o.ng tu.. treˆn taˆ.p
Va neˆ´u hai die`ˆu kieˆ.n sau tho’a ma˜n:
1. s(a1, a2) = s(a2, a1), vo´.i mo. i a1, a2 ∈ Va,
2. s(a1, a2) = 1⇔ a1 = a2.
s(a1, a2) du.o.. c go. i la` mu´
.c tu.o.ng tu.. giu˜
.a hai gia´ tri. a1 va` a2. Cho α ∈ [0, 1], hai gia´ tri. a1 va`
a2 du.o.. c go. i la` α−tu
.o.ng tu.. , va` ky´ hieˆ.u a1 =α a2, neˆ´u s(a1, a2) 
 α. Ro˜ ra`ng khi ha`m s chı’
nhaˆ.n hai gia´ tri. 0 va` 1, th`ı, vo´
.i mo.i α > 0, a1 =α a2 khi va` chı’ khi a1 = a2.
Cho taˆ.p thuoˆ.c t´ınh B = {b1, b2, · · · , bm} ⊆ A va` β, γ ∈ dom(B). Khi do´ β va` γ co´ theˆ’
xem la` hai da˜y (βi)i va`(γi)i, vo´.i βi, γi ∈ dom(bi), 1  i  m. Doˆ. tu
.o.ng tu.. giu˜
.a β va` γ du.o.. c
di.nh ngh˜ıa la` gia´ tri.:
S(β, γ) = min{s(βi, γi) | 1  i  m}. (3)
Baˆy gio`., gia’ su.’ γ ∈ dom(B) va` D ⊆ dom(B), ta go. i doˆ. thuoˆ.c cu’a γ va`o D la` doˆ. tu
.o.ng
tu.. lo´
.n nhaˆ´t giu˜.a γ vo´.i ca´c gia´ tri. trong D. Cu. theˆ’, gia´ tri. na`y du
.o.. c xa´c di.nh bo
.’ i:
b(γ,D) = max
β∈D
S(γ, β).
Moˆ.t ca´ch tu
.
. nhieˆn, ta tieˆ´p tu. c du`ng ky´ hieˆ.u β =α γ neˆ´u S(β, γ) 
 α va` no´i ra`˘ng β va`
γ la` α−tu.o.ng tu.. . Cu˜ng vaˆ.y, ta no´i γ thuoˆ.c va`o taˆ.p D vo´
.i mu´.c α, va` ky´ hieˆ.u γ ∈α D, neˆ´u
MO
.’ ROˆ. NG PHU. THUOˆ. C HA`M VA` PHU. THUOˆ. C DA TRI. 123
b(γ,D) 
 α. Meˆ.nh de`ˆ du
.´o.i daˆy cho ta moˆ.t soˆ´ t´ınh chaˆ´t co
. ba’n cu’a ca´c kha´i nieˆ.m na`y ma`vieˆ.c
chu´.ng minh co´ theˆ’ suy ra tru.. c tieˆ´p tu`
. di.nh ngh˜ıa.
Meˆ.nh de`ˆ 2.1. Cho B ⊆ A, D ⊆ dom(B), β, γ ∈ dom(B), ta co´
1. S(β, γ) = S(γ, β); S(β, γ) = 1⇔ β = γ.
2. 0  b(γ,D)  1; b(γ,D) = 1⇔ γ ∈ D.
3. Neˆ´u D ⊆ D′ ⊆ dom(B), th`ı b(γ,D)  b(γ,D′).
4. γ ∈α D ⇔ ∃β ∈ D, γ =α β.
Vı´ du. 2.1. Xe´t heˆ. thoˆ´ng vo´
.i ba thuoˆ.c t´ınh: a (teˆn laˆ.p tr`ınh vieˆn), b (tr`ınh doˆ. chuyeˆn moˆn),
c (ngoˆn ngu˜. laˆ.p tr`ınh su
.’ du. ng) du
.o.. c cho trong Ba’ng 1.
Ba’ng 1
a b c
A Bc PASCAL
A Bc FORTRAN
A Bc COBOL
A Dip PASCAL
A Dip C
A Dip FORTRAN
A Ms COBOL
A Ms PASCAL
B Bc C
B Bc PASCAL
Gia’ su.’ ha`m tu.o.ng tu.. giu˜
.a nhu˜.ng gia´ tri. trong tu`
.ng thuoˆ.c t´ınh du
.o.. c cho bo
.’ i ca´c ba’ng sau
Ba’ng 2. Ha`m tu.o.ng tu.. treˆn Vb
b Bc Dip Ms
Bc 1 0.6 0.8
Dip 0.6 1 0.3
Ms 0.8 0.3 1
Ba’ng 3. Ha`m tu.o.ng tu.. treˆn Vc
c FORTRAN COBOL PASCAL C
FORTRAN 1 0.9 0.7 0.8
COBOL 0.9 1 0.7 0.6
PASCAL 0.7 0.7 1 0.8
C 0.8 0.6 0.6 1
Da˘.t B = {b, c}, β = (Bc, FOTRAN), γ = (Ms,COBOL) ∈ dom(B), ta co´
S(β, γ) = min{s(Bc,Ms), s(FORTRAN,COBOL)} = min{0.8, 0.9} = 0.8.
124 HOˆ` THUA`ˆN, HOA`NG THI. LAN GIAO
Ma˘.t kha´c, vo´
.i D = {Bc,Dip} ⊆ dom(b) va` Ms ∈ dom(b), ta co´
b(Ms,D) = max{s(Ms,Bc), s(Ms,Dip)} = max{0.8, 0.3} = 0.8.
Nhu. vaˆ.y, β =0.8 γ va` Ms ∈0.8 D.
3. PHU. THUOˆ. C MO
.’ ROˆ. NG VA` CA´C TI´NH CHA´ˆT
Du.. a treˆn quan heˆ. α−tu
.o.ng tu.. treˆn ca´c taˆ.p gia´ tri., chu´ng ta se˜ da ra ca´c kha´i nieˆ.m phu.
thuoˆ.c ha`m va` phu. thuoˆ.c da tri. mo
.’ roˆ.ng. Moˆ.t ca´ch ch´ınh xa´c, chu´ng ta co´ ca´c di.nh ngh˜ıa sau.
Di.nh ngh˜ıa 3.1. Cho X, Y ⊆ A va` α ∈ [0, 1]. Ta no´i Y α−phu. thuoˆ.c ha`m va`o X treˆn U va`
ky´ hieˆ.u X →α Y neˆ´u
∀u, v ∈ U : u(X) = v(X)⇒ u(Y ) =α v(Y ).
Khi α = 1 ta nhaˆ.n du
.o.. c di.nh ngh˜ıa phu. thuoˆ.c ha`m nguyeˆn thu’y.
Di.nh ngh˜ıa 3.2. Cho X, Y ⊆ A va` α ∈ [0, 1]. Da˘. t Z = A \ (X ∪ Y ). Ta no´i Y la` α−phu.
thuoˆ.c da tri. va`o X treˆn U , va` ky´ hieˆ.u X →→α Y , neˆ´u vo´
.i mo. i ca˘.p doˆ´i tu
.o.. ng u, v ∈ U sao
cho u(X) = v(X) = x, toˆ`n ta. i doˆ´i tu
.o.. ng t ∈ U sao cho t(X) = x, doˆ`ng tho`
.i tho’a ma˜n moˆ.t
trong hai die`ˆu kieˆ.n sau:
1. t(Y ) = u(Y ) va` t(Z) =α v(Z),
2. t(Y ) =α u(Y ) va` t(Z) = v(Z).
Ro˜ ra`ng, khi α = 1 hai die`ˆu kieˆ.n treˆn tu
.o.ng du.o.ng va` cu˜ng tu.o.ng du.o.ng vo´.i (2), neˆn ta
cu˜ng nhaˆ.n du
.o.. c kha´i nieˆ.m phu. thuoˆ.c da tri. nguyeˆn thuy’. Tu`
. ca´c di.nh ngh˜ıa mo
.’ roˆ.ng treˆn
de˜ˆ kieˆ’m tra du.o.. c ra`˘ng, neˆ´u 0  β  α  1, th`ı X →α Y (X →→α Y ) ke´o theo X →β Y
(X →→β Y ). Ngoa`i ra, moˆ. t soˆ´ t´ınh chaˆ´t cu’a phu. thuoˆ.c ha`m va` phu. thuoˆ.c da tri. vaˆ˜n co`n
du´ng doˆ´i vo´.i ca´c phu. thuoˆ.c mo
.’ roˆ.ng. Die`ˆu do´ du
.o.. c kha˘’ ng di.nh trong meˆ.nh de`ˆ du
.´o.i daˆy
Meˆ.nh de`ˆ 3.1. Cho X,Y,Z ⊆ A, α ∈ [0, 1]. Khi do´
1. Neˆ´u Y ⊆ X th`ı X →α Y.
2. Neˆ´u X →α Y th`ı X ∪ Z →α Y ∪ Z.
3. Neˆ´u X →→α Y th`ı X →→α A \ (X ∪ Y ).
4. Neˆ´u X →α Y th`ı X →→α Y.
Chu´.ng minh.
1) Hieˆ’n nhieˆn du´ng v`ı ta da˜ bieˆ´t, neˆ´u Y ⊆ X th`ı X →1 Y.
2) Vo´.i mo. i ca˘.p doˆ´i tu
.o.. ng u, v ∈ U neˆ´u u(X ∪Z) = v(X ∪Z) th`ı u(Z) = v(Z) va`u(X) =
v(X). V`ı X →α Y neˆn u(Y ) =α v(Y ). Do do´ u(Y ∪Z) =α v(Y ∪Z). Vaˆ.y X ∪Z →α Y ∪Z.
3) Khoˆng maˆ´t t´ınh toˆ’ng qua´t, gia’ su.’ X ∩ Y = ∅. Khi do´, da˘.t Z = A \ (X ∪ Y ), th`ı
Y = A\ (X ∪Z). Tu`.X →→α Y suy ra vo´.i mo. i ca˘.p doˆ´i tu
.o.. ng u, v ∈ U ma` u(X) = v(X) = x
th`ı toˆ`n ta. i doˆ´i tu
.o.. ng t ∈ U sao cho t(X) = x va` t(Y ) = u(Y ), t(Z) =α v(Z) hoa˘.c t(Y ) =α
u(Y ), t(Z) = v(Z). Do do´ X →→α Z.
MO
.’ ROˆ. NG PHU. THUOˆ. C HA`M VA` PHU. THUOˆ. C DA TRI. 125
4) Da˘.t Z = A \ (X ∪ Y ). Do X →α Y neˆn vo´
.i mo. i ca˘.p doˆ´i tu
.o.. ng u, v ∈ U ma` u(X) =
v(X) = x ta co´ v(Y ) =α u(Y ). Ba`˘ng ca´ch cho.n t = v ta nhaˆ.n du
.o.. c t(X) = x, t(Z) = v(Z)
va` t(Y ) =α u(Y ). Vaˆ.y X →→α Y . 

Vı´ du. 3.1. Xe´t heˆ. thoˆ´ng A = (U, {X,Y,Z}) du
.o.. c cho trong Ba’ng 4, ca´c ha`m tu
.o.ng tu.. treˆn
VY va` VZ du
.o.. c cho treˆn Ba’ng 5.
Khi do´, de˜ˆ thaˆ´y X →→0.8 Y . Nhng X →/→0.9 Y v`ı co´ hai doˆ´i tu.o.. ng t4 va`t5 cu`ng ba`˘ng
x1 treˆn thuoˆ.c t´ınh X , ma˘.t kha´c t4(Y ) = β1 va`t5(Z) = γ3, nhng khoˆng co´ doˆ´i tu
.
. o
.ng v na`o
ma` v(X) = x1 doˆ`ng tho`.i thoa’ ma˜n (v(Y ) = β1 va` v(Z) =0.9 γ3) hoa˘.c (v(Y ) =0.9 β1 va`
v(Z) = γ3).
Ba’ng 4 Ba’ng 5. Ca´c ha`m tu.o.ng tu.. treˆn VY va` VZ
U X Y Z
t1 x1 β1 γ1
t2 x1 β2 γ1
t3 x1 β3 γ2
t4 x1 β1 γ2
t5 x1 β3 γ3
t6 x1 β2 γ3
t7 x2 β1 γ1
t8 x2 β1 γ2
Y β1 β2 β3
β1 1 0.5 0.7
β2 05 1 0.9
β3 0.7 0.9 1
Z γ1 γ2 γ3
γ1 1 0.6 0.7
γ2 06 1 0.8
γ3 0.7 0.8 1
4. KIEˆ’M TRA β - PHU. THUOˆ. C DA TRI.
4.1. Die`ˆu kieˆ.n toˆ`n ta. i - phu. thuoˆ.c da tri.
Trong moˆ.t ba`i ba´o tro´
.c [?], deˆ’ nghieˆn cu´.u phu. thuoˆ.c da tri., ca´c ta´c gia’ da˜ thieˆ´t laˆ.p ma
traˆ. n phu. thuoˆ. c du
.
. a va`o phaˆn hoa.ch treˆn ca´c gia´ tri. thuoˆ.c t´ınh va` da˜ chu´
.ng minh du.o.. c ra`˘ng,
X →→ Y du´ng khi va` chı’ khi ma traˆ. n phu. thuoˆ. c la` da`ˆy da˘. c, tu´
.c la`mo. i pha`ˆn tu
.’ cu’a ma traˆ.n
de`ˆu co´ gia´ tri. 1. Trong tru
.`o.ng ho.. p ma traˆ.n phu. thuoˆ.c la` ga`ˆn da˘. c (tu´
.c la` chu´.a pha`ˆn lo´.n ca´c
soˆ´ 1), th`ı ta cu˜ng nhaˆ.n du
.o.. c moˆ.t phu. thuoˆ.c da tri. xaˆ´p xı’(tu´
.c la` bo’ di moˆ.t soˆ´ ı´t boˆ. na`o do´ cu’a
ba’ng du˜. lieˆ.u th`ı nhaˆ.n du
.o.. c phu. thuoˆ.c du´ng). Treˆn co
. so.’ ca´c keˆ´t qua’ na`y, moˆ. t thuaˆ.t toa´n
kieˆ’m chu´.ng phu. thuoˆ.c va` phu. thuoˆ.c xaˆ´p xı’ du
.
. a va`o ma traˆ.n phu. thuoˆ.c cu˜ng da˜ du
.o.. c thieˆ´t
laˆ.p. Pha´t trieˆ’n y´ to
.’ ng do´, o.’ daˆy chu´ng ta se˜ xaˆy du.. ng moˆ.t ma traˆ.n co´ vai tro` tu
.o.ng tu.. trong
vieˆ.c xa´c di.nh α−phu. thuoˆ.c da tri..
Treˆn U ta xa´c di.nh quan heˆ. IND(X) xa´c di.nh bo
.’ i
u IND(X)v ⇔ u(X) = v(X); u, v ∈ U.
De˜ˆ kieˆ’m chu´.ng du.o.. c ra`˘ng IND(X) la` moˆ. t quan heˆ. tu
.o.ng du.o.ng treˆn U . Ta ky´ hieˆ.u ho. ca´c lo´
.p
tu.o.ng du.o.ng cu’a U theo quan heˆ. na`y bo
.’ i [X] = {X1, · · · ,Xm}. Ro˜ ra`ng, Y →→α Z du´ng treˆn
U khi va` chı’ khi Y →→α Z du´ng treˆn mo. i Xi. Do do´, o
.’ daˆy ta chı’ ha.n cheˆ´ vieˆ.c kieˆ’m tra phu.
thuoˆ.c treˆn moˆ˜i Xi coˆ´ di.nh. Ky´ hieˆ.u Z = A \ (X ∪ Y ). Gia’ su
.’ dom(Xi, Y ) = {β1, β2, · · · , βp}
va` dom(Xi, Z) = {γ1, γ2, · · · , γq}. Vo´.i moˆ˜i βj , γk ta ky´ hieˆ.u
Ej := {t(Z) | t ∈ Xi; t(Y ) = βj} ⊆ dom(Z);
Fk := {t(Y ) | t ∈ Xi; t(Z) = γk} ⊆ dom(Y ).
126 HOˆ` THUA`ˆN, HOA`NG THI. LAN GIAO
Ta go.i ma traˆ. n phu. thuoˆ. c mo
.’ roˆ. ng, tu
.o.ng u´.ng vo´.i lo´.p Xi, la` D
i = (djk)p×q, vo´
.i ca´c tha`nh
pha`ˆn djk du
.o.. c xa´c di.nh bo
.’ i:
djk := max{b(βj , Fk), b(γk, Ej)}.
Ma traˆ.n D
i du.o.. c go. i la` α−da`ˆy da˘.c neˆ´u vo´
.i mo. i j, k ta de`ˆu co´ djk 
 α, hay, moˆ. t ca´ch tu
.o.ng
du.o.ng: hoa˘.c βj ∈α Fk hoa˘.c γk ∈α Ej .
tu.o.ng tu.. nh phu. thuoˆ.c da tri. nguyeˆn thu’y, α−phu. thuoˆ.c da tri. cu˜ng co´ theˆ’ du
.o.. c da˘.c
tru.ng hoa`n toa`n ba`˘ng ho. ca´c ma traˆ.n phu. thuoˆ.c mo
.’ roˆ.ng D
i. Die`ˆu do´ du.o.. c kha˘’ ng di.nh trong
di.nh ly´ sau.
Di.nh ly´ 4.1. Y la` α−phu. thuoˆ. c da tri. va`o X khi va` chı’ khi D
i la`α−da`ˆy da˘. c, vo´
.i mo. i
1  i  m.
Chu´.ng minh. Gia’ su.’ X →→α Y . Chu´ng ta se˜ chu´.ng minh mo. i D
i de`ˆu la` ma traˆ.n α−da`ˆy
da˘.c. Thaˆ. t vaˆ.y, vo´
.i mo. i 1  j  p va` 1  k  q, toˆ`n ta. i hai doˆ´i tu
.o.. ng u, v ∈ Xi sao cho
u(Y ) = βj va` v(Z) = γk. V`ı u va`v cu`ng thuoˆ.c lo´
.p Xi neˆn u(X) = v(X). Theo di.nh ngh˜ıa
cu’a α−phu. thuoˆ.c da tri., toˆ`n ta. i boˆ. t ∈ Xi thoa’ ma˜n moˆ.t trong hai die`ˆu kieˆ.n sau
1. t(Y ) = u(Y ) = βj va` t(Z) =α v(Z) = γk,
2. t(Y ) =α u(Y ) = βj va` t(Z) = v(Z) = γk.
Neˆ´u tru.`o.ng ho.. p a) xa˜y ra th`ı t(Z) ∈ Ej va` γk =α t(Z). Do do´, b(γk, Ej) 
 α. Tu
.o.ng tu.. ,
neˆ´u b) xa˜y ra th`ı b(βj, Fk) 
 α. Ca’ hai tru
.`o.ng ho.. p do´ de`ˆu daˆ˜n deˆ´n djk 
 α. Vı` die`ˆu na`y
du´ng vo´.i mo. i djk neˆn D
i la` ma traˆ.n α−da`ˆy da˘.c.
Ngu.o.. c la. i, gia’ su
.’ mo. i D
i de`ˆu la` ma traˆ.n α− da`ˆy da˘.c. Cho hai doˆ´i tu
.o.. ng tuy` y´u, v ∈ U
thoa’ ma˜n u(X) = v(X). Lu´c do´, u va` v pha’i thuoˆ.c cu`ng moˆ.t lo´
.p tu.o.ng du.o.ng Xi na`o do´.
Da˘.t βj = u(Y ) va` γk = v(Z). Do djk 
 α neˆn ta co´
1. hoa˘.c b(βj , Fk) 
 α,
2. hoa˘.c b(γk, Ej) 
 α.
Neˆ´u i) du´ng th`ı toˆ`n ta. i t ∈ Xi sao cho t(Z) = γk = v(Z) va` t(Y ) =α βj = u(Y ), co`n neˆ´u
ii) du´ng th`ı toˆ`n ta. i t ∈ Xi sao cho t(Y ) = βj = u(Y ) va` t(Z) =α γk = v(Z). Trong ca’ hai
tru.`o.ng ho.. p, t de`ˆu thoa’ ma˜n die`ˆu kieˆ.n cu’a Di.nh ngh˜ıa ??. Vaˆ.y X →→α Y va` di.nh ly´ da˜ du
.o.. c
chu´.ng minh. 

Vı´ du. 4.1. Xe´t la. i heˆ. thoˆ´ng cho trong V´ı du. ??. Ho. ca´c lo´
.p tu.o.ng du.o.ng theo quan
heˆ.IND(X) la` [X] = {X1,X2}, vo´
.i X1 = {t1, t2, t3, t4, t5, t6} va`X2 = {t7, t8}.
Treˆn lo´.p X1 ta co´ dom(X1, Y ) = {β1, β2, β3}, dom(X1, Z) = {γ1, γ2, γ3} va`
E1 = {t(Z) | t ∈ X1, t(Y ) = β1} = {γ1, γ2};
E2 = {t(Z) | t ∈ X1, t(Y ) = β2} = {γ1, γ3};
E3 = {t(Z) | t ∈ X1, t(Y ) = β3} = {γ2, γ3};
F1 = {t(Y ) | t ∈ X1, t(Z) = γ1} = {β1, β2};
F2 = {t(Y ) | t ∈ X1, t(Z) = γ2} = {β1, β3};
F3 = {t(Y ) | t ∈ X1, t(Z) = γ3} = {β2, β3}.
Tu`. do´ ca´c pha`ˆn tu.’ cu’a ma traˆ.n D
1 du.o.. c xa´c di.nh bo
.’ i:
MO
.’ ROˆ. NG PHU. THUOˆ. C HA`M VA` PHU. THUOˆ. C DA TRI. 127
d11 = max{b(β1, F1), b(γ1, E1)} = max{1; 1} = 1;
d12 = max{b(β1, F2), b(γ2, E1)} = max{1; 1} = 1;
d13 = max{b(β1, F3), b(γ3, E1)} = max{0.7; 0.8} = 0.8;
d21 = max{b(β2, F1), b(γ1, E2)} = max{1; 1} = 1;
d22 = max{b(β2, F2), b(γ2, E2)} = max{0.9; 0.8} = 0.9;
d23 = max{b(β2, F3), b(γ3, E2)} = max{1; 1} = 1;
d31 = max{b(β3, F1), b(γ1, E3)} = max{0.9; 0.7} = 0.9;
d32 = max{b(β3, F2), b(γ2, E3)} = max{1; 1} = 1;
d33 = max{b(β3, F3), b(γ3, E3)} = max{1; 1} = 1.
Tu.o.ng tu.. , treˆn lo´
.p X2 ta co´ dom(X2, Y ) = {β1}, dom(X2, Z) = {γ1, γ2} va` ba`˘ng t´ınh
toa´n do.n gia’n ta thu du.o.. c ca´c pha`ˆn tu
.’ cu’a ma traˆ.n D
2 la`d11 = d12 = 1. To´m la. i, ta du
.o.. c
D1 =

 1 1 0.81 0.9 1
0.9 1 1

 , D2 = ( 1 1 ) .
Ro˜ ra`ng vo´.i α  0.8 th`ı ca’ hai ma traˆ.n D
1 va` D2 de`ˆu α−da`ˆy da˘.c. Do do´ X →→α Y , vo´
.i
mo. i α  0.8. Trong khi do´, neˆ´u α > 0.8 th`ı D
1 khoˆng α−da`ˆy da˘.c neˆn X →/→α Y .
TA`I LIEˆ. U THAM KHA
’O
[1] David Maier, The Theory of Relational Databases (Computer Science Press, Rockville,
Maryland, 1983).
[2] Jeffrey D. Ullman, Principles of Database and Knowledge-Base Systems, Volume I (Com-
puter Science Press, Rockville, Maryland, 1988).
[3] Hoa`ng Thi. Lan Giao, Hoˆ` Thua`ˆn, “Kha´m pha´ phu. thuoˆ.c da tri. du
.
. a va`o ma traˆ.n phu.
thuoˆ.c“, Tin ho. c va` die`ˆu khieˆ’n (2006).
[4] Hoˆ` Thua`ˆn, “Contribution to the theory of relational databases“, Tanulmanyok 184/1986,
Studies 184/1986. Budapest, Hungary.
[5] Iztok Savnik and Peter A. Flash, “Discovery of multivalued dependencies from ralations“
Intelligent data Analysis, 4(3,4) 195 - 211, 2000
[6] Mannila, H., Toivonen, H. and Verkamo, A.I. , “Discovery of frequency episodes in event
sequences“ Data Mining and Knowledge Discovery (1997), I, 259 - 289.
[7] Shrabonti Ghosh, Ranjit Biswas, S.S. Alam, “Reduction of the Decision Table: A Rouhg
Approach“, International Journal of Intelligent Systems, Vol 19, 2004.
[8] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen, “Tane: An Efficient
Algorithm for Discovering Functional and Approximate Dependencies“ The Computer
Journal, Vol 42, No 2. 1999.
[9] Yka Huhtala, Juha Karkkainen, Pasi Porkka and Hannu Toivonen, “Efficient Discovery
of Functional and Approximate Dependencies using Partitions“ In Proc, 14th Int. Conf.
on Data Engineering, IFFE Computer Society Press (’98).
Nhaˆ. n ba`i nga`y 5 - 6 - 2006