W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > April to June 2004

Subgraph results counter-example(s)

From: Rob Shearer <Rob.Shearer@networkinference.com>
Date: Tue, 8 Jun 2004 07:45:54 -0700
Message-ID: <CFE388CECDDB1E43AB1F60136BEB49730280D2@rome.ad.networkinference.com>
To: <public-rdf-dawg@w3.org>

The current requirement says to return the subgraph "that the query
matches", which suggests that any information used to determine whether
solutions should be returned is part of the result.

The most trivial problems occur when the query contains disjunction:
"find everyone who is friends with Eddie or friends with Jane". If
someone is friends with both of these people, what results should be
returned? Either a query processor is required to follow all disjunction
even thought it's redundant (and return both the triples if they both
exist), or the results are nondeterministic.

The more serious issue is that such a requirement can completely kill
the use of "supplementary" information about RDF graphs. OWL, SWRL, or
other languages can encode information which allows you to derive the
fact that Eddie is friends with Jane. This may be the result of
interaction between dozens or hundreds of axioms. If some of these
axioms are encoded in RDF, are we supposed to return them? What about
the supplementary information which is not in RDF? What about such
information which does have an RDF representation but also has other
formats, and one of those other formats was used?

Worse, such other languages can encode disjunction in the language
itself: one can assert that someone is friends with either Eddie or Jane
without specifying which one. Now there isn't even a final "result"
triple than can be returned in the result; *now* do we have to go back
and try to figure out what bits of supplementary information need to be

This also clashes with a few other objectives, including the querying
for non-existent results. (Does *every* triple affect this?)

The problem is that this requirement as written introduces the notion of
"explanation", which is actually a *very* hard problem in general, and
is almost always more information than the user really wanted.
Received on Tuesday, 8 June 2004 10:47:48 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:00:44 UTC