Assume that we are given as input a database \(_0\) , an ontology
, and a \(k\) -expression \(s_0\)  that generates \(_0\) . We may
assume w.l.o.g. that takes the form
\(\lbrace  \top \sqsubseteq C_\rbrace \)  where \(C_\)  is an -concept in
negation normal form (NNF), that is, negation is only applied to
concept names, but not to compound concepts. Every -ontology can be converted into this form in linear time
[1]}.
