Re: Final text for Basic Graph Patterns

Enrico Franconi wrote:
> 
> Hi,
> we ask to finalise the text of Section 2.5.
> 
> The new proposal of Pat 
> <http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JanMar/0061.html> 
> does not work for any approach where bnodes are implicit, and this 
> happens not only for OWL-Lite entailment, as we already pointed out in 
> <http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JanMar/0064.html>, 
> but also for RDF entailment. For example, given the graph
>     :john :age "25"^^xsd:decimal .
> the query
>     ASK { _:b rdf:type rdf:XMLLiteral }
> should clearly return YES if RDF entailment is considered.
> However,
> according to the latest proposal from Pat the answer to the query would 
> be NO regardless of the type of entailment considered. The reason is 
> that Pat considers bnodes in the query restricted to be bound only to 
> URIs and bnodes explicitly appearing in the graph.

This hinges on the different definitions of 'pattern solution'.  The scoping
graph proposal maps variables and bNodes; the ordered-merge proposal maps
just variables.  Each has consequences.

If bNodes are bound by pattern solutions, then the algebra works out as per
the current document.

If bNodes are not bound at all, as in the ordered-merge proposal, then there
is a change to the algebra.

Query:

{ _:a :p ?v
   FILTER(?v < 5)
   _:a :q ?x
}

Data:
:A :p 3
:A :q :x
:B :q :y

under the ordered-merge proposal:
BGP1 { _:a :p  3 } => ?v/3
BGP2 { _:a :q ?x } => solutions (?v/3, ?x/:x) and (?v/3, ?x/:y)

under the scoped graph proposal [+]:
BGP1 { _:a :p  3 } => (?v/3, _:a/:A)
BGP2 { _:a :q ?x } => (?v/3, _:a/:A, ?x/:x)


The query
{ _:a :p ?v .
   _:a :q ?x
   FILTER(?v < 5)
}
has one solution under both proposals.


Further examples exist such as:
{ _:a :p ?v { _:a :q ?x } UNION { ... } }

I hadn't realised that, under the ordered-merge proposal, this does not have 
the canonical expansion people might expect.

- - - - - - - -

[+] I can read the definition in the scoping graph proposal in other ways as 
to whether a bNode in a BGP must be bound or whether it can be left alone - it
depends on how the "by its value under B" is interpreted when it has no such
value.  If it is left alone then the machinery works the same in each case.

- - - - - - - -

The algebra works if a bNode in occurring in two or more BGPs in a graph
pattern is bound by the pattern solution [*].

This is a conservative approach and, like any extension to the level of
entailment, more solutions might become possible when relaxed.  It would allow
all entailments for queries consisting of a single BGP.  It would leave open 
the possibility ofthe rdfD1 use case above as an extension.

	Andy

[*] OPTIONALs may not need this treatment but it is simpler and preserves
rewrites.

> 
> At this point it is becoming too late. We ask that either our text is 
> used (with possible editorial changes to discuss), or that the DAWG does 
> not conclude the work on the 31st of January and we'll have a F2F during 
> the W3C tech plenary in France at the end of February.
> We recall that our text provides the use of entailment, the 
> correspondence with the subgraph matching based implementations, and 
> uniqueness of solutions for interoperability; its core definitions are 
> stable since its appearance on the 2nd of November 2005 
> <http://www.inf.unibz.it/krdb/w3c/sparql/>.
> 
> So, the latest version of our proposed text for Section 2.5 (having 
> minor changes wrt our previous proposal 
> <http://lists.w3.org/Archives/Public/public-rdf-dawg/2006JanMar/0018>) 
> is below.
> 
> 
> """
> 2.5  Basic Graph Patterns
> 
> Definition 4 (OrderedMerge)
> The OrderedMerge of a sequence of graphs is the ordered merge-union of 
> the graphs, where repeated bnodes are substituted with fresh ones, by 
> keeping the names of the bnodes coming first in the sequence order. Note 
> that, w.r.t. the standard definition of RDF merge [RDF-MT], if any of 
> the graphs contains variables, then those are not renamed (i.e., 
> variables are treated as URIs).
> 
> The above OrderedMerge definition is totally compatible with the RDF 
> merge definition given in [RDF-MT]. In particular, if the graphs do not 
> contain any variable or they are considered simply as IRIs, then 
> OrderedMerge is a RDF merge. The other way around is not true in 
> general, since the original definition does not specify which bnodes are 
> renamed. From the semantic point of view OrderedMerge is equivalent to 
> RDF merge; moreover, if the graphs do not share any bnode name, then the 
> two results are “syntactically” identical, in the sense that they 
> contain the same triples.
> 
> Definition: Basic Graph Pattern matching.
> A Basic Graph Pattern is a set of Triple Patterns.
> A basic graph pattern, BGP, matches on graph G with pattern solution S if:
>     - G  simply entails  S( G OrderedMerge BGP )
>     - the graph S( G OrderedMerge BGP ) is an RDF graph
>     - the bnodes involved in S are among the bnodes appearing in G.
> 
> Simple entailment (as defined in [RDF-MT]) is the default choice of 
> entailment in SPARQL, since it allows for the basic operation of 
> querying the "syntax" of RDF graphs, completely neglecting its 
> semantics. In this way, the basic option for SPARQL is to manipulate 
> graphs, rather than involving reasoning on knowledge bases; the latter 
> may be possible by choosing another form of entailment, among the 
> current standards of W3C. In fact, with the proviso that bnodes are not 
> allowed to appear in pattern solutions, SPARQL may be extended to 
> provide a way to override the default "simple entailment" with "RDF 
> entailment", "RDFS entailment" (as defined in [RDF-MT]), and "OWL 
> entailment" (as defined in [OWL-Semantics], where the syntactic 
> restrictions in OWL-DL or OWL-Lite should be reflected in suitable 
> syntactic restrictions on the form of basic graph patterns).
> 
> In the default case of simple entailment, Basic Graph Pattern matching 
> corresponds really to the expected operation of subgraph matching from 
> the basic graph pattern (the query) to the graph (the dataset). So, 
> querying a dataset with a basic graph pattern corresponds to find all 
> the assignments for variables and bnodes in the query pattern such that 
> the resulting graph is a subgraph of the dataset. This provides a 
> connection for the formal definition of basic graph pattern matching to 
> the practices adopted in SPARQL implementations.
> 
> Implementational hint: Simple Entailment as Subgraph Matching.
> In the case of simple entailment, a pattern solution can be equivalently 
> defined as follows: for each subgraph matching between BGP and G, where 
> bnodes and variables in BGP are mapped to any node in G, a pattern 
> solution is the mapping of variables in BGP to nodes in G.
> 
> Moreover, the uniqueness property of pattern solutions guarantees the 
> interoperability between SPARQL systems: given a graph G and a basic 
> graph pattern query BGP, the set of all the pattern solutions is unique.
> """

Received on Sunday, 15 January 2006 18:02:12 UTC