W3C home > Mailing lists > Public > www-rdf-interest@w3.org > November 2003

Collections vs Containers

From: David Menendez <zednenem@psualum.com>
Date: Wed, 12 Nov 2003 01:19:46 -0500
To: www-rdf-interest@w3.org
Message-ID: <r02000200-1030-370003B214D811D8B0D8000393758032@[10.0.1.2]>

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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:03 GMT