The requirement on p **can seem very strong but it is necessary. In order to be able**
to perform the selection after the projection, the projection must not remove too much information from the collection. For instance, if the selection is defined by p(X, Y ) =
(D ∈ X) (i.e., select the concepts containing attribute D**), then this selection does not**
commute with the projection π{A,B,C}**. Indeed, after this projection the information**
whether a concept contained attribute D **is no longer available. There is a similar**
behavior with selection and projection defined on relational tables. If the selection uses an attribute which is suppressed by the projection, the two operations do not commute.

## 5.4 Duality

In the two previous sections, we defined the projection of a collection of concepts on a set A **of attributes. In a dual manner, we can define another projection on a set** O of objects. The dual equivalence relation of the A**-equivalence (Def. 1) can be defined as** follow: two concepts (X, Y **) and (**X
′, Y ′) are O**-equivalent iff** Y ∩ O = Y
′ ∩ O**. Then**
we have the dual of theorems 1 and 2.

## 5.5 Algorithms

In this section, we present the algorithms to actually perform the selection and projection on the graph representation of the collection.

To perform the projection of a collection of concepts C **with respect to a set of**
attributes A, we need to be able to test if a concept is minimal in its A**-equivalence**
class. However, this is not always possible without additional information: it is possible that the collection C **does not contain all the concepts belonging to an equivalence class,**
in this case, we could find a minimum concept in this equivalence class in C **which is**
not the least element of this equivalence class in Concepts(Db).

For instance, suppose C **contains all the concepts of Fig. 2 (before projection) except**
concept (D, **12345). Then, if we compute the projection of this collection with respect** to {A, B, C}, we must be able to detect that (DE, **135) is not a least element of an**
equivalence class. Without additional information, it is not possible without a possibly expensive check in the data.

This is the reason why we add some information in our graph representation. Given a collection C of concepts, we add into the graph the concepts that are "just **outside"**
of the collection. By just outside, we mean the concepts that **are either predecessor or successor of a concept belonging to the collection. These additional concepts**
are marked and are not linked to ⊤ and ⊥ **(they are inserted in the graph with the**
insert marked vertex **function), they are linked only to the concept(s) of the collection which is (are) their predecessor or successor. Of course, when doing selection or**
projection operations, this additional information must be maintained.

The algorithm to perform the projection is given in Alg. 6. For all vertex X**, the**
algorithm computes le[X] which is the least element of the A**-equivalence class of** X.

If this least element is not in the collection, then le[X]=NIL**. The least elements of the**
equivalence classes are inserted in the new graph G
′**and the edges are added to** G
′**. In**
the algorithm, we use the notation proj(X,Y) to denote (X ∩ A, Y ).