In this paper, we introduce the dependence graph of a lattice defined on the set of its join-irreducible elements. This graph, issued from the dependence relation on a lattice, is a nice structure encoding together the minimal generators and the canonical direct basis of a lattice. Then, we propose a new generation algorithm.
From the year 2000, the increasing interest into Formal Concept Analysis (FCA)[
FCA’s increasing importance has many reasons. For one, new scientific areas have recently begun to incorporate computer technologies on a large scale through data-bases, whence a large production of data and the need for handling them. Secondly, the increasing power of computers permits the automatization of tasks that might have, in the worst case, exponential time-space costs. Among them, the typical problems from FCA related to the representation of a lattice that could have exponential size relative to the size of the original data.
In data mining, the problem of classification is naturally related to the notion of concept from FCA. Unsupervised classification consists in grouping objects that have close attributes while separating those having distant attributes; supervised classification groups objects having a same label (called class), while it distinguishes those having different labels. The notion of concept is then repeatedly used in applications to classify data, in a supervised or unsupervised way. Dependencies between attributes are classically represented by rules. Associative rules, well-known in data mining, can be either exact or approximate rules. For relational data-bases, systems of rules are known under the name of functional dependencies. The combinatorial explosion of the number of rules and the growing volume of data to be handled have made the use of concise representations, called bases, necessary. c 2012 by the paper authors. CLA 2012, pp. 223–231. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978–84–695–5252–0, Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.
In lattice theory, a fundamental representation theorem establishes that
every lattice is the concept lattice of its binary table [
There can be many equivalent bases, where two bases are equivalent if they
give rise to the same closed set lattice. The canonical direct basis is the only
one that is direct, meaning that the closure of an arbitrary set can be computed
by just one application of the rules to the set, and that, at the same time, is
minimal among the direct systems. Moreover, it has been shown in [
In this paper, we introduce the dependence graph as a representation of a
lattice defined on the set of its join-irreducible elements. This graph, issued from
the dependence relation on a lattice [
After a first section of definitions, we define the dependence graph of a lattice. In the last section, we discuss about existing generation algorithms of the dependence graph, and we propose a new generation algorithm. 2
Lattice. In lattice theory, the structure of lattice can been introduced either as an
algebraic structure provided with two operators named lower and upper bounds,
or as an ordered structure defined by the existence of particular elements called
upper and lower bounds [
More formaly, a lattice is an order relation ≤ on a set S (i.e. a reflexiv, antisymmetic and transitiv relation) where every couple of elements has a a join and a meet. The meet (resp. join) of x and y, denoted x ∧ y (resp. x ∨ y), is the unique greatest lower bound (resp. least upper bound) of x and y.
Meet and join elements are defined in a more general but identical manner for a subset X ⊆ S: the meet of X, noted ∨X, is the unique greatest element of the predecessors of X, while the join of X, noted ∧X, is the unique least element of the successors of X. As a direct consequence, any lattice admits a unique maximal element called top and denoted ⊤ or 1, and a unique minimal element called bottom and denoted ⊥ or 0.
The strict order relation of any order relation ≤, denoted <, is an antisymmetric, transitive and irreflexive relation defined by x < y if x ≤ y and x 6= y. It corresponds to the reflexive reduction of ≤. The cover relation of ≤, denoted ≺, is an antisymmetric relation defined by x ≺ y if x < y, and there is no z so that x < z < y. We then say that y cover x. It corresponds to the reflexive and transitive reduction of ≤. The Hasse diagram is a graphical representation of an order where only the arcs of the cover relation ≺ are represented since reflexivity and transitivity edges can be deduced.
Irreducibles elements. An element of a lattice is called reducible if it corresponds to a meet and a join of two distinct elements. Otherwise, it is called irreducible. More precisely, an element j is called a join-irreducible if for any subset X of elements, j = ∨X implies that j ∈ X. An element m is called meet-irreducible if for any subset X of elements, m = ∧X implies that m ∈ X. The set of joinirreducibles of a lattice L is usually denoted JL, and the set of meet-irreducibles ML. In particular, we have ⊥ = ∨∅ and ⊤ = ∧∅ implying that ⊥ is not a join-irreducible, and ⊤ is not a meet-irreducible.
A nice characterization establishes that an element is a join-irreducible if, and only if, it covers only one element, denoted j−, while an element is a meetirreducible if, and only if, it is covered by only one element, denoted m+.
Any element x ∈ S of a lattice L is the join of its predecessors, and the meet of its successors. The latticial property implies a reduction to join-irreducible predecessors and meet-irreducible successors: x = ∨Jx = ∨{y ∈ JL : y ≤ x} x = ∧Mx = ∧{y ∈ ML : y ≥ x} (1) (2)
Therefore, irreducible elements are enough to build the lattice in its entirety, using either join irreducibles for reconstruction by upper bound, or meetirreducibles for reconstruction by lower bound. Moreover, JL and ML are minimal set allowing reconstruction.
Minimal generators. Consider one element x ∈ S. Although x is the join of Jx, Jx is not always the minimal subset to define x as a join. A minimal subset to obtain x as a join, including in Jx, is named a basis, a minimal generating set or a minimal generator for x. More formally, a minimal generator of x is a subset B of Jx such that x = ∨B and B is inclusion-minimal, i.e for all A ⊂ B, then x 6= ∨A. The family Bx of minimal generators of x is then:
Bx = {B ⊆ Jx : x = ∨B and x 6= ∨A for all A ⊂ B} (3)
The dual observation for Mx is valid for a reconstruction of x as meet. The number of minimal generators of x can be exponential in the cardinality of Jx in the worst case.
Consider the example of lattice in Figure 1(a). Six elements possess a single incoming arc, forming all join-irreducibles ; the meet-irreducibles, characterized (a) A lattice (b) The isomorphic lattice with the sets Jx and
Mx inside each node x by a single outcoming arc, are heigth:
J = {a, b, c, d, e, f } M = {b, c, d, i, k, l, m, n} (4) (5) These irreducible elements are used to describe more precisely the elements of the lattice (see Figure 1) where node of each element x contains its join-irreducible predecessors Jx and its meet-irreducible successors Mx. Minimal generators are given in Table 1. One can observe that each join-irreducible possesses itself as unique minimal generator ; the top element possesses 4 minimal generators. x a b Jx a b Bx {a} {b} c ac {c} d e f g def e f ∅ {d} {e} {f } {∅} x h i j k l m n Jx ef adef abcdef aef bf af ae
Bx {ef } {ad} {ab, bc, bd, dc} {aef } {bf } {af } {ae}
Dependence graph and canonical direct basis of a lattice.
Dependence graph. The dependence graph of a lattice is defined on the set
JL of join-irreducible elements.It is an edge-labeled directed graph whose edges
corresponds to the dependence relation δ of a lattice [
The subgraph δ∅ of the dependence graph to the edges containing the empty set as label corresponds to the subgraph of the lattice induced by its joinirreducible, since j < j′ implies j < j′ ∨ ⊥ and ω(j, j′) = J⊥ = {∅}. As a direct consequence, a lattice is distributive when edge-labels of its dependence graph all are the empty set. Canonical direct unit basis. A set of unit implication (or rules) Σ is a binary relation between P(S) and S where a rule (X, y), generaly denoted X → y, means that X”implies” y, with X called the premisse and y the conclusion.
The dependence graph encodes a set of rules defined on the join-irreducibles
JL of a lattice, with a rule B + j′ → j for each (j, j′) ∈ δB. This set of rules
forms a particular basis of the lattice called the canonical direct unit basis, and
denoted Σcdb [
Morover, an important result establishes that every lattice is isomorphic to the closed set lattice (F , ⊆) of its canonical direct basis, where F is a family on JL. This family contains all the closures of the basis where a closure is a subset X of JL verifying all rules, i.e. for each rule B → y, if B ⊆ X then y ∈ B.
Therefore, the dependence graph of a lattice encodes the canonical direct basis from which the lattice reconstruction is possible as a closed set lattice. 4
Since the size of the dependence graph can be exponential in the size of the
lattice, this generation problem belongs to the more general class of problems
having an input of size n, and an output of size N bounded by 2n. For this
class of problems, a classical worst-case analysis makes them exponential, thus
NP-hard, with an exponential space. However, a more precise information can
be obtained by output-sensitive analysis techniques (see a survey in [
The time complexity per Σcdb-rule has then to be considered. Although the most common algorithms have an exponential delay complexity, there exist some algorithms with a polynomial delay complexity.
The definition of minimal generators for an element x induces an
exponential generation since any subset of Jx as to be tested. Another strategy is issued
from the equivalence between minimal generators and minimal transversals of
a closed set, problem known to be exponential. This strategy has been
capitalized by Pfaltz’s incremental algorithm [
However, in logic area, the algorithm attributable to Ibaraki et al. ([
Algorithm 1 generates the dependence graph with the same polynomial complexity per rule or per minimal generator. Name: dependenceGraph Data : A lattice L = (S, ≤) Result : The dependence graph of the lattice begin compute the set JL of join-irreducibles of the lattice; initialize a graph G with join-irreducibles as nodes; compute a topological sort T of the lattice; foreach x ∈ T do foreach (j, j′) ∈ J × J such that x ∨ j′ ≥ j do add the edge (j, j′) in G; compute the set Jx of join-irreducible predecessors of x; initalize the empty family GMx; let G′ subgraph of G induced by Jx on nodes and edges’s labels; foreach edge (k, k′) of G′ do foreach valuation B of the edge (k, k′) do
if B ∨ k′ = x then add the set B + k′ to the family GMx end end if GMx is empty then GMx = {Jx}; end end label the edge (j, j′) with GMx; return G; end
Algorithm 1: Generation of the dependence graph of a lattice Proposition 1. Algorithm 1 generates the dependence graph, the minimal generators, or the canonical direct basis of a lattice L = (S, ≤) in O(|Σcdb||S||JL|3), i.e. in O(|S||JL|3) per Σcdb-rule or per minimal generator.
Proof. First, computation of the relation δ on the join-irreducibles can be done in O(|S|2|JL|2) by determining, for each x ∈ S, if x is a minimal element in the lattice such that jδxj′.
Computation of edges’s labels is more difficult. One can observe that minimal generators are recursively defined according to the relation ≤ in the lattice. Indeed, if we consider two join-irreducibles such that jδxj′ - with x an element of the lattice - or equivalently jδBj′ - with B minimal generator of x - then B + j′ is a minimal generator of x ∨ j′, thus recursively defined from B. One can distinguish between two cases: – When B is strictly included in Jx, then B can be deduced from a minimal generator of a predecessor of x.
– When B = Jx, then Jx is the only minimal generator of x.
Therefore, a travel of the lattice from the bottom to the top allows to recursively compute minimal generators in O(|Σcdb||S||JL|3).
The dependence graph of a lattice, and thus its canonical direct basis and its
minimal generators, can easily be generated with a binary table as input, after
its concept lattice generation. In particular, Bordat’s algorithm [
In this paper, we introduced the dependence graph as a representation of a finite lattice encoding both its canonical direct basis and its minimal generators. We propose a new generation algorithm with an improvment complexity. This structure can be used in various domains of computer science, such as datamining and knowledge representation. Indeed, the canonical direct basis of rules is a nice basis to represent dependencies between attributes, in a classification task for example. The use of minimal generators could gives raise to an attributs set reduction, usefull for data indexation for example.