- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Tue, 20 Sep 2005 00:55:09 +0200
- To: RDF Data Access Working Group <public-rdf-dawg@w3.org>, Pat Hayes <phayes@ihmc.us>
Hi.
(This message summarises long discussions and studies we did in the
last ten days with Sergio Tessaris, PFPS, Bijan.)
In this long message I will argue:
(a) how can we introduce the notion of entailment in SPARQL, and how
should we change and/or understand the current definitions in
order to have an entailment-based core (as opposed to subgraph
matching); here we don't argue whether this is useful and how this
is going to be used. This is the basis for the real definitions
given in (b) and (c).
(b) we show how it is possible to get the current understood and
implemented behaviour of SPARQL once we have entailment as the
basis of SPARQL. This gives a semantics to what we call
"told-bnode redundant" answers, which behaves *exactly* like the
current subgraph matching semantics.
(c) we finally show how we can get pure entailment based answers as a
simple extension of the case (b), so that we get correct RDF
entailed answers, and we obtain a system which may scale up to
OWL-DL querying.
Overall, we hope that this message highlights the fact that it is
possible to adopt an entailment based semantics for SPARQL that (i)
maintains the properties of graph matching of the current
understanding of SPARQL, and (ii) allows for future interoperability
with OWL based languages.
------------------------------------------------------------------------
(a) ON CLOSURE VS ENTAILMENT
[issue <http://www.w3.org/2001/sw/ DataAccess/issues#rdfSemantics>]
* Definition of Matching for a basic graph pattern from
<http://www.w3.org/TR/rdf-sparql-query/#BasicGraphPatternMatching>:
Definition: Graph Matching
A basic graph pattern [...] matches if S(GP) is an RDF graph
and is a subgraph of G.
This definition, as Bijan and Pat argued, assumes that G is already
a closure of an original graph G0, and, as explicated in the mailing
list, calculating G is "somebody else['s] business"
<http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JulSep/0380>.
But what closure? There are several possibilities.
First case (completion):
One closure is the completion of G under the rdf or rdfs entailment
rules from RDF Semantics, or just G itself (for simple entailment,
which is what all the current implementations are looking at now).
Because of the entailment lemmas for simple, rdf, and rdfs entailment
in RDF Semantics, matching by means of the usual subgraph isomorphism
(with special care of bnodes) works properly in the cases of simple,
rdf, or rdfs entailment, but it does not work for any logic without
the minimal model property (such as OWL-Lite/DL).
In fact, for other entailments there may not be such a set of
entailment rules leading to a unique model representative (see, e.g.,
the worker example in OWL-Lite
<http://www.w3.org/2001/sw/DataAccess/issues#owlDisjunction>), so this
approach is only guaranteed to work for simple, rdf, and rdfs
entailment. As well, the closure of any graph under the rdf and rdfs
entailment rules is always infinite (since there is the infinite
rdf-vocabulary rdf:_1, rdf:_2, etc), so the closure cannot be directly
computed; as a possible solution to this problem, we may easily assume
that this part of the vocabulary is finite.
Second case (deductive closure):
Another closure is the deductive closure,
G = graph-merge{ GPi | G0 entails GPi }.
In principle, this one will always work, in that matching will then
pick up all entailments, for whatever definition of entailment one
wants. This basically emulates the idea of constructing the set of all
deductions, and each solution S(GP) should be element of that set.
Note that, even in the case of simple entailment, the deductive
closure G is not just the completion of G0 as defined in RDF-MT.
Consider the following example:
G0 = { :a :P :a . }.
The simple completion of G0 is just G0. OTOH, the simple deductive
closure of G0 includes also all the infinitely many triples of the
kind:
{ :a :P _:x . _:x :P :a }
{ :a :P _:x . _:x :P _:y . _:y :P :a }
{ :a :P _:x . _:x :P _:y . _:y :P _:z . _:z :P :a }
...
Third case (entailment):
It is easy to show that the definition of matching making use of the
deductive closure is equivalent to the one which makes directly use of
entailment (for a wide range of entailments including OWL-DL
entailment):
Definition: Entailment Matching
A basic graph pattern GP matches on graph G with solution S if
S(GP) is an RDF graph and is entailed by G.
Note that there is no need to compute a closure here, and so no
infinite graphs are involved in the definition. It is up to the
appropriate definition of entailment to define when a GP is entailed
by G, given their RDF linearisation.
OUR CONCLUSIONS
Both the definition of graph matching with deductive closure and the
definition of graph matching based directly on entailment are
obviously equivalent, and both correctly work with with RDF and OWL
entailment (cfg., the "worker example"
<http://www.w3.org/2001/sw/DataAccess/issues#owlDisjunction>).
However, we strongly believe that the direct use of entailment in the
definition provides a more intuitive and direct approach, and it has
the advantage that it uses the original graph without any
transformation.
(Referring to <http://lists.w3.org/Archives/Public/www-archive/
2005Sep/0009>, the query and its proof doesn't capture the main idea
behind the "worker example". In fact, the graph in the message
doesn't implies that :Andrea is an instance of :EMPLOYEE, so the
tuple (:Paul :Andrea :Caroline) cannot be in the answer of the given
query. Most likely, the theorem prover didn't consider the certain
answers (those true in every model) but possible answers (as those
true in at least one model). The only variable in the SELECT should
be ?X, then the query returns :Paul because of reasoning by case on
all the possible models of the graph.)
------------------------------------------------------------------------
ON REDUNDANCY OF TOLD BNODES IN ANSWERS
[issue <http://www.w3.org/2001/sw/DataAccess/issues#rdfSemantics>]
"""
Should queries of non-lean and lean graphs that entail each other
give the same answers?
"""
The answer to this question should be *yes*. See use case 1,
"Publishing on the Web", in
<http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JulSep/0430>).
This is also relevant, as noted by PFPS, to enable interoperability
between different interoperating implementations of RDF.
Please note that in the case of the relational model (e.g., SQL) this
problem does not arise, since there is no equivalent to the bnodes in
the relational data model, and redundancy never appears in the data
and the answer sets of arbitrary relational algebra queries are always
non redundant. Also note that the notion of SQL queries is perfectly
formalised as entailment (after the seminal works by Ray Reiter in the
late 70ies), and as a matter of fact when a notion similar to bnodes
sneaked in the relational model in the form of null values, the logic
based definition of query answering proved to be extremely useful to
characterise the various notions of incompleteness implied by the null
values. So, the peculiarity and interestingness of SPARQL lies in the
fact that it allows bnodes in the answers.
On the oher hand, in SPARQL there are cases where some controlled form
of redundancy is desirable. According to the use case 2 "Building a
Graph" (in
<http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JulSep/0430>)
it may be necessary to get in the solution set also the redundant
bnodes as they appear "redundantly" in the original non-lean graph. We
call this "told bnodes redundancy". The current general understanding
and the current implementations of SPARQL capture exactly this kind of
redundancy. This behaviour can be seen as querying the syntactic form
of the an RDF graph, and it is an important part of the motivations of
SPARQL. We want to formalise this understanding first.
This can be achieved by transforming all the bnodes in the original
graph G into fresh skolem constants before evaluating any basic
pattern query. The skolem constants appearing in the resulting
solution set are transformed back into their original bnode names
before starting the evaluation process by the SPARQL algebra. We
observe that in RDF/S the only bnodes that will ever appear in the
solution may appear only in correspondence of the bnodes in the
original graph. We can show that the only bnodes that will appear in
the answer will be the ones coming through the skolemisation
process. Therefore, the definition of Pattern Solution
<http://www.w3.org/TR/rdf-sparql-query/#PatternSolutions> should be
changed to disallow the use of bnodes in the substitution:
A pattern solution is a substitution function from a subset of
the set of variables to the set of the IRIs and RDF Literals.
In other words, we say that a solution S is a substitution of the
variables in a query with only IRIs and literals, and it is in the
solution set of a query GP to a graph G iff there exists a S' such
that
SK(G) entails S'(GP), and S = UNSK(S'(GP)),
where SK is a skolemisation operation of the bnodes, and UNSK is its
inverse (giving back the bnode names to the skolem constants).
This guarantees that the solution set is always finite, and the only
redundancy will be from the told bnodes.
Note that it can be shown that this changed basic pattern evaluation
procedure corresponds to the current SPARQL algorithms. This means
that no change should be made to the current systems if they want to
implement the semantics allowing for redundancy of told bnodes.
Note also that in order not to change the original told names of those
bnodes, it is required that the subsequent SPARQL algebra always
preserves the bnode names.
OUR CONCLUSIONS
This is the semantics of the current SPARQL implementations, that
allows for told-bnodes redundancy in the solution set. We also
introduce (in the next section) the non-redundant semantics, that is
defined by "minimising" the told-bnode redundant solution set.
------------------------------------------------------------------------
(c) ON REDUNDANCY AND MINIMALITY OF ANSWERS WITH BNODES
[issue <http://www.w3.org/2001/ sw/DataAccess/issues#rdfSemantics>]
"""
Should queries of non-lean and lean graphs that entail each other
give the same answers?
"""
As said before, the answer to this question should be *yes*. See use
case 1, "Publishing on the Web", in
<http://lists.w3.org/Archives/Public/public-rdf-dawg/2005JulSep/0430>).
We present here how this can be achieved by requiring a form of
minimality of the solution set at the level of basic query patterns
evaluation after the computation of the told-bnode redundant solution
set as shown before.
There are two problems here:
1/ Pairwise redundancy between two independent solutions, as in
G1 = { ex:a ex:b ex:c .
_:a ex:b _:c . }
GP = { ?a ex:b ?c . }
The closure matching solutions are (and the entailment solutions
include)
S1 = { {?a/ex:a, ?c/ex:c} ,
{?a/ _:a, ?c/ _:c} }
The second solution is redundant, in that it is simple-entailed by
the first.
2/ Information present in the graph that is lost when solutions are
considered independently, as in
G2 = { ex:a ex:b ex:c .
_:a ex:b _:c .
ex:a' ex:b _:c . }
GP = { ?a ex:b ?c . }
The closure matching solutions are
S2 = { {?a/ex:a, ?c/ex:c} ,
{?a/ _:a, ?c/ _:c} ,
{?a/ex:a', ?c/ _:c} }
There is information present in this set of solutions that is lost
if the blank nodes in the solution are considered to be scoped to
each different substitution, and the solution reduced to
S2' = { {?a/ex:a, ?c/ex:c},
{?a/ex:a', ?c/ _:c} }
In order to provide a non-redundant semantics, we introduce the
minimisation of the solution set.
Given a set AS of solutions of a basic graph pattern GP
(remember that a solution of a GP is an assignment to the n
variables in GP), its FO translation FO(AS) is the FO formula
formed by a conjunction of atoms, each one of them
corresponding to a solution in AS encoded as n arguments of a
special fixed predicate (say, S); the bnodes are globally
existentially quantified (so the coreferences are preserved).
For example:
GP: { ?x ?y }
AS: { <_:a, :b>, <:c, _:d>, <:e, _:d>, ... }
FO(AS): \exists _:a, _:d, ...
S(_:a, :b) \and S(:c, _:d) \and S(:e, _:d) \and ...
The minimal solution set, is the solution set which is minimal w.r.t.
the order induced by FO entailment among all possible subsets of AS.
It can be proved that such minimal solution set exists and it is
unique. The problem is NP-hard in the dimension of cycles with bnodes
in AS.
Comment: if bnodes are not appearing in the solution set, the process
of minimisation is not required, since each solution is unique and the
set is automatically non-redundant. Bnodes may appear in the solution
set *only* if they appear in the original graph (in fact, bnodes in
the solution set come only through the process of skolemisation). So,
if the original grah is lean, we get a correct (i.e., sound and
complete) non redundant solution set; if the original graph is not
lean, we get a correct (i.e., sound and complete) finitely redundant
solution set (whit the only redundancy of the told redundant nodes in
G).
Note that in order to keep the coreference among bnodes across
different solutions also in the final graph obtained by the CONSTRUCT
operation, it is required that the RDF-merge operation changes only
the name of the bnodes in the CONSTRUCT template but not the bnode
names from the solutions.
The minimisation of the solution set basic query pattern provides the
starting point for the evaluation of the SPARQL complex query. In
fact, it can be observed that each composite SPARQL query is grounded
on the evaluation of basic patterns. It can be shown that each SPARQL
operator preserves the minimality of the solution set, but the SELECT
and UNION operators (just like in SQL). For those two operators, we
require the adoption of an optional keyword "DISTINCT" that forces
the minimisation of the operator application.
OUR CONCLUSIONS
Minimisation on solutions sets of basic graph patterns should always
be performed in the case one want a generic pure entailment based
query answering mechanism, and one does not want the told-bnode
redundancy; minimisation of SELECT and UNION operators is optional by
means of the keyword DISTINCT.
------------------------------------------------------------------------
Received on Monday, 19 September 2005 22:55:50 UTC