Characterisations of multivalued dependency implication over undetermined universes

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.

► The implication problem of multivalued dependencies over relations is studied.
► The problem is considered where the underlying schema remains undetermined.
► A characterisation in terms of Boolean propositional logic is established.
► A characterisation in terms of a chase procedure is established.
► A characterisation in terms of closed sets of schema attributes is established.