Phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 09-10/8/2018 DOI: 10.15625/vap.2018.00058  n i i 1 )(idYX, PHỤ THUỘC BOOLEAN DƯƠNG THEO NHÓM BỘ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Trịnh Đình Thắng 1, Trần Minh Tuyến 2, Trịnh Ngọc Trúc1 1 ĐHSP Hà Nội 2, 2 ĐH Công đoàn thangdhsp2@hpu2.edu.vn, tuyentm@dhcd.edu.vn, tructn@yahoo.com TÓM TẮT: Báo cáo đề xuất các khái niệm về khối chân lý theo nhóm bộ của khối, phụ thuộc Boolean dương theo nhóm bộ trong mô hình dữ liệu dạng khối, từ đó phát biểu và chứng minh định lý tương đương để khẳng định sự tương đương của ba loại suy dẫn trên lược đồ khối: suy dẫn logic, suy dẫn theo khối và suy dẫn theo khối có không quá p phần tử, điều kiện cần và đủ để một khối là thể hiện chặt của tập phụ thuộc Boolean dương theo nhóm bộ trên khối,... Ngoài ra, một số tính chất liên quan đến khối chân lý của khối và khối chân lý của tập phụ thuộc Boolean dương theo nhóm bộ trên khối cũng đã được phát biểu và chứng minh ở đây. Từ khóa: Phụ thuộc Boolean dương theo nhóm bộ, khối, lược đồ khối. I. MÔ HÌNH DỮ LIỆU DẠNG KHỐI 1.1. Khối, lát cắt của 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=1..n) 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 = { ti : 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. 1.2. 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ả mãn 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), Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 447  Ai ixX )(  Bj jxY )(  n i ix 1 )( t1(y (k)) = t1(y; Ak ), t2(y (k)) = t2(y; Ak ). Từ đây trở đi, để 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 }. Đị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 = Fh 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 bởi việc thay x bởi y. II. CÔNG THỨC BOOLEAN DƢƠNG 2.1. 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). 2.2. 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.  n i ix 1 )(  n i ix 1 )( 448 PHỤ THUỘC BOOLEAN DƢƠNG THEO NHÓM BỘ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Đị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. 2.3. 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. 2.4. 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 Boole 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 Boole 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. III. KẾT QUẢ NGHIÊN CỨU 3.1. Khối chân lý theo nhóm bộ của khối dữ liệu Định nghĩa III.1 Cho lược đồ khối R = (id; A1,A2,...,An ), r(R) là một khối trên R, ta quy ước rằng mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id), 1 i n, có chứa ít nhất p (p 2) phần tử. Khi đó, với mỗi miền trị di ta xét ánh xạ: i: (di) p B thỏa các tính chất sau: (i) Tính phản xạ: a (di) p: i(a) = 1, nếu trong a có ít nhất hai thành phần giống nhau. (ii) Tính giao hoán: a (di) p: i(a) = i(a’), trong đó a’ là một hoán vị của a. (iii) Tính bộ phận: a (di) p: i(a) = 0. Nhƣ vậy, ta thấy các ánh xạ i chính là phép đánh giá trên p giá trị của di thỏa các tính chất phản xạ và giao hoán. Quan hệ đẳng thức là một trƣờng hợp riêng của quan hệ này. Định nghĩa III.2 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di, của thuộc tính chỉ số x(i), x id, 1 i n. Với mỗi nhóm p phần tử: u1, u2, ..., up tùy ý (không nhất thiết phân biệt) trên khối, ta gọi ( u1, u2, ..., up) là phép gán trị: ( u1, u2, ..., up) = (tx1, tx2, ..., txn) trong đó txi = i(u1.x (i), u2.x (i),, ..., up.x (i)), x id, 1 i n. Khi đó, với mỗi khối r ta kí hiệu khối chân lý theo nhóm bộ của khối r là Tr: Tr = { (u1, u2, ..., up) | uj r, 1 j p }. Từ định nghĩa ta thấy khối chân lý theo nhóm bộ 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 khối chân lý theo nhóm bộ của khối lại trở thành khái niệm bảng chân lý theo nhóm bộ 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ý theo nhóm bộ của khối là mở rộng khái niệm bảng chân lý theo nhóm bộ của quan hệ trong mô hình dữ liệu quan hệ. 3.2. Phụ thuộc Boolean dƣơng theo nhóm bộ của khối dữ liệu Định nghĩa III.3 Cho lược đồ khối R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 449 thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x (i), x id, 1 i n.. Ta gọi mỗi công thức Boolean dương trong P(U), với U =  n i i 1 )(id , là một phụ thuộc Boolean dương theo nhóm bộ. Ta nói khối r thỏa mãn phụ thuộc Boolean dƣơng theo nhóm bộ (PTBDTNB) f, hoặc f đúng trong khối r và kí hiệu r(f) nếu Tr Tf. Khối r thỏa tập PTBDTNB F và kí hiệu r(F) nếu khối r thỏa mọi phụ thuộc f trong F: r(F) f F: r(f) Tr TF . Nếu có r(F) ta cũng nói tập PTBDTNB F đúng trong khối r. Cho tập PTBDTNB F và một PTBDTNB 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á p phần tử và kí hiệu F |- p f nếu: rp : rp(F) rp(f). Ta có định lý tƣơng đƣơng sau: Định lý III.1 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2)giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n, tập PTBDTNB F và một PTBDTNB f . 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 |- p f (suy dẫn theo khối có không quá p phần tử). Chứng minh (i) (ii): Ta cần chứng minh: F |= f F |- f . Thật vậy, theo giả thiết ta có F |= f TF Tf . (1) Giả sử r là một khối bất kì thỏa F: r(F), khi đó theo định nghĩa: Tr TF . (2) Từ (1) và (2) ta suy ra: Tr Tf , do đó: r(f). Nhƣ vậy từ r(F) ta suy ra r(f): r(F) r(f) nghĩa là: F |- f . Vậy ta có: F |= f F |- f . (ii) (iii): Ta cần chứng minh: F |= f F |- p f . Hiển nhiên, vì suy dẫn theo khối có không quá p phần tử là trƣờng hợp đặc biệt của suy dẫn theo khối. (iii) (i): Ta cần chứng minh: F |- p f F |= f . Thật vậy, từ giả thiết F |- p f nghĩa là với mọi khối rp có không quá p phần tử ta có: rp(F) rp(f), ta cần chứng minh F |= f nghĩa là TF Tf . Giả sử t = (tx1, tx2, ..., txn) x id , t TF, ta chứng minh t Tf. Nếu t = e thì ta có ngay t Tf vì nhƣ ta đã biết f là công thức Boole dƣơng. Nếu t e, ta xây dựng khối r gồm p phần tử nhƣ sau: theo tính chất bộ phận (c) của ánh xạ i: (di) p B thì ai = (ai1, ai2, ..., aip) sao cho i(ai) = 0. Khi đó, với mỗi miền trị di của các thuộc tính chỉ số x (i) trong U =  n i i 1 )(id , ta lấy một phần tử nào đó aij { ai1, ai2, ..., aip}. Nếu txi = 1 ta điền vào cột thuộc tính chỉ số x (i) của khối r với p giá trị bằng nhau và bằng aij. Nếu txi = 0 ta điền vào cột thuộc tính chỉ số x (i) của khối r với p giá trị ai1, ai2, ..., aip. Theo cách xây dựng khối r đó, ta có : Tr = {e, t} TF với e là phép gán trị đơn vị. Nhƣ vậy r là khối có p phần tử và thỏa tập PTBDTNB F. Theo giả thiết nếu r thỏa F thì r sẽ thỏa mãn f, điều này có nghĩa là: Tr = {e, t} Tf , suy ra: t Tf. Trong trƣờng hợp tập chỉ số id = {x}, khi đó khối suy biến thành quan hệ và định lý tƣơng đƣơng ở trên lại trở thành định lý tƣơng đƣơng trong mô hình dữ liệu quan hệ. Cụ thể, ta có hệ quả sau: 450 PHỤ THUỘC BOOLEAN DƢƠNG THEO NHÓM BỘ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI Hệ quả III.1 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n, tập PTBDTNB F và một PTBDTNB f. Khi đó nếu id = {x} thì khối r suy biến thành quan hệ và ba mệnh đề sau là tương đương: (i) F |= f (suy dẫn logic), (ii) F |- f (suy dẫn theo quan hệ), (iii) F |- p f (suy dẫn theo quan hệ có không quá p phần tử). Đây chính là một kết quả đã đƣợc chứng minh trong mô hình dữ liệu quan hệ. Định nghĩa III.4 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n, là tập PTBDTNB xét trên các nhóm p bộ. Khi đó bao đóng + của tập PTBDTNB được xác định như sau: + = { f | f P(U), |= f } = { f | f P(U), T Tf }. Định nghĩa III.5 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó ta kí hiệu NBD(r) là tập các PTBDTNB thỏa mãn trong khối r, nghĩa là: NBD(r) = {f | f P(U), r(f)}. Mệnh đề III.1 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó ta có: (NBD(r))+ = NBD(r). Chứng minh Theo định nghĩa, ta có: (NBD(r))+ = { f | f P(U), NBD(r) |= f } = { f | f P(U), TNBD(r) Tf }. Nhƣ vậy suy ra: (NBD(r))+ NBD(r) (3) Mặt khác, giả sử ta có: g (NBD(r))+, ta cần chứng minh g NBD(r). Thật vậy, từ giả thiết g (NBD(r))+ = { f | f P(U), TNBD(r) Tf } g P(U), TNBD(r) Tg. Mà theo định nghĩa của NBD(r) ta có: Tr TNBD(r) Tr Tg (theo tính bắc cầu) khối r thỏa PTBDTNB g. Từ đó ta có: g NBD(r) (NBD(r))+ NBD(r) (4) Từ (3) và (4) ta suy ra: (NBD(r))+ = NBD(r). Hệ quả III.2 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó, nếu id = {x} thì khối r suy biến thành quan hệ và ta có trong mô hình dữ liệu quan hệ: (NBD(r))+ = NBD(r). Mệnh đề III.2 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó ta có: Tr = TNBD(r). Chứng minh: Theo định nghĩa của tập các PTBDTNB NBD(r) ta có: nếu f NBD(r) khối r thỏa PTBDTNB f Tr Tf. Theo tính chất về tƣơng quan giữa các công thức Boolean và khối chân lý, từ khối chân lý Tr ta tìm đƣợc một công thức Boolean h sao cho: Th = Tr. Mặt khác, vì e Tr = Th nên h là công thức Boolean dƣơng. Từ đẳng thức: Tr = Th ta suy ra khối r thỏa PTBDTNB h, nghĩa là h NBD(r). Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 451 Vậy suy ra: NBD(r) |= h . Do đó ta có: TNBD(r) Th = Tr. TNBD(r) Tr (5) Từ định nghĩa của NBD(r) ta có: Tr TNBD(r) (6) Kết hợp (5) và (6) ta suy ra: Tr = TNBD(r). Hệ quả III.3 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó, nếu id = {x} thì khối r suy biến thành quan hệ và ta có trong mô hình dữ liệu quan hệ: Tr = TNBD(r). Định nghĩa III.6 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Ta nói khối r thể hiện tập PTBDTNB nếu NDB(r) + và khối r thể hiện chặt tập PTBDTNB nếu NDB(r) = +. Nếu khối r là thể hiện chặt tập PTBDTNB thì ta nói r là khối Armstrong của tập PTBDTNB . Định lý III.2 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó khối r thể hiện chặt tập PTBDTNB nếu và chỉ nếu Tr = T . Chứng minh: Sử dụng kết quả của các mệnh đề III.1 và mệnh đề III.2 về các PTBDTNB ta có: (NBD(r))+ = NBD(r) và Tr = TNBD(r). Khi đó: r là thể hiện chặt tập PTBDTNB NBD(r) = + NBD(r) TNBD(r) = T Tr = T . Do đó: r là thể hiện chặt tập PTBDTNB Tr = T ,m. Hệ quả III.4 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, mỗi miền trị di của thuộc tính Ai (cũng là của thuộc tính chỉ số x(i), x id,1 i n), có chứa ít nhất p phần tử, i là các phép đánh giá trên p (p 2) giá trị ứng với mỗi miền trị di của thuộc tính chỉ số x(i), x id, 1 i n. Khi đó, nếu id = {x} thì khối r suy biến thành quan hệ và ta có trong mô hình dữ liệu quan hệ: quan hệ r là thể hiện chặt tập PTBDTNB khi và chỉ khi Tr = T . IV. KẾT LUẬN Với khái niệm mới đƣợc đề xuất là phụ thuộc Boole dƣơng theo nhóm bộ trên khối, bài báo đã đƣa ra khái niệm khối chân lý theo nhóm bộ của khối dữ liệu, phát biểu và chứng minh định lý tƣơng đƣơng cho các phụ thuộc Boolean dƣơng theo nhóm p (p 2) bộ trên khối, chứng minh điều kiện cần và đủ để một khối là thể hiện chặt tập PTBDTNB đã cho Trong trƣờng hợp tập chỉ số id = {x}, khối suy biến thành quan hệ thì các kết quả này lại trùng với các kết quả đã đƣợc nhiều tác giả đƣa ra đối với quan hệ trong mô hình dữ liệu quan hệ. Từ 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 phụ thuộc logic khác trên lƣợc đồ khối,... một số kết quả mới có thể đƣợc tìm thấy khi xét mối quan hệ giữa các tập PTBDTNB trên khối và trên các lát cắt,... 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. V. 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, 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. 452 PHỤ THUỘC BOOLEAN DƢƠNG THEO NHÓM BỘ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI [4] 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. [5] 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. POSITIVE BOOLEAN DEPENDENCIES BY GROUPS IN THE DATABASE MODEL OF BLOCK FORM Trinh Dinh Thang, Tran Minh Tuyen, Trinh Ngoc Truc ABSTRACT: The report proposes the concepts of truth blocks by groups in block, Boolean positive dependencies by groups in the database model of block form, then states and proved the equivalence theorem to assert equivalence for three types of inference on block diagrams: logical inference, block inference, and block inference have no more than p elements, necessary and sufficient conditions for a block to be a solid representation of a set of positive Boolean dependencies by groups on the block ... In addition, some properties related to the truth block of the block and the truth block of the positive Boolean dependence set on the block are also stated and demonstrated here.