Conditional Differential Dependencies (CDDs)

Differential dependency (DD) is a newly proposed data dependency theory that captures the relationships amongst data values. Like the classical functional dependency (FD) theory, DDs are defined to hold over entire instances of relations. This paper proposes a novel extension of the DD theory to hold over subsets of relations, called conditional DD (CDD), similar to the relaxations of FD to conditional FD (CFD) [4] and conditional FD with predicates (CFDPs) [6]. In this work, we present: the formal definitions; the consistency and implication analysis; and a set of axioms to infer CDDs. Furthermore, we study the discovery problem of CDDs and present an algorithm for mining a minimal cover set Σc of constant CDDs from a given instance of a relation. And, we propose an interestingness measure for ranking discovered CDDs and reducing the size |Σc| of Σc. We demonstrate the efficiency, effectiveness and scalability of the discovery algorithm through experiments on both real and synthetic datasets.