Về một số dạng chuẩn trong cơ sở dữ liệu mờ chứa dữ liệu ngôn ngữ

,
khá-cao nằm trong (6.25, 8.75]. Tương tự, chúng ta có thể phân hoạch miền trị của các thuộc
tính khác có tồn tại giá trị ngôn ngữ như thuộc tính Quy mô, Thời gian cung cấp.
Cuối cùng, trong Ví dụ 2.1, ta có 9.5 =1 rất-cao, 5.8 =1 ít-cao và khá-nhỏ =1 nhỏ (có thể
suy ra nhờ tính phổ dụng của ĐSGT).
Vì vậy, R thỏa các phụ thuộc hàm mờ Tên Doanh nghiệp →K Quy mô và (Tên Doanh
nghiệp, Mặt hàng) →K Giá với K = (∞, 1,∞, 1, 2) nhưng rõ ràng không có các phụ thuộc
hàm tương ứng theo kiểu kinh điển.
Để định nghĩa và chứng minh một số tính chất về dạng chuẩn, chúng ta sẽ sử dụng một
số kết quả chính về phụ thuộc hàm mờ trong [4, 5, 7] như sau:
Giả sử F là một tập phụ thuộc hàm mờ. Bao đóng của F , kí hiệu là F+, là tập tất cả
các phụ thuộc hàm mờ được suy diễn từ F bởi các quy tắc suy diễn (K1)− (K4):
(K1) Phản xạ: X →K Y nếu Y ⊆ X;
(K2) Mở rộng: X →K Y ⇒ XZ →K Y Z, với mọi Z ⊆ U ;
(K3) Giảm mức: X →K Y ⇒ X →K′ Y nếu K′X = KX và K′Y ≤ KY ;
(K4) Bắc cầu: X →K Y và Y →K′ Z ⇒ X →K∨K′ Z nếu K′Y ≤ KY
Tập các quy tắc suy diễn (K1)− (K4) đã được chứng minh đúng đắn và đầy đủ [5], tức
là F+ = F ∗ (ở đây F ∗ là tập các hệ quả logic của F ), đồng thời ta cũng có:
Định lý 2.1. [5] Giả sử F là một tập phụ thuộc hàm mờ. Khi đó F+ có những tính chất
sau:
(i) X →K Y ∈ F+ ⇒ X →K A ∈ F+,∀A ∈ Y .
(ii) (X →K Y ∈ F+, X →K′ Z ∈ F+)⇒ X →K∪K′ Y Z ∈ F+, với điều kiện KX = K′X .
(iii) (X →K Y ∈ F+, V →K′ W ∈ F+)⇒ XV →K∨K′ YW ∈ F+, với K′Y ∩VW ≤ KY ∩VW .
(iv) Đặt G = {X →K A|X →K Y ∈ F và A ∈ Y }. Khi đó, G+ = F+.
Một số quy tắc khác được chứng minh là đúng đắn bằng cách dùng (K1)-(K4) [7]. Đặc
biệt chúng ta quan tâm đến các quy tắc trong mệnh đề sau:
Mệnh đề 2.1. [7] Các quy tắc suy diễn sau đây là đúng đắn
Quy tắc hợp: {X →K Y,X →K′ Z} |= X →K∪K′ Y Z nếu KX = K′X .
Quy tắc giả bắc cầu: {X →K Y,WY →K′ Z} |= WX →K∨K′ Z nếu K′Y ≤ KY .
Quy tắc tách: Nếu X →K Y và Z ⊆ Y thì X →K Z.
3. MỘT SỐ DẠNG CHUẨN MỜ TRONG CSDL NGÔN NGỮ
Thiết kế "tốt" một CSDL ngôn ngữ nhằm ngăn chặn hiện tượng "dư thừa", "dị thường"
xảy ra khi cập nhật dữ liệu. Chúng ta sẽ mở rộng một số định nghĩa từ CSDL kinh điển để
phù hợp với việc sử dụng quan hệ bằng nhau mức K theo cách tiếp cận đại số gia tử.
Định nghĩa 3.1. (Phụ thuộc toàn phần, phụ thuộc bộ phận) Cho X,Y ⊆ U với U là tập
thuộc tính của lược đồ CSDL ngôn ngữ R. Y được gọi là phụ thuộc hàm mờ toàn phần mức
K đối với X nếu và chỉ nếu X →K Y và không tồn tại X ′ ⊂ X, X ′ 6= ∅ sao cho X ′ →K Y . Y
VỀ MỘT SỐ DẠNG CHUẨN TRONG CƠ SỞ DỮ LIỆU MỜ CHỨA DỮ LIỆU NGÔN NGỮ 373
được gọi là phụ thuộc hàm mờ bộ phận mức K đối với X khi và chỉ khi X →K Y và tồn tại
X ′ ⊂ X, X ′ 6= ∅ sao cho X ′ →K Y .
Bây giờ chúng ta sẽ định nghĩa khóa, siêu khóa mức K của lược đồ CSDL ngôn ngữ.
Định nghĩa 3.2. (Khóa mức K, siêu khóa mức K) Cho K ⊆ U và F là tập các phụ thuộc
hàm mờ trong R và K là một mức tương tự cho trước. Khi đó, K được gọi là một khóa mức
K khi và chỉ khi K →K U ∈ F+ và K →K U là phụ thuộc hàm mờ toàn phần mức K. Tập
S ⊆ U được gọi là một siêu khóa mức K khi và chỉ khi S chứa một khóa mức K.
Nếu R có nhiều hơn một khóa mức K, ta chọn một khóa K bất kỳ làm khóa chính mức K.
Những thuộc tính A ∈ K được gọi là thuộc tính khóa mức K, những thuộc tính A /∈ K được
gọi là thuộc tính không khóa mức K.
Miền trị của mỗi thuộc tính trong CSDL ngôn ngữ chấp nhận các kiểu dữ liệu khác nhau
từ kiểu (1)-(7) bao gồm: giá trị rõ, khoảng, tập hợp, giá trị ngôn ngữ và 3 kiểu dữ liệu Null
khác "unknown", "applicable", "undefine" và quan hệ bằng nhau mức k giữa các kiểu dữ
liệu cũng đã được định nghĩa (xem chi tiết trong [4]). Vì vậy, dạng chuẩn 1 được định nghĩa
như sau.
Định nghĩa 3.3. (F1NF ) Lược đồ quan hệ mờ R được gọi là ở dạng chuẩn 1 (F1NF) khi
và chỉ khi với mọi r ∈ R miền trị của các thuộc tính chứa dữ liệu thuộc kiểu (1)-(7) [4].
Ngoại trừ dạng chuẩn F1NF, các dạng chuẩn khác được định nghĩa trên lược đồ CSDL ngôn
ngữ dựa trên cơ sở tập phụ thuộc hàm mờ và khóa mức K. Vì vậy, trong các định nghĩa sau
đây chúng ta sẽ gọi là dạng chuẩn mờ mức K.
Định nghĩa 3.4. (KF2NF ) Cho F là tập phụ thuộc hàm mờ của lược đồ quan hệ ngôn ngữ
R và K là một khóa mức K. Khi đó, R được gọi là ở dạng chuẩn 2 mức K (KF2NF) khi và chỉ
khi R ở dạng chuẩn F1NF và với mọi thuộc tính không khóa A /∈ K ta có K →K′ A ∈ F+
và K →K′ A thỏa điều kiện K′K = KK và K′A ≥ KA là phụ thuộc hàm mờ toàn phần.
Định nghĩa 3.5. (KF3NF ) Cho F là tập phụ thuộc hàm mờ của lược đồ quan hệ ngôn ngữ
R và K là một khóa mức K. Khi đó, R được gọi là ở dạng chuẩn 3 mức K (KF3NF) khi và
chỉ khi R ở dạng chuẩn F1NF và với mọi phụ thuộc hàm mờ X →K′ A ∈ F+, A /∈ X thì A
là thuộc tính khóa mức K của R hoặc X là một siêu khóa mức K của R.
Định nghĩa 3.6. (KFBCNF ) Cho F là tập phụ thuộc hàm mờ của lược đồ quan hệ ngôn
ngữ R và K là một khóa mức K. Khi đó, R được gọi là ở dạng chuẩn mờ Boyce-Codd mức K
(KFBCNF) khi và chỉ khi R ở dạng chuẩn F1NF và nếu phụ thuộc hàm mờ X →K′ A ∈ F+,
A /∈ Xthì X là một siêu khóa mức K.
Ví dụ 3.1. R là lược đồ quan hệ ngôn ngữ có tập thuộc tính U=ABCDE. Mức tương
tự K = (∞, 2,∞, 1, 2). Tập phụ thuộc hàm mờ F = {A →KAB B,AC →K′ACD D}, ở đây
K′ = (∞, 2,∞, 2, 2).
ACE là một khóa mức K của R, bởi vì: Từ AC →K′ACD D ta suy ra AC →KACD D theo
(K3) do KAC = K′AC và KD ≤ K′D; kết hợp với A →KAB B và các phụ thuộc tầm thường
A→KA A, C →KC C, E →KE E, theo Quy tắc hợp, ta được ACE →K ABCDE.
R không ở dạng chuẩn KFBCNF vì tồn tại A→KAB B mà A không là siêu khóa mức K
của R. R cũng không ở dạng chuẩn KF3NF, bởi vì tồn tại AC →K′ACD D ∈ F+ mà D không
là thuộc tính khóa mức K và AC không là siêu khóa mức K của R. 
374 LÊ XUÂN VINH, TRẦN THIÊN THÀNH, LÊ XUÂN VIỆT
Tiếp theo, chúng ta sẽ nghiên cứu việc tách lược đồ quan hệ như trong ví dụ 3.1 về các
dạng chuẩn KF3NF và KFBCNF bảo toàn một số tính chất. Trước tiên, chúng ta quan tâm
đến khái niệm phép chiếu một tập phụ thuộc hàm mờ sau đây.
Giả sử R là một lược đồ quan hệ của CSDL ngôn ngữ với tập thuộc tính U và F là một
tập phụ thuộc hàm mờ đối với R, V là tập con của U . Phép chiếu F lên V cho kết quả là
một tập phụ thuộc hàm mờ, kí hiệu là ΠV (F ), với
ΠV (F ) = {X →K′ A|X →K′ A ∈ F+, XA ⊆ V }
Nếu chúng ta quan tâm một mức K xác định trên U thì chỉ những phụ thuộc hàm mờ trong
tập {X →K′ A|X →K′ A ∈ F+, XA ⊆ U và K′X = KX ,K′A ≥ KA} mới có ý nghĩa và đáng
được quan tâm. Vì vậy, đối với V ⊆ U , chúng ta định nghĩa
ΠV (F )|K = {X →K′ A|X →K′ A ∈ F+, XA ⊆ V và K′X = KX ,K′A ≥ KA}
Rõ ràng, ΠV (F )|K ⊆ ΠV (F ). Bây giờ, chúng ta sẽ nghiên cứu việc tách lược đồ quan hệ.
4. TÁCH VỀ DẠNG CHUẨN KF3NF BẢO TOÀN PHỤ THUỘC HÀM MỜ
Trong CSDL kinh điển, đối với lược đồ quan hệ R có tập thuộc tính U và tập phụ thuộc
hàmD bao giờ cũng tồn tại một phép tách ρ = {R1, ..., Rm} sao cho mỗi Ri, i = 1, ...,m đều ở
dạng chuẩn 3NF với tập phụ thuộc hàm Di = ΠUi(D) = {X → Y |X → Y ∈ D+, XY ⊆ Ui}.
Trong đó Ui là tập các thuộc tính của Ri. Vấn đề này sẽ xảy ra thế nào đối với CSDL ngôn
ngữ và tập phụ thuộc hàm mờ. Trước tiên chúng ta trình bày các định nghĩa mở rộng về tập
phụ thuộc hàm mờ tương đương và tập phụ thuộc hàm mờ tối tiểu.
Định nghĩa 4.1. Cho R là một lược đồ quan hệ của CSDL ngôn ngữ. Tập phụ thuộc hàm
mờ F và G được gọi là tương đương nhau đối với R nếu và chỉ nếu F+ = G+.
Định nghĩa 4.2. Tập phụ thuộc hàm mờ F được gọi là tối tiểu nếu nó thoản mãn các điều
kiện sau đây:
1. Vế phải của mỗi phụ thuộc hàm mờ trong F đều chứa đúng một thuộc tính;
2. Không có phụ thuộc hàm X →K A ∈ F mà F − {X →K A} tương đương với F ;
3. Không có phụ thuộc hàm X →K A ∈ F mà tồn tại Z ⊂ X sao cho (F − {X →K
A}) ∪ {Z →K A} tương đương với F .
Bây giờ, chúng ta trình bày thuật toán tách lược đồ quan hệ được mở rộng từ một thuật
toán trong [8] như sau:
Thuật toán 1
+ Đầu vào: Lược đồ quan hệ R và tập phụ thuộc hàm mờ tối tiểu F
+ Đầu ra: ρ = {R1, ..., Rm} sao cho mỗi Ri ở dạng chuẩn K(i)F3NF và Ri thỏa các phụ thuộc
hàm trong ΠUi(F )|K(i)
+ Phương pháp:
1. Nếu tồn tại thuộc tính không thuộc bất kỳ vế trái hoặc vế phải của một phụ thuộc
hàm mờ nào trong F thì loại bỏ thuộc tính đó khỏi R
2. Nếu tồn tại phụ thuộc hàm mờ trong F bao hàm tất cả các thuộc tính của R thì đặt
ρ = {R}, ngoài ra:
VỀ MỘT SỐ DẠNG CHUẨN TRONG CƠ SỞ DỮ LIỆU MỜ CHỨA DỮ LIỆU NGÔN NGỮ 375
3. Với mỗi X →K A ∈ F , xác lập Ri với tập thuộc tính Ui = XA là một phần tử của
phép tách ρ.
Trong thuật toán trên, mỗi phụ thuộc hàm mờ X →K A ∈ F có một mức K riêng và
phép tách bảo toàn phụ thuộc hàm trong ΠUi(F )|K ứng với mức K đó.
Mệnh đề 4.1. Giả sử R là một lược đồ quan hệ của CSDL ngôn ngữ, F là một tập phụ
thuộc hàm tối tiểu trong R và ρ = {R1, ..., Rm} là một kết quả tách từ R bằng Thuật toán 1.
Khi đó, mỗi Ri thỏa các phụ thuộc hàm trong ΠUi(F )|K và Ri ở dạng chuẩn KF3NF với
i = 1, ...,m.
Chứng minh. Rõ ràng Ri thỏa các phụ thuộc hàm trong ΠUi(F )|K bởi vì ΠUi(F )|K ⊆ ΠUi(F ).
Bây giờ, chúng ta sẽ chứng minh Ri ở dạng chuẩn KF3NF đối với ΠUi(F )|K. Ở đây Ui = XA
tương ứng với X →K A được xử lý trong bước 3 của Thuật toán 1. Để chứng minh phản
chứng, giả sử rằng Ri không ở dạng chuẩn KF3NF đối với ΠUi(F )|K. Khi đó, tồn tại Y →K′
B ∈ ΠUi(F )|K (B không thuộc Y ) mà Y không là siêu khóa mức K và B không là thuộc tính
khóa mức K trong Ri. Để ý rằng A là thuộc tính đơn và Y B ⊆ XA. Xét hai trường hợp sau
đây:
Trường hợp 1: A = B. Khi đó Y B ⊆ XB. Vì B không thuộc Y nên ta suy ra Y ⊆ X.
Hơn nữa, vì X là siêu khóa mức K và Y không là siêu khóa mức K trong XA nên Y ⊂ X.
Ta có Y →K′ B ∈ ΠUi(F )|K, tức là Y →K′ A ∈ ΠUi(F )|K. Theo định nghĩa của ΠUi(F )|K thì
K′Y = KY ,K
′
A ≥ KA. Theo (K3), Y →K A ∈ ΠUi(F )|K và do đó Y →K A ∈ F+. Vì vậy, trong
F ta có thể thay X →K A bằng Y →K A mà bao đóng F+ không thay đổi. Điều này mâu
thuẫn với tính chất tối tiểu của F .
Trường hợp 2: A 6= B. Vì X →K A nên X là một siêu khóa mức K trong XA và tồn tại
Z ⊆ X sao cho Z là một khóa mức K trong XA. Do A 6= B và B ⊆ XA nên tồn tại B′ trong
B và B′ ∈ X. Hơn nữa, B′ không là thuộc tính khóa mức K do B không chứa thuộc tính
khóa mức K theo giả thiết phản chứng. Vì vậy B′ /∈ Z, ta suy ra Z ⊂ X. Như vậy ta có thể
thay Z →K A cho X →K A trong F mà F+ không thay đổi. Điều này mâu thuẫn với tính
chất tối tiểu của F .
Cả hai trường hợp đều xảy ra mâu thuẫn, mệnh đề đã được chứng minh. 
Ví dụ 4.1. R là lược đồ quan hệ của CSDL ngôn ngữ, có tập thuộc tính U=ABCD. Tập
phụ thuộc hàm mờ F = {A →KAB B,AC →K′ACD D,A →KAD D}, trong đó mức tương tự
K = (∞, 2,∞, 1), K′ = (∞, 2,∞, 2). R không ở dạng chuẩn KF2NF vì tồn tại D, không là
thuộc tính khóa mức K, phụ thuộc hàm bộ phận mức K vào AC do tồn tại AC →KACD D
và A →KAD D. Trong đó, AC →KACD D ∈ F+ được suy ra từ AC →K′ACD D bởi (K3). Sử
dụng Thuật toán 1, tách R thành ρ = (AB,ACD,AD). Rõ ràng, ρ bảo toàn các phụ thuộc
hàm mờ. AB ở dạng chuẩn KF3NF đối với ΠAB(F )|K, ACD ở dạng chuẩn K′F3NF đối với
ΠACD(F )|K′ và AD ở dạng chuẩn KF3NF đối với ΠAD(F )|K. Để ý rằng A →KAD D không
thuộc ΠACD(F )|K′ do KD ≤ K′D.
5. TÁCH VỀ DẠNG CHUẨN KFBCNF BẢO TOÀN THÔNG TIN
5.1. Định nghĩa phép kết nối tự nhiên trong CSDL ngôn ngữ
Trong CSDL kinh điển, phép tách lược đồ quan hệ R với tập phụ thuộc hàm F thành
ρ = (R1, ..., Rm) được gọi là phép tách bảo toàn thông tin (hay tách không tổn thất) nếu
376 LÊ XUÂN VINH, TRẦN THIÊN THÀNH, LÊ XUÂN VIỆT
như kết nối tự nhiên các hình chiếu của R lên các thành phần Ri có tập thuộc tính Ui tương
ứng ta thu được chính quan hệ R. Điều này nghĩa là đối với mỗi quan hệ r ∈ R thỏa F , ta
có r = r1 ∗ ... ∗ rm, trong đó ri ∈ Ri và ri = ΠUi(r), i = 1, ...,m. Khi thực hiện phép kết nối
tự nhiên giữa hai quan hệ, kết quả thu được phụ thuộc vào sự bằng nhau của dữ liệu trên
các thuộc tính chung của hai quan hệ. Khi quan hệ bằng nhau thông thường được thay bởi
quan hệ bằng nhau mức K trong CSDL ngôn ngữ một số tình huống xảy ra trong ví dụ sau.
Ví dụ 5.1. Cho R = ABC, R1 = ΠAB(R), R2 = ΠBC(R) tương ứng với các quan hệ:
r = {a1b1c1, a1b1c2, a2b2c2}, r1 = {a1b1, a2b2}, r2 = {b1c1, b1c2, b2c2}
Nếu xét quan hệ bằng nhau thông thường thì r1 ∗ r2 = r nhưng nếu dùng quan hệ bằng
nhau mức K, giả sử b1 =k b2 và đặt b′ là giá trị bằng nhau mức k đối với b1 và b2 thì
r1 ∗ r2 6= r, bởi vì r1 ∗ r2 = {a1b1c1, a1b1c2, a1b′c2, a2b′c1, a2b′c2, a2b2c2}.
Để hạn chế các bộ sinh ra từ các cặp có giá trị bằng nhau mức K trên những thuộc tính
chung, khi xử lý trên CSDL ngôn ngữ, chúng ta sẽ giới hạn phép kết nối tự nhiên chỉ thực
hiện đối với những cặp có giá trị bằng nhau thông thường, không sử dụng quan hệ bằng
nhau mức K trên những thuộc tính chung. Giả sử U = {A1, ..., An}, Dom(R), Dom(S) ⊆ U ,
một cách hình thức:
r ∗ s = {(r1, ..., rk−1, rk, ..., rm, sm+1, ..., sn)|ri = si, i = k, ...,m},∀r ∈ R,∀s ∈ S
Với phép kết nối tự nhiên như vậy, chúng ta định nghĩa phép tách bảo toàn thông tin trong
CSDL ngôn ngữ.
Định nghĩa 5.1. Cho R là lược đồ quan hệ CSDL ngôn ngữ có tập thuộc tính U , F là tập
phụ thuộc hàm mờ đối với R. Phép tách ρ = (R1, ..., Rm) được gọi là bảo toàn thông tin đối
với R khi và chỉ khi với mọi r ∈ R, r thỏa F ta có r = ΠU1(r) ∗ ... ∗ ΠUm(r), trong đó Ui là
tập thuộc tính của Ri tương ứng.
Bổ đề 5.1. Cho R là một lược đồ CSDL ngôn ngữ với tập phụ thuộc hàm mờ F trên tập
thuộc tính U và ρ = (R1, ..., Rm) là một phép tách của R. Khi đó,
a) Nếu ρ là phép tách bảo toàn thông tin và thay thế Ri bởi phép tách σ = (S1, ..., Sn)
bảo toàn thông tin thì phép tách τ = (R1, ..., Ri−1, S1, ..., Sn, Ri+1, ..., Rm) bảo toàn thông tin
đối với F .
b) Nếu ρ = (R1, ..., Rm) là phép tách bảo toàn thông tin thì bổ sung vào ρ một số lược
đồ quan hệ (Rm+1, ..., Rm+k) trên U ta được phép tách τ = (R1, ..., Rm, Rm+1, ..., Rm+k) bảo
toàn thông tin đối với F .
Chứng minh. Chứng minh tương tự như trong [8].
5.2. Tách bảo toàn thông tin về các dạng chuẩn KFBCNF
Phép tách bảo toàn thông tin được đặt ra đối với các lược đồ quan hệ R không ở dạng
chuẩn KFBCNF. Trong CSDL kinh điển, một quan hệ R với tập phụ thuộc hàm F không ở
dạng chuẩn BCNF đều có thể tách bảo toàn thông tin thành các quan hệ con ở dạng chuẩn
BCNF. Trên mô hình CSDL ngôn ngữ, ngữ nghĩa của phụ thuộc hàm mờ mức K và phép
chiếu tập phụ thuộc hàm mờ đã định nghĩa, chúng ta cũng có một kết quả tương tự bằng
việc mở rộng Thuật toán 5.3 trong [8]
VỀ MỘT SỐ DẠNG CHUẨN TRONG CƠ SỞ DỮ LIỆU MỜ CHỨA DỮ LIỆU NGÔN NGỮ 377
Thuật toán 2. Tách bảo toàn thông tin về các dạng chuẩn KFBCNF
+ Đầu vào: Lược đồ quan hệ R, tập phụ thuộc hàm mờ F và một mức K
+ Đầu ra: ρ là một tách của R
+ Phương pháp:
1. Đặt ρ = {R}
2. While (tồn tại S ∈ ρ không ở dạng chuẩn KFBCNF) do
Chọn phụ thuộc hàm mờ X →K′ A ∈ ΠS(F )|K vi phạm chuẩn KFBCNF trong S:
a. Đặt S1 = XA;
b. Đặt S2 = S −A.
c. ρ = ρ− {S} ∪ {S1, S2}
Mệnh đề 5.1. Giả sử R là một lược đồ quan hệ của cơ sở dữ liệu ngôn ngữ, F là một tập
phụ thuộc hàm mờ trong R, K là một mức tương tự cho trước và ρ = {R1, ..., Rm} là kết quả
tách từ R bằng Thuật toán 2. Khi đó mọi Ri, i = 1, ...,m đều ở dạng chuẩn KFBCNF và
ρ bảo toàn thông tin.
Chứng minh. Trước tiên, chúng ta chứng minh Ri, i = 1, ...,m đều ở dạng chuẩn KFBCNF.
Thuật toán 2, tách mỗi lược đồ quan hệ không ở dạng chuẩn KFBCNF thành các lược đồ
quan hệ có số thuộc tính ít hơn và Thuật toán dừng sau hữu hạn bước. Khi đó, ta thu được
kết quả là các lược đồ quan hệ ở dạng chuẩn KFBCNF. Thật vậy:
Giả sử, tồn tại S ∈ ρ không ở dạng chuẩn KFBCNF vì có phụ thuộc hàm mờ X →K′ A ∈
ΠS(F )|K với A /∈ X mà X không là siêu khóa mức K đối với S. Thuật toán 2 chia S thành
hai lược đồ quan hệ S1 = XA và S2 = S − A. Rõ ràng, S2 ⊂ S. Chúng ta sẽ chứng minh
S1 cũng là tập con thực sự của S. Giả sử ngược lại S1 = S tức XA = S . Theo giả thiết
X →K′ A ∈ ΠS(F )|K thỏa S tức là X →K′ A với K′X = KX và K′A ≥ KA. Do đó X →K A
theo (K3). Hơn nữa, theo (K1) X →K X. Theo quy tắc hợp, ta suy ra X →K XA tức là
X →K S, mâu thuẫn với X không là siêu khóa mức K của S. Như vậy, số thuộc tính trong
S1 cũng như S2 luôn ít hơn trong S.
Thuật toán dừng sau hữu hạn bước vì số thuộc tính trong mỗi lược đồ quan hệ ít dần. Nếu
S chỉ có một thuộc tính thì S hiển nhiên ở dạng chuẩn KFBCNF. Nếu S có đúng hai thuộc
tính chẳng hạn S = AB và tồn tại một phụ thuộc hàm mờ, chẳng hạn A→K′ B ∈ ΠAB(F )|K
thì chứng minh tương tự như trên, ta được A→K AB, tức A là một siêu khóa mức K của S.
Do đó S ở dạng chuẩn KFBCNF.
Bây giờ ta sẽ chứng minh phép tách ρ bảo toàn thông tin. Thật vậy, khi khởi tạo ρ = {R}.
Tại một thời điểm nào đó, giả sử một lược đồ quan hệ S ∈ ρ có X →K′ A ∈ ΠS(F )|K không
thỏa điều kiện của KFBCNF. Theo Thuật toán 2, S được tách thành hai lược đồ quan
hệ S1 = XA và S2 = S − A. Như vậy S1 ∩ S2 = X, S1 − S2 = A và theo giả thiết
X →K′ A ∈ ΠS(F )|K, tức là S1 ∩ S2 →K′ S1 − S2. Tương tự phép chứng minh Định lý 5.5
[8], phép tách S thành (S1, S2) bảo toàn thông tin. Theo Bổ đề 5.1, ρ bảo toàn thông tin.
Ví dụ 5.2. R là lược đồ quan hệ của CSDL ngôn ngữ, có tập thuộc tính U=ABCDE. Mức
tương tự K = (∞, 2,∞, 1, 2). Tập phụ thuộc hàm mờ F = {A→KAB B,AC →K′ACD D}, ở đây
K′ = (∞, 2,∞, 2, 2). R không ở dạng chuẩn KFBCNF vì tồn tại A →KAB B mà A không là
siêu khóa mức K của R. Sử dụng Thuật toán 2 tách R thành ρ = {AB,ACDE}. AB ở dạng
chuẩn KFBCNF đối với tập phụ thuộc hàm mờ ΠAB(F )|K = {A→KAB B}. ACDE không ở
dạng chuẩn KFBCNF đối với tập phụ thuộc hàm mờ là ΠACDE(F )|K = {AC →K′ACDE D}
378 LÊ XUÂN VINH, TRẦN THIÊN THÀNH, LÊ XUÂN VIỆT
vì trong lược đồ ACDE, AC không là siêu khóa mức K. Tách ACDE thành {ACD,ACE}.
Lúc này, ACD ở dạng chuẩn KFBCNF (do AC là khóa mức K trong ACD, điều này được
suy ra từ AC →KACD D bởi vì K′AC = KAC và K′D ≥ KD). ACE ở dạng chuẩn KFBCNF là
tầm thường. Như vậy, R được tách thành ρ = {AB,ACD,ACE}.
6. KẾT LUẬN
Trong cơ sở dữ liệu ngôn ngữ, phụ thuộc hàm mờ được nghiên cứu dựa trên quan hệ
tương tự để phân hoạch miền trị của các thuộc tính theo mức K. Như một tham số, mức K
có thể thay đổi theo ý nghĩa của từng ứng dụng. Vì vậy, mở rộng của các dạng chuẩn từ cơ
sở dữ liệu kinh điển sang cơ sở dữ liệu ngôn ngữ là không tầm thường. Khóa mức K và một
số dạng chuẩn mờ mức K được định nghĩa. Giới hạn các phụ thuộc hàm mờ hạn chế theo
mức K cho phép tách một lược đồ cơ sở dữ liệu ngôn ngữ thành các lược đồ ở dạng K3NF
thỏa các phụ thuộc hàm mờ trong ΠUi(F )|K cũng như tách một lược đồ cơ sở dữ liệu ngôn
ngữ về dạng chuẩn KFBCNF bảo toàn thông tin đóng góp một phần trong định hướng thiết
kế các cơ sở dữ liệu ngôn ngữ. Các dạng chuẩn mờ liên quan đến phụ thuộc đa trị trong cơ
sở dữ liệu ngôn ngữ [7] là những vấn đề cần nghiên cứu tiếp theo.
TÀI LIỆU THAM KHẢO
[1] G. Chen, E. E. Kerre, J. Vandenbulcke, Fuzzy normal forms and a dependency-preserving decom-
position into ϕ-F3NF, Proceedings 3rd, IEEE International Conference on Fuzzy Systems,
IEEE Computer Society Press, Los Alamitos, 1994 (156–161).
[2] J. Mishra and S. Ghosh, Normalization in a fuzzy relational database model, International
Journal of Computer Engineering - Technology 3 (2) (2012) 506–517.
[3] N. C. Ho, L. X. Vinh, On some properties of ordering relation in non-homogeneous hedge alge-
bras, Tạp chí Tin học và Điều khiển học 19 (4) (2003) 373–381.
[4] N. C. Hồ, L. X. Vinh, N. C. Hào, Thống nhất dữ liệu và xây dựng quan hệ tương tự trong cơ
sở dữ liệu ngôn ngữ bằng đại số gia tử, Tạp chí Tin học và Điều khiển học 25 (4) (2009)
314–332.
[5] Nguyễn Cát Hồ, Vũ Minh Lộc, Hoàng Tùng, Nguyễn Tân Ân, Phụ thuộc hàm mờ trong CSDL
quan hệ với dữ liệu ngôn ngữ, Tạp chí Khoa học và Công nghệ 51 (2) (2013) 137–151.
[6] S. Shenoi, A. Melton and L. T. Fan, Functional dependencies and normal forms in the fuzzy
relational database model, Information Sciences 60 (1992) 1–28.
[7] L. X. Vinh, T. T. Thành, Một số vấn đề về phụ thuộc đa trị trong cơ sở dữ liệu mờ chứa dữ liệu
ngôn ngữ, Tạp chí Tin học và Điều khiển học 28 (1) (2012) 88–102.
[8] J. D. Ullman, Principles of Database Systems, Computer Sciences Press Inc, 1982.
Ngày nhận bài 04 - 6 - 2013
Nhận lại sau sửa ngày 15 - 10 - 2013