Increasing the Expressivity of Conditional Functional Dependencies without Extra Complexity

Loreto Bravo, Wenfei Fan, Floris Geerts, Shuai Ma

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The paper proposes an extension of CFDs [1], referred to as extended Conditional Functional Dependencies (eCFDs). In contrast to CFDs, eCFDs specify patterns of semantically related values in terms of disjunction and inequality, and are capable of catching inconsistencies that arise in practice but cannot be detected by CFDs. The increase in expressive power does not incur extra complexity: we show that the satisfiability and implication analyses of eCFDs remain NP - complete and coNP -complete, respectively, the same as their CFDs counterparts. In light of the intractability, we present an algorithm that approximates the maximum number of eCFDs that are satisfiable. In addition, we revise SQL techniques for detecting CFD violations, and show that violations of multiple eCFDs can be captured via a single pair of SQL queries. We also introduce an incremental SQL technique for detecting eCFD violations in response to database updates. We experimentally verify the effectiveness and efficiency of our SQL -based detection methods.
Original languageEnglish
Title of host publicationProceedings of the 24th International Conference on Data Engineering, ICDE 2008, April 7-12, 2008, Cancún, México
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages10
ISBN (Electronic)978-1-4244-1837-4
ISBN (Print)978-1-4244-1836-7
Publication statusPublished - 2008


Dive into the research topics of 'Increasing the Expressivity of Conditional Functional Dependencies without Extra Complexity'. Together they form a unique fingerprint.

Cite this