In Database Theory, Multivalued Dependencies are the main tool to define the Fourth Normal Form and, as such, their inference problem has been deeply studied; two related notions appearing in that study are a syntactical analog in propositional logic and a restriction that maintains to this logic the same relationship as Functional Dependencies do to Horn logic. We present semantic, lattice-theoretic characterizations of such multivalued dependencies that hold in a given relation, as well as similar results for the related notions just mentioned. Our characterizations explain better some previously known facts by providing a unifying framework that is also consistent with the studies of Functional Dependencies.
Functional Dependencies (FDs) and Multivalued Dependencies (MVDs) are important notions in Database Theory. They help to formalize the necessary conditions on a given relation to ensure, up to various degrees, a reduced amount of redundancy; and they indicate decomposition (more properly, normalization) operations to be performed to obtain such irredundant (normal form) relations.
The most widely studied specific problems about these notions concern how
to axiomatize, with a limited number of dependencies, a large set of them, or
how to test as efficiently as possible whether a given dependency is a logical
consequence of others ([
The less famous notion of Degenerate Multivalued Dependencies (DMVDs) does not play such an important role in database normalization, and has been usually neglected by database design practitioners, but has been studied by theorists. The interest of DMVDs is that they share some features with FDs (they are equality-generating instead of tuple-generating) and some features with MVDs (they have a similar form and analogous syntactical inference rules); then, their study may clarify relationships between FDs and MVDs. In particular, the highly more complex combinatorics of MVDs compared to FDs makes it nontrivial to extend results for FDs into the MVD realm, and then DMVDs may offer a useful intermediate stepping stone.
In some ways, dependencies (functional or multivalued) behave as certain
fragments of propositional logic. The main interest of studying this analogy is
double: rfist, to propose alternative ways to solve inference problems, either for
sets of propositional clauses or for sets of dependencies; and, second, to offer
alternative semantic proofs of the syntactical correspondences of the (fully
analogous) inference calculi available for FDs and MVDs and for their propositional
counterparts. This approach thus allows one to simplify, to some extent, the
combinatorics contained in the dependencies. More precise explanations of how
functional dependencies and multivalued dependencies are related to
propositional clauses are given in the next section, and additional details can be found
in [
Recent progresses in [
Thanks to the additional knowledge obtained in [
Since we will be dealing with sets of data that have different domains (multivalued and binary) for a set of attributes R, we will denote a set of tuples or a relation r = {t1, t2 . . . tn} when the attributes are defined over a multivalued domain, following the usual notation in database research. Likewise we denote a theory, that is, a set of propositional models, each a binary tuple, as T = {m1, m2 . . . mn} when the domain is binary.
Definition 1. The binarization of r, BIN (r), is the set of binary tuples (theory) that result from comparing all the pairs of tuples attributewise.
For instance, given a set of tuples r = {{a, b, c, d}, {a, b, d, c}, {a, c, c, d}, {a, c, d, c}}, it would yield BIN (r) = {{1, 0, 0, 0}, {1, 0, 1, 1}, {1, 1, 0, 0}} Observe that, being a set, BIN (r) has no duplicates. 2.1
A main combinatorial ingredient of our contributions is given by partitioning the set of attributes into equivalence classes.
Definition 2. The partition of attributes P ART (mi) that results from a model mi is the partition of R such that each attribute that has a true value in mi, forms a singleton class, and all the attributes with false value are together in the same class.
For instance, if mi = {11001}, then P ART (mi) = {A|B|CD|E}. We freely say that P ART (T ) is the set of partitions for each model of T , with no duplications, of course, even if the same partition arises from several models. For instance, if T = {1101, 1011}, then P ART (T ) would be {A|B|C|D}. The set of all the partitions is denoted ℘.
The key operation on partitions will be here a standard meet operation
corresponding to the lattice of partitions; the corresponding join operation is also a
usual operation on partitions. Namely, given two partitions, their join is formed
by all the classes that can be obtained by pairwise intersecting one class from
each, that is, the coarsest partition that is finer than both; whereas the meet is
the nfiest partition that is coarser than both, so that the partial ordering
associated to the lattice is the natural ordering where P ≤ P 0 whenever P 0 is nfier
than P . More details on alternative ways to define the meet operation can found
in [
Moreover, through the operation P ART , we obtain a way of computing a meet operation on models that is different from the standard bitwise intersection. For instance, 1110 ∧ 0011 = 0011, because P ART (1110) = {a|b|c|d} and P ART (0011) = {ab|c|d}, and {a|b|c|d} ∧ {ab|c|d} = {ab|c|d} corresponding to the model 0011. Note that the operator ∧ may not be applicable to some models, in the sense that the meet partition might have more than one nonsingleton class and then there would be no model corresponding to the meet partition (e.g., for 11100 and 00111). Either among partitions or among models, we employ the following notation: Definition 3. For any given set S, if the operator ∧ is defined on that set, the closure under meet of a subset Q ⊆ S, denoted [Q]∧, is the smallest subset of S that contains Q and is closed under ∧. 2.2
All our expressions have two parts, an antecedent and a consequent, each being a set of attributes or of propositional variables, denoted X, Y , or the like; juxtaposition as in XY denotes union. It is customary to separate them by some sort of double arrow. For now on, we use only the word “attributes” to mean “attributes or propositional variables” whenever this is the necessary interpretation. The various expressions, and their semantics, are as follows.
Definition 4. A multivalued dependency clause (MVDcl) X ⇒⇒ Y holds in a theory T if for each mi ∈ T if mi |= X then mi |= Y or mi |= R \ XY . It is, if the X attributes are true, then, the Y attributes are true or the R \ XY attributes are true.
Definition 5. A degenerate multivalued dependency (DMVD) X 7 →7→ Y holds in r if whenever two tuples ti, tj ∈ r, ti[X] = tj [X] implies that ti[Y ] = tj [Y ] or ti[R \ XY ] = tj [R \ XY ].
Definition 6. A multivalued dependency (MVD) X →→ Y holds in r if whenever two tuples ti, tj ∈ r coincide in X, ti[X] = tj [X], it implies that the tuples t0i, t0j exist in r, where t0i[X] = t0j [X] = ti[X], t0i[Y ] = ti[Y ], t0j [Y ] = tj [Y ], and conversely t0i[R \ XY ] = tj [R \ XY ] and t0j [R \ XY ] = ti[R \ XY ]. Definition 7. The syntactically equivalent MVD (DMVD) of a MVDcl X ⇒⇒ Y is X →→ Y (X 7 →7→ Y ); and similarly between MVDs and DMVDs.
It is immediate to check that, if a degenerate multivalued dependency holds in
a relation r, so does the syntactically equivalent multivalued dependency. Some
common properties for DMVDs, MVDs and MVD clauses are the following:
1. Complementation: If X → Y holds, then X → R \ Y holds.
2. Reflexivity: If Y ⊂ X, then X → Y holds.
3. Union of right-hand side: If X → Y and X → Y 0 hold, then X → Y Y 0 holds.
where X → Y can be a DMVD, a MVD or a MVD clause. For a proof of these
properties the reader can refer to [
We note that, for a given set of attributes X, all these attributes will appear as singletons in DEP (X) regardless of the kind of dependency basis. This is so because of the reflexivity property that holds in all these dependencies; they are often omitted in this generalized dependency. Additionally, the unions Y mentioned at the end include, as particular cases, the individual classes of the partition DEP (X). The definition of a dependency basis allows us to group all the MVDcl, DMVDs or MVDs that have the same left-hand side in one generalized MVDcl, DMVD or MVD: Definition 9. All the MVDcl (DMVD, MVD) that have X in their lefthand side may be represented by a generalized MVDcl (DMVD, MVD) X ⇒⇒ DEP (X) (X 7 →7→ DEP (X), X →→ DEP (X).).
In [
Another relevant notion about partitions of attributes is that of matching,
which varies depending whether the partition is considered to be modelling a
set of DMVDs or a set of MVDs. We provide here a brief description of this
property (more details can be found in [
Lattice Characterization of Multivalued Dependency Clauses It is easy to prove that, given a relation r, a DMVD X 7 →7→ Y holds in r if and only if the syntactically equivalent MVDcl X ⇒⇒ Y holds in BIN (r), as the next proposition states: Proposition 1. Let be r a relation, then X 7 →7→ Y holds in r if and only if X ⇒⇒ Y holds in BIN (r).
According to this result, and due to the fact that the operator Γ DMV D as
denfied in [
Proposition 2. Γ MV Dcl is a closure operator. Proof. We prove the three axioms for closure operators.
1. P ≤ Γ MV Dcl(P ). Obvious since Γ MV Dcl always returns a P 0 ∈ [P ART (T )]∧ such that P ≤ P 0. 2. Γ MV Dcl(P ) = Γ MV Dcl(Γ MV Dcl(P )). Let P 0 = Γ MV Dcl(P ) and, besides, Q = Γ MV Dcl(P 0) so that P 0 ≤ Q. For all P 00 ∈ [P ART (T )]∧, P 0 ≤ P 00 ≤ Q implies that P 00 = Q, and since P 0 ∈ [P ART (T )]∧ and P 0 ≤ P 0 ≤ Q, we have that Q = P 0. 3. P ≤ P 0 ⇒ Γ MV Dcl(P ) ≤ Γ MV Dcl(P 0). Since P ≤ P 0, we have that P ≤ Γ MV Dcl(P 0), and also P ≤ Γ MV Dcl(P ). We then have that
P ≤ Γ MV Dcl(P ) ∧ Γ MV Dcl(P 0) ≤ Γ MV Dcl(P ) By the closure under meet, Γ MV Dcl(P ) ∧ Γ MV Dcl(P 0) ∈ [P ART (T )]∧; by the last condition of the definition, we get Γ MV Dcl(P ) ∧ Γ MV Dcl(P 0) = Γ MV Dcl(P ) or, equivalently, Γ MV Dcl(P ) ≤ Γ MV Dcl(P 0) as desired.
Note that P ART (mi) can only express a partition that has only one class that is not a singleton. Then, all the partitions that belong to P ART (T ) will have only one class that is not a singleton. Partitions with more than one nonsingleton can be obtained through the meet operation. The next theorem proves that Γ MV Dcl characterizes all the MVD clauses that hold in a theory T : Theorem 1. A generalized MVD clause X ⇒⇒ Y1| . . . |Ym holds in T if and only if for P = {X1| . . . |Xn|Y1| . . . |Ym} and P 0 = {X1| . . . |Xn|Y1 . . . Ym} we have that Γ MV Dcl(P 0) = P , where the Xj are the attributes in X. Proof. (⇒) We rfist note that the fact that a generalized MVD clause X ⇒⇒ Y1| . . . |Ym holds in T means that these Yi constitute the finest possible right hand side for a generalized MVD clause that has X in its left hand side. For each i, each model in T must satisfy X ⇒⇒ Yi ∨ Y 0, where Y 0 stands for the union of the remaining classes of attributes. This implies that all the zeros of the model are in the same class Yi, since otherwise it is easy to check that this last condition becomes violated. Conversely, it is immediate to see that, if all the models satisfying X have all their zeros together in one single Yi, then T satisfies the dependency clause.
We must prove that P 0 = {X1| . . . |Xn|Y1| . . . |Ym} belongs to [P ART (T )]∧, and that no other partition in [P ART (T )]∧ exists in between P and P 0. Consider the theory T 0 = {m ∈ T m |= X}, and let Q = Vm∈T 0 P ART (m). Clearly all Xi are singletons in all P ART (m) form m ∈ T 0, and, as just described, all of them have their zeros (the only nonsingleton in P ART (m)) included in one of the Yi’s, so that for all such m we have P 0 ≤ P ART (m), and the properties of the meet ensure P 0 ≤ Vm∈T 0 P ART (m) = Q. We argue that actually P 0 = Q so that indeed P 0 ∈ [P ART (T )]∧: assume that P 0 < Q, that is, some class Yi of P 0 is split in Q into more than one class. Fix two attributes A and B that belong to Yi that are in different classes of Q, say ZA and ZB respectively; from P 0 ≤ Q as just proved, ZA ∪ ZB ⊆ Yi. Noting the definition of Q, we see that no model in T 0 has zeros both in ZA and in ZB, since otherwise the meet operation would have joined them into a single class. Then, the observation we made in the previous paragraph tells us that the multivalued dependency clause X ⇒⇒ ZA is true in T , and ZA should be obtained as a union of Yi’s, which is not the case. Therefore P 0 = Q, so that P 0 ∈ [P ART (T )]∧.
It remains to prove that there is no other partition P 00 ∈ [P ART (T )]∧ with P ≤ P 00 ≤ P 0, except, of course, for P 0 itself, and this will imply that Γ MV Dcl(P ) = P 0, as we wish. Assume P 00 ∈ [P ART (T )]∧, and let T 00 ⊆ T such that P 00 = Vm∈T 00 P ART (m). Again all the Xi must be singletons in P 00 due to P ≤ P 00, which means that the models in T 00 satisfy X, or, equivalently, T 00 ⊆ T 0. It is immediate to see, then, that Vm∈T 0 P ART (m) ≤ Vm∈T 00 P ART (m) because, due to the way the meet operation works, having at least as many tuples in T 0 makes the partition at least as coarse as the one corresponding to T 00. That is, we see that P 0 ≤ P 00; and from the assumption P 00 ≤ P 0 we get P 00 = P 0. Taken together, all our consequents prove that Γ MV Dcl(P ) = P 0.
(⇐) We prove that if Γ MV Dcl(P 0) = P , then X ⇒⇒ Y1| . . . |Yn holds in T . We use the same simple observation as in the rfist paragraph of the converse direction. Pick any model m ∈ T that satisefis X: we will prove that all the zeros of m are in the same Yi, and this implies that the MVD clause is true in T . This is not difficult now, since whenever m satisfies X all the singletons of P are also singletons of m, that is, P ≤ P ART (m), and because P ART (m) belongs obviously to the lattice, the closure of P , namely P 0 under our assumption, must also obey P 0 ≤ P ART (m). The only way for this to hold is that the only nonsingleton class of P ART (m) is fully included in one of the classes of P 0, that is, all the zeros of m are in one single Yi, and this implies that the MVD clause is true.
In fact, completely analogous theorems for DMVDs and MVDs, using the
corresponding closure operators instead, were proved in [
We define LMV Dcl(T ) as the set of closed partitions of attributes that are closed under Γ MV Dcl for T . Since Γ MV Dcl is a closure operator, the set LMV Dcl(T ) is closed under the operator meet. We have seen how to create a lattice to represent the MVD clauses that hold in a theory T and, as we previously mentioned, since the equivalence of a DMVD that holds in a relation and a MVDcl that holds in the binarization of that relation is direct, then we can conclude that the lattices generated by Γ MV Dcl and Γ DMV D must be the same.
Theorem 1 could have been proved instead by the following argumentation: By Proposition 1, we have that Γ MV Dcl generates the same set of closed partitions in BIN (r) as Γ DMV D in r. Then, to prove Theorem 1 we may also derive it from the following theorem, whose proof resorts heavily to our previous work: Theorem 2. Let P = {P1| . . . |Pn} be a partition of attributes. P = Γ MV Dcl(P ) ⇔ P = Γ DMV D(P ).
Proof. For this proof, we will use the Armstrong relation that can be derived
from a set of closed partitions as described in [
⇒) P = Γ MV Dcl(P ) implies that in the Armstrong relation for each Pi ∈ P there will be a pair of tuples that will only differ in Pi, and each pair will be different one from each other. It implies that if BIN is performed between the two tuples of each pair (otherwise it will result in a all zeros model), it will result in a binary model such that all the attributes in Pi will be set to zero, and the rest will be set to one. It induces a set of partitions such that all the attributes not in Pi will be singleton, and those in Pi will be in the same partition. Since it happens for all Pi ∈ P , the meet for all those partitions will be P , which proves that it will be closed under Γ DMV D.
⇐) P = Γ DMV D(P ) implies that for each Pi ∈ P that is not a singleton, there is a P 0 such that all the attributes are singleton except those that are in Pi. For all those models, it would imply that there is a pair of tuples that disagree only in Pi, which constitues a set of tuples that imply that P = Γ MV Dcl(P ).
Theorem 1 and the correspondence between MVD clauses and DMVD’s gives
us an alternative way to construct a lattice and derive the DMVDs of a relation
r: binarizing the tuples in r, and closing under meet the resulting partitions of
attributes. This process parallels that of the construction of Armstrong relations
for a set of FD’s [
Corollary 1. [P ART (BIN (r))]∧ = LMV Dcl(BIN (r)) = LDMV D(r).
We just proved that [P ART (BIN (r))]∧ = LDMV D(r), it is, that binarizing a
relation, then transforming these models into partitions of attributes and then
closing the resulting models under meet, the set of partitions of attributes so
constructed characterizes the DMVDs that hold in r. Our previous paper [
LDMV D(r).
Proof. Fixed r, we prove that if partition P is not in LDMV D(r) then P is not
in LMV D(r) either. We use the facts, proved in [
Our next result provides a postprocessing method that eliminates the appropriate models in BIN (r) to obtain the MVD lattice. The method consists of traversing the DMVD lattice top-down, and testing, for each node, the conditions stated in the theorem below; at that point, it is necessary to assume that all the nodes above the current node have been already tested, since we need for the proof the meet of all the nodes in the MVD lattice that sit above the node undergoing the test.
In fact, it is immediate to see that, upon considering a node P , if we take the meet of all the nodes above it in the MVD lattice, we obtain a node Q ≥ P which is, in fact, one of them due to the closure under meet; and, of course, to maintain the closure property, in case Q = P then P also belongs to the MVD lattice.
Thus, assume from now on that P < Q; since all nodes above P are already
correctly placed in the MVD lattice, we know that either P belongs to it, or its
closure is exactly Q. Thus, we consider a generalized dependency on the basis
of P and Q, and we know from [
Theorem 3. Let m ∈ BIN (r) and P = P ART (m), where P = {X1| . . . |Xn|Y } with X = X1 . . . Xn, and Q = {X1| . . . |Xn|Y1| . . . |Ym} is the meet of all the nodes above P in LMV D(r); assume P < Q. For each Yi, consider the related models m1 and m2: m1 has true the true variables of m and those corresponding to Yi, and m2 has all variables true except those in Yi. It holds that P ∈ LMV D(r) if and only if there is a Yi (with associated m1 and m2) and a pair of tuples t1 and t2 whose comparison results in m, for which there are no pairs t3 and t4 so that the comparisons of t1 with t3 and of t2 with t4 yield m1 and the comparisons of t1 with t4 and of t2 with t3 yield m2.
Proof. One direction is easy. If indeed there is Yi and the pair of tuples, then it
can be readily checked from the properties of m1 and m2 that this pair witness
that r 6|= X →→ Yi, so the generalized dependency constructed from P and Q
does not hold; it follows from the results in [
For the converse, in fact all the steps in the previous paragraph are “if and only if”, up to the point that r 6|= X →→ Yi However, this does not complete the proof since there could be pairs of tuples violating the dependency somewhere else: it remains to argue that t1 and t2 violating the implication can be picked so that their comparison is m. In fact we prove more: we prove that all these pairs are there. Fix any pair of tuples whose comparison gives m0 6= m: we will prove that they satisfy the conditions for X →→ Yi. Note that what we want to prove, that the X →→ Yi are satisefid for all Yi in this case, is the same as proving that the generalized dependency X →→ Y1| . . . |Ym is satisefid: it is the one that would correspond to P in case its closure was Q.
Since P = P ART (m) and X is the union of the singletons of P , that is, the ones of m, the result is immediate whenever m0 has a zero among these, because the pair of tuples would not satisfy the antecedent. Thus, we only need to consider m0 > m. Let P 0 = P ART (m0), which implies that P 0 has at most one class that is not a singleton and that P ≤ P 0, and suppose rfist that Q ≤ P 0. Then, Q being coarser, the zeros of m0 must be all in the same class in Q and the pair of tuples differ only in one class of Q, which implies that they trivially satisfy the generalized dependency.
Therefore, we suppose now that Q 6≤ P 0, that is, P ≤ P 0 ∧ Q < Q, which implies that P 0 ∈/ LMV D(r) since otherwise, due to the closure under meet, Q would not have been the meet of all the part of the MVD lattice above P . This implies that a dependency holds in r associated to P 0 and Γ MV D(P 0). Its left hand side X0 is formed by the singletons of P 0, which include those of P , say X1, . . . , Xk, and some more, say Xk+1, . . . , Xn; call the union of this set W = W1W2 according to whether they come from Yi or from its complement.
Regarding its right hand side, made up by the rest of the classes of Γ MV D(P 0), we know that P ≤ P 0 ≤ Γ MV D(P 0), which surely is in the MVD lattice, so that Q ≤ Γ MV D(P 0) by the denfiition of Q. Thus, we nfid that Yi is W1 (from the left hand side X0) union a union of classes of the right hand side. A pair of tuples corresponding to m0 must coincide in X1, . . . , Xn = XW1W2, and from the fact that the generalized dependency associated to P 0 holds we easily obtain the tuples needed to prove that the pair fullfils X →→ Yi as well.
According to this process we can identify one by one, proceeding from the top down, those nodes in LDMV D that must remain in LMV D and distinguish them from those that must be deleted to construct LMV D from LDMV D.