Quan hệ giữa phụ thuộc hàm nới lỏng và phụ thuộc Boole dương tổng quát

 tác giả Nguyễn Xuân Huy và Lê Thị Ví dụ, cho tập U={a,b,c} khi đó công thức f :ab→c là
Thanh đã đề xuất một loại phụ thuộc dữ liệu mới là phụ một công thức Boole dương vì f (1,1,1) = 1.
thuộc Boole dương tổng quát (PTBDTQ) và chứng minh
phụ thuộc hàm và một số biến thể của phụ thuộc hàm như Bảng II
 BẢNG CHÂN LÝ T
phụ thuộc yếu, phụ thuộc mạnh, phụ thuộc đối ngẫu là 
những trường hợp riêng của phụ thuộc Boole dương tổng a b c ab f =ab→c
quát [1], [3]. Tiếp đến trong các năm từ 2012 đến 2016 0 0 0 0 1
 0 0 1 0 1
nhóm nghiên cứu về phụ thuộc Boole dương tổng quát đã 0 1 0 0 1
tiếp tục chứng minh rằng các phụ thuộc sai khác [6] và các 0 1 1 0 1
biến thể như các phụ thuộc hàm xấp xỉ [4] cũng là những 1 0 0 0 1
 1 0 1 0 1
trường hợp riêng của phụ thuộc Boole dương tổng quát. 1 1 0 1 0
 1 1 1 1 1
 Trong bài này, tiếp tục mạch nghiên cứu trên, sẽ chỉ ra
rằng các phụ thuộc hàm nới lỏng cũng là những trường hợp
riêng của phụ thuộc Boole dương tổng quát. Nếu U = { x1, x2,..., x푛 } là tập các thuộc tính và v là
 một bộ trong quan hệ r trên U, x ∈ U thì v.x được ký hiệu
 là trị của thuộc tính x trong bộ v. Nếu X ⊆ U thì ta định
II. CÁC KHÁI NIỆM VÀ QUY ƯỚC
 nghĩa v.X = {v.x | x∈X}. Với tập thuộc tính U cho trước,
 quan hệ trên tập thuộc tính U được kí hiệu là r, khi cần
 Cho U = { x1, ..., x푛 } là tập hữu hạn các biến Boole
nhận giá trị trong tập trị logic B = {0, 1} Tập các công chỉ rõ tập thuộc tính ta có thể sử dụng kí hiệu r(U).
thức Boole (CTB), kí hiệu L(U), bao gồm các biểu thức Các qui ước và kí pháp truyền thống khác được giới thiệu
được xây dựng từ các biến trong U, các hằng 0/1 và các trong các tài liệu kinh điển về cơ sở dữ liệu và được trích
phép toán logic ∧, ∨, ¬, → dẫn trong [1] và [2].
 푛
 Mỗi vector 0/1, v = (v1,...,vn) trong không gian B được III. PHỤ THUỘC BOOLE DƯƠNG TỔNG QUÁT
gọi là một phép gán trị. Khi đó với mỗi CTB f = L(U),
 Cho U = {x1, ..., x } là tập hữu hạn các biến Boole
f (v) là trị của công thức f đối với phép gán trị v. Kí hiệu e
 nhận giá trị trong tập trị logic B = {0, 1}.
là phép gán trị đơn vị, e = (1,1,...,1). Công thức f = L(U)
 Ta quy ước mỗi miền trị d của thuộc tính x trong U
được gọi là công thức Boole dương (CTBD) nếu f (e)= 1. 
 có chứa ít nhất hai phần tử. Với mỗi miền trị d , xét ánh
 Ký hiệu P(U). Với mỗi công thức Boole f ∈ L(U), kí 2
 xạ ∝ : d → B thoả các tiên đề sau [2][3]:
hiệu T = { v ∈ B푛| f (v) = 1 } là bảng chân lí của f. Mỗi
 v ∀a, b∈d
tập công thức F ⊆ L(U) được hiểu là một hội logic của các 
 Ñ v A1) Tiên đề phản xạ ∝ (a, a) = 1
công thức thành phần, F = ∧f | f ∈ F. Khi đó, T 퐹 = T 
| f ∈ F là bảng chân lí của tập công thức F. Với hai CTBD v A2) Tiên đề đối xứng ∝ (a, b) = ∝ (b, a)
f và g trên U, ta đã biết CTBD g được suy dẫn logic từ v A3) Tiên đề bộ phận ∃c ∈ d : ∝ (a, c) = 0
CTBD f và được ký hiệu là f → g khi và chỉ khi T ∈
 ∝ chính là quan hệ (hai ngôi) bộ phận thực sự, thoả các
T . Tương tự, nếu F là tập các CTBD trên U thì F → g
 tính chất phản xạ và đối xứng trên miền trị d . Việc xác
khi và chỉ khi T 퐹 ⊆ T . Hai tập CTBD F và G trên U là
 định ∝ được hiểu là thiết lập một phép sánh trị trên miền
tương đương nhau khi và chỉ khi T 퐹 = T .
 trị d cho thuộc tính x
 Theo truyền thống của lý thuyết cơ sở dữ liệu, ta chấp
 Quan hệ bằng = (tạm gọi là quan hệ đẳng thức) được
nhận các ký hiệu sau đây:
 định nghĩa: ∀a, b ∈ d : = (a, b) = 1, khi và chỉ khi a = b,
 Hợp của hai tập X và Y được viết XY; giao của hai tập là trường hợp riêng của phép sánh trị và được ngầm định
X và Y được viết XÑY; phép trừ hai tập X và Y được ký trong rường hợp không định nghĩa tường minh phép sánh
hiệu là X-Y. trị cho thuộc tính x.
 45
 Tập 2020, Số 1, Tháng 6
 Ta gọi lược đồ dữ liệu là một cặp p = (U, F), trong đó f (X (훾)→Y(휗), X, Y ⊆ U
U là tập thuộc tính với các miền trị tương ứng và các phép
sánh trị trên mỗi miền trị, F là tập các phụ thuộc trên U Ta nói phụ thuộc hàm nới lỏng f thỏa trong quan hệ r(U)
[1][2][3]. nếu:
 Cho lược đồ p = (U, F) và quan hệ r trên U. Với mỗi f (X (훾)→Y(휗), X, Y ⊆ U
cặp bộ u = (u1, u2,... , u푛), v = (v1, v2,... , v푛) trong r, ta
 ∈
đặt tương ứng một vector 0/1 t = (t1, t2,... , t푛) ∈ B 푛 và kí Với mọi cặp bộ u, v r, nếu tân từ 훾(u.X,v.X) suy ra
hiệu là t = ∝(u, v), trong đó thành phần t.x ứng với thuộc dược tân từ 휗(u.X,v.Y).
tính x trong U chính là ảnh của ánh xạ t.x = ∝ (u.x, v.x). Phụ thuộc hàm nới lỏng được hiểu là phụ thuộc hàm với
 Khi đó mỗi quan hệ r sẽ được đặt tương ứng với tập các điều kiện kèm theo nhằm giảm nhẹ các điều kiện của phụ
vector 0/1, T = { ∝( u, v) | u, v ∈ r}, và được gọi là bảng thuộc hàm chính thống. Các điều kiện giảm nhẹ được phát
trị của quan hệ r trên LĐBDTQ p [2][3]. biểu thông qua các tân từ 훾 và 휗
 Quan hệ r trên tập thuộc tính U thỏa PTBDTQ f (tập
PTBDTQ F) và viết r(f) (r(F)) nếu T ⊆ T (T ⊆ T퐹 ). V. CÁC LỚP BIẾN THỂ CỦA PHỤ THUỘC
 Mỗi công thức Boole dương f trong P(U) với các phép BOOLE DƯƠNG TỔNG QUÁT
sánh trị cho trước được gọi là một phụ thuộc Boole dương Các kết quả chủ yếu của mục này cho thấy, tùy thuộc
tổng quát (PTBDTQ), lược đồ thu được trong trường hợp vào các dạng của công thức Boole dương cụ thể và phép
này được gọi là lược đồ với phụ thuộc boole dương tổng sánh trị alpha cụ thể ta có thể nhận được các phụ thuộc nới
quát. lỏng khác nhau ứng với các lược đồ dữ liệu tương ứng sau
 đây.
IV. PHỤ THUỘC HÀM NỚI LỎNG
 1. Lớp IE (Implication Fomula và Equal Comparison)
 Phụ thuộc hàm nới lỏng [5] được xây dựng dưới dạng
thức chung: f : X(휆) → Y(훾); X, Y ⊆ U với các điều kiện Lớp IE là lớp các lược đồ phụ thuộc hàm kinh điển, được
nới lỏng 휆 và 훾 như sau: xây dựng trên cơ sở phép toán suy dẫn và phép sánh trị
 Quan hệ r(U) thỏa PTHNL f : X(휆) → Y(훾); X, Y ⊆ U đẳng thức.
nếu T ⊆ T Cho tập các thuộc tính U = (x1, x2,... , x푛), n>1. Giả sử
 ⊆
 Nới lỏng các phép sánh trị trên một vài thuộc tính: ngoài X,Y U. Một phụ thuộc thuộc lớp IE là biểu thức dạng
 →
sánh trị đẳng thức có thể xét các phép xấp xỉ theo độ đo, f: X Y.
hoặc các phép so sánh , ≥, =, ≠. Quan hệ r thỏa phụ Dựa trên biểu thức logic X và Y ta phân biệt các dạng
thuộc hàm nới lỏng theo phép sánh trị X (휌)→Y và được phụ thuộc hàm sau:
viết là r(X (휌)→Y) khi và chỉ khi hai bộ bất kỳ trong r sai IE-1: Biểu thức logic có dạng X → Y, ta có phụ thuộc
khác nhau không quá ngưỡng 휌 trên X thì hai bộ đó cũng hàm truyền thống: Cho LĐQH (U, F) Cho LĐQH (U, F)
sai khác nhau không quá ngưỡng 휌 trên Y. và một phụ thuộc hàm f :X→ Y trên U. Ta nói quan hệ r
 Nới lỏng theo lực lượng: thỏa phụ thuộc hàm f và ký hiệu r(f ), nếu hai bộ tùy ý
 trong r giống nhau trên X thì cũng giống nhau trên Y
 ≠ ( → 푌)
 r(X (훿)→Y) = ≤ 훿 IE-2: biểu thức logic có dạng ÔX → Y cho ta lược đồ
 ≠ 
 phụ thuộc hàm mạnh: Cho quan hệ r trên tập thuôc tính U,
 Trong đó ≠S là số phần tử có trong tập S. Biểu thức quan hệ R thỏa phụ thuộc hàm mạnh ÔX → Y trên U nếu
trên cho biết quan hệ r thỏa phụ thuộc hàm nới lỏng theo với hai bộ u, v bất kỳ trong r: u và v bằng nhau tại một
lực lượng X (훿)→Y và được viết là r(X (훿)→Y) khi và thuộc tính nào đó trên X thì u và v cũng bằng nhau trên Y.
chỉ khi tỷ lệ giữa số lượng các bộ còn lại thỏa phụ thuộc IE-3: Biểu thức logic có dạng X → ÔY, ta có lược đồ
hàm truyền thống X → Y và các bộ của quan hệ r đạt trên phụ thuộc hàm yếu: Cho quan hệ r trên tập thuôc tính U,
ngưỡng 훿. Nói cách khác, ta có thể xóa khỏi quan hệ r một quan hệ r thỏa phụ thuộc hàm yếu X → ÔY trên U nếu
số bộ với tỷ lệ tỷ lệ 훿 để quan hệ còn lại thỏa phụ thuộc với hai bộ u, v bất kỳ trong r: u và v bằng nhau trên X thì
hàm truyền thống X → Y. u và v cũng bằng nhau tại một thuộc tính nào đó trên Y.
 Định nghĩa chung về phụ thuộc hàm nới lỏng tổng quát IE-4: Biểu thức logic có dạng ÔX → ÔY , ta có lược
như sau: đồ phụ thuộc hàm đối ngẫu: Cho quan hệ r trên tập thuôc
 Cho U là tập thuộc tính, X và Y là hai tập thuộc tính tính U, quan hệ r thỏa phụ thuộc hàm đối ngẫu ÔX → ÔY
trong U. PTH nới lỏng có dạng: trên U nếu với hai bộ u, v bất kỳ trong r: u và v bằng nhau
 46
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
tại một thuộc tính nào đó trên X thì u và v cũng bằng nhau Cho tập thuộc tính X ⊆ U. Hàm sai khác ∅ trên tập
tại một thuộc tính nào đó trên Y. thuộc tính X là hội logic của các hàm sai khác trên mọi
 Ó
 Bảng dưới đây tóm lược các đặc tả cho các lớp con IE1-4 thuộc tính a ∈ X: ∅ = 훼∈ ∅훼
của lớp IE Trong [5], đã chỉ ra rằng phụ thuộc hàm sai khác là
 trường hợp riêng của phụ thuộc hàm nới lỏng, trong phần
 này chỉ ra rằng, phụ thuộc sai khác thuộc lớp LA-1.
 Dạng phụ Tên gọi Đặc điểm
 thuộc - Nếu biểu thức logic có dạng f : X(훿) → Y, 0 6 훿 6 1
 X→ Y phụ thuộc hàm ràng buộc chặt ta có phụ thuộc nới lỏng theo lực lượng.
 ÔX → Y phụ thuộc hàm nới lỏng vế trái Ví dụ, khi khảo sát các khoa của một trường đại học
 mạnh người ta đánh giá tổng thể môi trường đào tạo của khoa
 X → ÔY phụ thuộc hàm yếu nới lỏng vế phải theo ý kiến của các chuyên gia (thuộc tính A). Có 4 mức
 ÔX → phụ thuộc hàm đối nới lỏng cho A lần lượt là a, b, c và d, trong đó a là mức tốt nhất.
 ÔY ngẫu Thuộc tính B cho biết mức độ hài lòng của các sinh viên
 X(훿) → Y phụ thuộc xấp xỉ nới lỏng về trường đó. B gồm 4 mức là 1, 2, 3 và 4, trong đó 1 là
 mức cao nhất. Giả sử kết quả khảo sát được thể hiện trong
 Như vậy, các dạng phụ thuộc hàm IE-1, IE-2, IE-3, IE-4 quan hệ r(A, B). Người ta muốn biết giữa môi trường học
là các phụ thuộc hàm nới lỏng và chúng là những trường tập (A) và mức độ hài lòng (B) có đạt trên ngưỡng 0.6 hay
hợp riêng của phụ thuộc Boole dương tổng quát. không, tức là xác định f : A(0.6)→B?
 r
2. Lớp LA (Logic Fomula và Alpha Comparison) AB
 a 1
 Dựa theo điều kiện nới lỏng, ta chia lớp LA thành các b 2
lớp con sau đây: a 1
 LA-1: Lớp LA-1 là lớp các phụ thuộc được xây dựng a 2 *
trên cơ sở phép toán suy dẫn và phép sánh trị alpha. b 2
 Cho tập các thuộc tính U = (x , x ,... , x ), n>1. Giả sử
 1 2 푛 Ta thấy, sau khi xóa bộ thứ tư khỏi quan hệ r thì quan
X, Y ⊆U. Một phụ thuộc thuộc lớp LA-1 là biểu thức dạng
 hệ con còn lại, ký hiệu là r’ sẽ thỏa phụ thuộc hàm truyền
f : 훼 → 훼 với các phép sách trị 훼 như đã trình bày ở
 푌 thống A → B. Tỷ lệ thu được lúc này sẽ là
phần III.
 ≠ r0 4
 Ta nói quan hệ r thỏa LA-1: 훼 → 훼푌 và viết r(X(훼) → = = 0.8 > 0.6
Y(훼)), nếu với hai bộ bất kỳ u, v ∈ r, thỏa các ràng buộc ≠ 5
được đặc tả bởi 훼 trên tập thuộc tính X, thì u và v cũng - Phép sánh trị theo khoảng
thỏa các ràng buộc được đặc tả bởi hàm sai khác 훼푌 trên Miền trị d được phân hoạch thành k khoảng không giao
tập thuộc tính Y: nhau:
 Trong lớp LA-1, ta có các phụ thuộc đại diện sau:
 ∀ x, y ∈ d : 훼 )(x, y) = 1 khi và chỉ khi x và y thuộc
 - Nếu biểu thức logic dạng f : 훼 → 훼푌 , ta có phụ thuộc cùng một khoảng:
sai khác [6], với 훼 và 훼푌 là các hàm sai khác được định Ví dụ, điểm tổng kết của học sinh được chia thành 8
nghĩa : khoảng
 Cho quan hệ r trên tập thuộc tính U, a ∈ U và độ sai v Điểm F : [0; 3.9]
khác m . Hàm sai khác 훼 trên thuộc tính ∝ đặc tả ràng v Điểm D : [4.0; 4.7]
buộc của độ sai khác m : Với hai trị x, y ∈ d , ta định v Điểm D+ : [4.8; 5.4]
nghĩa 훼 (x, y) = 1 khi và chỉ khi m (x, y) thỏa điều kiện v Điểm C : [5.5; 6.2]
cho 훼 dưới dạng các biểu thức so sánh với các phép so v Điểm C+ : [6.3; 6.9]
sánh =, ≠, và >. v Điểm B : [7.0; 7.7]
 47
 Tập 2020, Số 1, Tháng 6
v Điểm B+ : [7.8; 8.4] [6] Song S. and Chen L. (2011), "Differential Dependen-
v Điểm A : [8.5; 10] cies: Reasoning and Discovery", ACM Trans. Datab.
Lớp LA-2: Lớp LA-2 là lớp các phụ thuộc được xây dựng Syst, vol.9, no 4, Article 39.
trên cơ sở phép toán logic Boole và phép sánh trị đẳng
thức. Đại diện cho lớp LA-2 là phụ thuộc Boole dương. SƠ LƯỢC VỀ TÁC GIẢ
[2][3] Nguyễn Xuân Huy
Lớp LA-3: Lớp LA-3 là lớp các phụ thuộc được xây dựng
 Sinh năm 1944 tại Hải Phòng.
trên cơ sở phép toán logic Boole và phép sánh trị alpha
 Cử nhân Toán, Đại học Sư phạm
(mục 4.2). Đại diện cho lớp LA-3 là phụ thuộc Boole dương
 Leningrad (Liên Xô) năm 1973.
tổng quát (phần III), đây cũng là lớp phụ thuộc bao hàm
 Tiến sỹ CNTT năm 1982, tiến
các phụ thuộc logic trong cơ sở dữ liệu đã và đang được
 sỹ khoa học CNTT năm 1990,
nghiên cứu bởi các nhóm tác giả trong và ngoài nước.
 Viện Hàn lâm Khoa học Liên
 Xô. Nguyên trưởng Phòng Cơ sở
VI. KẾT LUẬN dữ liệu và Lập trình, Viện Công
 Việc phân loại và đề xuất một mô hình chung cho các nghệ Thông tin, Viện Hàn lâm
loại phụ thuộc dữ liệu là một trong những vấn đề đang được Khoa học và Công nghệ Việt
giới nghiên cứu dữ liệu lớn quan tâm. Các điều kiện cần Nam (1997-2009). Lĩnh vực
và đủ để nhận biết các đặc trưng của một lớp phụ thuộc là nghiên cứu: Cơ sở dữ liệu và
cơ sở để phân loại và tạo ra mối liên hệ giữa các lớp phụ Công nghệ phần mềm. Email: nxhuy564@gmail.com.
thuộc.
 Bài báo mô tả mối quan hệ giữa phụ thuộc hàm nới lỏng Nguyễn Thị Vân
và phụ thuộc Boole dương tổng quát trong cơ sở dữ liệu. Sinh năm 1985 tại Hà Tĩnh.
Các kết quả chủ yếu bao gồm: Cử nhân CNTT tại Trường
 1. Xây dựng các lớp phụ thuộc trong cơ sở dữ liệu dựa Đại học Kinh doanh và Công
vào hai đặc trưng cơ bản là công thức suy dẫn và phép nghệ Hà Nội năm 2011. Thạc
sánh trị. sĩ ngành Khoa học máy tính
 2. Chỉ ra mối quan hệ giữa phụ thuộc hàm nới lỏng với tại Trường Đại học Công nghệ
phụ thuộc Boole dương tổng quát. Từ các loại phụ thuộc thông tin và Truyền thông năm
hàm nới lỏng có thể tổng quát hóa thành phụ thuộc Boole 2014. Hiện đang công tác tại
dương tổng quát và ngược lại, từ lý thuyết phụ thuộc Boole Khoa Công nghệ thông tin,
dương tổng quát có thể thực tế hóa về các phụ thuộc hàm Trường Cao đẳng Cộng đồng
nới lỏng tùy thuộc từng trường hợp biến thể của yêu cầu Hà Nội. Lĩnh vực nghiên cứu:
thực tế. Các phụ thuộc logic trong cơ
 sở dữ liệu, mô hình dữ liệu và cơ sở dữ liệu. Email:
TÀI LIỆU THAM KHẢO van.cdcd@gmail.com
[1] Nguyễn Xuân Huy (2006), "Các phụ thuộc logic trong
 cơ sở dữ liệu", NXB Thống Kê. Trương Thị Thu Hà
[2] Berman J., Blok W. J. (1988), "Positive Boolean de- Sinh năm 1979 tại Nghệ An. Cử
 pendencies" Inf. Processing Letters, 27, p.147 – 150. nhân CNTT Trường Đại học Sư
[3] Huy Nguyen Xuan, Thanh Le Thi (1992), "Generalized phạm Hà Nội năm 2000. Thạc
 Positive Boolan Dependencies", J. Inf. Process. Cybern. sĩ CNTT Trường Đại học Công
 EIK, vol. 28, p. 363 – 370. nghệ, Đại học Quốc Gia Hà
[4] Jalal Atoum (2009), "Mining Approximate Functional Nội năm 2006. Tiến sĩ CNTT,
 Dependencies from Databases", European Journal of Học viện Kỹ thuật Quân sự
 Scientific Research, ISSN 1450 – 216X vol. 33 no. 2, năm 2018. Hiện công tác tại
 p.338 – 346. Trường Đại học Kinh doanh
[5] Loredana Caruccio, Vincenzo Deufemia, Giuseppe và Công nghệ Hà Nội. Lĩnh
 Polese (2016), "Relaxed Functional Dependencies - A vực nghiên cứu: Cơ sở dữ liệu,
 Survey of Approaches", IEEE Transactions on Knowl- Công nghệ phần mềm. Email:
 edge and Data Engineering, vol. 28, p. 147–165. thuha.bh@gmail.com
 48