However, a new extraction of concepts in the projected database would be expensive. Furthermore, the original data are perhaps not available anymore (for privacy purposes for example). If the collection of concepts in the whole database is still available, a natural question is whether it is possible to compute **the collection of concepts**
in the projected database from the concepts in the whole database (i.e., to find the operation corresponding to the dotted arrow in Fig. 2).

In other words, we want to be able to compute Concepts(πA(Db**)) from**
Concepts(Db) without having to perform an extraction in πA(Db). It is indeed possible. First, we need to define an A**-equivalence relation on the concepts.**
Definition 1 (A-equivalence). Given a set A of attributes, two concepts (X, Y ) and
(X
′, Y ′) are A**-equivalent iff** X ∩ A = X
′ ∩ A.

This is obviously an equivalence relation. Figure 2 gives an **example of the equivalence classes. Furthermore, we have the following proposition:**
Proposition 1. The A**-equivalence classes have a least element (for** ).

To prove this proposition, we use the following well known result: if C1 = (X1, Y1)
and C2 = (X2, Y2) are two concepts, then there exists a concept C = (X1 ∩ X2, Y )
with Y1 ∪ Y2 ⊆ Y .

Proof. Given two A-equivalent concepts C1 = (X1, Y1) and C2 = (X2, Y2**), then there**
exists a third concept C = (X1 ∩ X2, Y **) with** Y1 ∪ Y2 ⊆ Y .

Of course, C is A-equivalent to C1 and C2 and we also have C  C1 and C  C2
(by definition of ).

Therefore, the A-equivalence class of C1 and C2 **has only one minimum element,**
i.e., it has a least element.

⊓⊔
The following theorem characterizes the collection Concepts(πA(Db**)) with respect**
to Concepts(Db).

Theorem 1. Given a database Db and a set of attributes A, we denote by LEA the set of the least elements of the A**-equivalence classes. Then**
Concepts(πA(Db)) = {(X ∩ A, Y ) | (**X, Y** ) ∈ LEA}.

Proof. In this proof, we use the fact that if (X, Y ) is a concept in πA(Db**) then it can**
be "extended" to form a concept (X′, Y ) in Db **where** X′ ∩ A = X.

First inclusion ⊆ :
Let (X, Y ) be a concept in πA(Db**). We can "extend" it to a concept (**X
′, Y **) of** Db.

Let (X′′, Y ′′) be a concept A-equivalent to (X′, Y ) such that (X′′, Y ′′)  (X′, Y ).

(X
′′ ∩ A, Y ′′) = (X, Y ′′) is a 1-rectangle of πA(Db**). Since** Y ⊆ Y
′′ and (X, Y **) is a**
concept of πA(Db), Y and Y
′′ **are equal. Therefore (**X
′′, Y ′′**) is included in (**X
′, Y )
and therefore X′′ = X′ which means that (X′′, Y ′′) = (X′, Y ) and (X′, Y **) is the least**
element of its A**-equivalence class.**
Inclusion ⊇ :
Let (X, Y ) ∈ LEA. Then (X∩A, Y ) is a 1-rectangle in πA(Db**). Suppose that there exists**
a 1-rectangle (X
′, Y ′) in πA(Db**) such that (**X
′, Y ′) ⊇ (X ∩ A, Y **). Then** X
′ = X ∩ A
otherwise (X ∪ X
′, Y ) is a 1-rectangle strictly containing (X, Y ) and therefore (**X, Y** )
cannot be a concept. We can extend (X′, Y ′) = (X ∩ A, Y ′) to a concept (X′′, Y ′) of