The frequency of a pattern may not be a sufficient indicator for finding meaning patterns from a database. Temporal regularity of pattern appearance can be regarded as another important criterion for measuring the interestingness in several applications. A pattern can be said regular if it appears at a regular interval given by the user in the database. Even though there have been some efforts to discover periodic patterns in time-series and sequential data, none of the existing works is appropriate for discovering the patterns that occur regularly in a transactional database. Therefore, in this paper, we introduce a novel concept of mining regular patterns from transactional databases. We also devise an efficient tree-based data structure, called Regular Pattern tree (RP-tree in short), that captures the database contents in a highly compact manner and enables a pattern growth-based mining technique to generate the complete set of regular patterns in a database for a user-given regularity threshold. Our performance study shows that mining regular patterns with RP-tree is time and memory efficient and it is also highly scalable.