UI-FAME is a Java-based forgetting system for creating views of ALC-TBoxes. The system implements the method developed in our previous work for forgetting concept and role names from ALC-TBoxes. In this paper, we introduce UI-FAME and compare it with LETHE, a peer forgetting system for ALC-ontologies and many its extensions, over the ALC-TBox fragment of 494 realistic ontologies taken from the Oxford Ontology Repository. The comparison considers success rates, speed, memory consumption as the principal indicators to assess the performance of the two systems. For validation purpose, we also explore the semantic relationships between the views computed by the two systems. The experimental results showed that UI-FAME attained in general better success rates and performance results than LETHE. We found that in 97.08% cases UI-FAME and LETHE computed logically equivalent views, in 2.06% cases LETHE's solution entailed UI-FAME's solution but not the other way round, in 0.79% cases UI-FAME's solution entailed LETHE's solution but not the other way round, and in 0.07% cases they had no mutual entailment relationship. This was somewhat undesirable and thus needs further investigation.
In Computer Science and Arti cial Intelligence, ontology is a technical term denoting an artifact that is designed for a speci c purpose to enable the modeling of knowledge about a domain of discourse. More speci cally, an ontology is a formal representation of the knowledge within a domain of discourse using a set of representational primitives. These representational primitives are classes (concepts), class members (individuals ), and properties (attributes of class members or relationships among class members).
Ontologies model domain knowledge of applications rooted in numerous industry sectors, including energy, laws, biology, medical, and healthcare sectors. ? Copyright © 2020 for this paper by its authors. Use permitted under Creative
Modern ontologies are speci ed in the Web Ontology Language (OWL) that has
a formal semantics based on description logics (DLs) [
Computing Views of Ontologies With the growing usage of ontologies in real-world applications, not only has the number of available ontologies increased considerably, but also they are becoming large in size, complex in structure, and thus more di cult to manage. Moreover, capturing domain knowledge in the form of ontologies is labor-intensive work from the engineering perspective. There is therefore a strong demand for techniques and automated tools for re-engineering with ontologies, so that existing ontologies can be reused to their full potential | new ontologies can be generated from existing ones and are not necessarily developed from scratch, which is costly and error-prone. Computing views of ontologies is one of such ontology re-engineering operations that seeks to generate new ontologies from existing ones. A view V of an ontology O is a new ontology obtained from O using only part of O's signature, namely the target signature, while preserving the original meanings of the terms in the target signature. Computing ontology views is useful for many ontology re-engineering and related tasks. These include, but are not limited to the following ones.
i. Ontology Reuse: Knowledge modelled in ontologies is often rich,
heterogeneous, and multi-topic related, while applications are interested in or focused
on speci c parts. Compared to exploiting existing ontologies or building new
ontologies from scratch, extracting fragments w.r.t. speci c topics from
existing ontologies and reusing them in a specialized context is simpler, cheaper,
and thus more interesting to the ontology engineers.
ii. Information Hiding Medical and military ontologies may contain sensitive
information that must be kept con dential to the public and the
correspondences when the ontologies are published, shared, or disseminated. The
condentiality and protection can be achieved through the removal of concept
and role name relative to sensitive information.
iii. Ontology-Based Query Answering: Taking ontological knowledge into
account when retrieving data from relational databases has been widely
acknowledged. It has been found in many cases [
Computing ontology views is also useful for many other tasks such as
ontology alignment and merging [
Basics of Forgetting Forgetting is a form of non-standard reasoning concerned with eliminating from an ontology a set of concept and role names in its signature, namely the forgetting signature, in such a way that, after the elimination, all logical consequences are preserved up to the remaining signature. Forgetting in this sense can be used as a means of computing views of ontologies: the ontology obtained from forgetting, namely the forgetting solution, is the view of the original ontology for the target signature, which corresponds to the remaining signature in forgetting.
Related notions of forgetting are inseparability and conservative extensions [
Forgetting is an inherently di cult problem; it is much harder than standard
reasoning (satis ability testing), and very few logics are known to be complete
for forgetting. Previous studies have shown that: (i) deductive or model-theoretic
solutions of forgetting do not always exist for E L and ALC [
Although forgetting is a challenging problem, there is however general
consensus on its potential for ontology-based knowledge processing, and there has
been continuous e orts dedicated into the development and automation of
practical methods for forgetting. A few such methods have thus been developed and
automated for various description logics. These methods include LETHE [
Contribution
In this paper, we introduce UI-FAME, a Java implementation of the forgetting
method developed in our previous work [
Let NC and NR be pairwise disjoint and countably in nite sets of concept names and role names, respectively. Concepts in ALC (or concepts for short) have one of the following forms:
> j ? j A j :C j C u D j C t D j 9R:C j 8R:C; where A 2 NC, r 2 NR, and C and D are arbitrary concepts.
An ALC-TBox is a nite set of axioms of the form C v D (concept inclusions ) and the form C D (concept equivalences), where C and D are concepts. In the remainder of this paper, the terms TBox and ontology are used interchangeably.
The semantics of ALC-TBox is de ned using an interpretation I = h I ; I i, where I denotes the domain of the interpretation (a non-empty set), and I denotes the interpretation function, which assigns to every concept name A 2 NC a set AI I , and to every role name r 2 NR a binary relation rI I I . The interpretation function I is inductively extended to concepts as follows: >I =
I
?I = ; (C u D)I = CI \ DI (:C)I =
I nCI (C t D)I = CI [ DI (9R:C)I = fx 2 (8R:C)I = fx 2
I j 9y:(x; y) 2 RI ^ y 2 CI g
I j 8y:(x; y) 2 RI ! y 2 CI g
Let I be an interpretation. A concept equivalence C D is true in I (or I satis es C D) i CI DI . A concept inclusion C v D is true in I (or I satis es C v D) i CI DI . I is a model of an ontology O i every axiom in O is true in I. In this case, we write I j= O.
By sigC(X) and sigR(X) we denote respectively the sets of the concept names and role names occurring in X, where X ranges over concepts, axioms, and a set of axioms (ontologies). We de ne sig(X) = sigC(X) [ sigR(X). De nition 1 (Deductive Forgetting). Let O be an ALC-TBox and let F sig(O) be a set of concept and role names. An ALC-TBox V is a solution of deductively forgetting F from O i the following conditions hold: (i) sig(V) sig(O)nF , and (ii) for any axiom with sig( ) sig(O)nF , V j= i O j= .
De nition 1 means that V (the forgetting solution) has the same logical consequences with O (the original ontology) in the remaining signature sig(O)nF . F is called the forgetting signature, i.e., the set of concept and role names to be eliminated. V can be regarded as a view of O w.r.t. the remaining signature sig(O)nF in the sense that it gives the same answers as O to the queries formulated using the names in sig(O)nF . In traditional databases, a view is a subset of the database, whereas in ontologies, a view is more than a subset; it contains not only axioms that are contained in the original ontology, but also newly derived axioms that are entailed by the original ontology (implicitly contained in the original ontology). Such new axioms can be derived during the forgetting process. The remaining signature in forgetting corresponds to the target signature in the problem of computing views of ontologies.
A view V of an ontology O is the strongest entailment of O in the target signature. By de nition, V is a strongest entailment of O in sig(O)nF , if O j= V and for any ontology V0 such that O j= V0 and sig(V0) sig(O)nF , then V j= V0. In general it can be shown that: V is a view of an ontology O for a speci c target signature i V is the strongest entailment of O in this signature. Views are unique up to logical equivalence, i.e., if both V and V0 are views of O for a target signature, then they are logically equivalent, though their representations may not be identical. 3
UI-FAME is implemented in Java using the OWL API,7 a Java API for creating, parsing, manipulating, and serializing OWL ontologies, and is released under the open source licenses LGPL8 and Apache9. UI-FAME uses the OWL API Version 3.4.7 for the aforementioned tasks.
Figure 1 depicts the general design of UI-FAME. Given as input to UI-FAME are an ALC-TBox O, a set FC sigC(O) of concept names to be forgotten, and
a set of FR sigR(O) of role names to be forgotten. Together, FC and FR make up the forgetting signature F . The input ontology must be given as a text le in XML, OWL, RDF, or TURTLE format, or a URL pointing to the le. UI-FAME takes only ALC-axioms; axioms not expressible in ALC are removed. Figures 2 lists the types of axioms handled by UI-FAME, which, via simple reformulations, can be represented as SubClassOf axioms.
Types of Axioms SubClassOf Representation
SubClassOf(C1 C2) SubClassOf(C1 C2) EquivalentClasses(C1 C2) SubClassOf(C1 C2), SubClassOf(C2 C1)
DisjointClasses(C1 C2) SubClassOf(C1 ObjectComplementOf(C2)) ObjectPropertyDomain(R C) SubClassOf(ObjectSomeValuesFrom(R owl:Thing), C) ObjectPropertyRange(R C) SubClassOf(owl:Thing ObjectAllValuesFrom(R C))
UI-FAME computes a solution of forgetting F from O by eliminating single
concept and role names in F . Concept and role names are eliminated using two
mutually independent calculi for respectively concept and role name elimination
for ALC-TBoxes [
We compared UI-FAME with LETHE to gain an insight into the overall performance of the two systems considering success rate, speed, size of resulting ontology and memory consumption.10
Figure 3 depicts the comparison framework. Given O as the input ontology, an ALC-TBox fragment O0 is obtained via the preprocessing step by removing all axioms not expressible as ALC-TBox axioms. Based on sig(O0), forgetting signatures, which are randomly generated in the Forgetting Signature Generator module, are delivered into UI-FAME and LETHE together with O0. Here, we didn't pick symbols by their frequency of occurrence. On account of forgetting frequent symbols is not friendly to the case study, which is very important in this phase. But randomly symbol generation is not enough, for further investigations, we may use more sampling strategies.
VLETHE and VUI-FAME are the ontologies obtained from forgetting (not
necessarily forgetting solutions) using respectively LETHE and UI-FAME. We used
10 We did not bring the implementation of the forgetting method of [
TestNG11, one of the most powerful testing frameworks, for performance evaluation, and HermiT12, one of the most reliable DL reasoners, for entailment relationship checking of the forgetting solutions computed by UI-FAME and LETHE. The experiments were run on a laptop with an Intel Core i7-9750H processor, 6 cores running at up to 2.60 GHz, and 16 GB of DDR4-1330 MHz memory. Both UI-FAME and LETHE were allocated 8GB heap space for each test round. 4.2
Test Data
The ontologies used for the comparison were taken from the Oxford Ontology Repository (Oxford-ISG).13 Oxford-ISG contained a large number of ontologies collected from multiple sources. In particular, Oxford-ISG contained 797 ontologies, and we took 494 of them with the number jT Boxj of TBox axioms in the ontology not exceeding 10000. We further split the entire corpus of 494 ontologies into three groups: Corpus I with 10 jT Boxj 1000, containing 356 ontologies, Corpus II with 1000 jT Boxj 5000, containing 108 ontologies, and Corpus III with 5000 jT Boxj 10000, containing 26 ontologies. This gives a clearer insight into how LETHE and UI-FAME perform forgetting for ontologies of different sizes. Table 1 shows statistical information about the selected ontologies, where jNC j and jNRj denote the average numbers of the concept names and role names in the selected ontologies. To t for real-world application scenarios, the standard of forgetting success was set to be: (1) forgetting all the terms in the forgetting signature F ; (2) without 11 https://testng.org/doc/ 12 http://www.hermit-reasoner.com/ 13 https://www.cs.ox.ac.uk/isg/ontologies/ introducing any extra expressivity outside of ALC in the forgetting solutions (de ners); (3) nished in the given timeout; (4) nished in the given space limit. In this experiment, we limited the timeout to 20 minutes and heap space to 8GB.
Both UI-FAME and LETHE were tested over the three Oxford-ISG snapshots. For each snapshot, we considered forgetting respectively 10% and 30% of the terms from the signature of each ontology. With a randomly generated forgetting signature, the test was repeated three times for UI-FAME and LETHE.
I 0.3 II
III
I 0.1 II
III
I 0.3 II
III
The results are shown in Table 2, where \Duration" denotes the average time consumption of the successful cases, and \Extra" denotes the percentage of cases introducing extra expressivity outside of ALC. Such expressivity is not desired to be in forgetting solutions; if extra expressivity cannot be removed from the resulting ontologies, then the forgetting fails.
UI-FAME had better success rates than LETHE because of a less timeout rate attained by UI-FAME (TO-Rate). Apparently, UI-FAME was faster than LETHE when forgetting percentage is relatively big. This is partly because the elimination in LETHE is based on resolution, while UI-FAME uses both resolution and Ackermann's Lemma; the latter allows concept names to be eliminated more cheaply when forgetting task is big. In addition, we found that in almost 97% of the elimination rounds, a concept name could be eliminated using Ackermann's Lemma. Another fact that accounts for such performance results is that UI-FAME introduces de ners in a conservative manner (only when really necessary), while LETHE introduces them in a systematic and exhaustive manner, as is illustrated in the following example.
Example 1. Let O = fC t 9r:A; E t 8r::Ag and F = fAg. ND is the de ners set disjoint with the signature of O. UI-FAME applies directly the combination rule (Case 8) to O to eliminate A, yielding the solution fC t 9r:>; C t Eg. LETHE computes the same solution as our method does, but the derivation is more complicated, involving these steps: Step 1: Normalization (D1; D2 2 ND): f1: C t 9r:D1; 2: :D1 t A; 3: E t 8r:D2; 4: :D2 t :Ag.
Step 2: Role propagation (D3 2 ND): f5: C t E t 9r:D3 (from 1, 3), 6: :D3 t D1; 7: :D3 t D2g.
Step 3: Classical resolution: f8: :D3 t A (2, 6), 9: :D3 t :A (4, 7), 10: :D3 (8, 9)g Step 4: Existential role elimination: f11: C t E (5, 10)g.
Step 5: At this point, O is saturated w.r.t. A, and no further inferences can be performed. LETHE removes all clauses that contain A; Clauses 2, 4, 8 and 9 are thus removed.
Step 6: Clause 5 is redundant because of 11. Clauses 6 and 7 are redundant because of 10. Hence, 5, 6 and 7 are removed.
Step 7: Only Clauses 1, 3, 10, 11 remain. LETHE eliminates the de ners in Clauses 1, 3 and 10 by puri cation, yielding: f12: C t 9r:>; 13: E t 8r:>; 14: E t F g. As 13 is a tautology, the forgetting solution computed by LETHE is f12; 14g.
The results also show that UI-FAME had lower memory consumption during the forgetting process; see the \Mem" column. In particular, LETHE's memory consumption was about four times of UI-FAME. We believe that this could be attributed to the de ner introduction mechanism employed by LETHE. 0-1 1-2 2-4 4-10 10-20
Fig. 4. Statistical graph of samples in each time period 1000 800 tn 600 u o C e s aC 400 200 0 prototype_0.1 prototype_0.3 lethe_0.1 lethe_0.3
Figure 4 depicts the cach time distribution for all the successful cases, where it can be seen that most successful cases were nished within 1 second for both LETHE and UI-FAME, while UI-FAME had more such cases. In most test cases, the variation in the sizes of the forgetting signatures did not a ect the overall time consumption too much. This was an undesirable yet interesting observation which is worth a comprehensive study; we leave this as one of our future work. 10000 8000 ) g n i t t e rg 6000 o F r e t f A ( ize 4000 S x o B T 2000 0 0 2000 4000 6000
TBox Size(Before Forgetting)
Figure 5 exhibits the changes in the number of the axioms in the ontologies
before and after forgetting in each group of experiments. In general, with the
increase in the size of the original ontologies, the size of the forgetting solutions
decreases; this seems against the theoretical result found in [
Entailment Relationship Checking In principle, UI-FAME and LETHE should compute logically equivalent forgetting solutions for the same problems, which are the strongest entailment sets in the target signature, though their solutions may look di erent (having distinct representations). Based on the forgetting solutions obtained in the experiment, we compared the entailment relationship of these two systems for the successPrototype_0.1 Prototype_0.3 LETHE_0.1
LETHE_0.3 8000 10000 ful cases. HermiT14 was employed to compute the inequivalence between the forgetting solutions computed by UI-FAME and LETHE.
The results showed that in 97.08% cases UI-FAME and LETHE computed logically equivalent forgetting solutions, in 2.06% cases LETHE's solution entailed UI-FAME's solution but not the other way round, in 0.79% cases UI-FAME's solution entailed LETHE's solution but not the other way round, and in 0.07% cases they had no mutual entailment relationship. The inequivalent cases are caused by the data procession or maybe tool bugs. This is somewhat undesirable and thus needs further investigation. 5
This paper presents an empirical comparison of two forgetting systems, namely UI-FAME and LETHE, showing better performance of UI-FAME.
Previous work has been largely focused on forgetting concept and role names, while there has been little attention paid to the problem of nominal elimination. This considerably restricts the applicability of forgetting for many real-world applications such as information hiding and privacy protection, where nominals are extensively present. Our immediate step for future work is to develop a forgetting method able to eliminate not only concept names and role names, but also nominals in expressive description logics. 14 http://www.hermit-reasoner.com/