Hệ sinh ánh xạ đóng và bài toán biểu diễn phản cơ sở

Abstract

Closure mapping on a finite set  U is a mapping satisfied reflexibility, monotonicity, and idempotence properties. This is one of mathematical tools supporting theoretical aspects in several of IT fields, such as database and knowledge-base systems, deductive systems, data mining etc. .. Each closure mapping can be specified by a deductive system, called generation system. An antibase of a closure mapping f on U  is the subset P of U satified f(P) ¹ U, and "A ÎU \ P: f(PA) = U. It is shown that antibases can be used in database design and data mining to reduce computational complexity of  algorithms for computing such objects as closures, keys, normal forms, sensitive itemsets and association rules, etc… This paper presents some new results concerning representing the antibases of a given generation system.  We show that each antibase in a generation system can be represented as a union of the maximal right-hand side and an antibase of the reduced system.