Case based reasoning (CBR) is a methodology where new problems are solved by investigating, adapting and reusing solutions to a previously solved, similar problem. Hereby knowledge is deduced from the characteristics of a collection of past cases, rather than induced from a set of knowledge rules that are stored in a knowledge base. In this paper we describe how fuzzy CBR techniques can be used to enhance the accessibility of relational databases, more specifically, flexible querying of regular relational databases. Two approaches are discussed: an approach where a database system is extended with a standalone instance-based prediction facility and an approach where such a prediction facility is embedded as an extension of the relational algebra. In both approaches, fuzzy set theory is used for the gradual modelling of similarity. Furthermore, its related possibility theory is used for the modelling of query satisfaction and for the handling of the inevitable uncertainty that occurs when predictions are made.