Incorporating Cardinality Constraints and Synonym Rules into Conditional Functional Dependencies

We propose an extension of conditional functional dependencies (CFDs), denoted by cCFDs, to express cardinality constraints, domain-specific conventions, and patterns of semantically related constants in a uniform constraint formalism. We show that despite the increased expressive power, the satisfiability and implication problems for cCFDs remain NP-complete and coNP-complete, respectively, the same as their counterparts for CFDs. We also identify tractable special cases.