CODEWITHSUNDEEP
owlontologyasymptotic-complexityprotegeowl-api
user10264746
user10264746

Reputation: 59

What are the asymptotic running times for OWL EntitySearcher methods (eg. EntitySearcher.getAnnotations(c, o, factory.getRDFSLabel()))

I am writing an application which makes use both of an ontology/owlapi and a sqlite database in which the value of certain fields is an IRI from the ontology.

I'm wondering whether it would be (asymptotically) quicker to retreive the rdfs:Label and rdfs:Comment annotations from the SQL DB (assumeing they are stored there in advance) rather than retrieve those values from the OWLAPI every time.

In general, how time/space intensive are the main operations in EntitySearcher (asymptotically, or otherwise)?

Assume for this example that rdfs:label is the only annotation property belonging to class c, so we don't have to explicitly iterate through a list of annotation properties.

Upvotes: 1

Views: 77

Answers (1)

Ignazio
Ignazio

Reputation: 10684

I haven't done a complete analysis of the relevant code here, but roughly speaking the operations involved are:

  • Given an ontology and an entity
  • get annotation axioms for entity
  • iterate looking for matching annotation property
  • get the literal value

The axioms are indexed by type, so getting the annotation axioms is O(1). Selecting the axioms relevant for an entity also leverages an index, so that's O(1) again. Iterating through and looking for a matching property is O(N) where N is the number of annotations - 1 in your example, so again O(1). The comparison itself resolves in a string comparison for the property IRI. rdfs:label itself is a singleton, as it is used a lot, so the comparison is insignificant in performance. Extracting the literal value is a simple access, so overall the process should be O(1).

Comparing to a database, O order would be the same; but the default OWLAPI implementation is ConcurrentHashMaps in memory. Access to a remote database over the network, assuming there's no need to open a new connection, is still likely to dominate the actual time measurements.

Upvotes: 2

Related Questions