Closure system is a fundamental concept appearing in several areas such as databases, formal concept analysis, artificial intelligence, etc. It is well-known that there exists a connection between a closure operator on a set and the lattice of its closed sets. Furthermore, the closure system can be replaced by a set of implications but this set has usually a lot of redundancy inducing non desired properties. In the literature, there is a common interest in the search of the minimality of a set of implications because of the importance of bases. The well-known Duquenne-Guigues basis satisfies this minimality condition. However, several authors emphasize the relevance of the optimality in order to reduce the size of implications in the basis. In addition to this, some bases have been defined to improve the computation of closures relying on the directness property. The efficiency of computation with the direct basis is achieved due to the fact that the closure is computed in one traversal. In this work, we focus on the D-basis, which is ordered-direct. An open problem is to obtain it from an arbitrary implicational system, so it is our aim in this paper. We introduce a method to compute the D-basis by means of minimal generators calculated using the Simplification Logic for implications.
Discovering knowledge and information retrieval are currently active issues where Formal Concept Analysis (FCA) provides tools and methods for data analysis. The notions around the concept lattice may be considered as the main attractions in Formal Concept Analysis and they are strongly connected to the notion of closure.
Closure system is a fundamental concept appearing in several areas such as database theory, formal concept analysis, artificial intelligence, etc. It is wellknown that there exists a connection between a closure operator on a set and the lattice of its closed sets. Furthermore, the closure system can be presented, dually, as a set of attribute implications, namely an implicational system but this set has usually a lot of redundancy inducing non-desired properties.
We can not fail to mention the relevance of the role of the implication notion
in different areas. It was the main actor of the normalization theory in database
area; it has an outstanding character in Formal Concept Analysis and it was
prominently used in Frequent Set Mining and Learning Spaces, see the survey
of M. Wild [
Nonetheless, as V. Duquenne says in [
In this paper, we are focused in the Formal Concept Analysis area and the
fundamental notions are assumed (see [
Many applications must massively compute closures of sets of attributes and
any improvement of execution time is relevant. In [
An important matter in FCA is to transform implicational systems in
canonical forms for special proposals in order to provide an efficient further
management. Hence, some alternative definitions have been established:
DuquenneGuigues basis, direct optimal basis, D-basis, etc. In this work we focus on the
last one [
The major issue is that the execution of the D-basis in one iteration is more
efficient that the execution of a shorter, but un-ordered one, for instance the
canonical basis of Duquenne and Guigues. K. Adaricheva et.al prove in [
In [
Currently the retrieval of the D-basis from an arbitrary implicational system is an open problem, so it becomes our aim in this paper. We introduce a method to compute the D-basis by means of minimal generators calculated using the Simplification Logic for implications. The relationship among minimal generators, covers, minimal covers and D-basis is presented and an algorithm to calculate D-basis from an arbitrary set of implications is proposed.
Section 2 presents the main notions necessary to the understanding of the new method: closure operators, the D-basis, Simplification Logic and the method to calculate minimal generators. In Section 3, the relationships between covers and generators are presented. In Section 4, the new method to obtain the Dbasis from a set of implications is shown, and some conclusions and extensions are proposed in Section 5. 2 2.1
Given a non-empty set M and the set1 2M of all its subsets, a closure operator is a map φ : 2M → 2M that satisfies the following, for all X, Y ∈ 2M : (1) increasing: X ⊆ φ(X); (2) isotone: X ⊆ Y implies φ(X) ⊆ φ(Y ); (3) idempotent: φ(φ(X)) = φ(X).
We will refer to the pair hM, φi of a set M and a closure operator on it as a closure system.
In the next two subsections we will follow the introduction of the
implicational system based on the minimal proper covers 2 given in [
We will call closure system reduced, if φ({x}) = φ({y}) → x = y, for any
x, y ∈ M 3. If the closure system hM, φi is not reduced, one can modify it to
produce an equivalent one that is reduced, see [
We will now define a closure operator φ∗, which is associated with a given operator φ.
Definition 1. Let hM, φi be a closure system. Define φ∗ as a self-map on 2M such that φ∗(X) = Sx∈X φ(x), X ⊆ 2M .
It is straightforward to verify that
1 In the FCA framework, that set M can be thought a set of attributes of a context.
2 Although in [
Lemma 1. φ∗ is a closure operator on M .
Given a closure system hM, φi, we introduce several important concepts.
Definition 2 ([
In this subsection, we briefly summarize the introduction of the D-basis in [
The existence of several proper covers for the same element induces the need to introduce the notion of minimality.
Lemma 2. If x ∼p X, then there exists Y such that x ∼p Y , Y ⊆ φ∗(X) and Y is a minimal proper cover for x. In other words, every proper cover can be reduced to a minimal proper cover under the subset relation added with the φ∗ operator.
These ideas bring to the following definition of the implicational system defining the reduced closure system by means of the minimal proper covers. Definition 4. Given a reduced closure system hM, φi, define the D-basis ΣD as a union of two subsets of implications: 1. {y → x : x ∈ φ(y) \ y, y ∈ M } (such implications are called binary); 2. {X → x : X is a minimal proper cover for x}.
Note that the D-basis belongs to the family of the unit bases, i.e. implicational sets where each implication A → b has a singleton b ∈ M as a consequent. Lemma 3. ΣD generates hM, φi. 2.3
Here we recall the notion of the ordered direct basis introduced in [
Xk ∪ B, if A ⊆ Xk,
Xk, otherwise.
Finally, ρΣ (X) = Xn. We will call ρΣ an ordered iteration of Σ.
The concept of the ordered iteration is central for the definition of the ordered direct basis. For any given set of implications Σ on set M , by φΣ we understand the closure operator on M defined by Σ. Equivalently, the fixed points of φΣ are exactly subsets X ⊆ M which are stable for all implications A → B in Σ: if A ⊆ X, then B ⊆ X.
Definition 6. The set of implications with some linear ordering on it, hΣ, <i, is called an ordered direct basis, if, with respect to this ordering, φΣ (X) = ρΣ (X) for all X ⊆ S.
We note that any direct basis is ordered direct. By direct basis we understand any set of implications that allows to produce the closure of subsets of the base set while attending each implication only once.
More precisely, if Σ is some set of implications defining the closure system hM, φi, then let πΣ (X) = X ∪ S{B : A ⊆ X and (A → B) ∈ Σ}. In order to obtain φ(X), for any X ⊆ M , one would normally need to repeat several iterations of πΣ : φ(X) = πΣ (X) ∪ πΣ2 (X) ∪ π3 (X) . . . . Σ
The bases for which one can obtain the closure of any set X performing only
one iteration of πΣ , i.e., φ(X) = πΣ (X), are called direct. The various direct
bases appearing in the literature were surveyed in K. Bertet and B. Monjardet
[
The following result from [
2.4
In this subsection we summarize how the inference system of Simplification Logic
SLFD [
SLFD logic considers reflexivity as axiom scheme [Ref] A ⊇ B
A → B and the following inference rules called fragmentation, composition and simplification respectively.
[Frag] A → B ∪ C
A → B
A → B, C → D [Comp] A ∪ C → B ∪ D
A → B, C → D
[Simp] A ∪ (C r B) → D
The important matter is that these rules can be considered as equivalence rules
which have been used as the core in automated methods for removing
redundancies, obtaining minimal keys, or computing closures. In particular, the last
method indicated is based on the following results (see [
Theorem 2 ([
In order to compute closures, since φ(A) is the biggest subset B such that Σ ` A → B, the formula ∅ → A is used as a seed which guides the reasoning to render the closure φ(A) just by applying the following equivalences where the [Simp] inference rule plays a main role.
Proposition 1. Let A, B and C be subsets of M , then the following equivalences hold: – Eq. I: If B ⊆ A then {∅ → A, B → C} ≡ {∅ → A ∪ C}. – Eq. II: If C ⊆ A then {∅ → A, B → C} ≡ {∅ → A}.
– Eq. III: Otherwise {∅ → A, B → C} ≡ {∅ → A, B r A → C r A}.
Based on the above proposition and Theorem 2, in [
Notation: From now on, in order to simplify the examples, elements of M are denoted by numbers from 0 to 9 or lowercase letters and we omit brackets and commas in subsets of M .
Example 1. Let Σ be {ab → c, ac → df, bcd → ef, f → c}. Then, Cls(af, Σ) = (acdf, {b → e}) where φ(af ) = acdf and Σ0 = {b → e} has important information that will be used in the computation of minimal generators. For X, Y ⊆ M satisfying that X = φ(Y ), it is usual to say that Y is a generator of the closed set X. Notice that any subset of X containing Y is also a generator of X. When the base set M of a closure system is finite, the set of generators of a closed set can be characterized by its minimal ones.
is said to be a minimal generator if, for all proper subsets Y ⊂ X, one has φ(Y ) ⊂ φ(X).
In [
MinGen(M, Σ) = {habcd, {c, ad, bd}i, hab, {a}i, hb, {b}i, hd, {d}i, h∅, {∅}i}
Observe that there is trivial information (e.g. hb, {b}i) included in the output
of this algorithm. In [
For the same input, MinGen0(M, Σ) = {habcd, {c, ad, bd}i, hab, {a}i, h∅, {∅}i} 3
The definition of a D-basis is strongly based on the notion of a proper minimal cover, and the latter is connected with the notion of a minimal generator. In this paper we are going to work with covers instead of proper covers because our idea is to manage, in a uniform way, the binary implications and non-binary ones. Throughout this section we will assume that M is the base set of a closure system defined either by closure operator φ, or by means of a set of implications Σ and its related operator φΣ . The following definition introduces a notion that extends the concept of a proper cover.
Definition 8 (Cover). Given X ⊆ M and x ∈ M , we say X is a cover of x, denoted x ∼ X, if x ∈ φ(X) \ X.
The following proposition, whose proof is straightforward from definitions,
illustrates the relationship among proper covers, covers and minimal generators.
Proposition 2. Let Σ be a set of implications. For each set C ⊆ M closed with
respect to φΣ and each X C,
1. X is a generator of C if and only if X is a cover of any x ∈ C r X.
2. If X is a proper cover of x ∈ M then X is also a cover of x.
Observe that the converse of the second item is not true, e.g. ad is a cover of
b (b ∼ ad) in Example 2 but it is not a proper cover. As we have remarked
in Section 2, the above definition of a cover does not coincide with the one
introduced in [
Corollary 1. Let Σ be a set of implications. For each set C ⊆ M closed with respect to φΣ and each X C, if X is a minimal generator of C then X is a cover of any x ∈ C r X.
The following example illustrates these relationships and gives a counterexample to the converse statement in the previous corollary.
Example 3. Let M = {a, b, c, d, e} and Σ = {a → d, bce → ad, bde → ac, ade → bc, cd → abe, abd → ce}. In Table 1, the covers of each element of M and the nontrivial minimal generators of each φΣ -closed set are shown. Moreover, underlined covers are not proper covers whereas the others are.
Closed Sets Minimal Generators abcde ad ab, ac, ae, bce, bde, cd a cd, bcd, bce, bde, cde, bcde ac, ae, cd, acd, ace, ade, cde, acde ab, ae, abd, abe, ade, bde, abde a, ab, ac, ae, abc, abe, ace, bce, abce ab, ac, cd, abc, abd, acd, bcd, abcd
Observe that, by Proposition 2, X is a cover of an element x if and only if there exist a closed set C and a minimal generator Y of C such that Y ⊆ X and x ∈ C r X. For example, cd is a minimal generator of abcde and cd ⊆ cde, thus, cde is a cover of a but not a minimal generator.
The closure operator φ∗ allows us to introduce the notion of a minimal cover. It will be used later to avoid redundancies in the implications of the basis when we look for an optimal basis.
Definition 9 (Minimal Cover). Let Σ be a set of implications. Given X ⊆ M and x ∈ M , X is a minimal cover of x if X is a cover and satisfies one of the following conditions: 1. X is a singleton, i.e., | X |= 1. 2. for every cover Y of x, Y ⊆ φ∗(X) implies X ⊆ Y .
From this definition we directly obtain the following proposition that relates minimal generators and minimal covers.
Proposition 3. Let Σ be a set of implications, X ⊆ M and x ∈ M . If X is a minimal cover of x ∈ φ(X) \ X, then X is a minimal generator of φ(X). The following example illustrates the definition of minimal covers and shows that the converse statement to the above proposition is not true. Example 4. Given the base set and the set of implications of Example 3, Table 2 shows the minimal covers of each element.
Element Minimal Covers a b c d e cd, bce, bde ae, cd ab, ae, bde a, bce ab, cd
Although ae is a minimal generator of abcde, it is not a minimal cover for all x ∈ φ({a, b, c, d, e}) \ {a, e} = {b, c, d} but only for b and c. As the previous examples show, a minimal cover is always a minimal generator, but not conversely. Thus, if we compute all minimal generators for some x ∈ M , we have, at the same time, all minimal covers for x, and the latter are exactly what we need for the computation of the D-basis. 4
We remark that it is an open problem to design an algorithm rendering the D-basis from an arbitrary implicational system. In this section, we are going to introduce such an algorithm based on the strong connection between minimal covers and minimal generators. This is shown in Algorithm 1. To begin with, we define the Function MinimalCovers to make the algorithm easier to understand.
The input of the Function MinimalCovers is a set of covers of a given x ∈ M and it returns a subset with all its minimal covers.
Function MinimalCovers(L) input : A set of covers L output: The set of minimal covers begin foreach g ∈ L do foreach h ∈ L \ g do if h ⊆ g then
remove g from L else if | g |6= 1 and h ⊆ remove g from L [ φ(x) then x∈g return L Notice that although the condition h ⊆ g implies h ⊆ x∈g them lead to the same action, it is more efficient to split them off because the cost of the first one is lower. Thus, we previously check the first one and, if it is not fulfilled, then the other one is tested.
As we have mentioned before, our goal is to obtain the D-basis from an
arbitrary implicational system. In the first stage, the algorithm computes all
minimal generators by means of the MinGen0 method proposed in [
As Figure 1 depicts, the transition from stage 1 to stage 2 needs a way to associate the minimal generators with some of the elements in its closed set. [ φ(x) and both of
a ~Yk
Yk minimal cover Original Situation
....
Ak⟶Bk ....
Implicational System
Stage 1
.... <Xk , Y1...Yn>
....
Set of (non trivial) Closed sets and Minimal Generators Thus, let a be an attribute and mg be the set of minimal generators such that its closure contains a. We write this association as a pair ha, mgi. Let Φ be a set of such pairs of attributes with their generators. We define the Function Add which builds the set of covers produced in Stage 2 as follows:
Add(ha, mgi, Φ) = {ha, {g ∈ mg|a 6∈ g} ∪ {mga}i : ha, mgai ∈ Φ}
Then, in stage 3, the algorithm picks up the set of minimal covers from the set obtained in stage 2 using the Function MinimalCovers. The method ends with the Function OrderedComp which applies Composition Rule at the same time that it orders the implications in the following sense: the first implications in the D-basis are the binary ones (those with the left-hand side being a singleton).
input : An implicational system Σ on M output: The D-basis ΣD on M begin
MinGen:=MinGen0(M , Σ) C:= ∅ foreach hC, mg(C)i ∈MinGen do foreach a ∈ C do
C:=Add(ha, mg(C)i, C) ΣD := ∅ foreach ha, mgai ∈ C do mga :=MinimalCovers(mga) foreach g ∈ mga do ΣD := ΣD ∪ {g → a} ; OrderedComp(ΣD) return ΣD Example 5. Algorithm 1 returns the following D-basis from the input implicational system of Example 3: ΣD = {a → d, bce → ad, ab → ce, ae → bc, bde → ac, cd → abe}
We emphasize that although ac is a minimal generator, it is not a minimal cover, thus an implication with ac in the left-hand side is redundant (deduced from inference axioms) and hence should not appear in the D-basis.
In the conclusion of this section we show the execution of the method, in all its
stages, on a set of implications from [
As a first step in the algorithm, MinGen0 renders the following set of pairs of closed sets and its non-trivial minimal generators, see Figure 2: {h12345, {123, 14, 15, 25, 35}i, h234, {23, 24, 34}i, h45, {5}i, h∅, ∅i}
5⟶4, 2 3⟶4, 2 4⟶3, 3 4⟶2, 1 4⟶2 3 5, 2 5⟶1 3 4, 3 5⟶1 2 4, 1 5⟶2 4, 1 2 3⟶4 5 ø⟶5 1⟶452 3, 2⟶1 3, 3⟶1 2
{5} 1 2ø⟶31 ø⟶2 ø⟶3 {ø1 5} 1 2{ø235} 1 2{ø335} 1 ⟶ø2⟶35,425⟶31
{2 3} 1ø⟶51 ø⟶5 {1ø2 3} {12ø53 5} 2ø3 ⟶42 4 1⟶5, 5⟶{214} 1ø⟶51 ø⟶5 {1ø2 4} 1{2ø54 5}
Then, for each closed set and each of its elements, our algorithm renders the following set of pairs of elements and covers: {h1, {25, 35}i, h2, {14, 15, 35, 34}i, h3, {14, 15, 25, 24}i,
h4, {123, 15, 25, 35, 5, 23}i, h5, {123, 14}i} For each element, the Function MinimalCovers picks up its minimal covers: {h1, {25, 35}i, h2, {14, 34}i, h3, {14, 24}i, h4, {5, 23}i, h5, {14, 123}i} Finally, at the last step, the algorithm turns these pairs into implications and applies ordered composition resulting in the D-basis.
ΣD = {5 → 4, 23 → 4, 24 → 3, 34 → 2, 14 → 235, 25 → 1, 35 → 1, 123 → 5}
In this work we have presented a way to obtain the D-basis from any
implicational system. In [
The Function MinimalCovers renders the D-basis within the framework of the closure systems without the need of any transformation. A key point of our work is the connection between covers and generators. Using minimal generators, the D-basis is obtained by reducing the set of minimal generators and transforming it into a set of minimal covers.
As future work, we propose to develop an algorithm which computes the D-basis with better integration of the minimal generator computation to render the minimal covers in a more direct way. In addition, we are planning to design an empirical study and to make a comparison between this algorithm and other techniques proposed in previous papers.
Supported by Grants TIN2011-28084 and TIN2014-59471-P of the Science and Innovation Ministry of Spain.