| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 427759 | Information Processing Letters | 2009 | 7 Pages |
Abstract
We propose an extension of conditional functional dependencies (CFDs), denoted by CFDcs, 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 CFDcs remain NP-complete and coNP-complete, respectively, the same as their counterparts for CFDs. We also identify tractable special cases.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
