Phụ thuộc Boolean dương đa trị trong mô hình dữ liệu dạng khối

trị của dòng tƣơng ứng. Nhƣ vậy, bảng trị chứa 
 kn dòng, n là số phần tử của P, k là số phần tử của B. 
 Định nghĩa II.5 [2] 
 Cho m [0 ;1], bảng chân lý ngưỡng m của f hoặc bảng m-chân lý của f , kí hiệu Tf,m là tập các phép gán trị v 
 sao cho f(v) nhận giá trị không nhỏ thua m: 
 n
 Tf,m = {v B | f(v) m} 
 Khi đó, bảng m-chân lý TF,m của tập hữu hạn các công thức F trên P, chính là giao của các bảng m-chân lý 
 của mỗi công thức thành viên trong F. 
 TF,m = Tfm, . 
 fF 
 Ta có: v TF,m khi và chỉ khi f F: f(v) m. 
II.3 Suy dẫn logic 
 Định nghĩa II.6 [2] 
 Cho f, g là hai CTBĐT và trị m B. Ta nói công thức f dẫn ra được công thức g theo ngưỡng m và kí hiệu f 
Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 605 
|=m g nếu Tf,m  Tg,m . Ta nói f và g là hai công thức tương đương theo ngưỡng m, kí hiệu f≡m g nếu Tf,m = Tg,m. 
 Với F, G trong MVL(P) và trị m [0;1], ta nói F dẫn ra được G theo ngưỡng m, kí hiệu F |=m G nếu TF,m  
TG,m . Hơn nữa, ta nói F và G là tương đương theo ngưỡng m, kí hiệu F≡m G nếu TF,m = TG,m . 
II.4 Công thức Boolean dương đa trị 
 Định nghĩa II.7 [2] 
 Công thức f MVL(P) được gọi là công thức Boolean dương đa trị (CTBDĐT) nếu f(e) = 1 với e là phép gán 
trị đơn vị: e = (1, 1, ..., 1), ta kí hiệu MVP(P) là tập toàn bộ các công thức Boolean dương đa trị trên P. 
 III. KẾT QUẢ NGHIÊN CỨU 
III.1 Khối m-chân lý của khối dữ liệu 
 Định nghĩa III.1 n
 id ()i
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = i 1 , |id|=s, ta gọi mỗi vector các phần tử v = {vi1, vi2, ..., 
 nxs
vin}i=1..s trong không gian B là một phép gán trị. Như vậy, với mỗi CTBĐT f MVL(U) ta có f(v) = f(vi1, vi2, ..., 
vin)i=1..t là trị của công thức f đối với phép gán trị v. 
 (1) (2) (3) (1) (2) (3)
 Ví dụ III.1: Cho R = ({1,2}, A1, A2, A3), khi đó U = {1 , 1 , 1 , 2 , 2 , 2 }, B ={0, 0.5, 1}. 
 0.5 1 0.5 ( 1) (2) (1) (2) (3) (3)
 Cho v = , f = 1 1 2 2 1 2 , khi đó ta có f(v) = max( 1 - min(0.5, 1, 1, 0.5), min(0.5, 
0.5)). 1 0.5 0.5
 Suy ra : f (v) = 0.5. 
 Ta có hai phép gán trị đặc biệt : 
 111 000
 Phép gán trị đơn vị : e = , và phép gán trị 0 : z = ... . 
 ... 
 Định nghĩa III.2 111 000
 Cho m [0 ;1], khối chân lý ngưỡng m của f hoặc khối m-chân lý của f, kí hiệu Tf,m là tập các phép gán trị v 
sao cho f(v) nhận giá trị không nhỏ thua m: 
 nxs 
 Tf,m = {v B | f(v) m} 
 Khi đó, khối m-chân lý TF,m 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 khối m-chân lý 
của mỗi công thức thành viên f trong F. 
 TF,m = Tfm, . 
 fF 
 Ta có: v TF,m khi và chỉ khi  f F: f(v) m. 
 Với |B | = k thì khi đó |B nxs | = k nxs, ta có định lý sau: 
 Định lý III.1 
 nxs nxs
 Với mỗi khối T={t1, t2, , td}  B và mỗi dãy trị m1, m2,,md trong B , 1 d k , tồn tại một CTBĐT f 
thỏa hai tính chất sau: 
 (i)  ti T: f(ti) = mi, 
 (ii)  t B nxs\ T: f(t)= 0. 
 Chứng minh: 
 Với mỗi ti T: ti = {tij1, tij2, ..., tijn}j=1..s , 1 i d, ta xây dựng công thức : 
 (j1) (j2) (jn) (j1) (j2) (jn)
 hi (x , x ,, x )j=1..s = (Itij1(x ), Itij2(x ),,Itijn(x ), mi)j=1..s. 
 (j1) (j2) (jn)
 khi đó nếu (x , x ,, x )j=1..s = ti = {tij1, tij2, ..., tijn}j=1..s 
 thì hi (ti) = mi , hi (t) = 0 với t ti , 1 i d. 
 (j1) (j2) (jn)
 Do vậy, nếu ta đặt: f(x , x ,, x )j=1..s = h1  h2    hd thì f chính là công thức cần tìm. 
 Thật vậy, ta có: f(ti) = (h1  h2    hd)(ti) = h1(ti)  h2(ti)  hi(ti)  hd(ti) 
 Mà theo tính chất của hi: hi (ti) = h({tij1, tij2, ..., tijn}j=1..s) = (Itij1(tij1), Itij2(tij2),,Itijn(tijn), mi)j=1..s = mi, 
 hi (t) = 0 với t ti , 1 i d. 
606 PHỤ THUỘC BOOLEAN DƢƠNG ĐA TRỊ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI 
 nxs
 Vậy suy ra: f(ti) = mi , 1 i d và  t B \ T: f(t)= 0 f chính là CTBĐT cần tìm. 
 Hệ quả III.1: Với mỗi khối T B nxs, T  và mỗi trị m>0 trong B, tồn tại một CTBĐT f nhận T làm khối 
m-chân lý, tức là Tf,m = T. 
 Chứng minh: 
 Sử dụng kết quả của định lý III.1 với trƣờng hợp đặc biệt: m1 = m2 =  = md = m ta thu đƣợc CTBĐT f thỏa 
mãn hai điều kiện: 
 (i)  ti T: f(ti) = mi, 
 (ii)  t B nxs\ T: f(t)= 0. 
 Từ đó suy ra: Tf,m = T. 
 Định nghĩa III.3 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = , mỗi CTBĐT f MVL(U) được gọi là công thức 
Boolean dương đa trị (CTBDĐT) nếu f(e) = 1, với e là phép gán trị đơn vị. Ở đây: 
 111
 ...
 e = . 
 111
 Ví dụ III.2: 
 (1) (2) (3) (1) (2) (3)
 Cho R = ({1,2}, A1, A2, A3), U = {1 , 1 , 1 , 2 , 2 , 2 }, B ={0, 0.5, 1}. Khi đó: 
 - Các công thức: 1(1) 1(2) 2(1) 2(2), 1(1) 1(2) 2(1) 2(2) là các CTBDĐT. 
 - Các công thức : 1(2)  ( 2(3)), ( 1(3))  ( 2(1)) không phải là các CTBDĐT. 
 Ta kí hiệu MVP(U) là tập toàn bộ các công thức Boolean dƣơng đa trị trên U. 
 Định nghĩa III.4 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, ta kí hiệu di là miền trị của thuộc tính Ai (cũng là của thuộc 
 (i)
tính chỉ số x , x id), 1 i n. Khi đó, với mỗi miền trị di ta xét ánh xạ: i: di x di B thỏa các điều kiện sau: 
 (i) Tính phản xạ:  a di: i(a,a) = 1, 
 (ii) Tính đối xứng:  a,b di: i(a,b )= i(b,a), 
 (iii)Tính đầy đủ:  m B,  a,b di: i(a,b) = m. 
 Nhƣ vậy, ta thấy các ánh xạ i chính là các quan hệ trên di thỏa các tính chất phản xạ, đối xứng và đầy đủ. 
Quan hệ đẳng thức với logic hai trị B ={0,1} là trƣờng hợp riêng của quan hệ trên. 
 Định nghĩa III.5 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, u,v r, các ánh xạ i xác định trên mỗi miền trị di, 1 i 
 (1) (1) (2) (2) (n) (n)
n. Ta gọi (u,v) là phép gán trị: (u,v) = ( 1(u.x ,v.x ), 2(u.x ,v.x ), ..., n(u.x ,v.x )) 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 }. 
 Nếu khối r có chứa ít nhất một phần tử u nào đó thì: (u,u) = e e Tr. 
 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ý 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 dữ liệu quan hệ. 
 III.2 Phụ thuộc Boole dương đa trị trên khối 
 Định nghĩa III.5 n
 id ()i
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = i 1 , ta gọi mỗi công thức Boolean dương đa trị trong 
MVP(U) là một phụ thuộc Boolean dương đa trị (PTBDĐT) trên khối. 
 Ta nói khối r m-thỏa phụ thuộc Boolean dương đa trị f và kí hiệu r(f,m) nếu Tr  Tf,m . 
 Khối r m-thỏa tập phụ thuộc Boolean dương đa trị F và kí hiệu r(F,m) nếu khối r thỏa mọi PTBDĐT f trong F: 
 r(F,m)  f F: r(f,m) Tr  TF,m . 
 Nếu có r(f,m) ta cũng nói PTBDĐT f m-đúng trong khối r. 
Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 607 
 Cho tập PTBDĐT F và một PTBDĐT f:, m [0;1]: 
 - Ta nói F m-dẫn ra f theo khối và kí hiệu F |-m f nếu:  r: r(F,m) r(f,m). 
 - Ta nói F m-dẫn ra f theo khối có không quá 2 phần tử và kí hiệu F |-2,m f nếu:  r2 : r2(F,m) r2(f,m). 
 Ta có định lý tƣơng đƣơng sau: 
 Định lý III.2 
 Cho tập PTBDĐT F và một PTBDĐT f , R = (id; A1,A2,...,An ), r(R) là một khối trên R, m B. Khi đó ba 
mệnh đề sau là tương đương: 
 (i) F |=m f (suy dẫn logic), 
 (ii) F |-m f (suy dẫn theo khối), 
 (iii) F |-2,m f (suy dẫn theo khối có không quá 2 phần tử). 
 Chứng minh 
 (1)
 (i) => (ii): Theo giả thiết ta có F |=m f => TF,m  Tf,m . Giả sử r là một khối bất kì và r(F,m), khi đó theo 
 (2)
định nghĩa: Tr  TF,m . Từ (1) và (2) ta suy ra: Tr  Tf,m , vậy ta có: r(f,m). 
 (ii) => (iii): Hiển nhiên, vì suy dẫn theo khối có không quá 2 phần tử là trƣờng hợp đặc biệt của suy dẫn theo 
khối. 
 (1) (2) (n)
 (iii) => (i): Giả sử t = (x , x , ..., x ) x id , t TF,m, ta cần chứng minh t Tf,m. 
 Thật vậy, nếu t = e thì ta có ngay t Tf,m vì nhƣ ta đã biết f là công thức Boolean dƣơng. Nếu t e , ta 
 (1) (2) (n) (1) (2) (n)
xây dựng khối r gồm 2 phần tử u và v nhƣ sau: u = (y , y , ..., y ) y id , v = (z , z , ..., z ) z id sao cho (u,v) 
 (i) (i)
= t (nghĩa là i(y ,z ) = ti , 1 i n). Sự tồn tại của các phần tử u và v nhƣ trên là do tính chất của các ánh xạ i đã nói 
tới ở trên. Nhƣ vậy r là khối có 2 phần tử và Tr = {e, t}  TF,m , với e là phần tử của khối mà mọi giá trị thành phần 
đều bằng 1. 
 (1)
 Từ đó suy ra r(F,m). Theo giả thiết thì từ r(F,m) => r(f,m), do đó Tr  Tf,m . 
 Từ bao hàm thức (1) ta suy ra t Tf,m. 
 Trong trƣờng hợp tập id = {x}, khi đó khối suy biến thành quan hệ và định lý m-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: 
 Hệ quả III.2 
 Cho tập PTBDĐT F và một PTBDĐT f , R = (id; A1,A2,...,An ), r(R) là một khối trên R, m B. 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 |=m f (suy dẫn logic), 
 (ii) F |-m f (suy dẫn theo quan hệ), 
 (iii) F |-2,m f (suy dẫn theo quan hệ có không quá 2 phần tử). 
 Định nghĩa III.6 n
 id ()i
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = i 1 , m B,  là tập con các PTBDĐT trên U, ta kí 
 hiệu (,m)+ là tập tất cả các PTBDĐT được m-suy dẫn từ , nói một cách khác: 
 +
 (,m) = {g MVP(U) |  |=m g} = { g MVP(U) | T,m  Tg,m }. 
 Định nghĩa III.7 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = , m B, ta kí hiệu MBDĐT(r,m) là tập tất cả các 
 PTBDĐT m-đúng trong r, nói một cách khác: 
 MBDĐT(r,m) = {g MVP(U) | r(g,m)} 
 Nhƣ vậy, ta có: g MBDĐT(r,m) g MVP(U)  Tr  Tg,m . 
 Định lý III.3 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = , m B. Khi đó ta có: 
 (MBDĐT(r,m),m)+ = MBDĐT(r,m). 
608 PHỤ THUỘC BOOLEAN DƢƠNG ĐA TRỊ TRONG MÔ HÌNH DỮ LIỆU DẠNG KHỐI 
 Chứng minh 
 +
 Theo định nghĩa, ta có: (MBDĐT(r,m),m) ={g MVP(U) | MBDĐT(r,m) |=m g} (1) 
 Áp dụng kết quả của định lý ba mệnh đề tƣơng đƣơng cho PTBDĐT, ta lại có: 
 {g MVP(U) | MBDĐT(r,m) |=m g} = {g MVP(U) | MBDĐT(r,m) |-m g} (2) 
 Từ (1) và (2) ta suy ra: (MBDĐT(r,m),m)+ = MBDĐT(r,m). 
 Vậy hai tập (MBDĐT(r,m),m)+ và MBDĐT(r,m) là hai tập PTBDĐT m-tƣơng đƣơng trên khối. 
 Hệ quả III.3 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, m B. 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ệ: (MBDĐT(r,m),m)+ = MBDĐT(r,m). 
 Định nghĩa III.8 n
 id ()i
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, U = i 1 , m B,  là tập con các PTBDĐT trên U. Ta 
 nói khối r là m-thể hiện tập  nếu MBDĐT(r,m) ( ,m)+ và khối r là m-thể hiện chặt tập  nếu MBDĐT(r,m)= 
 ( ,m)+. 
 Nếu khối r là m-thể hiện chặt tập PTBDĐT  thì ta nói r là khối m-Armstrong của tập PTBDĐT . 
 Định lý III.4 
 Cho R = (id; A1,A2,...,An ), m B. Khi đó, với mọi khối r(R) khác rỗng trên R ta có: 
 Tr = TMBDĐT(r,m),m. 
 Chứng minh 
 Giả sử g MBDĐT(r,m) r là m-thỏa g Tr  Tg,m. Từ khối Tr và giá trị m, theo định lý III.1 ta tìm đƣợc 
 một công thức Boolean đa trị f thỏa điều kiện: f(e) = 1 và Tf,m = Tr. Nhƣ vậy: e Tr = Tf,m nên f là một 
 CTBDĐT và hơn nữa do Tr = Tf,m r là m-thỏa f, nghĩa là: f MBDĐT(r,m). 
 Ta kí hiệu: F = MBDĐT(r,m), từ chứng minh trên ta có: 
 Tgm,
 -  g MBDĐT(r,m) Tr  Tg,m Tr  gF (3) 
 -  f MBDĐT(r,m): Tr = Tf,m Tr  (4) 
 Từ (3) và (4) ta suy ra: 
 Tr = = TF,m . 
 Vậy: Tr = TMBDĐT(r,m),m. 
 Hệ quả III.4 
 Cho R = (id; A1,A2,...,An ), r(R) là một khối trên R, m B. 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 = TMBDĐT(r,m),m. 
 Định lý III.5 
 Cho R = (id; A1,A2,...,An ), U = , m B,  là tập con các PTBDĐT trên U. Khi đó, với mọi khối r(R) 
 khác rỗng trên R ta có: r là m-thể hiện chặt tập PTBDĐT  khi và chỉ khi Tr = T,m. 
 Chứng minh 
 + 
 Theo định nghĩa, ta có: r là m-thể hiện chặt  MBDĐT(r,m) = (, m) MBDĐT(r,m) m . 
 Mặt khác: MBDĐT(r,m) m  TMBDĐT(r,m),m = T,m. (5) 
 Áp dụng kết quả của định lý III.4 ta đƣợc: Tr = TMBDĐT(r,m),m. (6) 
 Vậy từ (5) và (6) ta suy ra: Tr = T,m. 
 Do đó: r là m-thể hiện chặt tập  Tr = T,m. 
 Hệ quả III.5 
 Cho R = (id; A1,A2,...,An ), U = , m B,  là tập con các PTBDĐT trên U. 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ệ: mọi quan hệ r khác rỗng trên R là m-thể 
 hiện chặt tập PTBDĐT  khi và chỉ khi Tr = T,m. 
Trịnh Đình Thắng, Trần Minh Tuyến, Trịnh Ngọc Trúc 609 
 Hệ quả này chính là kết quả mà ta đã biết trong mô hình dữ liệu quan hệ. 
 IV. KẾT LUẬN 
 Từ khái niệm mới đƣợc đề xuất là phụ thuộc Boole dƣơng đa trị trên khối, bài báo đã định nghĩa khối chân lý 
của khối dữ liệu, chứng minh tính đầy đủ của họ hàm I,  và , phát biểu và chứng minh định lý tƣơng đƣơng cho các 
phụ thuộc Boolean dƣơng đa trị trên khối, đặc biệt là điều kiện cần và đủ để một khối là m-thể hiện chặt tập PTBDĐT 
 đã 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ệ. 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 phụ thuộc logic khác trên lƣợc đồ khối..., một số kết quả khác có thể 
đƣợc xét trong trƣờng hợp riêng của tập các phụ thuộc hàm F nhƣ tập các phụ thuộc hàm Fh, tập các phụ thuộc hàm Fhx 
..., 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. 
 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. 
[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. 
 MULTIVALUE POSITIVE BOOLEAN DEPENDENCIES 
 IN THE DATABASE MODEL OF BLOCK FORM 
 Trinh Dinh Thang, Tran Minh Tuyen, Trinh Ngoc Truc 
ABSTRACT — The report proposed the concept of multivalue positive Boolean dependencies in the database model of block form, 
proved the sufficient properties of the functions I,  and , equivalence of three types derived: logically m-derived, m-derived by 
block, m-derived by block not exceeding two elements, the necessary and sufficient criteria of the tight expression for the set of 
multivalue positive Boolean dependencies... In addition, the properties related to this concept while the block degenerate into 
relationship has been stated and proved here.