Over the last couple of years, the interest in combining probability and logic has grown strongly. This led to the development of different software packages like PRISM, ProbLog and Alchemy, which offer a variety of exact and approximate algorithms to perform inference and learning. What is lacking, however, are algorithms to perform efficient inference in relational temporal models by systematically exploiting temporal and local structure. Since many real-world problems require temporal models, we argue that more research is necessary to use this structure to obtain more efficient inference and learning. While existing relational representations of dynamic domains focus rather on approximate inference techniques we propose an exact algorithm.