Multi-relational data mining(MRDM) is concerned with data that contains heterogeneous and semantically rich relationships among various entity types. In this paper, we introduce multi-relational iceberg-cubes (MRI-Cubes) as a scalable approach to efficiently compute data cubes (aggregations) over multiple database relations and, in particular, as mechanisms to compute frequent multi-relational patterns ("itemsets"). We also present a summary of performance results of our algorithm.