Abstract:
We investigate the implication problem for classes of data dependencies over
SQL table definitions. Under Zaniolo’s “no information” interpretation of null
markers we establish an axiomatization and algorithms to decide the implication
problem for the combined class of functional and multivalued dependencies in the
presence of NOT NULL constraints. The resulting theory subsumes three previously orthogonal frameworks. We further show that the implication problem of
this class is equivalent to that in a propositional fragment of Cadoli and Schaerf’s
family of para-consistent S-3 logics. In particular, S is the set of variables that
correspond to attributes declared NOT NULL. We also show how our equivalences
for multivalued dependencies can be extended to Delobel’s class of full first-order
hierarchical decompositions, and the equivalences for functional dependencies can
be extended to arbitrary Boolean dependencies. These dualities allow us to transfer
several findings from the propositional fragments to the corresponding classes of
data dependencies, and vice versa. We show that our results also apply to Codd’s
null interpretation "value unknown at present", but not to Imielinski’s or-relations
utilizing Levene and Loizou’s weak possible world semantics. Our findings establish NOT NULL constraints as an effective mechanism to balance not only the
1certainty in database relations but also the expressiveness with the efficiency of
entailment relations. They also control the degree by which the implication of data
dependencies over total relations is soundly approximated in SQL table definitions.
