Analyses and Validation of Conditional Dependencies with Built-in Predicates

Wenguang Chen, Wenfei Fan, Shuai Ma

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


This paper proposes a natural extension of conditional functional dependencies (cfds [14]) and conditional inclusion dependencies (cinds [8]), denoted by cfd p s and cind p s, respectively, by specifying patterns of data values with ≠, <, ≤, > and ≥ predicates. As data quality rules, cfd p s and cind p s are able to capture errors that commonly arise in practice but cannot be detected by cfds and cinds. We establish two sets of results for central technical problems associated with cfd p s and cind p s. (a) One concerns the satisfiability and implication problems for cfd p s and cind p s, taken separately or together. These are important for, e.g., deciding whether data quality rules are dirty themselves, and for removing redundant rules. We show that despite the increased expressive power, the static analyses of cfd p s and cind p s retain the same complexity as their cfds and cinds counterparts. (b) The other concerns validation of cfd p s and cind p s. We show that given a set Σ of cfd p s and cind p s on a database D, a set of sql queries can be automatically generated that, when evaluated against D, return all tuples in D that violate some dependencies in Σ . This provides commercial dbms with an immediate capability to detect errors based on cfd p s and cind p s.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications
Subtitle of host publication20th International Conference, DEXA 2009, Linz, Austria, August 31 - September 4, 2009. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-03573-9
ISBN (Print)978-3-642-03572-
Publication statusPublished - 2009

Cite this