Abstract:$\mathcal{EL}$ is a tractable description logic serving as the logical underpinning of large-scale ontologies. We launch a systematic investigation of the boundary between tractable and intractable reasoning in $\mathcal{EL}$ under relational constraints. For example, we show that there are (modulo equivalence) exactly 3 universal constraints on a transitive and reflexive relation under which reasoning is tractable: being a singleton set, an equivalence relation, or the empty constraint. We prove a number of results of this type and discuss a spectrum of open problems including generalisations to the algebraic semantics for $\mathcal{EL}$ (semi-lattices with monotone operators).
