W3C home > Mailing lists > Public > public-rdf-dawg@w3.org > July to September 2006

ISSUE: entailment and general framework

From: Fred Zemke <fred.zemke@oracle.com>
Date: Fri, 22 Sep 2006 13:32:22 -0700
Message-ID: <45144856.40103@oracle.com>
To: public-rdf-dawg@w3.org

I believe that section 5 "Basic graph patterns" and especially
5.1 "General framework" need a rewrite.  I believe the following
issues with this material need to be addressed:

1. The discovery that the general framework is not equivalent
to the mapping technique for simple entailment, as shown in
http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JulSep/0081.html


2. I believe that the general framework needs to define when a solution
of a basic graph pattern satisfies a Constraint (rule [27]).
This is because of the possibility that a FILTER might contain a predicate
such as _:a != _:b .
See 
http://lists.w3.org/Archives/Public/public-rdf-dawg/2006AprJun/0189.html
and the discussion that followed that thread.  My reading of that thread
is that the consensus was that the scope of a blank node identifier
needs to be enlarged to be at least rule [21] FilteredBasicGraphPattern
rather than merely a basic graph pattern.  To me, this implies that
we need to define "filtered basic graph pattern matching" rather than
just "basic graph pattern matching".

3. The definition of E-entailment regime, taken literally, says that
any subset of P(RDFG) x P(RDFG) is an entailment regime, where
P(RDFG) is the power set of RDFG, the set of all RDF graphs.
In contrast, reference [RDF-MT] "RDF Semantics" never actually
defines entailment, but I see two consequences from the discussion
there:

a) Entailment is a relation from a set of graphs to a single graph,
not to a set of graphs.  Thus we want a subset of P(RDFG) x RDFG.
It seems the text also has this in mind, since the definition of
"well-formed" contemplates that the range of E (ie, the projection
of E on its second component) is not a set of sets of graphs but
a set of graphs.

b) Entailment involves the notion of correct inferencing: given
a set of graphs S, they entail graph G if all interpretations of S
are interpretations of G.  Thus it is not true that just
any subset of P(RDFG) x RDFG constitutes an entailment.


4. The definition of "well-formed for simple entailment" is difficult
to apply.  It seems that all RDF graphs are well-formed for simple
entailment.  For example, every graph G is entailed by the singleton
set { G }.  Therefore every RDF graph is in the range of simple
entailment.  Therefore every RDF graph is well-formed.  So what
is the point to this concept?

Looking ahead, it seems that the reason for introducing "well-formed"
is for the third bullet in the definition of "basic graph pattern
e-matching".  However, the fourth bullet of that definition already
implies the third bullet.  That is, if G E-entails (G' union S(BGP')),
then G' union S(BGP') must be in the range of the entailment E,
and so must be well-formed.  Hence it seems that we can dispense
with the notion of well-formed, since the only use of it is
superfluous.


5. After the definition of scoping set, it says "The scoping set may be
characterized differently by different entailment regimes".
I don't know what "characterized" means here.  Does it mean that
the entailment implies the scoping set?  So that simple entailment
uses one scoping set and RDF-entailment uses another scoping set?
If in fact the scoping set is not an independent parameter, then
the scoping set should be mentioned in the definition
of "E-entailment regime".


6. Definition of scoping graph says that "*the* scoping graph ... is
*an* RDF graph".  This does not make sense.  One cannot use
"the" to refer to something that is not pinned down uniquely.
There is not one graph that is uniquely graph-equivalent to G.
What we mean is "A scoping graph... is an RDF graph...".

After making this correction, the definition of scoping graph does
not imply the sentence immediately following the definition,
"The [sic, should be "a"] scoping graph makes the graph to be matched
independent of the chosen blank node names".  For example,
G is graph-equivalent to G, trivially, therefore G is a scoping
graph for itself.  But if G has a problem with blank node names,
then the scoping graph G also does, so we cannot conclude that
the scoping graph automatically solves this problem.  The best that
can be said that a suitably chosen scoping graph will make
the graph to be matched independent of the chosen blank node names.

Looking ahead to the use of the notion, it is currently treated as
a parameter in the definition of "basic graph pattern E-matching".
However, I doubt that one has a specific scoping graph in mind when
one does a basic graph pattern E-match.  That is, treating
"basic graph pattern E-match" as a boolean-valued function, you don't
want the scoping graph as one of the arguments to this function.

Proposed resolution: Delete the definition of "scoping graph", and
in the definition of "basic graph pattern E-matching", delete the
phrase "with scoping graph G'", replacing it with a new bullet
reading "there exists a graph G' that is graph-equivalent to G".

7. (editorial) The pattern solution S is not being treated with the
same respect shown to the other parameters in the definition
of "basic graph pattern e-matching".  It should be listed as one
of the "givens" at the start of the sentence.

8. In the definition of "Basic graph pattern E-matching", regarding
the first bullet:

a) it would be clearer if it were
reworded "There exists BGP' such that BGP' is a basic graph pattern
...".

b) The notion of graph-equivalent is not defined for basic graph
patterns, only for graphs.  Rather, the defined term is just
"equivalent".
All together, the first bullet should read
"There exists BGP' such that BGP' is a basic graph pattern that is
equivalent to BGP"

(An alternative solution would be to rename the notion of
"equivalent basic graph patterns" to "graph-equivalent basic graph 
patterns".)


9. Summary of my proposed rewrite to the definition of "Basic graph pattern
E-matching":

Given:
- an entailment regime E,
- a basic graph pattern BGP,
- an RDF graph G,
- a pattern solution S, and
- a scoping set B
then BGP E-matches with pattern solution S on graph G with
respect to B if:
- There exists a basic graph pattern BGP' and a graph G' such that:
 + BGP' is equivalent to BGP
 + G' is graph-equivalent to G
 + G' and BGP' do not share any blank node labels
- G E-entails (G' union S(BGP'))
- The RDF terms introduced by S all occur in B

Fred
Received on Friday, 22 September 2006 21:11:48 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 16:15:27 GMT