3

I am currently developing an ontology using protege and would like to determine if a node is a last one of a list. So basically a list points to a node and every node has some content and can have another node:

List startsWith some Node

Node hasContent some Content

Node hasNext some Node

Now I'd like to define a subclass named EndNode that doesn't point to another Node. This is what I've tried so far, but the after classifying, EndNode always equals Nothing:

Node and not(hasNext some Node)

Node and (hasNext exactly 0 Node)

Pedro
  • 4,100
  • 10
  • 58
  • 96

1 Answers1

2

First, there is a built-in List construct in RDF which you can use in the following way:

ex:mylist  rdf:type  rdf:List .
ex:myList  rdf:first  ex:firstElement .
ex:myList  rdf:rest  _:sublist1 .
_:sublist1 rdf:first  ex:SecondElement .
_:sublist1  rdf:rest  rdf:nil .

Here, in order to know you reach the end of the list, you need a special list called rdf:nil. This plays the same role as a null pointer at the end of a linked list in programming languages.

However, even though rdf:List is well used in existing data on the Web, it doesn't constrain in any way the use of the predicates rdf:first and rdf:rest, so you can have many first elements for a given list without triggering an inconsistency.

So, if you really want to model linked list in a strict way, you need pretty expressive features of OWL. I did it a while ago and it can be found at http://purl.org/az/List.

It's normal that you have an empty class as you specified that a Node must have a nextNode. You should not impose that Nodes have content or next element. You should rather say that the cardinality is maximum 1, that the domain and range of hasNext is Node, and that EndNode is a node with no next node. But it's still not enough, as it does not impose that there is an EndNode at all. You may have an infinite sequence or a loop.

If you want to avoid loops or infinite sequence, you have to define the transitive property hasFollower and say that there is at least a follower in the class EndNode.

All in all, implementing strict lists in OWL completely sucks in term of performance and is most of the time totally useless as rdf:List is sufficient for the wide majority of the situations.

Antoine Zimmermann
  • 5,314
  • 18
  • 36
  • "rdf:List is sufficient for the wide majority of the situations." Unless you want to use an OWL reasoner, in which case you can't use the RDF vocabulary terms because they're used in the RDF/XML serialization of OWL. :( – Joshua Taylor Oct 28 '14 at 17:45
  • Joshua, not really a problem for reasoners that I know. I just tried making an ontology with rdf:List used as an OWL class and the reasoners (HermiT and FacT++ in this case) did not complain. – Antoine Zimmermann Oct 31 '14 at 14:30
  • Agreed, but it is important to note that, strictly speaking, it's [disallowed in OWL1](http://www.w3.org/TR/owl-semantics/mapping.html#4.2). Offhand, though, I can't find corresponding text for OWL2. Is it allowed in OWL2? – Joshua Taylor Oct 31 '14 at 14:39
  • 1
    It's not allowed in OWL 2 DL. Sec.2.4 of the structural spec defines the reserved vocabulary as any IRI with prefix in the namespaces of `rdf`, `rdfs`, `owl` or `xsd`. Sec.5.1 says that "IRIs from the reserved vocabulary other than `owl:Thing` and `owl:Nothing` MUST NOT be used to identify classes in an OWL 2 DL ontology". Thus, `rdf:List` cannot be used as a class in OWL 2 DL. But OWL reasoners & other OWL processors are able to deal with more liberal OWL ontologies. Only few existing RDF documents online make OWL processors collapse, although most of them are not conforming to the OWL spec. – Antoine Zimmermann Oct 31 '14 at 20:06
  • OK, I thought it was in there somewhere. Thanks for the reference! – Joshua Taylor Oct 31 '14 at 20:07