Pushing the Boundaries of Tractable Ontology Reasoning
Dec 19, 2014 2136 views 
0.25
0.5
0.75
1.25
1.5
1.75
2
We identify a class of Horn ontologies for which standard reasoning tasks such as instance checking and classification are tractable. The class is general enough to include the OWL 2 EL, QL, and RL profiles. Verifying whether a Horn ontology belongs to the class can be done in polynomial time. We show empirically that the class includes many real-world ontologies that are not included in any OWL 2 profile, and thus that polynomial time reasoning is possible for these ontologies.