Re: Efficient context mechanisms

Dave,
> > [Discussion on contexts]
>
> > If you ever decide to get serious about contexts, it would probably be
> > worth your
> > while to assign someone the task of deciphering our context algorithm (or
> > Austin's).
> > It may be overkill for RDF, but some of the lessons learned probably 
> apply to
> > simpler context systems.
>
>I agree. A serious context mechanism is not on our short term priority 
>list but
>it's an interesting area to think about in the longer term. The open world
>assumption behind the semantic web makes it likely that some applications will
>require non-monotonic reasoning, some forms of which would benefit from 
>such an
>efficient context mechanism.

We have an application that is tracking objects across time.  We seem
to need a context per time frame (or a model per time frame).  So contexts
can arise for very simple datasets.

>What is the space complexity of the algorithm like?

The contexts are organized into a hierarchy, and numbered so
that a parent's number is always smaller than the numbers of its
descendants.  Some sort of data structure is needed that can quickly
determine, given two contexts C1 and C2, whether C1 inherits C2.
One could imagine that the space requirements for this would be
superlinear in the worst case, but they should be linear (in the number
of contexts) for the average case.

Each statement/triple points to a list of contexts where it has
appeared within an assertion. If a triple [S P O] is asserted to be true in
contexts C1, C2, and C3, then there is a triple object that points
to a list containing C1, C2, and C3 (ordered according to the
numbers they are assigned, largest number first).

If we were using a quad representation, then memory is linear in
the number of quads.  However, wrt quads, I'm not sure our notion is
in sych with the statings crowd.  Suppose the quad form is

[C1 S P O]
[C2 S P O]
[C3 S P O]

While we conceptualize this as one triple [S P O], asserted
in three different contexts, the statings crowd seems two think of
these quads as three different statings that are only loosely
related.

What the semantics of the above is can't really be resolved unless we
decide on what a quad is (for example, must one of its arguments always
be a context?) and what a context is (e.g., is a context a set of
assertions or a set of statings?).

Cheers, Bob

Received on Tuesday, 14 January 2003 13:58:38 UTC