Summary: In this paper, we improve the construction of triangulation and junction tree in propagation algorithm by decomposing the moral graph of a Bayesian network into its prime blocks. It is proved that the problem of finding optimal triangulation can be split into smaller and independent problems on the prime blocks without losing optimality. Thus, the union of optimal triangulations of all the prime blocks is the desired optimal triangulation of a Bayesian network. Furthermore, we give an algorithm to construct a clique junction tree of the optimal triangulation by connecting clique junction trees of the optimal triangulations. Experiments are shown to evaluate the performance of decomposition in compilation stage of propagation algorithm.