Data encodings and their costs

This paper is devoted to developing and studying a precise notion of the "encoding" of a "logical data structure" in a "physical storage structure," that is motivated by considerations of computational efficiency. The development builds upon the notion of an encoding of one graph in another. The cost of such an encoding is then defined so as to reflect the structural compatibility of the two graphs, the (externally specified) costs of "implementing" the host graph, and the (externally specified) set of intended "usage patterns" of the guest graph. The stability of the constructed framework is demonstrated in terms of a number of results; the faithfulness of the formalism is argued in terms of a number of examples from the literature; and the tractability of the model is hinted at by several results and by further references to the literature. © 1978 Springer-Verlag.