Luận án Các phụ thuộc logic trong mô hình dữ liệu dạng khối

là O(mnk). 
2.3 Biểu diễn bao đóng và khoá qua phép dịch chuyển 
 2.3.1 Biểu diễn bao đóng 
 Mệnh đề 2.1 
 Cho lược đồ khối α = (R,Fh), R = (id; A1, A2, ... , An ) , X, Y  , 
X ={x(i), x id, i A}, Y ={x(i), x id, i B}; A, B {1,2, ..., n}, AB = . 
Khi đó: 
 + +
 a) (XY) Fh = X (Y) Fh \ X 
 n
 + (i) 
 b) (XY) Fh = X ( (Y  x ) Fhx\X ). 
 x id i 1
 n n
 + (i) (i) 
 c) (XY) Fh = [(X x )(Y x ) Fhx\X ]. 
 x id i 1 i 1
Chứng minh 
 - Trước hết ta chứng minh mệnh đề c): 
 Dựa vào điều kiện cần và đủ của bao đóng trên lược đồ khối (mệnh đề 
 n
 + (i) 
1.5) ta có: (XY) Fh = (XY  x ) Fhx . 
 x id i 1
 Mặt khác, theo giả thiết ta có: AB =  XY =  
 n n n
 (i) (i)
 Suy ra: (X x id) (i) (Y   x ) = ,  x id. 
 i 1 i 1
 i 1
 48 
 Tiếp theo, ta chứng minh: 
 n n
 (i) (i) 
 (XY  x )Fhx = )  (Y  x )Fhx\X (1) 
 i 1 i 1
 n n
 (i) (i)
 Để ngắn gọn, ta kí hiệu: Xx = X   x , Yx = Y   x , khi đó đẳng 
 i 1 i 1
thức (1) có dạng: (XxYx )Fhx = Xx (Yx )Fhx\X (2) 
 Mặt khác, theo công thức tính bao đóng của tập XxYx dựa vào phép 
dịch chuyển lược đồ quan hệ theo tập Xx trong lát cắt Rx (đây là một lược đồ 
quan hệ trong mô hình quan hệ) đã được chứng minh [6], ta có: 
 = X (Y ) (3) 
 x x Fhx\X x
 Tuy nhiên: Fhx\X = Fhx\Xx 
 Do đó: X (Y ) = X (Y ) (4) 
 x x Fhx\X x x x Fhx\X
 Từ (3) và (4) ta có: = (1) được chứng minh. 
 Từ (1) ta có: 
 = 
 +
 Suy ra: (XY) Fh = c) được chứng minh. 
 n n
 (i) (i) 
 - Ta chứng[(X minh mệnhx )(Y đề b):x ) Fhx\X ]
 x id i 1 i 1
 Theo chứng minh mệnh đề c) ở trên, ta có : 
 +
 (XY) Fh = . 
 n
 (i)
 Mà: X = (X n x ) 
 (i) 
 (XYx id xi 1 ) Fhx
 x id i 1
 n
 + (i) 
 Suy ra: (XY) Fh =X ( (Y  x ) Fhx\X ) . 
 x id i 1
 n
 - Ta(X chứngx minh(i) mệnh đề a): 
 i 1
 49 
 +
 Theo kết quả ở phần b) ta có: (XY) Fh =X . 
 Dựa vào điều kiện cần và đủ của bao đóng trên lược đồ khối (mệnh 
 n
 + (i) 
đề 1.5) ta có: (Y) Fh\X = (Y  x ) Fhx\X . 
 x id i 1
 + +
 Vậy: (XY) Fh =X (Y) Fh\X a) được chứng minh. 
 Từ mệnh đề ở trên, ta có hệ quả sau: 
 Hệ quả 2.1 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ) , X  , 
X ={ x(i), x id, i A}, A {1,2, ..., n}. Khi đó: 
 a) . 
 XX 
 b) Fh Fh\ X . 
 x id
Chứng minh 
 Thật vậy, sử dụng kết quả a) và b) của mệnh đề 2.1 vừa chứng minh ở 
trên với trường hợp đặc biệt Y = ta có ngay hệ quả này. 
 2.3.2 Biểu diễn khóa 
 Cho lược đồ khối α = (R,Fh), R = (id; A1, A2, ... , An ) và X, Uo, UK, UI là 
các tập thuộc tính chỉ số  , đối với lược đồ khối α ta ký hiệu: 
 - Uo là tập tất cả các thuộc tính không khoá. 
 - UK là tập tất cả các thuộc tính khoá. 
 - UI là tập tất cả các thuộc tính nằm trong mọi khoá. 
 n
 (i) 
 Cho các lược đồ khối α(=(R, ( YFh), R=x )(id;Fhx\ XA)1, A2, ... , An );  = (S,G), 
 x id i 1
 = α \ X. Khi đó ta kín hiệu: 
 id (i)
 - αx = (Rx,Fi 1 hx) là lược đồ lát cắt của α=(R,Fh) tại điểm x, 
 50 
 - x = (Sx,Gx) là lược đồ lát cắt của  =(S,G) tại điểm x. 
 Mệnh đề 2.2 
 Cho lược đồ khối α=(R,Fh), R= (id; A1, A2, ... , An ); X, Y, Q  , 
X ={ x(i), x id, i A }, Y = { x(i), x id, i B }; Q ={ x(i), x id, i C }; 
A, B, C {1,2, ..., n},  = (S,G),  = α \ X. Khi đó: 
 a) Nếu Y là siêu khoá của α thì Y\X là siêu khoá của . 
 b) Nếu Y là siêu khoá của α thì Yx\Xx là siêu khoá của x = (Sx, Gx ), 
 (i) (i)
 x id , ở đây Yx= {x , i B}, Xx= {x , i A}. 
 c) Nếu Q là siêu khoá của  thì XQ là siêu khoá của α. Trường hợp X 
 chỉ gồm các thuộc tính không khoá của α và Q là siêu khoá của  thì 
 Q chính là siêu khoá của α. 
 d) Nếu Q là siêu khoá của  thì XxQx là siêu khoá của αx , x id, ở đây 
 (i)
 Qx={x , i C}. Trường hợp X chỉ gồm các thuộc tính không khoá của 
 α và Q là siêu khoá của  thì Qx chính là siêu khoá của αx , x id. 
Chứng minh 
 a) Giả sử Y là siêu khoá của α, đặt . 
 Theo giả thiết Y là siêu khoá của α do đó: 
 + + +
 X( \X) = = Y Fh  (XP) Fh = X(P) Fh\X . 
 + +
 Mà: X( \X) = , X P Fh\X = P Fh\X = \X. (1) 
 Từ (1) ta thấy P = Y\X chính là siêu khoá của  = α \ X. 
 b) Giả sử Y là siêu khoá của α, theo kết quả của a) thì Y\X là siêu khoá 
 của  = α \ X. Từ đó, áp dụng tính chất của khóa và siêu khóa trên 
 n
 id (i)
 lược đồ khối ta có: Yx\Xx là siêu khoá của x = (Sx,Gx ), x id. 
 i 1
 51 
 +
 c) Giả sử Q là siêu khoá của  thì: Q X = , Q Fh\X = \X 
 + +
 Suy ra: (XQ) Fh = X(Q) Fh\X =X( \X) = . 
 Vậy XQ là siêu khoá của α. 
 Nếu X chỉ gồm các thuộc tính không khoá của α thì việc loại bỏ từ 
 siêu khoá XQ các thuộc tính không khoá X vẫn cho ta siêu khoá Q 
 của α. 
 d) Giả sử Q là siêu khoá của  thì theo c) ta có XQ là siêu khoá của α. 
 Từ đó, áp dụng kết quả của mệnh đề 1.8 ta có: XxQx là siêu khoá của 
 αx , x id. 
 Trường hợp X chỉ gồm các thuộc tính không khoá của α Xx là các 
thuộc tính không khoá của αx , do đó Qx = XxQx \ Xx chính là siêu khoá của 
αx , x id. 
 Mệnh đề 2.3 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, Q  , 
X ={x(i), x id, i A}, Q ={x(i), x id, i C}; A, C {1,2, ..., n},  = (S,G), 
 = α \ X +. Khi đó nếu Q là siêu khoá của  thì: 
 a) XQ là siêu khoá của α. 
 b) XxQx là siêu khoá của αx , x id. 
Chứng minh 
 a) Giả sử Q là siêu khoá của  thì theo mệnh đề trên ta có X+Q là siêu 
 khoá của α, khi đó: (X+Q)+ = . 
 +n + +
 Mà ta có: (XQ) =id ((Xi) Q) = XQ là siêu khoá của α. 
 i 1
 52 
 b) Giả sử Q là siêu khoá của  thì theo a) ta có XQ là siêu khoá của α. 
 Từ đó, áp dụng kết quả của mệnh đề 1.8 ta có: XxQx là siêu khoá của αx , 
 x id. 
 Mệnh đề 2.4 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, K  , 
X ={x(i), x id, i A}, K = {x(i), x id, i B}; A, B {1,2, ..., n},  = (S,G), 
 = α \ X. Khi đó: 
 a) Nếu K là khoá của α thì K\X là khoá của . 
 b) Nếu K là khoá của α thì Kx\Xx là khoá của x=(Sx,Gx), x id , ở đây 
 (i) (i)
 Kx = {x , i B}, Xx= {x , i A}. 
Chứng minh 
 a) Giả sử K là khoá của α K là siêu khoá của α, theo mệnh đề 2.2 ta 
 có K\X là siêu khoá của . Nếu K\X không phải là khoá của  thì 
  M  K\X là siêu khoá của , theo mệnh đề trên ta lại có XM là siêu 
 khoá của α. 
 Mà: XM  X(K\X) = K , điều này mâu thuẫn với giả thiết K là khoá 
 của α. Do đó K\X là khoá của . 
 b) Giả sử K là khoá của α, khi đó theo a) ta có K\X là khoá của . Từ 
 đó, áp dụng kết quả của mệnh đề 1.8 ta có: Kx\ Xx là khoá của x x id. 
 Mệnh đề 2.5 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, K  , 
 (i) (i)
X ={ x , x id, i A}, K = {x , x id, i B}; A, B {1,2, ..., n}, X  Uo, 
 = (S,G),  = α \ X. Khi đó: 
 n
 (i)
 a) Nếu K là khoá củid a  thì K là khoá của α. 
 i 1
 53 
 (i)
 b) Nếu Kx là khoá của x = (Sx,Gx), Kx = {x , i B}, x id thì K là khoá 
 của α. 
Chứng minh 
 a) Giả sử K là khoá của  K là siêu khoá của  theo mệnh đề 2.2 
 ta có K là siêu khoá của α (vì giả thiết X  Uo ). Ta chứng minh K là 
 khoá của α. 
 Giả sử ngược lại, K không là khoá của α , khi đó  K’  K mà K’ là 
 siêu khoá của α. Theo mệnh đề 2.2 ta có K’ = K’ \ X (vì giả thiết X 
  Uo ) là siêu khoá của , điều này mâu thuẫn với giả thiết K là siêu 
 khoá của . Vậy K là khoá của α. 
 (i)
 b) Giả sử Kx là khoá của x=(Sx,Gx), Kx= {x , i B}, x id khi đó theo 
 kết quả của mệnh đề 1.8 ta có K là khoá của . Từ đó dựa vào kết quả 
 câu a) ta có K là khoá của α. 
 Định lý 2.1 (Điều kiện cần và đủ) 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, K  , 
 (i) (i)
X ={ x , x id, i A}, K = {x , x id, i B}; A, B {1,2, ..., n}, X  Uo, 
 = (S,G),  = α \ X. Khi đó: 
 a) K là khoá của α khi và chỉ khi K là khoá của . 
 (i)
 b) K là khoá của α khi và chỉ khi Kx là khoá của x=(Sx,Gx), Kx= {x , 
 i B}, x id . 
Chứng minh 
 a) K là khoá của α K là khoá của . 
 Thật vậy, từ giả thiết K là khoá của α, X  Uo và mệnh đề 2.4 ta 
 suy ra: K = Kn\X là khoá của . 
 id (i)
 K là khoá củai 1 K là khoá của α. 
 54 
 Giả sử K là khoá của  vì X  Uo theo kết quả của mệnh đề 2.5 
 ta có K là khoá của α. 
 b) Giả sử K là khoá của α theo kết quả câu a) ta suy ra K là khoá của 
  theo kết quả của mệnh đề 1.8 ta có: Kx là khoá của x=(Sx,Gx), 
 (i)
 Kx= {x , i B}, x id. 
 (i)
 Ngược lại, nếu Kx là khoá của x=(Sx,Gx), Kx= {x , i B}, x id 
 theo kết quả của mệnh đề 1.8 ta có K là khoá của  . 
 Từ đó, áp dụng kết quả câu a) K là khoá của α. 
2.4 Khóa và các tập thuộc tính nguyên thủy, phi nguyên thủy 
 Cho các lược đồ khối α =(R, Fh), R= ( id; A1, A2, ... , An );  = (S, G), 
 = α \ X. Khi đó ta kí hiệu: 
 - αx = (Rx,Fhx) là lược đồ lát cắt của α=(R,Fh) tại điểm x, 
 - x = (Sx,Gx) là lược đồ lát cắt của  =(S,G) tại điểm x. 
 Định lý 2.2 (Điều kiện cần và đủ) 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, K  , 
X={x(i), x id, i A}, K={x(i), x id, i B}; A, B {1,2, ..., n}, X  K = , 
X  UI ,  = (S,G),  = α \ X. Khi đó: 
 a) K là khoá của  khi và chỉ khi XK là khoá của α. 
 b) K là khoá của  khi và chỉ khi Xx Kx là khoá của αx = ( Rx, Fhx ), 
 (i) (i)
 Xx = {x , i A}, Kx= {x , i B}, x id. 
Chứng minh: 
( a) ) Giả sử K là khóa của  K là siêu khóa của  XK là siêu khóa 
của α tồn tại K’  K , XK’ =  mà XK’ là khóa của α (vì X  UI ). 
Theo tính chất của khóan đã phát biểu trong mệnh đề 2.4 XK’ \ X = K’ là 
 id (i)
khóa của , vì K’ i 1 K K’ = K. Vậy XK là khóa của α. 
 55 
( a) ) Ngược lại, giả sử XK là khóa của α, theo tính chất của khóa đã phát 
biểu trong mệnh đề 2.4 XK\ X = K là khóa của . 
 n
 (i)
( b) ) Giả sử K là khóa của  theox câu a) ở trên ta có XK là khóa của 
 i 1
α, theo điều kiện cần và đủ của khóa trong lược đồ khối [10] XK  
= Xx Kx là khóa của αx=(Rx,Fhx ). 
 (i) (i)
( b) ) Giả sử Xx Kx là khóa của αx=(Rx,Fhx ), Xx= {x , i A}, Kx= {x , 
i B}, x id  Xx K x = XK là khóa của α (theo tính chất của khóa 
 x id
trong lược đồ khối [10]) . Mặt khác từ XK là khóa của α, nên theo kết quả 
của câu a) K là khóa của . 
 Hệ quả 2.2 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, Y, K  
 , X ={x(i), x id, i A}, Y ={x(i), x id, i B}, K ={x(i), x id, i 
C}; A, B, C {1,2, ..., n}, Y  UI , X  Uo ,  = (S,G),  = α \ XY. Khi đó: 
 a) K là khoá của  khi và chỉ khi YK là khoá của α. 
 b) K là khoá của  khi và chỉ khi Yx Kx là khoá của αx = ( Rx, Fhx ), 
 (i) (i)
 Yx= {x , i B}, Kx= {x , i C}, x id. 
Chứng minh: 
a) Ta kí hiệu  = α \ X, khi đó  = α \ XY = (α \ X) \ Y =  \ Y ( ở đây X 
 Y =  vì Y  UI , X  Uo ) . Từ đó, do Y  UI, áp dụng định lí 2.2 ta có: 
K là khoá của  khi và chỉ khi YK là khoá của . 
Mặt khác, do X  Uo nên áp dụng tính chất của khóa khi dịch chuyển lược 
đồ khối trong định lý 2.1, ta có: YK là khoá của  khi và chỉ khi YK là khoá 
 n
của α. id (i)
 i 1
Như vậy: K là khoá của  khi và chỉ khi YK là khoá của α. 
 56 
b) Giả sử K là khoá của , vậy theo a) ta có: 
 K là khoá của  khi và chỉ khi YK là khoá của α. (1) 
Từ đó áp dụng tính chất khóa của lược đồ khối trong [10] suy ra: 
 YK là khoá của α khi và chỉ khi Yx Kx là khoá của αx = ( Rx, Fhx ), 
 (i) (i)
 Yx= {x , i B}, Kx= {x , i C}, x id. (2) 
 Từ (1) và (2) ta có: 
 K là khoá của  khi và chỉ khi Yx Kx là khoá của αx = ( Rx, Fhx ), 
 (i) (i)
 Yx= {x , i B}, Kx= {x , i C}, x id. 
Cho lược đồ khối  = (R, F), khi đó ta kí hiệu: 
- LS(F) là tập các thuộc tính xuất hiện trong vế trái và RS(F) là tập các 
 thuộc tính xuất hiện trong vế phải của các phụ thuộc hàm trong F. 
- Attr(F) = LS(F)  RS(F). 
 Khi đó ta có: Attr(F)  . 
 Định lý 2.3 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, M  , 
X  M, X ={x(i), x id, i A}, M = {x(i), x id, i B}; A, B {1,2, ..., n}. 
Khi đó các điều kiện sau là tương đương: 
 +
 a) Xx  Mx = Xx , x id 
 +
 b) Xx  (Mx\ Xx ) = , x id 
 +
 c) Mx\ Xx = Mx \ Xx , x id 
 (i) (i)
 trong đó: Xx = {x , i A}, Mx = {x , i B}. 
Chứng minh 
 +
a) b): Ta có Xx n Mx = Xx , x id, ta cần chứng minh: 
 id (i)
  +
 i 1 Xx  (Mx\ Xx ) = , x id. 
 57 
 + +
 Thật vậy, giả sử ngược lại tồn tại P Xx  (Mx\ Xx ) P Xx và 
 + +
P Mx\ Xx P Xx và P Mx và P Xx P Xx  Mx = Xx và 
 +
P Xx mâu thuẫn. Do đó Xx  (Mx\ Xx ) = , x id. 
 +
b) c): Ta có Xx  (Mx\ Xx ) = , x id, ta cần chứng minh: 
 +
 Mx\ Xx = Mx \ Xx , x id. 
 + +
 Thật vậy, do Xx  Xx Mx\ Xx  Mx \ Xx. (1) 
 +
 Giả sử P Mx\ Xx P Mx và P Xx , như vậy thì P Xx vì nếu 
 + +
P Xx thì ta lại suy ra P Xx  (Mx\ Xx ) =  (theo giả thiết trên) mâu 
 + +
thuẫn. Do đó P Mx\ Xx Mx \ Xx  Mx\ Xx (2) 
 +
 Từ (1) và (2) ta có: Mx\ Xx = Mx \ Xx , x id. 
 +
c) a): Ta có Mx\ Xx = Mx \ Xx , x id, ta cần chứng minh: 
 +
 Xx  Mx = Xx , x id. 
 Thật vậy, theo giả thiết ta có X  M Xx  Mx, mặt khác theo tính 
 + +
chất của bao đóng thì: Xx  Xx Xx  Xx  Mx . (3) 
 + +
 Ngược lại, giả sử P Xx  Mx P Xx và P Mx P Mx\ Xx 
 + +
Nếu P Xx thì P Mx \ Xx = Mx\ Xx , do đó P Mx và P Xx mâu 
 +
thuẫn P Xx . Vậy Xx  Mx  Xx . (4) 
 +
 Từ (3) và (4) ta suy ra Xx  Mx = Xx . 
 Định lý 2.4 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, M  , 
X ={x(i), x id, i A}, M = {x(i), x id, i B}; A, B {1,2, ..., n}. Khi đó 
các điều kiện sau là tương đương: 
 a) X + M = X 
 n
 + (i)
 b) X  (M \ X ) =id  
 i 1
 +
 c) M \ X = M \ X 
 58 
Chứng minh 
 Sử dụng điều kiện cần và đủ về bao đóng của tập thuộc tính chỉ số của 
 n
lược đồ khối trong [10] ta có:  x (i)
 i 1
 + +
 a) Xx  Mx = Xx , x id X  M = X 
 + +
 b) Xx  (Mx\ Xx ) = , x id X  (M \ X ) =  
 + +
 c) Mx\ Xx = Mx \ Xx , x id M \ X = M \ X 
 Mặt khác, từ định lý 2.3 ở trên ta suy ra các vế trái của các mệnh đề 
tương đương trong a), b) và c) là tương đương nhau, kết quả này dẫn tới sự 
tương đương của các vế phải của 3 mệnh đề a), b) và c). Như vậy, sự tương 
đương của 3 đẳng thức trong phát biểu của định lý trên đã được chứng minh. 
 Mệnh đề 2.6 
 Cho lược đồ khối α = ( R, Fh ), R = ( id; A1, A2, ... , An ); X  , 
 (i)
X = { x , x id, i A }; A {1,2, ..., n}, Fh là tập đầy đủ các phụ thuộc hàm 
trên R. Khi đó ta có: 
 a) \ Attr(Fhx )  UIx , x id. 
 + 
 b) Nếu Xx  UIx thì Xx  UKx = Xx , x id. 
Chứng minh 
 a) Kí hiệu Mx = RS(Fhx) \ LS(Fhx), khi đó: UIx = \ Mx , hơn nữa ta 
 lại có: 
 Mx  Attr(Fhx ) \ Attr(Fhx )  \ Mx = UIx. 
 b) Giả sử {K1, K2,, Kt} là tập các khóa trên lược đồ lát cắt αx=(Rx,Fhx), 
 Xx  UIx , khi đó theo tính chất của khóa ta có: 
 n
 (i) +
 Nếu Xx  UIx id thì Xx  UIx  Kix Xx  Kix = Xx , i=1..t . 
 i 1
 +
 Vậy: Xx  UKx = Xx , x id . 
 59 
 Hệ quả 2.3 
 Cho lược đồ khối α = ( R, Fh ),n R = ( id; A1, A2, ... , An ); X  , 
  x (i)
 (i) i 1
X ={x , x id, i A}; A {1,2, ..., n}, Fh là tập đầy đủ các phụ thuộc hàm 
trên R. Khi đó ta có: 
 a) \ Attr(Fh )  UI. 
 +
 b) Nếu X  UI thì X  UK = X. 
 Chứng minh 
 a) Theo phần a) của mệnh đề 2.6 ta có: \ Attr(Fhx )  UIx , x id. 
 Như vậy, khi ta lấy hợp của các vế trái và hợp của các vế phải tương ứng 
 thì tính chất của bao hàm thức không thay đổi, do đó: 
 \ Attr(Fh )  UI. 
 b) Chứng minh theo phương pháp như ở câu a). 
 Mệnh đề 2.7 
 Cho lược đồ khối α = ( R, Fh ), R = ( id; A1, A2, ... , An ); X, Y  , 
 (i) (i)
X ={x , x id, i A}, Y={x , x id, i B}; A, B {1,2, ..., n}, Fh là tập đầy 
đủ các phụ thuộc hàm trên R. Khi đó: 
 (i) (i) (i)
 Nếu x LS(Fhx ) và Fhx Xx Yx thì Fhx Xx\ x Yx \ x , i=1..n, 
 (i) (i)
với Xx = {x , i A}, Yx = {x , i B}. 
Chứng minh 
 Ta xét theo lược đồ của lát cắt αx = (Rx, Fhx ), từ giả thiết Fhx Xx Yx 
 +
suy ra Yx  Xx . Dựa vào thuật toán tìm bao đóng của Xx thì tồn tại dãy phụ 
 n
 (i)
thuộc hàm L1 R1 , L2id R2 ,  ,Lk Rk sao cho: 
 i 1
 L1  X , L2  XR1 , L3  XR1R2 , , Lk  XR1R2 Rk-1 , 
 60 
 +
 Y  XR1R2 Rk-1 Rk = X . (1) 
 (i) (i) 
Vì x LS(Fhx ) x không xuất hiện trong các vế trái của F nên ta có: 
 n
 (i) (i) x (i) (i) 
 L  X\ x , L  (X\x ) R , L  (X\x ) R R , , 
 1 2 1 3 i 1 1 2
 (i) (i) (i) +
 Lk  (X\x ) R1R2 Rk-1 , Y  (X\x ) R1R2 Rk-1 Rk = (X\x ) . (2) 
Từ (1) và (2) ta có: 
 (i) + (i) (i) (i)
 (X\x ) = (X\x ) R1R2 Rk-1 Rk = XR1R2 Rk-1 Rk\ x  Y\ x 
 (i) (i)
Vậy: Fhx X\x Y\ x . 
 Hệ quả 2.4 
 Cho lược đồ khối α = (R, Fh), R = (id; A1, A2, ... , An ); X, Y  . 
 (i) (i) (i)
Khi đó nếu x LS(Fh ) và Fh X Y thì Fh X\ x Y \ x , i = 1..n, 
x id. 
 Mệnh đề 2.8 
 Cho lược đồ khối α = ( R, Fh ), R = ( id; A1, A2, ... , An ); X  , 
 (i)
X = {x , x id, i A}; A  {1,2, ..., n}, Fh là tập đầy đủ các phụ thuộc hàm 
trên R. Khi đó: 
 +
 a) Uox = Uox , x id. 
 + +
 b) Xx  Uox Uox Xx Uox Xx Xx  Uox, x id. 
 +
 c) Nếu  Xx thì Xx  Uox , x id. 
 d) RS(Fh) \ LS(Fh)  Uox, x id. 
 (i) (i) (i) 
 với Xx = {x , i A}, Uox = {x | x Uo}, x id. 
Chứng minh 
 +
 a) Theo định nghĩa của bao đóng ta có: Uox  Uox , vậy để chứng minh 
 + +
Uox = Uox ta cần chứngn minh Uox  Uox. 
 id (i)
  +
 Thật vậy, giả sửi 1 P là thuộc tính khóa và P Uox , Kx là khóa chứa P 
 61 
trong αx = (Rx, Fhx). Khi đó: Uox P, đặt Y= Kx\P YP = Kx. 
 Ta có: YUo YP, mà YP=Kx là khóa YUo là siêu khóa trong αx, mà 
theo tính chất của siêu khóa thì trong siêu khóa ta có thể bỏ đi tập các thuộc 
tính không khóa Uo để được một siêu khóa Y là siêu khóa. Điều này mâu 
 +
thuẫn với giả thiết Y là bộ phận thực sự của khóa Kx. Vậy ta có: Uox  Uox. 
b) Để chứng minh dãy trên, ta sẽ chứng minh theo sơ đồ vòng tròn: 
 + + +
 Thật vậy, từ Xx  Uox Uox Xx Uox Xx Xx  Uox , mà theo 
 + + 
a) ta lại có: Uox = Uox. Do đó: Xx  Uox Xx  Uox . 
c) Ta có: Uox , mà  Xx suy ra: Uox Xx. Theo kết quả b) vừa được 
 +
chứng minh thì Xx  Uox . 
d) Ta chứng minh: RS(Fh) \ LS(Fh)  Uox, x id, thật vậy: 
 Giả sử Fh = {L1 R1, L2 R2, ..., Lk Rk} khi đó nhờ tính chất cộng 
tính của các phụ thuộc hàm ta có: 
 L1L2...Lk R1R2...Rk nghĩa là: LS(F) RS(F). 
Để chứng minh RS(Fh) \ LS(Fh)  Uox, ta sử dụng phương pháp phản chứng. 
 Giả sử ngược lại, ta có thuộc tính khóa P RS(F) \ LS(F) và Kx là khóa 
chứa P. Khi đó: Kx Ux , P RS(F), P LS(F) Kx\P Ux\P. Vì P 
LS(F) LS(F)  Ux \ P Ux \ P LS(F), mà LS(F) RS(F), RS(F) P. 
Vậy Kx\P P mâu thuẫn với giả thiết Kx là khóa. Vậy ta có: 
 RS(Fh) \ LS(Fh)  Uox, x id. 
2.5 Lược đồ khối cân bằng 
 Định nghĩa 2.2: Lược đồ khối = (R,F), R = (id; A1, A2, ... , An ) 
được gọi là cân bằng nếu tập phụ thuộc hàm F thỏa mãn hai tính chất sau: 
 1) Hợp của tất cả các vế trái của các phụ thuộc hàm trong F bằng hợp của 
 n
 tất cả các vế phải củaid (nói) và bằng tập . 
 i 1
 62 
 2) F có dạng thu gọn tự nhiên. 
 Như ta đã biết, F có dạng thu gọn tự nhiên có nghĩa là F thỏa các điều 
kiện sau: 
 - F không chứa các phụ thuộc hàm tầm thường, nghĩa là các phụ thuộc 
hàm có dạng: X Y F và X  Y. 
 - Hai vế trái và phải của mọi phụ thuộc hàm trong F không giao nhau: 
 f F: LS(f)  RS(f) =  . 
 - Các vế trái của mọi phụ thuộc hàm trong F khác nhau đôi một, nghĩa là : 
 f, g F: LS(f) = LS(g) f = g. 
 Ta có nhận xét sau: 
 
 Nhận xét: 
 Cho lược đồ khối = (R,F), R = (id; A1, A2, ... , An ) là lược đồ cân 
bằng. Khi đó, nếu id ={x} thì lược đồ khối cân bằng suy biến thành lược đồ 
quan hệ cân bằng trong mô hình dữ liệu quan hệ. 
Ví dụ 2.2: Cho lược đồ khối α = (R,F), R = (id; A1, A2, A3, A4), id = {1, 2}, 
F ={1(1) 2(1) 1(3) 2(3) 1(4) 2(4), 1(2) 2(2) 1(3) 2(3) 1(1) 2(1), 1(3) 2(3) 1(2) 2(2) 
1(1) 2(1), 1(4) 2(4) 1(2) 2(2) }. 
 Ta thấy lược đồ khối α = (R,F) là lược đồ cân bằng. 
 Thật vậy, ta có: 
- LS(F) = 1(1)2(1)1(2)2(2)1(3)2(3)1(4)2(4) = RS(F) = (1) 
- F có dạng thu gọn tự nhiên. (2) 
 Từ (1) & (2) tan kết luận α = (R,F) là lược đồ khối cân bằng. 
 id (i)
 Mệnh đề 2.9 i 1
 63 
 Cho lược đồ khối = (R, Fh ), R = (id; A1, A2, ... , An ) là lược đồ cân 
bằng. Khi đó x id, lược đồ của lát cắt tại điểm x: x= (Rx, Fhx ) cũng là 
 n
 (i)
lược đồ cân bằng.  x
 i 1
Chứng minh 
 Thật vậy, vì Fh là lược đồ cân bằng nên theo định nghĩa ta có: Fh ở dạng 
thu gọn tự nhiên và LS(Fh) = RS(Fh) = . Từ đó suy ra: 
 LS(Fh) = RS(