Integrating the expressive power of first-order logic with the probabilistic reasoning power of Bayesian networks has attracted the interest of many researchers. We review many techniques for integration of first-order logic and Bayesian networks and propose a new framework that exploits the translation of logical knowledge into Bayesian networks. We present a new search algorithm, relation search, to carry out the translation. We prove that Bayesian networks (LBNs, Logical Bayesian Networks) constructed using relation search behave according to our logical intuition. We show by experiment that LBNs can achieve classification accuracy similar to FOIL (First-Order Inductive Learner) classifiers, thus suggesting that most of the probabilistic information contained in a dataset can be exploited by an LBN. As a byproduct of the experiment, a new technique is proposed for improving the accuracy of Bayesian network classifiers. In our framework, Bayesian network composition supported by an ontology can be used to combine LBNs with other Bayesian networks (PBNs, Probabilistic Bayesian Networks).