Multi-relational data mining has become popular due to the limitations of propositional problem definition in structured domains and the tendency of storing data in relational databases. Several relational knowledge discovery systems have been developed employing various search strategies, heuristics, language pattern limitations and hypothesis evaluation criteria, in order to cope with intractably large search space and to be able to generate high-quality patterns. In this work, we improve an ILP-based concept discovery method, namely Confidence-based Concept Discovery (C 2D) by removing the dependence on order of target instances in the relational database. In this method, the generalization step of the basic algorithm of C 2D is modified so that all possible frequent rules in Apriori lattice can be searched in an efficient manner. Moreover, this improved version directly finds transitive rules in the search space. A set of experiments is conducted to compare the performance of proposed method with the basic version in terms of support and confidence. © 2008 IEEE.