Abstract: While dealing with multi-relation, traditional data mining algorithms used physical join, thus it had the problem of low efficiency. In order to solve this problem, the problem of classification in multi-relational data mining was investigated, and an efficient multi-relational Bayesian classification algorithm called EMBC was proposed. EMBC aims at increasing the accuracy of classification, and decreasing running time. By taking advantage of tuple ID propagation approach, and combined with naive Bayesian classification algorithm, EMBC can directly classify in multi-relation. Performance results demonstrate that, EMBC increases the accuracy of classification, and significantly decreases running time.