KnowWE is a semantic wiki that provides the possibility to de ne and maintain ontologies and strong problem-solving knowledge. Recently, the ontology engineering capabilities of KnowWE were signi cantly extended. As with other ontology engineering tools, the support of ontology debugging during the development of ontologies is the de cient. We present an Ontology Debugger for KnowWE that is based on the delta debugging approach known from Software Engineering. KnowWE already provides possibilities to de ne test cases to be used with various knowledge representations. While reusing the existing testing capabilities we implemented a debugger that is able to identify failure-inducing statements between two revisions of an ontology.
In software engineering changing requirements and evolving solutions are
wellknown challenges during the software development process. Agile software
development [
In the eld of ontology engineering the challenges are similar. It is extremely rare that the development of an ontology is a one-time task. In most cases an ontology is developed continuously and collaboratively. Even though this insight is not new and tool support has improved in recent years, a mature method for agile ontology development still is a vision.
The idea of continuous integration (CI) has been adapted for the development
of knowledge systems (cf. Baumeister et al. [
As abandoning a complete change set because of an error is as unrealistic
as tracing down the failure cause manually, a method for isolating the fault
automatically is necessary. We developed a debugging plugin for the semantic
wiki KnowWE that is able to nd the failure-inducing parts in a change set.
The debugger is based on the Delta Debugging idea for software development
proposed by Zeller [
The remainder of this paper is structured as follows: Section 2 describes the delta debugging approach for ontologies; in Section 3 we present the developed plugin for KnowWE in detail. Section 4 contains a short case study while Section 5 concludes with a discussion and the description of future work. 2 2.1
The proposed Delta Debugging approach assumes that we are able to access
di erent revisions of an ontology. Additionally, we assume that a mechanism
for the detection of changes exists. We call the di erence between two revisions
the set of changes C. The detection can be realized for example by utilizing
revision control systems like SVN or Git or by manually calculating the di erence
between two snapshots of an ontology. Even more sophisticated change detection
approaches are possible, like the one proposed by Goncalves et al. [
De nition 1 (Changes). Let C = fc1; c2; : : : ; cng be the set of changes ci provided by a change detection mechanism.
De nition 2 (Revision). Let O1 be the base revision of an ontology and O2 = O1 [ C a revision of the ontology, where the set of changes C have been applied.
With respect to a given test one of the revisions has to pass while the other one has to fail a speci c test (Axiom 1).
De nition 3 (Test Function). A function test : O ! BOOLEAN determines for a given ontology whether it passes (T RU E) a speci ed test procedure or not (F ALSE).
Axiom 1 For a given test function test and the revisions O1 and O2 of the ontology test(O1) = T RU E and test(O2) = F ALSE holds. 2.2
Test outcome The Delta Debugging approach we propose is not limited to
a certain test procedure as long as it can assert a boolean value as de ned in
De nition 3 and Axiom 1. In software engineering the outcome of a test can also
be unde ned. Zeller [
As ontology engineering is basically about adding/removing/changing triples, these failures can hardly occur|at least on the syntactical level. Incorrect statements can usually not be added to a repository and therefore should not detected as a valid/applicable change by the change detection mechanism. Additionally triples do syntactically not depend on other triples and therefore can be added to and removed from a repository independently. Finally ontologies are not executed in the way a program is, what relaxes the execution failure. On the semantical level, however, integration and construction failures are very likely to occur but they do not result in an unde ned test outcome, but a failing test|which is the desired behavior.
Example tests A test could consider for example the result of a SPARQL query. A concrete implementation could compare the actual query result with an explicitly de ned (expected) result. Another realization could use SPARQL's ASK form.
When dealing with an ontology that makes heavy use of semantics like OWL,
a reasoner like Pellet [
A test does not even have to test the ontology itself, as in task-based
ontology evaluation [
Regardless of the actual implementation the de nition of test cases should be
a substantial and integral part of the underlying ontology engineering
methodology. We described the TELESUP project [
We propose a delta debugging algorithm (Algorithm 1) for ontologies that is basically a divide-and-conquer algorithm recursively tracing down the faulty parts of an ontology.
The input of the recursive algorithm is the base revision of the ontology O1 that is known to pass the speci ed test procedure test. Additionally the set of changes C between this base revision and the failing revision O2 is provided. Algorithm 1 The delta debugging algorithm for ontologies.
function DeltaDebug(O1, C, test) if C:length is 1 then
return C end if r fg for all ci in Divide(C) do
Ot O1 [ ci if test(Ot) is F ALSE then
r r + DeltaDebug(O1; ci; test) end if end for return r end function
If the considered change set only contains one change then this is the failureinducing change by de nition. Otherwise the helper function Divide slices the set of changes in i new change sets. The function may use heuristics or exploit the semantics of the ontology to divide the initial change set. In the following each change set ci proposed by the Divide function is applied to the base revision O1 of the ontology. If the resulting revision of the ontology Ot does not pass the speci ed test procedure, then the change set is recursively examined in order to nd the triple responsible for the failure. As more than one recursive call of the DeltaDebug algorithm can return a non empty set of failure inducing changes, the nal result may contain more than one triple.
The shown version of the algorithm returns all changes that applied to the base revision O1 cause the failure. It additionally assumes monotonicity, i.e. a failure occurs as long as the responsible changes are contained in the change set. A more sophisticated handling of interferences will be subject of future work. 3 3.1
We have implemented the delta debugging algorithm as an extension of the
semantic wiki KnowWE [
We use a dedicated change log to keep track of all changes applied to an ontology in KnowWE. Each time a change is applied to the repository KnowWE's event mechanism is used to re events that inform about the statements that have been added to and removed from the repository. For every change a log entry is created. Listing 1.1 shows an example of log entries, that indicate the removal (line 1) and addition (line 2) of statements at the speci ed timestamps.
The change detection mechanism can now be realized by accessing the log le and asking for the changes between two points in time. The ontology revisions O1 and O23 can be constructed by reverting all changes between a speci ed start point and the currently running revision of the ontology (HEAD). The set of changes C between these two revisions can be extracted directly from the log le. 3.3
In order to realize the test function, we have introduced a Java interface called OntologyDeltaDebuggerTest which requires implementors to realize the method boolean execute(Collection<Statement> statements).
We have implemented a sample test that checks whether a revision of an ontology is able to provide speci ed results for a SPARQL query. We exploit the already existing possibilities of KnowWE to formulate and execute labeled SPARQL queries. In the following, we use an exemplary ontology inspired by the comic characters "The Simpsons"4.
Listing 1.2. Example for an expected SPARQL result. 1 2 3 4 5 6 7 8 } 9 @name : maleSimpsons 10 % %% SPARQL SELECT ?s WHERE { ?s rdf : type si : Human ; si : gender si : male ; rdfs : label ? name .
FILTER regex ( str (? name ), " Simpson ") 12 %% ExpectedSparqlResult 13 | si : abraham 14 | si : homer 15 | si : bart 16 @sparql : maleSimpsons 17 @name : maleSimpsonsExpected 18 % 3 The revision O2 is constructed to check whether Axiom 1 holds. 4 http://en.wikipedia.org/wiki/The Simpsons
Additionally we use KnowWE's feature to de ne expected results for a speci ed query. This can be done by adding the expected results to a table and referencing a labeled SPARQL query. For the convenient formulation a special markup has been introduced. Listing 1.2 shows an example where si:homer and si:bart are the expected results of the SPARQL query with the label \maleSimpsons". In order to access the formulated expected results, the markup also gets a label (\maleSimpsonsExpected"). The actual test is instantiated using this label, which allows accessing the expected results as well as the underlying SPARQL query. 3.4
The Delta Debugger for Ontologies is realized by the markup OntologyDebugger that allows for the convenient con guration of the debugger. The con guration is done by specifying the base revision O1 using the start annotation, optionally the revision O2 can be speci ed using the end annotation. If not speci ed the current revision of the ontology (HEAD) is considered as O2. Using the annotation expected the label of the expected SPARQL result is de ned.
The so de ned ontology debugger instance is rendered like depicted in Figure 1. A tool menu allows the execution of the debugger, a progress bar is used to visualize the running process. The actual implementation of the delta debugging algorithm for ontologies has been realized as LongOperation that is a feature of KnowWE's framework architecture, which allows for executing long operations in background without having the user to wait for the result. When the long operation has nished, then the failure-inducing changes are returned and displayed. An error message is rendered instead, if a failure occurs during the execution of the debugger, e.g. because the test is unde ned or Axiom 1 does not hold for the speci ed revisions.
4.1
In the following we describe a small case study that illustrates the functionality of the presented ontology debugging extension for KnowWE. Therefore we use an example ontology that has been developed for tutorial purposes and covers various facts of the popular comic television series \The Simpsons". The ontology contains several classes like Human or Building, as well as properties like parent or owns. Additionally, some instances of the de ned classes are included. We do not present the entire ontology but concentrate on some relevant parts.
Figure 2 shows relationships of the Simpsons family, e.g. that Homer (si:homer) is the father (si:father) of Bart (si:bart), Lisa (si:lisa) and Maggie (si:maggie), who are also marked as siblings (si:sibling). The sibling property was initially de ned as owl:TransitiveProperty, i.e. a triple that explicitly states that Lisa is sibling of Maggie is not necessary. We have also de ned that si:father is a sub-property of si:parent, which has an inverse property si:child. Listing 1.4 describes a SPARQL query for all children of Homer (si:homer) and Marge (si:marge).
An expert on the Simpson family knows that Bart, Lisa and Maggie are the expected result of this query. So this knowledge can be de ned in KnowWE as an expected SPARQL result (Listing 1.5), which than can be used as a test case for the ontology.
Listing 1.5. Expected results of the query for the children of Homer and Marge.
Listing 1.6 is another example containing a SPARQL query for all siblings of Maggie (si:maggie) and the de nition of the expected result (si:bart and si:lisa).
Listing 1.6. A test case for Maggie's siblings. %% SPARQL SELECT ? sibling WHERE {
BIND ( si : maggie as ? kid ) . ? kid si : sibling ? sibling .
FILTER (? kid != ? sibling ) .
For this case study various changes have been applied to the ontology (see Listing 1.7) and broke it nally, i.e. the SPARQL results do not return the expected results: Bart can not be retrieved as sibling of Maggie, and apparently Homer and Marge do not have any children.
Listing 1.7. Changes applied to the Simpsons ontology. -;1401267947600; si : snowball ; rdfs : label ; Snowball +;1401267947605; si : santas_little_helper ; rdfs : label ; Santa 's little helper@en +;1401267947605; si : snowball ; rdfs : label ; Snowball II -;1401268045755; si : child ; owl : inverseOf ; si : parent +;1401283675264; si : sibling ; rdf : type ; owl : IrreflexiveProperty -;1401283841549; si : relatedWith ; rdf : type ; owl : ReflexiveProperty +;1401283841552; si : relatedWith ; rdf : type ; owl : SymmetricProperty -;1401283907308; si : sibling ; rdf : type ; owl : TransitiveProperty -;1401287487640; si : Powerplant ; rdfs : subClassOf ; si : Building
In order to nd the failure-inducing changes, we have de ned two ontology debugger instances that utilize the test cases de ned above. Listing 1.8 shows their de nitions. Revision 1401267947599 is the base revision O1 for both instances as we know that the queries had been working before we started changing the ontology.
Listing 1.8. Changes applied to the Simpsons ontology.
After manually triggering the debugging process, the ontology debugger instances return the correct results. As depicted in Figure 3 the rst ontology debugger instance identi ed that removing the statement declaring si:child as inverse property of si:parent has caused the failure that the children of Homer and Marge could not be retrieved. The second instance reports that Bart is not identi ed as sibling of Maggie because the transitivity (owl:TransitiveProperty) has been removed from the si:sibling property.
We ran the case study on an Apple MacBook with 3 GHz Intel Core i7 processor and 8 GB RAM; the example ontology contained 2,518 triples. The ontology debugger returned each result after about 1.2 seconds on.
The ontology debugger was also utilized to trace down a failure-inducing change in an ontology for an industrial information system. The ontology comprises more than 700,000 triples and makes heavy use of OWL2-RL semantics. In this scenario the debugger returned the correct hint for the failure-inducing change after 5 minutes. The manual tracing of the error would have costed many times over the presented automated approach. 5
In this paper we presented an extension for KnowWE that adds support for ontology debugging by using a divide-and-conquer algorithm to nd failureinducing changes. Our current implementation is working on the syntactical level of an ontology and uses a provided test case in combination with a change detection mechanism and a heuristic for dividing the change set. However, the design of the algorithm and the software allows for the incorporation of more sophisticated methods that may consider semantics to leverage the debugging to a semantic level.
There has already been work on considering semantics for the debugging of
ontologies. Schlobach et al. [
While already functional we consider the current implementation of our ontology debugging plugin for KnowWE as early work. For the future we plan several enhancements to the debugger, like the replacement of the change log by a change detection mechanism that is based on standard wiki functionality providing direct access to di erent revisions of an ontology. As mentioned above we want to improve the handling of interferences, check the monotonicity assumption for di erent ontology languages and plan to examine the applicability of OWL debugging approaches. As KnowWE also allows for the de nition of strong problem-solving knowledge the generalization of the debugger to other knowledge representations will be subject of future work. The work described in this paper is supported by the Bundesministerium fur Wirtschaft und Energie (BMWi) under the grant ZIM KF2959902BZ4 "SELESUP { SElf-LEarning SUPport Systems".