Discrete-time relational dynamical systems are mathematical models of possibly nonlinear and nondeterministic, state-based transition systems. They describe the time evolution of forests, viruses, parallel programs or cooperating agents. This thesis develops the compositional analysis of iterated relations: we study dynamical and computational properties of composed systems by combining the individual analyses of their components, simplified by abstraction techniques. We present a structural view of dynamical complexity, and a strict computational hierarchy of systems. Classical case studies are successfully analyzed: low-dimensional chaotic systems (logistic map, Smale horseshoe map, Cantor relation), high-dimensional complex systems (cellular automata), as well as formal systems (paperfoldings, Turing machines).