Applications and Extensions of PTIME Description Logics with Functional Constraints

1 Introduction

The need to provide better guarantees on performance has prompted a resurgence of interest in ontology languages for which various reasoning tasks have PTIME complexity. The latest version of the OWL web ontology standard [W3C, 2008] reflects this trend by including so-called profiles. Notably, two of these are based on the description logics (DLs) EL++ [Baader et al., 2005] and DL-Lite [Calvanese et al., 2007], each of which has PTIME complexity for the fundamental task of deciding concept subsumption. In this paper, we consider a third DL with PTIME complexity for this problem, called CFD [Khizder et al., 2000], that can also serve as the basis for an OWL profile.

CFD is designed for ontologies that require an ability to express universal restrictions over functional roles, that have terminological cycles and that also require more general ways of expressing identification constraints such as composite keys and functional dependencies. This combination of features makes CFD another option to DL-Lite for integrating ontological knowledge about formatted data sources such as those conforming to underlying relational database schemata, a very common circumstance for many web applications. To illustrate, one can say the following about a hypothetical human resources data source in CFD:

∗Preliminary version appeared in [Toman and Weddell, 2008].

The statements assert that an employee is supervised by a boss and has a unique phone number within a given city, and also that a boss is an employee that is more specifically supervised by a director. In contrast, EL++ is not able to capture (abstract) functionality and functional restrictions such as keys, the first two statements for example, and DL-Lite is not able to capture additional conditions on attributes or roles that might be satisfied by subclasses, as in the case of the last statement about the supervision of bosses. However, both EL++ and DL-Lite are able to capture disjointness conditions which is not possible in CFD, as we show. Also note that Calvanese et al. [Calvanese et al., 2008] have recently extended DL-Lite with a path-based variety of identification constraints. Consequently, DL-Lite is now able to capture the second statement in (1).

We review and extend the earlier work on CFD, first considering the problem of reasoning about concept subsumption with respect to a CFD TBox, and then considering the problem of computing certain answers for a large subclass of conjunctive queries with respect to a CFD knowledge base consisting of both a TBox and ABox. In both cases, we consider the effect on the complexity of these problems with respect to the addition of concept constructors for expressing concept union and the bottom (unsatisfiable) class. In particular, in Sections 2 and 3, we show the following for CFD (with a TBox that may contain terminological cycles).

1. The problem of determining if a particular concept subsumption, called a posed question, is logically implied by the TBox is in PTIME. Our proof is based on a reduction of the problem to a Horn formulation over a finite universe, a much simpler approach than the procedure outline in [Khizder et al., 2000], and one that enables a more transparent consideration of extensions to CFD that follow.
2. This problem is coNP-complete if one adds a concept constructor that expresses concept union to CFD.
3. The problem is PSPACE-complete if, alternatively, one adds a concept for the bottom class.

1. The problem is ultimately EXPTIME-complete if one adds concept constructors for both concept union and the bottom class.

We also consider extending the expressiveness of posed questions to allow primitive negation, disjunction, general negation and inverse features, and show the effect of these extensions on the complexity of the implication problem, in particular when measured only in the size of the posed question.

We then consider the problem of computing certain answers to a family of attribute-connected conjunctive queries over an arbitrary CFD knowledge base. Such queries are more general than those that can be folded into a single concept description in more typical DLs and include, for example, queries with existential restrictions corresponding to foreign-key joins. We show how all of the above complexity bounds for the concept subsumption problem for CFD and its extensions transfer to this second problem.

The remainder of this section introduces CFD, in particular, the definitions related to the logical implication problem for inclusion dependencies that are needed for an understanding of the results in Sections 2 and 3. Additional definitions concerning ABox reasoning are left to the start of Section 4 in which we consider certain answer computation. We conclude in Section 5 and 6 with a discussion of related work and with summary comments.

1.1 The Description Logic CFD

A formal definition of the syntax and semantics and of the logical implication problem of CFD follows. Note that CFD itself is based on attributes (also called features) instead of the more common case of roles (which are easily accommodated by reification [Toman and Weddell, 2005a]).

SYNTAX SEMANTICS: "(·)I " C::=A | C1 ⊓ C2 (C1)I ∩ (C2)I D::=C | D1 ⊓ D2 (D1)I ∩ (D2)I | ∀Pf .C {x : (Pf)I (x) ∈ (C)I } | C : Pf1, ..., Pfk →Pf {x : ∀y ∈ (C)I . ∧ki=1 (Pfi)I (x) = (Pfi)I (y) ⇒ (Pf)I (x) = (Pf)I (y)} E::=C | ⊥ ∅ | E1 ⊓ E2 (E1)I ∩ (E2)I | ∀Pf .E {x : (Pf)I (x) ∈ (E)I } | (Pf1 = Pf2) {x : (Pf1)I (x) = (Pf2)I (x)}

Definition 1 (The logic CFD) Let F and A be disjoint sets of (names of) attributes and primitive concepts, respectively. A path expression Pf is a word in F∗ with the usual convention that the empty word is denoted by Id and concatenation by ".". Concept descriptions are defined by the grammar on the left-hand-side of Figure 1. A concept produced by the "C : Pf1, . . . , Pfk → Pf" production of this grammar is called a path functional dependency (PFD). In addition, any occurrence of a PFD must adhere to one of the following two forms:

An inclusion dependency C is an expression of the form C ⊑ D. (Note the distinction of concept descriptions that can appear on the left- and right-hand sides of C.) A terminology (TBox) T consists of a finite set of inclusion dependencies. A posed question Q is an expression of the form E1 ⊑ E2.

The semantics of expressions is defined with respect to a structure (△, ·I ), where △ is a domain of "objects" and (.)I an interpretation function that fixes the interpretation of primitive concepts A to be subsets of △ and attributes f to be total functions (f )I : △ → △. The interpretation is extended to path expressions by interpreting the empty word (Id) as the identity function λx.x, concatenation as function composition, and to derived concept descriptions C, D and E as defined on the right-hand-side of Figure 1.

An interpretation satisfies an inclusion dependency C ⊑ D (resp. a posed question E1 ⊑ E2) if (C)I ⊆ (D)I (resp. (E1)I ⊆ (E2)I ).

The logical implication problem asks if T |=Qholds; that is, for a posed question Q, if Q is satisfied by any interpretation that satisfies all inclusion dependencies in T .

The conditions imposed on PFDs in (2) distinguish, for example, PFDs of the formC : f → Id and C : f → g from PFDs of the form C : f → g.h. The strategic advantage of these conditions is that chase procedures can employ a simple saturation strategy for PFDs that will "fire" them unconditionally, a process that would otherwise not terminate. Indeed, we rely on this in presenting a PTIME procedure for the implication problem in the next section.

Note that the conditions are still satisfied by PFDs that correspond to arbitrary keys or functional dependencies in the sense of the relational model. Indeed, we have found that the conditions do not appear to hinder any modeling utility of CFD for ontologies that occur in practice. Moreover, relaxing the boundary conditions, such as allowing PFDs of the form C : f → g.f, already leads to undecidability [Toman and Weddell, 2006].

To illustrate, consider our introductory example relating to a hypothetical human resources data source. The statements in (1) can be captured in CFD as follows:

In particular, the ith statement in (1) is captured by the ith inclusion dependency in (3) above.

There are two final things to note about the grammar. First, in presenting our PTIME procedure in the next section and again when considering the addition of the bottom class to CFD in Section 3, we presume each inclusion dependency in a TBox T has the form A1 ⊓ · · · ⊓Ak ⊑ D for Ai a primitive concept. Second, although the grammar does not allow a PFD to appear directly in a posed question, the following lemma establishes that an indirect check for the logical implication of such concepts can be easily simulated.

Lemma 2 Let T be a CFD terminology and E1 ⊑ E2 : Pf1, . . . , Pfk → Pf be a posed question in an extension of CFD (that allows such a construct in posed questions). Then there is a posed question Q in CFD such that T |= E1 ⊑ E2 : Pf1, . . . , Pfk →Pf iff T |=Q.

Proof (sketch): Define Q to be the subsumption

where f and g are attributes not occurring in T . ✷

2 The Polynomial Case

We first show that the logical implication problem for CFD is in PTIME. Our proof is based on encoding a given problem as a collection of Horn clauses. The reduction introduces terms that correspond to path expressions, and relies on the fact that the number of required terms is polynomial in the size of the problem itself.

Definition 3 (Expansion Rules) Let T and Q be a CFD terminology and a posed question, respectively. We write CON(T ,Q) to denote the set of all subconcepts appearing in T and Q, define PF(T , Q) as

{Pf . Pf ′ | Pf is a prefix of a path expression in Q and Pf ′ is a path expression in T or Id},

write CC to denote unary predicates for C ∈ CON(T , Q), and introduce the binary predicate E, with all predicates ranging over the universe PF(T ,Q). The expansion rules for a given terminology T , denoted R(T ), are defined in Figure 2.

Figure 2: EXPANSION RULES.

A goal for each concept E is a set of ground assertions defined as follows:

Given two concept descriptions E1 and E2, we say that

if GE2 ⊆ M for every ground model M of R(T ) over PF(T ,Q) that contains CE1 (Id).

Intuitively, PF(T ,Q) represents a finite graph of objects, predicates E(Pf1, Pf2) express equality of the objects at the end of paths Pf1 and Pf2, and predicates CC′(Pf) express that the object at the end of path Pf is in the interpretation of concept C′ .

Our PTIME result for the CFD implication problem follows by a simple check for goals occurring in a ground model for expansion rules generated by a polynomial sized collection of path expressions.

Theorem 4 Let T be a CFD terminology and Q a posed question of the form E1 ⊑ E2. Then

Proof (sketch): The least model of R(T )∪{CE1 (Id)}, if one exists, can be extended to a model of T . Since the original model is the least model, it suffices to determine whether E2 subsumes E1 in (the extension of) this model. ✷

Since the expansion rules are Horn clauses over a finite universe PF(T ,Q) of polynomial size, we have the following:

Corollary 5 Let T and Q denote a terminology and posed question in CFD. Then the implication problem T |= Q is decidable in PTIME.

Proof (sketch): The least model of R(T ) ∪ {CE1 (Id)} can be obtained by using a bottom-up construction of the least fix-point of the rules in time polynomial in |T | + |Q|. ✷

In practice, elements of this set can be constructed on demand by using additional Horn rules in such a way that only path expressions needed to confirm subsumption or nonsubsumption are generated.

3 Intractable Extensions

We now consider the consequences of the various extensions to CFD outlined in our introductory comments. The extensions add options for the right-hand-sides of inclusion dependencies and are illustrated in Figure 3. We begin by considering the case for concept union. Subsection 3.2 then considers an alternative addition of a constructor for the bottom class, and Subsection 3.3 considers the addition of both constructors. Finally, in Subsection 3.4, we consider consequences of various extensions to a posed question.

3.1 The Coverage Case: CFD⊔

To handle disjunction in right-hand sides of inclusion dependencies, we extend the expansion rules with "or" rules as follows:

This rule is added to the expansion rules used for the polynomial case. The intuition behind using this rule is to nondeterministically find a model with an object that belongs to the left-hand side of the posed question but which does not belong to the right-hand side.

Theorem 6 Let T be a CFD⊔ terminology and Q a posed question of the form E1 ⊑ E2. Then

Proof (sketch): The proof is similar to the proof of Theorem 4 augmented with a non-deterministic application of the above rule. Thus non-subsumption can be detected using polynomially many non-deterministic guesses. ✷

Corollary 7 Let T and Q denote a terminology and posed question in CFD⊔. Then the implication problem T |= Q is decidable and coNP-complete.

Proof (sketch): To obtain the upper bound, simply apply rules of the form "CC1⊔C2 (Pf) → CC1 (Pf) or CC2 (Pf)" nondeterministically during the construction of a minimal (but not necessarily unique) model of R⊔(T ) ∪ {CE1 (Id)} that yields an counterexample to T |= Q; a construction similar to Theorem 4. Non-implication can be detected in a polynomial number of guesses (is in NP). To obtain the lower bound, we reduce 2+2-SAT to non-implication T ̸|= Q in CFD⊔. ✷

3.2 The Disjointness Case: CFD⊥

We now show that the logical implication problem for CFD becomes PSPACE-complete if the bottom class is allowed in inclusion dependencies. This is also accomplished by appealing to our construction in Section 2, expanding in particular on the issue of "completing" the construction of counterexample interpretations.

Definition 8 (Satisfiable Atomic Type) Let T denote a finite set of primitive concepts. An atomic type over T is the concept ⊓A∈TA. We say that T is satisfiable with respect to a CFD⊥ terminology T if there is an interpretation IT such that IT |= T and (⊓A∈TA)I ̸= ∅.

Lemma 9 Let T be a CFD⊥ terminology and T a finite set of primitive concepts. The problem of determining if T is satisfiable with respect to T is decidable and in PSPACE.

Note that it is easy to construct terminologies (using only ⊓ and ∀f.) in which a contradiction is found only after exponentially many steps (of f). We use a reachability search algorithm to detect these situations. Since the graph of all atomic types T is exponential in the size of the terminology, the reachability of an unsatisfiable atomic type starting from T can be determined in PSPACE.

Theorem 10 Let T be a CFD⊥ terminology and Q a posed question of the form E1 ⊑ E2. Then T |= Q iff either

1. C⊥(Pf) ∈M for some Pf ∈ PF(T ,Q), or
2. the set {A ∈ CON(T ,Q) | CA(Pf) ∈ M, A primitive} is unsatisfiable w.r.t. T for some Pf ∈ PF(T ,Q), or
3. GE2 ⊆M

holds in the minimal model M of R(T ) ∪ {CE1 (Id)}.

Proof (sketch): The construction of a counterexample follows the construction in the proof of Theorem 4. However, the completion of the interpretation by infinite trees now depends on the existence of such trees and must be checked using Lemma 9. Note that this also relies on the fact that any interpretation IT that exists for an atomic type T can be made into a tree interpretation. ✷

Corollary 11 Let T and Q denote a terminology and posed question in CFD⊥. Then the implication problem T |= Q is decidable and PSPACE-complete.

Proof (sketch): To show hardness for PSPACE, we reduce the (deterministic) Linear Bounded Automaton Acceptance [Garey and Johnson, 1979; Karp, 1972] to the implication problem in CFD⊥. ✷

3.3 The Boolean Complete Case: CFD⊔,⊥

We now show that adding both disjointness and coverage constraints leads to EXPTIME completeness. In particular, we show how to simulate axioms of the form

Consider the following auxiliary inclusion dependencies relating to primitive concepts occurring in a logical implication problem for CFD:

• Define T as a top-replacement concept and pairs of Ai and ¯Ai as disjoint partitions of the simulated top (and similarly for B and ¯B):

• Propagate the top-replacement concept across all attributes:

Then the pair of inclusion dependencies

simulates the dependency (4) above, and, as a consequence, the decision problem is EXPTIME-hard [Toman and Weddell, 2005a]. To obtain a matching upper bound, we note that CFD⊔,⊥ is a fragment of DLFDE - that is EXPTIMEcomplete [Khizder et al., 2007]. The latter logic is Booleancomplete and thus might be more convenient to use.

3.4 Extensions to the Posed Questions

In this final subsection, we consider several ways that the structure of posed questions for a CFD implication problem might be extended.

Primitive Inequalities and Negations: CFD̸=,(¬)

Extending the grammar for the posed questions with primitive negations, i.e., negated primitive concepts, ¬A, and primitive inequalities, (Pf1 ̸= Pf2), still enjoys a PTIME complexity bound for the logical implication problem.

Theorem 12 Let T be a CFD terminology and Q = E1 ⊑ E2 that allows primitive negations and/or inequalities. Then T |=Q is decidable in PTIME.

Proof (sketch): We replace Q with a (linearly-sized) set of questions that do not use negations or inequalities. The result then follows from Theorem 4. ✷

Similar PTIME results can be obtained for CFD⊥, i.e., when terminologies do not use disjunction and only when complexity is measured solely in |Q|, i.e., under the data complexity assumption. For the extensions that allow disjunctions in the terminology, the data complexity increases to coNP:

Theorem 13 Let T be a CFD⊔ terminology and Q = E1 ⊑ E2 that allows primitive negations and/or inequalities. Then T |=Q is coNP complete.

Proof (sketch): We encode a propositional DNF formula using the concept E1, force a valuation using disjunction in T , encode evaluation of the boolean formula (also in T ), and then test if every such valuation evaluates to true using E2. ✷

Primitive Inequalities and Disjunction: CFD̸=,⊔ or Full Negation: CFD¬

Adding disjunctions to posed questions with primitive negations and/or allowing general negations in posed questions leads to an increase in data complexity.

Theorem 14 Let T be a CFD terminology and Q = E1 ⊑ E2 with disjunctions and inequalities. Then T |= Q is decidable and coNP-complete.

The coNP-completeness result can be lifted to the intractable extensions of CFD under the data complexity assumption.

Inverse Features: CFDinv

Last, we consider adding the inverse feature constructor, ∃f -1 .E, to the grammar for posed questions 1 . Intuitively, such an extension allows for enforcing and checking for existence of additional objects that are not reachable from the objects interpreting E1 and E2 in the posed questions.

To accommodate the new constructor, we extend the set PF(T , Q) to accommodate the new paths that are induced by the new constructor; the extended set is defined as

where o and ai are distinct constants. Intuitively, we create a new constant ai for each instance of the ∃f -1 .D constructor in the posed question. This set is still polynomial in the size of the original problem. Note also that the expansion rules naturally apply to this new set. Hence we can use similar techniques to solve the logical implication problem: we simply extend the definition of GE to accommodate the new constructor by introducing the new constants ai and by using equations to ensure their fi attributes agree with the existing paths as required. However, note that allowing the ∃f -1 .D constructor in the E2 concept of the posed question leads to an increase of complexity: to verify that E2 is entailed by T and E1, a subgraph isomorphism problem must be solved (one needs to match the new constants in E2 to those that originated from E1).

1 Adding inverse to terminologies leads to undecidability in the presence of functional dependencies [Toman and Weddell, 2005b].

Theorem 15 Let T be a CFD terminology and Q = E1 ⊑ E2 with inverse attributes. Then T |= Q is decidable and NP-complete.

The data complexity for CFD⊥ terminologies is also NPcomplete (for the same reasons). For terminologies that allow the ⊔ constructor, the complexity increases to Π2p since matching must be tested in all minimal models of T and E1.

The complexity results for CFD and its extensions are summarized in Figure 4: the superscripts denote the extensions allowed in the terminology T and the subscripts the extensions in the posed questions Q.

4 Query Answering

In this section, we consider the problem of computing certain answers to a family of conjunctive queries over an arbitrary CFD knowledge base that augments a CFD TBox with an ABox.

Definition 16 (The ABox consistency problem for CFD)

Let N be a set of (names of) individuals disjoint from F and A. An ABox A consists of a finite set of assertions of the form C(a) or f (a) = b, where C is a concept description, f ∈ F and {a, b} ⊆ N.

The ABox consistency problem asks if T ∪ A is consistent, that is, if there exists an interpretation that satisfies all inclusion dependencies in T and all assertions in A.

We write Pf(a) = b as shorthand for the equivalent set of primitive ABox assertions with "single use" intermediate individuals.

Proposition 17 Let T be a CFD⊔,⊥ terminology. Then

1. for every ABox A there is a concept E such that T ∪A is not consistent if and only if T |= E ⊑ ⊥; and
2. for every equational concept E there is an ABox A such that T |= E ⊑ ⊥ iff T ∪ A is not consistent.

This proposition is a special case of a result for DLFDE - [Khizder et al., 2007]; we also use a similar representation of the ABox in the proof of Theorem 19 below. Note that, for CFD and CFD⊔, inconsistency cannot be derived. The expansion rules from Definition 3, however, still allow us to construct (a representation) of a minimal model(s) of the TBox and ABox that we shall use to show whether or not a particular tuple of ABox individuals is a certain answer to a query with respect to the given TBox and ABox.

Conjunctive Queries.

The equational constructs in CFD posed questions allow us to characterize certain conjunctive queries as equational concepts. This provides a straightforward approach to query answering over ABoxes. Unfortunately, the equational construct is not powerful enough to capture all conjunctive queries.

Definition 18 A conjunctive query Q is an expression

where Cl and fl are CFD concepts and attributes, respectively. We call the variables xi1 , . . . , xik distinguished.

A query graph for a conjunctive query Q is a directed graph with variables xi of Q playing the role of nodes that are connected by (directed) edges (xi, xj) whenever fi(xi) = xj is an atom in the query Q.

We say that a conjunctive query Q is attribute-connected (resp. connected) if every variable in the query graph of Q is reachable from a distinguished variable along a directed (resp. undirected) path.

Although attribute-connected conjunctive queries disallow some forms of arbitrary conjunctive queries, they do admit non tree-shaped queries that cannot be folded into concept descriptions in common description logics.

We assume a standard definition of query answering under constraints utilizing the certain answer semantics, i.e., the ground instantiation of the head of the query is entailed by the underlying theory T extended with the query Q considered to be a universally quantified implication.

Theorem 19 Let T be a CFD terminology, A an ABox, Q a attribute-connected conjunctive query, and θ a substitution 〈a1/xi1 , . . . , ak/xik 〉 for a1, . . . , ak ABox objects. Then there are equational concepts EA, Eθ, and EQ such that

In addition, EA, Eθ, and EQ can be constructed from A and Q in polynomial time.

Proof (sketch): Let A be an ABox expressing assertions about the set of individuals {a1, . . . , al}. We associate an equational concept EA as follows:

where the attributes h1, . . . , hl do not occur in T ∪A nor in Q. Intuitively, these attributes represent the individual ABox objects.

For an attribute-connected query Q, let Pf ji be a path that leads from a distinguished query variable xi to the variable xj in the query graph of Q. At least one such path that starts from some distinguished variable xi must exist for every variable xj (0 < j ≤ n) in Q (for the distinguished variables, the path can be Id). We define the concept Eθ to capture the substitution θ = 〈a1/xi1 , . . . , ak/xik 〉 as follows:

To determine whether Qθ is a certain answer to Q (under T ∪ A) we create an equational concept EQ as follows:

It is now easy to show that the tuple 〈(h1)I (o), . . . , (hk)I (o)〉 can serve as certain answer to Q whenever o ∈ (EQ)I and vice versa. ✷

This result allows transferring complexity bounds derived in Sections 2 and 3 for the implication problem in CFD and its extensions to answering of path-connected conjunctive queries over an ABox under the certain answer semantics.

A similar approach can be used to determine subsumption for more general connected queries. However, the restriction to at least connected queries is essential to maintain the low complexity:

Theorem 20 The problem of finding certain answers over CFD terminologies and ABoxes is PSPACE-complete even for queries of the form ∃x.C(x) for C a primitive concept.

The restriction is also needed to maintain decidability in the presence of inequalities in queries [Calvanese et al., 1998].

5 RelatedWork

It has been shown that removing the boundary conditions imposed on right-hand-sides of PFDs in CFD makes its implication problem EXPTIME-complete [Khizder et al., 2001], and leads to undecidability of both the implication problems and ABox consistency problems for CFD⊔,⊥ [Khizder et al., 2007; Toman and Weddell, 2006]. It is also easy to see that allowing path agreements in terminologies makes the implication problem for CFD undecidable (by virtue of a straightforward reduction of the uniform word problem [Machtey and Young, 1978]). And it is interesting that: 1) the following two restricted cases have decidable decision problems:

• allowing arbitrary PFDs in terminologies, or
• allowing path agreements in the posed question;

but that 2) the combination of these two cases leads to undecidability [Khizder et al., 2007].

PFDs were first introduced and studied in the context of object-oriented data models [Ito and Weddell, 1994; Weddell, 1989]. Subsequently, an FD concept constructor was proposed and incorporated in Classic [Borgida and Weddell, 1997], an early DL with a PTIME reasoning procedure, without changing the complexity of its implication problem. The generalization of this constructor to unrestricted PFDs alone leads to EXPTIME completeness of the implication problem [Khizder et al., 2001], a complexity that remains unchanged in the presence of additional concept constructors common in rich DLs such as roles, qualified number restrictions, and so on [Toman and Weddell, 2001; 2004]. PFDs have also been applied to a number of applications in objectoriented schema diagnosis and synthesis [Biskup and Polle, 2000; 2003], in query optimization [DeHaan et al., 2003; Khizder et al., 2000] and in the selection of indexing for a database [Stanchev and Weddell, 2003]. Finally, we note that CFD compliments EL++ [Baader et al., 2005] and DL-Lite [Calvanese et al., 2007] as an additional DL-based option for PTIME OWL profiles.

6 Summary

We have reviewed and extended earlier work on CFD, a dialect of description logic with universal restrictions over functional roles that allows terminological cycles in a given TBox. Notably, CFD includes a concept constructor that can capture a general form of functional constraint that can in turn be used to express, among other things, TBox constraints for capturing knowledge that relates to object identification. CFD complements existing dialects such as EL++ and DL-Lite with PTIME reasoning procedures. In particular, we have shown that both the concept implication problem and the problem of computing certain answers for a CFD knowledge base for an important family of conjunctive queries have PTIME procedures. We have also considered the effect on the complexity of these problems following the addition of concept constructors for expressing concept union and the bottom class, showing for each possible extension that the complexity becomes progressively more intractable. Finally, we considered extending the expressiveness of posed questions to allow primitive negation, disjunction, general negation and inverse features, and have shown the effect of these extensions on the complexity of the associated implication problems when measured in the size of the posed question.