We present in this paper the original notion of natural relation, a
quasi order that extends the idea of generality order: it allows the
sound and dynamic pruning of hypotheses that do not satisfy a
property, be it completeness or correctness with respect to the
training examples, or hypothesis language restriction.
Natural relations for conjunctions of such properties are
characterized. Learning operators that satisfy these complex natural
relations allow pruning with respect to this set of properties to take
place before inappropriate hypotheses are generated.
Once the natural relation is defined that optimally prunes the search
space with respect to a set of properties, we discuss the existence of
ideal operators for the search space ordered by this natural relation.
We have adapted the results from [Van der Laag/Nienhuys-Cheng,ECML'94]
on the non-existence of ideal operators to those complex natural
relations. We prove those non-existence conditions do not apply to
some of those natural relations, thus overcoming the previous negative
results about ideal operators for space ordered by theta-subsumption
only.