A Bayesian network can represent any distribution over a given set of random variables [33, 69], and this flexibility has been used to great effect in a variety of applications [107]. Many of these applications contain repetitive patterns of entities and relationships. Thus it is not surprising that practical concerns have led to modeling languages where Bayesian networks are specified using relations, logical variables, and quantifiers [46, 109]. Some of these languages enlarge Bayesian networks with plates [47, 83], while others resort to elements of database schema [44, 58]; some others mix probabilities with logic programming [104, 116] and even with functional programming [85, 89, 100]. The spectrum of tools that specify Bayesian networks by moving beyond propositional sentences is vast, and their applications are remarkable. Yet most of the existing analysis on the complexity of inference with Bayesian networks focuses on a simplified setting where nodes of a network are associated with categorial variables and distributions are specified by flat tables containing probability values [73, 113]. This is certainly unsatisfying: as a point of comparison, consider the topic of logical inference, where much is known about the impact of specific constructs on computational complexity — suffice to mention the beautiful and detailed study of inference complexity in description logics [3]. In this paper we examine the complexity of inferences in Bayesian networks as dependent on the language that is used to specify the networks. We adopt a simple specification strategy inspired by probabilistic programming [105] and by structural equation models [99], where a Bayesian network over binary variables is specified by a set of logical formulas and a set of independent random variables. As we show in the paper, this abstract specification strategy captures a vast range of modeling languages in the literature. To illustrate the sort of specification we contemplate, consider a short example that will be elaborated later. Suppose we have a population of students, and denote by fan(x ) the fact that student x is a fan of say a particular band. And write friends(x , y) to indicate that x is a friend of y. Now consider a Bayesian network with a node fan(x ) per student, and a node friends(x , y) per pair of students (see Figure 1). Suppose each node fan(x ) is associated with the assessment P(fan(x ) = true)=0.2. And finally suppose that a person is always a friend of herself, and two people are friends if they are fans of the band; that is, for each pair of students, friends(x , y) is associated with the formula friends(x , y) ↔ (x = y) ∨ (fan(x ) ∧ fan(y)). (1) Now if we have data on some students, we may ask for the probability that some two students are friends, or the probability that a student is a fan. We may wish to consider more sophisticated formulas specifying friendship: how would the complexity of our inferences change, say, if we allowed quantifiers in our formula? Or if we allowed relations of arity higher than two? Such questions are the object of our discussion. We can thus parameterize computational complexity by the formal language that is allowed in the logical formulas; we can move from sub-Boolean languages to relational ones, in the way producing languages that are similar in power to plate models [47] and to probabilistic relational models [72]. Overall we follow a proven strategy adopted in logical formalisms: we focus on minimal sets of constructs (Boolean operators, quantifiers) that capture the essential connections between expressivity and complexity, and that can shed light on more sophisticated languages. Our broader goal is to help with the design of knowledge representation formalisms, and in that setting it is important to understand the complexity introduced by language features, however costly those may be.