Abstract:
We investigate the implication problem for independence atoms X?Y of dis-
joint attribute sets X and Y on database schemata. A relation satisfi es X?Y
if for every X-value and every Y -value that occurs in the relation there is some tuple in the relation in which the X-value occurs together with the Y -value. We
establish an axiomatization by a finite set of Horn rules, and derive an algorithm
for deciding the implication problem in low-degree polynomial time in the input.
We show how to construct Armstrong relations which satisfy an arbitrarily given
set of independence atoms and violate every independence atom not implied by
the given set. Our results establish independence atoms as an e fficient subclass of
embedded multivalued data dependencies which are not axiomatizable by a finite set of Horn rules, and whose implication problem is undecidable.