NSByGrounding

From Knoesis wiki
Revision as of 18:17, 4 March 2012 by DavidCarral (Talk | contribs) (Conclusions)

Jump to: navigation, search

Nominal Schema Reasoning by Grounding

This page contains the implementations of nominal schema reasoning using naive and smart grounding.

Introduction

In this page we include the empirical evaluation and implementation of nominal schemas, a new description logics construct (See the Literature section). Several ontologies selected from the TONES repository [1] were used for this evaluation. For each experiment presented one or more axioms containing nominal schemas were added to each ontology, resulting in the inclusion of several regular axioms containing nominals. As stated in the paper, occurences of nominal schemas are grounded with all possible combinations of individuals contained in the knowledge bases. After the grounding reasoning times (using Pellet after grounding) are averaged over 100 runs, and load time is reported separately. We are particularly interested in finding what are the limits of this implementation varying both the number of different nominal schemas and their number of occurrences per axiom.

Testing was performed using a 64-bit Windows 7 computer with an Intel(R) Core(TM) i5 CPU processor. A java JDK 1.5 version, allocating 3GB as the minimun for the java heap and 3.5GB as the maximun, was used for each experiment.

We include an appendix with examples of nominal schemas and their intuitive semantics, which we recommend if the reader is unfamiliar with this new DL construct, and a tutorial to ground axioms with nominal schemas into a given ontology.

Naive Implementation

Although not very time-efficient this implementation will serve as a baseline for development and testing of more optimised algorithms. It also shows that even the grounding approach can be used for small use cases or for initial testing.

The section includes testing data obtained from different experiments showing the feasibility of this implementation when the number of different nominal schemas per axiom is low.

Java code to ground axioms containing nominal schemas to a given ontology is also included. After the grounding reasoning tasks can be performed with the ontology using any reasoner available just as usual.

Ontologies

We present in this section the metrics of the ontologies used for the naive implementation. Some ontologies were modified, as shown in the table, to better suit test purposes.

Ontology Classes Annotation P. Data P. Object P. Individuals URI Modifications
Fam 4 0 1 11 5 [2] No mod
Swe 189 1 6 25 22 [3] 20 individuals added
Bui 686 15 0 24 42 [4] 40 individuals added
Wor 1842 6 0 31 80 [5] 80 individuals added
Tra 445 2 4 89 183 [6] No mod
FTr 22 2 6 52 368 [7] No mod
Eco 339 2 8 45 482 [8] No mod

Note that the ontologies are sorted by the number of individuals they contain. As show in [1] the number of regular axioms grounded from an original axiom containing nominal schemas is k^{n} where n is the number of different nominal schemas in the original axiom and k is the number of individuals in the knowledge base. Consequently, the number of individuals is one of the relevant factors that must be taken into account in the testing results.

Testing results

This section contains two tables showing the reasoning time results for the ontologies when axioms with different combinations of nominal schemas are added. Every experiment time results are presented in two columns showing loading time for the first and checking satisfiability for the second.

Adding one axiom to each Ontology

For every experiment in this section only one axiom was added to each ontology varying the number of different nominal schemas and their number of appearances.

Ontology No axioms added 1 different nominal schema 2 different nominal schemas 3 different nominal schemas
2 appearances 8 appearances 2 appearances 4 appearances 2 appearances
Fam (5) 0.01 0.00 0.01 0.00 0.01 0.01 0.01 0.00 0.01 0.00 0.04 0.02
Swe (22) 3.58 0.08 3.73 0.07 3.73 0.11 3.85 0.10 3.88 0.11 10.86 1.11
Bui (42) 2.7 0.16 2.5 0.15 2.47 0.15 2.75 0.26 3.05 0.36 1'14 6.68
Wor (82) 0.11 0.04 0.12 0.05 1.48 0.87 1.1 0.55 1.88 1.03 197'12 5'15
Tra (183) 0.05 0.03 0.05 0.02 0.05 0.02 5.76 1.76 9.9 3.73 OOM OOM
FTr (368) 0.03 4.28 0.05 5.32 0.09 5.51 35.53 42.73 1'18 9'30 OOM OOM
Eco (368) 0.04 0.24 0.07 0.02 0.10 0.04 56.59 13.67 53.32 35.35 OOM OOM

Adding several axioms to each Ontology

Two experiments were considered in this section:

Experiment 1: 20 axioms containing one different nominal schema per axiom with two appearances were added to each ontology.

Experiment 2: 10 axioms containing two different nominal schemas per axiom with two appearances each were added to each ontology.


Name No axioms added Experiment 1 Experiment 2
Fam (5) 0.01 0.00 0.01 0.00 0.02 0.01
Swe (22) 3.58 0.08 3.42 0.08 3.73 0.28
Bui (42) 2.7 0.16 2.69 0.25 5.7 3.21
Wor (80) 0.11 0.04 0.23 0.28 12.42 6.88
Tra (183) 0.05 0.03 0.32 0.15 1' 43.54' 43.63
FTr (368) 0.03 4.28 0.52 11.33 OOM OOM
FTr (368) 0.04 0.24 0.65 0.3 OOM OOM

Naive Safe Grounding

In this section we present results for the empirical evaluation for nominal schema when the optimization proposed in [1,2] is applied comparing the results with the standard naive implementation. Three ontologies, also obtained from the TONES repository, are considered in this section.

To apply this Smart Grounding ontologies need to be part of the SROELVn description logics (essentially the OWL EL profile) and the nominal schema appearances need to be "safe". Intuitively, if the nominal schemas are "safe" they are independent from each other. The exact definition of safeness is described in [1]. Since the nominal schemas are independent from each other instead grounding the original axiom containing several appearances of nominal schemas we can ground several axioms with less number of different nominal schemas each. Remember that the final number of axioms is k^n where k is the number of individuals and n the number of different nominal schemas appearing per axiom. Therefore lowering this n will yield a much smaller amount of grounded axioms and a better performance of the approach.

Note that this implementation was done with testing purposes in mind rather than usability and the program will not be able to detect if an axiom contains "safe" nominal schemas. The division of an axiom containing "safe" nominal schemas has to be done manually, as shown in [1] by the user, and then ground all resulting axioms separately.

Ontologies

We present metrics for the three EL ontologies used for the testing in this section. Due to the lack of EL ontologies with their own individuals all individuals for this section were artificially builded for the given ontologies.

Ontology Classes Annotation P. Data P. Object P. Individuals URI Modifications
Rex 552 10 0 6 100 [9] 100 individuals added
Spatial 106 13 0 13 100 [10] 100 individuals added
Xenopus 710 19 0 5 100 [11] 100 individuals added

Testing Results

The next table present the testing results for the ontologies considered in this section. Again results for each experiment are refered in pairs of columns showing loading and checking satisfiability times.

Ontology No ns 1 different ns P. 2 different ns 3 different ns
Rex 0.025 0.009 0.031 0.013 1.689 0.112 OOM OOM
Rex Optimized 0.058 0.023 0.046 0.011 0.053 0.009
Rex 0.035 0.029 0.021 0.014 1.536 0.101 OOM OOM
Rex Optimized 0.018 0.013 0.033 0.007 0.044 0.011
Rex 0.063 0.018 0.07 0.19 1.598 0.112 OOM OOM
Rex Optimized 0.099 0.037 0.083 0.018 0.097 0.063

For each couple of rows, the first (Rex) shows the reasoning time for the original axiom containing "safe" nominal schemas. The second (Rex Optimized) show the time results when this original axiom is split in several simpler ones. As it can be seen in the table the performance of these two methods is completely different.

Conclusions

With this empirical results we obtain a baseline to test smarter approaches that are currently under development for reasoning over nominal schemas. Not only that, we have that for ontologies containing a small number of individuals, or axioms with a small number of different nominal schemas per axiom the approach is still feasible. Note that adding several axioms containing a low number of nominal schemas is not very time consuming, while the addition of one single axiom with a high number of different nominal schemas can significantly rise the time complexity (Remember that k^n is the number of grounded axioms). Consequently, we have that for axioms containing only "safe" nominal schemas the Naive Safe approach performs quite well (when the nominal schemas are "safe" we can substitute an axiom containing a large number of nominal schemas into several containing a smaller amount). This last assertion is clearly supported by the empirical results in the Naive Safe Grounding section

Note that, as stated in [5] we can express any First Order Logic Rule (FOL) containing n variables with a Description Logics (OWL) axiom containing at most m different nominal schemas such that m \leq n - 2 (in most cases m can be reduced even more, as shown in [5]). With the empirical results in place this result give us a good intuition of which FOL rules can be directly expressed in OWL using nominal schemas using the presented approach.

Literature

  1. Markus Krötzsch, Frederick Maier, Adila Alfa Krisnadhi, Pascal Hitzler, A Better Uncle For OWL - Nominal Schemas for Integrating Rules and Ontologies. In: S. Sadagopan, Krithi Ramamritham, Arun Kumar, M.P. Ravindra, Elisa Bertino, Ravi Kumar (eds.), WWW '11 20th International World Wide Web Conference, Hyderabad, India, March/April 2011. ACM, New York, 2011, pp. 645-654.
  2. Adila Alfa Krisnadhi, Frederick Maier, Pascal Hitzler, OWL and Rules. In: Reasoning Web 2011, Springer Lecture Notes in Computer Science. To appear.
  3. David Carral Martinez, Adila Krisnadhi, Frederick Maier, Kunal Sengupta, Pascal Hitzler, Reconciling OWL and Rules. Technical Report, Kno.e.sis Center, Wright State University, Dayton, OH, USA, June 2011.
  4. David Carral Martinez, Adila A. Krisnadhi, Pascal Hitzler, Syntax Proposal for Nominal Schemas. Technical Report, Kno.e.sis Center, Wright State University, Dayton, OH, USA, June 2011.
  5. David Carral Martinez, Pascal Hitzler, Extending Description Logic Rules. In: Proceedings of the 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 2012. Lecture Notes in Computer Science, Springer, Heidelberg (2012), to appear.

Acknowledgements

This work was supported by the National Science Foundation under award 1017225 III: Small: TROn---Tractable Reasoning with Ontologies, and by State of Ohio Research Incentive funding in the Kno.e.CoM project. Adila Krisnadhi acknowledges support by a Fulbright Indonesia Presidential Scholarship PhD Grant 2010.

Appendix

Nominal Schemas Examples

In this section we introduce some examples that will help the unexperienced reader to get more familiar with nominal schemas without having to understand the deeper technical details. Some of the information is repeated just to make the section more readable and self-contained. We start by a simple example of a nominal schema axiom in the DL and its semantics to continue with the simplification of an axiom containing "safe" nominal schemas.

Consider the following example. It states that somebody has a conflicting review assignment (paper x) if this person has a paper submitted at the same event z which is co-authored by one of the authors y of paper x. Each of \{x\}, \{y\}, and \{z\} is a nominal schema, occurring multiple times in the axiom.

\exists hasReviewAssignment.((\{x\}\sqcap\exists hasAuthor.\{y\})\sqcap(\{x\}\sqcap\exists atVenue.\{z\})) \sqcap \exists hasSubmittedPaper.(\exists hasAuthor.\{y\}\sqcap\exists atVenue.\{z\}) \sqsubseteq \exists hasConflictingAssignedPaper.\{x\}

Semantically, nominal schemas can be bound only to nominals, i.e., a class indicated by a nominal schema can contain only known (named) individuals from the knowledge base. As such, they are reminiscent of DL-safe rules or more precisely of DL-safe variables. The formal semantics has been spelled out explicitly in [1], however the same semantics can be obtained by a transformational approach which eliminates all nominal schemas by full grounding: We replace an axiom with nominal schemas by all axioms (without nominal schemas) which can be obtained by substituting all nominal schemas by nominals. The above example thus gives rise to all axioms of the form

\exists hasReviewAssignment.((\{a_i\}\sqcap\exists hasAuthor.\{a_j\})\sqcap(\{a_i\}\sqcap\exists atVenue.\{a_k\})) \sqcap \exists hasSubmittedPaper.(\exists hasAuthor.\{a_j\}\sqcap\exists atVenue.\{a_k\}) \sqsubseteq \exists hasConflictingAssignedPaper .\{a_i\}

where a_i, a_j and a_k are individual names. The resulting knowledge base carries the classical DL semantics.


To give a better understanding about safeness we provide one axiom simplification example and its definition from [1].

An occurrence of a nominal schema \{x\} in a concept C is safe if C has a sub-concept of the form \{a\}\sqcap\exists R.D for some individual a, such that D contains the occurrence of \{x\} but no other occurrence of any nominal schema. In this case, \{a\}\sqcap\exists R.D is a safe environment for this occurrence of \{x\}. S(a,x) will sometimes be used to denote an expression of the form \{a\}\sqcap\exists R.D within which \{x\} occurs safely.

Now, we show how the simplification is applied for axiom \alpha, which is contained in an knowledge base KB with 3 individuals \{p\}, \{a\}, and \{b\}:

 \exists hasReviewAssignment.((\{p\}\sqcap\exists hasAuthor.\{y\}) \sqcap(\{p\}\sqcap\exists atVenue.\{z\})) \sqcap \exists hasSubmittedPaper.(\exists hasAuthor.\{y\}\sqcap\exists atVenue.\{z\}) \sqsubseteq \exists hasConflictingAssignedPaper.\{p\}

For each nominal schema \{x\} safe for \alpha with safe environments S_{i}(a_{i},x), i=1,\dots,\ell, introduce a fresh concept name O_{x,\alpha}.

Note that in the first line of the axiom both \{y\} and \{z\} are safe with respect to \{p\}. Do not mistake nominals (\{p\}, \{a\}, and \{b\}) with nominal schemas (\{x\}, \{y\}, and \{z\}).

For each individual b in KB, add polynomially many new ground axioms to KB: \sqcap_{i=1}^{\ell}\exists U.S_{i}(a_{i},b)\sqsubseteq \exists U.(\{b\}\sqcap O_{x,\alpha}

\exists U.(\{p\}\sqcap\exists hasAuthor.\{p\}) \sqsubseteq \exists U.(\{p\}\sqcap O_{y,\alpha})

\exists U.(\{p\}\sqcap\exists hasAuthor.\{a\}) \sqsubseteq \exists U.(\{a\}\sqcap O_{y,\alpha})

\exists U.(\{p\}\sqcap\exists hasAuthor.\{b\}) \sqsubseteq \exists U.(\{b\}\sqcap O_{y,\alpha})

\exists U.(\{p\}\sqcap\exists atVenue.\{p\}) \sqsubseteq \exists U.(\{p\}\sqcap O_{z,\alpha})

\exists U.(\{p\}\sqcap\exists atVenue.\{a\}) \sqsubseteq \exists U.(\{a\}\sqcap O_{z,\alpha})

\exists U.(\{p\}\sqcap\exists atVenue.\{b\}) \sqsubseteq \exists U.(\{b\}\sqcap O_{z,\alpha})

Let C be the left hand side of \alpha. For each nominal schema \{x\} safe for \alpha:

Replace all safe occurrences S(a,x) in C by \{a\}

Replace the non-safe occurrence (if any) of \{x\} in C by O_{x,\alpha}

Add a new conjunct \exists U.O_{x,\alpha} to C

After applying the transformation, add the resulting axiom to KB:

\exists hasReviewAssignment.\{p\} \sqcap
\exists hasSubmittedPaper.(\exists hasAuthor.O_{y,\alpha} \sqcap \exists atVenue.O_{z,\alpha})
\sqcap

 \exists U.O_{y,\alpha} \sqcap \exists U.O_{z,\alpha} \sqsubseteq \exists hasConflictingAssignedPaper.\{p\}

After the simplification KB now contains more axioms containing nominal schemas, but less number of different nominal schemas drastically reducing the number of grounded axioms.

Grounding Tutorial

This section presents java code to ground axioms with nominal schema for a given ontology (the code makes use of the OWL API that must be added to the classpath of the project). Remember that the implementation main purpose is to test the Naive approach rather than usability, robustness, maintainability or other desirable Software quality properties.

Create the frame

First the user needs to write down the frame containing the axiom we want to ground to the knowledge base and store in a .owl file. It can be created with any text editor available. This file should be placed in the same folder as our ontology.

Example of frame containing one axiom with one nominal schema and two appearances:

[

rdf:type owl:Class;
rdfs:subClassOf :frameClass1;
owl:intersectionOf(
[ rdf:type owl:Restriction;
owl:onProperty :property1;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v1” ]
]
[ rdf:type owl:Restriction;
owl:onProperty :property2;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v1” ]
]
)

].

The blank node [ rdf:type owl:ObjectVariable; owl:variableId "v1"] represents the nominal schema. It will be replaced and grounded with all individuals in the ontology.

Remark: for the program to work correctly nominal schemas must be typed in the same line with no other axioms, as shown above, when the user builds the frame.

Example of frame containing one axiom with two nominal schemas and two appearances each:

[

rdf:type owl:Class;
rdfs:subClassOf :frameClass1;
owl:intersectionOf(
[ rdf:type owl:Restriction;
owl:onProperty :property1;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v1” ]
]
[ rdf:type owl:Restriction;
owl:onProperty :property2;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v1” ]
]
[ rdf:type owl:Restriction;
owl:onProperty :property3;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v2” ]
]
[ rdf:type owl:Restriction;
owl:onProperty :property4;
owl:someValuesFrom
[ rdf:type owl:ObjectVariable; owl:variableId ”v2” ]
)

].

For this second example the program will ground all possible pair combinations for the nominal schemas "v1" and "v2". In this specific case, the number of grounded axioms is equal to k^{2} where k is the number of individuals in the knowledge base and we have two different nominal schemas in the axiom.

Remark: note that all classes, properties, and namespaces in the frame need to be previously defined in the ontology for a correct performance of the reasoner after the grounding. We assume that all predicates that are part of the rule we wanted to ground previously appeared in the ontology.

Grounding the axioms

The program will start and prompt the user for the folder's path where we have stored the frame and the ontology and then for the names of these. After execution a new file with appear with the same name as the ontology followed with the word "Grounded.owl". The new file contains the same previous ontology with all possible grounded combinations of individuals for the defined frame added at the end. To ground several nominal schemas for a given ontology we just have to run the program several times with the desired frames.

The program is currently only available for Turtle Syntax. A converter of OWL syntax is available in: [12]. Also, the ontology editor Protégé allows to load an ontology in any syntax and save it in another one, i.e. Turtle in this case.

Code can be downloaded from: [13]