Competency Questions (CQs) play an important role in the ontology development life-cycle, as they represent the ontology requirements. Although the main methodologies use them, there is room for improvement in the current practice of ontology engineering. One of the main problems is the lack of tools to check if CQs de ned in OWL, are being ful lled by an ontology, preferably in an automated way. Moreover, requirement (or CQ) traceability is rarely explored. Recently, there has been a trend on checking CQs against ontologies using RDF and SPARQL. Naturally, this language, being created for Semantic Networks, is inadequate to check the ful llment of OWL CQs. In this paper, we introduce a semi-automatic, full- edged method to develop ontologies iteratively, using CQs as requirements. It presents many novelties: a tracker to monitor the relations among CQs and the OWL code; an NLP component that translates CQs in natural language into OWL queries; a logic checker that con rms whether CQs are satis ed or not; a generator of new CQs, which comes into play when the CQ being dealt is not satis ed yet; and an axiom generator that suggests to the user new axioms to be included in the ontology.
For years, ontology development was more like a craft or arcane art form than
engineering, because there are no patterns or methodologies to guide the
engineers. Thus, each development team followed its own rules [
In a clear sign of progress, systematic 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, de ne how to describe the ontology scope and requirements (this latter
consisting of the competency questions (CQs) [
A noteworthy fact is that these methodologies are slightly di erent, but share
many common features. Two important ones consist of the iterative way of
development, and the use of CQs to de ne requirements. There are also many
tools to assist ontology development. Protege [
Despite the advances in ontology engineering, there are many areas to improve. The CQs are widely used to de ne requirements, however most of works use the CQs to check manually the ontology. This way could create a bottleneck, because it is slow to check a huge quantity of questions, and error-prone.
Traceability is other area that could be explored further. DL ontologies have a formal logic foundation that o ers possibilities to trace changes in an automatic way that is very hard to replicate in software engineering. For example, it could be possible to check which requirements are associated with which axioms, and vice-versa. It could be possible to check if all requirements are satis ed or not. And, it could be possible to check if some changes in the ontology code break some requirement. Thus, we are missing an opportunity to build powerful traceability tools to improve the ontology development process.
In this paper, we propose a method and introduce a system to improve some areas of ontology engineering. Using the system an engineer can build or evolve ontologies iteratively using CQs and their respective answers. The CQs are used as requirements and, with the system, every relation among them and axioms are traceable without extra e ort from the engineer.
The system uses CQs written in English to check OWL DL ontologies automatically using reasoning. This is di erent from many works that usually check the ontologies manually or at most use SPARQL queries. The user does not need to know DL syntax or other complex language to use the system, because all the interaction is made by natural language, thus there are not barriers to people without DL expertise. Furthermore, an ontology engineer can retrieve the axioms for every requirement or, for a given axiom, the system can show the requirement. Finally, the iterative nature of the system ts in many methodologies, then it can improve well-known development processes.
The basic usage can be described as follows: the user asks a CQ for the system, and it tries to answer the question with the knowledge encoded in an ontology. If it cannot answer correctly, the system asks for the user for more axioms, and generates other auxiliary CQs that the user can answer; then the process restarts, until it can answer all the generated CQs, including the rst.
The remainder of this paper is organized as follows: Section 2 provides a background about description logic ontologies, ontology engineering, competency questions, and requirement traceability; Section 3 presents our proposal of the system to build ontologies iteratively using competency question with automatic tracing; Section 4 details the implementation of the system; In section 5 we
show the results of tests using the system; Section 6 discusses related work; and, Section 7 concludes the paper and presents some ideas for future works. 2
To set the scene of the rest of this paper, the next three sections elucidate concepts related to description logic ontologies, ontology engineering and competency questions. These concepts serve as foundation of this work. 2.1
Description Logics (DLs) are a family of knowledge representation formalisms
that have been gaining growing interest in the last two decades, particularly
after OWL (Ontology Web Language) [
One of the most used DL languages is ALC, due to its good trade-o between expressivity and reasoning costs. We will describe in the following since this language is used in the paper.
An ontology or knowledge base in ALC is a set of axioms ai de ned over the
triple (NC ; NR; NO) [
There are two axiom types allowed in ALC: (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.
ALC semantics is formally de ned in terms of interpretations, model,
xpoints, interpretation functions, etc, over a domain or discourse universe [
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.3
Competency questions [
Many works propose the use of CQs for ontology engineering, but they usually used them to check ontologies manually, or, at most, express them as SPARQL queries. For answers that arise from more complex DL reasoning, in which the answers are not present in the ontology but can be entailed by it, no other option is yet o ered, but to check CQs manually, what constitutes a slow and expensive process that could be impracticable with very large ontologies or when the quantity of CQs is huge. 2.4
Requirement traceability is a problem studied by many software engineer
researches. But, for ontology engineers this area is almost absent. Requirement
traceability links the requirement speci cation and the code. It brings to the
engineer the capability of verify the completeness of an implementation with
respect to stated requirements [
There are two fundamental types of requirements traceability [
In our approach, we focus on post-requirements speci cation traceability. 3
We developed a method and a system implementation to build ontologies iteratively using CQs and their respective answers with an automatic requirement tracker. It is based on the idea of Uschold [24], which was never tried in the Semantic Web context. Yet, all the questions and answers are written in English.
Considering an ontology with the following axioms: Herbivorous Animalu 8eats::meat and Cow Animal u 8eats:grass. Then, a CQ states \Are cows herbivorous?", where the expected answer is \true". A system implementing the method tries to answer the question, but fails, because the ontology lacks the necessary axioms to infer that Cows v Herbivorous. Next, the system generates a new CQ for the user, for instance, \are grass and meat disjoint?". If the user answers \yes" the system includes in the ontology an axiom stating that the classes Grass and Meat are disjoint (Grass v :M eat). Now, the ontology has the necessary axioms to answer the initial question correctly.
Using this iterative process, a user can evaluate if an ontology has the necessary axioms to answer questions, and can add new knowledge, \teaching" it through the answers to the CQ made by the method/system. In the current version, our system can answer many types of questions using natural language, can add new axioms to an ontology according to the answers to questions, and it traces all changes. The question generation by the system is still being studied since it indeed represents a new DL problem, which requires additional speci c research to determine for which DL languages the problem is decidable, and in case they are, the problem's computability. Currently, we are assuming an oracle for that problem exists, in this implementation, the user provides the questions.
In the next section, we describe an implementation of the method with its four components: the natural language checker, the question generator, the ontology builder, and the tracker. 4
The current implementation includes four components: { Natural language checker: this component parses questions in English, uses the knowledge speci ed in an ontology, and returns an answer; { Question generator: when the system cannot answer a question correctly using the natural language checker, it generates questions for the user, to gather more knowledge to answer the initial question; { Ontology builder: all the new knowledge learned through the questions generated by the previous component are added to the ontology. This component is responsible for transforming the information of the previous component into an ontology speci cation language. { Tracker: all changes using the system are traceable. This component creates relations among all axioms added to an ontology and their correspondent competency question.
Next, each component is detailed, except the question generator, because in the current implementation the user needs to create the question manually. 4.1
The rst step of the process to build or evolve an ontology with the proposed system is to write a CQ in natural language. We choose this approach to compose a CQ, because it is easier for the engineer to use natural language than description logics.
In the system, there are prede ned types of questions that it understands. The types are de ned by rules, and each rule is de ned using grammatical tags (nouns, adjectives, verbs, etc.) and regular expression operators (*, +, ?, and j). Each word of a question is labeled using the NLP Stanford POS Tagger [23]. The labels are the grammatical category of the word. Then, the component veri es if the words and its POS tags match with some question rule. If it satis es some rule, the component will perform the operations to retrieve information of the ontology according to the question type. Otherwise, the system returns that it does not understand what the user asked.
There are three main question types: is-a, property value, and existence. They are detailed by table 1. Each table shows a usage example, the regular expression rules and the type of answers the question support. In the tables, Noun means all POS tags related do nouns, Adj means all POS tags related to adjectives, and Num means all POS tags related to numbers.
The component can nd names de ned in the ontology even though they are written in the question in plural, or separated by spaces, or with di erent capitalizations. For example, \red wine" can be matched with a class \RedWine" in the ontology, or the word \cows" in a question can be matched with a class \Cow". The component tests many variations of names in the question to nd the correct match in the ontology. Thus, the user can make questions in a very natural way regardless the speci c notation used to specify the ontology.
This component uses OWL API [
The goal of the ontology builder component is to add new knowledge to an ontology. Answering questions generated by the system, the user acts as a teacher Examples Does bancroft chardonnay have color white?
Do birds eat animals? Rules (doesjdo) (NounjAdjjNum)+ have Noun (NounjAdjjNum)
(doesjdo) (NounjAdjjNum)+ Verb (NounjAdjjNum)+ Answer Yes, no, true or false Existence question type Examples Which wines exist?
Which wines have sugar dry? Rules which (NounjAdjjNum)+
which (NounjAdjjNum)+ have (NounjVerb) (somejonly)? (NounjAdjjNum)+ Answer Classes separated by commas or the word \and" to the system that stores what it learns in the ontology. The system has prede ned types of questions it can generate. These questions are called system's questions (SQ), in other words, a competency question generated by the system. In this case, there are not rules for each SQ, because the system knows exactly the format of the question it will generate. To add knowledge to an ontology, the user only needs to answer the question properly.
There are three main system's question types: is-a, property value, and existence. They are detailed by table 2. Each table shows an example, the type of answers, and examples of axioms created. 4.3
All changes made using the system are traceable. When a user creates a CQ the system store this CQ, and it stores, if necessary, the SQs associated with the CQ. When a user answers a SQ the system stores the answer, create a relation between the answer and the SQ, and it also stores the OWL code added (a patch) to the ontology speci cation. This way, every step is monitored for later analysis. The Figure 1 shows the tracker data structure. Where CQi represents competency questions and i is the CQ index, for example, CQ1 is the rst CQ, CQ2 the second, etc. SQij are the system's questions, where i is the CQ index and j is the SQ index, for example, SQ12 is the second system's question related to the rst CQ, or SQ31 is the rst system's question related to the third CQ. Finally, Aij are the answers of the SQs, and Pij represents the code patch related to the answers.
Using the relations stored in the data structure, this component provides a series of useful operations: { Log: this command shows every CQ and every SQ and their answers in a hierarchy. Thus, an engineer has a manner to see the SQs generated for each CQ. Using the log command the user has an overview of how the ontology is being built through the change history. To do this, the system only needs to iterate over the nodes of the data structure and presents the information to the user. { Di : using this command the user speci es a SQ using the indexes and the system shows the OWL code included or removed. It is a good way to know exactly the axioms added for each SQ. This is possible, because the system saves the code patch, in other words, only the code added and the information where it was added in the ontology le. Thus, the system has all the information to presents the di to the user. { Rollback: if some change is not desirable, the user can undo what he did. The rollback returns the system to a speci ed point according to a CQ and SQ in the change history provided by the log command. Again, this is possible because the code patches saved in the data structure. In this operation, the system unapply every patch since the current state of the ontology until, but no including, the patch of the choosen SQ. { Code to question: this command is in some way the opposite of the di .
Using this command the user speci es an axiom in the OWL code, and the system returns, if there is one, a SQ. To do this, the system searches for the axiom selected in the added code. To test our implementation we perform some operations to check requirements, add code and use the tracker in the wine ontology. This ontology is available in the Protege website4.
First, we loaded the wine ontology and de ned the CQ \is red wine a wine?" with the expected answer \true". Because, we expected that the ontology has the necessary axioms to answer this question with this answer. For this case, the system returns \ok", in other words, the requirement is satis ed by the ontology.
Further, we asked other CQ, but now about a type of wine that does not exist in the ontology. The CQ is \is foo wine a red wine?" and the expected answer is \true". Since the ontology did not have this knowledge the system returned an error, because the requirement was not satis ed.
Now, the system should create SQs to question the user. This process was made manually. Two SQs was creates, the rst \is foo wine a wine?" and the second \does foo wine have color red?". Both question was answered with \yes", then the axioms F ooW ine v W ine and F ooW ine v 8hasColor:Red were added to the ontology. After, if the CQ \is foo wine a red wine?" is asked again the system can answer \ok". It is interesting to notice that we did not explicitly create the subclass relation between FooWine and RedWine, but, the reasoner can infer it after the addition of the new axioms.
To check the change history, the tracker provides the log command. For now, we had:
C l a s s : FooWine
SubClassOf :
v i n : Wine And the code added for SQ 1.b was: v i n : h a s C o l o r o n l y ( f v i n : Red g )
Other useful command is the rollback. For example, if we do not want the change made by the SQ 1.b, we can rewind to the state of SQ 1.a. After the command, the code line added by the answer of SQ 1.b does not exist anymore.
We can continue asking CQs, generating SQs and answering them, and use the tracker commands to analyze all the process until all the requirements were satis ed. Further, if more requirements appear, the engineer can use the system again to ask for new questions and he can continue the process every time he needs. 6
This work was inspired by the iterative way of develop ontologies proposed by many methodologies, and by the use of CQs to evaluate and de ne requirements.
Methontology [
Other methodologies emerged since 1990. Lenat and Guha presented the
steps of Cyc development in one of the rst works in this area [
During the emergence of the methodologies, many tools to support the
ontology development process are proposed. The rst was the OntolinguaServer in
the beginning of 1990. It started only with a simple editor, and later other
components were added, such an equation solver and an ontology merge tool [
All these works presented tried to improve the way of develop ontologies. In this paper, we are not proposing a new full featured ontology editor, neither a new methodology, but we are presenting a method and creating a system to support some phases of iterative methodologies and to improve some characteristics in ontology development overlooked in previous works. 7
In this paper, we presented a method, and an implementation of a system to support the process of building a DL ontology. Further, we presented a novel approach to trace requirements automatically, thus engineers can analyze the relations among requirements (CQs) and axioms. We also de ned the process to build or evolve an ontology iteratively using the system implemented.
In the current implementation, we can already see some useful features that can be used during and ontology development. For example, the natural language checker to con rm if an ontology satis es some requirements and the traceability tools provided by the tracker to analyze and navigate for all development history.
There are still limitations in the work. Each component needs to evolve. The natural language query component must support more types of question and treat more intrinsic details of the written language. The ontology builder needs to support more SQs too. Finally, we need to study the problem and develop the automatic question generation when some knowledge is missing in the ontology and the system cannot answer a question correctly. For now, this process is made manually. With the improvements of the previous components, the tracker will be even more powerful, providing a useful tool for ontology engineers.
Besides evolving the system's components, we can also integrate the whole system or some parts with popular ontology environments like Protege and NeOn. 20. Shearer, R., Motik, B., Horrocks, I.: HermiT: A Highly-E cient OWL Reasoner.
In: Ruttenberg, A., Sattler, U., Dolbear, C. (eds.) Proc. of the 5th Int. Workshop on OWL: Experiences and Directions (OWLED 2008 EU). Karlsruhe, Germany (October 26{27 2008) 21. Staab, S., Studer, R., Schnurr, H.P., Sure, Y.: Knowledge processes and ontologies. IEEE Intelligent Systems 16(1), 26{34 (Jan 2001), http://dx.doi.org/10.1109/5254.912382 22. Sure, Y., Erdmann, M., Angele, J., Staab, S., Studer, R., Wenke, D.: Ontoedit: Collaborative ontology development for the semantic web. In: Proceedings of the First International Semantic Web Conference on The Semantic Web. pp. 221{235. ISWC '02, Springer-Verlag, London, UK, UK (2002), http://dl.acm.org/citation.cfm?id=646996.711413 23. Toutanova, K., Klein, D., Manning, C.D., Singer, Y.: Feature-rich part-of-speech tagging with a cyclic dependency network. In: Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Volume 1. pp. 173{180. NAACL '03, Association for Computational Linguistics, Stroudsburg, PA, USA (2003), http://dx.doi.org/10.3115/1073445.1073478 24. Uschold, M.: Building ontologies: Towards a uni ed methodology. In: In 16th Annual Conf. of the British Computer Society Specialist Group on Expert Systems. pp. 16{18 (1996) 25. Uschold, M., Gruninger, M., Uschold, M., Gruninger, M.: Ontologies: Principles, methods and applications. Knowledge Engineering Review 11, 93{136 (1996) 26. Uschold, M., King, M.: Towards a methodology for building ontologies. In: In Workshop on Basic Ontological Issues in Knowledge Sharing, held in conjunction with IJCAI-95 (1995)