Characterizations of multivalued dependency implication over undetermined universes

Abstract

In relational databases the original definition of a multivalued dependency is dependent on the underlying relation schema. In this context, the implication of multivalued dependencies has been characterised from multiple perspectives. Logically, it is equivalent to the logical implication of certain material implications in Boolean propositional logic. Proof-theoretically, the Chase procedure offers a convenient tool to decide implication. And algebraically, the implication can be characterised by the notion of closed attribute sets with respect to multivalued dependencies. The assumption of having a fixed underlying relation schema is not always feasible in practice, and also distinguishes multivalued dependencies from other classes of data dependencies. In this paper, we establish logical, proof-theoretical and algebraic characterisations for Biskup’s notion of multivalued dependency implication over undetermined universes. That is, we unburden the current theory of the assumption of having a fixed underlying relation schema. From the perspective of probability theory this means that is unnecessary to fix the set of discrete probabilistic variables in order to utilise conditional independencies.