Text for 18.6 Extending SPARQL Basic Graph Matching

Hi all,
Andy suggested that we take my concerns about the text in 18.6 to
another thread since this is already old SPARQL 1.0 text and not an
issue with newly introduced features.

I wrote:
"18.6 Extending SPARQL Basic Graph Matching
I am not quite happy with the text (in particular the formulation of
the conditions) since it is not at all well-aligned with the notation
used in the rest of the document, e.g., "answer set" is everywhere
else "solution sequence" and in this case answer set is even a set of
pattern instance mappings, which is not the case anywhere else, where
a BGP evaluates into a multiset of solution mappings and the RDF
instance mappings just determine the multiplicity.

We (Markus Krötzsch and I) discuss what is wrong with the conditions in
an ISWC paper and I am happy to suggest a more aligned version of the
conditions, if the WG is interested in this."

I propose, therefore, to change the text with the purpose of getting
the terminology aligned with the rest of the spec and motivate more
clearly the purpose of the conditions (see also Sec. 4 of the attached
paper for explanations for the proposed changes).

Current text:
A SPARQL extension to E-entailment must satisfy the following conditions:
1. The scoping graph SG, corresponding to any consistent active graph
AG, is uniquely specified and is E-equivalent to AG.
2. For any basic graph pattern BGP and pattern solution mapping P,
P(BGP) is well-formed for E.
3. For any scoping graph SG and answer set {P_1,...,P_n} for a basic
graph pattern BGP, and where BGP_1, ..., BGP_n is a set of basic graph
patterns all equivalent to BGP, none of which share any blank nodes
with any other or with SG
  SG E-entails (SG union P_1(BGP_1) union ... union P_n(BGP_n)).
4. Each SPARQL extension must provide conditions on answer sets which
guarantee that the set of triples obtained by instantiating BGP with
each solution μ is uniquely specified up to RDF graph equivalence, and
should provide further conditions to prevent trivial infinite answers
as appropriate to the regime.

Proposed text:
An entailment regime E must provide conditions on basic graph pattern
evaluation such that for any basic graph pattern BGP, any RDF graph G,
and any evaluation that satisfies the conditions, the resulting
multiset of solutions is uniquely determined up to RDF graph
equivalence. We denote the multiset of solutions from evaluating BGP
over G using E with Eval_E(G, BGP).
An entailment regime must further satisfy the following conditions:
1. For any consistent active graph AG, the entailment regime E
uniquely specifies a scoping graph SG that is E-equivalent to AG.
2. A set of well-formed graphs for E is specified such that, for any
basic graph pattern BGP, scoping graph SG, and solution mapping μ in
Eval_E(SG, BGP), the graph μ(BGP) is well-formed for E.
3. For any basic graph pattern BGP and scoping graph SG, if μ_1, ...,
μ_n in Eval_E(SG, BGP) and BGP_1, ..., BGP_n are basic graph patterns
all equivalent to BGP but not sharing any blank nodes with each other
or with SG, then
  SG E-entails SG union μ_1(BGP_1) union ... union μ_n(BGP_n)
4. Entailment regimes should provide conditions to prevent trivial
infinite solution multisets as appropriate to the regime.

The uniqueness requirement of condition 4 is moved above all other
conditions, since 2. and 3. don't make sense if the solution multiset
was not defined in this sense. I am happy to turn the text into XML if
we decide to replace the current text with the proposed one.

The notes (18.6.1 Notes) on BGP matching extensions also have some
inconsistent use of pattern instance mappings as solutions/answers:

(b) ... If the extension does not allow answer bindings to blank
nodes, then this condition can be simplified to the condition:
SG E-entails P(BGP) for each pattern solution P.
should be
(b) ... If the extension does not allow bindings to blank nodes, then
this condition can be simplified to the condition:
  SG E-entails μ(BGP) for each solution mapping μ.

(d) ...an empty answer set.
should be
(d) ...an empty solution sequence.

(e) ... Every answer P_i is the solution mapping restriction of a
SPARQL instance M_i such that M_i(BGP_i) is a subgraph of SG. Since
BGP_i and SG have no blank nodes in common, the range of M_i contains
no blank nodes from BGP_i; therefore, the solution mapping P_i and RDF
instance mapping I_i components of M_i commute, so M_i(BGP_i) =
I_i(P_i(BGP_i)). So
M_1(BGP_1) union ... union M_n(BGP_n)
= I_1(P_1(BGP_1)) union ... union I_n(P_n(BGP_n))
= [ I_1 + ... + I_n]( P_1(BGP_1) union ... union P_n(BGP_n) )
since the domains of the I_i instance mappings are all mutually
exclusive. Since they are also exclusive from SG,
SG union [ I_1 + ... + I_n]( P_1(BGP_1) union ... union P_n(BGP_n) )
= [ I_1 + ... + I_n](SG union P_1(BGP_1) union ... union P_n(BGP_n) )
i.e.
SG union P_1(BGP_1) union ... union P_n(BGP_n)
has an instance which is a subgraph of SG, so is simply entailed by SG
by the RDF interpolation lemma [RDF-MT].
should be

(e) ... For every solution mapping μ_i, there is, by definition of
basic graph pattern matching, an RDF instance mapping σ_i such that
P_i(BGP_i) is a subgraph of SG where P_i is the pattern instance
mapping composed of μ_i and σ_i. Since BGP_i and SG have no blank
nodes in common, the ranges of σ_i and μ_i contain no blank nodes from
BGP_i; therefore, the solution mapping μ_i and the RDF instance
mapping σ_i of P_i commute, so P_i(BGP_i) = σ_i(μ_i(BGP_i)). So
P_1(BGP_1) union ... union P_n(BGP_n)
= σ_1(μ_1(BGP_1)) union ... union σ_n(μ_n(BGP_n))
= [ σ_1 + ... + σ_n]( μ_1(BGP_1) union ... union μ_n(BGP_n) )
since the domains of the σ_i RDF instance mappings are all mutually
exclusive. Since they are also exclusive from SG,
SG union [ σ_1 + ... + σ_n]( μ_1(BGP_1) union ... union μ_n(BGP_n) )
= [ σ_1 + ... + σ_n](SG union μ_1(BGP_1) union ... union μ_n(BGP_n) )
i.e.
SG union μ_1(BGP_1) union ... union μ_n(BGP_n)
has an instance which is a subgraph of SG, so is simply entailed by SG
by the RDF interpolation lemma [RDF-MT].

Best regards,
Birte


-- 
Dr. Birte Glimm, Room 309
Computing Laboratory
Parks Road
Oxford
OX1 3QD
United Kingdom
+44 (0)1865 283520