Thuật toán tìm tất cả các rút gọn trong bản 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