Phụ thuộc hàm đối tượng mở trong cơ sở dữ liệu hướng đối tượng

 º x¡c
ành c¡c kiºu èi t÷ñng mí kh¡c, γ : c¡c th nh ph¦n cõa mët kiºu èi t÷ñng mí ÷ñc x¡c
ành bði c¡c kiºu èi t÷ñng mí kh¡c)
C¡c FOFD ÷ñc biºu di¹n b¬ng c¡c c¥y nèi c¡c èi t÷ñng mí t÷ìng ùng vîi c¡c ¿nh cõa
ç thà l÷ñc ç mí £m b£o r¬ng khæng câ sü nhªp nh¬ng li¶n quan ¸n c¡c k¸t nèi giúa c¡c
kiºu èi t÷ñng mí nguçn (source) v  kiºu èi t÷ñng mí tr¤m (sink). Vîi mët kiºu èi t÷ñng
mí câ thº vøa l  èi t÷ñng mí nguçn vøa l  èi t÷ñng mí trung gian cõa mët FOFD (ch¯ng
108 ffiO€N V‹N BAN, HÇ C‰M H€, VÔ ffiÙC QUƒNG
h¤n, kiºu èi t÷ñng Cho−o trong H¼nh 3.3). Méi th nh ph¦n cõa nh¢n bao gçm mët tªp c¡c
thuëc t½nh hay kiºu èi t÷ñng cõa ch½nh nâ. Méi th nh ph¦n cõa nh¢n ÷ñc g¡n cho ¿nh
trong ç thà phö thuëc èi t÷ñng mí khæng thº gçm c£ c¡c thuëc t½nh v  kiºu èi t÷ñng v¼
ành danh cõa èi t÷ñng x¡c ành duy nh§t mët èi t÷ñng n¶n nâ công x¡c ành duy nh§t
c¡c thuëc t½nh cõa èi t÷ñng.
Chóng ta sû döng kþ hi»u ∆
f−→ Γ thay cho vf , trong â ∆ =
⋃
O∈Vf ,vf (O)=(δ,γ)∧δ 6=
{δ},
Γ =
⋃
O∈Vf ,vf (O)=(δ,γ)∧γ 6=
{γ}, ∆ ÷ñc gåi l  v· ph£i v  Γ ÷ñc gåi l  v¸ tr¡i cõa FOFD. Khi â,
mët FOFD f = (Gf , vf ) câ thº ÷ñc biºu di¹n bði f : ∆
f−→
Gf
Γ vîi ç thà phö thuëc èi t÷ñng
mí Gf v  ∆
f−→ Γ . V½ dö, mët FOFD biºu di¹n r ng buëc ¢ ÷ñc · cªp trong ph¦n giîi
thi»u (H¼nh 1.a) v  ÷ñc ch¿ ra trong H¼nh 3.3 vîi h m g¡n nh¢n cho ¿nh vf (Khach−san) =
(δ, γ), δ = Khach−san, γ =  v  vf (Cho−o) = (δ, γ), δ = loaiPhong, γ = Cho−o. Ta câ
FOFD: {Khach−San, loaiPhong} f−→
Gf
{Cho−o}.
Mët kiºu èi t÷ñng mí O ÷ñc tham chi¸u bði FOFD f (hay ÷ñc bao h m trong FOFD
f ) n¸u ch½nh O hay b§t ký tªp con cõa tªp thuëc t½nh cõa nâ xu§t hi»n trong v¸ tr¡i hay
v¸ ph£i cõa f. f ÷ñc gåi l  phö thuëc h m èi t÷ñng mí chu©n t­c n¸u ch¿ câ mët kiºu èi
t÷ñng mí ÷ñc bao h m trong v¸ ph£i Γ. f ÷ñc gåi l  cöc bë (to n cöc) n¸u ch¿ câ mët kiºu
èi t÷ñng mí (nhi·u hìn mët kiºu èi t÷ñng mí) ÷ñc bao h m trong f.
H¼nh 3.3. Phö thuëc h m èi t÷ñng mí
4. QUAN H› MÍ BIšU DI™N MËT BË PHŁN CÕA s(S)
L m th¸ n o º kiºm tra mët tr¤ng th¡i s(S) cõa l÷ñc ç CSDL HffiT mí câ thäa FOFD
f : ∆
f−→
Gf
Γ hay khæng. T÷ìng tü nh÷ trong CSDL quan h», ìn gi£n chóng ta ch¿ c¦n kiºm
tra tr¶n quan h» mí Rext(O), n¸u f l  FOFD cöc bë. Tr÷íng hñp, f l  FOFD to n cöc, tr÷îc
ti¶n, chóng ta t¤o ra mët quan h» mí b¬ng c¡ch k¸t nèi c¡c quan h» mí t÷ìng ùng vîi c¡c
mèi quan h» mí cõa l÷ñc ç CSDL HffiT mí v  c¡c kiºu èi t÷ñng mí trong c¡c ÷íng d¨n
k¸t nèi ¸n c¡c kiºu èi t÷ñng mí trong ç thà phö thuëc h m èi t÷ñng mí Gf , sau â kiºm
tra quan h» mí thu ÷ñc câ thäa f khæng.
Tr÷îc khi · cªp ¸n thuªt to¡n t¤o ra mët quan h» mí nh÷ ¢ th£o luªn ð tr¶n, chóng
ta ph¡t triºn ph²p to¡n li¶n k¸t ngo i ¦y õ trong [6] º k¸t nèi c¡c quan h» mí. Khæng m§t
t½nh têng qu¡t, nhúng thuëc t½nh th nh vi¶n trong c¡c quan h» mí s³ khæng ÷ñc xem x²t
khi thüc thi ph²p to¡n.
ffiành ngh¾a 4.1. Cho R v  S l  hai quan h» mí vîi tªp c¡c thuëc t½nh l¦n l÷ñt l  ΩR,ΩS ,ΩR∩
ΩS 6= . Ph²p li¶n k¸t ngo i mí ¦y õ vîi ng÷ïng t÷ìng ÷ìng α, (α ∈ [0, 1]) cõa R v  S,
kþ hi»u R
f
./
α
S ÷ñc x¡c ành nh÷ sau:
PHÖ THUËC H€M ffiÈI T×ÑNG MÍ TRONG CÌ SÐ DÚ LI›U H×ÎNG ffiÈI T×ÑNG MÍ 109
R
f
./
α
S = {t|t l  bë x¡c ành tr¶n ΩR ∪ ΩS∧
((t[C] 6=′ ⊥′, ∀C ∈ (ΩR ∩ΩS) ∧ (∃t′)(∃t′′)(t′ ∈ R, t′′ ∈ S)(SE(t′[ΩR ∩ΩS ], t′′[ΩR ∩ΩS ]) >
α ∧ t[ΩR − (ΩR ∩ ΩS)] = t′[ΩR − (ΩR ∩ ΩS)] ∧ t[ΩS − (ΩR ∩ ΩS)] = t′′[ΩS − (ΩR ∩ ΩS)]) ∧
t[ΩR ∩ ΩS ] = t′[ΩR ∩ ΩS ])
∨(t[ΩR] ∈ R ∧ t[C] 6=′ ⊥′, ∀C ∈ (ΩR ∩ ΩS) ∧ ¬(∃t′ ∈ S)(SE(t[ΩR ∩ ΩS ], t′[ΩR ∩ ΩS ]) ≥
α) ∧ t[C] =′ ⊥′, ∀C ∈ (ΩS − ΩR))
∨(t[ΩS ] ∈ S ∧ t[C] 6=′ ⊥′, ∀C ∈ (ΩR ∩ ΩS) ∧ ¬(∃t′ ∈ R)(SE(t[ΩR ∩ ΩS ], t′[ΩR ∩ ΩS ]) ≥
α) ∧ t[C] =′ ⊥′, ∀C ∈ (ΩR − ΩS))
∨(t[ΩR] ∈ R ∧ t[C] =′ ⊥′,∀C ∈ ΩS)
∨(t[ΩS ] ∈ S ∧ t[C] =′ ⊥′,∀C ∈ ΩR))}.
trong â, hai bë t v  t' ÷ñc xem nh÷ gièng nhau tr¶n tªp thuëc t½nh X n¸u mùc ë t÷ìng
÷ìng giúa hai bë n y tr¶n gi¡ trà cõa tªp thuëc t½nh X lîn hìn ho°c b¬ng α. Ba i·u ki»n
¦u cõa ph²p li¶n k¸t ngo i mí ¦y õ câ ÷ñc b¬ng c¡ch mð rëng ba i·u ki»u cõa ph²p li¶n
k¸t ngo i ¦y õ, c¡c bë thu ÷ñc sau khi thüc hi»n ph²p to¡n n y l  ¦y õ tr¶n c¡c thuëc
t½nh chung. Hai i·u ki»n sau ÷ñc th¶m v o cho ph²p c¡c bë câ gi¡ trà khæng x¡c ành tr¶n
c¡c thuëc t½nh chung ÷ñc bê sung v o quan h» k¸t qu£. C¡c i·u ki»n n y l  phò hñp vîi
c¡ch ti¸p cªn cõa chóng ta v¼ gi¡ trà tr¶n tªp c¡c thuëc t½nh li¶n k¸t l  duy nh§t.
H¼nh 4.4. ffiç thà l÷ñc ç CSDL h÷îng èi t÷ñng mí
V½ dö 4.1: X²t l÷ñc ç trong H¼nh 4.1 bao gçm 3 kiºu èi t÷ñng mí O1, O2, O3 câ tªp thuëc
t½nh l¦n l÷ñt l  A, B, C v  hai mèi quan h» r1, r2, ÷ñc biºu di¹n nh÷ sau:
Ext(O1) = {(1, [{1.0/a, 0.7/b, 0.6/c}]), (2, [{1.0/a, 0.7/b, 0.7/c}]), (3, [{0.6/a, 1.0/b, 0.7/c}])};
Ext(O2) = {(4, [{0.6/a, 1.0/c}]), (5, [{0.6/a, 0.7/b, 1.0/c}]), (6, [{1.0/a, 0.6/b, 0.6/c}]),
(7, [{0.6/a, 0.6/c, 1.0/d}]), (8, [{0.7/a, 1.0/b, 0.6/c}])};
Ext(O3) = {(9, [{0.6/a, 0.6/b, 1.0/e}]), (10, [{0.7/a, 0.7/c, 1.0/f}]), (11, [{0.6/a, 0.7/b, 1.0/g}])};
Ext(r1) = {(1, 5), (1, 6), (2, 7), (3, 8)};
Ext(r2) = {(6, 9), (7, 10)}.
Düa tr¶n kh¡i ni»m v· li¶n k¸t bë phªn trong [5], ta câ: c¡c èi t÷ñng (1, [{1.0/a, 0.7/b,
0.6/c}]), (2, [{1.0/a, 0.7/b, 0.7/c}]) ∈ O1 câ li¶n k¸t bë phªn ¸n c¡c èi t÷ñng cõa O3, tùc l 
c¡c èi t÷ñng vîi id = 1 v  id = 2 n y câ mët sè chuéi li¶n k¸t ¸n c¡c èi t÷ñng cõa O3 (khæng
c¦n ph£i câ li¶n k¸t ¸n t§t c£ c¡c èi t÷ñng O3); èi t÷ñng (3, [{0.6/a, 1.0/b, 0.7/c}]) ∈ O1
ch¿ câ mët li¶n k¸t thi¸u ¸n c¡c èi t÷ñng cõa O3; èi t÷ñng (4, [0.6/a, 1.0/c]) ∈ O2 khæng
câ li¶n k¸t n o ¸n c¡c èi t÷ñng cõa O3. V½ dö, sû döng ph²p to¡n li¶n k¸t ngo i mí ¦y õ
º nèi c¡c quan h» mí Rext(O3) v  Rext(r2) ta thu ÷ñc quan h» mí R (nh÷ trong B£ng 2).
N¸u quan h» mí R l  mët quan h» trung gian cho vi»c thüc hi»n c¡c ph²p to¡n li¶n k¸t ngo i
mí ¦y õ ti¸p theo, i·u ki»n bèn v  n«m £m b£o r¬ng bë t = (
′⊥′, 11, {0.6/a, 0.7/b,
1.0/g}) khæng bà m§t.
B£ng 2. R = Rext(O3)
f
./
0.9
Rext(r2)
ido2 ido3 C
6 9 {0.6/a, 0.6/b, 1.0/e}
7 10 {0.7/a, 0.7/c, 1.0/f}
⊥ 11 {0.6/a, 0.7/b, 1.0/g}
Vîi S l  mët l÷ñc ç CSDL HffiT mí, düa v o ph²p
to¡n li¶n k¸t ngo i mí ¦y õ ÷ñc tr¼nh b y ð tr¶n,
thuªt to¡n x¡c ành quan h» mí Rfo biºu di¹n mët bë
110 ffiO€N V‹N BAN, HÇ C‰M H€, VÔ ffiÙC QUƒNG
phªn cõa s(S) ÷ñc tham chi¸u bði f ÷ñc tr¼nh b y
nh÷ sau:
Thuªt to¡n x¡c ành quan h» mí
V o: f : {δ1, δ2, . . . , δn} f−→
Gf
{γ1, γ2, . . . , γk} vîi
Gf = (Vf , Ef , ηf ) v  h m g¡n nh¢n vf .
Ra: Rfo biºu di¹n mët bë phªn cõa s(S)
Ph÷ìng thùc:
1. ffi°t δ′i = δi n¸u δi l  tªp thuëc t½nh, δ
′
i = {ido} n¸u δi = O,O ∈ OTs, ∆′ =
n⋃
i=1
δ′i.
2. ffi°t γ′i = γi n¸u γi l  tªp thuëc t½nh, γ
′
i = {ido} n¸u γi = O,O ∈ OTs, Γ′ =
k⋃
i=1
γ′i.
(i) n¸u f l  mët FOFD cöc bë tham chi¸u ¸n kiºu èi t÷ñng mí, O,Rfo = Rext(O);
(ii) n¸u f l  mët FOFD to n cöc, vîi mët ng÷ïng t÷ìng ÷ìng α ∈ [0, 1], Rfo ÷ñc x¡c ành
nh÷ sau
ffi°t {O1, . . . , Ok} l  tªp c¡c kiºu èi t÷ñng mí tr¤m thuëc Vf v  τ = {idO1 , idO2 , . . . , idOk}
l  tªp c¡c thuëc t½nh ành danh cõa chóng. Vîi méi ¿nh O ∈ Vf , °t φO = δ ∪ γ ∪ {idO} n¸u
vf (O) = (δ, γ) v  φO = {idO} n¸u vf (O) khæng x¡c ành.
(a) Chån mët ¿nh b­t ¦u O ∈ Vf , Rfo = Rext(O)[φO]
Vîi méi e ∈ Ef
N¸u e = (O,Oi) and ηf (e) = r {
Rfo = Rfo
f
./
α
Rext(r);Ef = Ef − {e}; }
Vf = Vf − {O};
Vîi (Vf 6= ) {
Chån mët ¿nh Oj ∈ Vf sao cho idOj ∈ ΩRfo
Rfo = Rfo
f
./
α
Rext(Oj)[φOj ];
Vîi méi e′ ∈ Ef
N¸u e′ = (Oj , Ok) and ηf (e′) = r′
{ Rfo = Rfo
f
./
α
Rext(r′);
Ef = Ef − {e′}; }
Vf = Vf − {Oj};
};
(b) Chu©n hâa v¸ ph£i: N¸u (τ 6= ), xâa t§t c£ c¡c bë khæng x¡c ành tr¶n τ : Rfo =
WNF (Rfo, τ)
(c) Chu©n hâa phõ: Xâa t§t c£ c¡c bë ÷ñc phõ bði c¡c bë kh¡c tr¶n c¡c thuëc t½nh thuëc v·
c¡c kiºu cõa v¸ tr¡i v  v¸ ph£i cõa f : Rfo = {t|¬(∃t′ ∈ Rfo) m  t' phõ t vîi mùc α tr¶n tªp
thuëc t½nh ∆′ ∪ Γ′}.
end;
V½ dö 2: Gi£ sû ta câ mët FOFD f : {A,O3} f−→
Gf
{O2} cõa l÷ñc ç CSDL HffiT mí (H¼nh
4.1). Vîi ng÷ïng t÷ìng ÷ìng α = 0.9, Rfo ÷ñc x¡c ành bði mët chuéi ph²p to¡n li¶n k¸t
ngo i mí ¦y õ b­t ¦u tø O3 : (((Rext(O3)[idO3 ]
f
./
α
Rext(r2)[idO2 ])
f
./
α
Rext(O2)[idO2 ])
f
./
α
PHÖ THUËC H€M ffiÈI T×ÑNG MÍ TRONG CÌ SÐ DÚ LI›U H×ÎNG ffiÈI T×ÑNG MÍ 111
Rext(r1)
f
./
α
Rext(O1)[A, idO1 ]).
Vîi quan h» mí nh÷ ð trong V½ dö 1 (bä i thuëc t½nh C ) ta câ:
Rfo = (Rext(O3)[idO3 ]
f
./
α
Rext(r2)) Rfo = (Rfo
f
./
α
Rext(O1)[idO2 ])
idO2 idO3 idO2 idO3
6 9 6 9
7 10 7 10
⊥ 11 5 ⊥
8 ⊥
4 ⊥
⊥ 11
Rfo = (Rfo
f
./
α
Rext(r1)) Rfo = (Rfo
f
./
α
Rext(O1)[A, idO1 ])
idO2 idO3 idO1 idO2 idO3 idO1 A
6 9 1 6 9 1 {1.0/a, 0.7/b, 0.6/c}
7 10 2 7 10 2 {1.0/a, 0.7/b, 0.7/c}
5 ⊥ 1 5 ⊥ 1 {1.0/a, 0.7/b, 0.6/c}
8 ⊥ 3 8 ⊥ 3 {0.6/a, 1.0/b, 0.7/c}
4 ⊥ ⊥ 4 ⊥ ⊥ ⊥
⊥ 11 ⊥ ⊥ 11 ⊥ ⊥
Bèn bë ¦u cõa Rfo câ ÷ñc tø i·u ki»n k¸t nèi ¦u ti¶n cõa ph²p li¶n k¸t ngo i mí ¦y õ,
bë ti¸p theo l  bë treo tø Rext(O2), k¸t qu£ tø i·u ki»n 3. Bë n y biºu di¹n mët èi t÷ñng
mí thuëc O2 khæng câ c¡c li¶n k¸t. Bë thù 5 ÷ñc t¤o ra bði i·u ki»n cuèi còng cõa ph²p
li¶n k¸t ngo i mí ¦y õ. Quan h» mí Rfo sau khi thüc hi»n b÷îc chu©n hâa v¸ ph£i, bë thù
5 s³ ÷ñc xâa khäi Rfo do bë n y khæng ÷ñc x¡c ành tr¶n idO2 . B÷îc chu©n hâa phõ khæng
bë n o bà xâa.
Vi»c x¥y düng quan h» mí £m b£o t§t c£ c¡c èi t÷ñng ð b¶n ph£i cõa tr¤ng th¡i ¢ cho
÷ñc biºu di¹n trong Rfo nh÷ng lo¤i bä i c¡c bë thæng qua vi»c chu©n hâa v¸ ph£i v  chu©n
hâa phõ. C¡c bë khæng x¡c ành tr¶n c¡c thuëc t½nh cõa Rfo m  thuëc v· c¡c èi t÷ñng mí
tr¤m, chóng mæ t£ c¡c li¶n k¸t m  khæng câ èi t÷ñng cõa kiºu èi t÷ñng v¸ ph£i tham gia,
vi»c lo¤i bä chóng ra khäi quan h» Rfo khæng l m m§t thæng tin cõa c¡c thº hi»n cõa c¡c
kiºu èi t÷ñng mí ð v¸ ph£i. N¸u hai bë mæ t£ li¶n k¸t cõa mët èi t÷ñng v¸ ph£i vîi c¡c èi
t÷ñng v¸ tr¡i tçn t¤i, n¸u bë n y ÷ñc bao phõ bði mët bë kh¡c trong Rfo ÷ñc lo¤i bä bði
chu©n hâa phõ.
5. CC D„NG PHÖ THUËC H€M ffiÈI T×ÑNG MÍ
Theo c¡ch ti¸p cªn cõa Raju [7], mët phö thuëc h m mí f : X
f→ Y óng tr¶n quan h» r
n¸u v  ch¿ n¸u vîi hai bë b§t ký thuëc quan h» r ë g¦n nhau giúa hai gi¡ trà cõa hai bë tr¶n
Y luæn lîn hìn ho°c b¬ng ë g¦n nhau giúa hai gi¡ trà cõa hai bë tr¶n X. Trong ngú c£nh
cõa CSDL HffiT mí, düa tr¶n quan h» mí, c¡c kh¡i ni»m kh¡c nhau li¶n quan ¸n t½nh óng
cõa c¡c FOFD trong tr¤ng th¡i cõa mët l÷ñc ç CSDL HffiT mí s³ ÷ñc tr¼nh b y trong möc
n y. Vîi mët FOFD f : ∆
f−→
Gf
Γ chóng ta ch¿ xem x²t ngú ngh¾a cõa f tr¶n tªp c¡c thuëc
t½nh v  c¡c thuëc t½nh ành danh trong quan h» mí Rfo m  thuëc v· ∆,Γ. C¡c thuëc t½nh
kh¡c li¶n quan ¸n c¡c chuéi li¶n k¸t giúa c¡c èi t÷ñng cõa ∆ v  Γ khæng ÷ñc xem x²t m°c
112 ffiO€N V‹N BAN, HÇ C‰M H€, VÔ ffiÙC QUƒNG
dò chóng công ÷ñc biºu di¹n trong Rfo. Vîi ∆
′,Γ′ v  τ = {idO1 , idO2 , . . . , idOk} ÷ñc x¡c
ành nh÷ trong thuªt to¡n x¡c ành quan h» mí ÷ñc tr¼nh b y ð tr¶n, mët FOFD ÷ñc thäa
m¤nh hay y¸u trong tr¤ng th¡i l÷ñc ç CSDL HffiT ÷ñc ành ngh¾a nh÷ sau:
ffiành ngh¾a 5.1. Cho S l  mët l÷ñc ç CSDL HffiT mí, s(S) l  tr¤ng th¡i cõa S, α l  mët
ng÷ïng t÷ìng ÷ìng, mët FOFD f : {δ1, δ2, . . . , δn} f−→
Gf
{γ1, γ2, . . . , γk} ÷ñc thäa m¤nh
trong s(S) n¸u thäa m¢n hai i·u ki»n sau ¥y:
(i) (∀t, t′ ∈ NF (Rfo,∆′))⇒ SE(t[Γ′], t′[Γ′]) ≥ SE(t[∆′], t′[∆′]))
(ii)Rfo[{idOi}] = NF (Rfo,Γ′)[idOi ] vîi idOi ∈ τ, i = 1, 2, . . . , k.
ffièi vîi CSDL HffiT mí, kiºu dú li»u cõa c¡c thuëc t½nh khæng ìn thu¦n l  c¡c kiºu cì
sð m  cán câ c¡c kiºu phùc t¤p kh¡c nh÷ kiºu tªp, kiºu bë, . . . . Düa tr¶n th÷îc o ë t÷ìng
÷ìng ngú ngh¾a giúa hai gi¡ trà mí, v  kh¡i ni»m v· hai èi t÷ñng çng nh§t, hai èi t÷ñng
b¬ng nhau, cæng thùc x¡c ành mùc ë t÷ìng ÷ìng SE(...) cõa hai bë tr¶n tªp thuëc t½nh X
vîi quan h» t÷ìng tü tr¶n mi·n gi¡ trà cõa c¡c thuëc t½nh thuëc X trong c¡ch ti¸p cªn n y
÷ñc t½nh t÷ìng tü nh÷ trong [2].
Ð i·u ki»n (i), f l  h m ¡nh x¤ méi gi¡ trà ¦y õ cõa ∆′ trong Rfo v o óng mët gi¡
trà cõa Γ′. Vîi c¡c gi¡ trà (t÷ìng ùng, c¡c èi t÷ñng) ÷ñc ÷a ra ð iºm ¦u v o cõa méi δi,
nhi·u nh§t mët tê hñp c¡c èi t÷ñng v¸ ph£i hay c¡c gi¡ trà ÷ñc t¼m th§y. ffii·u ki»n (ii) £m
b£o t½nh ch§t to n ¡nh khi t§t c£ c¡c li¶n k¸t bë phªn v  li¶n k¸t thi¸u ÷ñc lo¤i bä. Do â,
vîi méi èi t÷ñng mí tr¤m, ½t nh§t mët tê hñp c¡c èi t÷ñng mí nguçn (t÷ìng ùng, c¡c gi¡
trà cõa c¡c èi t÷ñng) ph£i tçn t¤i º thæng qua â c¡c èi t÷ñng tr¤m ÷ñc x¡c ành duy
nh§t.
V½ dö 3: Cho f{O2} f−→
Gf
{A} tr¶n còng l÷ñc ç CSDL HffiT mí v  tr¤ng th¡i cõa l÷ñc ç
CSDL HffiT mí nh÷ V½ dö 1. Theo thuªt to¡n tr¶n, quan h» mí Rfo ÷ñc x¡c ành nh÷ sau:
idO2 idO1 A
6 1 {1.0/a, 0.7/b, 0.6/c}
7 2 {1.0/a, 0.7/b, 0.7/c}
5 1 {1.0/a, 0.7/b, 0.6/c}
8 3 {0.6/a, 1.0/b, 0.7/c}
Ta câ , vîi hai bë b§t ký t, t′ ∈ NF (Rfo, {idO2}) ta ·u câ
SE(t[A], t′[A]) > SE(t[idO2 ], t′[idO2 ]) v  Rfo[{idO1}] =
NF (Rfo, {idO2})[{idO1}]. Vªy f' l  phö thuëc h m ÷ñc
thäa m¤nh trong s(S). T÷ìng tü nh÷ phö thuëc h m trong
CSDL quan h», i·u n y câ ngh¾a l  vîi gi¡ trà ¦u v o
l  mët èi t÷ñng x¡c ành thuëc kiºu èi t÷ñng mí O2 s³
x¡c ành duy nh§t mët gi¡ trà thuëc t½nh A cõa mët èi t÷ñng thuëc kiºu èi t÷ñng O1 tr¶n
tr¤ng th¡i cõa l÷ñc ç CSDL HffiT mí.
ffiành ngh¾a 5.2. Cho S l  mët l÷ñc ç CSDL HffiT mí, s(S) l  tr¤ng th¡i cõa S, α l  mët
ng÷ïng t÷ìng ÷ìng, mët FOFD f : {δ1, δ2, . . . , δn} f−→
Gf
{γ1, γ2, . . . , γk} ÷ñc thäa y¸u trong
s(S) n¸u: (∀t, t′ ∈ NF (Rfo,∆′))⇒ SE(t[Γ′], t′[Γ′]) ≥ SE(t[∆′], t′[∆′]))
V½ dö 4: Vîi FOFD f ′{A,O3} f−→
G′f
{O2} nh÷ trong V½ dö 2, ta câ NF (Rfo, {idO3}) gçm 2 bë
(6, 9, 1, {1.0/a, 0.7/b, 0.6/c}), (7, 10, 2, {1.0/a, 0.7/b, 0.7/c}). Vîi hai bë t, t′ ∈ NF (Rfo, {idO3})
ta câ SE(t[idO2 ], t
′[idO2 ]) > SE(t[A, idO3 ], t′[A, idO3 ]). Theo ành ngh¾a, f' l  ÷ñc thäa y¸u
trong tr¤ng th¡i l÷ñc ç ¢ cho v  i·n ki»n (ii) trong ành ngh¾a 3 khæng ÷ñc thäa m¢n.
N¸u mët FOFD l  ÷ñc thäa y¸u, t§t c£ c¡c èi t÷ñng cõa c¡c kiºu èi t÷ñng mí tr¤m
÷ñc x¡c ành duy nh§t b¬ng vi»c sû döng t§t c£ c¡c δi ∈ ∆ nh÷ c¡c iºm ¦u v o. Tuy
nhi¶n, i·u ki»n ¦y õ tr¶n ∆ l  qu¡ ch°t n¸u ta c¦n t¼m ki¸m kh£ n«ng kh¡c º x¡c ành
PHÖ THUËC H€M ffiÈI T×ÑNG MÍ TRONG CÌ SÐ DÚ LI›U H×ÎNG ffiÈI T×ÑNG MÍ 113
èi t÷ñng nh÷ ¢ · cªp trong H¼nh 1.b. V¼ vªy, c¡c li¶n k¸t bë phªn tø èi t÷ñng mí tr¤m
¸n èi t÷ñng mí nguçn câ thº ÷ñc sû döng º nhªn bi¸t c¡c èi t÷ñng.
ffiành ngh¾a 5.3. Cho S l  mët l÷ñc ç CSDL HffiT mí, s(S) l  tr¤ng th¡i cõa S, α l  mët
ng÷ïng t÷ìng ÷ìng, mët FOFD f : {δ1, δ2, . . . , δn} f−→
Gf
{γ1, γ2, . . . , γk} ÷ñc thäa m¤nh
trong s(S) theo li¶n k¸t bë phªn n¸u thäa m¢n hai i·u ki»n sau ¥y:
(i) (∀t, t′ ∈ NF (Rfo,∆′))⇒ SE(t[Γ′], t′[Γ′]) ≥ SE(t[∆′], t′[∆′]))
(ii)Rfo[{idOi}] = WNF (Rfo,Γ′)[idOi ] vîi idOi ∈ τ, i = 1, 2, . . . , k.
Mët FOFD ÷ñc thäa m¤nh theo li¶n k¸t bë phªn biºu di¹n mët kh½a c¤nh kh¡c trong
vi»c nhªn bi¸t èi t÷ñng, ð ¥y, nhi·u nh§t mët èi t÷ñng ð v¸ ph£i câ thº ÷ñc t¼m th§y
vîi ch¿ mët sè gi¡ trà hay c¡c èi t÷ñng ð c¡c iºm ¦u v o δ1, δ2, . . . , δn. C¡c èi t÷ñng ð v¸
ph£i ch¿ câ li¶n k¸t thi¸u hay khæng câ li¶n k¸t ¸n c¡c kiºu èi t÷ñng mí nguçn s³ khæng
÷ñc xem x²t v¼ chóng khæng ÷ñc t¼m th§y tø b§t ký c¡c iºm ¦u v o n o. Trong tr÷íng
hñp n y, n¸u tçn t¤i c¡c èi t÷ñng nh÷ th¸ th¼ FOFD khæng ÷ñc thäa m¤nh theo li¶n k¸t bë
phªn. Mët FOFD ÷ñc thäa y¸u trong s(S) theo li¶n k¸t bë phªn n¸u ch¿ thäa m¢n i·u ki»n
(i).
V½ dö 5: Vîi f ′′ : {A,O3} f−→
G′′f
{O2} nh÷ trong V½ dö 2, WNF (Rfo, {idO3}) gçm c¡c bë sau:
idO2 idO3 idO1 A
6 9 1 {1.0/a, 0.7/b, 0.6/c}
7 10 2 {1.0/a, 0.7/b, 0.7/c}
5
′⊥′ 1 {1.0/a, 0.7/b, 0.6/c}
8
′⊥′ 3 {0.6/a, 1.0/b, 0.7/c}
Vîi hai bë b§t ký t, t′ ∈ WNF (Rfo, {A, idO3}) th¼
SE(t[idO2 ], t
′[idO2 ]) > SE(t[A, idO3 ], t′[A, idO3 ])
(thäa m¢n i·u ki»n i). ffii·u ki»n (ii) khæng ÷ñc
thäa m¢n do èi t÷ñng câ id = 4 thuëc O2 khæng câ
chuéi li¶n k¸t n o ¸n c¡c èi t÷ñng cõa O3. Vªy, f'
khæng ÷ñc thäa m¤nh trong s(S) theo li¶n k¸t bë
phªn.
V½ dö 6: Cho f ′′′ : {B,A} f−→
G′′′f
{O1} tr¶n còng l÷ñc ç CSDL HffiT mí nh÷ trong V½ dö 1.
Ta câ WNF (Rfo, {B,C}) gçm c¡c bë sau.
idO2 B idO3 C idO1
6 {1.0/a, 0.6/b, 0.6/c} 9 {0.6/a, 0.6/b, 1.0/e} 1
7 {0.6/a, 0.6/c, 1.0/d} 10 {0.7/a, 0.7/c, 1.0/f} 2
5 {0.6/a, 0.7/b, 1.0/c}
′⊥′ ′⊥′ 1
8 {0.7/a, 1.0/b, 0.6/c}
′⊥′ ′⊥′ 3
Vîi hai bë t1 = (6, {1.0/a, 0.6/b,
0.6/c}, 9, {0.6/a, 0.6/b, 1.0/e}, 1)
v  t2 = (7, {0.6/a, 0.6/c, 1.0/d},
10, {0.7/a, 0.7/c, 1.0/f}, 2).
Ta câ : SE(t1[idO1 ], t2[idO1 ]) =
SE( {1.0/a, 0.7/b, 0.6/c},{1.0/a,
0.7/b, 0.7/c}) = min(2.32.3 ,
2.3
2.4) =
0.96. SE(t1[BC], t2[BC]) = min(SE(t1[B], t2[B]), SE(t1[C], t2[C])) = min(
1.2
2.2 ,
0.6
2.4) = 0.25.
Suy ra, SE(t1[idO1], t2[idO1]) > SE(t1[BC], t2[BC]). T÷ìng tü, vîi hai bë kh¡c cõa quan h»
mí ·u thäa m¢n i·u ki»n (i). Ngo i ra, ta cán câ Rfo[{idO1}] = WNF (Rfo, BC)[{idO1}].
Vªy f ′′′ ÷ñc thäa m¤nh trong s(S) theo li¶n k¸t bë phªn. f ′′′ câ thº ÷ñc xem nh÷ mët c¡ch
thùc x¡c ành èi t÷ñng O1 düa v o gi¡ trà.
Tø c¡c ành ngh¾a v· c¡c d¤ng phö thuëc h m èi t÷ñng mí ¢ ÷ñc tr¼nh b y ð tr¶n,
mët phö thuëc h m mí câ d¤ng f : ∆
f−→
Gf
{O} câ thº ÷ñc xem nh÷ mët cæng cö nhªn bi¸t
èi t÷ñng trong CSDL HffiT mí. Ð ¥y, mët FOFD x¡c ành mët tªp c¡c iºm ¦u v o câ
thº bao gçm c£ c¡c kiºu èi t÷ñng mí, n¸u vîi mët tªp gi¡ trà iºm ¦u v o δi(δi ∈ ∆) m 
114 ffiO€N V‹N BAN, HÇ C‰M H€, VÔ ffiÙC QUƒNG
δi∩OTs =  cho ta mët c¡ch thùc nhªn bi¸t èi t÷ñng ch¿ düa v o gi¡ trà cõa c¡c thuëc t½nh,
¥y l  v§n · ÷ñc quan t¥m nhi·u bði ng÷íi sû döng CSDL.
6. K˜T LUŁN
T÷ìng tü nh÷ trong CSDL quan h», phö thuëc h m ÷ñc xem nh÷ cæng cö º biºu di¹n
c¡c r ng buëc dú li»u. B i b¡o ¢ · xu§t mët FOFD tr¶n c¡c thuëc t½nh cõa c¡c kiºu èi
t÷ñng mí câ thº bao gçm c£ c¡c kiºu cõa chóng. Düa tr¶n t½nh óng ­ng cõa FOFD, vîi
mët gi¡ trà ¦u v o FOFD gióp ta x¡c ành duy nh§t mët èi t÷ñng trong méi tr¤ng th¡i cõa
l÷ñc ç CSDL HffiT mí, nâ ÷ñc xem nh÷ c¡ch thùc x¡c ành èi t÷ñng trong méi tr¤ng th¡i
CSDL HffiT mí. C¡c luªt suy d¨n cõa phö thuëc h m èi t÷ñng mí v  nghi¶n cùu c¡c £nh
h÷ðng cõa c¡c phö thuëc h m èi t÷ñng mí trong qu¡ tr¼nh thi¸t k¸ CSDL HffiT mí s³ ÷ñc
nghi¶n cùu trong nhúng cæng tr¼nh ti¸p theo.
T€I LI›U THAM KHƒO
[1] B. S. Lee, Normalization in OODB Design, ACM SIGMOD Record 24(3) (1995) 2327.
[2] ffi.V. Ban, H.C. H , V.ffi. Qu£ng, Chu©n hâa c¡c lîp èi t÷ñng trong l÷ñc ç CSDL h÷îng èi
t÷ñng mí, T¤p ch½ Tin håc v  ffii·u khiºn håc 27(2) (2011) 131141.
[3] D.V. Ban, H.C. Ha, V. D. Quang, Querying fuzzy object-oriented data based on fuzzy association
algebra, Proc. 3th Intl. Conf. on Knowledge and Systems Engineering (KSE2011), Hanoi-
Vietnam, IEEE Computer Society Press, 2011 (4047).
[4] K. D. Schewe and B. Thalheim, Fundamental concepts of object-oriented databases, Acta Cy-
bernetica, 11 (1-2) (1993) 4983.
[5] H.J. Klein and J. Rasch, Value base identification and functional dependencies for object
databases, Proc. 3th Intl. Basque Workshop on Information Technology (BIWIT 97),
Biarritz France, IEEE Computer Society Press, 1997 (2232).
[6] M. Lacroix, A. Pirotte, Generalized Joins, ACM SIGMOD Record 29(2) (1976) 5-16.
[7] Raju et al, Fuzzy functional dependencies and lossless join decomposition of fuzzy relational
database systems, ACM TODS 13(2) (1998).
[8] Vojtech Merunka, Jir½ Brozek, Martin

Sebek, Martin Molhanec, Normalization rules of the object-
oriented data model, Proc. Intl. Workshop on Enterprises & Organizational Modeling and
Simulation, Amsterdam-Netherlands, 2009.
[9] Zahir Tari, John Stokes, Stefano Spaccapietra, Object normal forms and dependency constraints
for object-oriented schemata,ACM Transactions on Database Systems 22(4) (1997) 513569.
[10] Zongmin Ma, Fuzzy database modeling with XLM, Springer, NewYork, 2005.
[11] Z. M. Ma, W. J. Zhang, W. Y. Ma, Assessment of data redundancy in fuzzy relational databases
based on semantic inclusion degree, Information Processing Letters 72 (1-2) (1999) 2529.
Ng y nhªn b i 28 - 12 - 2011
Nhªn l¤i sau sûa 30 - 5 - 2012