We propose MRFPDA, an efficient and scalable algorithm for multi-relational frequent pattern discovery. We incorporate in the algorithm an optimal refinement operator to provide an improvement of the efficiency of candidate generation. Furthermore, MRFPDA utilizes a new strategy of sharing computations to avoid redundant computations in the candidate evaluation. In our experiments, it is shown that on small datasets the performance of MRFPDA is comparable with the performance of the state-of-theart of multi-relational frequent pattern discovery, and on large datasets MRFPDA is more scalable than two existing approaches.