This is the first of a series of papers devoted to the thorough investigation of refinement based on an underlying partial relational model. In this paper we restrict attention to operation refinement. We explore four theories of refinement based on an underlying partial relation model for specifications, and we show that they are all equivalent. This, in particular, sheds some light on the relational completion operator due to Woodcock which underlies data refinement in, for example, the specification language Z. It (...) further leads to two simple alternative models which are also equivalent to the others. (shrink)