Data Complexity of Instance Checking in the EL Family of Description Logics

TitleData Complexity of Instance Checking in the EL Family of Description Logics
Publication TypeThesis
Year of Publication2007
AuthorsKrisnadhi, A
DegreeMaster of Science
Number of Pagesv+68
Date Published03/2007
UniversityTechnische Universit├Ąt Dresden
Thesis TypeMaster's

Subsumption in the description logic (DL) EL is known to be tractable even when it is done with respect to the most general form of terminology, namely a set of general inclusion axioms (GCIs). Recently, this tractability boundary has been clarified by identifying DL constructors that causes intractability of subsumption when added to EL and that do not. These results provide us with a characterization of the complexity of subsumption for the EL family of DLs (i.e., EL and its extensions).

Besides subsumption, there are other standard reasoning problems studied in DL. Among them, the instance checking problem is the most basic reasoning problem that is concerned with deriving implicit knowledge about individuals in a DL knowledge base. Such a knowledge base consists of an intensional part in the form of a terminology (TBox) and an extensional or data part in the form of assertions about particular individuals in the domain of the knowledge base (ABox). Like other reasoning problems, complexity of instance checking is usually measured in the size of the whole input - thus called combined complexity - which, in this case, consists of a TBox, an ABox, a query concept and an individual name. On the other hand, it is common to assume that the data (ABox) is very large compared to the TBox and the query. Therefore, it is often more realistic to use a complexity measure based only on the size of the ABox, i.e., data complexity.

For the EL family, results for the combined complexity of instance checking can be derived from the complexity results for subsumption. But results which are concerned with data complexity are still lacking. This motivates us to investigate the data complexity of instance checking in the EL family. In particular, we are interested in whether there are extensions of EL which are intractable regarding combined complexity, but tractable regarding data complexity.

The first part of this thesis establishes coNP-hardness (and even coNP-completeness) results regarding data complexity of instance checking w.r.t. sets of GCIs for extensions of EL with negation, disjunction, value restriction, number restriction and role constructors such as role negation, role union and transitive closures. The lower bounds of data complexity for these DLs are proved by polynomial reductions from the complement of 2+2-SAT, a variant of propositional satisfiability problem which is NP-complete, whereas the upper bounds follow from known results of data complexity for ALC and SHIQ.

The second part identifies an extension of EL called ELIf, for which data complexity of instance checking w.r.t. sets of GCIs is tractable. The DL ELIf is obtained from EL by adding inverse roles and global functionality. This result is interesting since adding only one of those two constructors leads to intractability of reasoning w.r.t. combined complexity. The result is derived by giving an algorithm that decides instance checking in ELIf w.r.t. sets of GCIs and runs in time polynomial in the size of the input ABox.

Refereed DesignationDoes Not Apply