=Paper=
{{Paper
|id=None
|storemode=property
|title=Bridging the Semantic Gap between RDF and SPARQL Using Completeness Statements
|pdfUrl=https://ceur-ws.org/Vol-1272/paper_50.pdf
|volume=Vol-1272
|dblpUrl=https://dblp.org/rec/conf/semweb/DarariRN14
}}
==Bridging the Semantic Gap between RDF and SPARQL Using Completeness Statements==
https://ceur-ws.org/Vol-1272/paper_50.pdf
Bridging the Semantic Gap between RDF and
SPARQL using Completeness Statements
Fariz Darari, Simon Razniewski, and Werner Nutt
Faculty of Computer Science, Free University of Bozen-Bolzano, Italy
fariz.darari@stud-inf.unibz.it,{razniewski,nutt}@inf.unibz.it
Abstract. RDF data is often treated as incomplete, following the Open-
World Assumption. On the other hand, SPARQL, the standard query
language over RDF, usually follows the Closed-World Assumption, as-
suming RDF data to be complete. This gives rise to a semantic gap
between RDF and SPARQL. In this paper, we address how to close the
semantic gap between RDF and SPARQL in terms of certain answers
and possible answers using completeness statements.
Keywords: SPARQL, RDF, data completeness, OWA, CWA
1 Introduction
Due to its open and incremental nature, data on the Semantic Web is gen-
erally incomplete. This can be formalized using the Open-World Assumption
(OWA)[1]. SPARQL, on the other hand, interprets RDF data under closed-
world semantics. While for positive queries, this does not create problems [2],
SPARQL queries with negation make only sense under closed-world semantics.
This ambiguous interpretation of RDF data poses the question how to determine
which semantics is appropriate in a given situation.
As a particular example, suppose we want to retrieve all Oscar winners that
have tattoos. For obvious reasons, no sources on the Semantic Web contain
complete information about this topic and hence the Open-World Assumption
applies. On the other hand, suppose we want to retrieve all Oscar winners. Here,
an RDF version of IMDb1 would contain complete data and hence one may
intuitively apply closed-world reasoning.
In [3], completeness statements were introduced, which are metadata that
allow one to specify that the CWA applies to parts of a data source. We argue
that these statements can be used to understand the meaning of query results
in terms of certain and possible answers [4], which is especially interesting for
queries with negation: Suppose an RDF data source has the completeness state-
ment “complete for all Oscar winners”. The result of a SPARQL query for Oscar
winners contains not only all certain but also all possible answers. The result
of a SPARQL query for Oscar winners with tattoos contains only all certain
1
http://www.imdb.com/oscars/
2 Fariz Darari, Simon Razniewski, and Werner Nutt
answers. Moreover, the result of a SPARQL query for people with tattoos that
did not win an Oscar contains all certain answers, but not all possible answers.
The result of a SPARQL query for Oscar winners not having tattoos contains
all possible answers but none of the answers is certain.
In this paper, we discuss how to assess the relationship between certain an-
swers, possible answers and the results retrieved by SPARQL queries in the
presence of completeness statements.
2 Formalization
SPARQL Queries. A basic graph pattern (BGP) is a set of triple patterns [5].
In this work, we do not consider blank nodes. We define a graph pattern induc-
tively as follows: (1) a BGP P is a graph pattern; (2) for a BGP P , a NOT-EXISTS
pattern ¬P is a graph pattern; (3) for graph patterns P1 and P2 , P1 AND P2 is a
graph pattern. Any graph pattern P can be equivalently written as a conjunction
of a BGP (called the positive part and denoted as P + ) and several NOT-EXISTS
patterns { ¬P1 , . . . , ¬Pn } (referred to as the negative part and denoted as P − ).
A query with negation has the form Q = (W, P ) where P is a graph pattern and
W ⊆ var (P + ) is the set of distinguished variables. The evaluation of a graph
pattern P over a graph G is defined in [5]:
JP + AND ¬P1 AND . . . AND ¬Pn KG = { µ | µ ∈ JP + KG ∧ ∀i . Jµ(Pi )KG = ∅ }
The result of evaluating (W, P ) over a graph G is the restriction of JP KG to W .
This fragment of SPARQL queries is safe, that is, for a query with negation Q
and a graph G, the evaluation JQKG returns finite answers. We assume all queries
to be consistent, that is, there is a graph G where JQKG 6= ∅.
Completeness Statements. Formally, a completeness statement C is of the
form Compl(P1 |P2 ) where P1 , called the pattern, and P2 , called the condition,
are BGPs. Intuitively, such a statement expresses that the source contains all
instantiations of P1 that satisfy condition P2 (e.g., all Golden Globe winners
that won an Oscar).
In line with the Open-World Assumption of RDF, for a graph G, we call any
graph G0 such that G0 ⊇ G an interpretation of G [2]. We associate to a complete-
ness statement C the CONSTRUCT query QC = (CONSTRUCT { P1 } { P1 AND P2 }). A
pair (G, G0 ) of a graph and one of its interpretations satisfies a completeness
statement C, written (G, G0 ) |= C if JQC KG0 ⊆ G holds. It satisfies a set C of
completeness statements, written (G, G0 ) |= C if it satisfies every element in C. A
set of completeness statements C entails a statement C, written C |= C, if for all
pairs (G, G0 ) of a graph G and an interpretation G0 of G such that (G, G0 ) |= C,
it is the case that (G, G0 ) |= C.
Completeness statements restrict the set of interpretations:
Definition 1 (Valid Interpretation with Completeness Statements). Let
G be a graph and C be a set of completeness statements. An interpretation G0 ⊇ G
is valid w.r.t. C iff (G, G0 ) |= C. We write the set of all valid interpretations of
G w.r.t. C as int(G, C).
Bridging the Semantic Gap between RDF and SPARQL 3
Definition 2 (Certain and Possible Answers with Completeness State-
ments). Let Q be a query, G be a graph and C be a set of completeness state-
ments. Then the certain and possible answers of Q over G w.r.t. C are CAQ
C (G) =
T Q S
G0 ∈int(G,C) JQKG and PAC (G) = G0 ∈int(G,C) JQKG , respectively.
0 0
If C is empty, then PAQ Q
C (G) and CAC (G) correspond to the classical certain and
possible answers [4]. With completeness statements, some query results may
correspond to the certain and possible answers while others may not.
Example 1 (Possible Answers). Consider again the query asking for people that
have tattoos. Since this is private information we have no knowledge how com-
plete our data source is, and hence the set of possible answers is (nearly) infinite:
Anyone not explicitly stated to have tattoos might still have tattoos.
On the other hand, consider the query for people who won an Oscar. It is
relatively easy for a data source to be complete on this topic, by comparing:
e.g., to the Internet Movie Database (IMDb). If a data source is complete for all
Oscar winners, then there are no further possible answers.
The reasoning for queries with negation is more complex. By [2], under the OWA,
for a monotonic query Q and a graph G the certain answers are JQKG , while
for queries with negation, the certain answers are empty. With completeness
statements, the certain answers of a query with negation can be non-empty.
Example 2 (Certain Answers). Consider first a query for people that won an
Oscar but no Golden Globe. If a data source is complete both for Oscar winners
and Golden Globe winners, then the query result contains all possible and all
certain answers.
On the other hand, a query for people with tattoos that did not win an Oscar
would only return certain answers, but not all possible answers, because there
are probably many more people with tattoos that did not win an Oscar.
The result of a query for people that won an Oscar and do not have tattoos
contains all possible answers but no certain answers, because we do not know
for certain which Oscar winners have tattoos and which do not.
We next define for each query some completeness statements that allow one to
capture the crucial information for getting certain or possible answers. Knowing
about the crucial statements helps in data acquisition identify which data is
needed in order to achieve desired answer semantics.
Definition 3 (Crucial Statements). For a query Q = (W, P ), the positive
+
crucial statement of Q, denoted as CQ , is the statement Compl(P + |true). The
−
set of negative crucial statements of Q, denoted as CQ , is the set { Compl(P1 |P + ),
. . . , Compl(Pn |P ) }, where P1 , . . . , Pn are from the negative part P − of Q.
+
The next theorems show that the crucial statements can be used to infer
relationships between certain answers, possible answers and SPARQL query re-
sults.
4 Fariz Darari, Simon Razniewski, and Werner Nutt
Theorem 1 (Bounded Possible Answers). Let C be a set of completeness
statements and Q be a positive query. Then
+
C |= CQ implies for all graphs G, PAQ Q
C (G) = CAC (G) (= JQKG ).
While the equality JQKG = CAQC (G) always holds, the new insight is that JQKG =
Q
PAC (G). This means the query results cannot miss any information w.r.t. reality.
Theorem 2 (Queries with Negation). Let C be a set of completeness state-
ments and Q be a query. Then
−
1. C |= CQ implies for all graphs G, CAQ C (G) = JQKG ;
+ −
2. C |= CQ ∧ CQ implies for all graphs G, PAQ Q
C (G) = CAC (G) = JQKG .
−
The first item means that if C |= CQ , then every answer returned by the query
+
is a certain answer. The second item means that if additionally C |= CQ , then
there also cannot be any other possible answers than those returned by JQKG .
The completeness statement entailment problems can be solved using standard
query containment techniques [6].
3 Discussion
We have shown that in the presence of completeness statements, the semantics
of SPARQL may correspond to the certain answer or possible answer semantics.
Our work is based on the observation that parts of data on the Semantic Web are
actually complete. In future research, we would like to consider explicit negative
RDF knowledge and completeness statements over it as an alternative for getting
certain and possible answers. In this work, we assume all information contained
in a graph is correct. An interesting case is when this assumption does not hold
in general. We would like to investigate correctness statements as the dual of
completeness statements. A further study is also needed for an effective way
of maintenance of completeness statements to cope with information changes.
One possible way is to add timestamps to completeness statements. An extended
version with proofs of this paper is available at http://arxiv.org/abs/1408.6395.
References
1. Raymond Reiter. On Closed World Data Bases. 1977.
2. Marcelo Arenas and Jorge Pérez. Querying Semantic Web Data with SPARQL. In
PODS, 2011.
3. Fariz Darari, Werner Nutt, Giuseppe Pirrò, and Simon Razniewski. Completeness
Statements about RDF Data Sources and Their Use for Query Answering. In ISWC
2013, pages 66–83. Springer Berlin Heidelberg, 2013.
4. Serge Abiteboul, Paris C. Kanellakis, and Gösta Grahne. On the Representation
and Querying of Sets of Possible Worlds. Theor. Comput. Sci., 78(1):158–187, 1991.
5. Steve Harris and Andy Seaborne. SPARQL 1.1 Query Language. Technical report,
W3C, 2013.
6. Simon Razniewski and Werner Nutt. Completeness of Queries over Incomplete
Databases. PVLDB, 4(11):749–760, 2011.