A rectangle of a binary relation R is a couple of two sets (A,B) such that A×B⊆R. Searching for the maximal rectangles of a finite binary relation is a problem which has been previously studied by pure mathematicians within the framework of lattice theory and which has been later proved relevant in several practical fields of computer science. In this paper, the authors study a similar problem (which is NP-complete) of searching for a minimal subset of rectangles which covers a binary relation R. In particular, they propose a strategy for an ‘optimal’ decomposition of a finite binary relation R in the sense that it realizes the maximum of an heuristic gain function (from a storage space gain point of view). The resulting solution (minimal number of rectangles) provides us with a pyramidal covering of R (in the sense that an element of R can belong to several rectangles). As an illustration, the authors apply this decomposition strategy for structuring a toy indexed documentary database where ℝ5R is the binary relation between a set ℝ5D of documents and a set ℝ5T of terms used for indexing these documents (i.e. ℝ5R⊆ℝ5D×ℝ5T).
