Joshua Taylor 20080918 Presentation Jesse Weaver

From Semantic Portal Wiki

• Question is for the Presentation: Joshua Taylor 20080918 Presentation
• Question is asked by: Jesse Weaver
• The Question is:

What is the time complexity of the proposed algorithm with respect to the number of subsumptions that change their entailment status?

One of the main assumptions proposed in section 3 is that "the number of subsumptions that change their entailment status w.r.t. the ontology ... is probably small compared to the number of subsumptions that do not ...." What about when mapping ontologies? For example, consider the paper "Collecting Community-Based Mappings in an Ontology Repository". In that paper, users are allowed to map certain relationships between ontologies. These mappings do not use OWL properties but rather properties indicating, for example, that two classes _could_ be considered equivalent (among others). Now imagine a user selects an ontology to add to his/her own preexisting ontology, replacing those "could-be-considered-equivalent-class" relations (between the two ontologies) with actual owl:equivalentClass relations for purposes of reasoning over data that uses both ontologies. This seems like a plausible situation in which the aforementioned assumption may not hold. What kind of results would be gotten from experiments reflecting this ontology-mapping example?

A casual question of interest: How could such an incremental approach be applied (if at all) to promote reasoning in large and/or distributed RDF stores?

Answer

Joshua Taylor writes, The for loops in the algorithm iterate over concept names and the axioms that are added and removed. Checking whether an axiom is local to a signature should run in linear time in terms of the length of the axiom. Thus lines 1–19 of Algorithm 2 should depend primarily on the changes to the ontology (which may, of course, have some correlation to the number of altered subsumptions). In lines 20–34, nested for loops iterate over all pairs of concept names in the O2 (give or take some for ⊤and ⊥). Line 29 is only executed when a concept's module has changed in a particular way and it had a particular subsumption relation in O1. But this still gives no information about whether the subsumption between the two concepts under consideration changes. The most direct answer, however, is probably to cite the authors' claim that "for large ontologies, over 99% of subsumption relations do not hold." Since the the runtime of Algorithm 2 is primarily determined by the size of the size of the ontologies, and the number of axioms added and removed, and if the "over 99%" rule holds before and after incremental changes, it seems likely that the runtime does have a strong correlation with the number of subsumption relationships that change. Also consider column "6. # New (Nn)Sub. (Av/Max)", and the last three rows of Table 6. It appears that the number of changed subsumptions does not correlate with column "5. Total Time (Av/Max)".

If the process of ontology mapping is viewed starting with two completely disconnected ontologies, and then taking their union along with some mapping axioms, it's something of a stretch to call ontology mapping an "incremental modification." However, if the union if viewed as the initial ontology, the subsumption relation probably reflects that there are two, as of yet, unrelated ontologies. In this case there are even fewer subsumptions than would be expected in a typical ontology, and so incremental modifications, while possibly changing more subsumptions than would typically be expected, still probably only have the effect of making the new super-ontology more like a typical ontology. Nonetheless, the parallel structure of an ontology that is the union of two unrelated ontologies, once mapped, would probably lead to more pairs in the subsumption relation than what is expected in a typical ontology.

Tayloj 19:46, 18 September 2008 (UTC)