In recent years, there have been several proposals that extend the expressive power of Bayesian networks with that of relational models. These languages open the possibility for the specification of recursive probability models, where a variable might depend on a potentially infinite (but finitely describable) set of variables. These models are very natural in a variety of applications, e.g., in temporal, genetic, or language models. In this paper, we provide a structured representation language that allows us to specify such models, a clean model-theoretic semantics for this language, and a probabilistic inference algorithm that exploits the structure of the language for efficient query-answering.