=Paper=
{{Paper
|id=None
|storemode=property
|title=A New Formal Context for Symmetric Dependencies
|pdfUrl=https://ceur-ws.org/Vol-959/paper23.pdf
|volume=Vol-959
|dblpUrl=https://dblp.org/rec/conf/cla/Baixeries11
}}
==A New Formal Context for Symmetric Dependencies==
https://ceur-ws.org/Vol-959/paper23.pdf
A New Formal Context for Symmetric
Dependencies
Jaume Baixeries
Departament de Llenguatges i Sistemes Informàtics.
Universitat Politècnica de Catalunya.
08024 Barcelona. Catalonia.
jbaixer@lsi.upc.edu
Abstract. In this paper we present a new formal context for symmet-
ric 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.
1 Introduction and Motivation
In database theory there are different types of dependencies, yet, two of them
appear to be the most popular: functional dependencies and multivalued depen-
dencies. 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 confined to the database domain. For instance, implications (the equiva-
lent of functional dependencies for binary data) are present in datamining and
learning ([4,19,20]).
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 =
{name, income, age} 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 → {name, income}, name → income and income → name hold in that
table.
Functional dependencies and multivalued dependencies have their own set
of axioms ([9,21]), which state what dependencies hold in the presence of other
dependencies. For instance, an axiom for functional dependencies states that
2 Baixeries J.
transitivity holds, which means that, in the previous case, if we had that name →
income and income → age hold in that table (which is not true in that table,
but just as a supposition), it must follow necessarily that name → age holds.
Given a set of dependencies Σ, we define as Σ + the set of all dependencies that
hold according to those axioms.
These axioms, in turn, are also shared by other dependencies: implications
share the same axioms of functional dependencies ([4]), and degenerate multi-
valued dependencies share the same axioms of multivalued dependencies ([5]).
That is why we generically call Armstrong Dependencies (AD) those dependen-
cies that share the same axioms of the former, and Symmetric Dependencies
(SD) those that share the axioms of the latter.
Since in this paper we are focusing on the syntactical properties of those de-
pendencies, 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 [10,11,13,14,15], and their characterization with a formal con-
text in [7,17]. However, the lattice characterization of symmetric dependencies
has not been so widely studied. The main work is in [12], and the character-
ization of symmetric dependencies with a formal contexts was studied in [3,5]
(we talk indistinctly of a lattice characterization and a characterization with a
formal context). In the case of AD’s, the formal context yields a powerset lattice
([17]), whereas in the case of symmetric dependencies, it yields a partition lattice
([3]).
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 finding
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 ([8]), or, more generally,
sets of Armstrong dependencies. Thus, the same general algorithm for learning
Horn clauses ([1]) has been adapted to learn Armstrong dependencies ([2]). This
adaptation was obviously easied by the fact that Horn clauses and Armstrong
dependencies share the same set of axioms. Yet, no such algorithm for symmetric
dependencies exists (to the best of the author’s knowledge).
The minimal base (also: Duquenne-Guigues basis [16]) is the minimal set
of Armstrong dependencies needed to compute Σ + . In [11], [16] and [17] it is
characterized and computed in terms of the (powerset) lattice characterization
of Σ + .
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 ([21]), but no lattice
characterization of mixed sets.
A New Formal Context for Symmetric Dependencies 3
Although AD’s and SD’s are related, the lattice characterization yielded by
the formal context in [3] is quite different in nature to that for AD’s. Potentially,
it may pose different problems. The first is that the solutions that have been
found for AD’s (based on their lattice characterization) may not be applied
directly to the case of SD’s. We do not mean that having AD’s characterized
with a powerset lattice and SD’s with a partition lattice makes it impossible
to solve the same problems for SD’s. What we mean is that having a similar
characterization for SD’s would make it easier to try and find an answer using
existing solutions for AD’s.
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ôle in that characterization. A simple analysis of [3]
yields that partitions that contain no singleton are completly useless, but a
more detailed analysis (out of the scope of this paper) indicates that there are
more redundant partitions.
Finally, although partitions may be intuitive when dealing with SD’s, they do
not reflect the B ⇔ ¬B symmetry of the definition of symmetric dependencies
(as stated by Alan Day in [12]). It seems that the connection between AD’s and
SD’s is stronger than what the partition lattice characterization suggests.
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 [3]. The results presented in this paper parallel those results,
but from a different perspective that, we think, improve both the understanding
and the possibilities to solve the open problems previously listed.
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 Notation
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 { a, b, c }.
We define 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 | P2 | · · · | 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,
{ a, b, c, d } = { { a }, { b }, { c }, { d } }. We overload P ≥ Q to indicate that a
4 Baixeries J.
partition P refines a partition Q and P ≤ Q to indicate that P is coarser than
Q. More details of this (reversed) order can be found in [18].
As for Formal Concept Analysis, we use the usual notation ([17]), which
includes the use of 0 as the (overloaded) function that relates the set of attributes
and that of objects and viceversa.
2.1 Symmetric Dependencies
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 define 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:
Definition 1 (Axioms for SD’s).
1. Reflexivity: If Y ⊆ X, then, X ⇒ Y holds.
2. Complementation: If X ⇒ Y holds, then, X ⇒ XY holds.
3. Augmentation: If X ⇒ Y holds and W 0 ⊆ W ⊆ U, then, XW ⇒ Y W 0 holds.
4. Transitivity: If X ⇒ Y and Y ⇒ Z hold, then, X ⇒ Z \ Y holds.
Because of complementation, we give a symmetric dependency as X ⇒ Y | 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 | XY and sometimes
we will simply use X ⇒ Y | Z. In both cases, X is the left-hand side of the
dependency, Y its first 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 | Z
such that:
Definition 2. A symmetric dependency X ⇒ Y | Z is non-trivial if:
1. X ∪ Y ∪ Z = U.
2. X ∩ Y = X ∩ Z = Y ∩ Z = ∅.
3. X 6= ∅, Y 6= ∅, Z 6= ∅.
As it can be seen, according to the axioms for symmetric dependencies, this
limitation incurs in no loss of information, since the remaining symmetric de-
pendencies can easily be derived from SDU ([21]).
It is precisely the complementation rule that states the relation between Arm-
strong dependencies and symmetric dependencies. Broadly speaking, we could
say that a symmetric dependency X ⇒ Y | Z is equivalent to the fact that either
the Armstrong dependencies X → Y or X → Z hold. This is a too general state-
ment, but if, as an example, we take, functional dependencies and its symmetric
A New Formal Context for Symmetric Dependencies 5
counterpart, degenerate multivalued dependencies, we see that the definition of a
functional dependency X → Y states that whenever two tuples agree on X they
also agree on Y , whereas the definition of a degenerate multivalued dependency
X ⇒ Y | 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 | 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 | 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 ([21]) and defines all the symmetric dependencies that
hold in Σ + such that their left-hand side is X.
We also have that, since reflexivity holds for SD’s, all the attributes of X ⊆ U
are singletons in DBΣ (X).
2.2 Previous Work
The origins of defining a formal context to characterize the closure of a set of
Armstrong dependencies started in [17]. This formal context was defined as:
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 [3], it was presented a formal context for symmetric dependencies with
identical properties:
KSD (U) = (SDU , Part(U), I 0 )
The relations I and I 0 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 differences, charac-
terized 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. Σ + = Σ 00 .
2. Σ 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 definition of a closure operator on Σ 0 :
6 Baixeries J.
^
ΓΣ 0 (X) = { Y ∈ Σ0 | Y ⊇ X }
The fact that this function is total indicates that ∧ is always defined in Σ 0 .
Depending on the formal context we were dealing with, we would have that
X ∈ ℘(U) (AD’s) or that X ∈ Part(U) (SD’s). In the case of Armstrong depen-
dencies, we would then have that X → Y ∈ Σ + 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 | Z ∈ Σ +
if and only if:
ΓΣ 0 ([X | Y Z]) = ΓΣ 0 ([X | Y | 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 defined
by the formal context.
3 Results
The results in this paper try to overcome the potential problems that may rep-
resent the differnet 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 pre-
senting 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 [17] as it will seen in Section 5.
We define a formal context, and prove that it characterizes the set of sym-
metric dependencies Σ + , in a way similar to that in [3]: (SDU , ℘(U), I ), where
the relation I is defined as follows:
Definition 3. A ⊆ U respects a symmetric dependency X ⇒ Y | Z (that is:
X ⇒ Y | Z I A) if and only if:
A + X or A ⊇ XY or A ⊇ XZ
We have that Σ 0 ⊆ ℘(U). As a trivial consequence of Definition 3 we have
the following proposition:
Proposition 1. X ⇒ Y | Z ∈ Σ 00 if and only if
@A ∈ Σ 0 : A ⊇ X and A + XY and A + XZ
A New Formal Context for Symmetric Dependencies 7
We now study the properties of this contexts and how they characterize Σ + .
We first 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 reflexivity and complementation
are trivial, we only prove augmentation and transitivity.
Proposition 2 (Augmentation). If X ⇒ Y | XY ∈ Σ, and W 0 ⊆ W then,
XW ⇒ Y W 0 | XW Y ∈ Σ 00 .
Proof. By the way of contradiction, we suppose that there is a set A ⊆ U, A ∈ Σ 0
such that (note that XW XY W = XW Y )
A ⊇ XW and A + XW Y and A + XW Y
Since X ⇒ Y | XY ∈ Σ, 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 ⊇ XW yields A ⊇ XY W , which
contradicts A + XW Y .
(ii) A ⊇ XY , which in combination with A ⊇ XW yields A ⊇ XW Y , which
contradicts A + XW Y .
Proposition 3 (Transitivity). If X ⇒ Y | XY ∈ Σ and Y ⇒ Z | Y Z ∈ Σ,
then, X ⇒ Z \ Y | X(Z \ Y ) ∈ Σ.
Proof. By the way of contradiction, we suppose that there is A ⊆ U, A ∈ Σ 0
such that
A ⊇ X and A + X(Z \ Y ) and A + XX(Z \ Y )
We have to note that XX(Z \ Y ) = X(Z \ Y ), and that Z \ Y = Y Z, we
finally have that XX(Z \ Y ) = XY Z. Therefore, we suppose that there is a set
A ⊆ U, A ∈ Σ 0 such that:
(i) A ⊇ X.
(ii) A + X(Z \ Y ).
(iii) A + XY Z.
On the other hand, we have that:
X ⇒ Y | XY ∈ Σ implies that A + X or A ⊇ XY or A ⊇ XY .
Y ⇒ Z | Y Z ∈ Σ 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:
8 Baixeries J.
(i) A ⊇ XY and A ⊇ Y Z, that is, A ⊇ XY Z ⊇ X(Z \ Y ). This contradicts
A + X(Z \ 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 \ Y ⊆ Y . All this yields A ⊇ XY ⊇
X(Z \ Y ). This contradicts A + X(Z \ Y ).
Therefore, we have proved that any Σ 00 contains, at least, all the symmetric
dependencies that are in Σ + .
Corollary 1. Σ + ⊆ Σ 00 .
Proof. By Propositions 2 and 3.
We now prove completeness, that is, that Σ 00 only contains all the depen-
dencies in Σ + .
Theorem 1. Σ 00 ⊆ Σ + .
Proof. We prove that X ⇒ Y | Z ∈ / Σ + implies that X ⇒ Y | Z ∈ / Σ 00 .
+
We have that X ⇒ Y | Z ∈ / Σ . It means that the dependency basis of X
is such that in DBΣ (X) = [X | P1 | · · · | Pn ] (with n ⊇ 1) there is, at least, a
class Pk such that Pk ∩ Y 6= ∅ and Pk ∩ Z 6= ∅. We fix Pk in this proof. We note
that |Pk | ⊇ 2, since it contains, at least, one attribute from Y and one from Z.
Sn
Let P = ( Pj )\Pk , 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 ∈ Σ 0 . We
prove this statement by the way of contradiction. Assume that XP 6∈ Σ 0 . That
is because there is a dependency R ⇒ S | T ∈ Σ 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 ∈ RS, s 6∈ XP and t ∈ RT, t 6∈ XP . Since X ⊇ R, then, s ∈ S, s 6∈ XP and
t ∈ T, t 6∈ XP . Necessarily, since s, t 6∈ XP , then, s, t ∈ Pk .
Since XP ⊇ R, by reflexivity, XP ⇒ R | XP R, and by transitivity, XP ⇒
S \ R | XP (S \ R). Without lack of generality, we assume that R, S, T are
disjoint, so, finally, we have XP ⇒ S | XP S. By the definition of DBΣ (X),
then, X ⇒ P | XP , and by transitivity, we have X ⇒ S \ XP | X(S \ XP ).
Since s ∈ S, s 6∈ XP , then, s ∈ S \ XP , and since t ∈ T (assuming R, S, T
disjoint), t 6∈ S, that, together with t 6∈ XP yields that t ∈ X(S \ XP ). It means
that the attributes s, t are in different classes in DBΣ (X), but this contradicts
the previous assumption that Pk ∈ DBΣ (X).
Now, we have that XP ∈ Σ 0 . Since s, t 6∈ XP , we have that XP + XY and XP +
XZ and XP ⊇ X, which implies X ⇒ Y | Z 6∈ Σ 00 .
A New Formal Context for Symmetric Dependencies 9
We have that Σ 00 is exactly the set Σ + . But, as we have already discussed
in the previous section, in [3] and [17] we had a method to query Σ 0 whether a
dependency was in Σ + , and consisted in the closure operator ΓΣ 0 that, given a
set of attributes, returned the meet of its up-set. In this present case, we may
have that Σ 0 is not a lattice (but a partial lattice) and the same operator would
not be a total function. Therefore, we use the up-set, instead of its meet:
Definition 4. Let Σ ⊆ SDU . We define the up-set of X ⊆ U as follows:
U PΣ (X) = { Y ∈ Σ 0 | Y ⊇ X }
This definition is the standard one in lattice theory ([18]) when Σ 0 is an
ordered set. The proof of the following proposition is trivial, yet, it will come
handy to prove the last result of this paper.
Proposition 4. Let X, Y, Z ⊆ U such that Y ⊇ X and Z ⊇ X.
U PΣ (X) = U PΣ (Y ) ∪ U PΣ (Z)
if and only if
@A ∈ Σ 0 : A ⊇ 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 | Z ∈ Σ + if and only if
U PΣ (X) = U PΣ (XY ) ∪ U PΣ (XZ)
Proof.
X ⇒ Y | Z ∈ Σ+
if and only if (by Corollary 1 and Theorem 1)
X ⇒ Y | Z ∈ Σ 00
if and only if (by Proposition 1)
@A : A ⊇ X and A + XY and A + XZ
if and only if (by Proposition 4)
U PΣ (X) = U PΣ (XY ) ∪ U PΣ (XZ)
10 Baixeries J.
4 Example
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 =
{ a, b, c, d }. 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
Σ = {a ⇒ b | cd, b ⇒ ad | c}
According to this context, we have that
Σ 0 = {c, d, bc, cd, abc, abd, acd, bcd, abcd}
and, finally,
Σ 00 = Σ + = {a ⇒ b | cd, b ⇒ ad | c, a ⇒ c | bd, a ⇒ d | bc,
ab ⇒ c | d, ac ⇒ b | d, ad ⇒ b | c, bd ⇒ a | c}
To check these results, we see that ac ⇒ b | d, ad ⇒ b | c and bd ⇒ a | c
are derived from Σ by the reflexivity, transitivity and complementation. For
instance, given a ⇒ b | cd, by reflexivity we have ac ⇒ a | bd, and by transitivity
ac ⇒ b | d (complementation comes from the notation X ⇒ Y | Z used in this
paper). Dependencies ad ⇒ b | c and bd ⇒ a | c can be derived alike.
As for the remaining SD’s:
a ⇒ c | bd, a ⇒ d | bc
by applying transitivity to a ⇒ b | cd and b ⇒ ad | c, we obtain a ⇒ c | bd, and
with complementation we have a ⇒ d | bc.
A New Formal Context for Symmetric Dependencies 11
abcd
acd
abd
abc
bcd
ad
ac
ab
cd
bd
bc
a
d
c
b
a ⇒ b | cd ×××× ××××××××
b ⇒ a | cd × ××××× ××××××
a ⇒ c | bd ××× × ××××××××
c ⇒ a | bd × × ×××× × ×××××
a ⇒ d | cb ××× ×××××××××
d ⇒ a | cb × × × ×××× ×××××
b ⇒ c | ad × ×× ××× ××××××
c ⇒ b | ad × × ×× ××× ×××××
b ⇒ d | ac × ×× ×× ×××××××
d ⇒ b | ac × × × ×× ×× ×××××
c ⇒ d | ab × × ×× × ×××××××
d ⇒ c | ab × × × ×× × ××××××
ab ⇒ c | d × × × × ××××××××××
ac ⇒ b | d × × × × × ×××××××××
bc ⇒ a | d × × × × × × × ×××××××
ad ⇒ b | c × × × × × × ××××××××
bd ⇒ a | c × × × × × × × × ××××××
cd ⇒ a | b × × × × × × × × × ×××××
Fig. 1. Formal context (SDU , ℘(U), I) for U = { a, b, c, d }
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 = { a, b, c, d, e }. Let Σ be the set of symmetric
dependencies:
b ⇒ a | cde b ⇒ c | ade c ⇒ a | bde c ⇒ b | ade d ⇒ a | bce d ⇒ e | abc
e ⇒ a | bcd e ⇒ d | abc
According the formal context (SDU , ℘(U), I ), we have that:
Σ 0 = { a, abc, ade, abcd, abce, abde, acde, bcde, abcde }
We can see that, applying the axioms of symmetric dependencies in Definition
1, the set Σ + is:
b ⇒ a | cde b ⇒ c | ade c ⇒ a | bde c ⇒ b | ade d ⇒ a | bce d ⇒ e | abc
e ⇒ a | bcd e ⇒ d | abc abd ⇒ c | e acd ⇒ b | e ce ⇒ a | bd de ⇒ a | bc
bcd ⇒ a | e abe ⇒ c | d ace ⇒ b | d bce ⇒ a | d bde ⇒ a | c cde ⇒ a | b
ab ⇒ c | de ac ⇒ b | de ad ⇒ bc | e ae ⇒ bc | d bc ⇒ a | de bd ⇒ ac | e
bd ⇒ a | ce bd ⇒ ae | c be ⇒ ac | d be ⇒ ad | c be ⇒ a | cd cd ⇒ a | be
cd ⇒ ae | b cd ⇒ ab | e ce ⇒ ab | d ce ⇒ ad | b
12 Baixeries J.
We only state the non-trivial dependencies as in Definition 2. We take, for
instance, the dependencies:
bd ⇒ ac | e, bd ⇒ a | ce, bd ⇒ ae | c
They are derived from the dependencies b ⇒ a | cde and b ⇒ c | 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 | c because abcd ≥ bcd (the left-
hand side plus the second right-hand side) and that it also respects bd ⇒ a | ce
because abcd ≥ abd (the left-hand side plus the first right-hand side). We can
see in this example the duality of the definition 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 | cde and b ⇒ c | ade. We take, for instance, the set bde, (which
would prevent bd ⇒ a | ce from being in Σ 00 ) is not in Σ 0 because it does not
respect the dependency b ⇒ a | cde.
We now illustrate one case of derivation by transitivity with the following
set:
a ⇒ bc | de, bc ⇒ d | ae
By transitivity, we have that a ⇒ d | bce ∈ Σ + . If we take Σ = { a ⇒ bc | de },
we have:
Σ 0 = {b, c, d, e, bc, bd, be, cd, ce, de, abc, ade, bcd, bce, bde, cde, abcd, abce, abde,
acde, bcde, abcde}
/ Σ 00 since the sets abc, acde ∈ Σ 0 do not respect
It is clear that a ⇒ d | bce ∈
this dependency. Now, if we include bc ⇒ d | ae in Σ, we have:
Σ 0 = { b, c, d, e, bd, be, cd, ce, de, ade, bcd, bde, cde, abcd, abce, abde, acde, bcde, abcde }
It has precisely been the dependency bc ⇒ d | ae the one that has cleared
both abc and acde from Σ 0 and, therefore, allows a ⇒ d | 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 | cde b ⇒ c | ade c ⇒ a | bde c ⇒ b | ade d ⇒ a | bce d ⇒ e | abc
e ⇒ a | bcd e ⇒ d | abc
and, therefore:
Σ 0 = { a, abc, ade, abcd, abce, abde, acde, bcde, abcde }
A New Formal Context for Symmetric Dependencies 13
We can see that Σ 0 in not closed (abcd, abde ∈ Σ 0 , but ab ∈ / Σ 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 | de and query Σ 0 :
U PΣ (a) = { a, abc, ade, abcd, abce, abde, acde, abcde }
U PΣ (abc) = { abc, abcd, abce, abcde }
U PΣ (ade) = { ade, abde, acde, abcde }
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 | de:
U PΣ (ab) = { abc, abcd, abce, abde, abcde }
U PΣ (abc) = { abc, abcd, abce, abcde }
U PΣ (abde) = { abde, abcde }
In this case, the sets U PΣ (ab) and U PΣ (abc) ∪ U PΣ (abde) coincide.
5 Discussion
We have seen in Section 2 that the different characterizations of dependencies
with formal contexts follow a common pattern, regardless of the type of depen-
dencies or the definition of the context. Yet, the definition of formal contexts for
AD’s and SD’s as in [3] was structurally different (powersets versus partitions)
and that made it difficult to find a relationship and generalization between both
contexts, in spite of the clear structural similarities that exist between AD’s and
SD’s.
Now, we have that the relation I is a generalization of the relation defined
in the context KAD (U) = (ADU , ℘(U), I). We recall the definition of this relation
([17]):
Definition 5. A ⊆ U respects an Armstrong dependency X → Y iff:
A + X or A ⊇ XY
We see that this definition avoids the reference to the second right-hand side,
precisely because in AD’s, complementation does not hold. If we drop this part
from Definition 3, we have the definition of the respect relation for Armstrong
dependencies.
This generalization seems to suggest that the solutions that have been de-
veloped based on the lattice characterization of sets of Armstrong dependencies,
may also be applied to symmetric dependencies, namely:
1. To define a formal context for mixed sets of AD’s and SD’s.
14 Baixeries J.
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
defining a formal context for mixed sets of dependencies, such that the relation
would be the union of the relations already defined 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 definition 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 characteri-
zation of the generating set of a set of SD’s may encounter some difficulties. The
main difference 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, offers a much clearer perspective and
understanding than before.
It must be said too that whereas this new characterization may make it po-
tentially easier to find methods for finding minimal basis and query learning
for SD’s, it is true that SD’s have not yet been used outside the database do-
main. We think that advancing in the study of lattice characterization for SD’s
and finding 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, profiting 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 [3], since we have replaced the set Part(U) by the
set ℘(U). Yet, and for the sake of algorithmic solutions already existing in the
FCA community, we have to say that the size of the context remains exponential.
6 Conclusions and Future Work
We have presented a new formal context for symmetric dependencies. This con-
texts provides the same functionalities as previous approaches, and it is much
simpler. Yet, it offers the same expressivity power and, in fact, reduces the con-
ceptual gap between Armstrong and symmetric dependencies that existed in a
previous approach. We strongly believe that this may be the first step towards
the resolution via formal concept analysis, of the learning, minimal bases and
mixed sets of dependencies problems for symmetric dependencies, profiting from
solutions already existing for Armstrong dependencies.
A New Formal Context for Symmetric Dependencies 15
References
1. Angluin D., Frazier M., Pitt L. Learning Conjunctions of Horn Clauses. Machine
Learning, 9:147-164, 1992.
2. Arias M., Balcázar, José L. Canonical Horn Representations and Query Learning.
Lecture notes in computer science, vol. 5809, p. 156-17, 2009.
3. Baixeries, Jaume. A Formal Context for Symmetric Dependencies. ICFCA 2008.
LNAI 4933.
4. Baixeries, Jaume and Balcázar, José L. Discrete Deterministic Data Mining as
Knowledge Compilation. Proceedings of Workshop on Discrete Mathematics and
Data Mining in SIAM International Conference on Data Mining, 2003.
5. Baixeries, Jaume and Balcázar, José L. Characterization and Armstrong Relations
for Degenerate Multivalued Dependencies Using Formal Concept Analysis. Formal
Concept Analysis, Third International Conference, ICFCA 2005, Lens, France,
February 14-18, 2005, Proceedings. Lecture Notes in Computer Science, 2005
6. Baixeries, Jaume and Balcázar, José L. Unified Characterization of Symmetric
Dependencies with Lattices. Contributions to ICFCA 2006. 4th International Con-
ference on Formal Concept Analysis 2005.
7. Baixeries, Jaume. A Formal Concept Analysis framework to model functional
dependencies. Mathematical Methods for Learning, 2004.
8. Balcázar, José L. and Baixeries, Jaume. Discrete Deterministic Data Mining as
Knowledge Compilation. Workshop on Discrete Mathematics and Data Mining in
SIAM Int. Conf. 2003.
9. Beeri, Catriel and Fagin, Roland and Howard, John H. A Complete Axiomatization
for Functional and Multivalued Dependencies in Database Relations. Proceedings
of the 1977 ACM SIGMOD International Conference on Management of Data,
Toronto, Canada, August 3-5, 1977.
10. Caspard, Nathalie and Monjardet, Bernard. The Lattices of Closure Systems, Clo-
sure Operators, and Implicational Systems on a Finite Set: a Survey. Proceedings of
the 1998 Conference on Ordinal and Symbolic Data Analysis (OSDA-98). Discrete
Applied Mathematics, 2003.
11. Day, Alan. The Lattice Theory of Functional Dependencies and Normal Decompo-
sitions. International Journal of Algebra and Computation Vol. 2, No. 4 409-431.
1992.
12. Day, Alan. A Lattice Interpretation of Database Dependencies. Semantics of Pro-
gramming Languages and Model Theory, 1993.
13. Demetrovics, János and Hencsey, Gusztav and Libkin, Leonid and Muchnik, Ilya.
Normal Form Relation Schemes: a New Characterization. Acta Cybernetica, 1992.
14. Demetrovics, János and Huy, Xuan. Representation of Closure for Functional, Mul-
tivalued and Join Dependencies. Computers and Artificial Intelligence, 1992.
15. Demetrovics, János and Libkin, Leonid and Muchnik, Ilya. Functional Dependen-
cies in Relational Databases: a Lattice Point of View. Discrete Applied Mathemat-
ics, 1992.
16. Duquenne, Vincent and Guigues, J.L. Familles Minimales d’Implications Informa-
tives Resultant d’un Tableau de Donées Binaires. Mathematics and Social Sciences,
1986.
17. Ganter, Bernhard and Wille, Rudolf. Formal Concept Analysis: Mathematical
Foundations. Springer, 1999.
18. Grätzer, George. General Lattice Theory. Academic Press, 1978.
16 Baixeries J.
19. Pfaltz, John L. Using Concept Lattices to Uncover Causal Dependencies in Soft-
ware. Formal Concept Analysis, 4th International Conference, ICFCA 2006, Dres-
den, Germany, February 13-17, 2006.
20. Pfaltz, John L. Incremental Transformation of Lattices: A Key to Effective
Knowledge Discovery. In Proc. of the First Intl. Conf. on Graph Transformation
(ICGT’02), pages 351–362, Barcelona, Spain, Oct 2002.
21. Ullman, Jeffrey D. Principles of Database Systems. Computer Science Press, 1982.