RIF-RDF-Lists

It is deemed desirable that the RIF Lists facility can be used for processing RDF lists. Towards that aim, this page discusses two possible extensions of the semantics of RIF-RDF combinations (original definition in SWC).

RDF Lists

Syntactically speaking, an RDF list is a set of triples of the form

``` l1 rdf:first d1 .
l1 rdf:rest l2 .
...
ln rdf:first dn .
ln rdf:rest rdf:nil .
```

Here, l1 - ln provide the structure of the linked list and d1 - dn are the data items. The above list would be written in RIF syntax as List(d1 ... dn).

Note that when using the RDF semantics the last triple (rdf:nil rdf:type rdf:List) is already implicit in the semantics, and when using RDFS semantics all mentioned rdf:type triples are interested in semantics.

Semantically speaking, an element l1 refers to an RDF list y1,...,yn: if n=0, l1=IS(rdf:nil); otherwise, ∃ l2, ..., ln such that <l1,y1> ∈ IEXT(IS(rdf:first)), <l1,l2> ∈ IEXT(IS(rdf:rest)), ..., <ln,yn> ∈ IEXT(IS(rdf:first)), and <ln,IS(rdf:nil)> ∈ IEXT(IS(rdf:rest)).

Note that, if n > 0, there may be several lists identified by l1, since there is no restriction on the rdf:first elements and the rdf:rest successors.

RIF lists as extensions

This option considers RIF list as extensions of RDF lists. Every RDF list is an RIF list, but the converse is not necessarily the case.

This option extends the definition of SWC#Common_RIF-RDF_Interpretations with the following condition:

9. For any nonnegative integer n and any sequence of elements y1,...,yn, if an element l1 refers to the list y1,...,yn, then Ilist(y1,...,yn)=l1.

Note that a consequence of the RIF semantics for lists, which gives lists a fixed structure, is that in combinations, identifiers are unique, i.e., one element cannot identify more than one list.

In the following we assume that the definitions of satisfaction and entailment are suitably extended to incorporate this condition.

One-To-One Mapping between Lists in RIF-RDF Combinations

This extension considers a one-to-one mapping between RDF lists and RIF lists.

This option extends the definition of SWC#Common_RIF-RDF_Interpretations with the following condition:

9. For any nonnegative integer n and any sequence of elements y1,...,yn, an element l1 refers to the list y1,...,yn iff Ilist(y1,...,yn)=l1.

The same restrictions about identifiers of lists as in the previous semantics apply here.

In the following we assume that the definitions of satisfaction and entailment are suitably extended to incorporate this condition.

Test cases

In the following we illustrate the two proposed semantics with a number of simple test cases.

The test cases are all entailment tests. Note that the positive entailment tests for the "RIF lists as extensions" option are also positive entailment tests for the "One-To-One Mapping" option, while the listed positive entailment tests for the "One-To-One Mapping" option are all negative entailment tests for the "RIF lists as extensions" option.

The test cases consist of a set of RDF triples, a set of RIF rules, and an entailed in RIF condition formula. It is assumed that the RIF rules are contained in RIF document that imports the RDF graph with the Simple profile.

RIF lists as extensions

Positive Entailment Tests

Multiple lists with one identifier

An example of multiple lists with the same identifier. In this case, _:l1 identifies the lists (ex:a) and (ex:b).

RDF graph:

``` _:l1 rdf:first ex:a .
_:l1 rdf:first ex:b .
_:l1 rdf:rest rdf:nil .
```

RIF rules:

Entailed formula:

``` ex:a=ex:b
```
RIF lists from RDF list

RDF graph:

``` ex:a ex:p _:l1 .
_:l1 rdf:first ex:b .
_:l1 rdf:rest rdf:nil .
```

RIF rules:

Entailed formula:

``` ex:a[ex:p -> List(ex:b)].
```

One-to-One Mapping

Positive Entailment Tests

RDF lists from RIF lists

This example illustrates that the structure of an RDF list can be obtained from that of an RIF list.

RDF graph:

RIF rules:

``` ex:p(List(ex:a))
```

Entailed formula:

``` Exists ?x (And(ex:p(?x) ?x[rdf:first -> ex:a] ?x[rdf:rest -> rdf:nil])).
```

Negative Entailment Tests

Non-wellformed RDF lists (I)

The following list is not well formed (_:l1 does not have an rdf:rest), and thus does not correspond to an RIF list.

RDF graph:

``` ex:a ex:p _:l1 .
_:l1 rdf:type rdf:List .
_:l1 rdf:first ex:b .
```

RIF rules:

Non-entailed formula:

``` ex:a[ex:p -> List(ex:b)].
```