jcel is a reasoner for the description logic EL+ that uses a rule-based completion algorithm. These algorithms are used to get subsumptions in the lightweight description logic EL and its extensions. One of these extensions is EL+, a description logic with restricted expressivity, but used in formal representation of biomedical ontologies. These ontologies can be encoded using the Web Ontology Language (OWL), and through the OWL API, edited using the popular ontology editor Protege. jcel implements a subset of the OWL 2 EL pro le, and can be used as a Java library or as a Protege plug-in. This system description presents the architecture and main features of jcel, and reports some of the challenges and limitations faced in its development.
Modular Rule-based Reasoner
This system description presents jcel1, a reasoner for the description logic E L+. The design and implementation details refer to jcel 0.17.1, unless other version is speci ed.
The lightweight description logic (DL) E L and its extensions have recently
drawn considerable attention since important inference problems, such as the
subsumption problem, are polynomial in E L [
The basic entities are concepts (class expressions), which are built with concept names (classes) and role names (object properties).
An ontology is a formal vocabulary of terms which refers to a conceptual schema inside a domain. The terms are related using an ontology language. The main service that this reasoner provides is classi cation, a hierarchical relation of the concepts in the ontology. jcel, as an E L+ reasoner, includes the standard constructors of E L: conjunction (C u D), existential restriction (9r:C), and the top concept (>). In addition, this logic includes role composition (r s v t) and role hierarchy (r v s).
Name concept name role name top conjunction existential restriction subsumption role hierarchy role composition
Syntax
A r > C u D 9r:C C v D r v s r s v t
AI Semantics
I rI I I
>I = I (C u D)I = CI \ DI (9r:C)I = fx j 9y : (x; y) 2 rI ^ y 2 CI g
CI DI rI sI rI sI tI jcel is developed in Java and can be compiled in Java 1.6 or Java 1.7 indistinctly. jcel is integrated to the OWL API 3.2.43, which is a Java application programming interface (API) and reference implementation for creating, manipulating and serializing OWL ontologies. Using the OWL API, jcel can be used as a Protege4 plug-in. Protege is a free, open source ontology editor, and also a knowledge base framework. Protege ontologies can be exported to several formats, like RDF, OWL and XML Schema. In order to keep compatibility with Protege 4.1, jcel is distributed as a Java binary for Java 1.6.
jcel can also be used as a library without the OWL API. It has its own factories to construct the optimized data types used in the core. 4
The algorithm is rule-based, and there is a set of rules that are successively applied to saturate data structures. These rules are called completion rules. The process is called classi cation, and is the main part of jcel's algorithm.
An algorithm that classi es the set of axioms by applying these rules could be
expensive in time if it is performed by a systematic search. The algorithm used by
jcel is based on CEL's algorithm [
The input of the algorithm is a normalized set of axioms T as in the following list: A v B, A1 u u An v B, A v 9r:B, 9r:A v B, r v s, r s v t.
The invariant of the algorithm has a set S, called set of subsumptions, such that for each pair of concept names A, B in T : (A; B) 2 S if and only if T j= A v B, and a set R such that for each triple of role r, and concept names A, B in T : (r; A; B) 2 R if and only if T j= A v 9r:B, where j= has the usual meaning.
The algorithm nishes when S is saturated. The output is S itself, which tells the subsumption relation for every pair of concept names.
In Figure 1, we can observe S and R, the completion rules (CR-1, CR-2, . . . ), the duplicates checker, and a set Q which has a set of entries to be processed.
In each iteration, an S-entry (a pair) or an R-entry (a triple) is taken from Q and added to either S or R. This change is propagated and sent to the chain of rules sensitive to changes in S (S-chain) or in R (R-chain). Every completion rule takes the new entry as input and returns a set of S- and R-entries. The arrows indicate how these entries ow.
Every element proposed by the rules is veri ed by the duplicates checker before being added to Q. The dashed lines indicate that the duplicates checker uses S and R for the veri cation. This procedure is repeated until Q is empty.
Architecture and Optimization Techniques jcel axioms are encoded using integers. This optimizes the use of memory and required time in comparisons. Any program using jcel as a library can encode its entities with integers, and take advantage of this e cient representation.
jcel is composed by several modules, as shown in Figure 2. The arrows indicate the relation \depends on".
jcel.coreontology and jcel.core are modules that use only normalized axioms. The former contains the normalized axioms themselves, the latter contains the implementation of the completion rules, together with the data structures for the subsumption graphs.
jcel.ontology is a module that contains the axioms for the ontology and the procedures to normalize the ontology. jcel.reasoner is the reasoner interface. It can classify an ontology and compute entailment.
All the modules mentioned above work with data types based on integers. jcel.owlapi is the module that connects to the OWL API. This module performs the translation between the OWL API axioms and jcel axioms. jcel.protege is a tiny module used to connect to Protege.
Figure 2 describes the module dependencies and shows that jcel can be used: { extending the core (with jcel.coreontology and jcel.core) { as a library using integers (adding jcel.ontology and jcel.reasoner) { as a library using the OWL API (adding jcel.owlapi) { as a Protege plug-in (adding jcel.protege)
jcel is a pure Java, open source project. Its source code can be cloned with Git5 and compiled using Apache Ant6 or Apache Maven7 indistinctly. 5 http://git-scm.com/ 6 http://ant.apache.org/ 7 http://maven.apache.org/
jcel includes several advantages derived from its design and from good practices of software engineering. Regarding the design, jcel has independent maintenance of rules. Each rule works as an independent unit that can be implemented, improved and pro led independently.
Regarding the good practices, jcel uses no null pointers. Every public method is prevented of accepting null pointers (throwing a runtime exception) and no public method returns a null pointer. Referred by its inventor as \The Billion Dollar Mistake"8, a null pointer may have di erent intended meanings. For example, min(1; null), may give the results \0" (considering null as 0), \1" (considering null as an empty argument), or \null" (considering null as an unde ned value).
Another good practice is that public methods return unmodi able collections when they refer to collections used in the internal representation. This prevents a defective piece of code from modifying the collection.
jcel has no cyclic dependencies of packages in each module. This facilitates maintenance, since modi cations on one package do not alter any other package that does not depend on the former.
jcel has also some points that are not implemented yet, but can be considered as good future improvements.
One of the improvements is to apply techniques to unchain properties [
Another improvement is incremental classi cation. This could be especially interesting for entailment, since jcel computes entailment by adding fresh auxiliary concepts and reclassifying the ontology.
Finally, the reduction of use of memory is an important improvement to consider. jcel 0.16.0 was the rst version to include entailment, but also became signi cantly slower than jcel 0.15.0 when classifying large ontologies. The reason was a side e ect resulting from the memory required for the entailment, producing a frequent execution of the garbage collector. This was partially solved in jcel 0.17.0. 7
jcel can be used to classify small and medium-sized ontologies of the E L family.
jcel was designed to be robust, resilient, modular and extensible. Its binaries
are small and can be distributed inside other tools. One tool that uses jcel is
Gel9 (Generalizations for E L) [
Another example is OntoComP10. It is a Protege plug-in for completing OWL ontologies, and for checking whether an OWL ontology contains \all relevant information" about the application domain. This tool uses the OWL API to connect to jcel as a library. 8 http://qconlondon.com/london-2009/speaker/Tony+Hoare 9 http://sourceforge.net/p/gen-el/ 10 http://ontocomp.googlecode.com/
jcel is also used to verify correctness in UEL11, Uni cation for the description logic E L. 8
jcel is a reasoner for lightweight ontologies. Its rule-based design makes it easy to be con gured according to the rules. Provides a high-level interface to be used as a tool seamlessly integrated to the OWL API.
The implementation is modular, resilient and highly extensible. Implemented in a state-of-the-art technology, it has a low coupling and a high cohesion, it is portable, and has an optimal interface to connect to other technologies of the Semantic Web.