In this paper we present a new formal context for symmetric dependencies. We study its properties and compare it with previous approaches. We also discuss how this new context may open the door to solve some open problems for symmetric dependencies.
In database theory there are di erent types of dependencies, yet, two of them
appear to be the most popular: functional dependencies and multivalued
dependencies. The reason is that both dependencies come handy in order to explain
the normalization of a database scheme. But some of these dependencies are not
only con ned to the database domain. For instance, implications (the
equivalent of functional dependencies for binary data) are present in datamining and
learning ([
In general terms, a dependency states a relationship between sets of attributes in a table. Let us suppose that we have the following set of attributes: U = fname; income; ageg in a table that contains the following records: id Name Income Age 1 Smith 30.000 26-10-1956 2 Hart 35.000 14-02-1966 3 Smith 30.000 02-01-1964
In such a case, we have that the relationship between age and the attributes income and name is functional, this is, that given a value of age, the value of income and name can be determined. We also have that the value of name can be determined by income and viceversa. In such a case, given these functional relationships between the attributes, we say that the functional dependencies age ! fname; incomeg, name ! income and income ! name hold in that table.
Functional dependencies and multivalued dependencies have their own set
of axioms ([
These axioms, in turn, are also shared by other dependencies: implications
share the same axioms of functional dependencies ([
Since in this paper we are focusing on the syntactical properties of those dependencies, we will only talk of Armstrong and symmetric dependencies, rather than functional or multivalued dependencies.
The lattice characterization of a set of Armstrong dependencies has been
widely studied in [
The fact that some problems related to AD's have been solved using their lattice characterization, suggests that the same problems for SD's could also be solved using their corresponding lattice characterization. We name three of those problems already solved for AD's, not yet for SD's: learning SD's, the nding of a minimal basis for a set of dependencies for SD's and the characterization of mixed sets of SD's and AD's.
In general terms, query learning consists in deducing a function (a formula)
via membership queries to an oracle. This method has been used to learn sets
of Horn clauses, which can also be seen as implications ([
The minimal base (also: Duquenne-Guigues basis [
We have been dealing with unmixed sets of AD's and SD's, but there exists
an axiomatizations of mixed sets of AD's and SD's ([
Although AD's and SD's are related, the lattice characterization yielded by
the formal context in [
A second drawback is that the size of the formal context for SD's is much
larger, in comparison with that for AD's. This may cause a problem in case
the context is used in practical applications, but, more importantly, there are
partitions that play no r^ole in that characterization. A simple analysis of [
Finally, although partitions may be intuitive when dealing with SD's, they do
not re ect the B , :B symmetry of the de nition of symmetric dependencies
(as stated by Alan Day in [
As a step towards solving the learning problem and computation of a minimal
basis for SD's as well as the characterization of mixed sets of SD's and AD's, in
this paper we present a new formal context for symmetric dependencies, following
the work started in [
This paper starts with the Notation section, followed by a Previous Work section that explains the departing point of this paper. In the Results section, we present a new formal context for SD's. We also present an example in a separate section to illustrate the results. Finally, we discuss some aspects of this new formal context and present the conclusions and future work. 2
We depart from a set of attributes U . We use non capital letters for single elements of that set, starting with a; b; c; : : : , and capital letters for subsets of U .
The complement of a set X U is X. We drop the union operator and use juxtaposition to indicate set union. For instance, instead of X [ Y we write XY . Generally, we also drop the set notation, and write abc instead of f a; b; c g.
We de ne the powerset of a set U as }(U ). The set of partitions that can be
formed with U is Part(U ). The notation for a partition is P = [P1 j P2 j j Pn],
where Pi are the classes (subsets) of P . If needed, we indicate that the attributes
in a set X are in fact a set of singletons with this notation: X. For instance,
f a; b; c; d g = f f a g; f b g; f c g; f d g g. We overload P Q to indicate that a
partition P re nes a partition Q and P Q to indicate that P is coarser than
Q. More details of this (reversed) order can be found in [
As for Formal Concept Analysis, we use the usual notation ([
A symmetric dependency is a relation between two sets of attributes, and it is stated as X ) Y . Given a set of attributes U , we de ne SDU as the set of all symmetric dependencies that can be formed with U . Although they will only be mentioned in this paper, we say that X ! Y is an Armstrong dependency. Given a set of SD's SDU , we say that the closure of is +, and consists of plus the set of all SD's that can be derived from applying recursively the following axioms:
Because of complementation, we give a symmetric dependency as X ) Y j Z, where Z = XY . We always assume that the rightest set in the right-hand side of a symmetric dependency is the complementary of the union of the other two. However, sometimes we will state it explicitly, as in X ) Y j XY and sometimes we will simply use X ) Y j Z. In both cases, X is the left-hand side of the dependency, Y its rst right-hand side, and Z its second right-hand side. The set SDU is the set of all non-trivial symmetric dependencies that can be formed using all the attributes in U . By non-trivial we mean those SD's X ) Y j Z such that:
As it can be seen, according to the axioms for symmetric dependencies, this
limitation incurs in no loss of information, since the remaining symmetric
dependencies can easily be derived from SDU ([
It is precisely the complementation rule that states the relation between Armstrong dependencies and symmetric dependencies. Broadly speaking, we could say that a symmetric dependency X ) Y j Z is equivalent to the fact that either the Armstrong dependencies X ! Y or X ! Z hold. This is a too general statement, but if, as an example, we take, functional dependencies and its symmetric counterpart, degenerate multivalued dependencies, we see that the de nition of a functional dependency X ! Y states that whenever two tuples agree on X they also agree on Y , whereas the de nition of a degenerate multivalued dependency X ) Y j Z states that whenever two tuples agree on X they also agree on Y or they agree in Z. In fact, there are also a set of two axioms in the case we are dealing with mixed sets of AD's and SD's. One of this axioms state that if X ! Y holds, then, X ) Y j XY holds as well. This example is just to indicate that the relationship between AD's and SD's is strong, and that SD's can be as a generalization of AD's.
Given a set of symmetric dependencies , we say that the dependency
basis of a set of attributes X U (that is: DB (X)) is the coarsest partition
of U such that all the dependencies X ) Y j Z that hold in + are those such
that Y (symmetrically Z) is the union of one or more classes of DB(X). This
partition always exists ([
We also have that, since re exivity holds for SD's, all the attributes of X U are singletons in DB (X). 2.2
The origins of de ning a formal context to characterize the closure of a set of
Armstrong dependencies started in [
KAD(U ) = (ADU ; }(U ); I) where ADU is the set of Armstrong dependencies that can be formed with the set of attributes U , and I was a binary relation between an Armstrong dependency and a set of attributes.
In [
KSD(U ) = (SDU ; Part(U ); I0)
The relations I and I0 are generically called "respect" relations: a set of attributes (a partition) respects an Armstrong (symmetric) dependency.
Both formal contexts, in spite of its obvious structural di erences, characterized the closure of a set of dependencies of its kind. In fact, both contexts provided the following results for each respective kind of dependencies: 1. 2.
+ = 00. 0 is the lattice characterization of
+.
When we say that 0 was the lattice characterization of +, it may seem redundant, since we already have that + = 00. What we mean is that 0 alone, without the application of the operator 0, also characterized all the dependencies of +. This was done with the de nition of a closure operator on 0:
The fact that this function is total indicates that ^ is always de ned in 0. Depending on the formal context we were dealing with, we would have that X 2 }(U ) (AD's) or that X 2 Part(U ) (SD's). In the case of Armstrong dependencies, we would then have that X ! Y 2 + if and only if: 0 (X) = 0 (XY )
In the case of a symmetric dependency, it is a little bit more elaborated from a syntactical point of view, yet, equivalent to the previous case: X ) Y j Z 2 + if and only if: 0 ([X j Y Z]) = 0 ([X j Y j Z])
Clearly, 0 alone gives us the information of which dependencies are in + by querying the (closure) operator 0 . In both cases, and oversimplifying, we can say that a dependency holds in + if and only if there is some kind of relationship between its left-hand side and its right-hand side, being this relationship de ned by the formal context. 3
The results in this paper try to overcome the potential problems that may
represent the di ernet nature of the current formal contexts for AD's and SD's
(powerset versus partitions), as well as the larger size of a partition set, by
presenting a characterization of symmetric dependencies based on a formal context
whose set of attributes is the powerset of U instead of its partitions. This context
will generalize that for AD's in [
We de ne a formal context, and prove that it characterizes the set of
symmetric dependencies +, in a way similar to that in [
A + X or A
XY or A
XZ
We have that 0 }(U ). As a trivial consequence of De nition 3 we have the following proposition: Proposition 1. X ) Y j Z 2
00 if and only if 0 : A
X and A + XY and A + XZ
We now study the properties of this contexts and how they characterize +. We rst see that all the dependencies that are in + are also present in 00. To prove this claim, we must prove axiom by axiom that the dependencies derived by those axioms are also present in 00, but since re exivity and complementation are trivial, we only prove augmentation and transitivity.
Proposition 2 (Augmentation). If X ) Y j XY 2 XW ) Y W 0 j XW Y 2 00. , and W 0
W then, Proof. By the way of contradiction, we suppose that there is a set A such that (note that XW XY W = XW Y ) U ; A 2 0 A
XW and A + XW Y and A + XW Y
Since X ) Y j XY 2 , we have that A + X or A XY or A XY (because XXY = XY ). We have that A XW discards A + X. So, we only have two possible options: (i) A XY , which in combination with A
contradicts A + XW Y . (ii) A XY , which in combination with A contradicts A + XW Y .
XW yields A
XY W , which XW yields A
XW Y , which Proposition 3 (Transitivity). If X ) Y j XY 2 then, X ) Z n Y j X(Z n Y ) 2 . and Y ) Z j Y Z 2 Proof. By the way of contradiction, we suppose that there is A such that U ; A 2 0
X and A + X(Z n Y ) and A + XX(Z n Y )
We have to note that XX(Z n Y ) = X(Z n Y ), and that Z n Y = Y Z, we nally have that XX(Z n Y ) = XY Z. Therefore, we suppose that there is a set A U ; A 2 0 such that: (i) A X. (ii) A + X(Z n Y ). (iii) A + XY Z.
On the other hand, we have that: X ) Y j XY 2 implies that A + X or A XY or A XY .
Y ) Z j Y Z 2 implies that A + Y or A Y Z or A Y Z.
Since we are assuming that A X, we can discard A + X. We also have that the case A XY discards A + Y . This leaves three possibilities, either: (i) A XY and A Y Z, that is, A XY Z
A + X(Z n Y ). (ii) A XY and A Y Z, that is, A XY Z. This contradicts A + XY Z. (iii) A XY . Y \ Z = ; implies that Z n Y Y . All this yields A XY X(Z n Y ). This contradicts A + X(Z n Y ).
X(Z n Y ). This contradicts 00 contains, at least, all the symmetric 00 only contains all the depen
Therefore, we have proved that any dependencies that are in +.
+
Proof. We prove that X ) Y j Z 2= + implies that X ) Y j Z 2= 00.
We have that X ) Y j Z 2= +. It means that the dependency basis of X is such that in DB (X) = [X j P1 j j Pn] (with n 1) there is, at least, a class Pk such that Pk \ Y 6= ; and Pk \ Z 6= ;. We x Pk in this proof. We note that jPkj 2, since it contains, at least, one attribute from Y and one from Z.
n Let P = (SPj )nPk, that is, P is the union of all partitions in DB (X) which j=1 are not X, except Pk. Therefore, XP = Pk. We now claim that XP 2 0. We prove this statement by the way of contradiction. Assume that XP 62 0. That is because there is a dependency R ) S j T 2 such that X R and X + RS and X + RT . This implies that there is, at least, one attribute in RS which is not i XP , and, at least, one attribute in RT which is not in XP . Let them be s 2 RS; s 62 XP and t 2 RT; t 62 XP . Since X R, then, s 2 S; s 62 XP and t 2 T; t 62 XP . Necessarily, since s; t 62 XP , then, s; t 2 Pk.
Since XP R, by re exivity, XP ) R j XP R, and by transitivity, XP ) S n R j XP (S n R). Without lack of generality, we assume that R; S; T are disjoint, so, nally, we have XP ) S j XP S. By the de nition of DB (X), then, X ) P j XP , and by transitivity, we have X ) S n XP j X(S n XP ). Since s 2 S; s 62 XP , then, s 2 S n XP , and since t 2 T (assuming R; S; T disjoint), t 62 S, that, together with t 62 XP yields that t 2 X(S n XP ). It means that the attributes s; t are in di erent classes in DB (X), but this contradicts the previous assumption that Pk 2 DB (X).
Now, we have that XP 2 0. Since s; t 62 XP , we have that XP + XY and XP + XZ and XP X, which implies X ) Y j Z 62 00.
We have that 00 is exactly the set +. But, as we have already discussed
in the previous section, in [
SDU . We de ne the up-set of X
U P (X) = f Y 2 0 j Y
X g
This de nition is the standard one in lattice theory ([
X and Z
X.
U P (X) = U P (Y ) [ U P (Z) if and only if
X and A + Y and A + Z
We need to remark that, although the set 0 may not be closed under set intersection, the set of all up-sets of 0 is closed under intersection. We are now ready to prove that it can be tested whether a dependency is in + querying 0 alone: Proposition 5. X ) Y j Z 2
+ if and only if
U P (X) = U P (XY ) [ U P (XZ) Proof. if and only if (by Corollary 1 and Theorem 1)
X ) Y j Z 2 X ) Y j Z 2 + 00 if and only if (by Proposition 1) if and only if (by Proposition 4)
X and A + XY and A + XZ
U P (X) = U P (XY ) [ U P (XZ)
We provide a running example in order to illustrate and clarify the results that are contained in the previous section. We depart from a set of attributes U = f a; b; c; d g. The resulting formal context is presented in Figure 1.
As stated in Theorem 1, this contexts computes the set +. For instance, let us take the set
= fa ) b j cd; b ) ad j cg According to this context, we have that
0 = fc; d; bc; cd; abc; abd; acd; bcd; abcdg and, nally, + = fa ) b j cd; b ) ad j c; a ) c j bd; a ) d j bc;
ab ) c j d; ac ) b j d; ad ) b j c; bd ) a j cg
To check these results, we see that ac ) b j d, ad ) b j c and bd ) a j c are derived from by the re exivity, transitivity and complementation. For instance, given a ) b j cd, by re exivity we have ac ) a j bd, and by transitivity ac ) b j d (complementation comes from the notation X ) Y j Z used in this paper). Dependencies ad ) b j c and bd ) a j c can be derived alike.
As for the remaining SD's:
a ) c j bd; a ) d j bc by applying transitivity to a ) b j cd and b ) ad j c, we obtain a ) c j bd, and with complementation we have a ) d j bc. a ) b j cd b ) a j cd a ) c j bd c ) a j bd a ) d j cb d ) a j cb b ) c j ad c ) b j ad b ) d j ac d ) b j ac c ) d j ab d ) c j ab ab ) c j d ac ) b j d bc ) a j d ad ) b j c bd ) a j c cd ) a j b
Fig. 1. Formal context (SDU ; }(U); I) for U = f a; b; c; d g
We now present an example with one more attribute, which may provide more insight in the details, but in this case, we do not present the context explicitly. The set of attributes is now U = f a; b; c; d; e g. Let be the set of symmetric dependencies: b ) a j cde b ) c j ade c ) a j bde c ) b j ade d ) a j bce d ) e j abc e ) a j bcd e ) d j abc According the formal context (SDU ; }(U ); I ), we have that:
0 = f a; abc; ade; abcd; abce; abde; acde; bcde; abcde g
We can see that, applying the axioms of symmetric dependencies in De nition 1, the set + is: b ) a j cde b ) c j ade c ) a j bde c ) b j ade d ) a j bce d ) e j abc e ) a j bcd e ) d j abc abd ) c j e acd ) b j e ce ) a j bd de ) a j bc bcd ) a j e abe ) c j d ace ) b j d bce ) a j d bde ) a j c cde ) a j b ab ) c j de ac ) b j de ad ) bc j e ae ) bc j d bc ) a j de bd ) ac j e bd ) a j ce bd ) ae j c be ) ac j d be ) ad j c be ) a j cd cd ) a j be cd ) ae j b cd ) ab j e ce ) ab j d ce ) ad j b
We only state the non-trivial dependencies as in De nition 2. We take, for instance, the dependencies:
bd ) ac j e; bd ) a j ce; bd ) ae j c
They are derived from the dependencies b ) a j cde and b ) c j ade. They are in + because the sets that include bd are abcd; abde; bcde; abcde. This obviously means that all of them respect all the dependencies in +. We take, for instance, the set abcd and see that it respects bd ) ae j c because abcd bcd (the lefthand side plus the second right-hand side) and that it also respects bd ) a j ce because abcd abd (the left-hand side plus the rst right-hand side). We can see in this example the duality of the de nition of the relation respect. This is one case of derivation by augmentation, which means that the dependencies that derive another dependency remove the sets that would prevent the derived dependency from appearing in 00. In this latter particular case, the sets that could be forbitting any of these dependencies from appearing in 00 have been cleared by b ) a j cde and b ) c j ade. We take, for instance, the set bde, (which would prevent bd ) a j ce from being in 00) is not in 0 because it does not respect the dependency b ) a j cde.
We now illustrate one case of derivation by transitivity with the following set:
a ) bc j de; bc ) d j ae
By transitivity, we have that a ) d j bce 2 we have: +. If we take = f a ) bc j de g, 0 = fb; c; d; e; bc; bd; be; cd; ce; de; abc; ade; bcd; bce; bde; cde; abcd; abce; abde; acde; bcde; abcdeg
It is clear that a ) d j bce 2= 00 since the sets abc; acde 2 this dependency. Now, if we include bc ) d j ae in , we have: 0 do not respect 0 = f b; c; d; e; bd; be; cd; ce; de; ade; bcd; bde; cde; abcd; abce; abde; acde; bcde; abcde g
It has precisely been the dependency bc ) d j ae the one that has cleared both abc and acde from 0 and, therefore, allows a ) d j bce to appear in 00.
We now illustrate how 0 alone can be used to query what dependencies hold in +. Again, we have that is the set: b ) a j cde b ) c j ade c ) a j bde c ) b j ade d ) a j bce d ) e j abc e ) a j bcd e ) d j abc and, therefore: 0 = f a; abc; ade; abcd; abce; abde; acde; bcde; abcde g
We can see that 0 in not closed (abcd; abde 2 0, but ab 2= 0 ). Now, suppose that we want to test whether a dependency is in +. For instance, we take a dependency that is not in +, as a ) bc j de and query 0: U P (a) = f a; abc; ade; abcd; abce; abde; acde; abcde g U P (abc) = f abc; abcd; abce; abcde g U P (ade) = f ade; abde; acde; abcde g
According to Proposition 5, since the sets U P (a) and U P (abc)[U P (ade) do not coincide, then, this dependency does not hold in +. We see that the set that does not allow this equality to hold is the set a, which is in 0 because all dependencies in are respected by this set. We take now a positive example of a dependency that is in + but not in , as for instance ab ) c j de: U P (ab) = f abc; abcd; abce; abde; abcde g U P (abc) = f abc; abcd; abce; abcde g U P (abde) = f abde; abcde g
In this case, the sets U P (ab) and U P (abc) [ U P (abde) coincide. 5
We have seen in Section 2 that the di erent characterizations of dependencies
with formal contexts follow a common pattern, regardless of the type of
dependencies or the de nition of the context. Yet, the de nition of formal contexts for
AD's and SD's as in [
Now, we have that the relation I is a generalization of the relation de ned
in the context KAD(U ) = (ADU ; }(U ); I). We recall the de nition of this relation
([
A + X or A
XY
We see that this de nition avoids the reference to the second right-hand side, precisely because in AD's, complementation does not hold. If we drop this part from De nition 3, we have the de nition of the respect relation for Armstrong dependencies.
This generalization seems to suggest that the solutions that have been developed based on the lattice characterization of sets of Armstrong dependencies, may also be applied to symmetric dependencies, namely: 1. To de ne a formal context for mixed sets of AD's and SD's. 2. To adapt the classical query algorithm for learning Armstrong dependencies. 3. To characterize the generating set of a set of symmetric dependencies.
Yet, although we are now in a better position to attack those problems, it does not seem to be a trivial task. For instance, the intuition would tell us that de ning a formal context for mixed sets of dependencies, such that the relation would be the union of the relations already de ned for AD's and SD's would work, but this is not the case. In fact, although this is out of the scope of this paper, this mixed formal contexts characterizes the symmetric dependencies that are in +, where is a mixed set of AD's and SD's, but fails in characterizing the AD's that are in +. However, this simple strategy allows to advance towards the de nition of a mixed formal context, which would have not been that simple departing from a partition context.
Adapting the classic learning algorithm for learning AD's and the characterization of the generating set of a set of SD's may encounter some di culties. The main di erence between 0 for Armstrong and symmetric dependencies is that for the former, 0 is always a powerset lattice closed under intersection, whereas for symmetric dependencies, this is not necessarily the case, and, therefore, not all the existing solutions for Armstrong dependencies, based on lattices, may be applied out of the box to symmetric dependencies. Yet, the fact that now we are dealing with contexts of the same nature, o ers a much clearer perspective and understanding than before.
It must be said too that whereas this new characterization may make it potentially easier to nd methods for nding minimal basis and query learning for SD's, it is true that SD's have not yet been used outside the database domain. We think that advancing in the study of lattice characterization for SD's and nding algorithmic similarities with FD's may introduce the use of SD's in other domains, namely knowledge discovery and machine learning, or in database theory, where it is already present: it would be of interest to have algorithms to compute minimal basis for SD's, pro ting from the important collection of algorithms that compute the minimal basis of a set of AD's.
Finally, we would like to remark that the size of the formal context is greatly
improved w.r.t the context in [
We have presented a new formal context for symmetric dependencies. This contexts provides the same functionalities as previous approaches, and it is much simpler. Yet, it o ers the same expressivity power and, in fact, reduces the conceptual gap between Armstrong and symmetric dependencies that existed in a previous approach. We strongly believe that this may be the rst step towards the resolution via formal concept analysis, of the learning, minimal bases and mixed sets of dependencies problems for symmetric dependencies, pro ting from solutions already existing for Armstrong dependencies.