Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIV về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), TP. HCM, ngày 23-24/12/2021
DOI: 10.15625/vap.2021.0082

VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG
QUYẾT ĐỊNH KHƠNG ĐẦY ĐỦ
Vũ Đức Thi1, Nguyễn Long Giang2, Nguyễn Ngọc Cương3, Phạm Việt Anh4
Viện Công nghệ thông tin, Đại học Quốc gia Hà Nội
Viện Công nghệ thông tin, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
3
Cục An ninh mạng và Phịng chống tội phạm sử dụng cơng nghệ cao - Bộ Công an
4
Viện Công nghệ HaUI, Trường Đại học Cơng nghiệp Hà Nội
1

2

TĨM TẮT: Các vấn đề liên quan đến bài tốn rút gọn thuộc tính là những vấn đề quan trọng trong lý thuyết tập thô [13].
Hiện nay nhiều nhà khoa học trên thế giới quan tâm và phát triển những vấn đề này. M.Kryszkiewics [12] đã đưa ra khái niệm quan
hệ tương đối (tolerance relation) để nghiên cứu những vấn đề về các bảng quyết định không đầy đủ. Trong bài báo này, chúng tôi
giải quyết bài tốn tìm tất cả các rút gọn trong bảng quyết định không đầy đủ theo hướng tiếp cận cơ sở dữ liệu quan hệ. Chúng tơi
đề xuất thuật tốn tìm tất cả các rút gọn của bảng quyết định không đầy đủ. Thuật tốn này có độ phức tạp tồi nhất là hàm mũ. Tuy
nhiên, trong nhiều trường hợp với các dữ liệu khác nhau thì thuật tốn có độ phức tạp thời gian là đa thức.
Từ khóa: Tập rút gọn, lí thuyết tập thơ, quan hệ tương đối, bảng quyết định khơng đầy đủ.

I. MỞ ĐẦU
Rút gọn thuộc tính trong bảng quyết định là quá trình loại bỏ các thuộc tính dư thừa trong tập thuộc tính điều
kiện mà không ảnh hưởng đến việc phân lớp các đối tượng. Dựa vào tập rút gọn thu được, việc sinh luật và phân lớp
đạt hiệu quả cao nhất. Cho đến nay, có rất nhiều cơng trình nghiên cứu về các thuật tốn rút gọn thuộc tính trong lý
thuyết tập thơ. Tuy nhiên, các thuật tốn này đều tìm được một tập rút gọn tốt nhất theo một tiêu chí đánh giá nào đó
với độ phức tạp đa thức (các thuật tốn theo hướng tiếp cận heuristic) mà chưa giải quyết bài tốn tìm tất cả các tập rút
gọn trong bảng quyết định không đầy đủ. Trong [7], các tác giả đã đưa ra một phương pháp tính các thuộc tính rút gọn

(thuộc tính tham gia ít nhât một rút gọn) trong bảng quyết định không đầy đủ. Đối với bảng rút gọn nhất quán đầy đủ,
với cách tiếp cận bằng mô hình dữ liệu quan hệ [15, 16], chúng tơi [10] đã đề xuất một thuật tốn có thời gian tính đa
thức tìm tất cả các thuộc tính rút gọn. Với thuật tốn này chúng ta có thể rút gọn các cột (các thuộc tính) trong bảng
quyết định. Trong [9], chúng tơi đã đề xuất một thuật tốn đa thức rút gọn các dòng (các đối tượng) trong bảng quyết
định. Như vậy, với hai thuật toán hiệu quả này chúng ta có thể loại bỏ các các cột, các dịng dư thừa trên bảng quyết
định. Mặt khác, việc tìm tất cả các rút gọn trong bảng quyết định đầy đủ rất quan trọng. Trong [8], các tác giả đã đưa ra
phương pháp tìm tất cả các rút gọn trong một bảng quyết định nhất quá và đầy đủ. Các tác giả đã chứng minh bài tốn
tìm tất cả các rút gọn trên bảng quyết định này có độ phức tạp hàm mũ theo số lượng thuộc tính. Có nghĩa là phải
chứng minh được: Tồn tại một thuật tốn hàm mũ tìm tất cả các rút gọn này và chứng minh độ phức tạp của bài tốn
này khơng nhỏ hơn hàm mũ.
Dù rằng, trên một bảng quyết định nhất quán đầy đủ việc tìm một rút gọn được thực hiện bằng một thuật tốn đa
thức, nhưng việc tìm một rút gọn có lực lượng nhỏ nhất là khơng khả thi. Có nghĩa rằng cho đến nay, khơng tồn tại một
thuật tốn đa thức thực hiện cơng việc này. Trong [11], vì tập các rút gọn trên một bảng quyết định nhất quán đầy đủ là
quan trọng, chúng tôi đã chứng minh tập các rút gọn này tương đương với hệ Sperner ( hệ này là một hệ tổ hợp trong
đó các phần tử của nó khơng chứa nhau). Có nghĩa rằng việc nghiên cứu về tập các rút gọn có thể đưa về việc nghiên
cứu hệ Sperner.
II. CÁC KHÁI NIỆM CƠ BẢN
Các khái niệm cơ bản trong lý thuyết tập thô
Trong phần này sẽ trình bày một số khái niệm cơ bản trong lý thuyết tập thô [9]. Bảng quyết định là một bộ tứ
𝐷𝑇 = (𝑈, 𝐶 ∪ 𝐷, 𝑉, 𝑓) trong đó 𝑈 = {𝑢1 , 𝑢2 , . . . , 𝑢𝑛 } là tập khác rỗng, hữu hạn các đối tượng; 𝐶 = {𝑐1 , 𝑐2 , . . . , 𝑐𝑚 } là tập
các thuộc tính điều kiện; 𝐷là tập các thuộc tính với C và D là hai tập rời nhau và 𝑉 = UVa , với Va là tập giá trị của
thuộc tính 𝑎 ∈ 𝐴 = 𝐶 𝑈 𝐷; 𝑓: 𝑈 × (𝐶 ∪ 𝐷) → 𝑉 là hàm thông tin, với ∀𝑎 ∈ 𝐶 ∪ 𝐷, 𝑢 ∈ 𝑈 hàm 𝑓 cho giá trị 𝑓(𝑢, 𝑎) ∈
𝑉𝑎 . Khơng mất tính chất tổng quát giả thiết 𝐷 chỉ gổm một thuộc tính quyết định 𝑑 duy nhất (trường hợp 𝐷 có nhiều
thuộc tính thì bằng một phép mã hóa có thể quy về một thuộc tính [8]). Do đó, từ nay về sau ta xét bảng quyết định
𝐷𝑇 = (𝑈, 𝐶 ∪ 𝑑, 𝑉, 𝑓), trong đó {𝑑} ∉ 𝐶.
Mỗi tập con 𝑃 ⊆ 𝐶 𝑈{𝑑} xác định một quan hệ không phân biệt được, gọi là quan hệ tương đương.
𝐼𝑁𝐷(𝑃) = {(𝑥, 𝑦) ∈ 𝑈 × 𝑈|∀𝑎 ∈ 𝑃, 𝑓(𝑥, 𝑎) = 𝑓(𝑦, 𝑎)}.


VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ


400

𝐼𝑁𝐷(𝑃) xác định một phân hoạch của 𝑈, ký hiệu là 𝑈/𝑃 = {𝑃1 , 𝑃2 , . . . , 𝑃𝑚 }. Một phần tử trong 𝑈/𝑃 gọi là một
lớp tương đương.

Với 𝐵 ⊆ 𝐶 và 𝑋 ⊆ 𝑈, 𝐵 − xấp xỉ trên của 𝑋 là tập 𝐵𝑋 = {𝑢 ∈ 𝑈|[𝑢]𝐵 ∩ 𝑋 ≠ ∅}, 𝐵 − xấp xỉ dưới của 𝑋 là tập
𝐵𝑋 = {𝑢 ∈ 𝑈|[𝑢]𝐵 ⊆ 𝑋}, 𝐵 − miền biên của 𝑋 là tập 𝐵𝑋\𝐵𝑋 và 𝐵 − miền dương của {𝑑} là tập 𝑃𝑂𝑆𝐵 ({𝑑}) =
∪𝑋∈𝑈/𝐷(𝐵𝑋). Bảng quyết định 𝐷𝑇 được gọi là nhất quán khi và chỉ khi 𝑃𝑂𝑆𝐶 ({𝑑}) = 𝑈, hay phụ thuộc hàm 𝐶 → 𝑑
đúng, ngược lại 𝐷𝑇 là không nhất quán. Trường hợp 𝐷𝑇 khơng nhất qn thì 𝑃𝑂𝑆𝐶 ({𝑑}) chính là tập con cực đại của
𝑈 sao cho phụ thuộc hàm 𝐶 → 𝑑 đúng.
Định nghĩa 2.1: Cho bảng quyết định 𝐷𝑇 = (𝑈, 𝐶 ∪ 𝑑, 𝑉, 𝑓). Nếu 𝐵 ⊆ 𝐶 thỏa mãn:
(1) 𝑃𝑂𝑆𝐵 ({𝑑}) = 𝑃𝑂𝑆𝐶 ({𝑑})

(2) ∀𝐵′ ⊂ 𝐵(𝑃𝑂𝑆𝐵′ ({𝑑}) ≠ 𝑃𝑂𝑆𝐶 ({𝑑}))

thì 𝐵 được gọi là một tập rút gọn của 𝐶

Trường hợp 𝐷𝑇 nhất quán, định nghĩa trên cho thấy 𝐵 là một tập rút gọn nếu 𝐵 thỏa mãn 𝐵 → 𝑑 và ∀𝐵′ ⊂ 𝐵, 𝐵′ ↛
{𝑑}, ký hiệu 𝑅𝑑 là tập tất cả các rút gọn của 𝐷𝑇.
Định nghĩa 2.2: Quan hệ r = {ℎ1 , … , ℎ𝑚 } là quan hệ trên R={a1,...,an}. Nếu ∀𝑎𝑖 ∈ 𝑅 có 𝒟𝑎𝑖 và ∗ ∈ 𝒟𝑎𝑖
ℎ𝑗 : R→ ∪ 𝒟𝑎𝑖 sao cho ℎ𝑗 (𝑎𝑖 ) ∈ 𝒟𝑎𝑖

Định nghĩa 2.3: Cho r là quan hệ trên R={a1,...,an}, A ⊆ R

Khi đó ta kí hiệu ℎ𝑖 ~ ℎ𝑗 (𝐴) nếu với mỗi a thuộc A : ℎ𝑖 (𝑎) = ℎ𝑗 (𝑎) hoặc ℎ𝑖 (𝑎) = ∗ hoặc ℎ𝑗 (𝑎) = ∗ .

Định nghĩa 2.4: Cho 𝑟 = { ℎ1 , … , ℎ𝑚 } trên R={a1,...,an}. Khi đó 𝐴, 𝐵 ⊆ 𝑅 và ta gọi 𝐴 xác định tương đối 𝐵 kí hiệu
𝑡


𝐴 → 𝐵 nếu:

𝑡

(∀ ℎ𝑖 , ℎ𝑗 ∈ 𝑟) (nếu ℎ𝑖 ~ℎ𝑗 (𝐴) thì ℎ𝑖 ~ℎ𝑗 (𝐵))

Đặt 𝑇𝑟 = { (𝐴, 𝐵): 𝐴, 𝐵 ⊆ 𝑅 𝑣à 𝐴 → 𝐵}
Dễ thấy: 1) (𝐴, 𝐴) ∈ 𝑇𝑟 ∀𝐴 ⊆ 𝑅

2) (𝐴, 𝐵) ∈ 𝑇𝑟 thì 𝐴 ⊆ 𝐶, 𝐷 ⊆ 𝐵 có (𝐶, 𝐷) ∈ 𝑇𝑟

3) (𝐴, 𝐵) ∈ 𝑇𝑟 , (𝐵, 𝐶) ∈ 𝑇𝑟 ⟹ (𝐴, 𝐶) ∈ 𝑇𝑟
𝑡

Đặt 𝐴+ = {𝑎 ∈ 𝑅: 𝐴 → {𝑎}}

Định nghĩa 2.5: Bảng quyết định không đầy đủ 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 với ∗∉ 𝒟 α (có nghĩa cột giá trị của thuộc tính
quyết định 𝑑 khơng chứa ∗). 𝐶 là tập các thuộc tính điều kiện. 𝐷𝑆 là bảng quyết định khơng đầy đủ là nhất qn nếu
𝑡

𝐶 → {𝑑}

Có thể thấy nếu DS khơng nhất qn ta có thể kiểm tra bằng một thuật toán thời gian đa thức các phần tử của U
để loại bỏ các phần tử không làm cho DS là nhất quán. Sau khi loại bỏ chúng ta có tập U’ thì DS = < U’, C U d, V, f>
là nhất quán.
Định nghĩa 2.6: 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ nhất quán, 𝐵 là tập rút gọn 𝐷𝑆 nếu:
𝑡

𝑡


𝐵 ⊆ 𝐶: 𝐵 → {𝑑} và ∀𝐵’ ⊊ 𝐵 thì 𝐵’ ↛ {𝑑} (có nghĩa B’ là tập con thực sự của B thì B’ khơng xác định tương
đối với d)

Đặt PRED(C) = {𝐵 là các tập rút gọn của 𝐷𝑆}

Định nghĩa 2.7: Giả sử 𝑅 = {𝑎1 , … , 𝑎𝑛 } và 𝒦 = {𝐴1 , … , 𝐴𝑚 } là hệ Sperner trên R nếu:
𝐴𝑖 ⊈ 𝐴𝑗 ∀ 𝑖, 𝑗

Định nghĩa 2.8: 𝒦 = {𝐴1 , … , 𝐴𝑚 } là hệ Sperner trên R.

Đặt 𝒦 −1 = {𝐵 ⊊ 𝑅: (𝐴 ∈ 𝒦 ⟹ 𝐴 ⊈ 𝐵 và 𝐵 ⊊ 𝐶 thì ∃𝐴 ∈ 𝒦: 𝐴 ⊆ 𝐶}

Nhận xét 2.1: Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑚 },
𝑅 = 𝐶 ∪ 𝑑.


Vũ Đức Thi, Nguyễn Long Giang, Nguyễn Ngọc Cương, Phạm Việt Anh
𝑡

401
𝑡

Có thể thấy 𝑃𝑅𝐸𝐷(𝐶) = 𝒦𝑑𝑡 = {𝐴 ⊆ 𝐶: 𝐴 → {𝑑} và ∄𝐵: 𝐵 → {𝑑} 𝑣à 𝐵 ⊊ 𝐴 }

và 𝑃𝑅𝐸𝐷(𝐶) là hệ Sperner.

Nhận xét 2.2: Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑛 }, 𝑅 =
𝐶 ∪ 𝑑.
1.


2.

Từ r ta tính tập bằng nhau:
𝜀𝑟 = { 𝐸𝑖𝑗 ∶ 1 ≤ i ≤ j ≤ 𝑚 } với 𝐸𝑖𝑗 = { 𝑎 ∈ 𝑅: a(𝑢𝑖 ) = 𝑎(𝑢𝑗 ) hoặc 𝑎(𝑢𝑖 ) = ∗ hoặc 𝑎(𝑢𝑗 ) = ∗}
Từ 𝜀𝑅 đặt 𝑀𝑑 = {𝐴 ∈ 𝜀𝑟 : 𝐴 ≠ 𝑅, 𝑑 ∉ 𝐴 và ∄𝐵 ∈ 𝜀𝑟 : 𝑑 ∉ 𝐵 và 𝐴 ⊊ 𝐵}
III. MỘT SỐ THUẬT TOÁN CƠ BẢN TRONG CƠ SỞ DŨ LIỆU QUAN HỆ

A. Thuật tốn tìm tập phản khố
Thuật tốn 3.1. [14] Tìm tập phản khố 𝐾 −1

Đầu vào: 𝐾 = {𝐵1 , … , 𝐵𝑛 } là hệ Sperner trên 𝑅.

Đầu ra: 𝐾 −1

Bước 1: Đặt 𝐾1 = {𝑅 − {𝑎}: 𝑎 ∈ 𝐵1 }. Hiển nhiên 𝐾1 = {𝐵1 }−1

Bước q+1: (𝑞 < 𝑚). Giả thiết rằng 𝐾𝑞 = 𝐹𝑞 ∪ �𝑋1 , … , 𝑋𝑡𝑞 �, ở đây 𝑋1 , … , 𝑋𝑡𝑞 chứa 𝐵𝑞+1 và 𝐹𝑞 =
�𝐴 ∈ 𝐾𝑞 : 𝐵𝑞+1 ⊄ 𝐴�. Đới với mỗi 𝑖(𝑖 = 1, … , 𝑡𝑞 ) ta tìm các phản khoá của 𝐵𝑞+1 trên 𝑋𝑖 tương tự như 𝐾1 . Ký pháp của
chúng là 𝐴1𝑖 , … , 𝐴𝑖𝑟𝑖 . Đặt:
𝐾𝑞+1 = 𝐹𝑞 ∪ �𝐴𝑖𝑝 : 𝐴 ∈ 𝐹𝑞 ⇒ 𝐴𝑖𝑝 ⊄ 𝐴, 1 ≤ 𝑖 ≤ 𝑡𝑞 , 1 ≤ 𝑝 ≤ 𝑟𝑖 �
Cuối cùng ta đặt 𝐾 −1 = 𝐾𝑚

Độ phức tạp thuật toán

Đặt 𝐼𝑞 (1 ≤ 𝑞 ≤ 𝑚 − 1) là số phẩn tử của 𝐾𝑞 trong thuật toán trên. Theo [14], độ phức tạp thời gian của thuật
𝑚−1
𝑡𝑞 𝑢𝑞 � với 𝑢𝑞 = 𝐼𝑞 − 𝑡𝑞 nếu 𝐼𝑞 > 𝑡𝑞 và 𝑢𝑞 = 1 nếu 𝐼𝑞 = 𝑡𝑞 .
toán là 𝑂�|𝑅|2 ∑𝑞=1
Nhận xét


1) Trong mỗi bước của thuật toán, 𝐾𝑞 là hệ số Sperner trên 𝑅. Theo [5], kích thước của hệ Sperner bất kỳ trên
[𝑛/2]

𝑅 không vượt quá 𝐶𝑛
theo 𝑛.

≈ 2𝑛+1/2 /�∏. 𝑛1/2 � với 𝑛 = |𝑅|. Do đó, độ phức tạp tồi nhất của thuật toán là hàm số mũ

2) Trường hợp 𝐼𝑞 ≤ 𝐼𝑚 (𝑞 = 1, … , 𝑚 − 1), độ phức tạp của thuật tốn khơng lớn hơn 𝑂(|𝑅|2 |𝐾||𝐾 −1 |2 ), khi
đó độ phức tạp thuật toán là đa thức theo |𝑅|, |𝐾| và |𝐾 −1 |. Nếu số lượng các phấn tử của 𝐾 là nhỏ thì thuật tốn rất
hiệu quả, địi hỏi thời gian đa thức theo |𝑅|.
B. Thuật tốn tìm tập khố tối thiểu từ tập các phản khoá

Thuật toán 3.2. [5] Tìm một khố tối thiểu từ tập các phản khố
Đầu vào: Cho 𝐾 là hệ Sperner đóng vai trị là tập phản khoá, 𝐶 = {𝑏1 , … , 𝑏𝑛 } ⊆ 𝑅 và 𝐻 là hệ Sperner đóng
vai trị tập khoá (𝐾 = 𝐻 −1 ) sao cho ∃𝐵 ∈ 𝐾: 𝐵 ⊊ 𝐶.
Đầu ra: 𝐷 ∈ 𝐻

Bước 1: Đặt 𝑇(0) = 𝐶;

Bước i+1: Đặt 𝑇(𝑖 + 1) = 𝑇(𝑖) − 𝑏𝑖+1 nếu ∀𝐵 ∈ 𝐾 khơng có 𝑇(𝑖 + 1) ⊂ 𝐵; trong trường hợp ngược lại đặt
𝑇(𝑖 + 1) = 𝑇(𝑖);
Cuối cùng ta đặt 𝐷 = 𝑇(𝑛).

Có thể thấy độ phức tạp thời gian tồi nhất của thuật toán trên là đa thức với n và / K/.
Thuật tốn 3.3. [5] Tìm tập các khố tối thiểu từ tập các phản khoá
Đầu vào: Cho 𝐾 = {𝐵1 , … , 𝐵𝑘 } là hệ Sperner trên 𝑅.
Đầu ra: 𝐻 mà 𝐻 −1 = 𝐾.



VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHƠNG ĐẦY ĐỦ

402

𝐴𝑖+1

Bước 1: Bởi thuật tốn 3.2 ta tính 𝐴1 , đặt 𝐾1 = 𝐴1 .

Bước i+1: Nếu có 𝐵 ∈ 𝐾𝑖 −1 sao cho 𝐵 ⊄ 𝐵𝑗 (∀𝑗: 1 ≤ 𝑗 ≤ 𝑘) thì bởi Thuật tốn 3.2 ta tính 𝐴𝑖+1 , ở đây
∈ 𝐻, 𝐴𝑖+1 ⊆ 𝐵. Đặt 𝐾𝑖+1 = 𝐾𝑖 ∪ 𝐴𝑖+1 . Trong trường hợp ngược lại ta đặt 𝐻 = 𝐾𝑖 .
Độ phức tạp thuật toán 3.3

𝑚−1
Theo [5], độ phức tạp Thuật toán 3.3 là 𝑂 �|𝑅|�∑𝑞=1
�|𝐾|𝐼𝑞 + |𝑅|𝑡𝑞 𝑢𝑞 � + |𝐾|2 + |𝑅|��

với 𝐼𝑞 , 𝑡𝑞, , 𝑢𝑞 như trong Thuật tốn 3.1. Do đó, độ phức tạp tồi nhất của Thuật toán 3.3 là hàm số mũ theo 𝑛 với 𝑛 là số
phần tử của 𝑅. Trường hợp 𝐼𝑞 ≤ |𝐾|(𝑞 = 1, … , 𝑚 − 1), độ phức tạp của Thuật toán 3.3 là 𝑂(|𝑅|2 |𝐾|2 |𝐻|), độ phức tạp
của đa thức theo |𝑅|, |𝐾| và |𝐻|. Nếu |𝐻| là đa thức theo |𝑅|, |𝐾| thì thuật toán hiệu quả. Nếu số lượng các phần tử của
𝐻 là nhỏ thì thuật tốn rất hiệu quả.
IV. THUẬT TỐN TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH

Định lí 4.1:
Chứng minh:

𝑀𝑑 = (𝒦𝑑𝑡 )−1

∀𝐴 ∈ 𝑀𝑑 có thể thấy 𝐴 = 𝐴+ vì nếu 𝐴 ⊊ 𝐴+ thì có 𝑒 ∈ 𝐴+ và 𝑒 ∉ 𝐴. Vì 𝐴 là tập bằng nhau cực đại thì
𝑡


∃𝑖, 𝑗 (1 ≤ 𝑖 < 𝑗 ≤ 𝑚) để 𝐸𝑖𝑗 = 𝐴 và theo định nghĩa tập 𝐴+ , ta có 𝐴 → {𝑒} và phù hợp với định nghĩa tập 𝐸𝑖𝑗 thì
𝑡

𝑒 ∈ 𝐸𝑖𝑗 . Vì thế 𝐴 = 𝐴+ và 𝑑 ∉ 𝐴 nên 𝑑 ∉ 𝐴+ . Vậy 𝐴 ↛ {𝑑} (𝐴 khơng xác định tương đối 𝑒).

Nếu có 𝐵 mà 𝐴 ⊊ 𝐵, theo định nghĩa của tập 𝐴 nếu 𝑑 ∉ 𝐵 thì ∀𝑖, 𝑗 (1 ≤ 𝑖 < 𝑗 ≤ 𝑚) ta có ℎ𝑖 ~ℎ𝑗 (𝐵) khơng
𝑡

đúng. Do đó, theo định nghĩa của xác định tương đối, ta có 𝐵 → 𝑅. Trường hợp 𝑑 ∈ 𝐵 thì dễ thấy 𝑑 ∈ 𝐵+ . Như vậy, cả
𝑡

hai trường hợp ta có ∀𝐵: 𝐴 ⊊ 𝐵 ⇒𝐵+ → {𝑑}. Vậy theo định nghĩa của 𝒦𝑑𝑡 thì có 𝐶 ∈ 𝒦𝑑𝑡 để 𝐶 ⊆ 𝐵. Như vậy theo định
nghĩa của tập (𝒦𝑑𝑡 )−1 ta có 𝐴 ∈ (𝒦𝑑𝑡 )−1 . Ngược lại nếu 𝐴 ∈ (𝒦𝑑𝑡 )−1 thì 𝐴+ = 𝐴. Vì ngược lại nếu 𝐴 ⊊ 𝐴+ thì theo
𝑡

𝑡

định nghĩa của tập phản khóa ta có 𝐶 ∈ (𝒦𝑑𝑡 ) để 𝐶 ⊆ 𝐴+ , có nghĩa là 𝐴+ → {𝑑}, như vậy kéo theo 𝐴 → {𝑑}. Mà theo
𝑡

định nghĩa của (𝒦𝑑𝑡 )−1 thì 𝐴 khơng xác định tương đối {𝑑} (𝐴 ↛ {𝑑}). Như vậy 𝐴+ = 𝐴.

Theo định nghĩa của tập 𝑀𝑑 và tập (𝒦𝑑𝑡 )−1 (là tập hợp các tập lớn nhất không xác định 𝑑) có nghĩa là 𝐴 ∈ 𝑀𝑑 .
Vậy 𝑀𝑑 = (𝒦𝑑𝑡 )−1 .

Thuật tốn 4.1: Thuật tốn tìm tất cả các tập rút gọn trên bảng quyết định không đầy đủ

Giả sử 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định nhất quán không đầy đủ. Đặt 𝑟 = 𝑈 = {𝑢1 , … , 𝑢𝑛 }, 𝑅 = 𝐶 ∪ 𝑑.
1) Từ 𝑟 ta tính tập bằng nhau:
𝜀𝑟 = { 𝐸𝑖𝑗 ∶ 1 ≤ i ≤ j ≤ 𝑚 } với 𝐸𝑖𝑗 = { 𝑎 ∈ 𝑅: a(𝑢𝑖 ) = 𝑎(𝑢𝑗 ) hoặc 𝑎(𝑢𝑖 ) = ∗ hoặc 𝑎(𝑢𝑗 ) = ∗}

2) Từ 𝜀𝑅 đặt 𝑀𝑑 = {𝐴 ∈ 𝜀𝑟 : 𝐴 ≠ 𝑅, 𝑑 ∉ 𝐴 và ∄𝐵 ∈ 𝜀𝑟 : 𝑑 ∉ 𝐵 và 𝐴 ⊊ 𝐵}
3) Bởi Thuật toán 3.3 ta xây tập K từ Md ( K-1 = Md )

4) Đặt PRED (C) = K – {d}
Ví dụ 4.1: Giả sử 𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉, 𝑈 = {𝑢1 , 𝑢2 , . . . , 𝑢5 }, 𝐶 = {𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 }

Bảng 1. Một ví dụ bảng quyết định khơng đầy đủ

𝑢1
𝑢2
𝑢3
𝑢4
𝑢5

1
2
2
3
3

𝑎1

1
∗
2
1
1

𝑎2


∗
5
4
4
4

𝑎3

∗
2
1
1
*

𝑎4

d
6
7
6
7
7

Theo bước 1 và 2 của Thuật toán 4.1, cần thực hiện các bước sau:
1) Tính:
+ 𝐸12 = {𝑎2 , 𝑎3 , 𝑎4 }

+ 𝐸13 = {𝑎3 , 𝑎4 , 𝑑}

+ 𝐸23 = {𝑎1 , 𝑎2 } + 𝐸24 = {𝑎2 , 𝑑}


+ 𝐸14 = {𝑎2 , 𝑎3 , 𝑎4 }

+ E25 = {a2, a4, d}

+ 𝐸34 = {𝑎3 , 𝑎4 }

+ 𝐸15 = {𝑎2 , 𝑎3 , 𝑎4 }


Vũ Đức Thi, Nguyễn Long Giang, Nguyễn Ngọc Cương, Phạm Việt Anh

403

+𝐸35 = {𝑎3 , 𝑎4 } + 𝐸45 = {𝑎1 , 𝑎2 , 𝑎3 , 𝑎4 , 𝑑}

2) Theo bước 2 Thuật tốn 4.1 có 𝐴1 = {𝑎2 , 𝑎3 , 𝑎4 } và 𝐴2 = {𝑎1 , 𝑎2 } thỏa mãn điều kiện của Md.
Như vậy

𝑀𝑑 = {{𝑎2 , 𝑎3 , 𝑎4 }, {𝑎1 , 𝑎2 }}

Có thể thấy, trên cơ sở Thuật toán 3.3 từ Md chúng ta có:
PRED (C) = {{𝑎1 , 𝑎3 }, {𝑎1 , 𝑎4 }}

Độ phức tạp của thuật tốn:

Dễ thấy, đơ phức tạp thuật toán của Bước 1 và Bước 2 là đa thức theo kích thước của 𝑟. Do đó, độ phức tạp
của thuật toán là độ phức tạp của Thuật tốn 3.3 tính tập khố tối thiểu từ tập phản khố tại Bước 3. Do đó độ phức tạp
của thuật toán là:
𝑚−1


𝑂 �|𝑅| � � �|𝑀𝑑 |𝐼𝑞 + |𝑅|𝐼𝑞 𝑢𝑞 � + |𝑀𝑑 |2 + |𝑅|��
𝑞=1

với 𝐼𝑞 , 𝑡𝑞, , 𝑢𝑞 như trong Thuật toán 3.1 và độ phức tạp thuật toán này trong trường hợp xấu nhất là hàm số mũ theo 𝑛
với 𝑛 là số phần tử của 𝑅. Trường hợp 𝐼𝑞 ≤ |𝑀𝑑 |(𝑞 = 1, … , 𝑚 − 1), độ phức tạp của thuật toán là 𝑂(|𝑅|2 |𝑀𝑑 |2 |𝐾𝑑𝑡 |),
độ phức tạp này là đa thức theo |𝑅|, |𝑀𝑑 | và |𝐾𝑑𝑡 |. Dễ thấy tại bước 2, |𝑀𝑑 | là đa thức theo kích thước của 𝑟, do đó nếu
|𝐾𝑑𝑡 | là đa thức theo |𝑅| thì độ phức tạp của thuật tốn là đa thức theo kích thước của 𝑟. Nếu số lượng các phần tử của
|𝐾𝑑𝑡 | là nhỏ thì thuật toán rất hiệu quả.

Cho DS = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định không đầy đủ. Thuộc tính a của C được gọi là cốt lõi DS nếu a
tham gia trong tất các rút gọn của DS. Kí pháp CORE (DS) là tập tất cả các thuộc tính cốt lõi của DS. Có thể thấy rằng
CORE (DS) là tập giao của các tập rút gọn A của DS.
Từ Thuật tốn 4.1 chúng ta có hệ quả sau:
Hệ quả 4.1: Cho 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định khơng đầy đủ thì tồn tại thuật tốn tìm CORE (DS).

Chúng ta có thể thấy rằng trên cơ sở Thuật tốn 3.2 và Định lí 4.1 chúng ta có hệ quả sau:

Hệ quả 4.2: Cho 𝐷𝑆 = 〈𝑈, 𝐶 ∪ 𝑑, 𝑣, 𝑓〉 là bảng quyết định khơng đầy đủ thì tồn tại thuật tốn tìm một rút gọn
của DS. Thuật tốn này có độ phức tạp thời gian là đa thức.
TÀI LIỆU THAM KHẢO

[1] J. Demetrovics, On the equivalence of candidate keys with Sperner systems, Acts Cybernetica 4, 247-252, 1979.
[2] J. Demetrovics, V. D. Thi, Algorithms for generating Armstrong relation and inferring functional dependencies in the relational
datamodel, Computer and Mathematics with Applications 26 (4) 43-55 (Great Britain).
[3] J. Demetrovics, V. D. Thi, antikeys and prime attributes, Ann. Univ. Scien. Budapest Sect. Comut. 8: 37-54, 1987.
[4] J. Demetrovics, V. D. Thi, Relations and minimal keys, Acta Cybernetica 8 (3): 297-285, 1998.
[5] J. Demetrovics, V. D. Thi, Some remarks on generating, Armstrong and inferring functional dependencies relation, Acta
Cybernetica 12: 167-180, 1995.
[6] J. Demetrovics, V. D. Thi, Some result about functional dependencies, Acta Cybernetica 8 (3): 273- 280, 1988.

[7] J. Demetrovics, N. L. Giang, V. D. Thi, An efficient algorithm for determining the set of all reductive attributes in incomplete
decision tables. Journal CIT, Bungary, 13 (4): 118-126, 2013.
[8] J. Demetrovics, N. L. Giang, V. D.Thi, “On finding all reducts of consistent decision tables”. Journal CIT, Bungary, 14 (4): 310, 2014.
[9] J. Demetrovics, V. D.Thi, H. M. Quang, N. V. Anh, “A method to reduce the size of consistent decision tables”, Acta
Cybernetica, V. 23: 167-180, 2018.
[10] N. L. Giang, V. D. Thi, “Some problems concerning condition attributes and reducts in decision tables”. Proceeding of the 5th
National Symposium Fundamential and Applied Information Technology Research (FAIR), 142-152, 2011.
[11] N. L. Giang, J. Demetrovics, V. D. Thi, P. D. Khoa, “Some Properties Related to Reduct of Consistent Decision Systems”,
Journal of Cybernetics and Information Technologies, Bulgarian Academy of Sciences, V. 21(2): 3-9, 2021.
[12] M. Kryszkiewicz, Rough set approach to incomplete information systems, Information Science, 39-40, 1998.
[13] Z. Pawlak, Rough Sets - Theoritical Aspets of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
[14] V. D. Thi, Minimal keys and antikeys, Acta Cybernetica 7 (4): 361-371, 1986.
[15] V. D.Thi, N. L. Giang, “A method for extracting knowledge from decision tables in terms of functional dependencies”. Journal
CIT, Bungary, 13, 1, 73-82, 2013.
[16] V. D. Thi, N. L. Giang, “A method to construct decision table from relation scheme”, Cybernetics and Information
Technologies, Bulgarian Academy of Sciences, V.11 (3): 32-41, 2011.


404

VỀ VẤN ĐỀ TÌM TẤT CẢ CÁC RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ

ON THE PROBLEM FINDING ALL REDUCTS IN INCOMPLETE DECISION TABLE
Vu Duc Thi, Nguyen Long Giang, Nguyen Ngoc Cuong, Pham Viet Anh

ABSTRACT: Problems related to the attribute reduction are important in rough set theory [13]. Nowadays, scientists in the
world consider and develop these problems. M.Kryszkiewics [12] provided the tolerance relation to conduct research on issues
relating to incomplete decision tables. In this paper, we find all reducts in incomplete decision tables according to the relational
database approach. We propose the algorithm to find all reducts of incomplete decision tables. This algorithm has the time
complexity which is exponential. However, this algorithm has the time complexity which is polynomial in different cases of the

database.