The standard semantics of SPARQL and the standard semantics of RDF differ fundamentally, sometimes leading to unintuitive answers. In this paper, we thus motivate an alternative semantics for SPARQL based on certain answers, taking into account the existential nature of blank nodes, the open-world assumption of RDF, and perhaps even the lack of a unique name assumption. We propose that SPARQL is a natural use-case for applying existing techniques that approximate certain answers in relational database settings.
The foundational “simple semantics” of RDF is based on three premises: (i) an open world assumption (OWA) where anything not present in the data is assumed to be neither true nor false, (ii) a lack of unique name assumption (no UNA) where multiple names can refer to the same thing, and (iii) the presence of existential variables in the form of blank nodes. On the other hand, SPARQL – the standard query language for RDF – appears not to respect any of these premises. This may lead, in some cases, to unintuitive solutions.
Taking an example relating to (iii), the Wikidata knowledge-base uses existential blank nodes in RDF. For example, in the case of Nicole Brown Simpson, it is stated that she has a killer, but that the killer is unknown, encoded by the following triple with blank node _:b: (w:NicoleBrownSimpson; w:killedBy; _:b). Now consider the following SPARQL query over Wikidata (including this triple): SELECT * WHERE { ?person rdf:type w:Person .
MINUS { w:NicoleBrownSimpson w:killedBy ?person } } (1) The query will return the IRIs of all persons in Wikidata: the SPARQL engine will do a comparison to check if _:b = w:X – where w:X denotes each person – and will return false in every case since blank nodes in data act like constants. Semantically speaking however, the RDF graph does not provide any evidence that these people in the results are not the killer.
Leaving aside blank nodes, let’s turn to (i) and assume w:NicoleBrownSimpson has no w:killedBy edge. SPARQL will again return all people in the data based on the lack of existence of the edge in the data (effectively taking an implicit closed world assumption (CWA)). Conversely, the OWA semantics of RDF asserts that the relation may still hold even if the relevant triple is not given.
Likewise, with respect to (ii), the comparison w:x = w:y will always return false in SPARQL, whereas in the RDF graph, these may refer to the same thing: SPARQL sees unequal terms (effectively adopting a UNA) while in RDF, these terms may be referring to the same thing (no UNA).
There is another option, however: SPARQL could return answers only where it is certain that the person did not kill Nicole Brown Simpson. In other words, nobody would be returned for this query since anybody could have killed her. In the comparison _:b = w:X, we could say unknown instead of false to acknowledge that _:b could refer to w:X; this is similar to how SQL handles the case of nulls, using three-valued logic. Likewise, checking the (non-)existence of some relation not supported by the data could return unknown to align with RDF’s OWA; and so too could (in)equalities over IRIs, aligning with no-UNA.
In this paper, we do not develop new results, but rather position SPARQL
and RDF (with blank nodes) as a natural application of recent results in the
database literature relating to certain answers. Our proposed aim is to have a
keyword, such as SELECT CERTAIN [
While some authors have looked at certain answers for SPARQL in the context
of OWA [
Given two RDF graphs G and H, we say that G (simple) entails H, denoted
G j= H, if every model of G is a model of H; intuitively, H says nothing new over
G [
Example 1. Let us consider two RDF graphs, G on the left, H on the right, where b are blank nodes, and all other terms are IRIs.
w x b . w y b . w y z .
w x b1 . w y b2 . b3 y b2 .
In this case, G j= H with (b1) = b, (b2) = b, (b3) = w, (H)
Given a SPARQL query Q and two graphs G and H such that G H, it is often the case that (abusing notation) Q(G) 6$ Q(H). More generally, it does not hold that G j= H implies Q(H) ! Q(G) in SPARQL, even when considering just basic graph patterns (aka. conjunctive queries) with basic inequalities. SELECT * WHERE { ?w :x ?b1 ; y ?b2 . FILTER(?b1 != ?b2) } Under standard SPARQL query evaluation, Q(H) returns two results – (w,b1,b2) and (w,b2,b1) – whereas Q(G) is empty. Clearly Q(H) 6! Q(G). tu
SPARQL query evaluation is counter to the underlying RDF semantics: one can get more answers in SPARQL from an RDF graph with less information (in terms of entailment). Even if a query uses a feature like MINUS, the simple semantics of RDF adopts OWA, such that if G j= H, any information given by G that is not given by H is considered unknown, rather than false. We are thus interested in exploring an alternative semantics for SPARQL where we could guarantee, for example, that if G j= H, then Q(H) ! Q(G): that in some sense SPARQL answers are “monotonic” with respect to simple entailment in RDF. 3
An intuitive idea is to define the semantics of SPARQL with respect to all possible models of the RDF graph, where an answer is included in the result if and only if it is “valid” for all models. This idea corresponds closely with the notion of certain answers for incomplete databases.
More specifically, let C denote a set of constants and N a set of nulls where both sets are disjoint. Let us likewise assume, for simplicity, a single relation name R with arity k. An instance I of R is a k-ary relation RI Ck with only constants. A naive instance I of R is a k-ary relation RI (CN)k that may contain constants and nulls. Let : N ! C be a mapping from nulls to constants, and abusing notation, let (RI ) denote the image of RI under . A representative of a naive instance I is an instance I0 where (RI ) RI0 . Each representative fills in the incomplete information of I in a particular way. We denote the set of all representatives of I as rep(I).
Example 3. The following are instances of a relation R where numbers indicate constants and terms of the form ?i indicate a labelled null.
R 1 ?2 ?1 2 ?2 3
R In other words, a certain answer is an answer for all representatives.
Importantly, representatives in certain answers act somewhat like models
in simple entailment, leading to an interesting correspondence: an RDF graph
G j= H if and only if rep(G) rep(H) (assuming an intuitive encoding of G and
H as a ternary relation) [
To evaluate certain answers for SPARQL, we could apply recent results by
Libkin [
Example 5. Under Libkin’s proposal, for query (1) in the introduction, the w:killedBy pattern would be evaluated as unknown (with or without the triple mentioning _:b), which would lead to no results being returned as certain answers. In the case of Example 2, the inequality comparison would likewise return unknown, leading to certain(Q; H) returning no results.
Implementing and experimentally evaluating Libkin’s proposals [