A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> We give the mathematical theory of a simple knowledge acquisition procedure based on implications and counter examples, and show examples of application. <s> BIB001 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Abstract The OWL Web Ontology Language is a new formal language for representing ontologies in the Semantic Web. OWL has features from several families of representation languages, including primarily Description Logics and frames. OWL also shares many characteristics with RDF, the W3C base of the Semantic Web. In this paper, we discuss how the philosophy and features of OWL can be traced back to these older formalisms, with modifications driven by several other constraints on OWL. Several interesting problems have arisen where these influences on OWL have clashed. <s> BIB002 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> We introduce the OWL Plugin, a Semantic Web extension of the Protege ontology development platform. The OWL Plugin can be used to edit ontologies in the Web Ontology Language (OWL), to access description logic reasoners, and to acquire instances for semantic markup. In many of these features, the OWL Plugin has created and facilitated new practices for building Semantic Web contents, often driven by the needs of and feedback from our users. Furthermore, Protege's flexible open-source platform means that it is easy to integrate custom-tailored components to build real-world applications. This document describes the architecture of the OWL Plugin, walks through its most important features, and discusses some of our design decisions. <s> BIB003 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Attribute exploration is an interactive computer algorithm which helps the expert to get informations about the attribute implications of a formal context. In the part I of this paper (see [H04]) an algorithm for attribute exploration with incomplete knowledge was presented. In this part we prove the main results of the algorithm: At the end of the attribute exploration the expert gets maximal information with respect to his knowledge about the unknown universe: He gets a list of implications which are certainly valid, a list of implications which are possibly valid, a list of counterexamples against the implications which are certainly not valid and a list of fictitious counterexamples against the implications which he answered by "unknown". He only has to check the implications which he answered by "unknown" and if he can decide for each of these implications whether it is valid or not, he gets complete knowledge about the implications of the context. <s> BIB004 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> In this paper, we describe Swoop, a hypermedia inspired Ontology Browser and Editor based on OWL, the recently standardized Web-oriented ontology language. After discussing the design rationale and architecture of Swoop, we focus mainly on its features, using illustrative examples to highlight its use. We demonstrate that with its Web-metaphor, adherence to OWL recommendations and key unique features, such as Collaborative Annotation using Annotea, Swoop acts as a useful and efficient Web Ontology development tool. We conclude with a list of future plans for Swoop, that should further increase its overall appeal and accessibility. <s> BIB005 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> We show how state-of-the-art Semantic Web technology can be used in e-Science, in particular, to automate the classification of proteins in biology. We show that the resulting classification was of comparable quality to that performed by a human expert, and how investigations using the classified data even resulted in the discovery of significant information that had previously been overlooked, leading to the identification of a possible drug-target. <s> BIB006 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Whenever human knowledge is considered, one has to take into account that such knowledge may be incomplete. Since Formal Concept Analysis (FCA for short) deals with the representation and investigation of such knowledge which can be connected to data tables – in FCA these are represented as formal one- or many-valued contexts –, it seems to be useful to have ways of representing (and dealing with) situations, where one knows about the incompleteness of parts of the represented knowledge. In this note we try to give a survey of what has been done so far in connection with the treatment of incomplete knowledge in FCA. In particular, we shall compare different algorithms developed so far in connection with the knowledge acquisition tool of “attribute exploration”, which also treat incomplete knowledge – cf. in particular [B91], [G99] and [H01]. Moreover, at the end, different treatments of incomplete knowledge in many-valued contexts and databases are discussed. <s> BIB007 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> In this paper, we investigate the problem of repairing unsatisfiable concepts in an OWL ontology in detail, keeping in mind the user perspective as much as possible. We focus on various aspects of the repair process – improving the explanation support to help the user understand the cause of error better, exploring various strategies to rank erroneous axioms (with motivating use cases for each strategy), automatically generating repair plans that can be customized easily, and suggesting appropriate axiom edits where possible to the user. Based on the techniques described, we present a preliminary version of an interactive ontology repair tool and demonstrate its applicability in practice. <s> BIB008 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Axiom pinpointing has been introduced in description logics (DLs) to help the user to understand the reasons why consequences hold and to remove unwanted consequences by computing minimal (maximal) subsets of the knowledge base that have (do not have) the consequence in question. The pinpointing algorithms described in the DL literature are obtained as extensions of the standard tableau-based reasoning algorithms for computing consequences from DL knowledge bases. Although these extensions are based on similar ideas, they are all introduced for a particular tableau-based algorithm for a particular DL. ::: ::: The purpose of this paper is to develop a general approach for extending a tableau-based algorithm to a pinpointing algorithm. This approach is based on a general definition of "tableaux algorithms," which captures many of the known tableau-based algorithms employed in DLs, but also other kinds of reasoning procedures. <s> BIB009 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> We propose an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the knowledge base and by a domain expert. The use of techniques from Formal Concept Analysis ensures that, on the one hand, the interaction with the expert is kept to a minimum, and, on the other hand, we can show that the extended knowledge base is complete in a certain, well-defined sense. <s> BIB010 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> A justification for an entailment in an OWL ontology is a minimal subset of the ontology that is sufficient for that entailment to hold. Since justifications respect the syntactic form of axioms in an ontology, they are usually neither syntactically nor semantically minimal. This paper presents two new subclasses of justifications--laconic justifications and precise justifications . Laconic justifications only consist of axioms that do not contain any superfluous "parts". Precise justifications can be derived from laconic justifications and are characterised by the fact that they consist of flat, small axioms, which facilitate the generation of semantically minimal repairs. Formal definitions for both types of justification are presented. In contrast to previous work in this area, these definitions make it clear as to what exactly "parts of axioms" are. In order to demonstrate the practicability of computing laconic, and hence precise justifications, an algorithm is provided and results from an empirical evaluation carried out on several published ontologies are presented. The evaluation showed that laconic/precise justifications can be computed in a reasonable time for entailments in a range of ontologies that vary in size and complexity. It was found that in half of the ontologies sampled there were entailments that had more laconic/precise justifications than regular justifications. More surprisingly it was observed that for some ontologies there were fewer laconic justifications than regular justifications. <s> BIB011 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Formal Concept Analysis (FCA) can be used to analyze data given in the form of a formal context. In particular, FCA provides efficient algorithms for computing a minimal basis of the implications holding in the context. In this paper, we extend classical FCA by considering data that are represented by relational structures rather than formal contexts, and by replacing atomic attributes by complex formulae defined in some logic. After generalizing some of the FCA theory to this more general form of contexts, we instantiate the general framework with attributes defined in the Description Logic (DL) EL, and with relational structures over a signature of unary and binary predicates, i.e., models for EL. In this setting, an implication corresponds to a so-called general concept inclusion axiom (GCI) in EL. The main technical result of this paper is that, in EL, for any finite model there is a finite set of implications (GCIs) holding in this model from which all implications (GCIs) holding in the model follow. <s> BIB012 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> Lattice theory today reflects the general Status of current mathematics: there is a rich production of theoretical concepts, results, and developments, many of which are reached by elaborate mental gymnastics; on the other hand, the connections of the theory to its surroundings are getting weaker and weaker, with the result that the theory and even many of its parts become more isolated. Restructuring lattice theory is an attempt to reinvigorate connections with our general culture by interpreting the theory as concretely as possible, and in this way to promote better communication between lattice theorists and potential users of lattice theory. <s> BIB013 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> In a previous paper, we have introduced an approach for extending both the terminological and the assertional part of a Description Logic knowledge base by using information provided by the assertional part and by a domain expert. This approach, called knowledge base completion, was based on an extension of attribute exploration to the case of partial contexts. The present paper recalls this approach, and then addresses usability issues that came up during first experiments with a preliminary implementation of the completion algorithm. It turns out that these issues can be addressed by extending the exploration algorithm for partial contexts such that it can deal with implicational background knowledge. <s> BIB014 </s> A Survey on how Description Logic Ontologies Benefit from Formal Concept Analysis <s> Completing DL Ontologies <s> We investigate the computational complexity of axiom pinpointing, which is the task of finding minimal subsets of a Description Logic knowledge base that have a given consequence. We consider the problems of enumerating such subsets with and without order, and show hardness results that already hold for the propositional Horn fragment, or for the Description Logic EL. We show complexity results for several other related decision and enumeration problems for these fragments that extend to more expressive logics. In particular we show that hardness of these problems depends not only on expressivity of the fragment but also on the shape of the axioms used. <s> BIB015
The standardization of OWL BIB002 as the ontology language for the semantic web  led to the fact that several ontology editors like Protégé BIB003 , and Swoop BIB005 now support OWL, and ontologies written in OWL are employed in more and more applications. As the size of these ontologies grows, tools that support improving their quality become more important. The tools available until now use DL reasoning to detect inconsistencies and to infer consequences, i.e., implicit knowledge that can be deduced from the explicitly represented knowledge. There are also promising approaches that allow to pinpoint the reasons for inconsistencies and for certain consequences, and that help the ontology engineer to resolve inconsistencies and to remove unwanted consequences  BIB008  BIB011 BIB009 BIB015 . These approaches address the quality dimension of soundness of an ontology, both within itself (consistency) and w.r.t. the intended application domain (no unwanted consequences). In BIB010 BIB010 we have considered a different quality dimension: completeness. We have provided a basis for formally well-founded techniques and tools that support the ontology engineer in checking whether an ontology contains all the relevant information about the application domain, and to extend the ontology appropriately if this is not the case. As already mentioned, a DL knowledge base (nowadays often called ontology) usually consists of two parts, the terminological part (TBox), which defines concepts and also states additional constraints (GCIs) on the interpretation of these concepts, and the assertional part (ABox), which describes individuals and their relationship to each other and to concepts. Given an application domain and a DL knowledge base describing it, we can ask whether the knowledge base contains all the relevant information about the domain: -Are all the relevant constraints that hold between concepts in the domain captured by the TBox? -Are all the relevant individuals existing in the domain represented in the ABox? As an example, consider the OWL ontology for human protein phosphatases that has been described and used in BIB006 . This ontology was developed based on information from peer-reviewed publications. The human protein phosphatase family has been well characterised experimentally, and detailed knowledge about different classes of such proteins is available. This knowledge is represented in the terminological part of the ontology. Moreover, a large set of human phosphatases has been identified and documented by expert biologists. These are described as individuals in the assertional part of the ontology. One can now ask whether the information about protein phosphatases contained in this ontology is complete: are all the relationships that hold among the introduced classes of phosphatases captured by the constraints in the TBox, or are there relationships that hold in the domain, but do not follow from the TBox? Are all possible kinds of human protein phosphatases represented by individuals in the ABox, or are there phosphatases that have not yet been included in the ontology or even not yet have been identified? Such questions cannot be answered by an automated tool alone. Clearly, to check whether a given relationship between concepts-which does not follow from the TBox-holds in the domain, one needs to ask a domain expert, and the same is true for questions regarding the existence of individuals not described in the ABox. The rôle of the automated tool is to ensure that the expert is asked as few questions as possible; in particular, she should not be asked trivial questions, i.e., questions that could actually be answered based on the represented knowledge. In the above example, answering a non-trivial question regarding human protein phosphatases may require the biologist to study the relevant literature, query existing protein databases, or even to carry out new experiments. Thus, the expert may be prompted to acquire new biological knowledge. The attribute exploration method of FCA has proved to be a successful knowledge acquisition method in various application domains. One of the earliest applications of this approach is described in BIB013 , where the domain is lattice theory, and the goal of the exploration process is to find, on the one hand, all valid relationships between properties of lattices (like being distributive), and, on the other hand, to find counterexamples to all the relationships that do not hold. To answer a query whether a certain relationship holds, the lattice theory expert must either confirm the relationship (by using results from the literature or by carrying out a new proof for this fact), or give a counterexample (again, by either finding one in the literature or constructing a new one). Although this sounds very similar to what is needed in our case, we cannot directly use this approach. The main reason is the open-world semantics of description logic knowledge bases. Consider an individual i from an ABox A and a concept C occurring in a TBox T . If we cannot deduce from the TBox T and A that i is an instance of C, then we do not assume that i does not belong to C. Instead, we only accept this as a consequence if T and A imply that i is an instance of ¬C. Thus, our knowledge about the relationships between individuals and concepts is incomplete: if T and A imply neither C(i) nor ¬C(i), then we do not know the relationship between i and C. In contrast, classical FCA and attribute exploration assume that the knowledge about objects is complete: a cross in row g and column m of a formal context says that object g has attribute m, and the absence of a cross is interpreted as saying that g does not have m. There has been some work on how to extend FCA and attribute exploration from complete knowledge to the case of partial knowledge BIB001   BIB004 BIB007  , and how to evaluate formulas in formal contexts that do not contain complete information  . However, these works are based on assumptions that are different from ours. In particular, they assume that the expert cannot answer all queries and, as a consequence, the knowledge obtained after the exploration process may still be incomplete and the relationships between concepts that are produced in the end fall into two categories: relationships that are valid no matter how the incomplete part of the knowledge is completed, and relationships that are valid only in some completions of the incomplete part of the knowledge. In contrast, our intention is to complete the knowledge base, i.e., in the end we want to have complete knowledge about these relationships. What may be incomplete is the description of individuals used during the exploration process. In BIB010  we have introduced an extension of FCA that can deal with partial knowledge. This extension is based on the notion of a partial context that consists of a set of partial object descriptions (pod ). A pod is a tuple (A, S) where A represents the set of attributes that the pod is known to have, and S represents the set of attributes that the pod is known not to have. A and S are disjoint and their union need not be the whole attribute set, i.e., for some attributes it might be unknown whether the pod has this attribute or not. We say that a pod (A, S) refutes an implication L → R if L ⊆ A and R ∩ S = ∅. We also say that a partial context refutes an implication if there is a pod in this partial context that refutes this implication. Based on these, we define the notion of an undecided implication, which is an implication that does not follow from a given set of implications, and that is not refuted by a partial context. Then the attribute exploration method for partial contexts can be formulated as enumerating undecided implications as efficient as possible. In BIB010  we have described a version of attribute exploration algorithm that works for this setting, and proved that this algorithm terminates and it is correct. Later we have shown that given a DL knowledge base (T , A), any individual in A gives rise to a pod, and thus A induces a partial context. This enables us to use our attribute exploration algorithm on partial contexts for Acountries Asian EU European G8 Mediterranean Table 1 . The partial context before completion finding completing DL knowledge bases. As a result of running this algorithm on a DL knowledge base, the knowledge base is complete w.r.t. an intended interpreation, i.e., if an implication holds in this interpreation then it also follows from the TBox, and if not then the ABox contains a counterexample to this implication. For details of the attribute exploration on partial contexts and its application to DL ontologies we refer the reader to BIB010  , and demonstrate on a small example how it works. Example 2. Let our TBox T countries contain the following concept definitions: G8member ≡ Country ⊓ ∃memberOf.{G8} IslandCountry ≡ Country ⊓ ¬∃hasTerritoryIn.Continent MediterrenaenCountry ≡ Country ⊓ ∃hasBorderTo.{M editerrenaenSea} Moreover, let our ABox A countries contain the individuals Syria, Turkey, France, Germany, Switzerland, USA and assume we are interested in the subsumption relationships between the concept names AsianCountry, EUmember, EuropeanCountry, G8member and MediterreneanCountry. Table 1 shows the partial context induced by A countries , and Table 2 shows the questions asked by the completion algorithm and the answers given to these questions. In order to save space, the names of the concepts are shortened in both tables. The questions with positive answers result in extension of the TBox with the following GCIs: Moreover, the questions with negative answers result in extension of the ABox with the individuals Russia, Cyprus, Spain and Japan. The partial context induced by the resulting ABox A ′ countries is shown in ⋄ Based on on the described approach, we implemented a first experimental version of a DL knowledge base completion tool as an extension for the Swoop ontology editor using Pellet as the underlying reasoner. A first evaluation of this tool on the OWL ontology for human protein phosphatases with biologists as experts, was quite promising, but also showed that the tool must be improved in order to be useful in practice. In particular, we have observed that the experts sometimes make errors when answering queries. Thus, the tool should support the expert in detecting such errors, and also make it possible to correct errors without having to restart the completion process from scratch. Another usability issue on the wish list of our experts was to allow the postponement of answering certain questions, while continuing the completion process with other questions. In a follow-up paper BIB014 we have addressed these usability issues. We have improved the method in such a way that at any time during completion the expert can pause the process, see all of her previous answers or changes to the knowledge base, 'undo' some of those changes, and continue completion. Here we of course paid attention that the expert does not have to answer the same questions she has answered before pausing the process. We have achieved this by saving previous answers, and using them as background knowledge when the expert continues completion. The other wish of our experts, namely postponing questions was solved pausing completion, changing the order of attributes, and restarting the completion with previous answers as background knowledge. In theory, this method might not postpone a question, thus the expert might be asked the last question again. However, in practice the method turned out to be useful in many cases when the expert was not able to answer a particular question and wanted to get another one. We have implemented our ontology completion method together with these usability issues as a plugin for the Protégé ontology editor under the name OntoComP. BIB012 