一个新的基于数据库技术的快速求核算法

New Efficient Algorithm for Computing Core Based on Database Technology

求核是粗糙集中一个重要的研究内容之一.为降低求核的算法复杂度,给出了简化决策表的定义.由于求简化决策表时,要先求出IND(C),故以基数排序的思想设计了一个新的求IND(C)的算法,其时间复杂度为O(C‖U).然后将简化的决策表转化成协调的新决策表,在此新决策表上得到了一个求核的性质,并证明了用该性质求出的核与原决策表的核是一致的.在此基础上,设计了一个基于数据库技术的快速求核算法,其时间复杂度为O(C‖U).

Computing core is an important research issue in the rough set. To cut down the complexity of algorithm for computing core,a definition of simplified decision table is provided. Since the simplified decision table can not be got until IND（C） is determined,a new algorithm for computing the IND（C） is designed with the idea of radices sorting whose complexity is cut down to O（ ｜C ｜｜ U ｜）. Then this simplified decision table is transformed to a consistent decision table. A new property of this new consistent decision table is obtained. At the same time,it is proved that the core obtained from this new property is the same as the core of the old decision table. On this condition,a new algorithm for computing core based on database technology is designed whose complexity is cut down to O（ ｜ C ｜｜ U ｜ ）.