On lists, Lists and (...) - [was] defining the semantics of lists

Hi,

in May I asked about list semantics as I was trying to understand why =
rdf:Containers are considered ripe for deprecation and everybody seems =
to use rdf:Lists instead, or more specifically, what exactly it is that =
makes people say that "rdf:Lists have more semantics". I also wanted to =
find a way to put rdf:Containers on equal footing with rdf:Lists for =
reasons summarized below.=20
I learned a lot from the ensuing answers and discussions and would like =
to share how I now see the range of problems and possible solutions =
w.r.t. lists in RDF. This is predominantly about rdf:Containers and =
Collections aka rdf:Lists but like with many problems in RDF there are =
aspects that involve Named Graphs, native DataTypes as nodes, very basic =
questions of identification and the general design of a Knowledge =
Representation language that is both simplistic+approachable and =
powerful+versatile.

Pat in his first reply to my initial mail warned against pushing the =
limits of RDF too far as it is not a programming language. OTOH some =
argue that RDF needs a proper datatype for lists as it is such an =
ubiquitous and extensible (list > tree > table) datastructure. Then =
there=E2=80=99s the everlasting attractiveness of Lisp-style code as =
data and data as code. Most developers try to keep complexity down by =
minimizing the number of paradigms and languages they use to get some =
work done. That of course often leads to overly complex languages. =
Still: a data oriented language as RDF that offers only half-hearted =
support for the most basic data structure around doesn=E2=80=99t fit =
that bill very well. Lists will probably become even more important with =
more uptake in Linked Data based applications. So maybe better pave the =
cow paths.
The result of this discussion is important for the question if lists =
should become a proper, native datatype in RDF or if alternatively =
establishing semantic extensions for more rigid triple-based lists =
through Named Graphs is the way to go. Both aspects will be discussed =
below. The answer to this debate however only tangentially touches on my =
initial question about rdf:Containers and Collections.


The semantics

The specs are pretty clear about the lack of any formal standing of the =
semantics of rdf:Containers and rdf:lists alike. Their semantics is =
basically just handwaving. What differentiates them most is that =
rdf:Lists provides an - again: informal - notion of closed-ness as the =
last member is clearly marked by the rdf:nil attribute.=20
Restricting the semantics of any kind of lists in RDF to informal =
handwaving is necessary to uphold the Open World Assumption of RDF. Each =
statement has a self-contained meaning and other statements are only =
allowed to monotonically add to that, never to retract existing =
statements. Contradicting assertions are unavoidable and occur all the =
time on the Semantic Web. Constructs from the RDF vocabulary however =
can=E2=80=99t be allowed to reign into each other. Lists, which are =
necessarily composed from multiple statements, can not be constrained =
through other statements. Consequently RDF can=E2=80=99t give any =
guarantees about their well-formedness. All it can do is describe them.=20=

To be precise the semantics of rdf:Lists is indeed a little stronger =
than just handwaving. The list-ness of rdf:Lists is reflected in its =
first-rest-ladders - as cumbersome as they may be - and the definite =
rdf:nil element that closes them means that adding an element to a list =
requires removing the previous closing statement. This is more than =
rdf:Containers can ever provide, even with a vocabulary extension as =
proposed below.
Semantic extensions to RDF like OWL DL may impose further restrictions =
and OWL DL does indeed specify constraints for the rdf:List vocabulary =
that rule out malformed lists like e.g. those having multiple heads, =
tails or branches. However for other reasons it reserves the use of =
rdf:List to encode T-Box axioms only.
Lists not implemented by triples but inside a node as a proper datatype =
are another option, discussed further below.
Okay, I hope I got the semantics right this time. A remark: the RDF 1.0 =
Primer [0] and Semantics [1] from 2004 provide very gentle introductions =
to the semantics of RDF. I should have read them before bothering this =
list.=20


Containers versus Collections

The rdf:Container and rdf:List vocabularies have different strengths and =
weaknesses. The rdf:list syntax is based on Lisp-style =
first-rest-ladders and is very verbose. It's hard to write and read, =
even harder to query, has a high triple count, performs worse than =
rdf:Containers [2] and can=E2=80=99t be used in OWL DL outside of OWL =
axiomatic statements. Its big advantage is that the widely preferred =
syntax for RDF, Turtle, provides very nice syntactic sugar for =
rdf:Lists. The rdf:Container vocabulary on the other hand has a syntax =
that is quite easy to write and read, it has some preconfigured types =
that reasonably well capture common use cases for lists, it is easier to =
query in SPARQL and performs better in common triple stores. The syntax =
however, as okay as it might be, looses hands down against the syntactic =
sugar of rdf:Lists in Turtle. And unlike rdf:Lists, which are always =
finite, rdf:Containers can=E2=80=99t be limited to a certain length.
While the claim is often that rdf:Lists should be preferred over =
rdf:Containers because they "have more semantics" I strongly suspect =
that the most important reason for their popularity is the syntactic =
sugar that Turtle and now also JSON-LD provide. Some went back to using =
rdf:Containers because the rdf:List support in SPARQL is so cumbersome =
and incomplete. It has to be said though that while querying rdf:Lists =
in SPARQL is not pleasant, support for rdf:Containers is not that much =
better and could definitely use some love as well (*).
The argument of "more semantics" however is really self-contradictory: =
the semantics of rdf:List, informal as they are, always limit and close =
a list, which is the exact opposite of what RDF is designed for. I=E2=80=99=
m not arguing against the use case per se, obviously, but making =
closed-ness the default, even the exclusive semantics for lists is going =
fully against the essential idea of RDF.=20
So if one wants to close a list for some good reason (**) one can=E2=80=99=
t use rdf:Containers. Going with the swarm means closing each and every =
list, no matter if that makes sense or not. If one wants to use OWL DL =
reasoning rdf:Lists are off limits. If easy writing is required, =
rdf:Lists rule supreme. When querying comes into the picture (ergo: =
actually putting to use what we wrote) rdf:Containers win again, =
although not by a very wide margin. But in the end, all things =
considered, nobody wins. No solution got it all, and for no good reason. =
Put harshly: it=E2=80=99s a mess.


Now what?=20

SPARQL 1.2 is expected to provide better support for rdf:List through =
easier query syntax and better support for returning ordered lists. This =
could solve the most glaring gap in tool support for rdf:Lists. However =
the intimidating base syntax of first-rest-ladders will inevitably still =
surface every now and then.=20
Performance of rdf:Lists might get better when implementations learn to =
represent rdf:Lists internally in a more reasonable way.=20
Another question is if the Semantic Web is really well advised to =
standardise on a list style that through its closed-ness runs against =
the fundamental design of its semantics. RDF semantics are not the most =
popular topic but maybe people would have an easier time following them =
if certain kinks and hard edges were smoothed away.
In OWL DL, the flagship of reasoning powers on the Semantic Web, =
rdf:Lists are reserved for axiomatic statements in the T-Box. =
Closed-ness of lists in A-Box data can only be expressed through even =
more cumbersome design patterns which very seldom get used in the more =
pedestrian areas of the Semantic Web. That presents an at least =
unpleasant gap in interoperability. But OWL DL largely has its own user =
community which can handle complex design patterns alright.=20
So the jury is still out if anything has to be done at all. The =
situation surely could be improved, but is it worth the effort?


A little upgrade to the Container vocabulary

I entered the discussion with an idea to extend the rdf:Container =
vocabulary by a length attribute that would allow to close =
Container-based lists just like rdf:Lists. That way I thought we could =
keep all the good parts of rdf:Containers plus add the more on semantics =
that rdf:Lists have and we could put such lists into OWL DL reasoners =
without much ado. The only real issue would be how to provide syntactic =
sugar for them in Turtle as all the braces are already taken. After I =
better understood that the semantic issues go a bit deeper and after =
some clarifications and discussions I still think the approach has some =
merits, is actually rather modest and not too hard to implement. So here =
it is, again but improved:

    rdf:limit
        rdfs:domain  rdf:Limited ;
        rdfs:range  rdfs:ContainerMembershipProperty .
    rdf:Limited =20
        rdfs:subclassOf  rdf:Container .

The naming of the class rdf:Limited tries to evoke abstract classes in =
Java as the rdf:limit property shouldn=E2=80=99t be used on its own but =
only in conjunction with one of the proper rdf:Container subclasses =
rdf:Seq, rdf:Bag and rdf:Alt.

The RDF semantics of limited Containers are simple and they are just as =
informal as the rdf:Container vocabulary they are based on. Describing =
(!) an rdf:Seq, rdf:Bag or rdf:Alt Container as limited expresses the =
intent that the list is complete and no other members need to nor should =
be added. As one would naturally expect from any rdf:Container the =
rdfs:ContainerMembershipProperties should start with 1 and be =
incremented by 1. In other words there should be no gaps in the =
enumeration of the members as otherwise the rdf:limit property =
wouldn=E2=80=99t really describe the size of a list. Surplus members =
shouldn=E2=80=99t be considered actual  members of the list.
Constraint languages like Shacl and Shex can note the intent stated by =
rdf:limit and take it from there by providing ways to enforce the limit =
together with the well-formedness conditions it relies on in the Closed =
World semantics of applications.
Likewise semantic extensions to RDF like OWL DL might introduce =
syntactic well-formedness restrictions: limited rdf:Containers would =
have to be segregated from rdf:Lists, they would have to be well-behaved =
(starting from _1, increment by 1, no doubles, limit is the last member) =
and grounded. Consequently they would entail missing members with blank =
nodes (as the limit suggests that they exist), treat multiple values of =
the same membership property as owl:sameAs each other and consider =
statements introducing surplus members outside the limit inconsistent =
(***). Preliminary discussions suggest that the slightly unconventional =
approach of using rdfs:ContainerMembershipProperties not as properties =
but values of the rdf:limit property will indeed work in OWL DL.

Support for rdf:Containers with syntactic sugar equal to that of =
rdf:Lists in Turtle would probably be the biggest issue in an effort to =
bring rdf:Containers on par with rdf:Lists. JSON-LD technically could be =
extended rather easily [7] but in Turtle all braces are already taken. =
So either Turtle users would have to live with =
ContainerMembershipProperties or some more extravagant approaches would =
have to be considered like e.g. attributing bracketed lists like so: =
(=E2=80=A6)@Seq - similar to how JSON-LD does it - but that is really =
just an illustration, not an actual proposal.=20


Named Graphs

Named Graphs have been mentioned as a means to define contexts in which =
other semantics than the default OWA could be enforced. Named Graphs as =
implemented in SPARQL and standardized in RDF 1.1 [8] however lack the =
solid denotational semantics that the original Named Graphs proposal by =
Carroll et al. 2005 [9] defined. Ultimately this needs to be fixed but =
in practice a simple workaround would suffice, e.g. a vocabulary =
extension that allows to augment graph identifiers with denotational =
semantics. I=E2=80=99m not aware of anybody doing that today, which =
seems strange (and I=E2=80=99d be glad for references to the contrary!).
Also I=E2=80=99m sceptical if Named Graphs are the right tool to define =
semantics for such a fundamental datastructure as lists. They might be =
if modelling lists is indeed only a secondary concern - the question is =
if that is really a viable positiion. Extending Named Graphs in SPARQL =
and RDF to the semantics as proposed in the original paper will be the =
topic of another mail.


Native support for lists per a new datatype

Lists as first class citizens in RDF, represented by their own datatype, =
are a completely different approach that keeps the simple triple =
structure and hides structural complexity inside nodes of a specific =
type.=20
Datatyped lists would indeed provide some interesting properties: lists =
would be encapsulated in single nodes and consequently the triple as the =
basic bearer of truth in RDF would be uncompromised. A malformed list =
wouldn=E2=80=99t pose any semantic problem to the triple or graph in =
which it occurrs. datatyped lists could be designed to make explicit all =
the semantics that are already implicitly available in the different =
types of Containers and Collection: ordering, duplicates, alternatives, =
limits, maybe even some more. Implementations could easily optimize =
performance of such lists.=20
IMO they would however also need a triple-based representation to nail =
down their semantics in RDF in a backwards compatible way. N3 develops a =
mixed approach where the syntactic sugar known from Turtle is =
interpreted as a proper datatype with its own methods (built-ins in N3 =
speak) but also mirrored in the rdf:List vocabulary [3]. The same list =
can occurr as bracketed syntactic sugar or a first-rest-ladder in the =
same RDF graph. In principle this approach could just as well be =
implemented with the rdf:Container vocabulary.
Some tricky semantic questions around identity arise as encapsulating a =
list in a node introduces a level of indirection. N3=E2=80=99s issue =
about the relation between an rdf:List represented as first-rest-ladder =
and the same list as a (=E2=80=A6) datatype illustrates the problem. =
Earlier works suggest to interpret the first-rest-ladder as a kind of =
reification of the bracketed list but there remain open questions. Maybe =
the triplified version could be understood as owl:importing a datatyped =
list into the triple realm?=20
Proper identification always tends to have more facets than one expects =
and RDF has a record of oversimplifying that problem. OTOH issues about =
identification need to be resolved for good in more areas of RDF anyway =
- like denotation vs indication in URI semantics, Named Graph semantics =
in RDF 1.1, the upcoming RDF* semantics - and this might be a chance to =
tackle the problem in a principled way.
Other points need clarification too, e.g. attributions to a list node =
have to be disambiguated from attributions to individual list members =
(even if the attribution is made to all members). Pat provided a more =
detailed account of problems that will have to be solved [4] and David =
recorded them in the EasierRDF issue tracker [5].
Introducing more complex datatypes doesn=E2=80=99t need to be limited to =
lists but could also be used for reification (as RDF* proposes) and even =
n-ary relations etc. That would be quite a leap - however, as this =
represents a rather clean slate it=E2=80=99s probably better to start by =
thinking big.=20
Last not least introducing a native datatype in RDF requires quite some =
implementation effort throughout the whole Semantic Web tool chain. =
However RDF* is starting to proof that this can indeed happen if the =
need is understood and a rough consensus has been achieved.


How does it all fit together

A desirable outcome of the whole list/List issue IMO would be if in the =
long run:=20
- Containers became the go to solution for semantically lightweight =
descriptions of list-like data structures. Their informal Seq, Bag and =
Alt semantics seem to be intuitive and well understood. The proposed =
extension by a 'limit' attribute would satisfy a common need by data =
publishers to express that some description is complete. The bare syntax =
of rdf:Containers is bearable all things considered, unlike rdf:Lists. =
Still, syntactic sugar in Turtle and JSON-LD and a little more support =
in SPARQL would be very helpful.
- Constraints formulated in Shaecxl could take it from there and check =
and enforce such informally stated semantic intuitions and objectives in =
applications.=20
- Named Graphs may be used to denote environments where certain semantic =
restrictions apply and are enforced like e.g. lists being closed, =
default reasoning regime etc.
- Those requiring DL-safe constructs from the start or concentrating on =
DL environments anyway could alternatively resort to more involved =
design patterns for sequences.=20
- rdf:Lists were only used for OWL DL axiomatic statements.
- Lists as datatypes could complete this range of solutions. They would =
probbaly serve best the needs of application-oriented Linked Data-based =
data aggregation and publishing which doesn=E2=80=99t focus so much on =
modelling intricate knowledege structures and meta-modelling but on =
efficiency and high throughput.


Thomas


P.S.: Long emails take a lot of effort write and then nobody reads them =
because they are so long. But do complex discussions have to be =
constrained to academic papers and workshops? Of course I=E2=80=99m =
speaking out of self interest but I=E2=80=99d really like if this list =
would more be used for discussions about fundamental questions, for =
position statements, to discuss strategic directions for the Semantic =
Web.=20




(*) The paper by Daga et al. discusses list support in RDF stores in =
quite some detail. It suggest that it should be relatively easy to =
improve rdf:Container support in SPARQL considerably. It also notes that =
only querying was investigated and that in an update heavy scenario the =
first-rest-ladders of rdf:List might provide an advantage.
(**) I should probably be really specific and word this as "if one wants =
to describe a list as being closed" but you know what I mean
(***) I hope I understood Pat right when he wrote [6]: "Well, we could =
just have a semantic rule that says that IEXT(I(rdf:_n)) cannot contain =
< x, y> when rdfx:last contains <x, I(rdf:_m)> for any n>m. That would =
make statements about entries after the last one be inconsistent (always =
false) and allow applications to detect it by examining the innards of =
the membership properties, but not express it in RDF triples. But they =
could for example issue a potential error warning or take other special =
actions. "



[0] https://www.w3.org/TR/2004/REC-rdf-primer-20040210/
[1] https://www.w3.org/TR/rdf-mt/
[2] Daga et al. 2019 "Modelling and querying lists in RDF. A pragmatic =
study"
    http://CEUR-WS.org/Vol-2496/paper2.pdf
[3] https://lists.w3.org/Archives/Public/semantic-web/2020May/0065.html
[4] https://lists.w3.org/Archives/Public/semantic-web/2020May/0069.html
[5] https://github.com/w3c/EasierRDF/issues/74=20
[6] https://lists.w3.org/Archives/Public/semantic-web/2020May/0108.html
[7] https://lists.w3.org/Archives/Public/semantic-web/2020May/0112.html
[8] RDF 1.1 Note on Named Graphs, http://www.w3.org/TR/rdf11-datasets/
[9] Carroll et al. 2005 "Named Graphs"
    https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3D3199260
    =20