Information Systems Group

― Knowledge Representation and Reasoning

ConDOR: Consequence-Driven Ontology Reasoning

An ISG project in Knowledge Representation and Reasoning


Ontologies, and ontology based vocabularies, are becoming increasingly important. They provide a common vocabulary together with computer accessible descriptions of the meaning of relevant terms through relationships with other terms. Ontologies play a major role in the Semantic Web and in e-Science where they are widely used in, e.g., bio-informatics, medical terminologies and other knowledge management applications.

In the ConDOR project we investigated novel "consequence driven" reasoning procedures that are much more efficient than existing procedures. We have implemented our new algorithms in a highly optimised reasoning system called ELK, and made this system freely available via the web. The ELK reasoner provides extremely efficient reasoning for very large scale ontologies that use a subset of the OWL language (OWL 2 EL) for which polynomial time reasoning is possible, and has already established itself as the reasoner of choice for such ontologies, providing orders of magnitude performance improvements over existing systems.

Many ontologies in the healthcare and life sciences domains use the OWL 2 EL subset, with SNOMED being a prominent example. SNOMED is now developed and maintained by the International Health Terminology Standards Development Organisation (IHTSDO), an international not-for-profit organisation based in Denmark and funded by member organisations including, e.g., NHS Connecting for Health in the UK.

Reasoning systems are critical for the development and maintenance of such large structured vocabularies (SNOMED contains more than 400,000 terms), being used, e.g., to organise the terms into a subsumption hierarchy, to check the consistency of definitions and to identify equivalent definitions. ELK is used to provide these services in Snow Owl, a state-of-the-art authoring platform for clinical terminologies marketed by B2i Healthcare. According to their product description:

"ELK, Snow Owl's default reasoner, performs description logic classification in parallel on modern multi-core computers. This allows the full international SNOMED CT plus the Australian extensions (830,926 relationships) to be classified and checked for equivalencies in about 10 seconds on a modern desktop computer."

ELK is also used by the Open Biological and Biomedical Ontologies consortium (OBO), whose OBO "foundry" contains a large number of "orthogonal interoperable reference ontologies in the biomedical domain". ELK is used in OBO authoring tools, and it is run continuously by the foundry to check that the foundry ontologies are consistent, both individually and when integrated into a single large ontology.

Finally, in addition to a direct benefit to ontology developers, the project has also benefited the wider UK research community through further consolidation of its already established world leadership in research on knowledge representation and reasoning in general and ontology reasoning in particular.


ConDOR was sponsored by the UK Engineering and Physical Sciences Research Council (EPSRC).

Project Summary


August 2008 to June 2012


Ian Horrocks, Yevgeny Kazakov, and Frantisek Simancik


UK Engineering and Physical Sciences Research Council


CB Reasoner

ELK Reasoner

Key Publications

Vincent Delaitre and Yevgeny Kazakov.
Classifying ELH Ontologies In SQL Databases.
In OWL: Experiences and Directions 2009 (OWLED 2009), Chantilly, VA, United States, October 23-24 2009.
BibTeX-Entry | Pdf | Pdf | Abstract ]

Yevgeny Kazakov.
Consequence-Driven Reasoning for Horn SHIQ Ontologies.
In Bernardo Cuenca-Grau, Ian Horrocks, Boris Motik, and Ulrike Sattler, editors, Description Logics, volume 477 of CEUR Workshop Proceedings., 2009.
BibTeX-Entry | Pdf | Pdf (197K) ]

Yevgeny Kazakov.
Consequence-Driven Reasoning for Horn SHIQ Ontologies.
In IJCAI, pages 2040-2045, July 11-17 2009.
BibTeX-Entry | Pdf (191K) | Abstract ]

Despoina Magka, Yevgeny Kazakov, and Ian Horrocks. Tractable Extensions of the Description Logic EL with Numerical Datatypes. In Jürgen Giesl and Reiner Hähnle, editors, Proc. of the Int. Joint Conf. on Automated Reasoning (IJCAR 2010), volume 6173 of Lecture Notes in Artificial Intelligence, pages 61-75. Springer, 2010.
[ bib | .pdf ]