We consider the consequences on basic reasoning problems of the Krom extension to the description logic dialect CFDI_(nc)~(any-), that is, of allowing negated primitive concepts on left-hand-sides of inclusion dependencies. Specifically, we show that TBox consistency and concept satisfiability remain in PTIME, but that this extension leads to intractability for both knowledge base consistency and instance retrieval. We then trace the roots of intractability by presenting tight conditions that recover PTIME complexity for both of these problems. The conditions relate to the structure of functional constraints in CFDI_(nc)~(any-) and to the unique name assumption.
展开▼
