Very expressive Description Logics in the SH family have worst case complexity ranging from EXPTIME to double NEXPTIME. In spite of this, they are very popular with modellers and serve as the foundation of the Web Ontology Language (OWL), a W3C standard. Highly optimised reasoners handle a wide range of naturally occurring ontologies with relative ease, albeit with some pathological cases. A recent optimisation trend has been modular reasoning, that is, breaking the ontology into hopefully easier subsets with a hopefully smaller overall reasoning time (see MORe and Chainsaw for prominent examples).

However, it has been demonstrated that subsets of an OWL ontology may be harder — even much harder — than the whole ontology. This introduces the risk that modular approaches might have even more severe pathological cases than the normal monolithic ones.

In our submission to DL 2014, we analyse a number of ontologies from the BioPortal repository in order to isolate cases where random subsets are harder than the whole. For such cases, we then examine whether the module nearest to the random subset also exhibits the pathological behaviour.

Data
Experiment Data (Ontologies, subsets and their corresponding modules)
Spreadsheets