The ultimate goal of CBR applications is to satisfy customers using this technology in their daily business. As one of the crucial issues in CBR for practical applications, maintenance is important to cope with demands changing over time. Review and restore are the two steps in CBR that deal with tasks of maintenance. In order to perform these tasks, we suggested case and case base properties, quality criteria, and restore operators in earlier publications. In this paper, we specify concrete performance measures that correspond to general customer requirements, and analyze the relations between these performance criteria, case properties, and restore operators. We present initial results on theoretical analyzes on these relations, and report on examples of experimental studies that indicate that the suggested case properties and the respective restore operators help to identify maintenance strategies in order to optimize performance of CBR systems over time.