A rough set approach for approximating differential dependencies.

Highlights • A differential-relation-based rough set model on relational databases is proposed. • Using this model, the measures for differential dependencies (DDs) are expressed. • An efficient method to compute the approximate error measure of g 3 for DDs is developed. • The rough sets on the differential decision systems (DDSs) are introduced. • A bridge between DDs in databases and attribute dependencies in DDSs is formed. Abstract Data dependencies in databases and attribute dependencies in decision systems are important when addressing problems concerning data quality and attribute reduction, in which measures play a significant role in approximating these dependencies to achieve better adaptation to uncertain data. This paper proposes a differential-relation-based rough set model from the perspective of relational databases to express the dependency degree, error measures, confidence, information granulation and differential class distance for differential dependencies (DDs) and the relationships among them in a unified framework. Moreover, the error measure g 3 has been widely studied and applied for data dependencies. However, the computation of g 3 for DDs is NP-complete. Therefore, based on the proposed rough set, we introduce a new method that can compute the approximate error measure g 3 ˜ of g 3 in polynomial time. This study demonstrates that our approach can provide a substantially better approximation, that is, an approximation closer to the optimal solution g 3 , compared to the existing greedy method. We also introduce the differential-relation-based rough set from the perspective of information systems and make a connection to the rough sets induced by non-equivalence relations. The two views of the differential-relation-based rough sets form an essential bridge between the DDs in databases and attribute dependencies in differential decision systems (DDSs) that allows sharing measures for approximating the dependencies. These results are meaningful for approximate computations, the development of algorithms for attribute reduction in decision systems and the discovery of approximate differential dependencies (ADDs) in databases. [ABSTRACT FROM AUTHOR]