The adaptation knowledge container of a CBR system is often represented by adaptation rules that can be learned from the case base using various approaches proposed in the CBR literature. However, the formal representation of such rules has been much less investigated. This paper introduces a formalism for representing such rules, given a formalism that can be used to express cases in an attribute-value formalism. One benefit of this study is a case retrieval algorithm for which the retrieved case is the best one with respect to adaptation (i.e. the one that requires the least adaptation effort as defined by the cost of adaptation rule sequences). Moreover, when attributes have Boolean range, its complexity is independent of the size of the case base.