be impossible to query the set of objects of the concepts without recomputing them.

We propose to use a labeled graph: the Hasse diagram of the order  **on the**
collection of concepts: the vertices are the concepts and there is **an edge** X → Y between the concepts X and Y iff Y cover X, i.e., X ≺ Y **and it does not exist** a concept Z such that X ≺ Z ≺ Y . We add two special vertices: ⊥ and ⊤ **such** that (X, Y ) ≺ ⊤ and ⊥ ≺ (X, Y ) for all (**X, Y** ).

We can choose to put the labels on the edges or on vertices: On the vertices:
the label consists of the two sets X and Y . On the edges: on the edge (**X, Y** ) →
(X′, Y ′) the label consists of the sets X′ \ X and Y \ Y
′
.

Figure 1 shows an example of the constructed graph with the collection of all the concepts in the database.

With this representation, we do not need to order the attributes or the objects and we will show that it is easy to query this representation.

## 4 Construction Of The Graph Representation

Given a list of concepts extracted by a concept extraction algorithm such as D-miner [1], the following algorithm constructs the graph representing the collection. In fact this algorithm is a common release of classical algorithms that have been investigated by the Formal Concept Analysis community [17] in order to build a graph representation of concepts. As this is not the core **of our paper,** we do not provide too much details on this construction.

The idea of the construction of the graph is to start from a graph representing the empty collection (which contains only the vertices ⊤ and ⊥**) and to insert** the other concepts in the graph one after the other. In order to **simplify the**
algorithm, we choose to add the concepts (X, Y **) in order of the increasing size** of X.

When a new concept C = (X, Y **) is inserted, there is no other concept** C
′

in the graph such that C  C
′
**(because of the order in which the concepts are**
inserted). Therefore, the only successor of C is ⊤ and an arc C → ⊤ **is added.** Next, we must find all predecessors C
′ of C **in the graph (i.e., the concepts** C
′

in the graph such that C **covers** C
′
**) to create the arcs** C
′ → C.

For this purpose, a depth first traversal of the graph is performed (starting from ⊤). The whole graph does not need to be traversed: each time that a **concept** C
′
covered by C **is found, there is no need to explore the concepts smaller than**
C
′
(for **) since none of them can be covered by** C.

Finally, if C **covers a concept** C
′
that was covered by ⊤**, the edge** C
′ → ⊤
must be removed (since ⊤ **no longer covers** C
′
).

This is implemented by the algorithm construct graph**. It uses functions**
to manipulate the graph (insert vertex, insert edge and delete edge **which** are not detailed) and call a procedure insert concept **to insert the next concept** in the graph. This procedure call a recursive procedure rec insert **to traverse**
the graph (the set E is used to "mark" the vertices that have been explored).