Một số vấn đề tính toán liên quan đến cơ sở dữ liệu và khai phá dữ liệu

 phụ thuộc hàm { }C d→ đúng và B là một tập rút gọn của C nếu B là tập tối thiểu 
thỏa mãn phụ thuộc hàm { }B d→ . Trong cơ sở dữ liệu quan hệ, với quan hệ r trên tập thuộc 
tính R thì B là một tập tối thiểu của thuộc tính ,d R d B∈ ∉ nếu B là tập tối thiểu thỏa mãn phụ 
thuộc hàm { }B d→ [17]. Do đó, khái niệm tập rút gọn của bảng quyết định tương đương với 
khái niệm tập tối thiểu của thuộc tính{ }d trên quan hệ. 
Với các bảng quyết định nhất quán, chúng tôi trình bày một số thuật toán liên quan đến tập rút 
gọn sử dụng một số thuật toán và một số kết quả liên quan đến tập tối thiểu của một thuộc tính trong 
cơ sở dữ liệu quan hệ. 
Bảng quyết định trong các bài toán thực tế thường chứa một số thuộc tính dư thừa thực sự, 
là những thuộc tính mà việc loại bỏ chúng không ảnh hưởng gì đến việc phân lớp tập đối tượng. 
Sự có mặt của các thuộc tính này làm cho độ phức tạp tính toán của bài toán khai phá dữ liệu 
tăng lên rất lớn. Việc loại bỏ các thuộc tính này trước khi thực hiện các nhiệm vụ khai phá dữ 
liệu có ý nghĩa thực tiễn cao trong bối cảnh dữ liệu ngày càng lớn, ngày càng đa dạng và phức 
tạp. 
Như đã trình bày, trong bảng quyết định thuộc tính dư thừa thực sự là thuộc tính không 
xuất hiện trong bất kì tập rút gọn nào và thuộc tính rút gọn là thuộc tính xuất hiện trong một tập 
rút gọn nào đó. Khi đó, bài toán tìm tập tất cả thuộc tính dư thừa thực sự tương đương với bài 
toán tìm tập tất cả các thuộc tính rút gọn. Để giải quyết bài toán này, phương pháp tiếp cận 
thông thường là tìm họ tất cả các tập rút gọn của bảng quyết định, sau đó tìm phép hợp giữa các 
tập rút gọn. Tuy nhiên, cách tiếp cận này không khả thi với các bảng dữ liệu kích thước lớn vì 
độ phức tạp thời gian của thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định là hàm mũ 
đối với số thuộc tính điều kiện. 
Trong phần này, chúng tôi đề xuất một thuật toán tìm tập tất cả các thuộc tính rút gọn của 
bảng quyết định nhất quán có độ phức tạp thời gian là đa thức. 
Trong cơ sở dữ liệu quan hệ, chúng tôi [16] đã chứng minh bổ đề quan trọng sau. 
Bổ đề 1. [16] Giả sử K là một hệ Sperner trên R, khi đó 
1K K
K R K
−∈ ∈
= −U I
K K
. 
Trên quan hệ r, do r
aK là hệ Sperner trên R nên áp dụng Bổ đề 1 ta có bổ đề sau 
Bổ đề 2. Cho r là một quan hệ trên R và a R∈ , khi đó 
( ) 1r ra aK K
K R K
−∈ ∈
= −U I
K K
Cho bảng quyết định nhất quán { }( ), , ,DS U C d V f= ∪ với { }1 2, ,..., mU u u u= . Xét 
quan hệ { }1 2, ,..., mr u u u= trên tập thuộc tính { }R C d= ∪ , từ khái niệm tập rút gọn của bảng 
quyết định nhất quán và tập tối thiểu của một thuộc tính trên quan hệ ta có 
Một số vấn đề tính toán liên quan đến cơ sở dữ liệu và khai phá dữ liệu 
699
( ) { }rdPRED C d= −K , với ( )PRED C là họ tất cả các tập rút gọn Pawlak của C trong DS và 
r
dK là họ các tập tối thiểu của thuộc tính d trên r. Do đó, nếu kí hiệu ( )REAT C là tập tất cả các 
thuộc tính rút gọn của C thì 
( )
( )
{ }
r
dR PRED C R
REAT C R R d
∈ ∈
 
= = −  
 
U U
K
Thuật toán 1. Tìm tập tất cả các thuộc tính rút gọn. 
Đầu vào: Bảng quyết định { }( ), , ,DS U C d V f= ∪ với { }( )CPOS d U= , 
{ }1 2, ,..., nC c c c= , { }1 2, ,...,= mU u u u 
Đầu ra: ( )REAT C là tập tất cả các thuộc tính rút gọn của C. 
Xét quan hệ { }1 2, ,...,= mr u u u trên tập thuộc tính { }R C d= ∪ . 
Bước 1. Từ r ta tính hệ bằng nhau { }ij :1r E i j m= ≤ < ≤E với 
( ) ( ){ }ij : i jE a R a u a u= ∈ = . 
Bước 2. Từ 
rE ta xây dựng tập :d rA d A= ∈ ∉ ∃M E{ }: ,rB d B A B∈ ∉ ⊂E . 
Bước 3. Xây dựng tập 
dK
V R K
∈
= − I
M
. 
Bước 4. Đặt ( ) { }REAT C V d= − . 
Tập ( )REAT C được xây dựng là tập tất cả các thuộc tính rút gọn của C. 
Chứng minh 
Theo cách xây dựng dM tại Bước 2 và theo công thức tính bao đóng của tập thuộc tính 
trên quan hệ, dA∀ ∈M ta có rA A+ = và A không chứa d nên rA+ không chứa d, suy ra 
{ }A d F +→ ∉ . Mặt khác, nếu tồn tại B sao cho A B⊂ thì xảy ra hai trường hợp: (1) Nếu B 
không chứa d thì rB R
+
= ; (2) Nếu B chứa d thì hiển nhiên rB+ chứa d. Cả hai trường hợp ta 
đều có rB
+
chứa d hay { }B d F +→ ∈ . Do đó ( ),d MAX F d+=M với 
( ) { } { }{ }, : ,MAX F d A R A d F A B B d F+ + += ⊆ → ∉ ⊂ ⇒ → ∈ . Theo [17], 
( ) ( ) 1, rdMAX F d −+ = K với rdK là họ các tập tối thiểu của thuộc tính d trên quan hệ r. Do đó 
( ) 1rd d −=M K . Tại Bước 3 kết hợp với Bổ đề 5.2 ta có 
( ) 1 rrd ddK KK
V R K R K K
−∈ ∈∈
= − = − =I I U
M KK
. 
Tại Bước 4 ta có ( ) { } { }
( )rd R PRED CK
REAT C V d K d R
∈∈
 
= − = − =  
 
U U
K
 . 
Vũ Đức Thi 
700
Do đó theo định nghĩa, ( )REAT C là tập tất cả các thuộc tính rút gọn của C. 
Độ phức tạp thời gian của Thuật toán 1 
Với m là số đối tượng và n là số thuộc tính điều kiện, độ phức tạp thời gian để tính hệ bằng 
nhau rE tại Bước 1 là ( )2O m n . Tại Bước 2, hệ bằng nhau rE có tối đa 2m phần tử. Do đó, 
độ phức tạp thời gian để tính tập dM là ( )4O m n . Vì vậy, độ phức tạp thời gian của Thuật 
toán 1 là ( )4O m n . Độ phức tạp này là đa thức theo số hàng và số cột của bảng quyết định DS. 
Từ thuật toán 1 ta thu được các hệ quả sau: 
Hệ quả 1. Cho trước bảng quyết định nhất quán { }( ), , ,DS U C d V f= ∪ và thuộc tính a, tồn 
tại thuật toán xác định thuộc tính a là thuộc tính rút gọn hay không với thời gian đa thức theo 
số hàng và số cột của DS. 
 Về mặt lí thuyết, trong nhiều trường hợp chúng ta cần tìm tất cả các tập rút gọn 
trong bảng quyết định nhất quán. Chúng tôi đã xây dựng ba thuật toán sau: 
- Thuật toán tìm họ tất cả các tập rút gọn của bảng quyết định nhất quán với độ phức tạp 
thời gian là hàm mũ. 
 - Thuật toán xây dựng các phụ thuộc hàm từ bảng quyết định nhất quán với độ phức tạp 
thời gian là hàm mũ. Ý nghĩa của thuật toán này là xây dựng một công cụ hình thức để biểu 
diễn tất cả các quyết định dưới dạng các phụ thuộc hàm từ bảng quyết định nhất quán cho trước, 
không quan tâm đến dữ liệu cụ thể. 
 - Thuật toán xây dựng bảng quyết định thỏa mãn tập phụ thuộc hàm cho trước với độ 
phức tạp thời gian là hàm mũ. Ý nghĩa của thuật toán này là khẳng định tính đúng đắn của việc 
suy diễn và ra quyết định trên các phụ thuộc hàm. Nghĩa là có thể thực hiện suy diễn và ra quyết 
định trên các tri thức dưới được biểu diễn dưới dạng phụ thuộc hàm mà không quan tâm đến 
bảng dữ liệu cụ thể. 
Các kết quả này đã được công bố trong [5,33]. 
Lời cám ơn. Tôi xin chân thành cám ơn Ban Biên tập Tạp chí Khoa học và Công nghệ đã mời tôi viết bài 
báo này. Do khuôn khổ có hạn của bài báo, tôi chỉ có thể trình bày một phần những kết quả đã đạt được 
trong lĩnh vực cơ sở dữ liệu và khai phá dữ liệu. Một số kết quả trình bày trong bài báo này là những kết 
quả làm việc của các nghiên cứu sinh của tôi, TS. Nguyễn Long Giang, TS Nguyễn Huy Đức, TS Nguyễn 
Hoàng Sơn trong nhóm nghiên cứu “Cơ sở dữ liệu và khai phá dữ liệu “ của Viện Công nghệ thông tin. 
TÀI LIỆU THAM KHẢO 
1. Agrawal R., Imielinski T., Swami A. - Mining association rules between sets of items in 
large databases, Proceedings of the ACM SIGMOD conference, Washington DC, USA, 
1993, pp. 207-216. 
2. Tao F., Murtagh F., Farid M. - Weighed Association Rule Mining Using Weighted 
Support and sighificance Framework, SIGKDD,2003, pp. 61-666. 
Một số vấn đề tính toán liên quan đến cơ sở dữ liệu và khai phá dữ liệu 
701
3. Khan M. S., Muyeba M., Coenen F. - A weighted utility framework for mining 
association rule, Proc. IEEE European Modeling Symporium 2008, 2008, pp. 87-92. 
4. Nguyễn Long Giang, Vũ Đức Thi - Một số phương pháp rút gọn thuộc tính trong bảng 
quyết định dựa trên ENTROPY cải tiến, Tạp chí Tin học và Điều khiển học 27 (2) (2011) 
166-175. 
5. Nguyễn Long Giang, Vũ Đức Thi - Thuật toán tìm tất cả các rút gọn trong bảng quyết 
định, Tạp chí Tin học và Điều khiển học 27 (3) (2011) 211-218. 
6. Vũ Đức Thi, Nguyễn Huy Đức - Một số kỹ thuật hiệu quả tỉa các tập mục ứng viên trong 
khai phá tập mục lợi ích cao, Kỉ yếu Hội thảo quốc gia “Một số vấn đề chọn lọc của Công 
nghệ thông tin và truyền thông – Biên Hòa, 2010, tr. 214-232. 
7. Armstrong W. W. - Dependency Structures of Database Relationships, Information 
Processing 74, Holland publ. Co. 1974, pp. 580-583. 
8. Vũ Đức Thi - Cơ sở dữ liệu - Kiến thức và thực hành, Nhà xuất bản Thống kê, Hà Nội, 
1997. 
9. Chen C. H., Hong T. P., Tseng V. S. - An improved approach to find membership 
funtions and multiple minimum supports in fuzzy data mining, Expert Systems with 
Application 36 (2009) 10016-10024. 
10. Chen H., Li T., Qiao S., Ruan D. - A Rough set based dynamic maintenance approach for 
approximations in coarsening an refining attribue values, International Journal of 
intelligent systems 25 (2010) 1005-1026. 
11. Erwin A., Gopalan R. P., and Achuthan N. R. - CTU-Mine: An Efficient High Utility 
Itemset Mining Algorithm Using the Pattern Growth Approach, Paper presented at the 
IEEE 7th International Conferences on Computer and Information Technology, Aizu 
Wakamatsu, Japan. 
12. El-Hajj M. and Zaiane Osmar R. - Inverted matrix: Efficient discovery of frequent items 
in large datasets in the context of interactive mining, In Proc. 2003 Int’l Conf. on Data 
Mining and Knowledge Discovery (ACM SIGKDD) 2003, 2007, pp. 109-118. 
13. Demetrovics J. and Thi V. D. - Some remarks on generating Armstrong and inferring 
functional dependencies relation, Acta Cybernetica 12 (2003) 167-180. 
14. Demetrovics J, Thi V. D. - Some computational problems related to the functional 
dependency in the relational datamodel, Journal Acta Scien. Mathematics, Hungary, 57 
(1993) 627-638. 
15. Demetrovics J, Thi V. D. - Some results about normal forms for functional dependency in 
the relational datamodel,. Journal of Discrete Applied Mathematics, North Holland 69 
(1996) 61-74. 
16. Demetrovics J, Thi V. D. - Describing Candidate Keys by Hypergraphs, J. Computers and 
Artificial Intelligence 18(2) (1999) 191-207. 
17. Demetrovics J, Thi V. D. - Some Computational problems related to Boyce-Codd nornal 
form , Ann. Univ. Sci. Budapest. Sect. Comput. Hungary 19 (2000) 19-130. 
18. Han J., Pei J., and Yin Y. - Mining frequent patterns without candidate generation, In 
ACM SIGMOD Intl. Conference on Management of Data, 2003, pp. 1-12. 
19. Hilderman R. J., Carter C. L., Hamilton H. J., and Cercone N. - Mining association rules 
from market basket data using share measures and characterized itemsets, Intl. Journal 
of Artificial Intelligence Tools 7 (2003) 189-220. 
Vũ Đức Thi 
702
20. Vũ Đức Thi - Giáo trình Cơ sở dữ liệu nâng cao, Nhà xuất bản Đại học Thái Nguyên, 
2010. 
21. Khan M. S., M. Muyeba M., Coenen F. - Fuzzy Weighted Association Rule Mining with 
Weighted Support and Confidence Framework, Proc. 1st In workshop on Algorithems for 
Large _ Scale Information Processing in knowledge Discovery (ALSIP 2008), Held in 
conjunction with PAKDD 2008 (Japan), 2008, pp. 52-64. 
22. Li Y. C., Yeh J. S., Chang C. C. - A fast algorithm for mining share-frequent 
itemsets, Lecture Notes in Computer Science, Springer-Verlag, Germany 3399, 2005, 
pp. 417-428. 
23. Liang J. Y, Chin K. S., Dang C. Y., Richard C. M. YAM - New method for measuring 
uncertainty and fuzziness in rough set theory, International Journal of General Systems 31 
(2002) 331-342. 
24. Liu D., Li T., Ruan D., Zou W. - An incremental approach for inducing knowledge from 
dynamic information systems, Funda. Inform. 94 (2009) 245-260. 
25. Liu Y., W. Liao K., and Choudhary A. - A fast high utility itemsets mining algorithm”, in 
Proc. 1st Intl. Conf. on Utility-Based Data Mining, Chicago Illinois, 2009, USA, 
pp. 90-99,. 
26. Luo P., He Q. and Shi Z. Z. -Theoretical study on a new information entropy and its use 
in attribute reduction, ICCI (2005) pp. 73-79. 
27. Pawlak Z. -Rough sets, International Journal of Computer and Information Sciences, 11 
(5) (1982) 341-356. 
28. Vũ Đức Thi - Thuật toán trong tin học, Nhà xuất bản Khoa học kỹ thuật, Hà Nội, 1999. 
29. Thi V. D. Sơn N. H. - Some problems related to keys and Boyce-Codd normal form, Acta 
Cybernet, Hungary 16 (3) (2004) 473-483. 
30. Thi V.D., Son N.H. - Some results related to dense families of database relations. Acta 
Cybernet, Hungary 17 (1) (2005) 173-182. 
31. Thi V. D., Son N. H. - On Armstrong relations for strong dependencies. Acta Cybernet, 
Hungary 17 (3) (2006) 521-531. 
32. Thi V. D., Duc N. H. - Mining High Utility Itemsets in Massive Transactional Database, 
Acta Cybernetica 20 (2011) 331-346. 
33. Thi V. D., Giang N. L. - A Method to Construct a Decision Table from a relation scheme, 
Jounal of Cybernetics and Information Technology, Bugarian Academy of Sciences 3 
(2011) 32-41. 
34. Yao H., Hamilton H. J. - Mining Itemsets Utilities from Transaction Databases, Data 
and Knowledge Engeneering 59 (3) (2006). 
35. Yao H., Hamilton H. J., Geng L. - A Unified Framework for Utility Based Measures for 
Mining Itemsets, UBDM’06 Philadelphia, Pennsylvania, USA, 2006. 
36. Wang G. Y. - Algebra view and information view of rough sets theory, In: Dasarathy 
BV,editor. Data mining and knowledge discovery: Theory, tools, and technology III, 
Proceedings of SPIE, 2001, pp. 200-207. 
Một số vấn đề tính toán liên quan đến cơ sở dữ liệu và khai phá dữ liệu 
703
ABSTRACT 
SOME COMPUTATIONAL PROBLEMS RELATED TO DATABASE 
AND DATA MINING 
Vu Duc Thi 
Institute of Information Technology, VAST, 18 Hoang Quoc Viet, Cau Giay, Hanoi, Vietnam 
Email: vdthi@ioit.ac.vn 
 Database and data mining are very important development in information technology (IT). 
In essence the data play a fundamental role in the processing of information on computer 
systems. Database theory and the practical applications of this theory have been developed and 
achieved many accomplishments since the 80th of last century. Essentially, database theory 
provides us with the most important knowledge related to organizational issues, design and 
construction of the database management system. On the basis of the results obtained in this 
theory, computer companies such as IBM, Microsoft, Oracle, Apple has built the database 
management system trade all over the world market requirements, such as SQL, Oracle, IBM 
DB2. In some aspects, the present, in all activities of mankind has accumulated a huge amount 
of data. However, knowledge is too small. Therefore, the current research directions for 
knowledge discovery from data is a very powerful development. A particularly critical stage in 
the process of knowledge discovery from data is data mining to acquire knowledge. Hence, 
research on data mining methods is a very basic directions in IT. In this paper, we present some 
main results related to the computational problems, in fact algorithmic problems, in the field of 
database and data mining. 
Keywords: database, data mining, database management system, knowledge discovery from 
data, computational problem, algorithm.