The Aldous--Hoover Theorem characterizes arrays of random variables which are exchangeable - that is, the distribution is invariant under permutations of the indices of the array. We consider the extension to exchangeable Markov chains. In order to give a satisfactory classification, we need an extension of the Adous--Hoover Theorem to "relatively exchangeable" arrays, which are only invariant under some permutations. Different families of permutations lead to different characterization theorems, with the crucial distinction coming from a model theoretic characterization of the way finite arrays can be amalgamated.