A novel query language for database mining, called RDM, is presented. RDM provides primitives for discovering frequent patterns and association rules, for manipulating example sets, for performing predictive and descriptive induction and for reasoning about the generality of hypotheses. RDM is designed for querying deductive databases and employs principles from inductive logic programming. Therefore RDM allows to query patterns that involve multiple relations as well as background knowledge. The embedding of RDM within a programming language such as PROLOG puts database mining on similar grounds as constraint programming. An operational semantics for RDM is outlined and an efficient algorithm for solving RDM queries is presented. This solver integrates Mitchell’s versionspace approach with the well-known APRIORI algorithm by Agrawal et al.