The OWL2's populators are currently an important support to empirically evaluate the reasoners and/or to escort the practitioners by leveraging instantiations in their knowledge bases. In this paper, after having evoked the closest approach describing their strengths and weakness, we present Just another Populator of TBOX (JPoT). This purely syntactic and domain independent populator is based on a random process of concept, role and data instantiations guaranteeing consistency of knowledge bases founded on TBOXes expressed in ALCQ(D). Moreover, we demonstrate that data instantiations can be tricky when the expectation of the modeler is to obtain a sound knowledge base able to pass the equivalent of a Turing test. Finally, we evaluate the performances of JPoT.
The rise of the domain ontologies in OWL2
compelled more and more practitioners to make
their data available
Our proposal is to create a tool that is Just another Populator of TBOX (JPoT) performing populations like a domain independent SDG and guaranteeing consistency of the knowledge base (that is defined as the union of the TBOX and the ABOX). The subsequent parts of the article are as follows: Section 2 presents the related works, Section 3 presents JPoT, Section 4 performs an evaluation and Section 5 explores some perspectives.
Very few SDGs have been developed in order to perform some stress tests before deploying an ontology in a Semantic Web application.
According to the creators, the Lehigh
University Benchmark
Another remarkable tool named OTAGen
Note that after this proposal, another approach
proposed a purely TBOX generation with different
reasoning complexities resulting from the relative
proportions of the design patterns of
biomedical structures representation
Finally, the only approach that can handle a
lack or inaccessibility of data in ABOXes when a
TBOX is already available is SKTI - a synthetic
data generator
This last solution is the closest related work with JPoT as a domain independent SDG that can populate TBOXes provided by users. Next, we will describe the heuristics JPoT follows to populate these TBOXes by guaranteeing consistency.
Formally, every Description Logic is based on
some finite sets: a set CA of concepts names, a
set DT of datatype names, a set RA of abstract
role names and a set RT of concrete role names.
Baader and Nutt introduced the notion of
interpretation in first-order logic
Note that the definition we introduce below is an adaptation of the interpretation presented in the OWL2 direct semantic1.
Definition (Interpretation). An interpretation I is a tuple I = h I , D, ·I i where: - I is the domain, i.e. a set of individuals, - D is a data-type domain disjoint with I , - ·I is the interpretation function which maps: - each A 2 CA to a set AI ✓ I , - each r 2 RA to a relation rI ✓ I ⇥ I , - each D 2 DT to a value space DI ✓ D, - each t 2 RT to a relation tI ✓ I ⇥ D.
JPoT can actually parse and populate guaranteeing consistency the expressive power of the fragment ALCQ(D) described below: R ::= >R | RA | RT D ::= C | DT C ::= CA | ¬C | >C | ? C | (C u C) | (C t C) | 9 R.D | 8R.D | nR.D | nR.D | =nR.D Definition (TBOX). Given the concepts C, D 2 C , we call a TBOX a finite set of i-concept equivalences i.e. ’C ⌘ D’ or ii-concept inclusions, i.e. ’C v D’. An interpretation I is a model of a TBOX iff for all the axioms ' 2 TBOX, I ', with: - I (C v D) iff CI ✓ DI - I (C ⌘ D) iff CI = DI
JPoT deals only with unequivocal
TBOX
The set of all the concept, role and data assertions are respectively denoted Ac, Ar and Ad. JPoT is designed to populate TBOX in function of i - a number n of potential individuals2 ii - a total number m of assertions
n=| I | m=|Ac [ Ar [ Ad| iii - a ratio ⌧ of the number of concept assertions on the total number of assertions iv - a ratio ⇢ of the number of role assertions on the number of data assertions
|Ac| ⌧ = |Ac[ Ar[ Ad|
|Ar| ⇢ = |Ar[ Ad| 3.1
The process of concept assertions initiates with the computation of the set of all the disjoint class denoted 0T such that 0T = {{C, D}|C v+ ¬D} with v+ is the transitive closure of v.
Algorithm 1: Concept Assertions (CAs) Data: TBOX, m, ⌧ Result: round(m · ⌧ ) CAs x= 0; while x round(m · ⌧ ) do i = Draw( I ); ⇥ =FALSE; while ¬⇥ do
Cj = Draw(C); if {{C, Cj }| i 2 CI } \ 0T = ; ; then
⇥ =TRUE; end end Cj ( i); x++; end
Next, each individual drawn will instantiate the first concept drawn that is not disjointed with the concepts the individual already instantiates. The Algorithm 1 describes the concept assertions phase of JPoT. Note that, the function Draw(S) returns a randomly drawn element from a set S.
2Here “potential” means the possibility to have non drawn individuals that are not involved in any assertion. 3.2
JPoT dealing only with unequivocal TBOX, an axiom ti s.t. ti 2 TBOX can be defined like that: ti = {Ai v⌘ Fd Bl Fd 8qj .Dk Fd 9 ro.Cp dF Ssu.Ev} l j,k o,p u,v with Fd 2 { d, F}, v⌘2{v , ⌘} and S 2 { =, , }
We introduce a rearrangement of TBOXes to gather a set of axioms with concepts, datatypes, roles and constructors. The claim of JPoT is to populate TBOXes respecting the consistency but due to the Open World Assumption (OWA), we treat indifferently intersection and union. A derivation of a TBOX is defined like that: TBOX0 = {M(ti)|ti 2 TBOX} with M(ti) = {jS,k{Ai , 8 qj.Dk}oS,p{Ai , 9 ro.Cp}uS,v{Ai ,S su.Ev}}
During this stage, JPoT draws abstract roles and try to instantiate them. The Algorithm 2 uses the following heuristic: once an abstract role is drawn, an individual subject is drawn and the concepts it already instantiates are confronted to the domain of the abstract role. In case of disjointness another individual is drawn. After this step, the concepts of the chosen individual are confronted with the universal quantification axioms implying the abstract role in order to build a set of mandatory concepts for the individual object that has to be drawn in the next step. In the event the drawn individual i-has a concept in common with the mandatory ones, ii-doesn’t have concepts disjoint with the range of the abstract and iii-doesn’t violate the max cardinality restriction, this object individual will participate to the instantiation with the abstract role and the subject individual. In case of a violation of the cardinality restriction, another abstract role will be drawn and the process of selection will restart. For example, in the TBOX axiom "Scholarship v 9 managedBy.Referrer F 9 supervisedBy.Organisation", the algorithm will randomly choose one of the element of the disjunction either involving the management or the supervision (or the both if the scholarship is drawn again). Moreover, in the axiom "Scholarship v 8 remunerates.Researcher d 9 providesBy.Organisation", the algorithm will either ensure that if a scholarship remunerates someone it will be a researcher or suggest (in absence of an axiom concerning a range) that a scholarship is provided by an organisation.
Result: round(m · (1 ⌧ ) · ⇢ ) RAs y= 0; while y round(m · (1 ⌧ ) · ⇢ ) do ⌅ =FALSE; while ¬⌅ do ⌅ =TRUE; rk = Draw(RA); P9 = {(C, D)|C , 9 rk.D}; (A, B) = Draw(P9 ); if domain(rk) = ; then I = {A}; else I = domain(rk); ⇥ =FALSE; while ¬⇥ do i = Draw( I ) s.t. 9 C. i 2 CI ; if {{C, I}| i 2 CI } \ ⌦ T = ; then ⇥ =TRUE; end P8 = {(C, D)|C , 8rk.D}; foreach c 2 { C| i 2 CI } do if 9 (E, F ) 2 P8 s.t. c v E then
F 2 W ; end if range(rk) = ; then J = {B}; else J = range(rk); ⇥ =FALSE; while ¬⇥ do j = Draw( I ) s.t. 9 C. j 2 CI ; if {{C, J }| j 2 CI } \ ⌦ T = ; AND W ✓ { C| j 2 CI } then ⇥ =TRUE; end T ={hC, D, li|C, lrk.D _ C,=lrk.D}; l = 0; foreach c 2 { C| i 2 CI } do if 9h E, F, Li 2 T s.t. c v E then foreach d 2 { D| h2 DI ^ ( i, h)2 rk} do
if d ✓ F then l++; end
The populations performed by JPoT follow heuristics that guarantee consistencies of the knowledge bases only on the basis of the axioms in the TBOXes, in other words without any consideration of a specific domain. The produced ABOXes are somewhere semantically consistent because the population respects the semantic rules of the world present in the TBOXes. While the URIs of the individuals are all based on an integer in a selected range, the concepts they instantiate (concept assertions) and more the relation in which they are involved (role assertions) can represent an artificial but apparently real world. Let’s imagine the equivalent of the Turing test for a SDG model in which the ABOXes should appear as real 70% of the time to succeed the test. Even if we didn’t lead this experiment, we can objectively assume that a JPoT’s population implying only concept and role assertions could pass this test.
The test gets much more complicated to pass when JPoT has to deal with concrete roles due to a set of issues concerning the creation of data values. First, the usage of datatype has to be tackled with caution under a penalty of undecidability. OWL2 solved this problem by recommending datatypes defining a datatype map3 which lists the datatypes that can be used in the knowledge bases. Even restricting a population to this subset of datatypes, JPoT could fail a Turing test for SDG by strictly following the heuristic described in the Algorithm 3 due to a lack of semantic soundness in the generation of the data values for the data assertions. For example, let’s imagine a TBOX with the following axioms: each person has exactly one age that is an integer, an author has exactly one number of citations and hindex that are integers and if a person has a name it is always a string. As it is, JPoT could give an inhuman age for a person, assert a number of citations inferior to the hindex squared for a same author and provide an absurd name that would just be a random sequence of characters.
We implemented functions Gen(D, t) generating data values in adequation with a datatype D and with a concrete role t facing with different issues concerning the automatic population.
3https://www.w3.org/TR/owl2-syntax/ #Datatype_Maps
In the following, we will describe three issues for this generation of data values corresponding to three kinds of data assertions illustrating through the concrete roles hasAge (3.3.1), citations/hindex (3.3.2) and hasName (3.3.3).
Result: round(m · (1 ⌧ ) · (1 ⇢ )) DAs z= 0; while z round(m · (1 ⌧ ) · (1 ⇢ )) do ⌅ =FALSE; while ¬⌅ do ⌅ =TRUE; tk = Draw(RT); P9 = {(C, D)|C , 9 tk.D}; (A, B) = Draw(P9 ); if domain(tk) = ; then I = {A}; else I = domain(tk); ⇥ =FALSE; while ¬⇥ do i = Draw( I ) s.t. 9 C. i 2 CI ; if {{C, I}| i 2 CI } \ ⌦ T = ; then ⇥ =TRUE; end P8 = {(C, D)|C , 8tk.D}; foreach c 2 { C| i 2 CI } do if 9 (E, F ) 2 P8 s.t. c v E then
F 2 W ; end if range(tk) = ; then J = {B}; else J = range(tk); dj = Gen(J, tk); T ={hC, D, li|C, ltk.D _ C,=ltk.D}; l = 0; foreach c 2 { C| i 2 CI } do if 9h E, F, Li 2 T s.t. c v E then foreach d 2 { D|dh2 DI ^ ( i, dh)2 tk} do
if d ✓ F then l++; end
The usage of facet spaces is the royal road for the modeler to obtain a knowledge base capable of passing the SDG Turing test. The facet space was introduced as a set of pairs of the form (F,v) where F is a constraining facet and v a constraining value. Each such pair is mapped to a subset of the value space of the datatype. Thus, the data range of concrete roles can be restricted using a datatypeRestriction which restricts the value space of a datatype by a constraining facet. In the example of hasAge, the modeler can use a datatypeRestriction that would restrict the datatype xsd:nonNegativeInteger by using a singleton facet space i.e. the pair (xsd:maxExclusive,"123"ˆˆxsd:nonNegativeInteger) that corresponds to the limit for an age never reached in the history of the humanity. In addition in JPoT, we used a Gaussian distribution (with an expectation of 42 and a standard deviation of 10) in order to simulate an age distribution of researchers following a pyramidal shape.
Ensuring the soundness of data assertions restricting dataranges using datatypeRestrictions can still produce knowledge bases incapable of passing the SDG Turing test. In fact, one can say that the value of the subject of a data assertion has to be an integer less than 123, but one cannot say that the value of the subject of one data assertion is less than that of another data assertion. In the example of citations and hindex, the modeler doesn’t have the ability with the current expressivity of OWL2 to constraint the TBOX with the fact that the total number of citations of an author is greater than the hindex-squared. A proposition of extension for OWL24 allows the expression of linear equations but not of polynomial equations.
As we described for a numerical datatype, it is also possible to restrict dataranges using a datatypeRestriction for String with a pattern (well known as a regular expression). This expressivity can be usefull to generate knowledge bases capable of passing the SDG Turing test. For example, a model that would represent a social security number could use such a pattern.
4https://www.w3.org/2007/OWL/wiki/ Data_Range_Extension:_Linear_Equations But when the concrete role is hasName, even the usage of space facet doesn’t prevent to produce knowledge ineligible for a SDG Turing test. In this case, the only solution is to use another generator or API to produce a soundness value. Then we used the API JaNaG (Java Name Generator) which is a random name generator based on a name fragment database that creates relatively reasonably sounding names from different cultures/influences. 4
We performed an evaluation of the populator JPoT (the version of JPoT based on the OWLAPI 4.1.0) using a simplified model of the scholar domain illustrated in Figure 1. We highlight here that the ontological choices made at this example are intuitive, but arguable. Our aim was to describe the performance of JPoT, not to propose an ontological analysis of the scholar domain.
We introduce here a UML interpretation for
the fragment ALCQ(D). We denote CA a set
of concept names, RA a set of abstract role
names, RT a set of concrete role names, DT a
set of datatype names and S a set of symbols
for Descriptions logics interpreted in first order
logic
Note that we use the following notations: - 8=nr.C ⌘ 8 r.C u =nr.C - 8 nr.C ⌘ 8 r.C u nr.C - 8 nr.C ⌘ 8 r.C u nr.C Definition (UML Interpretation U). Let {C, D1, . . . , Dn, E} ✓ C, {r1, . . . , rn} ✓ RA, {t1, . . . , tm} ✓ RT, { 1, . . . , m} ✓ DT and {µ1, . . . , µn, 1, . . . , m} ✓ ⌦ : In this domain, Authors (which are Persons with names) write Publications, which can be classified into Papers, Articles, Chapter or Books. A Publication can be quoted by another Publication, and Authors have a total number of citations and an hindex. A Researcher can be remunerated by Scholarships provided by Organisations in such a way that an Organisation can provide several Scholarships, and a Scholarship can remunerate a maximum of two Researchers (e.g. organisations authorizing to change one time the “owner” of a scholarship). Authors and Organisations can be associated. There are two kinds of Organisations: Team and University. A Team can be part of Universities.
D1 µ1 r1 rn µn
Dn E m
C -t1: 1[ 1]
...
-tm: m[ m] n (C v E u d `(µi)ri.Di u i=1 dm `( j )tj . j )U j=1
Our empirical analysis has been performed on a machine equipped with an Intel Core at 3.30GHz and Ubuntu 15.04. We ran the Java-based reasoner Pellet 2.4.0 with Sun Java 1.8, and we set the maximum heap space to 7.5 GB. We populated the Tbox stemming from the UML interpretation of the Figure 1. We performed all the populations with n and m equal and with ⌧ = 0.5 meaning in other words that the half of the assertions were concept assertions. For each pair (n, m), we performed three populations: i- with ⇢ = 0, iiwith ⇢ = 0.5 and iii- with ⇢ = 1.
Figure 2 shows the required CPU times of the populations and the consistency tasks. We used a range of total number of potential individuals and assertions going up to around one million. 00 25000 50000 75000 100000 125000 150000 175000 200000 225000 250000 275000 300000 325000 350000 375000 400000 425000 450000 475000 500000 525000 550000 575000 600000 625000 650000 675000 700000 725000 750000 775000 800000 825000 850000 875000 900000 925000 950000 975000 1000000 1025000 1050000
Assertions
Pellet output systematically that the ABOXes were consistent with the TBOX when the consistency checks were possible. After a certain amount of assertions, the reasoning tasks were impossible to conclude due to a heap space error thrown whenever the JVM reached the heap size limit. For ⇢ = 0.5 at n, m ⇡ 930.000, the first limit was detected. The same limit appeared for ⇢ = 0 at n, m ⇡ 970.000 and for ⇢ = 1 at n, m ⇡ 1.020.000. We can observe on the Figure2, the linear evolution of CPU times for the populator JPoT and the heap space limits (marked with bow ties) concerning the consistency checks of Pellet. 5
In this paper, we just presented another populator of TBOX: JPoT5. To the best of our knowledge, this is the first domain independent SDG guaranteeing consistency of the knowledge base founded on TBOXes expressed in ALCQ(D). The issues of the data assertions were tackled and some performances presented. For future work, we intend that JPoT deals with an higher expressiveness to cover the whole fragment SROIQ(D).
This work has been made possible by “la Regione Autonoma della Sardegna e Autorità Portuale di Cagliari con L.R. 7/2007, Tender 16 2011, CRP-49656 con il projeto: Metodi innovativi per il supporto alle decisioni riguardanti l’ottimizzazione delle attività in un terminal container” and by “o EDITAL FAPES/CAPES N 009/2014 (Bolsa de fixacão de doutores) com a proposta: Melhor integração de tecnologias de representação de conhecimento e raciocínio nas utilizações local e Web”.