Conjunctive Query Answering in ${\mathcal{CFD}}_{nc}$: A PTIME Description Logic with Functional Constraints and Disjointness

Abstract

We consider conjunctive query answering and other basic reasoning services in ${\mathcal{CFD}}_{nc}$, an alternative to the description logic ${\mathcal{CFD}}$ that retains the latter’s ability to support PTIME reasoning in the presence of terminological cycles with universal restrictions over functional roles and also in the presence of functional constraints over functional role paths. In contrast, ${\mathcal{CFD}}_{nc}$ replaces the ability to have conjunction on left-hand-sides of inclusion dependencies with the ability to have primitive negation on right-hand-sides. This makes it possible to say that primitive concepts must denote disjoint sets of individuals, a common requirement with many information sources.