Competency Questions (CQs) are widely used in ontology development to represent the ontology requirements. Engineers can check if a CQ is satis ed manually or with software assistance. However, when a CQ is not satis ed, they need to analyze the axioms to discover what is missing. This activity may be hard and time-consuming, because of the size of the ontology and the complexity to inspect the axioms using inferences. In this paper, we present a method that uses uni cation in EL to generate new CQs based on an unsatis ed CQ. They are used to questioning an engineer, therefore she can provide answers to add the missing knowledge so as to satisfy the initial CQ to the ontology. We did two experiments using the SNOMED CT ontology. Our approach generated questions to add the missing knowledge in 69.09% cases.
For years, ontologies were developed through ad hoc e orts. There was no
patterns or methodologies to guide engineers during the process to build an ontology.
Thus, each team followed its own rules and set of activities [
However, since 1990, consistent methodologies and tools have been proposed
to support ontology development. These methodologies address the tasks of
creating and maintaining an ontology; thus, they specify an ontology life-cycle,
dene how to describe the ontology scope and requirements (this latter consisting
of the competency questions (CQs) [
Competency questions (CQs) are widely used in ontology development to represent the ontology requirements. They are a set of questions that an ontology must answer using the knowledge represented by its axioms. For example, in an
ontology about wine, we may have the CQs [
Engineers can check if a CQ is satis ed manually or with software assistance
[
In this paper, we present a method to help engineers to add axioms to an
ontology. Given an unsatis ed CQ, our approach uses uni cation in DL E L with
acyclic TBoxes [
For example, given an ontology with two axioms: Herbivore Animal u
this CQ: \Is cow a herbivore?" with the expected answer \true". This question can be interpreted as the axiom Cow v Herbivore. With these axioms, a DL reasoner cannot conclude that the CQ is satis ed, thus our approach could suggest some questions, for instance, \Is vertebrate an animal?" and \Is grass a vegetable?". If an engineer answers both questions with a \yes", the axioms
Then, the initial CQ is checked again, and now it is satis ed.
The remainder of this paper is organized as follows: Section 2 provides the background about ontology engineering, competency questions, description logics ontologies, and uni cation; Section 3 presents our method to generate CQs; Section 4 shows the results of an experiment to evaluate our approach; In Section 5 we discuss the results; Section 6 presents the related work; and, Section 7 concludes the paper and shows some ideas for future works. 2
This section presents concepts that serve as foundation of this work. In the following four sections we explain about ontology engineering, competency questions, descriptions logics ontologies, and uni cation. 2.1
Ontology Engineering
According to Gomez-Perez and colleagues, ontology engineering refers to the
activities related to the process, life-cycle, methods, methodologies, tools, and
languages to support the ontology development [
In some ways, the methodologies to develop ontologies are analogous to the ones for software engineering. They provide guidance to developers and are divided in phases, for example, speci cation, execution, and evaluation. Besides, the process is usually iterative, and the ontology can evolve during its lifetime in a very similar way of a software, in the sense that it requires maintenance, versioning, etc. 2.2
Competency Questions
Competency questions [
The following list shows some CQs used in an ontology for public employment
services [
Description Logics Ontologies
Description Logics (DLs) are a family of knowledge representation formalisms
that have been gaining growing interest in the last two decades, particularly
after OWL (Web Ontology Language) [
A DL ontology is a set of axioms ai de ned over the triple (NC ; NR; NO)
[
There are two axiom types allowed in DL: (i) Assertional axioms, which are
concept assertions C(a), or role assertions r(a; b), where C 2 NC , r 2 NR, a; b 2
NO and (ii) Terminological axioms, composed of any nite set of GCIs (general
concept inclusion) in one of the forms C v D or C D, the latter meaning
C v D and D v C, C and D being concepts. An ontology or knowledge base
(KB) is referred to as a pair (T ; A), where T is the terminological box (or TBox)
which stores terminological axioms, and A is the assertional box (ABox) which
stores assertional axioms. T may contain cycles, in case at least in an axiom
of the form C v D, D can be expanded to an expression that contains C. DL
semantics is de ned through interpretations. An interpretation I is a non-empty
domain I and an interpretation function :I , then I = ( I ; :I ). Further, :I maps
concept names to subsets of I and role names to binary relations over I [
Distinct DL languages can be de ned according the operators they support.
In this work, we support E L ontologies with acyclic TBoxes. This DL language
is less expressive than others well know DL languages, for instance, ALC, but it
is used in very large ontologies, e.g., SNOMED CT4. Also, because its simplicity,
the inference of subsumptions is polynomial, in other words, it can be fast enough
for real life applications. The Table 1 shows the operators supported by the DL
E L and their semantics.
A DL E L uni cation [
For example, given an ontology with two de nitions of male sports car enthusiast: X Human u M ale u 9loves:SportsCar and Y M an u 9loves:(Car u F ast). Although both concepts express the same idea, we have di erent concepts. Thus, this is a typical case to use uni cation. De ning Nv = fM an; SportsCarg and = fX ? Y g, the solution are the substitutions M an 7! Human u M ale and SportsCar 7! Car u F ast.
For acyclic TBoxes, a concept only occurs once as left-hand side, and there is
no cyclic dependencies between concept de nitions. In this case, the subsumption
complexity is polynomial and the uni cation is NP-complete [
Our method generates CQs to guide an engineer to add axioms to satisfy a previously asked unsatis ed CQ. It is necessary that a CQ can be represented
as an axiom, thus we can de ne the problem as a TBox abduction problem.
Di erent approaches may be used to transform CQ into axioms, for instance the
transformations showed in [
Given a DL ontology O, a CQ and O [ f g consistent. The solution for a TBox abduction problem is a nite set , such that O [ j= and O [ 6j= ?. In our approach, to nd we solve a uni cation problem. All substitutions found are transformed into equivalence axioms. For instance, X 7! Y is transformed into X Y . Thus, is a set of these axioms.
We can convert the axioms of into natural language questions. Thus, an engineer can answer these questions. If she answers positively a generated CQ, then this knowledge can be added to the ontology. In this way, an engineer has an easier and natural way to add axioms to an ontology. Besides, she is guided in this process, because the questions generated are based on the unsatis ed CQ.
There are four steps to generate CQs solving a uni cation problem. First,
we need to de ne the equation of the uni cation problem. Second, the variables
are de ned to specify which concepts may receive a de nition. After this, the
uni cation is processed to nd the set of substitutions and their corresponding
axioms. In the end, the axioms are converted to questions in natural language.
The Figure 1 shows how the steps interact with each other.
A uni cation problem is a set of equations = fC1 ? D1; :::; Cn ? Dng.
To generate questions based on an unsatis ed CQ, the problem is a set with
one element representing the unsatis ed CQ. Given the unsatis ed CQ axiom,
then = f g. It is important to notice, that a CQ axiom may be a subsumption
axiom instead of an equivalence axiom. In this case, we transform C v D into
C C u D.
The variables are the concepts that may receive a de nition as the solution of the
uni cation problem. We use the following method to de ne the variable concepts
based on the approach of the UEL library [
First, the equation is stored. Next, every axiom that de nes the concepts in the equation is stored. Then, all axioms that de ne the concepts of the concepts stored previously are saved. This process continues recursively until there is no axiom de ning the concepts stored. For example, given an equation X Y , and a set of axioms: X A; Y B; B C; D E. First, X Y is stored. Then, the axioms that de ne concepts in the equations are stored, in this case, X A and Y B. Now, recursively, the axioms de ning concepts in the previously stored axioms are stored. Thus, B C is saved. After this, the process ends.
With this set of axioms in hands, the next step is to choose the variable concepts. For this, all concepts in the stored axioms that have no equivalence de nition are added to the set of incompletely de ned concepts Nv . In the example, we stored fX Y; X A; Y B; B Cg, then the concepts in the axioms are fX; Y; A; B; Cg. However, among these concepts, only fA; Cg does not have equivalence de nitions, hence Nv = fA; Cg.
Furthermore, in addition to the individual concepts, we also store the two by two combination of the concepts in Nv , thus generating the set of incompletely de ned concepts pairs C Nv . 3.3
Unifying
In this step we use the equation and variables de ned in the previous steps. For
each element in Nv and each pair in C Nv , we run the uni cation algorithm of
the UEL library [
Converting to Natural Language The last step transforms the equivalence axioms of the previous step in natural language competency questions.
All axioms have the form X C, such that C is a complex concept. The algorithm to convert to natural language starts adding C to a queue and set a ag with an empty value. Next, the algorithm gets the rst element of the queue, and tests if it is a concept, a role, an existential restriction or a conjunction. Based on the element type and the ag value, the algorithm builds the question step by step. If the element is an existential restriction or a conjunction, it is broken in smaller parts that are added to the queue. However, if the item is a concept or a role, parts of the question are generated. The process ends when there is no element in the queue.
The algorithm processes the names of concepts and roles to transform them into a more natural form. The process adds a space before each uppercase letter, except the rst, and convert everything to lowercase in the end. For instance, a concept \ProcedureOnSkeletalSystem" is transformed into \procedure on skeletal system".
The Figure 2 shows all steps of the algorithm to convert axioms into natural language questions. It is important to notice, that when the algorithm reaches a return (the items with quote marks) this text is concatenated with the previously generated texts. In this section, we present the whole process of generate CQs based on an unsatis ed CQ. Consider an ontology with these axioms:
{ F astEngine v CarEngine { RaceEngine v CarEngine { F astCar v Car u 9engine:F astEngine { RaceCar v Car u 9engine:RaceEngine
Given a CQ \is race car a fast car", or, as an axiom, RaceCar v F astCar. First, we de ne the uni cation problem equation, that is = fRaceCar v? F astCarg. The second step de nes the variables. The algorithm stores the axioms according to the process described in Section 3.2. Next, it chooses only the concepts in the axioms that have no equivalence de nitions . In this case, Mv = fCar; F astEngine; RaceEngineg. Also, it saves the combination pairs of the concepts in Mv , creating the set: C Mv = f(Car; F astEngine); (Car; RaceEngine); (F astEngine; RaceEngine)g.
In the third step, the uni cation problem is solved for each element in Mv and each pair in C Mv . Using Car as variable the result is Car 9engine:F astEngine, and using RaceEngine as variable the result is RaceEngine F astEngine. For the other cases, it does not nd any uni er.
To conclude the process, both axioms found in the uni cation step are transformed into natural language questions. The rst axiom is transformed into the question \does a car have engine some fast engine?", and the second into the question \is a race engine equivalent to fast engine?". 4
We did two experiments to evaluate our method. The goal of the rst was measuring the percentage of cases that the algorithm nds a uni er, so that the system can generate CQs. In the second experiment, we evaluate if the generated competency questions were similar to axioms created by engineers.
The SNOMED CT ontology was used in the experiments. It is the largest ontology about clinical concepts with more than 350,000 concepts and 1.38 millions relations. Many concepts in the ontology use a special role called \roleGroup" to group some existential restrictions. However, this practice can harm the semantics of the axiom, and hinder the translation to natural language. Thus, we removed all roleGroups before the experiments, but we kept the content inside the role. For instance, X 9roleGroup:(9r:Y u s:Z) was changed to X 9r:Y u 9s:Z. 4.1
Creating Questions
To test the capability to generate competency questions, we created three
modules extracted from the SNOMED CT ontology using the OWL-ME tool [
Next, we chose 10 random axioms from each module. Further, we made 10 copies of each module, and remove, from each copy, one of the 10 random axioms chosen previously. Thus, we had 30 modules, each with a missing axiom. To ensure that the knowledge represented by the axioms was removed, we tested if the axioms could be inferred. In all cases, they could not.
The next step was creating manually CQs that needed the axioms removed to be satis ed. Thus, we expected that our approach would return questions to guide us to add the axioms to satisfy the unsatis ed CQs.
The Table 2 shows the results of the tests. For the 10 modules created from the rst module, we had 63 CQs, and our approach generated questions to help satisfy 38 CQs. In other words, in 38 cases one or more uni ers were found, and in the remainder none were found. For the 10 modules created from the second module, we had 54 CQs, and our approach generated questions for 36 CQs. For the last 10 modules created from the third module, we had 66 CQs, and our approach generated questions for 53 CQs. In this experiment we tested if the axioms generated by the uni cation are similar to the axioms coded by engineers. To this end, we used the same modules of the rst test. We compared if the axioms of the uni cation problem solution are similar to the axioms removed in each module.
To compare axioms, we used two approaches. The rst, for each axiom we created a set of concepts according to them. For example, for an axiom X A v 9r:B, the set is fX; A; r; Bg. In the second approach, we also created a set for each axiom, however, we did not dissociate the role from its related concept. For example, given the same axiom X A v 9r:B, the set in the second approach is fX; A; r:Bg. Thus, the second approach is more rigorous than the rst, because the role and its concept must appear together.
The sets were compared using the following metrics: precision, recall and fmeasure. Given Ss = fA; B; X; Y g, a set generated from a suggested axiom by our approach, and Sc = fA; B; Cg, a set generated from an axiom coded by an engineer. The precision is 2/4, the recall is 2/3 and the f-measure is calculated using the equation F = 2 PPrreecciissiioonn+RReeccaallll .
Table 3 shows the results of this experiment. The metric name followed by the number 1 means that it was calculated using the rst approach to generate the sets. The metric name followed by the number 2 means that it used the second approach to generate the sets. Our approach can generate di erent types of CQs. Some are simple, for instance \does a disease of musculoskeletal system have nding site some body system structure?". And, some are complex, for instance, \is a malignant neoplasm of genitourinary organ equivalent to a clinical nding, that have associated morphology some mass, that have nding site some anatomical or acquired body structure, that have nding site some anatomical structure?".
Smaller questions are easier to understand than longer questions, because the latter represent large axioms with many concepts, roles and relationships among them. The uni cation ensures that the axioms represented by the questions will satisfy an unsatis ed CQ; however an engineer must analyze the content of the questions, to be sure that the knowledge make sense. The approach is not concerned with the ontological engagement.
The algorithm generated CQs to add the missing axioms in 69.09% of the cases, this happened because these are the cases that the uni cation could be solved. The cases that no CQ was generated were the ones that it was not found any uni er for the equation using the variables de ned by our approach.
In the results of the second experiment, precision in average is higher than recall. Our approach usually suggests axioms that have roles and concepts of the original axiom, but, it misses some roles and concepts too. For instance, the ontology have this axiom:
CongenitalF emaleU rogenitalAnomaly
and our approach suggests a question represented by this axiom:
In this example precision is 100% in both cases to generate the sets, however recall is 22.22% in the rst case and 16.67% in the second.
Sometimes, the suggested axiom has a correct role, but the concept is different, or vice-versa. Thus, the values of the metrics in the rst case is higher than the second case. In other cases, despite the concepts are di erent, they subsume one another. For instance, in one of the tests, the original axiom has f indingSite:F aceStructure and the suggestion has F indingSite:HeadStructure. 6
The idea of generating questions when a CQ is not satis ed is inspired in the work
of Uschold and Gruninger [
The method query-the-user [
In this paper we presented a method to suggest competency questions to guide engineers to satisfy a previous unsatis ed CQ. The method guide engineers to add axioms to an ontology through the answers to the suggested questions.
Two experiments were performed: the rst tested the capability of the approach to suggest CQ. In 69.06% of the cases the method generated questions that represented the necessary axioms to satisfy an CQ. The second experiment evaluated if the axioms suggested were similar to the axioms coded by engineers. We tried two ways to measure the similarity through precision, recall and f-measure. On average, the rst way had f-measure 35.66%, and the second way had f-measure 14,97%.
For future work, there is opportunity to test abduction in DL EL [