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 ( [7], [8], [14], [18], [19]).
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: first, 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 [18], [19].
Recent progresses in [3] makes it appropriate to revisit the somewhat unsatisfactory results in [6], trying to obtain a better understanding of the comparisonbased binarization. We considered there MVD clauses and stated a restricted form of closure under intersection that characterizes the theories axiomatized by such clauses in a form similar to Horn clauses (a full proof can be found in [4]); whereas that result gave a clear characterization for these propositional theories, it did not provide a lattice form due to the fact that, sometimes, the intersection operation may not be of the restricted form that ensures remaining within the theory. Likewise, the lattice form for MVDs did not consist only of propositional models, but they were labeled with the specific pairs of original tuples that gave rise to them, and the intersection had to be extended to the label through a sort of join.
Thanks to the additional knowledge obtained in [1], [2] and [3], we are now able to refine these facts into somewhat more satisfactory lattice-theoretic characterizations. Indeed, the purpose of this paper is twofold: on one hand, to provide a lattice-theoretic characterization of a set of MVD clauses that hold in a propositional theory; it generalizes that of [6] and parallels that of [5] for Horn clauses. On the other hand, to clarify the relationship between MVD lattices and MVD clauses for a larger-than-two-tuples world, by exactly identifying the nodes that must be removed from the binarization in order to get the lattice corresponding to MVDs. This result complements the discussion started in [18] about the fragment of propositional logic induced by MVDs; provides a new method to characterize the set of MVDs that hold in a relation; and contributes a new view of how close the MVD lattice is to the DMVD lattice, with the precise understanding of where the difference lies. We expect this progress to allow for further advances in the study of binary representations for more sophisticated dependencies that fully lack, so far, lattice-theoretic characterizations. A global longer-term aim guiding this research is to elucidate whether there are deep implications between two properties of dependencies, seen in a general view: some of them have Armstrong relations, others do not; and some of them admit lattice-theoretic characterizations, whereas it appears like others do not. We believe that these two properties have a deep interconnection that is worth to investigate and bring into light.
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 = {t 1 , t 2 . . . t n } 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 = {m 1 , m 2 . . . m n } 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.
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 (m i ) that results from a model m i is the partition of R such that each attribute that has a true value in m i , forms a singleton class, and all the attributes with false value are together in the same class.
For instance, if m i = {11001}, then P ART (m i ) = {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 finest partition that is coarser than both, so that the partial ordering associated to the lattice is the natural ordering where P ≤ P whenever P is finer than P . More details on alternative ways to define the meet operation can found in [3].
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 ∧.
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.
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:
where X → Y can be a DMVD, a MVD or a MVD clause. For a proof of these properties the reader can refer to [21] or [2]. For each left-hand side of a MVDcl, a DMVD or a MVD, we can define its dependency basis as follows: Definition 8. Given a theory T (a relation r), the MVDcl dependency basis (DMVD dependency basis, MVD dependency basis) for a set of attributes X, DEP (X), is a partition of the set of attributes such that for all MVDcl (DMVD, MVD) that have X in their left hand side, they hold in T (in r) if and only if their right hand side may be formed by the union of classes of DEP (X).
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)
In [2] and [3], we defined closure operators on partitions, characterizing all the DMVDs (MVDs respectively) that hold in a relation; the characterizations have the same overall form as Theorem 1 below. They also were proved to derive Armstrong relations for that set of DMVDs (MVDs). An Armstrong relation for a set of dependencies is a relation such that all those dependencies hold in this relation, as well as all the dependencies that are a logical consequence of this set, but the rest of dependencies do not hold. It can be used as an alternative way to characterize a set of dependencies. In this present paper, those closure operators will be called Γ DM V D and Γ M V D respectively.
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 [2] and [3]): we say that a partition of attributes P = {P 1 |P 2 | . . . |P n } matches a set of tuples C (when modelling a set of DMVDs) if all the tuples in C differ only in one class of attributes. If this same partition is considered to be modelling a set of MVDs, we say that P matches a set of tuples C if C = P r(P 1 , C) × P r(P 2 , C) × • • • × P r(P n , C), where P r(X, C) is the projection of C on the attributes X, that is, the set of all tuples obtained from C by removing the values corresponding to attributes not in X.
It is easy to prove that, given a relation r, a DMVD X → → Y holds in r if and only if the syntactically equivalent MVDcl X ⇒ ⇒ Y holds in BIN (r), as the next proposition states:
According to this result, and due to the fact that the operator Γ DM V D as defined in [2] provides a complete characterization of a set of DMVDs, the lattice that characterizes the MVD clauses that hold in BIN (r) must be the same. However, given a theory T whose lattice we wish to construct, we would need to start by going back into a relation r such that BIN (r) = T and operate on the DMVDs of r; and care must be to make sure that BIN (r) does not produce additional models. We deem useful to provide a construction of the lattice that goes on directly from T , by means of a new closure operator appropriate to work on models. We indeed provide now an operator that, given a theory, calculates a lattice that characterizes the set of all MVD clauses that hold in that theory, which is the following: Definition 10. Fix a theory T . Let Γ M V Dcl : ℘ → [P ART (T )] ∧ a map such that given a partition of attributes P , returns a partition of attributes P such that P ≤ P and for all P ∈ [P ART (T )] ∧ , if P ≤ P ≤ P implies that P = P .
Note that it is well-defined since P ≤ P and P ≤ P implies that P ≤ P ∧ P , and the codomain is closed under meet.
Proof. We prove the three axioms for closure operators.
1. P ≤ Γ M V Dcl (P ). Obvious since Γ M V Dcl always returns a P ∈ [P ART (T )] ∧ such that P ≤ P . 2. Γ M V Dcl (P ) = Γ M V Dcl (Γ M V Dcl (P )). Let P = Γ M V Dcl (P ) and, besides, Q = Γ M V Dcl (P ) so that P ≤ Q. For all P ∈ [P ART (T )] ∧ , P ≤ P ≤ Q implies that P = Q, and since P ∈ [P ART (T )] ∧ and P ≤ P ≤ Q, we have that Q = P . 3. P ≤ P ⇒ Γ M V Dcl (P ) ≤ Γ M V Dcl (P ). Since P ≤ P , we have that P ≤ Γ M V Dcl (P ), and also P ≤ Γ M V Dcl (P ). We then have that
By the closure under meet, Γ M V Dcl (P ) ∧ Γ M V Dcl (P ) ∈ [P ART (T )] ∧ ; by the last condition of the definition, we get Γ M V Dcl (P ) ∧ Γ M V Dcl (P ) = Γ M V Dcl (P ) or, equivalently, Γ M V Dcl (P ) ≤ Γ M V Dcl (P ) as desired.
Note that P ART (m i ) 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 Γ M V Dcl characterizes all the MVD clauses that hold in a theory T :
. . Y m } we have that Γ M V Dcl (P ) = P , where the X j are the attributes in X.
We first note that the fact that a generalized MVD clause X ⇒ ⇒ Y 1 | . . . |Y m holds in T means that these Y i 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 ⇒ ⇒ Y i ∨ Y , where Y stands for the union of the remaining classes of attributes. This implies that all the zeros of the model are in the same class Y i , 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 Y i , then T satisfies the dependency clause.
We must prove that
∧ , and that no other partition in [P ART (T )] ∧ exists in between P and P . Consider the theory T = {m ∈ T m |= X}, and let Q = m∈T P ART (m). Clearly all X i are singletons in all P ART (m) form m ∈ T , and, as just described, all of them have their zeros (the only nonsingleton in P ART (m)) included in one of the Y i 's, so that for all such m we have P ≤ P ART (m), and the properties of the meet ensure P ≤ m∈T P ART (m) = Q. We argue that actually P = Q so that indeed P ∈ [P ART (T )] ∧ : assume that P < Q, that is, some class Y i of P is split in Q into more than one class. Fix two attributes A and B that belong to Y i that are in different classes of Q, say Z A and Z B respectively; from P ≤ Q as just proved, Z A ∪ Z B ⊆ Y i . Noting the definition of Q, we see that no model in T has zeros both in Z A and in Z B , 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 ⇒ ⇒ Z A is true in T , and Z A should be obtained as a union of Y i 's, which is not the case. Therefore P = Q, so that P ∈ [P ART (T )] ∧ .
It remains to prove that there is no other partition P ∈ [P ART (T )] ∧ with P ≤ P ≤ P , except, of course, for P itself, and this will imply that Γ M V Dcl (P ) = P , as we wish. Assume P ∈ [P ART (T )] ∧ , and let T ⊆ T such that P = m∈T P ART (m). Again all the X i must be singletons in P due to P ≤ P , which means that the models in T satisfy X, or, equivalently, T ⊆ T . It is immediate to see, then, that m∈T P ART (m) ≤ m∈T P ART (m) because, due to the way the meet operation works, having at least as many tuples in T makes the partition at least as coarse as the one corresponding to T . That is, we see that P ≤ P ; and from the assumption P ≤ P we get P = P . Taken together, all our consequents prove that Γ M V Dcl (P ) = P .
(⇐) We prove that if Γ M V Dcl (P ) = P , then X ⇒ ⇒ Y 1 | . . . |Y n holds in T . We use the same simple observation as in the first paragraph of the converse direction. Pick any model m ∈ T that satisfies X: we will prove that all the zeros of m are in the same Y i , 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 under our assumption, must also obey P ≤ 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 , that is, all the zeros of m are in one single Y i , 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 [2] and [3] respectively.
We define L M V Dcl (T ) as the set of closed partitions of attributes that are closed under Γ M V Dcl for T . Since Γ M V Dcl is a closure operator, the set L M V 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 Γ M V Dcl and Γ DM V D must be the same.
Theorem 1 could have been proved instead by the following argumentation: By Proposition 1, we have that Γ M V Dcl generates the same set of closed partitions in BIN (r) as Γ DM V 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:
Proof. For this proof, we will use the Armstrong relation that can be derived from a set of closed partitions as described in [2].
⇒) P = Γ M V Dcl (P ) implies that in the Armstrong relation for each P i ∈ P there will be a pair of tuples that will only differ in P i , 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 P i 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 P i will be singleton, and those in P i will be in the same partition. Since it happens for all P i ∈ P , the meet for all those partitions will be P , which proves that it will be closed under Γ DM V D .
⇐) P = Γ DM V D (P ) implies that for each P i ∈ P that is not a singleton, there is a P such that all the attributes are singleton except those that are in P i . For all those models, it would imply that there is a pair of tuples that disagree only in P i , which constitues a set of tuples that imply that P = Γ M V 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 [15] and that of constructing an Armstrong relation for a set of DMVDs in [2].
We just proved that [P ART (BIN (r))] ∧ = L DM V 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 [2] provided such a construction by a Galois connection operating on partitions and relying strongly on the "matching" condition defined before: now we see that binarization offers a different, more natural way for both obtaining the set of DMVDs that hold in a relation and performing the implication test for DMVDs. Equipped with these facts, we move now to the most relevant notion, MVDs proper: in this section we compare L M V D (r) and [P ART (BIN (r))] ∧ . First consider the possibility of having an equivalence of the form L M V D (r) = [P ART (BIN (r))] ∧ . This correspondence holds in relations were the sets of attributes that have some values in common are reduced to sets of two tuples (a two-tuples world) as it is proved in [19]. Proposition 3 next states that the MVD lattice is actually included in the DMVD lattice; therefore, if the inclusion is an equality, then the equality [P ART (BIN (r))] ∧ = L M V D holds, otherwise, it does not.
Proposition 3. Let r be a relation, and let L DM V D (r) and L M V D (r) the lattices that characterize the DMVDs and MVDs respectively that hold in r. Then,
Proof. Fixed r, we prove that if partition P is not in L DM V D (r) then P is not in L M V D (r) either. We use the facts, proved in [2] and [3] respectively, that parallel theorem 1 for DMVDs and MVDs: each application of the corresponding closure operator to a partition P that gives a different partition corresponds to a DMVD, respectively MVD, that holds in the relation given. If P / ∈ L DM V D (r) then a nontrivial degenerate multivalued dependency with singletons from P as left hand side holds in r; as indicated just after the definition, if the degenerate multivalued dependency holds then its syntactically equivalent multivalued dependency holds as well; the syntactical equivalence implies that its left hand side is the same and therefore singletons of P , so that the closure operator for MVDs also maps P into a different partition and thus P is not closed in L M V D (r) either.
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 [3] that P is in the lattice if and only if the dependency does not hold. Namely, assuming that
}, P must be removed from the lattice if and only if r |= X → → Y i for each i. We prove that considering information local to P and Q suffices. if and only if there is a Y i (with associated m 1 and m 2 ) and a pair of tuples t 1 and t 2 whose comparison results in m, for which there are no pairs t 3 and t 4 so that the comparisons of t 1 with t 3 and of t 2 with t 4 yield m 1 and the comparisons of t 1 with t 4 and of t 2 with t 3 yield m 2 .
Proof. One direction is easy. If indeed there is Y i and the pair of tuples, then it can be readily checked from the properties of m 1 and m 2 that this pair witness that r |= X → → Y i , so the generalized dependency constructed from P and Q does not hold; it follows from the results in [3] that Q cannot be the closure of P . But Γ M V D (P ) is in the MVD lattice and, if it was above P , the definition of Q would imply P < Q < Γ M V D (P ) which contradicts the properties of the closure operator. Thus the only possibility is Γ M V D (P ) = P so that P ∈ L M V D (r).
For the converse, in fact all the steps in the previous paragraph are "if and only if", up to the point that r |= X → → Y i However, this does not complete the proof since there could be pairs of tuples violating the dependency somewhere else: it remains to argue that t 1 and t 2 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 m = m: we will prove that they satisfy the conditions for X → → Y i . Note that what we want to prove, that the X → → Y i are satisfied for all Y i in this case, is the same as proving that the generalized dependency X → → Y 1 | . . . |Y m is satisfied: 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 m has a zero among these, because the pair of tuples would not satisfy the antecedent. Thus, we only need to consider m > m. Let P = P ART (m ), which implies that P has at most one class that is not a singleton and that P ≤ P , and suppose first that Q ≤ P . Then, Q being coarser, the zeros of m 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 ≤ P , that is, P ≤ P ∧ Q < Q, which implies that P / ∈ L M V 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 and Γ M V D (P ). Its left hand side X is formed by the singletons of P , which include those of P , say X 1 , . . . , X k , and some more, say X k+1 , . . . , X n ; call the union of this set W = W 1 W 2 according to whether they come from Y i or from its complement.
Regarding its right hand side, made up by the rest of the classes of Γ M V D (P ), we know that P ≤ P ≤ Γ M V D (P ), which surely is in the MVD lattice, so that Q ≤ Γ M V D (P ) by the definition of Q. Thus, we find that Y i is W 1 (from the left hand side X ) union a union of classes of the right hand side. A pair of tuples corresponding to m must coincide in X 1 , . . . , X n = XW 1 W 2 , and from the fact that the generalized dependency associated to P holds we easily obtain the tuples needed to prove that the pair fulfills X → → Y i as well.
According to this process we can identify one by one, proceeding from the top down, those nodes in L DM V D that must remain in L M V D and distinguish them from those that must be deleted to construct L M V D from L DM V D .