Analyses and Validation of Conditional Dependencies with Built-in Predicates

This paper proposes a natural extension of conditional functional dependencies (

cfd

s [14]) and conditional inclusion dependencies (

cind

s [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

cfd

s and

cind

s. 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

cfd

s and

cind

s counterparts. (b) The other concerns validation of

cfd

p

s and

cind

p

s. We show that given a set

$\it \Sigma$

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

$\it \Sigma$

. This provides commercial

dbms

with an immediate capability to detect errors based on

cfd

p

s and

cind

p

s.