Incorporating cardinality constraints and synonym rules into conditional functional dependencies

Wenguang Chen, Wenfei Fan, Shuai Ma

Research output: Contribution to journalArticlepeer-review

Abstract

We propose an extension of conditional functional dependencies (CFDs), denoted by CFDcCFDcs, 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 CFDcCFDcs remain NP-complete and coNP-complete, respectively, the same as their counterparts for CFDs. We also identify tractable special cases.
Original languageEnglish
Pages (from-to)783-789
Number of pages7
JournalInformation Processing Letters
Volume109
Issue number14
DOIs
Publication statusPublished - 2009

Fingerprint Dive into the research topics of 'Incorporating cardinality constraints and synonym rules into conditional functional dependencies'. Together they form a unique fingerprint.

Cite this