Christiankissig.com

Institute for Theoretical Computer Science, is the first prototype implementation of non-standard inferences for Description Logics that can be used via a graphical user interface. In addition tothat our implementation extends an earlier implementation of the least commonsubsumer and of the approximation inference service to more expressive Descrip-tion Logics, more precisely to Description Logics with number restrictions. Sonicoffers these reasoning services via an extension of the graphical ontology editor Inference problems for Descriptions Logics (DLs) are divided into so-called standardand non-standard ones. Well-known standard inference problems are satisfiability andsubsumption of concept descriptions. For a great range of DLs, sound and completedecision procedures for these problems could be devised and some of them are putinto practice for very expressive DLs in state of the art DL reasoners as FaCT [15]and Racer [13].
Prominent non-standard inferences are the least common subsumer (lcs), and ap- proximation. Non-standard inferences resulted from the experience with real-world DLontologies, where standard inference algorithms sometimes did not suffice for buildingand maintaining purposes. For example, the problem of how to structure the appli-cation domain by means of concept definitions may not be clear at the beginning ofthe modeling task. Moreover, the expressive power of the DL under consideration canmake it difficult to come up with a faithful formal definition of the concept originallyintended. This kind of difficulties can be alleviated by the use of non-standard in-ferences in the bottom-up construction of DL knowledge bases, as described in [1, 8].
Here instead of directly defining a new concept, the knowledge engineer introducesseveral typical examples as objects, which are then automatically generalized into aconcept description by the DL system. This description is offered to the knowledgeengineer as a possible candidate for a definition of the concept. The task of computing This work has been supported by the Deutsche Forschungsgemeinschaft, DFG Project 1Sonic stands for “Simple OilEd Non-standard Inference Component”.
such a concept description can be split into two subtasks: computing the most spe-cific concepts of the given objects, and then computing the least common subsumerof these concepts.
The lcs was first mentioned as an inference problem for DLs in [12]. Given two concept descriptions A and B in a description logic L, the lcs of A and B is defined asthe least (w.r.t. subsumption) concept description in L subsuming A and B. The ideabehind the lcs inference is to extract the commonalities of the input concepts. It hasbeen argued in [1, 8] that the lcs facilitates the “bottom-up”-approach to the modelingtask: a domain expert can select a number of intuitively related concept descriptionsalready existing in an ontology and use the lcs operation to automatically constructa new concept description representing the closest generalization of these concepts.
For a variety of DLs there have been algorithms devised for computing the lcs, see[1, 16, 10] for details.
Approximation was first mentioned as a new inference problem in [1]. The ap- proximation of a concept description C1 from a DL L1 is defined as the least conceptdescription (w.r.t. subsumption) in a DL L2 that subsumes C1. The idea underlyingapproximation is to translate a concept description into a typically less expressiveDL. Approximation can be used to make non-standard inferences accessible to moreexpressive DLs so that at least an approximate solution can be computed. In case theDL L provides concept disjunction, the lcs of C1 and C2 is just the concept disjunction(C1 C2). Thus, a user inspecting this concept description does not learn anything about the commonalities between C1 and C2. Using approximation, however, one canmake the commonalities explicit to some extent by first approximating C1 and C2 ina sublanguage of L which does not provide disjunction, and then compute the lcs ofthe obtained approximations in L. Approximation has so far been investigated for afew DLs, see [7, 6].
Another application of approximation lies in user-friendly DL systems, such as the editor OilEd [4], that offer a simplified frame-based view on ontologies defined in anexpressive background DL. Here approximation can be used to compute simple frame-based representations of otherwise very complicated concept descriptions. OilEd isa widely accepted ontology editor and it can be linked to both state of the art DLreasoners, Racer [13] and FaCT [15]. Hence this editor is a good starting pointto provide users from practical applications with non-standard inference reasoningservices. The prototype system Sonic is the first system that provides some of thenon-standard inference reasoning services via a graphical user interface and thus makesthem accessible to a wider user group. Sonic was first introduced in [17] and it canbe downloaded from http://lat.inf.tu-dresden.de/systems/sonic.html.
In the next section we give an application example which underlines that—although the supported DLs are much less expressive compared to the DLs supported by thecurrent DL reasoners—the inferences implemented in Sonic can be useful in practice.
In Section3 we turn to the implementation of Sonic and describe how the inferencesare realized and and how Sonic is coupled to OilEd and the underlying DL reasoner Racer. Then we give an impression how users can work with Sonic and in the end we sketch how the Sonic prototype system can be extended in future versions.
Let us briefly recall the DLs covered by Sonic. Starting with a set NC of conceptnames and a set NR of role names concept descriptions are inductively defined withthe help of a set of concept constructors. The DL ALE offers the top- ( ) and bottom-concept (⊥), concept conjunction (C D), existential restrictions (∃r.C), value re- strictions (∀r.C), and primitive negation (¬P, P ∈ NC ). The DL ALC extends ALE byconcept disjunction (C D) and full negation (¬C). Extending each of these DLs by number restrictions, i.e., at most restrictions (≤ n r) and at least restrictions (≥ n r)one obtains ALEN and ALCN , respectively.
The semantics of these concept descriptions is defined in the usual model-theoretic way in terms of an interpretation I = (∆I, ·I). The domain ∆I of I is a non-emptyset of individuals and the interpretation function ·I maps each concept name P ∈ NCto a set P I ⊆ ∆I and each role name r ∈ NR to a binary relation rI ⊆ ∆I ×∆I.
The semantics are extended to complex concept descriptions in the usual way, see forexample [1, 6].
A TBox is a finite set of concept definitions of the form A ≡ C, where A is a concept name and C is a concept description. Sonic can only process TBoxes thatare unfoldable, i.e., they are acyclic and do not contain multiple definitions. Conceptnames occurring on the left-hand side of a definition are called defined concepts. Allother concept names are called primitive concepts.
Next, let us illustrate the procedure of computing the lcs for ALEN -concept de- scriptions and the approximation of ALCN -concept descriptions by ALEN -concept de-scriptions with an application example. Consider the TBox T with ALCN -conceptdescriptions modeling Airbuses and their configurations. T contains the followingconcept definitions: ∃has-configuration.Cargo-Config∃has-configuration.(Passenger-Config (≥ 2 has-configuration)∀ has-configuration.(Passenger-Config ∃has-configuration.((≤ 419 has-seats) ∃has-configuration.((≤ 380 has-seats) If we want to find the commonalities between the concepts Airbus-300 and Airbus-340by using the lcs in ALEN , we first have to compute the approximation of Airbus-340since its concept definition contains a disjunction. After that can we compute the lcsof Airbus-300 and approxALEN (Airbus-340).
In order to compute the approximation of the concept definition of Airbus-340 we first make implicit information explicit. In our example this is done by propagating thevalue restriction onto the two existential restrictions which yields the new disjunction: After the propagation of the value restriction, we can obtain the approximation of ourexample concept description by simply computing the lcs of these two disjuncts. Theydiffer only w.r.t. the number occurring in the at-most restrictions. Consequently wehave to pick the at-most restriction with the greater number from the two disjunctsand conjoin them with (Passenger-Config (≥ 261 has-seats) to obtain their lcs. We get the following approximation of Airbus-340: To compute the lcs of approxALEN (Airbus-340) and the concept definition of Airbus-300,we need to unfold the concept Airbus-300 w.r.t. T by replacing Cargo-Config with itsconcept definition ¬Passenger-Config. It obvious now that the concept descriptionimplies two distinct configurations, since one of the existential restriction requiresPassenger-Config and the other one ¬Passenger-Config. Thus the concept definition ofAirbus-300 induces (≥ 2 has-configuration) which occurs in approxALEN (Airbus-340) di-rectly. The primitive concept Plane appears in both concept descriptions and thus alsoin their lcs. Since the concept definition of Airbus-300 does not imply a value restrictionthe lcs does not contain any. Furthermore, we have to compute the lcs of each of thetwo existential restrictions from Airbus-300 and the one from approxALEN (Airbus-340).
We obtain for the overall lcs: lcs(approxALEN (Airbus-340), Airbus-300) = The first existential restriction is redundant and therefore can be omitted—it wouldnot be returned by our implementation. We have now extracted the commonalities ofthe Airbus-340 and the Airbus-300: they are both planes with at least two configura-tions where one configuration is a passenger configuration with up to 3 classes.
Although the DLs under consideration are not very expressible compared to the DLs handled by the state of the art DL reasoners this application example shows thatan implementation of lcs and approximation for these DLs can be very useful to helpusers to extend their ontologies.
The Sonic system implements the algorithms for computing the lcs for ALEN -conceptdescriptions and the approximation of ALCN - by ALEN -concept descriptions. Fur- thermore, Sonic implements a graphical user interface to offer these non-standardinferences and an interface to a DL reasoner needed for subsumption queries.
We briefly sketch the main idea of the inference algorithms here. The algorithm forcomputing the lcs in ALEN was devised and proven correct in [16], thus our imple-mentation is well-founded. The algorithm for computing the lcs of ALEN -conceptdescriptions consists of three main steps: 1. Unfold the input concept descriptions by recursively replacing defined concepts 2. Normalize the unfolded concept descriptions to make implicit information (e.g.
inconsistencies, induced existential restrictions, induced value restrictions or in-duced number restrictions) explicit.
3. Represent the normalized concepts as concept trees, build the cross-product of the trees and read out a concept description from it.
For the DL ALEN the normalization and the structural comparison are much moreinvolved than in ALE. Firstly, the number restrictions for roles, more precisely the atmost restrictions, necessitates merging of role-successors mentioned in the existentialrestrictions. To obtain all valid mergings is a combinatorial problem. Second, thecommonalities of all mergings for existential restrictions of a concept description haveto be determined by computing their lcs. These in turn are then used to compute thecross-product. In our implementation we use lists as data structures to represent theconcept descriptions and implement the algorithms without advanced optimizationsin order to keep this first implementation of the lcs for ALEN -concept descriptionssimple and easy to test.
The lcs algorithm for ALEN can return concept descriptions double exponential in the size of the input concepts in the worst case. Nevertheless, so far the lcs inALEN realized in Sonic is a plain implementation of this algorithm. Surprisingly, afirst evaluation of our implementation shows that for concepts of an application TBoxwith only integers from 0 to 5 used in number restrictions the run-times remainedunder a second (with Allegro Common Lisp on a Pentium IV System, 2 GHz). Ourimplementation of the lcs for ALE-concept descriptions as described in [3] uses lazyunfolding. Due to this technique shorter and thus more comprehensible concept de-scriptions can be obtained more quickly, see [3]. To implement lazy unfolding for thelcs for ALEN -concept descriptions in Sonic is yet future work.
The algorithm for computing the approximation of ALCN -concept descriptions by ALEN -concept descriptions was introduced and proven correct in [6]. The idea under-lying this algorithm is similar to the lcs algorithm. For approximation the normaliza-tion process additionally has to build a disjunctive normal form on each role-level by“pushing” the disjunctions outward. With concept descriptions in this normal formthe commonalities of the disjuncts are computed by applying the lcs on each role-level.
The approximation of ALCN - by ALEN -concept descriptions is also implemented in Lisp and uses the above mentioned implementation of the lcs for ALEN -conceptdescriptions as a subfunction. A first implementation of the approximation of ALC-by ALE-concept descriptions is described in [7]. This implementation is now extendedto number restrictions and provided by Sonic.
In the worst case the approximation in both pairs of DLs can yield concept de- scriptions that are double exponential in the size of the input concepts descriptions.
Nevertheless, this is not a tight bound. A first evaluation of approximating randomlygenerated concept descriptions shows that, unfortunately, both implementations runout of memory already for concepts that contain several disjunctions with about 6 dis-juncts. It is unknown whether this kind of concept descriptions appears in applicationTBoxes from practical applications. Nevertheless, effective optimization techniquesare needed for computing approximation, before this service can be applied to largeontologies. Similar to the lcs one can apply lazy unfolding to avoid “unnecessary”unfolding and thereby obtain smaller concept descriptions even faster. Besides lazyunfolding there is also the approach of so called nice concepts described in [9] knownas an optimization technique for approximation. Currently these techniques are im-plemented and evaluated for approximation of ALC- by ALE-concept descriptions in astudent’s project in our group.
The implementation of the algorithms for both inferences are realized in a straight- forward way without sophisticated data structures or advanced optimizations as, forexample the caching of results. This facilitated the testing and debugging of the Sonicprototype.
In order to provide the inferences lcs and approximation to users of the ontology editor OilEd, we need not only to connect to the editor OilEd, but also to a DL reasoner since both inferences, lcs and approximation, use subsumption tests heavily duringtheir computation. The connection from Sonic to the editor OilEd, is realized asa plug-in. Like OilEd itself, this plug-in is implemented in Java. Sonic’s plug-inis implemented for OilEd version 3.5.3 (or higher) and realizes mainly the graphicaluser interface of Sonic. A screen-shot of the lcs tab in Sonic is shown in Figure 3.2.
Sonic’s Java plug-in connects via a Telnet connection to the Lisp implementation of the non-standard inferences to pass concept descriptions or messages between thecomponents.
The OilEd user can classify an ontology in the OilEd editor, by either connect- ing OilEd to the FaCT reasoner via a CORBA interface or to any DL reasonersupporting the DIG (“Description Logic Implementation Group”) protocol. The DIGprotocol is an XML-based interface for DL systems with a tell/ask syntax, see [5]. DLdevelopers of most DL systems have committed to implement this standard in theirsystem making it a standard for DL related software.
Sonic must have access to the same instance of the reasoner that OilEd is con- nected to in order to have access to the information from the ontology, more precisely,to make use of stored concept definitions and of cached subsumption relations obtained Figure 1: Sonic’s lcs Tab in OilEd.
during classification by the DL reasoner. If OilEd and the DL reasoner do not haveconsistent versions of the ontology, the computed results for lcs and approximationmight simply be incorrect due to this inconsistency.
Sonic needs the functionality of retrieving the concept definition of a concept defined in the TBox in order to perform unfolding.
included in the DIG protocol, we cannot use the DIG interface to connect to the DLreasoner. Since the CORBA interface to FaCT is slow, we use Racer as underlyingDL reasoner. Sonic connects to Racer version 1.7.7 (or higher) via the TCP socketinterface described in [14]. Note, that in this setting the Racer reasoner need notrun locally, but may even be accessed via the web by OilEd and Sonic.
After the user has started the OilEd editor with Sonic, the lcs and approximationinference are available on two extra tabs in OilEd— as shown in Figure 3.2. Afterthe OilEd user has defined some concepts in the OilEd ontology, has connected tothe DIG reasoner Racer and classified the ontology, she can use, for example, the lcsreasoning service. In order to do so she can select some of the concept names from theontology on the lcs tab. When the button ‘compute lcs’ is clicked, the selected conceptnames are transmitted to Sonic’s Lisp component and the lcs is computed based on the current concept definitions stored in Racer.2 The concept description obtainedfrom the lcs implementation is send to the plug-in via Telnet and displayed on the lcstab. The approximation inference is offered on a similar Sonic tab in OilEd.
Since the concept descriptions returned by the lcs and the approximation inference can be very large, it is not feasible to display them in a plain fashion. Sonic displaysthe returned concept descriptions in a tree representation, where uninteresting sub-concepts can be folded away by the user and inspected later. In Figure 3.2 we seehow the concept description for the lcs obtained from the application example in Sec-tion 2 is displayed on Sonic’s tab in OilEd. Based on this representation Sonic alsoprovides limited functionality on both of its tabs to edit concept descriptions. OilEdusers can ’cut’ subdescriptions from the displayed concept description and therebyreduce the displayed concept description to interesting aspects. OilEd users can also’cut and store’ (a part of) the obtained concept description under a new concept namein their ontology.
The Sonic prototype is a graphical tool for supporting main steps of the bottom-up approach for augmenting ontologies. These steps are realized by implementationsof the least common subsumer in ALEN and the approximation of ALCN - by ALEN -concept descriptions. These reasoning services can be used from within the OilEdontology editor. Since Sonic is the first system that implements a graphical userinterface for non-standard inferences, it is now possible to evaluate how useful theseinference services are to users from practical applications.
Currently there is a big language gap between the DLs implemented in the state of the art DL reasoners and the DLs for which non-standard inferences are investigatedor even implemented. To overcome this language gap to some extend we are currentlystudying a new approach to compute approximate solutions for the lcs and thus obtaina “good” common subsumer (instead of a least one) for input concept descriptionsreferring to concepts defined in a more expressive DL, see [2].
implementation of approximation—on the one hand to speed-up the computation andon the other hand to obtain smaller concepts. This can be achieved by using lazyunfolding as our lcs implementation for ALE has shown, see [3]. Another step is toimplement minimal rewriting w.r.t. TBoxes to obtain more concise and thus bettercomprehensible result concept descriptions from both reasoning services. In the longerrun we want to comprise the implementations of the difference operator (see [7]) and ofmatching for ALE (see [11]) in Sonic and provide these inference services to users frompractical applications. The Sonic system can be down loaded for research purposesfrom http://lat.inf.tu-dresden.de/systems/sonic.html.
oller, Volker Haarslev and Sean Bechhofer for their help on how to implement Sonic’s linking to Racer and OilEd.
2This is why the TBox should be classified first.
usters, and Ralf Molitor. Computing least common sub- sumer in description logics with existential restrictions. In T. Dean, editor, Pro-ceedings of the 16th Int. Joint Conf. on Artificial Intelligence (IJCAI-99), pages96–101, Stockholm, Sweden, 1999. Morgan Kaufmann, Los Altos.
[2] Franz Baader, Baris Sertkaya, and Anni-Yasmin Turhan. Computing the least common subsumer w.r.t. a background terminology. In the Proceedings of 2004International Workshop on Description Logics (DL 2004). To appear.
[3] Franz Baader and Anni-Yasmin Turhan. On the problem of computing small representations of least common subsumers. In Proceedings of the 25th GermanAnnual Conf. on Artificial Intelligence (KI’02), LNAI. Springer–Verlag, 2002.
[4] Sean Bechhofer, Ian Horrocks, Carole Goble, and Robert Stevens.
Reason-able Ontology Editor for the Semantic Web. In Proceedings of the 24thGerman Annual Conf. on Artificial Intelligence (KI’01), volume 2174 of LNAI,pages 396–408, Vienna, Sep 2001. Springer-Verlag.
oller, and Peter Crowther. The DIG description logic interface. In Proceedings of the 2003 Description Logic Workshop (DL 2003),Rome, Italy, 2003.
ALCN -concept descriptions. In Proceedings of the 2002 Description Logic Work-shop (DL 2002), number 53 in CEUR-WS. RWTH Aachen, April 2002.
usters, and Anni-Yasmin Turhan. Approximation and difference in description logics. In D. Fensel, D. McGuinness, and M.-A. Williams,eds., Proceedings of the 8th Int. Conf. on the Principles of Knowledge Represen-tation and Reasoning (KR-02), 2002. Morgan Kaufmann Publishers.
[8] Sebastian Brandt and Anni-Yasmin Turhan. Using non-standard inferences in de- scription logics — what does it buy me? In Proceedings of the KI-2001 Workshopon Applications of Description Logics (KIDLWS’01), number 44 in CEUR-WS,Vienna, Austria, September 2001. RWTH Aachen.
[9] Sebastian Brandt and Anni-Yasmin Turhan. An approach for optimized approx- imation. In Proceedings of the KI-2002 Workshop on Applications of DescriptionLogics (KIDLWS’02), number 63 in CEUR-WS, Aachen, Germany, September2002. RWTH Aachen.
[10] Sebastian Brandt, Anni-Yasmin Turhan, and Ralf K¨ standard inferences for description logics with transitive roles. In Proceedingsof the 10th Int. Conf. on Logic for Programming and Automated Reasoning(LPAR’03), LNCS. Springer, 2003.
[11] Sebastian Brandt. Implementing matching in ALE—first results. In Proceedings of the 2003 International Workshop on Description Logics (DL2003), CEUR-WS,2003.
[12] Wiliam Cohen, Alex Borgida, and Haym Hirsh. Computing least common sub- sumers in description logics. In W. Swartout, editor, Proceedings of the 10th Nat.
Conf. on Artificial Intelligence (AAAI-92), pages 754–760, San Jose, CA, 1992.
AAAI Press/The MIT Press.
oller. RACER system description. In Proceedings of the International Joint Conference on Automated Reasoning IJCAR’01, LNAI.
Springer Verlag, 2001.
RACER User’s Guide and Manual, Sept.
2003. available from: http://www.sts.tu-harburg.de/~r.f.moeller/racer/racer-manual-1-7-7.pdf.
[15] Ian Horrocks. Using an expressive description logic: FaCT or fiction? In A.G.
Cohn, L.K. Schubert, and S.C.Shapiro, editors, Proceedings of the 6th Int. Conf.
on the Principles of Knowledge Representation and Reasoning (KR-98), pages636–647, 1998.
usters and Ralf Molitor. Computing Least Common Subsumers in ALEN .
In B. Nebel, editor, Proceedings of the 17th Int. Joint Conf. on Artificial Intelli-gence (IJCAI-01), pages 219–224. Morgan Kaufman, 2001.
[17] Anni-Yasmin Turhan and Christian Kissig. Sonic—Non-standard inferences go OilEd. In Proceedings of the International Joint Conference on Automated Rea- soning IJCAR’04, LNAI. Springer Verlag, 2004. To appear.

Source: http://www.christiankissig.com/cms/files/pubs/TurhanKissigDL04.pdf