Về vấn đề thể hiện tập phụ thuộc hàm của khối dữ liệu trong mô hình dữ liệu dạng khối

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00231  n i i 1 )(idYX,  Ai ixX )(  Bj jxY )(  n i ix 1 )(  n i ix 1 )( VỀ VẤN ĐỀ THỂ HIỆN TẬP PHỤ THUỘC HÀM CỦA KHỐI DỮ LIỆU TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Trịnh Đình Thắng1, Trần Minh Tuyến2 1Đại học Sư phạm Hà Nội 2, 2Đại học Công đoàn thangdhsp2@hpu2.edu.vn, tuyentm@dhcd.edu.vn TÓM TẮT: Bài báo phát biểu và chứng minh một số tính chất của khối dữ liệu khi thể hiện tập các phụ thuộc hàm trong mô hình dữ liệu dạng khối. Điều kiện cần và đủ đẻ hai tập phụ thuộc hàm trên lược đồ khối là tương đương, tính chất của hai tập phụ thuộc hàm tương đương trên khối dữ liệu. Tính chất của mối tương quan giữa các thể hiện trên khối cũng được phát biểu và chứng minh... Ngoài ra, thuật toán làm đóng khối trị của khối dữ liệu đối với phép nhân các phần tử và độ phức tạp của nó cũng đã được trình bày và chứng minh tính đúng ở đây. Từ khóa: Thể hiện tập phụ thuộc hàmn, công thức Boolean, khối chân lý, lược đồ khối. I. MÔ HÌNH DỮ LIỆU DẠNG KHỐI A. Khối, lược đồ khối Định nghĩa I.1 [1] Gọi R = (id; A1, A2,..., An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn khác rỗng, Ai (i = 1n) là các thuộc tính. Mỗi thuộc tính Ai (i = 1...n) có miền giá trị tương ứng là dom(Ai). Một khối r trên R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị của các thuộc tính Ai (i = 1...n). Nói một cách khác: t r(R) t = { t i : id dom(Ai)}i=1..n . Ta kí hiệu khối đó là r(R) hoặc r(id; A1, A2,..., An ), đôi khi nếu không gây nhầm lẫn ta kí hiệu đơn giản là r. Định nghĩa I.2 [1] Cho R = (id; A1, A2,..., An ), r(R) là một khối trên R. Với mỗi x id ta kí hiệu r(Rx) là một khối với Rx = ({x}; A1, A2,..., An ) sao cho: tx r(Rx) tx = {t i x = t i } i=1..n , ở đây t r(R), t = { t i : id dom(Ai)}i=1..n, x Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x. B. Phụ thuộc hàm Sau đây, để cho đơn giản ta sử dụng các kí hiệu: x (i) = (x; Ai ) ; id (i) = {x (i) | x id}. Ta gọi x(i) (x id, i = 1..n) là các thuộc tính chỉ số của lược đồ khối R = (id; A1,A2,...,An ). Định nghĩa I.3 [1] Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R và , X Y là kí hiệu một phụ thuộc hàm. Một khối r thoả X Y nếu: t1, t2 R sao cho t1(X) = t2(X) thì t1(Y) = t2(Y). Định nghĩa I.4 [3] Cho lược đồ khối = (R,F), R = (id; A1, A2,..., An), F là tập các phụ thuộc hàm trên R. Khi đó bao đóng của F kí hiệu F+ được xác định như sau: F + = { X Y | F X Y }. Nếu X = {x(m)} id(m) , Y = {y(k)} id(k) thì ta kí hiệu phụ thuộc hàm X Y đơn giản là x(m) y(k) . Khối r thoả x(m) y(k) nếu với mọi t1, t2 r sao cho t1(x (m) ) = t2(x (m) ) thì t1(y (k) ) = t2(y (k) ) . Trong đó: t1(x (m) ) = t1(x; Am), t2(x (m) ) = t2(x; Am), t1(y (k) ) = t1(y; Ak ), t2(y (k) ) = t2(y; Ak ). Về sau, để thuận tiện khi sử dụng ta kí hiệu các tập con phụ thuộc hàm trên R: Fh = { X Y | , , A, B {1,2,...,n} và x id }, Fhx = Fh = { X Y Fh | X, Y }. Trịnh Đình Thắng, Trần Minh Tuyến 697  n i i 1 )(idX  n i i 1 )(id n i i 1 )(id  n i i 1 )(id  n i i 1 )(id  n i i 1 )(id  n i i 1 )(id Định nghĩa I.5 [3] Cho lược đồ khối = (R,Fh), R = (id; A1, A2,..., An), khi đó Fh được gọi là tập đầy đủ các phụ thuộc hàm nếu Fhx là như nhau với mọi x id. Một cách cụ thể hơn: Fhx gọi là như nhau với mọi x id nghĩa là: x, y id: M N Fhx M’ N’ Fhy với M’, N’ tương ứng tạo thành từ M, N nhờ việc thay x bởi y. C. Bao đóng của tập thuộc tính chỉ số: Định nghĩa I.6 [4] Cho lược đồ khối = (R, F), R = (id; A1, A2,..., An ), F là tập các phụ thuộc hàm trên R. Với mỗi , ta định nghĩa bao đóng của X đối với F kí hiệu X+ như sau: X + = {x (i) , x id, i = 1..n | X x (i) F + }. Ta kí hiệu tập tất cả các tập con của tập hợp là tập SubSet( ) . Cho , SubSet ( ) và M, P SubSet( ), khi đó ta định nghĩa phép toán trên SubSet( ) như sau: M P = MP (hợp của 2 tập con M và P : M P), M = {MX | X }, = {XY | X , Y }. D. Khoá của lược đồ khối = (R, F) Định nghĩa I.7 [4] Cho lược đồ khối = (R,F), R = (id; A1, A2,..., An), F là tập các phụ thuộc hàm trên R, K . K gọi là khoá của lược đồ khối nếu nó thoả 2 điều kiện: i) K x(i) F+ , x id, i = 1..n. ii) K’ K thì K’ không có tính chất i). Nếu K là khoá và K K’’ thì K’’ gọi là siêu khoá của lược đồ khối R đối với F. II. CÁC CÔNG THỨC BOOLEAN A. Công thức Boolean Định nghĩa II.1 [2] Cho U = {x1, x2, ..., xn} là tập hữu hạn các biến Boolean, B là tập trị Boolean, B = {0, 1}. Khi đó các công thức Boolean (CTB) hay còn gọi là các công thức logic được xây dựng như sau: (i) Mỗi trị 0/1 trong B là một CTB. (ii) Mỗi biến nhận giá trị trong U là một CTB. (iii) Nếu a là một công thức Boolean thì (a) là một CTB. (iv) Nếu a và b là các CTB thì avb, a b, a và a b là một CTB. (v) Chỉ có các công thức được tạo bởi các quy tắc từ (i) – (iv) là các CTB. Ta kí hiệu L(U) là tập các CTB xây dựng trên tập các biến U. Định nghĩa II.2 [2] Mỗi vector các phần tử 0/1, v = {v1, v2, ..., vn} trong không gian B n = BxBx...xB được gọi là một phép gán trị. Như vậy, với mỗi CTB f L(U) ta có f(v) = f(v1, v2, ..., vn) là trị của công thức f đối với phép gán trị v. Trong trường hợp không gây ra nhầm lẫn thì ta hiểu kí hiệu X đồng thời biểu diễn cho các đối tượng sau đây : - Một tập thuộc tính trong U. - Một tập biến logic trong U. - Một công thức Boolean là hội logic các biến trong X. Mặt khác, nếu X = {B1, B2, ..., Bn} U, ta kí hiệu: X = B1 B2 ... Bn và gọi là dạng hội. vX = B1v B2v ... v Bn và gọi là dạng tuyển. Với mỗi tập hữu hạn các CTB F ={f1, f2, ..., fm} trong L(U), ta xem F như là một công thức dạng F = f1 f2 ... fm. Khi đó ta có: F(v) = f1(v) f2(v) ... fm(v). 698 VỀ VẤN ĐỀ THỂ HIỆN TẬP PHỤ THUỘC HÀM CỦA KHỐI DỮ LIỆU TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI B. Bảng trị và bảng chân lý Với mỗi công thức f trên U, bảng trị của f, kí hiệu Vf chứa n+1 cột, với n cột đầu tiên chứa các giá trị của các biến trong U, còn cột thứ n+1 chứa trị của f ứng với mỗi phép gán trị của dòng tương ứng. Như vậy, bảng trị chứa 2n dòng, n là số phần tử của U. Định nghĩa II.3 [2] Bảng chân lý của f , kí hiệu Tf là tập các phép gán trị v sao cho f(v) nhận giá trị 1: Tf = {v B n | f(v) = 1} Khi đó, bảng chân lý TF của tập hữu hạn các công thức F trên U, chính là giao của các bảng chân lý của mỗi công thức thành viên trong F. TF = f f F T . Ta có: v TF khi và chỉ khi f F: f(v) = 1. C. Suy dẫn logic Định nghĩa II.4 [2] Cho f, g là hai CTB, ta nói công thức f suy dẫn logic ra công thức g và kí hiệu f |=g nếu Tf Tg . Ta nói f tương đương với g và kí hiệu f≡g nếu Tf = Tg . Với F và G trong L(U) ta nói F suy dẫn logic ra G , kí hiệu F |= G nếu TF TG . Hơn nữa, ta nói F và G là tương đương, kí hiệu F≡G nếu TF = TG . D. Công thức Boole dương Định nghĩa II.5 [2] Công thức f L(U) được gọi là công thức Boolean dương (CTBD) nếu f(e) = 1 với e là phép gán trị đơn vị: e = (1, 1, ..., 1), ta kí hiệu P(U) là tập toàn bộ các công thức Boolean dương trên U. Ta có thể xem P(U) bao gồm các công thức được xây dựng từ các phép toán , , và hằng 1. E. Khối chân lý của khối dữ liệu Định nghĩa II.6 [7] Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, u, v r. Ta gọi (u,v) là phép gán trị: (u,v) = ( 1(u.x (1) ,v.x (1) ), 2(u.x (2) ,v.x (2) ), ..., n(u.x (n) ,v.x (n) )) x id , trong đó: i(u.x (i) ,v.x (i)) = 1 nếu u.x(i) = v.x(i) và i(u.x (i) ,v.x (i) ) = 0 nếu ngược lại, i = 1..n, x id. Khi đó, với mỗi khối r ta kí hiệu khối chân lý của khối r là Tr: Tr = { (u,v) | u, v r }. Từ định nghĩa ta thấy khối chân lý của khối r là một khối nhị phân. Trong trường hợp tập id = {x}, khi đó khối suy biến thành quan hệ và khái niệm bảng chân lý của khối lại trở thành khái niệm bảng chân lý của quan hệ trong mô hình dữ liệu quan hệ. Nói một cách khác, khối chân lý của khối là mở rộng khái niệm bảng chân lý của quan hệ trong mô hình quan hệ. G. Phụ thuộc Boolean dương trên khối Định nghĩa II.7 [7] Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, ta gọi mỗi công thức Boolean dương trong P(R) là một phụ thuộc Boolean dương (PTBD). Ta nói khối r thỏa phụ thuộc Boolean dương f và kí hiệu r(f) nếu Tr Tf . Khối r thỏa tập phụ thuộc Boolean dương F và kí hiệu r(F) nếu khối r thỏa mọi PTBD trong F: r(F) f F: r(f) Tr TF . Nếu có r(F) ta cũng nói PTBD f đúng trong khối r. Cho tập PTBD F và một PTBD f: - Ta nói F suy dẫn ra f theo khối và kí hiệu F |- f nếu: r : r(F) r(f). - Ta nói F suy dẫn ra f theo khối có không quá 2 phần tử và kí hiệu F |-2 f nếu: r2 : r2(F) r2(f). Ta có định lý tương đương sau: Định lý II.1 [7] Cho tập PTBD F và một PTBD f , R = (id; A1,A2,...,An ), r(R) là một khối trên R. Khi đó ba mệnh đề sau là tương đương: (i) F |= f (suy dẫn logic), (ii) F |- f (suy dẫn theo khối), (iii) F |-2 f (suy dẫn theo khối có không quá 2 phần tử). Đối với phụ thuộc hàm (PTH) trên khối r, ta đã định nghĩa khối r thỏa PTH f: X Y, kí hiệu r(f) nếu: Trịnh Đình Thắng, Trần Minh Tuyến 699 u, v r: u.X = v.X u.Y = v.Y Khi ta xem phụ thuộc hàm như là một trường hợp riêng của CTBD thì ta đã chấp nhận định nghĩa của khối r thỏa phụ thuộc hàm f: X Y nếu Tr Tf . Định lý cần và đủ sau đây khẳng định sự tương đương của hai định nghĩa trên: Định lý II.2 [7] Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, phụ thuộc hàm f: X Y với X, Y ( ) 1 n i i id . Khi đó: r(f) Tr Tf . Trong trường hợp F là tập các phụ thuộc hàm trên khối thì TF là giao của các Tf thành viên trong F nên ta lại có kết quả sau: Định lý II.3 [7] Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, tập phụ thuộc hàm F = {f: X Y | X, Y ( ) 1 n i i id }. Khi đó: r(F) Tr TF . Từ đây trở đi ta hiểu tập F trong lược đồ khối = (R, F) là tập các phụ thuộc Boolean dương trên R. Giả sử X ( ) 1 n i i id , v Bn x m (ở đây |id| = m), khi đó ta có: X(v) = 1 x (i) X: v. x (i) = 1 X(v) = 1 x (i) X: v. x (i) = 1 và X(v) = 0 x (i) X: v. x (i) = 0 X(v) = 0 x (i) X: v. x (i) = 0 Định nghĩa II.8 [8] Cho lược đồ khối R = (id; A1,A2,...,An ), B = {0,1}. Khi đó với mọi v B n x m ta kí hiệu: Set(v) = { x (j) | v. x (j) = 1} và với mỗi khối T B n x m ta kí hiệu : Set(T) = {Set(v) | v T}. Ta định nghĩa ánh xạ Vec: Subset(U) B n x m như sau: X U: Vec(X) = (vx (1) ,vx (2),, vx (n) )v id trong đó vx (i) = 1 nếu x(i) X, ngược lại vx (i) = 0 (1 ≤ i ≤ n, x id). III. KẾT QUẢ NGHIÊN CỨU A. Khối chân lý của khối dữ liệu và thuật toán TClosed& Định nghĩa III.1 Cho R = (id; A1,A2,...,An ), V là tập các phép gán trị trên . Giả sử u, v V, ta xét phép toán nhân của u và v, kí hiệu u&v, được xác định như sau: Nếu u =( ux (1) , ux (2) ,, ux (n) ) x id, v =( vx (1) , vx (2) ,, vx (n) ) x id thì u&v = ( ux (1) vx (1) , ux (2) vx (2),, ux (n) vx (n) ) x id . Ta quy ước tích của một tập rỗng các phần tử trong V chính là phép gán trị đơn vị e = (1, 1,, 1)x, x id. Định nghĩa III.2 Cho R = (id; A1,A2,...,An ), V là tập các phép gán trị trên . Tập các phép gán trị V gọi là đóng đối với phép nhân & nếu V chứa tích của mọi cặp phần tử trong nó, nghĩa là: u,v V: u&v V. Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R. Khi đó khối chân lý Tr là một khối nhị phân và nói chung không đóng với phép nhân & của các phần tử trong Tr. Giả sử T là một khối nhị phân, T B n x m , nếu khối T không đóng với phép nhân & thì ta có thể bổ sung vào khối T tối thiểu một số phần tử để được khối T* thỏa mãn hai tính chất sau: i) T* chứa phần tử đơn vị e và phần tử không z ii) T* đóng với phép nhân &. Ta gọi quá trình trên là làm đóng khối T theo phép nhân &. Thuật toán làm đóng khối nhị phân Thuật toán TClosed& Đầu vào: Khối nhị phân T B n x m, T={t1, t2, , tk} với phép nhân &. Đầu ra: Khối T* nhỏ nhất chứa T và T* chứa phần tử đơn vị e, phần tử không z, đóng với phép nhân &. Phương pháp ( ) 1 n i i id ( ) 1 n i i id ( ) 1 n i i id 700 VỀ VẤN ĐỀ THỂ HIỆN TẬP PHỤ THUỘC HÀM CỦA KHỐI DỮ LIỆU TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI T*:= T; i:=0; while i<k do i:= i+1; For j:=1 to i-1 do t:= ti & tj ; if t not_in T* then k:=k+1; add t to T* như là tk; endif; endfor; endwhile; T* := T* {e,z}; return T*; End TClosed& Định lý III.1 Với mỗi khối nhị phân T có các thuộc tính chỉ số thuộc gồm k phần tử thì thuật toán TClosed& bổ sung tối thiểu một số phần tử để thu được khối nhị phân T* chứa đơn vị e, không z và đóng đối với phép nhân &. Chứng minh Từ thuật toán TClosed& ta thấy khối nhị phân T* chứa các phần tử đơn vị e và không z. Do tính giao hoán của phép nhân &, nên khi vòng lặp while kết thúc thì T* là đóng đối với phép nhân &. Theo cách xây dựng các phần tử bổ sung vào T* trong thuật toán TClosed& ta thấy mỗi phàn tử mới bổ sung vào T* đều là tích của các phần tử thuộc T. Do vậy, một khối nhị phân bất kỳ T’ chứa T thì hiển nhiên nó phải chứa tích các phần tử bất kỳ của T, có nghĩa là nó chứa T* . Vậy T* là tập đóng với phép nhân & nhỏ nhất , suy ra thuật toán TClosed& đã bổ sung một số phần tử tối thiểu vào T để được T* chứa đơn vị e, không z và đóng đối với phép nhân &. Do các phần tử được bổ sung vào khối nhị phân T để được T* là tích các phần tử trong T nên chúng không thể là các phần tử sinh. Nhận xét này cho ta hệ quả sau: Hệ quả III.1 Nếu T* = TClosed&(T) thì T chứa tập các phần tử sinh của giàn T*. Mệnh đề III.1 Độ phức tạp thời gian của thuật toán TClosed& là O(k2). Chứng minh Thật vậy, từ hệ quả III.1 ta thấy T chứa tập các phần tử sinh của giàn T*, do đó theo tính chất của tập sinh ta có độ phức tạp thời gian của thuật toán TClosed& là O(k2). Ví dụ: Cho R = ({1, 2}, A1, A2, A3); r là một khối trên R, gồm 4 phần tử: t1, t2, t3, t4. Cụ thể như sau: t1.1 (1) = 1, t1.1 (2) = 1, t1.1 (3) = 1, t1.2 (1) = 1, t1.2 (2) = 1, t1.2 (3) = 1. t2.1 (1) = 0, t2.1 (2) = 0, t2.1 (3) = 0, t2.2 (1) = 0, t2.2 (2) = 0, t2.2 (3) = 0. t3.1 (1) = 1, t3.1 (2) = 1, t3.1 (3) = 0, t3.2 (1) = 1, t3.2 (2) = 1, t3.2 (3) = 0. t4.1 (1) = 0, t4.1 (2) = 1, t4.1 (3) = 1, t4.2 (1) = 0, t4.2 (2) = 1, t4.2 (2) = 1. Khi đó áp dụng thuật toán TClosed& ta bổ sung thêm được vào khối r này một phần tử thứ 5 kí hiệu t5 có giá trị cụ thể như sau: t5.1 (1) = 0, t5.1 (2) = 1, t5.1 (3) = 0, t5.2 (1) = 0, t5.2 (2) = 1, t5.2 (2) = 0. t5 = . Sau khi bổ sung phần tử mới t5 vào r thì khối r trở thành khối r* chứa phần tử đơn vị e và phần tử không z đồng thời đóng đối với phép &. B. Thể hiện tập phụ thuộc hàm của khối dữ liệu Định lý III.2 Cho R = (id; A1,A2,...,An ), F và G là hai tập phụ thuộc hàm trên R, U = . Khi đó, F và G là tương đương khi và chỉ khi X U: X+F = X + G. Chứng minh ) Giả sử F và G là tương đương ta cần chứng minh X U: X+F = X + G. Thật vậy, vì F G F+ = G+ , theo định nghĩa bao đóng của tập thuộc tính chỉ số ta có: X U: x (i) X + F X x (i) F + X x (i) G + x (i) X + G . Vậy ta có X U: X+F = X + G. ( ) 1 n i i id ( ) 1 n i i id 0 1 0 0 1 0 Trịnh Đình Thắng, Trần Minh Tuyến 701 ) Ngược lại, X U: X+F = X + G ta cần chứng minh F tương đương với G: F G. Thật vậy, theo giả thiết ta có X U: X+F = X + G . Khi đó, theo điều kiện của bài toán thành viên ta có: X Y F + Y X + F Y X + G X Y G + . Vậy suy ra: F+ = G+ nghĩa là: F G. Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = , S là một họ các tập con của U. Khi đó S được gọi là một hệ Sperner nếu các tập con trong S đôi một không bao nhau. Ta kí hiệu FD(r) là tập các phụ thuộc hàm đúng trong khối r. Định nghĩa III.3 Cho lược đồ khối a = (R,F), R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = , S là một hệ Sperner trên U. Khi đó ta nói khối r thể hiện hệ Sperner S nếu lược đồ khối b = (R, FD(r)) nhận S làm tập khóa: Key(b) = S. Định nghĩa III.4 Cho lược đồ khối a = (R,F), R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = . Khi đó ta nói khối r thể hiện tập phụ thuộc hàm F nếu FD(r) F+ và khối r thể hiện chặt tập phụ thuộc hàm F nếu FD(r) = F+. Mệnh đề III.2 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R. Khi đó, tập các khóa của khối r là một hệ Sperner. Chứng minh Theo định nghĩa của khóa trên khối ta thấy rõ ràng hai khóa khác nhau thì không bao nhau. Vậy suy ra tập các khóa của khối r là một hệ Sperner. Mệnh đề III.3 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = . F và G là các tập phụ thuộc hàm trên U. Nếu F và G là tương đương thì hai lược đồ khối a = (R,F) và b = (R,G) có cùng tập khóa: Key(a) = Key(b). Chứng minh Theo giả thiết ta có hai lược đồ khối a = (R,F) và b = (R,G), trong đó F G. Khi đó áp dụng kết quả của định lý III.2 và định nghĩa của khóa trên khối ta có: K Key(a) (KF + = U) ( A K: (K\A)F + U) (KG + = U) ( A K: (K\A)G + U) K Key(b) . Vậy ta có: Key(a) = Key(b). Định lý III.3 Cho lược đồ khối a = (R,F), R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = . Khi đó, nếu khối r thể hiện chặt tập phụ thuộc hàm F thì : i) Khối r thể hiện tập phụ thuộc hàm F. ii) Khối r thể hiện hệ Sperner Key(a). Chứng minh i) Theo giả thiết thì khối r là thể hiện chặt tập phụ thuộc hàm F, từ đó theo định nghĩa của thể hiện chặt ta suy ra khối r cũng thể hiện tập phụ thuộc hàm F. ii) Vì khối r là thể hiện chặt tập phụ thuộc hàm F, nên theo định nghĩa của thể hiện chặt ta có: FD(r) = F+, nghia là hai tập này là tương đương: FD(r) F+. Do vậy, ta suy ra hai lược đồ khối a = (R,F) và b = (R,FD(r)) là tương đương và do đó theo kết quả của mệnh đề III.3 thì chúng có cùng tập các khóa Key(a) = Key(b). Theo định nghĩa về việc thể hiện hệ Sperner của khối ta suy ra khối r thể hiện hệ Sperner Key(a). IV. KẾT LUẬN Mỗi phụ thuộc hàm được xây dựng tương ứng với một công thức suy dẫn Boolean trên lược đồ khối, phép toán nhân trên tập các phép gán trị trên khối đã chứng tỏ rằng khối chân lý của mỗi công thức suy dẫn f đều chứa các phép gán trị đơn vị e, không z và đóng với phép nhân &. Tuy nhiên, khối chân lý của khối dữ liệu thì nói chung không đóng đối với phép nhân &. Thuật toán làm đóng khối trị của một khối dữ liệu cho trước đã được xây dựng, nó bổ sung vào khối trị số phần tử ít nhất để khối trị đóng đối với phép nhân &. Điều kiện cần và đủ để hai tập phụ thuộc hàm trên lược đồ khối là tương đương cũng đã được đưa ra. Các tính chất của mối tương quan giữa các thể hiện trên khối đã được phát biểu và chứng minh. Một khối khi thể hiện chặt tập phụ thuộc hàm F thì nó cũng thể hiện hệ Sperner của tập các khóa. Những kết quả có được ở trên cho ta thấy rõ hơn cấu trúc và mối tương quan giữa các thể hiện trên khối dữ liệu trong lý thuyết thiết kế của mô hình dữ liệu dạng khối. Trên cơ sở của các kết quả này ta có thể nghiên cứu tiếp mối quan hệ giữa các loại thể hiện khác trên khối dữ liệu,... góp phần làm hoàn chỉnh thêm lí thuyết thiết kế mô hình cơ sở dữ liệu dạng khối. ( ) 1 n i i id ( ) 1 n i i id ( ) 1 n i i id ( ) 1 n i i id ( ) 1 n i i id 702 VỀ VẤN ĐỀ THỂ HIỆN TẬP PHỤ THUỘC HÀM CỦA KHỐI DỮ LIỆU TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI TÀI LIỆU THAM KHẢO [1] Nguyễn Xuân Huy, Trịnh Đình Thắng, “Mô hình cơ sở dữ liệu dạng khối”, Tạp chí Tin học và Điều khiển học, T.14, S.3 (52-60), 1998. [2] Nguyễn Xuân Huy, Các phụ thuộc logic trong cơ sở dữ liệu, NXB Thống kê, Hà Nội, 2006. [3] Trịnh Đình Thắng, “Một số kết quả về bao đóng, khóa và phụ thuộc hàm trong mô hình dữ liệu dạng khối”, Kỷ yếu Hội thảo quốc gia lần thứ IV “Một số vấn đề chọn lọc của công nghệ thông tin”, (245-251), Hải Phòng 05- 07/6/2001. [4] Trịnh Đình Thắng, Trần Minh Tuyến, “Phép dịch chuyển lược đồ khối và vấn đề biểu diễn bao đóng, khóa trong mô hình dữ liệu dạng khối”, Kỷ yếu Hội thảo quốc gia lần thứ XIII “Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông”, (276-286), Hưng Yên, 19-20/08/2010. [5] Trịnh Đình Thắng, Trần Minh Tuyến, “Khóa và các tập thuộc tính nguyên thủy, phi nguyên thủy với phép dịch chuyển lược đồ khối”, Kỷ yếu Hội thảo quốc gia lần thứ 13 Một số vấn đề chọn lọc của công nghệ thông tin và Truyền thông, (159-170), Cần Thơ 07-08/10/2011. [6] Trịnh Đình Thắng, Trần Minh Tuyến, “Lược đồ cân bằng, vế trái cực tiểu và khóa với phép dịch chuyển lược đồ khối”, Kỷ yếu Hội thảo quốc gia lần thứ XV Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, (174-179), Hà Nội 03-04/12/2012. [7] Tran Minh Tuyen, Trinh Dinh Thang, Nguyen Xuan Huy, “Some properties of the positive boolean dependencies in the database model of block form”, Journal of Computer Science and Cybernetics, V.31, N.2, (159-169), Viet Nam, 2014. [8] Trần Minh Tuyến, Trịnh Đình Thắng, Nguyễn Xuân Huy, “Phụ thuộc Boole dương tổng quát trong mô hình dữ liệu dạng khối”, Kỷ yếu hội thảo quốc gia lần thứ XVII Một số vấn đề chọn lọc của công nghệ thông tin và truyền thông, (274-279), Buôn Ma Thuột, 30-31/10/2014. ON THE PROBLEM OF EXPRESSING THE FUNCTIONAL DEPENDENCY SET OF THE DATA BLOCK IN THE DATABASE MODEL OF BLOCK FORM Trinh Dinh Thang, Tran Minh Tuyen ABSTRACT: The paper states and demonstrates some of the properties of a data block when expressing a set of functional dependencies in the database model of block form. The necessary and sufficient conditions for two sets of functional dependencies on the block schema are equivalent. Property for the equivalence of two sets of functional dependencies on the data block. The properties of correlation between the expressing on the data block are also stated and demonstrated In addition, algorithm for the closure of the block of values with multiplication of elements and its complexity has also been presented and proved correct here.