Collections vs Containers

RDF currently has two standard ways to represent sequences of resources,
which I'll call containers and collections. For example, to represent
the sequence A, B, C, we could do:

        # a container
    S1 rdf:_1 A.
    S1 rdf:_2 B.
    S1 rdf:_3 C.

or 

        # a collection
    S2 rdf:first A.
    S2 rdf:rest _:b1.
    _:b1 rdf:first B.
    _:b1 rdf:rest _:b2.
    _:b2 rdf:first C.
    _:b2 rdf:rest rdf:nil.


Collections have two advantages.
    1. They do not require an infinite vocabulary
    2. Adding a statement to a graph containing a well-formed collection
cannot change that collection *and* leave it well-formed.

On the other hand, they take twice as many statements, require an
arbitrary number of blank nodes, and can be a pain to query.

Anyway, the reason I bring this up is that S1 and S2 seem (to me) to
represent the same sequence: A, B, C. Furthermore, it seems like we
could map the container vocabulary onto the collection vocabulary.

For example:
        
    { A rdf:_1 B. } <-> { A rdf:first B. }
    { A rdf:_2 B. } <-> exists X. { A rdf:rest X. X rdf:first B. }
    { A rdf:_3 B. } <-> exists X, Y. { A rdf:rest X. X rdf:rest Y. Y
rdf:first B. }

Or, better yet:

    { A rdf:_3 B. } <-> exists X. { A rdf:rest X. X rdf:_2 B. }
    { A rdf:_4 B. } <-> exists X. { A rdf:rest X. X rdf:_3 B. }
    ...
    { A rdf:_[n] B. } <-> exists X. { A rdf:rest X. X rdf:_[n-1] B }

Since all the various rdf:_[n] properties are subproperties of
rdf:member, this has the nice side effect of making all the members of a
collection be values of rdf:member.

    { S rdf:first A;
        rdf:rest [
          rdf:first B;
          rdf:rest [ rdf:first C; rdf:rest rdf:nil ]
        ]
    } -> { S rdf:member A, B, C }.

It also shows that a collection encodes more information than the
equivalent container, for example:

    { S rdf:first A;
        rdf:rest [
          rdf:first B;
          rdf:rest [ rdf:first C; rdf:rest rdf:nil ]
        ]
    } -> { S rdf:_1 A; rdf:_2 B; rdf:_3 C }

*but*

    { S rdf:_1 A; rdf:_2 B; rdf:_3 C } ->
    { S rdf:first A;
        rdf:rest [ rdf:first B ], [ rdf:rest [ rdf:first C ]] }.

Even if S is known to be a well-formed list (in which case rdf:first and
rdf:rest are functional), we still can't infer the rdf:nil.

Perhaps this idea is already obvious to the community, but I hadn't seen
it in any of the literature, and it seemed neat, so here you go.
-- 
David Menendez <zednenem@psualum.com> <http://www.eyrie.org/~zednenem/>

Received on Wednesday, 12 November 2003 01:19:42 UTC