Independence in database relations

We investigate the implication problem for independence atoms X⊥Y of disjoint attribute sets X and Y on database schemata. A relation satisfies 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 efficient subclass of embedded multivalued data dependencies which are not axiomatizable by a finite set of Horn rules, and whose implication problem is undecidable.