Mô hình dữ liệu đối với các truy vấn định lượng

 Hai phe´p toa´n
mo´.i: phe´p nho´m va` phe´p mo.’ nho´m la` ca`ˆn thieˆ´t deˆ’ di.nh ngh˜ıa ca´c phe´p toa´n da. i soˆ´ treˆn ca´c
quan heˆ. nho´m. Chu´ y´ ra`˘ng, moˆ˜i quan heˆ. nho´m pha’i tu
.o.ng du.o.ng vo´.i moˆ.t quan heˆ. nguyeˆn
toˆ´ duy nhaˆ´t doˆ´i vo´.i ca´c caˆ´u tru´c phaˆn caˆ´p da˜ cho. Co´ ngh˜ıa la`, co´ moˆ.t moˆ h`ınh duy nhaˆ´t vo´
.i
ca´c gia´ tri. nguyeˆn toˆ´ (ca´c gia´ tri. thuoˆ.c mie`ˆn goˆ´c cu’a thuoˆ.c t´ınh) tho’a ma˜n quan heˆ. da˜ cho.
Moˆ. t phe´p toa´n na`o do´ treˆn ca´c quan heˆ. nho´m se˜ co´ cu`ng ta´c doˆ.ng baˆ´t keˆ’ no´ du
.o.. c thu
.
. c hieˆ.n
treˆn ca´c quan heˆ. nho´m hay treˆn ca´c quan heˆ. nguyeˆn toˆ´ tu
.o.ng du.o.ng. Theo ngh˜ıa na`y, ngu˜.
ngh˜ıa cu’a ca´c phe´p toa´n quan heˆ. la` khoˆng bi. thay doˆ’i ngay ca’ trong tru
.`o.ng ho.. p vo´
.i ca´c quan
heˆ. nho´m.
Deˆ’ tr`ınh ba`y ca´c phe´p toa´n treˆn ca´c quan heˆ. nho´m, tru
.´o.c tieˆn, chu´ng toˆi tr`ınh ba`y moˆ. t
thuaˆ.t toa´n kha´ do
.n gia’n cho phe´p di.ch moˆ. t taˆ.p ca´c gia´ tri. trong moˆ.t D
+ vo´.i HD tu.o.ng u´.ng
cu’a moˆ. t thuoˆ.c t´ınh A na`o do´ tha`nh ca´c lo´
.p toˆ’ng qua´t ho.n trong HD va` cho phe´p co´ ngoa. i
leˆ. . Vo´
.i ca´c loa. i caˆu truy vaˆ´n di.nh lu
.o.. ng kha´c nhau, chu´ng ta co´ theˆ’ su
.’ du. ng ca´c thuaˆ.t toa´n
di.ch kha´c nhau vo´
.i ca´c tieˆu ch´ı nho´m kha´c nhau. O
.’ daˆy, chu´ng toˆi chı’ quan taˆm deˆ´n ca´c truy
vaˆ´n vo´.i lu.o.. ng tu`
. ∀ va` bo.’ i vaˆ.y, tieˆu ch´ı nho´m cu’a chu´ng toˆi la` nho´m taˆ´t ca’ ca´c nu´t du
.o.ng
co´ cu`ng cha la. i khi soˆ´ ca´c ngoa. i leˆ. hay ca´c nu´t aˆm cu’a chu´ng la` nho’ ho
.n. Trong thu.. c teˆ´, vo´
.i
moˆ. t su
.
. phaˆn nho´m ca´c doˆ´i tu
.o.. ng ho
.
. p ly´, soˆ´ ca´c ngoa. i leˆ. thu
.`o.ng la` kha´ nho’ hay thu.. c chaˆ´t la`
khoˆng da´ng keˆ’.
Cho moˆ. t thuoˆ. c t´ınh A du
.o.. c keˆ´t ho
.
. p vo´
.i mie`ˆn D co´ moˆ.t caˆ´u tru´c phaˆn caˆ´p HD va` S ⊂ D
+
vo´.i D+ - k´ı hieˆ.u taˆ.p taˆ´t ca’ ca´c nu´t cu’a HD.
Thuaˆ.t toa´n 1. T´ınh ca´c lo´
.p toˆ’ng qua´t cu’a S ⊂ D+ va` ca´c ngoa. i leˆ..
MOˆ. T MOˆ HI`NH DU˜
.
LIEˆ. U DO´ˆI VO´
.
I CA´C TRUY VA´ˆN DI.NH LU
.
O.
.
NG 45
Va`o: Thuoˆ.c t´ınh A, mie`ˆn D, caˆ´u tru´c phaˆn caˆ´p HD va` S ⊂ D
+.
Ra: T´ınh Lo´.p (S) va` NgL(S).
Ca´ch t´ınh:
• T`ım nu´t cha chung nho’ nhaˆ´t cu’a S doˆ´i vo´.i HD va` k´ı hieˆ.u nu´t na`y la` Rt.
• Kı´ hieˆ.u caˆy con cu’a HD vo´
.i nu´t goˆ´c la` Rt va` ca´c nu´t la´ la` ca´c nu´t hoa˘. c thuoˆ.c S hoa˘. c la` ca´c
nu´t anh em cu’a ca´c nu´t trong S la` T.
• Da´nh daˆ´u ca´c nu´t la´ thuoˆ.c S la` +
• Da´nh daˆ´u ca´c nu´t la´ khoˆng thuoˆ.c S la` −
• Doˆ´i vo´.i moˆ˜i nu´t trong N cu’a T , k´ı hieˆ.u caˆy con cu’a T goˆ´c ta. i N la` TN va` k´ı hieˆ.u S
+
N la`
taˆ.p ca´c nu´t la´ du
.o.. c da´nh daˆ´u +, S
−
N la` taˆ.p ca´c nu´t la´ du
.o.. c da´nh daˆ´u - doˆ´i vo´
.i TN . T´ınh
x = |S+N | va` y = |S
−
N |. Moˆ.t nu´t N co´ x > y du
.o.. c go. i la` nu´t toˆ´t, ngu
.o.. c la. i du
.o.. c go. i la` nu´t
toˆ`i.
• Da˘.t N := Rt. Go. i thu’ tu. c Cho.n (N, TN , S
+
N , S
−
N)
• Thu’ tu. c cho.n nu´t Cho.n (N, TN , S
+
N , S
−
N):
1) Neˆ´u N la` nu´t la´ va` du.o.. c da´nh daˆ´u + th`ı Lo´
.p(S+N) = N, NgL(S
+
N) = ∅
2) Neˆ´u N la` nu´t toˆ´t co´ m con tru.. c tieˆ´p la` N1, N2, ...., Nm va` khoˆng maˆ´t t´ınh toˆ’ng qua´t,
gia’ su.’ N1, N2, ...., Nk la` ca´c nu´t toˆ`i va` Nk+1, N2, ...., Nm la` ca´c nu´t toˆ´t.
Neˆ´u 1+
∑k
1 yi < m−k+
∑k
1 xi vo´
.i xi = |S
+
Ni| va` yi = |S
−
Ni| th`ı Lo´
.p(S+N) = N, NgL(S
+
N) =
S−N va` keˆ´t thu´c.
Ngu.o.. c la. i, thu
.
. c hieˆ.n Cho.n (Ni, TNi, S
+
Ni, S
−
Ni) vo´
.i i = 1..m va` da˘.t Lo´
.p(S+N) = ∪
m
1
Lo´.p(S+Ni), NgL(S
+
N) = ∪
m
1 NgL(S
+
Ni).
3) Neˆ´uN la` nu´t toˆ`i co´ m con tru.. c tieˆ´p la`N1, N2, ...., Nm, thu
.
. c hieˆ.n Cho.n(Ni, TNi, S
+
Ni, S
−
Ni)
vo´.i i = 1..m va` da˘.t Lo´
.p(S+N) = ∪
m
1 Lo´
.p(S+Ni), NgL(S
+
N) = ∪
m
1 NgL(S
+
Ni).
• Da˘.t Lo´
.p(S) = Lo´.p(S+Rt) va` NgL(S) = NgL(S
+
Rt)
Meˆ.nh de`ˆ 1. Cho moˆ. t thuoˆ. c t´ınh A du
.o.. c keˆ´t ho
.
. p vo´
.i mie`ˆn D co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p
HD va` S ⊂ D+. K´ı hieˆ.u DTu
.o.. ng (S) la` taˆ. p taˆ´t ca’ ca´c doˆ´i tu
.o.. ng thuoˆ. c ca´c lo´
.p trong S th`ı
DTu.o.. ng (S) = DTu
.o.. ng (Lo´
.p(S)) \ DTu.o.. ng (NgL(S)).
Chu´.ng minh. De˜ˆ thaˆ´y, do caˆ´u tru´c phaˆn caˆ´p HD, taˆ.p taˆ´t ca’ ca´c doˆ´i tu
.o.. ng thuoˆ.c moˆ. t lo´
.p
ch´ınh la` ho.. p cu’a taˆ.p taˆ´t ca’ ca´c doˆ´i tu
.o.. ng thuoˆ.c ca´c lo´
.p con cu’a no´. Bo.’ i vaˆ.y, chu´ng ta co´
DTu.o.. ng (Lo´
.p(S)) = DTu.o.. ng (S) ∪DTu
.o.. ng (NgL(S)). Ho
.n nu˜.a, DTu.o.. ng (S) va` DTu
.o.. ng
(NgL(S)) la` ro`.i nhau. Do vaˆ.y, ta co´ die`ˆu pha’ i chu´
.ng minh. 
Phe´p mo.’ nho´m: Cho quan heˆ. nho´m R(X, Y, T ) vo´
.i ca´c thuoˆ.c t´ınh A ∈ Y du
.o.. c keˆ´t ho
.
. p vo´
.i
moˆ. t mie`ˆn D va` co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p HD va` ca´c thuoˆ.c t´ınh thuoˆ.c X khoˆng du
.o.. c keˆ´t
ho.. p vo´
.i moˆ.t caˆ´u tru´c phaˆn caˆ´p na`o. X hoa˘.c Y co´ theˆ’ ba`˘ng ∅ nhu
.ng XY 6= ∅.
Gia’ su.’ Y = {A1, A2, ..., Ak}, v[Y ] = (C1, C2, ..., Ck) va` moˆ.t boˆ. nguyeˆn toˆ´ t[Y ] =
(c1, c2, ..., ck) vo´
.i ci ∈ Di - mie`ˆn cu’a Ai. Chu´ng ta vieˆ´t t[Y ] ∈ v[Y ] neˆ´u vo´.i i = 1..k th`ı
ci ∈ Ci. Phe´p mo.’ nho´m doˆ´i vo´.i quan heˆ. nho´m R, k´ı hieˆ.u la` Mo
.’ Nho´m(R) du.o.. c di.nh ngh˜ıa
nhu. sau:
Mo.’ Nho´m(R) = {t[XY ]/∃v ∈ R(t[X ] = v[X ]∧ t[Y ] = y∧ y ∈ v[Y ]∧ v[T ] = ‘true′∧ 6 ∃v′ ∈
46 NGUYE˜ˆN KIM ANH
R (v′[X ] = v[X ]∧ v′[T ] = ‘false′ ∧ y ∈ v′[Y ]))}.
Chu´ y´: Phe´p mo.’ nho´m tra’ la. i keˆ´t qua’ la` moˆ.t quan heˆ. nguyeˆn toˆ´ thoˆng thu
.`o.ng, quan heˆ. chı’
chu´.a ca´c gia´ tri. nguyeˆn toˆ´ va` khoˆng chu´
.a thuoˆ.c t´ınh T lu
.u gia´ tri. chaˆn ly´ cu’a boˆ. . Ho
.n nu˜.a,
phe´p toa´n Mo.’ Nho´m da’m ba’o moˆ˜i quan heˆ. nho´m la` tu
.o.ng du.o.ng vo´.i moˆ. t quan heˆ. nguyeˆn toˆ´
duy nhaˆ´t doˆ´i vo´.i ca´c caˆ´u tru´c phaˆn caˆ´p da˜ cho.
Phe´p nho´m: Cho moˆ. t quan heˆ. nho´m R xa´c di.nh treˆn taˆ.p thuoˆ.c t´ınh U vo´
.i moˆ.t thuoˆ.c t´ınh
A ∈ U na`o do´ du.o.. c keˆ´t ho
.
. p vo´
.i moˆ. t mie`ˆn D va` co´ moˆ.t caˆ´u tru´c phaˆn caˆ´p HD. Kı´ hieˆ.u R
+
la` taˆ.p ca´c boˆ. du
.o.ng cu’a R va` R la` taˆ.p ca´c boˆ. aˆm cu’a R. Phe´p nho´m quan heˆ. nho´m R theo
thuoˆ.c t´ınh A, k´ı hieˆ.u la` Nho´mA(R) du
.o.. c di.nh ngh˜ıa nhu
. sau:
Nho´mA(R
+) = {t/(v ∈ R+(t[U\TA] = v[U\TA] ∧ ((t[A] = {C/∃C ∈ Lo´.p (S)} ∧ t[T ] =
‘true′) ∨ (t[A] = {C/∃C ∈ NgL(S)} ∧ t[T ] = ‘false′)) ∧ S = ∪v[A] vo´.i ca´c v ∈ R+ tho’a
t[U\A] = v[U\A])}.
Nho´mA(R) = Nho´mA(R
+) ∪ R−.
Chu´ y´: Trong qua´ tr`ınh nho´m, chu´ng ta luoˆn coˆ´ ga˘´ng nho´m nhie`ˆu nhaˆ´t co´ theˆ’ ca´c lo´.p con
xuaˆ´t hieˆ.n trong thuoˆ.c t´ınh A cu’a ca´c boˆ. du
.o.ng tha`nh moˆ.t lo´
.p toˆ’ng qua´t ho.n vo´.i vieˆ.c chaˆ´p
nhaˆ.n moˆ. t soˆ´ ngoa. i leˆ. khoˆng da´ng keˆ’ neˆn taˆ.p ca´c boˆ. thuoˆ.c Nho´mA(R
+) va` R− la` ro`.i nhau.
Meˆ.nh de`ˆ 2. Phe´p toa´n Nho´m ba’o toa`n noˆ. i dung thoˆng tin cu’a quan heˆ. nho´m ban da`ˆu.
Co´ ngh˜ıa la` vo´.i moˆ. t quan heˆ. nho´m R va` moˆ. t thuoˆ. c t´ınh A co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p th`ı
Mo.’ Nho´m(Nho´mA(R)) = Mo.’ Nho´m(R).
Chu´.ng minh. Theo di.nh ngh˜ıa cu’a ca´c phe´p toa´n Mo
.’ Nho´m, Nho´m va` t´ınh du´ng da˘´n cu’a
Thuaˆ.t toa´n 1 du
.o.. c kha˘’ ng di.nh trong meˆ.nh de`ˆ 1, moˆ˜i boˆ. x vo´
.i ca´c gia´ tri. nguyeˆn toˆ´ thuoˆ.c
Mo.’ Nho´m(Nho´mA(R)) cu˜ng thuoˆ. c Mo
.’ Nho´m(R) va` ngu.o.. c la. i. 
Heˆ. qua’ 1. Cho R la` quan heˆ. nho´m nguyeˆn toˆ´ va` moˆ. t thuoˆ. c t´ınh A co´ moˆ. t caˆ´u tru´c phaˆn
caˆ´p. Go. i R’ la` quan heˆ. nguyeˆn toˆ´ doˆ´i vo´
.i R th`ı Mo.’ Nho´m(Nho´mA(R)) = R’.
Heˆ. qua’ 1 du
.o.. c suy ra tru
.
. c tieˆ´p tu`
. Meˆ.nh de`ˆ 2.
Phe´p keˆ´t noˆ´i tu.. nhieˆn: Cho hai quan heˆ. nho´m R(U) va` S(V ) vo´
.i U ∩ V = Y Z va` Y =
{A1, A2, ..., Ak}. Ca´c thuoˆ. c t´ınh Ai ∈ Y du
.o.. c keˆ´t ho
.
.p vo´
.i moˆ.t mie`ˆn Di va` co´ moˆ. t caˆ´u tru´c
phaˆn caˆ´p HDi, i = 1..k. Ca´c thuoˆ. c t´ınh thuoˆ.c Z khoˆng du
.o.. c keˆ´t ho
.
. p vo´
.i moˆ. t caˆ´u tru´c phaˆn
caˆ´p na`o. Z co´ theˆ’ ba`˘ng ∅ va` k co´ theˆ’ ba`˘ng 0. Phe´p keˆ´t noˆ´i tu.. nhieˆn cu’a 2 quan heˆ. nho´m R
va` S, k´ı hieˆ.u la` R ∗ S du
.o.. c di.nh ngh˜ıa nhu
. sau:
R ∗ S = {t[UV ]/∃u ∈ R∃v ∈ S(t[U\Y T ] = u[U\Y T ] ∧ t[V \Y T ] = v[V \Y T ] ∧ (t[Ai] =
u[Ai]∩ v[Ai], i = 1..k)∧ t[T ] = u[T ] ∗ v[T ]}, o.’ daˆy ‘true
′ ∗ ‘true′ = ‘true′ va` ‘true′ ∗ ‘false′ =
‘false′ ∗ ‘true′ = ‘false′.
Phe´p chieˆ´u: Cho quan heˆ. nho´m R(X, Y, T ) vo´
.i ca´c thuoˆ.c t´ınh A ∈ Y du
.o.. c keˆ´t ho
.
. p vo´
.i moˆ. t
mie`ˆn D va` co´ moˆ.t caˆ´u tru´c phaˆn caˆ´p HD va` ca´c thuoˆ.c t´ınh thuoˆ.c X khoˆng du
.o.. c keˆ´t ho
.
. p vo´
.i
moˆ. t caˆ´u tru´c phaˆn caˆ´p na`o. X va` Y co´ theˆ’ ba`˘ng ∅. Chu´ng toˆi di.nh ngh˜ıa hai phe´p chieˆ´u
treˆn quan heˆ. nho´m R phu. thuoˆ.c va`o taˆ.p thuoˆ.c t´ınh chieˆ´u: Π
0 la` phe´p chieˆ´u vo´.i taˆ.p thuoˆ.c
t´ınh chieˆ´u chı’ lieˆn quan deˆ´n ca´c thuoˆ.c t´ınh khoˆng co´ caˆ´u tru´c phaˆn caˆ´p va` Π
1 la` phe´p chieˆ´u
vo´.i taˆ.p thuoˆ.c t´ınh chieˆ´u co´ lieˆn quan deˆ´n ca´c thuoˆ.c t´ınh co´ caˆ´u tru´c phaˆn caˆ´p.
MOˆ. T MOˆ HI`NH DU˜
.
LIEˆ. U DO´ˆI VO´
.
I CA´C TRUY VA´ˆN DI.NH LU
.
O.
.
NG 47
Π0Z(R) = {t[ZT ]/t ∈ R
+ vo´.i Z ⊆ X va` Z 6= ∅}, o.’ daˆy R+ la` taˆ.p ca´c boˆ. du
.o.ng cu’a R.
Π1Z(R) = {t[ZT ]/t ∈ R vo´
.i Z ⊆ XY va` Z 6= ∅}.
Phe´p cho.n: Cho quan heˆ. nho´m R(X, Y, T ) vo´
.i ca´c thuoˆ.c t´ınh A ∈ Y du
.o.. c keˆ´t ho
.
.p vo´
.i moˆ. t
mie`ˆn D va` co´ moˆ.t caˆ´u tru´c phaˆn caˆ´p HD va` ca´c thuoˆ.c t´ınh thuoˆ.c X khoˆng du
.o.. c keˆ´t ho
.
. p vo´
.i
moˆ. t caˆ´u tru´c phaˆn caˆ´p na`o. Chu´ng toˆi di.nh ngh˜ıa hai phe´p cho.n treˆn quan heˆ. nho´m R phu.
thuoˆ.c va`o da.ng cu’a die`ˆu kieˆ.n cho.n: σ
0 la` phe´p cho.n vo´
.i die`ˆu kieˆ.n cho.n chı’ lieˆn quan deˆ´n ca´c
thuoˆ.c t´ınh khoˆng co´ caˆ´u tru´c phaˆn caˆ´p va` σ
1, σ2 la` phe´p cho.n vo´
.i die`ˆu kieˆ.n cho.n lieˆn quan
deˆ´n ca´c thuoˆ. c t´ınh co´ caˆ´u tru´c phaˆn caˆ´p. Kı´ hieˆ.u R
+ la` taˆ.p ca´c boˆ. du
.o.ng cu’a R,R− la` taˆ.p
ca´c boˆ. aˆm cu’a R. Deˆ’ do
.n gia’n, gia’ thieˆ´t die`ˆu kieˆ.n cho.n co´ lieˆn quan deˆ´n ca´c thuoˆ.c t´ınh co´
caˆ´u tru´c phaˆn caˆ´p co´ da.ng AθC vo´
.i A ∈ Y , C ∈ HD va` θ ∈ {=,⊆,⊇}.
σ0
F (X)(R) = {t/t ∈ R ∧ F (t) = du´ng}
σ1A=C(R) = {t/∃u ∈ R(u[A] ∩C 6= ∅ ∧ t[U\A] = u[U\A]) ∧ t[A] = u[A] ∩C}
σ2A=C(R) = {t/∃u ∈ R
+(u[A] = C ∧ t[U ] = u[U ]) ∨ ∃v ∈ R−(v[A] ⊆ C ∧ t[U ] = u[U ])}.
σ2A⊇C(R) = {t/∃u ∈ R
+(u[A] ⊇ C ∧ t[U ] = u[U ]) ∨ ∃v ∈ R−(v[A] ⊆ C ∧ t[U ] = u[U ])}.
σ2A⊆C(R) = {t/∃u ∈ R
+(u[A] ⊇ C∧t[U ] = u[U ])∨∃v ∈ R−(v[A] ⊆ C∧t[U ] = u[U ])∧v 6∈
R
′−}. vo´.i R
′− la` ca´c boˆ. aˆm cu’a phe´p nho´m da`ˆu tieˆn theo A )}.
Chu´ y´: Phe´p cho.n σ
0 va` σ1 du.o.. c su
.’ du. ng trong tru
.`o.ng ho.. p X 6= ∅ co`n σ
2 du.o.. c su
.’ du. ng
trong tru.`o.ng ho.. p X = ∅ va` quan heˆ. R da˜ du
.o.. c nho´m theo moˆ.t thuoˆ.c t´ınh A ∈ Y da`ˆu tieˆn,
sau do´ co´ theˆ’ tieˆ´p tu. c nho´m theo ca´c thuoˆ. c t´ınh kha´c trong Y.
Ca´c phe´p toa´n taˆ. p ho
.
. p: Deˆ’ thu
.
. c hieˆ.n ca´c phe´p toa´n taˆ.p ho
.
. p: ho
.
.p, tru`
. va` giao, tru.´o.c tieˆn
chu´ng ta thu.. c hieˆ.n phe´p toa´n Mo
.’ Nho´m doˆ´i vo´.i hai quan heˆ. toa´n ha.ng, sau do´ thu
.
. c hieˆ.n ca´c
phe´p toa´n ho.. p, tru`
., giao tu.o.ng u´.ng cu’a da. i soˆ´ quan heˆ. kinh dieˆ’n treˆn hai quan heˆ. thu du
.o.. c.
Cuoˆ´i cu`ng, thu.. c hieˆ.n phe´p Nho´m treˆn quan heˆ. keˆ´t qua’ theo ca´c thuoˆ.c t´ınh mong muoˆ´n, chu´ng
ta se˜ thu du.o.. c quan heˆ. nho´m keˆ´t qua’ cu’a ca´c phe´p toa´n taˆ.p ho
.
. p na`y.
Di.nh ly´ 1. Ca´c phe´p toa´n da. i soˆ´: cho.n (σ
0), chieˆ´u Π(0) va` keˆ´t noˆ´i tu.. nhieˆn treˆn ca´c quan
heˆ. nho´m la` ba’o toa`n ngu˜
. ngh˜ıa baˆ´t keˆ’ no´ du.o.. c thu
.
. c hieˆ.n treˆn ca´c quan heˆ. nho´m hay treˆn
ca´c quan heˆ. nguyeˆn toˆ´ tu
.o.ng du.o.ng.
Chu´.ng minh. Gia’ su.’ P - k´ı hieˆ.u phe´p cho.n (σ
0) hoa˘. c phe´p chieˆ´u Π
(0). Du.. a treˆn di.nh
ngh˜ıa cu’a phe´p cho.n va` phe´p chieˆ´u doˆ´i vo´
.i quan heˆ. nho´m, chu´ng ta co´: Mo
.’ Nho´m(P (R))=
P (Mo.’ Nho´m(R)). Tu.o.ng tu.. vo´
.i phe´p keˆ´t noˆ´i tu.. nhieˆn, moˆ˜i boˆ. x ∈Mo
.’Nho´m(R ∗ S) khi va`
chı’ khi x pha’ i du.o.. c chu´
.a trong moˆ. t boˆ. du
.o.ng cu’a (R ∗ S) va` khoˆng toˆ`n ta. i moˆ. t boˆ. aˆm
cu’a (R ∗ S) chu´.a x, tu´.c la` x khoˆng theˆ’ du.o.. c ghe´p bo
.’ i moˆ.t boˆ. aˆm cu’a R hoa˘. c moˆ. t boˆ. aˆm
cu’a S. Die`ˆu na`y co´ ngh˜ıa la` x ∈ Mo.’Nho´m(R)∗Mo.’Nho´m(R). Do vaˆ.y, Mo
.’ Nho´m(R ∗ S) =
Mo.’ Nho´m(R)∗Mo.’Nho´m(R). 
Chu´ y´: Phe´p toa´n Π1 se˜ khoˆng co`n ba’o toa`n ngu˜. ngh˜ıa khi no´ du.o.. c a´p du. ng sau moˆ. t phe´p
cho.n σ
2. Di.nh ly´ 2 sau daˆy cho thaˆ´y, moˆ. t phe´p toa´n Π
1 se˜ du.o.. c a´p du. ng ngay sau moˆ. t phe´p
cho.n σ
2 co´ ta´c doˆ.ng tu
.o.ng du.o.ng vo´.i moˆ. t phe´p chia cu’a da. i soˆ´ quan heˆ. kinh dieˆ’n.
Meˆ.nh de`ˆ 3. Cho quan heˆ. nho´m R(U) vo´
.i moˆ. t thuoˆ. c t´ınh A ∈ U du
.o.. c keˆ´t ho
.
. p vo´
.i moˆ. t
mie`ˆn D va` co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p HD. Khi do´, ta co´ Mo
.’ Nho´m(σ1A=C(R)) = σA∈C
48 NGUYE˜ˆN KIM ANH
(Mo.’ Nho´m(R)), o.’ daˆy A ∈ C k´ı hieˆ. u bieˆ’u thu´
.c logic A = c1 ∨ A = c2 ∨ ... ∨ A = ck vo´.i
C = {c1, c2, ..., ck}.
Co´ theˆ’ de˜ˆ da`ng chu´.ng minh meˆ.nh de`ˆ na`y du
.
. a treˆn di.nh ngh˜ıa cu’a phe´p toa´n σ
1.
Di.nh ly´ 2. Cho moˆ. t quan heˆ. nho´m R xa´c di.nh treˆn taˆ. p thuoˆ. c t´ınh U = {X,A, T} vo´
.i
thuoˆ. c t´ınh A co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p. Quan heˆ. R da˜ du
.o.. c nho´m theo A da`ˆu tieˆn. Khi
do´ Mo.’ Nho´m(Π1Xσ
2
A⊇C (R)) = Mo
.’ Nho´m(R)÷ S vo´.i S la` moˆ. t quan heˆ. thoˆng thu
.`o.ng xa´c di.nh
treˆn moˆ. t thuoˆ. c t´ınh A va` chu´
.a ca´c boˆ. tu
.o.ng u´.ng vo´.i ca´c doˆ´i tu.o.. ng thuoˆ. c lo´
.p C.
Chu´.ng minh. Ta co´ moˆ˜i boˆ. x ∈Mo
.’Nho´m(ΠXσ
2
A⊇C(R)) khi va` chı’ khi x pha’ i du
.o.. c chu´
.a
trong moˆ.t boˆ. du
.o.ng cu’a σ2A⊇C(R) va` khoˆng toˆ`n ta. i moˆ.t boˆ. aˆm cu’a σ
2
A⊇C (R) chu´
.a x, tu´.c la`
∃u ∈ R+(u[Ak] = C)−u chu´.a x, va` khoˆng ∃v ∈ R−(v[Ak] ⊆ C)− v chu´.a x va` x chı’ xa´c di.nh
treˆn taˆ.p X. Die`ˆu na`y co´ ngh˜ıa la` x ∈Mo
.’Nho´m(R) ÷ S. Ta co´ die`ˆu pha’ i chu´.ng minh. 
4. BIEˆ
’
U DIE˜ˆN CA´C TRUY VA´ˆN DI.NH LU
.
O
.
. NG
CU’A MOˆ HI`NH DU˜
.
LIEˆ. U MO
.’ ROˆ. NG
Cho moˆ.t CSDL vo´
.i ca´c quan heˆ. nguyeˆn toˆ´: S1(S#, SNAME), S2(S#, CITY), P1(P#,
PNAME), P2(P#, COLOR), P3(P#, WEIGHT), SP(S#,P#), o.’ daˆy thuoˆ.c t´ınh S# du
.o.. c
keˆ´t ho.. p vo´
.i mie`ˆn DS va` va` co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p HDs va` P# du
.o.. c keˆ´t ho
.
.p vo´
.i mie`ˆn
DP va` va` co´ moˆ. t caˆ´u tru´c phaˆn caˆ´p HDp.
Ca´c truy vaˆ´n di.nh lu
.o.. ng
• Cho bieˆ´t ca´c lo´.p ma˘. t ha`ng co´ ma`u do’ : (Π
1
P#(σ
0
COLOR = Do’(Nho´mP#P2)))
• Cho bieˆ´t thoˆng tin ve`ˆ di.a chı’ cu’a taˆ´t ca’ ca´c ca´c ha˜ng thuoˆ.c lo´
.p D :
σ1S#=D(Nho´mS#S2) - keˆ´t qua’ na`y chu´
.a du.. ng da`ˆy du’ thoˆng tin mang t´ınh gia’ i th´ıch ve`ˆ
di.a chı’ cu’a taˆ´t ca’ ca´c ca´c ha˜ng thuoˆ.c lo´
.p D.
• Neˆ´u chu´ng ta khoˆng ca`ˆn quan taˆm deˆ´n di.a chı’ d´ıch xa´c cu’a tu`
.ng ha˜ng, chu´ng ta co´ theˆ’ bieˆ’u
die˜ˆn nhu. sau: Π0CITY (σ
1
S#=D(Nho´mS#S2)).
• Du.a ra teˆn ca´c ha˜ng cung u´.ng ı´t nhaˆ´t taˆ´t ca’ ca´c ma˘. t ha`ng thuoˆ.c lo´
.p C :
ΠSNAME(S1∗ Mo.’Nho´m(Π1S#σ
2
P#⊇C (Nho´mP#SP )))
• Du.a ra teˆn ca´c ha˜ng chı’ cung u´.ng taˆ´t ca’ ca´c ma˘. t ha`ng thuoˆ.c lo´
.p C :
ΠSNAME(S1∗ Mo.’Nho´m(Π1S#σ
2
P#=C (Nho´mP#SP )))
• Du.a ra thoˆng tin ve`ˆ di.a chı’ cu’a ca´c ha˜ng cung u´
.ng nhie`ˆu nhaˆ´t taˆ´t ca’ ca´c ma˘. t ha`ng thuoˆ.c
lo´.p C: Nho´mS#S2 ∗ (Π
1
S#σ
2
P# ⊇ C (Nho´mS# (Nho´mP#SP ))).
5. DA´NH GIA´ VA` KEˆ´T LUAˆ. N
Vo´.i vieˆ.c du
.a kha´i nieˆ.m phaˆn caˆ´p lo´
.p va`o moˆ h`ınh quan heˆ. thoˆng qua vieˆ.c cho phe´p ca´c
teˆn lo´.p du.o.. c su
.’ du. ng nhu
. ca´c gia´ tri. thuoˆ.c t´ınh trong moˆ.t quan heˆ. va` chaˆ´p nhaˆ.n ca´c ngoa. i
leˆ. , moˆ.t soˆ´ da.ng truy vaˆ´n di.nh lu
.o.. ng treˆn ca´c lo´
.p doˆ´i tu.o.. ng da˜ co´ theˆ’ du
.o.. c bieˆ’u die˜ˆn moˆ. t
ca´ch de˜ˆ da`ng thoˆng qua ca´c phe´p toa´n da. i soˆ´ treˆn ca´c quan heˆ. nho´m. Nhu
. vaˆ.y, moˆ h`ınh du˜
.
lieˆ.u mo
.’ roˆ.ng na`y co´ theˆ’ xem nhu
. moˆ. t giao dieˆ.n cung caˆ´p ca´c thao ta´c baˆ.c cao so vo´
.i moˆ
MOˆ. T MOˆ HI`NH DU˜
.
LIEˆ. U DO´ˆI VO´
.
I CA´C TRUY VA´ˆN DI.NH LU
.
O.
.
NG 49
h`ınh quan heˆ. chuaˆ’n vo´
.i su.. hoˆ˜ tro
.
. cu’a phaˆn caˆ´p ca´c lo´
.p doˆ´i tu.o.. ng. Vieˆ.c cung caˆ´p ca´c thao
ta´c baˆ.c cao cho phe´p ngu
.`o.i du`ng co´ theˆ’ bieˆ’u die˜ˆn ca´c truy vaˆ´n moˆ. t ca´ch do
.n gia’n ho.n vo´.i
ı´t thao ta´c ho.n va` ho.n nu˜.a, ca´c truy vaˆ´n du.o.. c da´nh gia´ hieˆ.u qua’ ho
.n. Da˘. c bieˆ.t, so vo´
.i ca´c
moˆ h`ınh du˜. lieˆ.u quan heˆ. loˆ`ng, ca´c quan heˆ. loˆ`ng khoˆng o
.’ da.ng chuaˆ’n 1, vieˆ.c ca`i da˘.t va` da´nh
gia´ ca´c bieˆ’u thu´.c da. i soˆ´ loˆ`ng kha´ phu´
.c ta.p va` thu
.`o.ng pha’ i bieˆ’n doˆ’i tha`nh ca´c bieˆ’u thu´.c da. i
soˆ´ pha˘’ ng [3, 4]. Trong moˆ h`ınh du˜. lieˆ.u mo
.’ roˆ.ng cu’a chu´ng toˆi, ca´c su
.
. kieˆ.n xem xe´t ca´c lo´
.p
doˆ´i tu.o.. ng co´ theˆ’ du
.o.. c lu
.u tru˜. va` thao ta´c gioˆ´ng nhu. ca´c su.. kieˆ.n xem xe´t ca´c theˆ’ hieˆ.n doˆ´i
tu.o.. ng. Moˆ h`ınh cu’a chu´ng toˆi la` tu
.o.ng th´ıch vo´.i moˆ h`ınh quan heˆ. chuaˆ’n. Tuy nhieˆn, moˆ. t
trong nhu.ng kho´ kha˘n va` ha.n cheˆ´ khi a´p du. ng moˆ h`ınh du˜
. lieˆ.u mo
.’ roˆ.ng na`y la` chu´ng ta ca`ˆn
xa´c di.nh du
.o.. c ca´c caˆ´u tru´c phaˆn caˆ´p HD doˆ´i vo´
.i mie`ˆn D cu’a moˆ. t thuoˆ.c t´ınh di.nh danh A
na`o do´. Trong thu.. c teˆ´, neˆ´u moˆ.t su
.
. phaˆn nho´m ca´c doˆ´i tu
.o.. ng ho
.
. p ly´ du
.o.. c cung caˆ´p tu`
. ch´ınh
nhu˜.ng ngu.`o.i su.’ du. ng cu’a heˆ. va` soˆ´ ca´c ngoa. i leˆ. la` kha´ nho’ hay thu
.
. c chaˆ´t la` khoˆng da´ng keˆ’,
ca´c truy vaˆ´n di.nh lu
.o.. ng treˆn ca´c lo´
.p doˆ´i tu.o.. ng se˜ du
.o.. c bieˆ’u die˜ˆn moˆ.t ca´ch de˜ˆ da`ng thoˆng
qua ca´c phe´p toa´n da. i soˆ´ treˆn ca´c quan heˆ. nho´m. Ngoa`i ra, chu´ng toˆi cu˜ng cho ra`˘ng, chu´ng ta
co´ theˆ’ a´p du. ng moˆ.t soˆ´ thuaˆ. t toa´n tu
.
. doˆ.ng sa’n sinh ra ca´c caˆ´u tru´c phaˆn caˆ´p du
.
. a treˆn ch´ınh
CSDL cu’a heˆ. vo´
.i tieˆu ch´ı toˆ´i thieˆ’u hoa´ lu.. c lu
.o.. ng ca´c quan heˆ. nho´m thu du
.o.. c. Ba`i ba´o [2]
de`ˆ caˆ.p deˆ´n moˆ. t gia’ i thuaˆ.t cho phe´p nho´m ca´c gia´ tri. thuoˆ.c t´ınh du
.
. a treˆn ca´c maˆ˜u co´ theˆ’ la`
moˆ. t tham kha´o toˆ´t cho y´ doˆ` na`y. Cuoˆ´i cu`ng, chu´ng toˆi hy vo.ng co´ theˆ’ tieˆ´p tu. c pha´t trieˆ’n va`
thu.’ nghieˆ.m moˆ h`ınh na`y vo´
.i nhie`ˆu da.ng truy vaˆ´n di.nh lu
.o.. ng kha´c nhau deˆ’ da´p u´
.ng du.o.. c
ca´c nhu ca`ˆu khai tha´c thoˆng tin da da.ng va` phong phu´ cu’a ngu
.`o.i du`ng.
TA`I LIEˆ. U THAM KHA
’O
[1] H.V. Jagadish, Incorporating hierarchy in a relational model of data, Proceedings ACM-
SIGMOD International Conference on Management of Data, 1989 (78–87). NOI NAO???
[2] M. Merzbacher, W.W. Chu, Pattern-Based Clustering for Database Attribute Values, Proceed-
ings AAAI Workshop on Knowledge Discovery in Database, 1993. NOI NAO???
[3] W.Y. Mok, D.W. Embley, A normal formal for precisely characterizing redundancy in nested
relations, ACM TODS 21 (1996) 77–106.
[4] J. Paredaens, D. V. Gucht, Converting nested algebra expressions to flat algebra expressions,
ACM TODS 17 (1992) 66–93.
[5] R. Rantzau, C. Mangold, Laws for rewriting queries containing division operators, Proceedings
ICDE, USA, 2006.
Nhaˆ. n ba`i nga`y 15 - 8 - 2007