Research On Application Of Rough Set Theory In Database

Rough Set Theory is a new mathematical tool to deal with vague and uncertain problems, which has been widely applied in machine learning, decision analysis, knowledge discovery, expert system, decision support system, pattern recognition, fuzzy control or other fields.At present the research on application of Rough Set Theory in database focuses on two aspects: One aspect is KDD (Knowledge Discovery in Database), the other aspect is RRDM (Rough Relational Database Model).Knowledge reduction, which is also named attribute reduction, is one of the main problems in KDD that Rough Set Theory deals with. The time complexity of present knowledge algorithms that based on discernible matrix or based on discrimination function is generally O(|A|~2|U|~2), where |A| is the number of attributes and |U| is the number of elements in discourse domain U. When the data amout is very large, the feasibility of these algorithms will face challenge. And the low efficiency of these algorithms has also limited the wide application of Rough Set Theory. So it has great significance in seeking the algorithm with high efficiency and good feasibility.Rough Relational Database Model (RRDM) is a composite production of Rough Set Theory and classical Relational Database Model. Now in the study on RRDM, the domestic and foreign scholars studied some aspects separately without combining them together, and some concepts of RRDM is not defined normally. So if an integrated and normal description of RRDM is constructed from four aspects: the rough relational data structure, the rough relational database operations, the rough relational integrity constraint and the rough relational normalization, it will certainly lay a complete theoretical foundation of the implementation and the wide application of RRDM.The research work of this paper focuses on two aspects: one aspect is to seek knowledge reduction algorithm with high efficiency and good feasibility, the other aspect is to consturct an integrated and normal description of RRDM from global perspective. The main research achievements are following:1. A new knowledge reduction definition based on partition subdivision is proposed; its equivalence to the classic attribute reduction definition based on positive region is proved. By using this new knowledge reduction, the calculation amount of knowledge reduction algorithm will shrink.2. A consistent degree is introduced to evaluate the importance of condition attribute for decision attribute. This consistent degree is taken as the heuristic information in knowledge reduction algorithm. And it is proved that the smaller of the conditional attribute's consistent degree the less importance of it for decision attribute, so it is rational to take this consistent degree as the heuristic information.3. Based on the above results, a heuristic knowledge reduction algorithm is designed. The time complexity of this algorithm is O (|C|~2|U|), where |C| is the number of conditional attributes and |U| is the number of elements in discourse domain U. Comparing with some classical algorithms of knowledge reduction, this algorithm has lower time complexity and smaller calculate amount.4. An integrated Rough Relation Database Model is constructed by four aspects: the Data Structure of Rough Relation, the Rough Relational Database Operations, the Rough Relational Integrity Constraint and the Rough Relational Normalization.5. The Rough Relational Integrity Constraint is proposed to consummate the capability of RRDM to solve uncertain information.6. The Rough Relational Normalization is proposed to solve the problem that how to construct a well-defined database schema in logical design of rough relational database.