RDF data is often treated as incomplete, following the OpenWorld Assumption. On the other hand, SPARQL, the standard query language over RDF, usually follows the Closed-World Assumption, assuming 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.
Due to its open and incremental nature, data on the Semantic Web is
generally incomplete. This can be formalized using the Open-World Assumption
(OWA)[
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 [
In this paper, we discuss how to assess the relationship between certain answers, possible answers and the results retrieved by SPARQL queries in the presence of completeness statements. 2
SPARQL Queries. A basic graph pattern (BGP) is a set of triple patterns [
JP + AND :P1 AND : : : AND :PnKG = f j 2 JP +KG ^ 8i : J (Pi)KG = ; g 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 nite 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(P1jP2) 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 [
Completeness statements restrict the set of interpretations: De nition 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 i (G; G0) j= 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 De nition 2 (Certain and Possible Answers with Completeness Statements). Let Q be a query, G be a graph and C be a set of completeness statements. Then the certain and possible answers of Q over G w.r.t. C are CAQ(G) = TG02int(G;C)JQKG0 and PACQ(G) = SG02int(G;C)JQKG0 , respectively. C If C is empty, then PAQ(G) and CAQ(G) correspond to the classical certain and
C C
possible answers [
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 [
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 de ne 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.
De nition 3 (Crucial Statements). For a query Q = (W; P ), the positive crucial statement of Q, denoted as CQ+, is the statement Compl(P +jtrue). The set of negative crucial statements of Q, denoted as CQ , is the set f Compl(P1jP +); : : : ; Compl(PnjP +) g, 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 results. Theorem 1 (Bounded Possible Answers). Let C be a set of completeness statements and Q be a positive query. Then
C j= CQ+ implies for all graphs G, PAQ(G) = CAQ(G) (= JQKG):
C C While the equality JQKG = CACQ(G) always holds, the new insight is that JQKG = PAQ(G). This means the query results cannot miss any information w.r.t. reality.
C Theorem 2 (Queries with Negation). Let C be a set of completeness statements and Q be a query. Then 1. C j= CQ implies for all graphs G, CACQ(G) = QKG; 2. C j= CQ+ ^ CQ implies for all graphs G, PACQ(GJ) = CACQ(G) = JQKG.
The rst item means that if C j= CQ , then every answer returned by the query
is a certain answer. The second item means that if additionally C j= 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 [