Phân mảnh trên giá trị lặp của các thuộc tính trong cơ sở dữ liệu quan hệ

tu
.o.ng
u´.ng vo´.i caˆu leˆ.nh SQL nhu
. sau:
SELECT 
FROM R (6)
WHERE True
PHAˆN MA’NH TREˆN GIA´ TRI. LA˘. P CU
’A CA´C THUOˆ. C TI´NH 89
Kha´c vo´.i phaˆn ma’nh ngang die`ˆu kieˆ.n True o
.’ daˆy la` meˆ.nh de`ˆ logic cho phe´p cho.n ra ca´c
thuoˆ.c t´ınh cu’a R co´ gia´ tri. tho’a ma˜n die`ˆu kieˆ.n na`o do´. V´ı du. True la` die`ˆu kieˆ.n deˆ’ cho.n ra
ca´c thuoˆ.c t´ınh co´ doˆ. roˆ.ng lo´
.n nhaˆ´t be´ nhaˆ´t hay ca´c thuoˆ.c t´ınh yeˆu ca`ˆu kha´c, cha˘’ ng ha.n, Null.
Ca´c ma’nh do.c thu du
.o.. c co´ da.ng Key ∪ Vl, l = 1, d.
Tuy nhieˆn phu.o.ng pha´p toˆ’ng qua´t deˆ’ phaˆn ma’nh do.c la` su
.’ du.ng ma traˆ.n lieˆn keˆ´t giu˜
.a
ca´c thuoˆ.c t´ınh AA deˆ’ t`ım ra ma traˆ.n lieˆn keˆ´t tu. CA thoˆng qua thuaˆ. t toa´n BEA ([1]) deˆ’ gom
tu. ca´c thuoˆ.c t´ınh co´ lieˆn keˆ´t cao la. i vo´
.i nhau roˆ`i ta´ch ca´c quan heˆ. du
.
. a theo moˆ´i lieˆn keˆ´t cao
do´. Deˆ’ la`m du.o.. c die`ˆu na`y th`ı kha´ phu´
.c ta.p v`ı chu´ng ta pha’i bieˆ´t du
.o.. c ca´c u´
.ng du. ng, soˆ´ truy
xuaˆ´t cu’a ca´c u´.ng du.ng do´,... Deˆ’ do
.n gia’n va` mang t´ınh chaˆ´t u´.ng du.ng, o
.’ daˆy chu´ng ta se˜
gom ca´c thuoˆ.c t´ınh Aj cu’a quan heˆ. R(Key, A1, A2, ..., An) tho’a ma˜n meˆ.nh de`ˆ do
.n gia’n (5),
tu´.c la` pj : Aj = dj =constant va` meˆ.nh de`ˆ (6) la. i vo´
.i nhau deˆ’ cu`ng vo´.i ca´c thuoˆ.c t´ınh kho´a
cu’a R ta.o ra moˆ.t ma’nh (quan heˆ. con). Ho
.n theˆ´ nu˜.a neˆ´u vieˆ.c phaˆn ma’nh thu
.
. c hieˆ.n du
.o.. c th`ı
vo´.i quan heˆ. con du
.o.. c ta.o tha`nh chı’ ca`ˆn lu
.u ca´c thuoˆ.c t´ınh kho´a va` gia´ tri. cu’a chu´ng. Co`n
ca´c thuoˆ.c t´ınh khoˆng kho´a va` ca´c gia´ tri. cu’a ma’nh chı’ ca`ˆn lu
.u du.´o.i da.ng bieˆ´n nho´
. ma’ng hai
chie`ˆu. Vo´.i phu.o.ng pha´p na`y chu´ng ta co´ theˆ’ tieˆ´t kieˆ.m du
.o.. c dung lu
.o.. ng boˆ. nho´
., tho`.i gian
do.c, caˆ.p nhaˆ. t va` xu
.’ ly´ - tu´.c la` gia’m chi ph´ı.
2.1.3. Phaˆn ma’nh hoˆ˜n ho.. p
Tru.`o.ng ho.. p khi phaˆn ma’nh keˆ´t ho
.
. p ca’ phaˆn ma’nh ngang va` phaˆn ma’nh do.c th`ı qua´ tr`ınh
phaˆn ma’nh du.o.. c go. i la` phaˆn ma’nh hoˆ˜n ho
.
. p. Phaˆn ma’nh hoˆ˜n ho
.
. p thu
.`o.ng du.o.. c thu
.
. c hieˆ.n
theo tr`ınh tu.. phaˆn ma’nh ngang tru
.´o.c sau do´ phaˆn ma’nh do.c hoa˘.c ngu
.o.. c la. i ([1]). Trong ba`i
ba´o na`y, ta se˜ cho.n theo ca´ch thu´
. nhaˆ´t. Co´ theˆ’ coi vieˆ.c phaˆn ma’nh hoˆ˜n ho
.
. p tu
.o.ng u´.ng vo´.i
ca´c caˆu leˆ.nh SQL nhu
. sau:
SELECT *
FROM R
WHERE <Meˆ.nh de`ˆ hoˆ. i so
. caˆ´p>
Ma’nh thu du.o.. c la` taˆ.p ca´c boˆ. du
.o.. c ta´ch ra qua vieˆ.c thu
.
. c hieˆ.n caˆu SQL o
.’ treˆn ch´ınh la`
ma’nh ngang. Ky´ hieˆ.u ma’nh ngang thu du
.o.. c la` H. Baˆy gio`
. thu.. c hieˆ.n phaˆn ma’nh do.c tu`
. ca´c
ma’nh ngang da˜ co´, du`ng caˆu leˆ.nh SQL nhu
. sau:
SELECT 
FROM H
WHERE True
Ky´ hieˆ.u ma’nh do.c thu du
.o.. c do caˆu leˆ.nh treˆn la` VH , va` taˆ.p kho´a cu’a H la` KeyH.
Ma’nh hoˆ˜n ho.. p thu du
.o.. c co´ da.ng KeyH ∪ VH va` du
.o.. c ky´ hieˆ.u la` HV .
2.1.4. Ta´i thieˆ´t quan heˆ. toa`n cu. c
- Ta´i thieˆ´t moˆ.t quan heˆ. toa`n cu. c tu`
. ca´c ma’nh ngang du.o.. c thu
.
. c hieˆ.n ba`˘ng toa´n tu
.’ ho.. p.
Tu´.c la` neˆ´u quan heˆ. R du
.o.. c phaˆn tha`nh ca´c ma’nh ngang H1, H2, ..., Hh th`ı:
R =
h⋃
i=1
Hi. (7)
- Ta´i thieˆ´t moˆ.t quan heˆ. toa`n cu. c tu`
. ca´c ma’nh do.c du
.o.. c thu
.
. c ba`˘ng toa´n tu
.’ noˆ´i ∇. Tu´.c
la` neˆ´u quan heˆ. R du
.o.. c phaˆn tha`nh ca´c ma’nh do.c V1, V2, ..., Vv th`ı:
R = ∇vi=1Vi. (8)
90 LEˆ HUY THAˆ. P
- Ta´i thieˆ´t moˆ. t quan heˆ. toa`n cu. c tu`
. phaˆn ma’nh hoˆ˜n ho.. p du
.o.. c thu
.
. c hieˆ.n ba`˘ng ca´ch du`ng
toa´n tu.’ noˆ´i deˆ’ noˆ´i ca´c ma’nh do.c sau do´ du`ng toa´n tu
.’ ho.. p deˆ’ ho
.
. p ca´c ma’nh ngang neˆ´u thu´
.
tu.. phaˆn ma’nh hoˆ˜n ho
.
. p la` phaˆn ma’nh ngang sau do´ mo´
.i phaˆn ma’nh do.c hoa˘.c du`ng toa´n tu
.’
ho.. p deˆ’ ho
.
. p ca´c ma’nh ngang sau do´ du`ng toa´n tu
.’ noˆ´i deˆ’ noˆ´i ca´c ma’nh do.c neˆ´u thu´
. tu.. phaˆn
ma’nh hoˆ˜n ho.. p la` phaˆn ma’nh do.c tru
.´o.c sau do´ mo´.i phaˆn ma’nh ngang. Nhu. vaˆ.y coˆng vieˆ.c ta´i
thieˆ´t co´ thu´. tu.. ngu
.o.. c vo´
.i thu´. tu.. phaˆn ma’nh ngang va` do.c. Tu´
.c la`:
R = ∪∇(HV )i hoa˘.c ∇∪ (V H)i vo´
.i ∀(HV )i va` ∀(V H)i. (9)
Thu´. tu.. thu
.
. c hieˆ.n phe´p toa´n tu`
. pha’i sang tra´i, ngu.o.. c vo´
.i thu´. tu.. phaˆn ma’nh.
Neˆ´u ca´c ma’nh (HV )i tho’a ma˜n die`ˆu kieˆ.n (HV )i∩(HV )j → (HV )i−(HV )j hoa˘.c (HV )i∩
(HV )j → (HV )j − (HV )i ∀i, j th`ı vieˆ.c phaˆn ma’nh va` ta´i thieˆ´t se˜ khoˆng maˆ´t ma´t thoˆng tin
([2]).
3. BA`I TOA´N PHAˆN MA’NH U´
.
NG DU. NG
3.1. Ba`i toa´n phaˆn ma’nh toˆ´i u.u
Gia’ su.’ vieˆ.c phaˆn ma’nh hoˆ˜n ho
.
. p quan heˆ. R se˜ cho ra n ma’nh HVi, moˆ˜i ma’nh HVi se˜ cho
heˆ. soˆ´ lo
.
. i ı´ch la` hvi. Go.i cri va` cai la` chi ph´ı deˆ’ chı’ do.c va` deˆ’ truy caˆ.p tu
.o.ng u´.ng deˆ´n ma’nh
HVi ([1]). Nhu. vaˆ.y co´ theˆ’ da˘. t vaˆ´n de`ˆ t`ım chieˆ´n lu
.o.. c phaˆn ma’nh hoˆ˜n ho
.
. p tu`
. quan heˆ. da˜ cho
R deˆ’ co´ ca´c n ma’nh HVi la`m cho ha`m lo.. i ı´ch:
U =
n∑
i=1
(hvi − cri − cai) (10)
co´ gia´ tri. lo´
.n nhaˆ´t.
Ca´c ra`ng buoˆ.c:
n∑
i=1
Size(HV )i 
 C, C la` kha’ na˘ng lu.u tru˜.
n∑
i=1
T imeRead(HV )i 
 Tread, Tread la` tho`
.i gian do.c toˆ´i da
n∑
i=1
T imeWrite(HV )i 
 Twrite, Twrite la` tho`
.i gian ghi toˆ´i da
(11)
3.2. Ba`i toa´n phaˆn ma’nh u´.ng du.ng
Deˆ’ u´.ng du.ng, ta se˜ khoˆng gia’ i (10) - (11) v`ı phu´
.c ta.p va` ke´m hieˆ.u qua’, ma` ta se˜ phaˆn
ma’nh quan heˆ. R tha`nh ca´c ma’nh hoˆ˜n ho
.
. p vo´
.i mu. c d´ıch da˜ no´i o
.’ pha`ˆn mo.’ da`ˆu, tu´.c la` ma’nh
hoˆ˜n ho.. p chı’ goˆ`m ca´c thuoˆ.c t´ınh du
.o.. c tuyeˆ’n cho.n keˆ´t ho
.
. p la. i vo´
.i nhau, moˆ˜i thuoˆ.c t´ınh chı’
nhaˆ.n gia´ tri. ha`˘ng va` ve`ˆ nguyeˆn ta˘´c moˆ˜i thuoˆ.c t´ınh cu’a ma’nh du
.o.. c thay bo
.’ i moˆ. t da. i lu
.o.. ng
ha`˘ng thay cho ca´c mie`ˆn D cu’a thuoˆ.c t´ınh do´. Tru
.´o.c heˆ´t tieˆ´n ha`nh phaˆn ma’nh quan heˆ. R
tha`nh ca´c ma’nh ngang co´ moˆ. t soˆ´ thuoˆ.c t´ınh co´ gia´ tri. la˘.p (ca´c ma’nh na`y co´ theˆ’ giao nhau).
Sau do´ taˆ.p ho
.
. p ca´c thuoˆ.c t´ınh co´ gia´ tri. la˘.p la. i vo´
.i nhau deˆ’ ta.o ra ma’nh hoˆ˜n ho
.
. p.
V´ı du. , cho quan heˆ. R\KeyR, Size(TenHuyen) = 20, Size(DanhHieu) = 15, Size(Muc)
= 10, Size(LyDoNhanDanhHieu) = 25, ...
PHAˆN MA’NH TREˆN GIA´ TRI. LA˘. P CU
’A CA´C THUOˆ. C TI´NH 91
TenHuyen DanhHieu Muc LyDoNhanDanhHieu 
Thanh Oai Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Thanh Oai Huy chu.o.ng Choˆ´ng My˜
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng Pha´p
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Ba V`ı Huaˆn chu.o.ng Ha.ng hai Choˆ´ng Pha´p
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Ca´c ma’nh ngang co´ theˆ’ co´ la` (trong ca´c ma’ng sau chı’ giu˜. la. i ca´c gia´ tri. la˘.p).
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Thanh Oai
Thanh Oai
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba V`ı
Ba V`ı
Ba V`ı
Ba V`ı
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Choˆ´ng Pha´p
Choˆ´ng Pha´p
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
92 LEˆ HUY THAˆ. P
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Thanh Oai Choˆ´ng My˜
Thanh Oai Choˆ´ng My˜
TenHuyen DanhHieu Muc ...
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Deˆ’ vieˆ.c phaˆn ma’nh hieˆ.u qua’, moˆ. t soˆ´ ma’nh ngang se˜ khoˆng du
.o.. c tham gia va`o phaˆn ma’nh
do.c. Die`ˆu na`y du
.o.. c theˆ’ hieˆ.n bo
.’ i Di.nh ly´ 1 sau daˆy.
Ky´ hieˆ.u
Size(HV ) = [Card(HV )− 2]
hv∑
j=1
Size(Aj) (12)
trong do´, Aj , j = 1, hv la` ca´c thuoˆ.c t´ınh khoˆng kho´a cu’a HV.
Card(HV ) la` soˆ´ boˆ. co´ trong ma’nh HV.
Size(Aj) la` doˆ. roˆ.ng cu’a thuoˆ.c t´ınh Aj .
Di.nh ly´ 1. Phaˆn ma’nh hoˆ˜n ho
.
. p HV hieˆ.u qua’ khi Size(HV ) > 0 hay Card(HV ) > 2.
Chu´.ng minh. Do
hv∑
j=1
Size(Aj) > 0 neˆn Size(HV ) > 0 khi Card(HV ) > 2. Nhu. vaˆ.y ma’nh
HV co´ ı´t nhaˆ´t 3 boˆ. . Co´ theˆ’ du`ng moˆ.t ma’ng hai chie`ˆu hai ha`ng va` hv coˆ. t. Moˆ.t ha`ng deˆ’ lu
.u
tru˜. ca´c thuoˆ.c t´ınh cu’a HV, ha`ng co`n la. i lu
.u tru˜. ca´c gia´ tri. tu
.o.ng u´.ng vo´.i ca´c thuoˆ.c t´ınh cu’a
moˆ.t boˆ. . Nhu
. vaˆ.y, chu´ng ta tieˆ´t kieˆ.m du
.o.. c moˆ.t boˆ. gia´ tri. khoˆng pha’i lu
.u tru˜.. 

Heˆ. qua’ 1. Ky´ hieˆ.u Card(βij) la` soˆ´ boˆ. thu du
.o.. c khi phaˆn ma’nh ngang vo´
.i meˆ. nh de`ˆ do
.n gia’n
βij, i = 1, nr, j = 1, n th`ı khi phaˆn ma’nh chu´ng khoˆng ca`ˆn quan taˆm deˆ´n thuoˆ. c t´ınh Aj ma`
Card(βij) 
 2 ∀i, ngh˜ıa la` co´ theˆ’ loa. i di taˆ´t ca’ ca´c meˆ.nh de`ˆ do
.n gia’n Pj trong P ([2]).
PHAˆN MA’NH TREˆN GIA´ TRI. LA˘. P CU
’A CA´C THUOˆ. C TI´NH 93
Theo Di.nh ly´ 1 va` Heˆ. qua’ 1, th`ı ngay tu`
. da`ˆu ta da˜ co´ theˆ’ loa. i di ca´c ma’nh ngang chı’ co´
hai boˆ. , v`ı vaˆ.y ca´c ma’nh ngang o
.’ v´ı du. treˆn co`n du
.o.. c giu˜
. la. i la`:
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba V`ı
Ba V`ı
Ba V`ı
Ba V`ı
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba Vı` Huaˆn chu.o.ng
Ba Vı` Huaˆn chu.o.ng
Ba Vı` Huaˆn chu.o.ng
Ba Vı` Huaˆn chu.o.ng
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
94 LEˆ HUY THAˆ. P
Tieˆ´n ha`nh phaˆn ma’nh hoˆ˜n ho.. p, ch´ınh la` phaˆn ma’nh do.c, trong tru
.`o.ng ho.. p na`y la` phaˆn
ma’nh do.c cu’a ca´c ma’nh ngang co`n du
.o.. c giu˜
. la. i treˆn (tu´
.c la` ta´ch laˆ´y ca´c pha`ˆn co´ chu˜. o.’ ca´c
ma’nh ngang treˆn).
Di.nh ly´ 2. Ca´c ma’nh hoˆ˜n ho
.
. p nhaˆ. n du
.o.. c tu`
. vieˆ. c phaˆn ma’nh do. c ca´c ma’nh ngang co´ soˆ´
boˆ. lo´
.n ho.n hai, vo´.i ca´c thuoˆ. c t´ınh tham gia va`o meˆ.nh de`ˆ hoˆ. i so
. caˆ´p deˆ’ co´ ma’nh ngang cu`ng
vo´.i ca´c boˆ. cu’a ma’nh ngang do´.
Chu´.ng minh.
Nhu. chu´ng ta da˜ quy di.nh vieˆ.c phaˆn ma’nh hoˆ˜n ho
.
. p qua hai bu
.´o.c: Da`ˆu tieˆn phaˆn ma’nh
ngang, sau do´ phaˆn ma’nh do.c ca´c ma’nh ngang da˜ nhaˆ.n du
.o.. c. Soˆ´ boˆ. lo´
.n ho.n 2 la` keˆ´t qua’
cu’a Di.nh ly´ 1.
Co`n ca´c thuoˆ.c t´ınh cu’a ma’nh hoˆ˜n ho
.
. p la` ca´c thuoˆ.c t´ınh tham gia va`o meˆ.nh de`ˆ hoˆ. i so
. caˆ´p
deˆ’ co´ ma’nh ngang do´ cu`ng vo´.i ca´c boˆ. cu’a chu´ng.
A´p Di.nh ly´ 2 va`o v´ı du. treˆn ta co´ ca´c ma’nh hoˆ˜n ho
.
. p sau:
TenHuyen
Ba V`ı
Ba V`ı
Ba V`ı
Ba V`ı
DanhHieu
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Huaˆn chu.o.ng
Muc
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
Ha.ng nhaˆ´t
LyDoNhanDanhHieu
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
Choˆ´ng My˜
HV1 HV2 HV3 HV4
TenHuyen DanhHieu
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
Ba V`ı Huaˆn chu.o.ng
TenHuyen DanhHieu Muc
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
Ba V`ı Huaˆn chu.o.ng Ha.ng nhaˆ´t
HV5 HV6
DanhHieu Muc
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
Huaˆn chu.o.ng Ha.ng nhaˆ´t
HV7
Di.nh ly´ 3. Trong taˆ´t ca’ ca´c ma’nh hoˆ˜n ho
.
. p nhaˆ. n du
.o.. c th`ı cho. n ma’nh HV sao cho Size(HV )
lo´.n nhaˆ´t la` hieˆ. u qua’ nhaˆ´t.
Chu´.ng minh.
A´p du.ng Di.nh ly´ 3 ta t´ınh k´ıch thu
.´o.c cu’a ca´c ma’nh hoˆ˜n ho.. p o
.’ v´ı du. treˆn theo coˆng thu´
.c
Size(HV ) = [Card(HV )− 2]
hv∑
i=1
Size(Ai),
vo´.i Size(TenHuyen) = 20, Size(DanhHieu) = 15, Size(Muc) = 10,
Size(LyDoNhanDanhHieu) = 25
PHAˆN MA’NH TREˆN GIA´ TRI. LA˘. P CU
’A CA´C THUOˆ. C TI´NH 95
Size(HV1) = [4− 2]× Size(TenHuyen) = 2× 20 = 40
Size(HV2) = [5− 2]× Size(DanhHieu) = 3× 15 = 45
Size(HV3) = [4− 2]× Size(Muc) = 2× 10 = 20
Size(HV4) = [4− 2]× Size(LyDoNhanDanHieu) = 2× 25 = 50
Size(HV5) = [4− 2]× (Size(TenHuyen) + Size(DanhHieu)) = 2× (20 + 15) = 70
Size(HV6) = [3− 2]× (Size(TenHuyen) + Size(DanhHieu) + Size(Muc))
= 20 + 15 + 10 = 45
Size(HV7) = [3− 2]× (Size(DanhHieu) + Size(Muc)) = 15 + 10 = 25
Cho.n ma’nh HV5 v`ı Size(HV5 ) = 70 lo´
.n nhaˆ´t.
Ghi la. i ma’nh HV5 bo
.’ i moˆ. t nha˜n.
La`m la. i tu`
. da`ˆu vo´.i ca´c ma’nh:
R1
TenHuyen DanhHieu Muc LyDoNhanDanhHieu ...
Thanh Oai Huaˆn chu.o.ng Ha.ng nhaˆ´t Choˆ´ng My˜
Thanh Oai Huy chu.o.ng Choˆ´ng My˜
R2
Muc LyDoNhanDanhHieu ...
Ha.ng nhaˆ´t Choˆ´ng Pha´p
Ha.ng nhaˆ´t Choˆ´ng My˜
Ha.ng hai Choˆ´ng Pha´p
Ha.ng nhaˆ´t Choˆ´ng My˜


3.3. Thuaˆ. t toa´n
3.3.1. Moˆ ta’ thuaˆ. t toa´n
Trong quan heˆ. R:
+ Khoˆng xe´t deˆ´n ca´c thuoˆ.c t´ınh co´ taˆ´t ca’ ca´c gia´ tri. la˘.p nho’ ho
.n 3 (nhu. vaˆ.y ca´c ma’nh ngang
de`ˆu co´ soˆ´ boˆ. lo´
.n ho.n hoa˘.c ba`˘ng 3).
+ Khoˆng xe´t deˆ´n ca´c thuoˆ.c t´ınh co´ mie`ˆn gia´ tri. la` moˆ.t ha`˘ng (v`ı co´ theˆ’ thay thuoˆ.c t´ınh do´
bo.’ i moˆ. t da. i lu
.o.. ng ha`˘ng).
+ Tieˆ´n ha`nh phaˆn ma’nh ngang.
+ Tieˆ´n ha`nh phaˆn ma’nh do.c ca´c ma’nh ngang da˜ co´ deˆ’ du
.o.. c ca´c ma’nh hoˆ˜n ho
.
. p.
+ T´ınh Size cho taˆ´t ca’ ca´c ma’nh nhaˆ.n du
.o.. c.
+ Cho.n ma’nh co´ Size lo´
.n nhaˆ´t va` da´nh daˆ´u ba`˘ng nha˜n (ma’ng hai chie`ˆu) HVmax.
+ Phaˆn ma’nh ba’ng CSDL goˆ´c deˆ’ du.o.. c ca´c ba’ng mo´
.i nhu. sau:
R1 = R\{ Ca´c boˆ. tham gia va`o ma’nh co´ nha˜n HVmax}.
R2 = { Ma’nh ngang du`ng deˆ’ phaˆn ma’nh hoˆ˜n ho
.
. p deˆ’ co´ nha˜n HVmax}\{ Ca´c thuoˆ. c co´
trong ma’nh hoˆ˜n ho.. p co´ nha˜n HVmax}
+ Tieˆ´n ha`nh phaˆn ma’nh la. i tu`
. da`ˆu doˆ´i vo´.i R1 va` R2 (Tu´
.c la` thay R bo.’ i R1, R2 va` la˘.p la. i
thuaˆ. t toa´n).
3.3.2. Thuaˆ. t toa´n
Nha˘´c la. i moˆ.t soˆ´ thoˆng tin lieˆn quan thuaˆ.t toa´n. Ky´ hieˆ.u:
96 LEˆ HUY THAˆ. P
nr = Cardr(R) la` lu
.
. c lu
.o.. ng ha`ng cu’a quan heˆ. R (la` soˆ´ boˆ. hieˆ.n co´), P = {P1, P2, ..., Pn},
trong do´ Pj la` taˆ.p ca´c meˆ.nh de`ˆ do
.n gia’n treˆn thuoˆ. c t´ınh Aj , j = 1, n. Cu. theˆ’ Pj la` taˆ.p ca´c
meˆ.nh de`ˆ so sa´nh ba˘`ng. Tu´
.c la` P ′j = {βij}, j = 1, n, trong do´ βij = dij ∈ Dom(Aj), P
′
j ky´
hieˆ.u chuyeˆ’n vi. cu’a Pj hay P = {βij}nr×n la` ma traˆ.n caˆ´p nr × n.
Nhu. vaˆ.y soˆ´ meˆ.nh de`ˆ do
.n gia’n co´ theˆ’ co´ treˆn quan heˆ. R la` m = nr × n.
Ky´ hieˆ.u Q = {q1, q2, ..., qn} la` taˆ.p ca´c taˆ.p meˆ.nh de`ˆ hoˆ. i so
. caˆ´p treˆn R trong do´ qk du
.o.. c
ta.o ra nhu
. sau:
U´
.
ng vo´.i moˆ˜i soˆ´ k, k = 1, n, go. i taˆ.p K ⊆ {1, 2, ..., n} sao cho Card(K) = k. Da˘. t:
qik = Λ
j∈K
βij , ∀i.
Nhu. vaˆ.y co´ theˆ’ thaˆ´y Card(Q) =
n∑
k=1
Ckm, trong do´ C
k
m =
m!
k!(m− k)!
.
Bu.´o.c 1.
k = 1, ∀βij ∈ qi1
SELECT *
FROM R
WHERE βij
Du.o.. c ma’nh ngang Hij .
Bu.´o.c 2. Neˆ´u ∀i, j, Card(Hij) 
 2 deˆ´n Bu
.´o.c 7 (v`ı khoˆng co´ thuoˆ.c t´ınh na`o co´ soˆ´ ca´c gia´ tri.
la˘.p lo´
.n ho.n 2). Ngu.o.. c la. i deˆ´n Bu
.´o.c 3.
Bu.´o.c 3. Phaˆn ma’nh do.c tu`
. ca´c ma’nh ngang Hj1 treˆn deˆ’ co´ ca´c ma’nh hoˆ˜n ho
.
. p va` t`ım ma’nh
hoˆ˜n ho.. p ma` Size(HV
∗
1 ) = max Size(HVj1). Ky´ hieˆ.u HVmax = HV
∗
1 , max = Size(HV
∗
1 ).
Sang Bu.´o.c 4.
Bu.´o.c 4.
k = k + 1
i = 0
Sang Bu.´o.c 5.
Bu.´o.c 5.
i = i + 1
SELECT *
FROM R
WHERE qik
Du.o.. c ma’nh ngang Hik.
Neˆ´u Card(Hik) <= 2 deˆ´n Bu
.´o.c 6.
Ngu.o.. c la. i, phaˆn ma’nh do.c tu`
. ca´c ma’nh ngang Hjk treˆn deˆ’ co´ ca´c ma’nh hoˆ˜n ho
.
. p va` t`ım
ma’nh hoˆ˜n ho.. p ma` Size(HV
∗
ik) = max(HVik).
Neˆ´u max < Size(HV ∗ik)
max = Size(HV ∗ik)
HVmax = HV
∗
ik
Sang Bu.´o.c 6.
Bu.´o.c 6.
Neˆ´u i < nr quay la. i Bu
.´o.c 5.
PHAˆN MA’NH TREˆN GIA´ TRI. LA˘. P CU
’A CA´C THUOˆ. C TI´NH 97
Ngu.o.. c la. i, neˆ´u k 
 n quay la. i Bu
.´o.c 4
Ngu.o.. c la. i, ga´n nha˜n HVmax va` da˘. t:
R1 = R\{ Ca´c boˆ. tham gia va`o ma’nh co´ nha˘n HVmax}.
R2 = { Ma’nh ngang du`ng deˆ’ phaˆn ma’nh hoˆ˜n ho
.
. p deˆ’ co´ nha˜n HVmax{Ca´c thuoˆ.c co´
trong ma’nh hoˆ˜n ho.. p co´ nha˜n HVmax}.
Thay R bo.’ i R1, la˘.p la. i Bu
.´o.c 1.
Thay R bo.’ i R2, la˘.p la. i Bu
.´o.c 1.
Bu.´o.c 7. Cho ra ca´c ma’nh (neˆ´u co´). Keˆ´t thu´c thuaˆ. t toa´n.
Di.nh ly´ 4.
1) Soˆ´ ma’nh hoˆ˜n ho.. p co´ hoa˘. c khoˆng co´, neˆ´u co´ th`ı khoˆng vu
.o.. t qua´ int(Card(R) × n/3),
trong do´ n la` soˆ´ thuoˆ. c t´ınh khoˆng kho´a cu’a R.
2) Thuaˆ. t toa´n keˆ´t thu´c sau moˆ. t soˆ´ hu˜
.u ha. n bu
.´o.c.
Chu´.ng minh.
1) Ro˜ ra`ng la` ma’nh hoˆ˜n ho.. p nho’ nhaˆ´t la` ma’nh chı’ co´ moˆ. t thuoˆ.c t´ınh va` moˆ. t gia´ tri..
Vı` vaˆ.y soˆ´ ma’nh hoˆ˜n ho
.
. p nhie`ˆu nhaˆ´t trong tru
.`o.ng ho.. p na`y la` (Card(R) × n. Nhu
.ng theo
Di.nh ly´ 1 th`ı ca´c ma’nh pha’ i co´ soˆ´ boˆ. lo´
.n ho.n hoa˘.c ba˘`ng 3 mo´
.i co´ hieˆ.u qua’ . Vı` vaˆ.y soˆ´ ma’nh
nhie`ˆu nhaˆ´t cu˜ng chı’ ba˘`ng int(Card(R)× n/3).
2) Die`ˆu na`y du.o.. c suy ra tu`
. 1). 

4. KE´ˆT LUAˆ. N
Vieˆ.c tieˆ´t kieˆ.m khoˆng gian lu
.u tru˜. thoˆng tin, ru´t nga˘´n tho`.i gian truy nhaˆ.p du˜
. lieˆ.u va` cu
.
. c
tieˆ’u hoa´ chi ph´ı khi caˆ´p pha´t du˜. lieˆ.u la` mu. c d´ıch ha`ng da`ˆu cu’a ngu
.`o.i laˆ.p tr`ınh va` ngu
.`o.i
su.’ du.ng. Ba`i ba´o na`y gia’ i quyeˆ´t vaˆ´n de`ˆ treˆn ba˘`ng ca´ch gom nho´m va` du`ng b´ı danh deˆ’ da. i
dieˆ.n cho nho´m ca´c boˆ. co´ ca´c thuoˆ.c t´ınh co´ ca´c gia´ tri. la˘.p la. i.
Coˆng tr`ınh da˜ du.o.. c u´
.ng du.ng deˆ’ qua’n ly´ coˆng ta´c la`m ba´o ca´o nhu
.: Ba´o ca´o doˆ. t xuaˆ´t,
Ba´o ca´o di.nh ky` cu’a ca´c huyeˆ.n thi., so
.’ nga`nh (Tha´ng, Quy´, 6 tha´ng,...). Qua’n ly´ thi dua
khen thu.o.’ ng, ngu.`o.i co´ coˆng ca´ch ma.ngtrong tı’nh ta. i ca´c thi. xa˜, huyeˆ.n va` va˘n pho`ng UBND
tı’nh Ha` Taˆy.
5. HU
.
O´
.
NG PHA´T TRIEˆ’N
Nghieˆn cu´.u moˆ h`ınh caˆ´p pha´t deˆ’ la`m gia’m chi ph´ı, tho`.i gian xu.’ ly´ va` khoˆng gian lu.u
tru˜.,... treˆn co. so.’ ca´c ma’nh hoˆ˜n da˜ du.o.. c ta.o ra, ngh˜ıa la` ta ca`ˆn nghieˆn cu´
.u moˆ h`ınh:
min(Total Cost)
Vo´.i ca´c ra`ng buoˆ.c
Tho`.i gian xu.’ ly´ ca´c caˆu truy vaˆ´n
Khoˆng gian lu.u tru˜.
...
98 LEˆ HUY THAˆ. P
TA`I LIEˆ. U THAM KHA
’O
[1] M. Tamer Ozsu, Patrick Valduriez, Nguyeˆn ly´ ca´c heˆ. co
. du˜. lieˆ. u phaˆn ta´n, Tra`ˆn Du´
.c
Quang bieˆn di.ch, NXB Thoˆ´ng keˆ, 1999.
[2] Leˆ Tieˆ´n Vu.o.ng, Nhaˆ. p moˆn co
. so.’ du˜. lieˆ. u quan heˆ. , NXB Thoˆ´ng Keˆ, 2000.
[3] Doˆ˜ Xuaˆn Loˆi, Caˆ´u tru´c du˜. lieˆ. u va` gia’ i thuaˆ. t, NXB Khoa ho.c va` Ky˜ thuaˆ. t, 1996.
[4] Robert Sedgewick, Caˆ’m nang thuaˆ. t toa´n, Vol.1 and Vol.2, NXB Khoa ho.c va` Ky˜ thuaˆ. t,
2001.
Nhaˆ. n ba`i nga`y 20 - 12 - 2002
Nhaˆ. n la. i sau su
.’ a nga`y 15 - 3 -2007