reasoning: transitiveOver (transitive with "step" property)

[VladimirAlexiev]

#295 "Note about transitivity"
hints why TRANSITIVE(rdfs:subClassOf) is "better" than a recursive rule
IF (?x rdfs:subClassOf ?y) (?y rdfs:subClassOf ?z) THEN (?x rdfs:subClassOf ?z):
a profile "non-recursive + transitive properties" may be easier to implement than a general "recursive rules" profile.
This corresponds to the T-Box declaration

rdfs:subClassOf a owl:TransitiveProperty

I want to give another example: transitive with a "step" (explicitly asserted) property, eg:

• skos:broader is the step, skos:broaderTransitive is the transitive closure
• sesame:directType is the step, rdfs:subClassOf results in the transitive closure rdf:type
• schema:location is the step, schema:containedInPlace results in a transitive closure.
  Eg "Graphwise :location Sofia. Sofia :containedInPlace Bulgaria => Graphwise :location Bulgaria"

GraphDB has long had rules using ptop:transitiveOver ("Proton top" or "Proton sys" is a dead ontology, but this predicate has survived).

• see documentation https://graphdb.ontotext.com/documentation/11.0/rules-optimisations.html#consider-specialized-property-constructs
• which refers to a bigger writeup with images https://rawgit2.com/VladimirAlexiev/my/master/pubs/extending-owl2/index.html

It is defined with this rule:

?p transitiveOver ?q. ?x p ?y. ?y q ?z => ?x ?p ?z

It subsumes (is a generalization of) owl:TransitiveProperty:

?p a TransitiveProperty <=> ?p transitiveOver ?p

It is subsumed by (is specialization of) owl:propertyChainAxiom:

?p transitiveOver ?q <=> ?p propertyChainAxiom (?p ?q)

Using this instead of TransitiveProperty we can implement the above examples like this:

skos:broader rdfs:subPropertyOf skos:broaderTransitive. skos:broaderTransitive transitiveOver skos:broader.
sesame:directType rdfs:subPropertyOf rdf:type. rdf:type transitiveOver rdfs:subClassOf. rdfs:subClassOf transitiveOver rdfs:subClassOf.
schema:location transitiveOver schema:containedInPlace. schema:containedInPlace transitiveOver schema:containedInPlace.

It is interesting because it can be implemented more efficiently than owl:TransitiveProperty.
Consider a chain of N "step" triples between two nodes.

• TransitiveProperty must consider every split of the chain in two parts, thus inferring the same closure N-1 times (O(N^2) complexity). Since it needs to infer a total of O(N^2) triples, the total complexity becomes O(N^4)
• transitiveOver only needs to grow the chain on the right. the total complexity becomes O(N^3)

A rule that looks at TransitiveProperty only, loses the info which is the Step property,
and loses the distinction which triples are asserted and which are inferred.

It is thus penalized by an extra degree of complexity.
(I made a synthetic dataset for a training that proved that.)