[data-shapes] reasoning: transitiveOver (transitive with "step" property) (#351)

VladimirAlexiev has just created a new issue for https://github.com/w3c/data-shapes:

== reasoning: transitiveOver (transitive with "step" property) ==
https://github.com/w3c/data-shapes/discussions/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
```ttl
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:
```ttl
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. It is thus penalized by an extra degree of complexity.

Please view or discuss this issue at https://github.com/w3c/data-shapes/issues/351 using your GitHub account


-- 
Sent via github-notify-ml as configured in https://github.com/w3c/github-notify-ml-config

Received on Wednesday, 9 April 2025 16:26:18 UTC