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

VỀ MỘT SỐ DẠNG CHUAN trong cơ sở dữ liệu mờ chứa dữ liệu
NGÔN ngữThis research is funded by Vietnam National Foundation for Science and Technology Development (NAFOSTED) under grant number 102.01- 2011.06
LÊ XUÂN VINH, TRẦN THIÊN THÀNH, LÊ XUÂN VIỆT
Trường Đại học Quy Nhơn
lexuanvinh@qnu.edu.vn
Tóm tắt. Trẽn quan điểm xem miền trị của mỗi thuộc tính trong cơ sở dữ liệu mờ chứa dữ liệu ngôn ngữ tương ứng với một đại số gia tử thích hợp phụ thuộc hàm mờ và phụ thuộc đa trị mờ đã được nghiẽn cứu [4, 5, 7]. Trong bài báo này, chúng tôi tiếp tục nghiẽn cứu một số dạng chuẩn mờ. Các khái niệm khóa mức K, siẽu khóa mức K và dạng chuẩn F1NF, KF2NF, KF3NF, KFBCNF trong cơ sở dữ liệu mờ chứa dữ liệu ngôn ngữ được định nghĩa. Phép tách một lược đồ cơ sở dữ liệu về dạng chuẩn KF3NF bảo toàn các phụ thuộc hàm mờ cũng như tách về dạng chuẩn KFBCNF bảo toàn thông tin được quan tâm nghiẽn cứu. Từ khóa: cơ sở dữ liệu mờ, dữ liệu ngôn ngữ, dạng chuẩn mờ, phép tách.
Abstract. On the viewpoint that each attribute domain of the fuzzy databases with linguistic data corresponds to an appropriate hegde algebras, the fuzzy functional dependencies and the fuzzy multivalued dependencies are studied [4, 5, 7]. In this paper, we continue to study a number of fuzzy normal forms. Such concepts as K-keys, super K-keys and the normal forms F1NF, KF2NF, KF3NF, KFBCNF are defined in fuzzy databases with linguistic data. The paper focuses on researching the fuzzy dependency preserving decomposition into KF3NF and the lossless join decomposition into KFBCNF.
Keywords: fuzzy databases, linguistic data, fuzzy normal forms, decomposition.
GIỚI THIÊU
Sự xuất hiện thông tin không chắc chắn, không chính xác, thông tin mơ hồ mà chúng ta sẽ gọi chung là thông tin mờ trong một mô hình cơ sở dữ liệu (CSDL) nào đó là hết sức tự nhiẽn. Chẳng hạn khi điều tra, khảo sát thông tin về những công ty, doanh nghiệp cung cấp một số mặt hàng trẽn thị trường ở một địa bàn trong những năm gần đây thì có nhiều thông tin không hoàn toàn chính xác hoặc theo kiểu định tính như: quy mô doanh nghiệp là nhỏ, rất nhỏ, vừa, lớn,..; giá cả có thể là cao, rất cao,...; thời gian cung cấp hàng là nhanh, chậm,...Việc biểu diễn, xử lý các loại thông tin này một cách trực tiếp là vấn đề nhận được sự quan tâm của nhiều nhà nghiẽn cứu và mô hình chứa thông tin mờ được gọi chung là CSDL mờ.
Trong các bài báo gần đây [4, 5, 7], các tác giả đã nghiên cứu một số vấn đề trẽn mô hình CSDL mờ theo cách tiếp cận đại số gia tử. Ngoài những kiểu dữ liệu đã được đề cập như giá trị rõ, giá trị khoảng, tập hợp các giá trị rõ, chúng tôi đặc biệt quan tâm đến các giá trị của biến ngôn ngữ tương ứng với các thuộc tính (quy mô, giá, thời gian cung cấp). Những giá trị của biến ngôn ngữ ở đây cũng chính là những phần tử, những giá trị ngôn ngữ của một đại số gia tử tương ứng và những CSDL chứa các giá trị ngôn ngữ như vậy chúng ta sẽ gọi là CSDL mờ chứa dữ liệu ngôn ngữ hay cho gọn là CSDL ngôn ngữ.
Phân hoạch miền trị của thuộc tính bằng một quan hệ tương đương phụ thuộc vào một số dương k cố định trước, có ý nghĩa là độ dài của một từ chuẩn được chọn, để xây dựng quan hệ bằng nhau mờ giữa các dữ liệu trong miền trị. Trên cơ sở này có thể thực hiện các chuyển đổi truy vấn mờ sang truy vấn rõ [4], định nghĩa phụ thuộc hàm mờ, phụ thuộc đa trị mờ, xây dựng tập luật suy diễn đúng đắn và đầy đủ [7]. Một số tác giả đã dựa trên những kết quả này để đề xuất phương pháp biểu diễn và cài đặt cơ sở dữ liệu mờ chứa dữ liệu ngôn ngữ trên XML.
Tương tự trong cơ sở dữ liệu kinh điển, việc thiết kế "tốt" CSDL mờ trên mô hình này sẽ tránh được những hiện tượng "dư thừa", "dị thường" khi thực hiện các thao tác cập nhật dữ liệu. Vì vậy, một cơ sở lý thuyết với các khái niệm khóa, siêu khóa và các dạng chuẩn mờ, phép tách lược đồ quan hệ theo quan điểm thống nhất với những kết quả trong [4, 5, 7] cần được nghiên cứu. Đây chính là mục tiêu của bài báo.
Bài báo được tổ chức như sau: Sau phần giới thiệu, Mục 2 dành cho việc trình bày những kết quả cơ bản nhất về phụ thuộc hàm mờ trong cơ sở dữ liệu ngôn ngữ. Mục 3 trình bày các khái niệm, định nghĩa về khóa, siêu khóa mức K và các dạng chuẩn F1NF, KF2NF, KF3NF, KFBCNF. Mục 4 dành cho việc nghiên cứu phép tách lược đồ cơ sở dữ liệu về dạng chuẩn KF3NF bảo toàn các phụ thuộc hàm mờ. Mục 5 trình bày về phép tách lược đồ cơ sở dữ liệu về dạng chuẩn KFBCNF bảo toàn thông tin. Cuối cùng, một số nhận xét và kết luận về những vấn đề đã được nghiên cứu trong bài báo sẽ được trình bày trong Mục 6.
PHỤ THUỘC HÀM MỜ TRONG Cơ SỞ DỮ LIÊU NGÔN NGỮ
CSDL ngôn ngữ, đã được giới thiệu trong [4, 7], là một tập DB ={U; R1;...; Rm; Const}, ở đây U = {A1, A2;...; An} là không gian các thuộc tính, mỗi Ri là một lược đồ quan hệ, Const là tập các ràng buộc dữ liệu. Miền trị Dom(A) của thuộc tính A (trong số các A1,A2,...; An) có thể chứa giá trị rõ, giá trị khoảng, các kiểu dữ liệu khác đặc biệt là giá trị của biến ngôn ngữ, chúng là những phần tử của đại số gia tử tương ứng với biến ngôn ngữ. Với mỗi Dom(A) ta chọn tùy ý một số nguyên dương k > 0. Ghép các khoảng mờ thích hợp của tất cả các từ có độ dài k + 1 (chi tiết trong [4]), ta được một phân hoạch trên [0; 1] và qua một phép tỉ lệ đơn giản ta sẽ thu được một phân hoạch trên Dom(A). Phân hoạch này xác định một quan hệ tương đương Sk. Những giá trị cùng thuộc một lớp tương đương được cho là bằng nhau mức k hay là tương tự mức k. Số k càng lớn phân hoạch càng mịn, hai giá trị bằng nhau mức k càng phải gần nhau. Vì vậy, đối với các thuộc tính không chứa các thông tin mờ như tên doanh nghiệp, mặt hàng mức k đối với các thuộc tính này bằng 1 với ý nghĩa hai giá trị bằng nhau khi đồng nhất với nhau về kí hiệu. Bộ các số nguyên dương K = (k1; k2;...; kn) được chọn tương ứng với các thuộc tính trong U được gọi là một mức tương tự trên lược đồ quan hệ R.
Để tiện theo dõi, chúng ta nhắc lại một số thuật ngữ và kí hiệu trong [4]. Nếu X c U thì kí hiệu KX là một bộ gồm |XI thành phần thu hẹp của K từ U xuống X. Cho KX và K0X là hai mức tương tự trẽn X, ta nói KX > KX hoặc KX k'A với mọi A 2 X. Cho Kx; Ky là hai mức tương tự trẽn X; Y c U tương ứng. Mức tương tự mở rộng trẽn X u Y, kí hiệu KX V Ky, được xác định là KX V Ky = KX_y u Ky_X u K'z, trong đó Z = X \ Y và K'z = {kA V kA|A 2 Z}, ở đây kA V kA = max(kA; kA). Nếu kZ = k'z thì KX V Ky được kí hiệu là KX u Ky.
Theo cách tiếp cận đại số gia tử, với X; Y c U, Y phụ thuộc hàm mờ vào X trong CSDL ngôn ngữ nếu hai bộ bằng nhau mức Kx trẽn X thì cũng bằng nhau mức Ky trẽn Y. Ta có thể dùng mức K để chỉ cho các mức hạn chế Kx, Ky cho gọn nếu không gây nhầm lẫn.
Định nghĩa 2.1. [5] Cho DB là một CSDL ngôn ngữ và R là một lược đồ quan hệ của DB có tập thuộc tính U. Với X; Y c U và K là một mức tương tự trẽn U, ta nói Y phụ thuộc hàm mờ vào X mức K trẽn lược đồ quan hệ R, kí hiệu f = X !K Y, nếu với mọi quan hệ r 2 R:
(8t; s 2 r)(t[X] =K s[X] ) t[Y] =K s[Y])
Ví dụ 2.1 Một quan hệ R của CSDL ngôn ngữ (mô hình cho các ví dụ còn lại)
Tên doanh nghiệp
Quy mô
Mặt hàng
Giá
Thời gian cung cấp
a1
lớn
c1
9.5
chậm
a1
lớn
c1
rất-cao
4
a2
nhỏ
c1
5.8
[2, 4]
a2
khá nhỏ
c1
ít-cao
3
a1
lớn
c2
thấp
nhanh
a3
vừa
c2
thấp
rất-nhanh
Giả sử chọn K = (1; 1; 1; 1; 2). Các số 1,1,2 trong K là ba mức được chọn với ba thuộc tính Quy mô, Giá và Thời gian cung cấp tương ứng. Nếu mức chọn là k thì mỗi cụm trong phân hoạch của miền trị sẽ là hợp của các khoảng mờ của một số giá trị ngôn ngữ độ dài k + 1.
Để minh họa, xét miền trị của thuộc tính "Giá" chứa các giá trị ngôn ngữ cao, thấp, rất cao, ít cao,...và các giá trị số. Giả sử miền trị tham chiếu của "Giá" là [0,10]. Chúng ta sẽ xây dựng ĐSGT tuyến tính AX = (X;G;C;H; không và rất > khá . Để ý rằng, không là gia tử phủ định địa phương, không phải là toán tử phủ định logic [3]. Các tham số mờ fm(cao) = fm(thấp) = W = 0.5, ụ-(không) = p,(ít) = ụ.(khá) = ụ(rất) = 0.25. Mức tương tự của thuộc tính "Giá" là 1.
Sử dụng hàm định lượng ngữ nghĩa [4], tính giá trị định lượng của các giá trị ngôn ngữ và chuyển đổi lẽn miền trị tham chiếu với hệ số r = 10. Ta có:
vr(cao) = [W + 0.5 X fm(cao)] X 10 = [0.5 + 0.5 X 0.5] X 10 = 7.5
Vr(ít-cao) = [W + 0.5 X fm(it-cao)] X 10 = [0.5 + 0.5 X 0.25 X 0.5] X 10 = 5.625
vr(không-cao) = [W + fm(ít-cao) + 0.5 X fm(không-cao)] X 10 = [0.5 + 0.25 X 0.5 + 0.5 X 0.25 X 0.5] X 10 = 6.875
vr(khá-cao) = vr(cao) + 0.5 X fm(khá-cao) X 10 = 7.5 + [0.5 X 0.25 X 0.5] X 10 = 8.125 vr(rất-cao) = 10 — 0.5 X fm(rất-cao) X 10 = 10 — 0.5 X 0.25 X 0.5 X 10 = 9.375 Tiếp tục, chúng ta tính các khoảng tương tự S1>r(.) trẽn [0,10] tạo thành bởi các khoảng mờ Ir(.) của các giá trị ngôn ngữ có độ dài 2:
S1;r(cao) = Ir(không-cao) u Ir(khá-cao) = (7.5 — 0.25 X 0.5 X 10; 7.5 + 0.25 X 0.5 X 10] = (6.25; 8.75]
51,r(rất-cao) = (10 - 0.25 X 0.5 X 10; 10] = (8.75,10]
s1;r(ít-cao) = (0.5, 0.5 X 10 + 0.25 X 0.5 X 10] = (5, 6.25]
Như vậy, nếu chọn k = 1 thì quan hệ tương tự 51 phân hoạch nửa trẽn miền trị tham chiếu của thuộc tính "Giá" thành các khoảng (5,6.25], (6.25, 8.75], (8.75,10]. Giá trị ít-cao nằm trong khoảng (5,6.25], rất-cao nằm trong (8.75,10], các giá trị còn lại không-cao, cao, 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 Quy mô và (Tẽn Doanh nghiệp, Mặt hàng) Giá với K = (1,1,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	Y nếu Y c X;
(K2) Mở rộng: X	Y ) XZ YZ, với mọi Z c U;
(K3) Giảm mùc: X Y ) X Y nếu KX = KX và KY < KY;
(K4) Bắc cầu: X Y và Y Z ) X !KVK0 Z nếu KY < 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:
X Y 2 F+ ) X a 2 F+, 8A 2 Y.
(X	Y 2 F+ , X	Z 2 F+) ) X !KịjK' YZ 2 F+, với điều kiện KX = KX.
(X	Y 2	F+> V	W 2 F+)	) XV !KVK'	YW 2 F với	KY<	KY.
Dặt G = {X	A|X	Y 2 F và A 2 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 Y, X Z} |= X !KjK0 YZ nếu KX = KX.
Quy tắc giả bắc cầu:	{X	Y, WY	Z}	|=	WX !KVK0	Z nếu	KY	<	KY.
Quy tắc tách: Nếu X Y và Z c Y thì X	Z.
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 c 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 Y và không tồn tại X0 c X, X0 = 0 sao cho X0	Y. Y đượ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 Y và tồn tại X0 c X, X0 = 0 sao cho X0 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 c 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 U 2 F + và K U là phụ thuộc hàm mờ toàn phần mức K. Tập S c 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 2 K được gọi là thuộc tính khóa mức K, những thuộc tính A 2 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 2 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 2 K ta có K A 2 F+ và K A thỏa điều kiện K0K = Kk và K0A > 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 a 2 F+, A 2 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 A 2 F +, A 2 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 = (1; 2; 1; 1, 2). Tập phụ thuộc hàm mờ F = {A !Kab B;AC	Dg, ở đây
K0 = (1; 2; 1; 2, 2).
ACE là một khóa mức K của R, bởi vì: Từ AC	D ta suy ra AC !Kacd D theo
(K3) do Kac = KAC và KD < KD; 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 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 2 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.	■
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à Hy (F), với
ny(F) = {X	A|X	a 2 F+; XA C 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	A|X	a 2 F+ ; XA C U và KX = KX; $A > Ka} mới có ý nghĩa và đáng
được quan tâm. Vì vậy, đối với V C U, chúng ta định nghĩa
Hy(F)|k = {X A|X a 2 F + ; XA C V và KX = Kx; kA > Ka}
Rõ ràng, ny(F)|K C ny(F). Bây giờ, chúng ta sẽ nghiên cứu việc tách lược đồ quan hệ.
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àm D bao giờ cũng tồn tại một phép tách p = {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 = Hí .(D) = {X ! Y|X ! Y 2 D+; XY C 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:
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;
Không có phụ thuộc hàm X A 2 F mà F — {X A} tương đương với F;
Không có phụ thuộc hàm X A 2 F mà tồn tại Z c X sao cho (F — {X
A}) u {Z	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: p = {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 nưi (F) |k(ì)
+ Phương pháp:
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
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 p = {R}, ngoài ra:
Với mỗi X a 2 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 p.
Trong thuật toán trẽn, mỗi phụ thuộc hàm mờ X A 2 F có một mức K riêng và phép tách bảo toàn phụ thuộc hàm trong Hu. (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à p = {R1;..., /í,,,.} 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 Hu. (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 Hu. (F)|K bởi vì nu. (F)|K c Hu. (F). Bây giờ, chúng ta sẽ chứng minh Ri ở dạng chuẩn KF3NF đối với nu. (F)|K. ở đây Ui = XA tương ứng với X 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 nUị (F)|K. Khi đó, tồn tại Y B 2 nu. (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à YB c XA. Xét hai trường hợp sau đây:
Trường hợp 1: A = B. Khi đó YB c XB. Vì B không thuộc Y nên ta suy ra Y c 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 c X. Ta có Y B 2 nu. (F)|K, tức là Y A 2 nu. (F)|K. Theo định nghĩa của nu. (F)|K thì KY = KY; $A > Ka. Theo (K3), Y A 2 nu.(F)|K và do đó Y A 2 F+. Vì vậy, trong F ta có thể thay X A bằng Y 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 = B. Vì X A nên X là một siêu khóa mức K trong XA và tồn tại Z c X sao cho Z là một khóa mức K trong XA. Do A = B và B c XA nên tồn tại B0 trong B và B0 2 X. Hơn nữa, B0 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 B0 2 Z, ta suy ra Z c X. Như vậy ta có thể thay Z A cho X 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 !&acd D;A !Kad Dg, trong đó mức tương tự K = (1; 2; 1; 1), K0 = (1; 2; 1; 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 2 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 p = (AB; ACD; AD). Rõ ràng, p bảo toàn các phụ thuộc hàm mờ. AB ở dạng chuẩn KF3NF đối với Hau(F)|K, ACD ở dạng chuẩn K0F3NF đối với nACD(F)|K0 và AD ở dạng chuẩn KF3NF đối với nAD(F)|K. Để ý rằng A !Kad D không thuộc nACD(F)|k do Kd < KD.
TÁCH VỀ DẠNG CHUẨN KFBCNF BẢO TOÀN THÔNG TIN
Đị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 p = (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 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 Rị 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 2 R thỏa F, ta có r = ri * ... * rm, trong đó r 2 R và r = U-Uị(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, Ri = II.AB(R), R2 = Il/V'(R) tương ứng với các quan hệ:
r = ịữibiCi;ữibiC2; ữ2b2c2 };ri = {aibi; a2b2}; r2 = {biCi;biC2; b2C2}
Nếu xét quan hệ bằng nhau thông thường thì ri * r2 = r nhưng nếu dùng quan hệ bằng nhau mức K, giả sử bi =k b2 và đặt b0 là giá trị bằng nhau mức k đối với bi và b2 thì ri * r2 = r, bởi vì ri * r2 = {aibici; aibic2; aib0c2; a2b'ci;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 = {Ai;...; An}, Dom(R); Dom(S) c U, một cách hình thức:
r * s = {(ri;...; rfc_i; rk; ...,Tm,sm+i, ...;Sn)|rị = Si; i = k; ...;m};8r 2 R;8s 2 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 p = (Ri;...; 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 2 R, r thỏa F ta có r =	(r) * ... * Iíc„,(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à p = (Ri;...; Rm) là một phép tách của R. Khi đó,
Nếu p là phép tách bảo toàn thông tin và thay thế Ri bởi phép tách ơ = (Si; ...;Sn) bảo toàn thông tin thì phép tách T = (Ri;...; Ri-i;Si;...; Sn; Ri+i;...; Rm) bảo toàn thông tin đối với F.
Nếu p = (Ri;...; Rm) là phép tách bảo toàn thông tin thì bổ sung vào p một số lược đồ quan hệ (Rm+i;...; Rm+k) trên U ta được phép tách T = (Ri;...; Rm; Rm+i;...; 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].
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]
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: p là một tách của R
+ Phương pháp:
Đặt p = {R}
While (tồn tại S 2 p không ở dạng chuẩn KFBCNF) do
Chọn phụ thuộc hàm mờ X a 2 IÍ,S'(F)|k vi phạm chuẩn KFBCNF trong S:
Đặt S1 = XA;
Đặt s2 = S - A.
p = p - {S}U{S1 S}
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à p = {R1;Rm} là kết quả tách từ R bằng Thuật toán 2. Khi đó mọi Rị, i = 1; ...,m đều ở dạng chuẩn KFBCNF và p bảo toàn thông tin.
Chùng minh. Trước tiên, chúng ta chứng minh Rị, 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 2 p không ở dạng chuẩn KFBCNF vì có phụ thuộc hàm mờ X A 2 Ils(F)|k với A 2 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 c 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 a 2 ns(F)|k thỏa S tức là X A với KX = KX và $A > Ka. Do đó X A theo (K3). Hơn nữa, theo (K1) X X. Theo quy tắc hợp, ta suy ra X XA tức là X	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 B 2 H.-1B(F)|k thì chứng minh tương tự như trên, ta được A 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 p bảo toàn thông tin. Thật vậy, khi khởi tạo p = {R}. Tại một thời điểm nào đó, giả sử một lược đồ quan hệ S 2 p có X A 2 ns(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 a 2 ns(F)|k, tức là S1 \ S2	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, p 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 = (1; 2; 1; 1; 2). Tập phụ thuộc hàm mờ F = {A !Kab B; AC	D}, ở đây
K0 = (1; 2; 1; 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 p = {AB; ACDE}. AB ở dạng chuẩn KFBCNF đối với tập phụ thuộc hàm mờ nAB(F)|k = {A Abị B}. ACDE không ở dạng chuẩn KFBCNF đối với tập phụ thuộc hàm mờ là nACDE(F)|k = {AC	D} vì trong lược đồ ACDE, AC không là siêu khóa mức K. Tách ACDE thành {ACD;ACEg. 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ì &AC = KAC và KD > KD). ACE ở dạng chuẩn KFBCNF là tầm thường. Như vậy, R được tách thành p = {AB; ACD; ACEg.
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 (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
G. Chen, E. E. Kerre, J. Vandenbulcke, Fuzzy normal forms and a dependency-preserving decomposition into '-F3NF, Proceedings 3rd, IEEE International Conference on Fuzzy Systems, IEEE Computer Society Press, Los Alamitos, 1994 (156-161).
J. Mishra and S. Ghosh, Normalization in a fuzzy relational database model, International Journal of Computer Engineering - Technology 3 (2) (2012) 506-517.
N. C. Ho, L. X. Vinh, On some properties of ordering relation in non-homogeneous hedge algebras, Tạp chi Tin học và Điều khiển học 19 (4) (2003) 373-381.
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 chi Tin học và Điều khiển học 25 (4) (2009) 314-332.
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 chi Khoa học và Công nghệ 51 (2) (2013) 137-151.
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.
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 chi Tin học và Điều khiển học 28 (1) (2012) 88-102.
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