We use a simple relational framework to develop the key notions and results on hidden variables and non-locality. The extensive literature on these topics in the foundations of quantum mechanics is couched in terms of probabilistic models, and properties such as locality and no-signalling are formulated probabilistically. We show that to a remarkable extent, the main structure of the theory, through the major No-Go theorems and beyond, survives intact under the replacement of probability distributions by mere relations. In particular, probabilistic notions of independence are replaced by purely logical ones. Thus relational models provide a kind of window through which to study the space of physical theories. We also study the relationships between quantum systems, probabilistic models and relational models. A number of algorithmic questions arise naturally; some surprising connections to Dependence Logic are also beginning to emerge.