In this paper, we present a querying language for probabilistic RDF databases, where each triple has a probability, called pSRARQL, built on SPARQL, recommended by W3C as a querying language for RDF databases. Firstly, we present the syntax and semantics of pSPARQL. Secondly, we define the query problem of pSPARQL corresponding to probabilities of solutions. Finally, we show that the query evaluation of general pSPARQL patterns is PSPACEcomplete.
Resource Description Framework (RDF)5 is the standard data model in the
Semantic Web. In our real world, RDF data possibly contains some uncertainty
data due to the diversity of data sources such as YAGO6. For instance, some
RDF data is generated from raw data via knowledge extraction and machine
learning. However, RDF model itself provides little support for uncertain data
[
In this paper, we present an extended querying language (called pSPARQL: probabilistic SPARQL) for probabilistic RDF databases with supporting SPARQL. As an important result of this paper, we show that the query evaluation of general pSPARQL patterns is PSPACE-complete, which has the same complexity of SPARQL. ? Corresponding author: xiaowangzhang@tju.edu.cn 5 https://www.w3.org/TR/rdf11-primer/ 6 http://www.mpi-inf.mpg.de/yago./ 7 https://www.w3.org/TR/rdf-sparql-query/
Let I, B, and L be infinite sets of IRIs, blank nodes and literals, respectively. These three sets are pairwise disjoint. We denote the union I [ B [ L by U , and elements of I [ L will be referred to as constants.
A triple (s; p; o) 2 (I [ B) I (I [ B [ L) is called an RDF triple. An RDF graph is a finite set of RDF triples.
A probabilistic RDF R is a pair (G; ) where G is an RDF graph and is a total function from G ! [0; 1]. Intuitively speaking, is a probability function mapping each triple to a probability.
For instance, let R = (G; ) be a probabilistic RDF with G = ft1; t2; t3g and is a function from G ! [0; 1] defined in the following table.
No Triple t1 (John, sufferedFrom, Schizophrenia) 0.32 t2 (John, sufferedFrom, MentalDisorder) 0.84 t3 (John, Treatedby, Psychiatrist) 0.95 3
pSPARQL
In this section, we introduce a probabilistic SPARQL (for short, pSPARQL).
Patterns The syntax of pSPARQL is slightly different from the syntax of
SPARQL [
Assume furthermore an infinite countable set V of variables, disjoint from U . It is a SPARQL convention to prefix each variable with a question mark.
Patterns are now inductively defined as follows. – Any triple from (I [ L [ V ) (I [ V ) (I [ L [ V ) is a pattern (called a triple pattern. – If P1 and P2 are patterns, then so are the following: P1 UNION P2, P1 AND
P2, and P1 DIFF P2. – If P is a pattern and C is a constraint, then P FILTER C is a pattern. Here, a constraint is a boolean combination (C1 ^ C2, C1 _ C2, or :C) of atomic constraints with one of the three following forms: bound(?x), ?x =?y, and ?x = c with ?x; ?y 2 V and c 2 U .
Note that, in pSRARQL, we leave out the OPTIONAL operator while we add the DIFF operator in SPARQL 1.1. Indeed, the treatment is allowed since OPTIONAL can be expressed by AND, UNION, and DIFF as follows: P OPT Q = (P AND Q) UNION (P DIFF Q): (1) Semantics The semantics of pSPARQL patterns is defined in terms of sets of pairs of the form ( ; p) (called a solution) where is simply a total function : S ! U on some finite set S of variables and p 2 [0; 1]. We denote the domain S of by dom( ). Note that ( ; p) is meaningless if p = 0. For simplification, we mainly consider p 6= 0 in the following.
Now given an RDF graph R = (G; ) and a pattern P , we define the semantics of P on R, denoted by JP KR, as a set of mappings, in the following manner.
– If P is a triple pattern (v1; v2; v3), then
P R := f( ; p) : fv1; v2; v3g \ V ! U j J K
( (v1); (v2); (v3)) 2 G and p = max ( (v1); (v2); (v3))2G f (( (v1); (v2); (v3)))gg: Here, for any mapping and any constant c 2 I [ L, we agree that (c) equals c itself. In other words, mappings are extended to constants according to the identity mapping. – If P is of the form P1 UNION P2, then
P R := f( ; p) j ( ; p1) 2 JP1KR or ( ; p2) 2 JP2KR J K and p = maxfp1; p2gg: – If P is of the form P1 AND P2, then JP KR := JP1KR on JP2KR, where, for any two sets of solutions 1 and 2, we define 1 on = f( 1 [ 2; p) j ( 1; p1) 2 1; ( 2; p2) 2
2; 1 2 and p = p1 p2g: Here, two mappings 1 and 2 are called compatible, denoted by 1 2, if they agree on the intersection of their domains, i.e., if for every variable ?x 2 dom( 1) \ dom( 2), we have 1(?x) = 2(?x). And p is the product of p1 and p2. – If P is of the form P1 DIFF P2, then JP KR := JP1KR r JP2KR, where, for any two sets of mappings 1 and 2, we define 1 r 2 = f( 1; p) 2 1 j :9( 2; p2) 2 2 s.t.
1
2g:
– Finally, if P is of the form P1 FILTER C, then JP KG := f( ; p) 2 JP1KG j
(C) = trueg. Here, for any mapping and constraint C, the evaluation of
C on , denoted by (C), is defined as normal [
The following proposition shows that the semantics of pSPARQL is welldefined.
Proposition 1. For any pSPARQL pattern P , for any probabilistic RDF R, for any solutions ( ; p) 2 J K
P R, we have p 2 [0; 1]. 4
A basic SPARQL query is an expression of the form SELECTS (P ) where S is a finite set of variables and P is a pattern. Semantically, given an RDF graph G, we define JSELECTS (P )KG = f( jdom( )\S ; p) j ( ; p) 2 JP KGg, where we use the common notation f jX for the restriction of a function f to a subset X of its domain.
Given a probabilistic RDF R, a pSPARQL pattern P , a mapping , a probability p 2 [0; 1], the query evaluation problem is to determine whether there exists some probability p0 2 [0; 1] with p0 p such that ( ; p0) 2 J K
P R.
Proposition 2. The query evaluation of general pSPARQL patterns is PSPACEcomplete.
This work is supported by the program of Applied Mathematics Discipline of Shanghai Polytechnic University (XXKPY1604) and the open funding project of Key Laboratory of Computer Network and Information Integration (Southeast University), Ministry of Education.