  A relational structure is homomorphism-homogeneous if every homomorphism
between finite substructures extends to an endomorphism of the structure. This
notion was introduced recently by Cameron and Ne\v{s}et\v{r}il. In this paper
we consider a strengthening of homomorphism-homogeneity --- we call a
relational structure polymorphism-homogeneous if every partial polymorphism
with a finite domain extends to a global polymorphism of the structure. It
turns out that this notion (under various names and in completely different
contexts) has been existing in algebraic literature for at least 30 years.
Motivated by this observation, we dedicate this paper to the topic of
polymorphism-homogeneous structures. We study polymorphism-homogeneity from a
model-theoretic, an algebraic, and a combinatorial point of view. E.g., we
study structures that have quantifier elimination for positive primitive
formulae, and show that this notion is equivalent to polymorphism-homogeneity
for weakly oligomorphic structures. We demonstrate how the Baker-Pixley theorem
can be used to show that polymorphism-homogeneity is a decidable property for
finite relational structures. Eventually, we completely characterize the
countable polymorphism-homogeneous graphs, the polymorphism-homogeneous posets
of arbitrary size, and the countable polymorphism-homogeneous strict posets.
