  Finding a logical formula that separates positive and negative examples given
in the form of labeled data items is fundamental in applications such as
concept learning, reverse engineering of database queries, generating referring
expressions, and entity comparison in knowledge graphs. In this paper, we
investigate the existence of a separating formula for data in the presence of
an ontology. Both for the ontology language and the separation language, we
concentrate on first-order logic and the following important fragments thereof:
the description logic $\mathcal{ALCI}$, the guarded fragment, the two-variable
fragment, and the guarded negation fragment. For separation, we also consider
(unions of) conjunctive queries. We consider several forms of separability that
differ in the treatment of negative examples and in whether or not they admit
the use of additional helper symbols to achieve separation. Our main results
are model-theoretic characterizations of (all variants of) separability, the
comparison of the separating power of different languages, and the
investigation of the computational complexity of deciding separability.
