Thuật toán tìm tất cả các rút gọn trong bảng quyết định

T¤p ch½ Tin håc v  ffii·u khiºn håc, T.27, S.3(2011), 199205
THUŁT TON TœM T‡T Cƒ CC RÓT GÅN TRONG BƒNG QUY˜T ffiÀNH
∗
NGUY™N LONG GIANG, VÔ ffiÙC THI
Vi»n Cæng ngh» thæng tin, Vi»n Khoa håc v  Cæng ngh» Vi»t Nam
Tóm tắt. Rót gån thuëc t½nh l  b i to¡n quan trång trong lþ thuy¸t tªp thæ. Cho ¸n nay, nhi·u
b i b¡o khoa håc v· c¡c thuªt to¡n rót gån thuëc t½nh ¢ ÷ñc · xu§t. Tuy nhi¶n, c¡c thuªt to¡n
n y ·u t¼m mët tªp rót gån tèt nh§t theo mët ti¶u ch½ ¡nh gi¡ n o â. B i b¡o · xu§t mët thuªt
to¡n mîi t¼m t§t c£ c¡c tªp rót gån trong b£ng quy¸t ành v  ¡nh gi¡ thuªt to¡n n y câ ë phùc
t¤p thíi gian l  h m mô. Tuy vªy, trong nhi·u tr÷íng hñp cö thº, thuªt to¡n n y câ ë phùc t¤p l 
a thùc.
Abstract. Attribute reduction is one of the most important issues in rough set theory. There have
been many scientific papers that suppose algorithms on attribute reduction. However, these algorithms
are all heuristic which find the best attribute reduction based on a kind of heuristic information. In
this paper, we present a new algorithm for finding all attribute reductions of a decision and we show
that the time complexity of the algorithm is exponential in the number of attributes. We also show
that this complexity is polynomial in many special cases.
1. MÐ ffi†U
Rót gån thuëc t½nh trong b£ng quy¸t ành l  qu¡ tr¼nh lo¤i bä c¡c thuëc t½nh d÷ thøa
trong tªp thuëc t½nh i·u ki»n m  khæng £nh h÷ðng ¸n vi»c ph¥n lîp c¡c èi t÷ñng. Düa
v o tªp rót gån thu ÷ñc, vi»c sinh luªt v  ph¥n lîp ¤t hi»u qu£ cao nh§t. Cho ¸n nay, câ
r§t nhi·u cæng tr¼nh nghi¶n cùu v· c¡c thuªt to¡n rót gån thuëc t½nh trong lþ thuy¸t tªp thæ.
Tuy nhi¶n, c¡c thuªt to¡n n y ·u t¼m ÷ñc mët tªp rót gån tèt nh§t theo mët ti¶u ch½ ¡nh
gi¡ n o â vîi ë phùc t¤p a thùc (c¡c thuªt to¡n theo h÷îng ti¸p cªn heuristic) m  ch÷a
gi£i quy¸t b i to¡n t¼m t§t c£ c¡c tªp rót gån.
Vîi b£ng quy¸t ành nh§t qu¡n DT = (U,C ∪ d, V, f) trong lþ thuy¸t tªp thæ, theo ành
ngh¾a cõa Pawlak n¸u B ⊆ C l  mët rót gån cõa C n¸u B l  tªp tèi thiºu thäa m¢n phö thuëc
h m B → d. Vîi quan h» r tr¶n tªp thuëc t½nh R trong lþ thuy¸t cì sð dú li»u, B l  mët tªp
tèi thiºu cõa thuëc t½nh a ∈ R tr¶n r n¸u B l  tªp thuëc t½nh nhä nh§t thäa m¢n phö thuëc
h m B → a. Do â, n¸u xem b£ng quy¸t ành DT = (U,C ∪ d, V, f) l  quan h» r tr¶n tªp
thuëc t½nh R = C ∪ d th¼ kh¡i ni»m tªp rót gån t÷ìng ÷ìng vîi kh¡i ni»m tªp tèi thiºu cõa
thuëc t½nh {d}. V¼ vªy, b i to¡n t¼m t§t c£ c¡c rót gån trong lþ thuy¸t tªp thæ trð th nh b i
to¡n t¼m hå t§t c£ c¡c tªp tèi thiºu cõa mët thuëc t½nh tr¶n quan h» v  b i to¡n n y ÷ñc
gi£i quy¸t düa tr¶n c¡c k¸t qu£ ¢ chùng minh trong lþ thuy¸t cì sð dú li»u quan h».
∗
Nghi¶n cùu ÷ñc ho n th nh d÷îi sü hé trñ tø Quß ph¡t triºn KHCNQG NAFOSTED, dü ¡n sè 102.01-2010.09
200 NGUY™N LONG GIANG, VÔ ffiÙC THI
B i b¡o n y x¥y düng mët thuªt to¡n t¼m t§t c£ c¡c tªp rót gån trong b£ng quy¸t ành
düa tr¶n c¡c k¸t qu£ ¢ cæng bè cõa gi¡o s÷ J. Demetrovics v  Vô ffiùc Thi trong cì sð dú
li»u quan h» v  chùng minh ë phùc t¤p cõa thuªt to¡n trong tr÷íng hñp x§u nh§t l  h m
mô theo sè thuëc t½nh i·u ki»n, tuy nhi¶n b i b¡o công ch¿ ra trong mët sè tr÷íng hñp °c
bi»t, ë phùc t¤p cõa thuªt to¡n l  a thùc theo k½ch th÷îc cõa b£ng quy¸t ành. Ph¦n cán
l¤i cõa b i b¡o gçm: Möc 2 tr¼nh b y mët sè kh¡i ni»m cì b£n trong cì sð dú li»u quan h» v 
trong lþ thuy¸t tªp thæ; Möc 3 tr¼nh b y mët sè thuªt to¡n cì b£n trong cì sð dú li»u quan
h» trong [5, 10]; Möc 4 · xu§t thuªt to¡n t¼m t§t c£ c¡c rót gån trong b£ng quy¸t ành v  v½
dö minh håa thuªt to¡n; Cuèi còng l  k¸t luªn.
2. CC KHI NI›M CÌ BƒN
2.1. C¡c kh¡i ni»m cì b£n trong cì sð dú li»u quan h»
Ph¦n n y s³ tr¼nh b y mët sè kh¡i ni»m cì b£n trong lþ thuy¸t cì sð dú li»u quan h». C¡c
kh¡i ni»m n y câ thº xem trong [1, 3, 4, 6, 7, 10].
Cho R = {a1, ..., an} l  tªp húu h¤n kh¡c réng c¡c thuëc t½nh, méi thuëc t½nh ai câ mi·n gi¡
trà l  D (ai). Quan h» r tr¶n R l  tªp c¡c bë {h1, ..., hm} vîi hj : R→ ∪
ai∈R
D (ai) , 1 ≤ j ≤ m
l  mët h m sao cho hj (ai) ∈ D (ai).
Cho r = {h1, ..., hm} l  mët quan h» tr¶n R = {a1, ..., an}. Phö thuëc h m (PTH) tr¶n
R l  mët d¢y kþ tü câ d¤ng A → B vîi A,B ⊆ R. PTH A → B thäa m¢n quan h» r
tr¶n R n¸u (∀hi, hj ∈ r) ((∀a ∈ A) (hi (a) = hj (a))⇒ (∀b ∈ B) (hi (b) = hj (b))). ffi°t Fr =
{(A,B) : A,B ⊆ R,A→ B} l  hå ¦y õ c¡c PTH thäa m¢n quan h» r. Gåi P (R) l  tªp c¡c
tªp con cõa R, n¸u F = P (R)× P (R) thäa m¢n:
(1) (A,A) ∈ F
(2) (A,B) ∈ F, (B,C) ∈ F ⇒ (A,C) ∈ F
(3) (A,B) ∈ F,A ⊆ C,D ⊆ B ⇒ (C,D) ∈ F
(4) (A,B) ∈ F, (C,D) ∈ F ⇒ (A ∪ C,B ∪D) ∈ F
th¼ F ÷ñc gåi l  mët hå f tr¶n R. Rã r ng Fr l  mët hå f tr¶n R. Theo [1] n¸u F l  mët
hå f tr¶n R th¼ câ mët quan h» r tr¶n R sao cho Fr = F . Kþ hi»u F
+
l  tªp t§t c£ c¡c PTH
÷ñc d¨n xu§t tø F b¬ng vi»c ¡p döng c¡c quy t­c (1)-(4).
Mët sì ç quan h» (SffiQH) s l  mët c°p vîi R l  tªp thuëc t½nh v  F l  tªp
c¡c phö thuëc h m tr¶n R. Kþ hi»u A+ = {a : A→ {a} ∈ F+} , A+ ÷ñc gåi l  bao âng cõa
A tr¶n s. D¹ th§y A → B ∈ F+ khi v  ch¿ khi B ⊆ A+ . Theo [1], n¸u s = l 
sì ç quan h» th¼ câ quan h» r tr¶n R sao cho Fr = F
+
, quan h» r nh÷ vªy gåi l  quan h»
Armstrong cõa s.
Cho r l  mët quan h», s = l  mët SffiQH v  A ⊆ R. Khi â A l  mët khâa cõa
r (mët khâa cõa s) n¸u A → R (A→ R ∈ F+). A l  mët khâa tèi thiºu cõa r(s) n¸u A l 
mët khâa cõa r(s) v  b§t ký mët tªp con thüc sü n o cõa A khæng ph£i l  khâa cõa r(s). Kþ
hi»u Kr (Ks) l  tªp t§t c£ c¡c khâa tèi thiºu cõa r(s). Gåi K ⊆ P (R) l  mët h» Sperner tr¶n
THUŁT TON TœM T‡T Cƒ CC RÓT GÅN TRONG BƒNG QUY˜T ffiÀNH 201
R n¸u vîi måi A,B ∈ K k²o theo A 6⊂ B, d¹ th§y Kr (Ks) l  c¡c h» Sperner tr¶n R. Cho K
l  mët h» Sperner tr¶n R âng vai trá l  tªp t§t c£ c¡c khâa tèi thiºu. Ta ành ngh¾a tªp c¡c
ph£n khâa cõa K, kþ hi»u l  K−1, nh÷ sau:
K−1 = {A ⊂ R : (B ∈ K)⇒ (B 6⊂ A)} v  n¸u (A ⊂ C)⇒ (∃B ∈ K) (B ⊆ C).
D¹ th§y K−1 công l  mët h» Sperner tr¶n R. Theo ành ngh¾a, n¸u K l  tªp c¡c khâa tèi
thiºu cõa mët SffiQH n o â th¼ K−1 l  tªp t§t c£ c¡c tªp khæng ph£i khâa lîn nh§t.
Cho r l  mët quan h» tr¶nR.ffi°tEr = {Eij : 1 ≤ i < j ≤ |r|} vîiEij = {a ∈ R : hi (a) = hj (a)}
, khi â Er ÷ñc gåi l  h» b¬ng nhau cõa r. Theo [4], n¸u Ar ⊆ R th¼ A+r = ∩Eij n¸u tçn t¤i
Eij ∈ Er : A ⊆ Eij v  A+r = R trong tr÷íng hñp ng÷ñc l¤i. Ti¸p theo, ta ÷a ra ành ngh¾a
hå c¡c tªp tèi thiºu cõa mët thuëc t½nh tr¶n quan h» v  SffiQH.
ffiành ngh¾a 2.1. [6]. Cho s = (R,F ) l  SffiQH tr¶n R v  a ∈ R.
ffi°t Ksa = {A ⊆ R : A→ {a} ,∃B ⊆ R : (B → {a}) (B 6⊂ A)}.
Ksa ÷ñc gåi l  hå c¡c tªp tèi thiºu cõa thuëc t½nh a tr¶n SffiQH.
T÷ìng tü, ta ành ngh¾a hå c¡c tªp tèi thiºu cõa mët thuëc t½nh tr¶n quan h».
ffiành ngh¾a 2.2. Cho r l  mët quan h» tr¶n R v  a ∈ R.
ffi°t Kra = {A ⊆ R : A→ {a} ,∃B ⊆ R : (B → {a}) (B 6⊂ A)}.
Kra ÷ñc gåi l  hå c¡c tªp tèi thiºu cõa thuëc t½nh a tr¶n quan h» r.
Rã r ng R /∈ Ksa, R /∈ Kra, {a} ∈ Ksa, {a} ∈ Kra v  Ksa, Kra l  c¡c h» Sperner tr¶n R.
2.2. C¡c kh¡i ni»m cì b£n trong lþ thuy¸t tªp thæ
Trong ph¦n n y s³ tr¼nh b y mët sè kh¡i ni»m cì b£n trong lþ thuy¸t tªp thæ [9].
B£ng quy¸t ành l  mët bë tù DT = (U,C ∪D,V, f) trong â U = {u1, u2, ..., un} l  tªp
kh¡c réng, húu h¤n c¡c èi t÷ñng; C = {c1, c2, ..., cm} l  tªp c¡c thuëc t½nh i·u ki»n; D l 
tªp c¡c thuëc t½nh quy¸t ành vîi C ∩D = . V = ∏
a∈C∪D
Va vîi Va l  tªp gi¡ trà cõa thuëc
t½nh a ∈ A; f : U × (C ∪D)→ V l  h m thæng tin, vîi ∀a ∈ C ∪D,u ∈ U h m f cho gi¡ trà
f (u, a) ∈ Va. Khæng m§t t½nh ch§t têng qu¡t gi£ thi¸t D ch¿ gçm mët thuëc t½nh quy¸t ành
d duy nh§t (tr÷íng hñp D câ nhi·u thuëc t½nh th¼ b¬ng mët ph²p m¢ hâa câ thº quy v· mët
thuëc t½nh [8]). Do â, tø nay v· sau ta x²t b£ng quy¸t ành DT = (U,C ∪ d, V, f), trong â
{d} /∈ C.
Méi tªp con P ⊆ C ∪ {d} x¡c ành mët quan h» khæng ph¥n bi»t ÷ñc, gåi l  quan h»
t֓ng ֓ng:
IND (P ) = {(x, y) ∈ U × U |∀a ∈ P, f (x, a) = f (y, a)}.
IND(P ) x¡c ành mët ph¥n ho¤ch cõa U , kþ hi»u l  U/P = {P1, P2, ..., Pm}. Mët ph¦n
tû trong U/P gåi l  mët lîp t÷ìng ÷ìng.
Vîi B ⊆ C v  X ⊆ U , B−x§p x¿ tr¶n cõa X l  tªp BX = {u ∈ U |[u]B ∩X 6= ∅}, B−x§p
x¿ d÷îi cõa X l  tªp BX = {u ∈ U |[u]B ⊆ X }, B−mi·n bi¶n cõa X l  tªp BNB (X) =
BX\BX v  B−mi·n d÷ìng cõa {d} l  tªp POSB ({d}) =
⋃
X∈U/D
(BX). B£ng quy¸t ành DT
÷ñc gåi l  nh§t qu¡n khi v  ch¿ khi POSC(d) = U , hay phö thuëc h m C → d óng, ng÷ñc
202 NGUY™N LONG GIANG, VÔ ffiÙC THI
l¤i DT l  khæng nh§t qu¡n. Trong tr÷íng hñp DT khæng nh§t qu¡n th¼ POSC ({d}) ch½nh l 
tªp con cüc ¤i cõa U sao cho phö thuëc h m C → d óng.
Trong lþ thuy¸t tªp thæ [9], Pawlak ÷a ra kh¡i ni»m tªp rót gån cõa b£ng quy¸t ành,
cán gåi l  tªp rót gån düa tr¶n mi·n d÷ìng.
ffiành ngh¾a 2.3. Cho b£ng quy¸t ành DT = (U,C ∪ d, V, f). N¸u B ⊆ C thäa m¢n:
(1)POSB ({d}) = POSC ({d})
(2) ∀B′ ⊂ B (POSB′ ({d}) 6= POSC ({d}))
th¼ B ÷ñc gåi l  mët tªp rót gån cõa C.
Tr÷íng hñp DT nh§t qu¡n, ành ngh¾a tr¶n cho th§y B l  mët tªp rót gån n¸u B thäa m¢n
B → d v  ∀B′ ⊂ B,B′ 6→ {d}, kþ hi»u Rd l  tªp t§t c£ c¡c rót gån cõa DT.
3. MËT SÈ THUŁT TON CÌ BƒN TRONG CÌ SÐ DÚ LI›U QUAN H›
3.1. Thuªt to¡n t¼m tªp ph£n khâa
Thuªt to¡n 3.1. [10] T¼m tªp ph£n khâa K−1
ffi¦u v o: K = {B1, ..., Bn} l  h» Sperner tr¶n R.
ffi¦u ra: K−1
B÷îc 1: ffi°t K1 = {R− {a} : a ∈ B1}. Hiºn nhi¶n K1 = {B1}−1
B÷îc q+1: (q<m). Gi£ thi¸t r¬ng Kq = Fq ∪ {X1, ..., Xtq}, ð ¥y X1, ..., Xtq chùa Bq + 1
v  Fq = {A ∈ Kq : Bq+1 6⊂ A}. ffièi vîi méi i (i = 1, ..., tq) ta t¼m c¡c ph£n khâa cõa Bq + 1
tr¶n Xi t÷ìng tü nh÷ K1. Kþ ph¡p cõa chóng l  A
i
1, ..., A
i
ri. ffi°t:
Kq+1 = Fq ∪
{
Aip : A ∈ Fq ⇒ Aip 6⊂ A, 1 ≤ i ≤ tq, 1 ≤ p ≤ ri
}
Cuèi còng ta °t K−1 = Km
ffië phùc t¤p thuªt to¡n
ffi°t Iq (1 ≤ q ≤ m− 1) l  sè ph¦n tû cõa Kq trong thuªt to¡n tr¶n. Theo [10], ë phùc
t¤p thíi gian cõa thuªt to¡n l  O
(
|R|2
m−1∑
q=1
tquq
)
vîi uq = Iq − tq n¸u Iq > tq v  uq = 1 n¸u
Iq = tq.
Nhªn x²t 3.1
1) Trong méi b÷îc cõa thuªt to¡n, Kq l  h» Sperner tr¶n R. Theo [5], k½ch th÷îc cõa h»
Sperner b§t ký tr¶n R khæng v÷ñt qu¡ C
[n/2]
n ≈ 2n+1/2/
(∏
.n1/2
)
vîi n = |R|. Do â,
ë phùc t¤p tçi nh§t cõa thuªt to¡n l  h m sè mô theo n.
2) Tr÷íng hñp Iq ≤ Im (q = 1, ...,m− 1), ë phùc t¤p cõa thuªt to¡n khæng lîn hìn
O
(
|R|2 |K| ∣∣K−1∣∣2), khi â ë phùc t¤p thuªt to¡n l  a thùc theo |R| , |K| v  |K|−1.
N¸u sè l÷ñng c¡c ph¦n tû cõa K l  nhä th¼ thuªt to¡n r§t hi»u qu£, ái häi thíi gian
a thùc theo |R|.
THUŁT TON TœM T‡T Cƒ CC RÓT GÅN TRONG BƒNG QUY˜T ffiÀNH 203
3.2. Thuªt to¡n t¼m tªp khâa tèi thiºu tø tªp c¡c ph£n khâa
Thuªt to¡n 3.2. [5] T¼m mët khâa tèi thiºu tø tªp c¡c ph£n khâa
ffi¦u v o: Cho K l  h» Sperner âng vai trá l  tªp ph£n khâa, C = {b1, ..., bm} ⊆ R v 
H l  h» Sperner âng vai trá l  tªp khâa
(
K = H−1
)
sao cho ∃B ∈ K : B ⊆ C.
ffi¦u ra: D ∈ H
B÷îc 1: ffi°t T (0) = C;
B÷îc i+1: ffi°t T (i + 1) = T (i) − bi+1 n¸u ∀B ∈ K khæng câ T ⊆ B; trong tr÷íng hñp
ng÷ñc l¤i °t T (i+ 1) = T (i);
Cuèi còng ta °t D = T (m);
Thuªt to¡n 3.3. [5] T¼m tªp c¡c khâa tèi thiºu tø tªp c¡c ph£n khâa
ffi¦u v o: Cho K = {B1, ..., Bk} l  h» Sperner tr¶n R.
ffi¦u ra: H m  H−1 = K.
B÷îc 1: Bði Thuªt to¡n 3.2 ta t½nh A1, °t K1 = A1.
B÷îc i+1: N¸u câ B ∈ K−1i sao cho B 6⊂ Bj (∀j : 1 ≤ j ≤ k) th¼ bði Thuªt to¡n 3.2 ta
t½nh Ai + 1, ð ¥y Ai+1 ∈ H,Ai+1 ⊆ B. ffi°t Ki+1 = Ki ∪ Ai+1. Trong tr÷íng hñp ng÷ñc l¤i
ta °t H = Ki.
ffië phùc t¤p thuªt to¡n 3.3
Theo [5], ë phùc t¤p cõa Thuªt to¡n 3.3 l O
(
|R|
(
m−1∑
q=1
(|K| Iq + |R| tquq) + |K|2 + |R|
))
vîi Iq, tq, uq nh÷ trong Thuªt to¡n 3.1. Do â, ë phùc t¤p tçi nh§t cõa Thuªt to¡n 3.3 l 
h m sè mô theo n vîi n l  sè ph¦n tû cõa R. Tr÷íng hñp Iq ≤ |K| (q = 1, ...,m− 1), ë phùc
t¤p cõa Thuªt to¡n 3.3 l  O
(
|R|2|K|2 |H|
)
, ë phùc t¤p n y l  a thùc theo |R| , |K| v  |H|.
N¸u |H| l  a thùc theo |R| , |K| th¼ thuªt to¡n hi»u qu£. N¸u sè l÷ñng c¡c ph¦n tû cõa H l 
nhä th¼ thuªt to¡n r§t hi»u qu£.
4. THUŁT TON TœM T‡T Cƒ RÓT GÅN TRONG BƒNG QUY˜T ffiÀNH
Cho b£ng quy¸t ành nh§t qu¡n DT = (U,C ∪ d, V, f), R ⊆ C l  tªp rót gån cõa DT
n¸u thäa m¢n POSR ({d}) = POSC ({d}) = U hay R → d, v  R′ 6⊂ R : POSR′ ({d}) =
POSC ({d}) = U hay R′ 6⊂ R : R′ → {d}. Tø ffiành ngh¾a 2.2 v  ffiành ngh¾a 2.3, b i to¡n
t¼m t§t c£ c¡c tªp rót gån cõa b£ng quy¸t ành nh§t qu¡n DT = (U,C ∪ d, V, f) vîi trð
th nh b i to¡n t¼m hå c¡c tªp tèi thiºu cõa thuëc t½nh {d} m  khæng chùa d èi vîi quan h»
r = {u1, u2, ..., um} tr¶n tªp thuëc t½nh R = C ∪ d. Kþ hi»u Rd l  tªp t§t c£ c¡c rót gån cõa
DT, khi â Rd = K
r
d − {d} vîi Krd l  hå c¡c tªp tèi thiºu cõa thuëc t½nh {d} tr¶n quan h» r.
Thuªt to¡n 4.1. Thuªt to¡n t¼m t§t c£ c¡c tªp rót gån tr¶n b£ng quy¸t ành.
ffi¦u v o: B£ng quy¸t ànhDT = (U,C∪d, V, f) vîi POSC ({d}) = U , C = {c1, c2, ..., ck},
U = {u1, u2, ..., um}.
ffi¦u ra: Rd.
Xem b£ng quy¸t ành DT l  quan h» r = {u1, u2, ..., um} tr¶n tªp thuëc t½nh R = C ∪ d.
204 NGUY™N LONG GIANG, VÔ ffiÙC THI
B£ng 1. B£ng quy¸t ành
U a b c d
u1 6 6 0 6
u2 0 2 2 0
u3 0 0 0 0
u4 0 0 3 0
u5 4 4 0 0
u6 5 0 5 5
u7 1 0 0 0
B÷îc 1: Tø r ta x¥y düng h» b¬ng nhau Er = {Eij : 1 ≤ i < j ≤ m}
vîi Eij = {a ∈ R : ui (a) = uj (a)}.
B÷îc 2: Tø Er ta x¥y düng tªp Md = {A ∈ Er : d /∈ A, 6 ∃B ∈ Er : d /∈ B,A ⊂ B}.
B÷îc 3: Bði Thuªt to¡n 3.3, t½nh tªp K tø tªp Md
(
K−1 =Md
)
.
B÷îc 4: ffi°t Rd = K − {d}.
Chùng minh tªp K thu ÷ñc tø B÷îc 3 l  hay hå c¡c tªp tèi thiºu cõa thuëc t½nh d tr¶n
quan h» r.
Thªt vªy, theo c¡ch x¥y düng Md t¤i B÷îc 2 v  theo cæng thùc t½nh bao âng cõa tªp
thuëc t½nh tr¶n quan h», ∀A ∈ Nd ta câ A+ = A v  A khæng chùa d n¶n A+ khæng chùa d, suy
ra A→ {d} /∈ F+. M°t kh¡c, n¸u tçn t¤i B sao cho A ⊂ B th¼ x£y ra hai tr÷íng hñp: (1) N¸u
B khæng chùa d th¼ B+ = R; (2) N¸u B chùa d th¼ hiºn nhi¶n B+ chùa d. C£ hai tr÷íng hñp
ta ·u câ B+ chùa d hay B → {d} ∈ F+. Do â Md = MAX (F+, d) vîi MAX (F+, d) =
{A ⊆ R : A→ {d} /∈ F+, A ⊂ B ⇒ B → {d} ∈ F+}. Theo [3, 6], MAX (F+, d) = (Krd)−1
n¶n Md = (K
r
d)
−1
do â t¤i B÷îc 3, K = Krd l  hå c¡c tªp tèi thiºu cõa thuëc t½nh d tr¶n
quan h» r. T¤i B÷îc 4, Rd = K−{d} thu ÷ñc l  tªp t§t c£ c¡c rót gån cõa b£ng quy¸t ành.
Ph¥n t½ch ë phùc t¤p thuªt to¡n
D¹ th§y, ë phùc t¤p cõa B÷îc 1 v  B÷îc 2 l  a thùc theo k½ch th÷îc cõa r. Do â, ë
phùc t¤p cõa thuªt to¡n l  ë phùc t¤p cõa Thuªt to¡n 3.3 t½nh tªp khâa tèi thiºu tø tªp
ph£n khâa t¤i B÷îc 3. Do â, ë phùc t¤p cõa thuªt to¡n l :
O
(
|R|
(
m−1∑
q=1
(|Md| Iq + |R| tquq) + |Md|2 + |R|
))
vîi Iq, tq, uq nh÷ trong Thuªt to¡n 3.1 v  ë phùc t¤p n y trong tr÷íng hñp x§u nh§t l 
h m sè mô theo n vîi n l  sè ph¦n tû cõa R. Tr÷íng hñp Iq ≤ |Md| (q = 1, ...,m− 1), ë
phùc t¤p cõa thuªt to¡n l  O
(
|R|2|Md|2 |Krd |
)
, ë phùc t¤p n y l  a thùc theo |R| , |Md| v 
|Krd |. D¹ th§y t¤i b÷îc 2, |Md| l  a thùc theo k½ch th÷îc cõa r, do â n¸u |Krd | l  a thùc
theo |R| th¼ ë phùc t¤p cõa thuªt to¡n l  a thùc theo k½ch th÷îc cõa r. N¸u sè l÷ñng c¡c
ph¦n tû cõa Krd l  nhä th¼ thuªt to¡n r§t hi»u qu£.
V½ dö 4.1: Cho b£ng quy¸t ành DT = (U,C ∪ d, V, f) vîi U = {u1, u2, u3, u4, u5, u6, u7},
C = {a, b, c} nh÷ sau:
THUŁT TON TœM T‡T Cƒ CC RÓT GÅN TRONG BƒNG QUY˜T ffiÀNH 205
Xem b£ng quy¸t ành nh÷ quan h» r = {u1, u2, u3, u4, u5, u6, u7} tr¶n tªp thuëc t½nh
R = {a, b, c, d}. ¡p döng Thuªt to¡n 4.1 ta t½nh ÷ñc:
Er = {{a, b, d} , {b, c, d} , {a, d} , {b, d} , {c, d} , {b} , {c} , {d}}
Md = {{b} , {c}}
Bði Thuªt to¡n 3.3, ta t½nh ÷ñc K = Krd = {{a} , {b, c} , {d}}
Nh÷ vªy, tªp t§t c£ c¡c rót gån cõa b£ng quy¸t ành DT l  Rd = K
r
d−{d} = {{a} , {b, c}}.
5. K˜T LUŁN
B i b¡o ÷a ra kh¡i ni»m tªp tèi thiºu cõa mët thuëc t½nh tr¶n quan h» düa tr¶n kh¡i
ni»m tªp tèi thiºu cõa mët thuëc t½nh tr¶n sì ç quan h» trong [6] v  x¥y düng thuªt to¡n
t¼m t§t c£ c¡c tªp rót gån cõa tªp thuëc t½nh i·u ki»n trong b£ng quy¸t ành düa v o kh¡i
ni»m khâa, ph£n khâa v  thuªt to¡n t¼m tªp t§t c£ c¡c khâa, ph£n khâa trong cì sð dú li»u
quan h» [5, 10]. Trong tr÷íng hñp x§u nh§t, ë phùc t¤p thíi gian cõa thuªt to¡n ÷ñc x¥y
düng l  h m mô theo sè thuëc t½nh i·u ki»n. Tr÷íng hñp lüc l÷ñng tªp c¡c khâa tèi thiºu
thu ÷ñc tø tªp c¡c ph£n khâa cho tr÷îc l  a thùc theo n, vîi n l  sè thuëc t½nh i·u ki»n
th¼ ë phùc t¤p thíi gian cõa thuªt to¡n l  a thùc theo sè h ng v  sè cët cõa b£ng quy¸t
ành.
T€I LI›U THAM KHƒO
[1] W. W. Armstrong, Dependency structures of database relationships, Information Processing
74, North-Holland Publ. Co. 1974 (580-583).
[2] J. Demetrovics, On the equivalence of candidate keys with Sperner systems, Acta Cybernetica
4 (1979) 247-252.
[3] J. Demetrovics, V.D. Thi, Algorithms for generating Armstrong relation and inferring functional
dependencies in the relational datamodel, Computers and Mathematics with Applications
26 (4) (1993) 43-55 (Great Britain).
[4] J. Demetrovics, V.D. Thi, Keys, antikeys and prime attributes, Ann. Univ. Scien. Budapest
Sect. Comput. 8 (1987) 37-54.
[5] J. Demetrovics, V.D. Thi, Relations and minimal keys, Acta Cybernetica 8 (3) (1998) 279-285.
[6] J. Demetrovics, V.D. Thi, Some remarks on generating Armstrong and inferring functional de-
pendencies relation, Acta Cybernetica 12 (1995) 167-180.
[7] J. Demetrovics, V.D. Thi, Some results about functional dependencies, Acta Cybernetica 8
(3) (1988) 273-278.
[8] M. Kryszkiewicz, Rough set approach to incomplete information systems, Information Science
(1998) 39-49.
[9] Z. Pawlak, Rough Sets - Theoritical Aspects of Reasoning about Data, Kluwer Academic
Publishers, Dordrecht, 1991.
[10] V.D. Thi, Minimal keys and Antikeys, Acta Cybernetica 7 (4) (1986) 361-371.
Ng y nhªn b i 8 - 6 - 2011