Handling uncertain knowledge - like information extracted from unstructured text, with some probability of being correct - is crucial for modeling many real world domains. Ontologies and ontology-based data access (OBDA) have proven to be versatile methods to capture this knowledge. Multiple systems for OBDA have been developed and there is theoretical work towards probabilistic OBDA, namely identifying efficiently processable (safe) queries. However, there is no analysis on the safeness of probabilistic queries in real-world applications, or in other words the feasibility of fulfilling users' information needs over probabilistic data. In this paper we investigate queries collected from several public SPARQL endpoints and determine the distribution of safe and unsafe queries. This analysis shows that many queries in practice are safe, making probabilistic OBDA feasible and practical to fulfill real-world users' information needs.
Ontology-based Data Access (ODBA) has received a lot of attention in the Semantic
Web Community. In particular, results on light-weight description logics that allow
efficient reasoning and query answering provide new possibilities for using ontologies in
data access. One approach for ontology-based data access is to rewrite a given query
based on the background ontology in such a way that the resulting – more complex –
query can directly be executed on a relational database. This is possible for different
light-weight ontology languages, in particular the DL-Lite family [
At the same time, many applications in particular on the (Semantic) Web have to deal with uncertainty in the data. Examples are large-scale information extraction from text or the integration of heterogeneous information sources. To cope with uncertainty, the database community has investigated probabilistic databases where each tuple in the database is associated with a probability indicating the belief in the truth of the respective statement. Querying a probabilistic database requires not only to retrieve tuples that match the query, but also to compute a correct probability for each answer. Research in probabilistic databases has shown that there is a strict dichotomy of safe (data complexity in PTIME) and unsafe (in #P-hard) queries [15].
The goal of our work is to develop data access methods that can use background knowledge in terms of a light-weight ontology and also deal with uncertainty in the data. A promising idea for efficiently computing probabilistic query answers is to use existing approaches for OBDA based on query rewriting and pose the resulting query against a probabilistic database that computes answers with associated probabilities.
Jung et al. have shown that query rewriting for OBDA can directly be lifted to
the probabilistic case [
In this paper we address the question of how real-world queries, and consequently
users’ information needs, are distributed concerning query safeness. Therefore, we
analyze the queries contained in the Linked SPARQL Queries Dataset (LSQ) [
The paper is structured as follows: In Section 2 we give the definition of extensional query processing and query safeness for probabilistic queries and the application to OBDA. The dataset and the analysis and its results are described in Section 3. In Section 4 we briefly discuss some related work analyzing SPARQL queries. We conclude and give directions for future work in Section 5. 2
In this section we briefly introduce DL-Lite, the description logic underlying the OWL
2 QL profile. Next, we detail how the distribution semantics for probabilistic description
logics [
DL-LiteR and the Distribution Semantics
In DL-LiteR concepts and roles are formed in the following syntax [
C ! B j :B E ! R j :R where A denotes an atomic concept, P an atomic role, and P the inverse of the atomic role P . B denotes a basic concept, i.e. either an atomic concept or a concept of the form 9R, where R denotes a basic role, that is, either an atomic role or the inverse of an atomic role. C denotes a general concept, which can be a basic concept or its negation, and E denotes a general role, which can be a basic role or its negation.
A DL-LiteR knowledge base (KB) K = hT ; Ai models a domain in terms of a TBox T and an ABox A. A TBox is formed by a finite set of inclusion assertions of the form B v C or R v E. An ABox is formed by a finite set of membership assertions on atomic concepts and on atomic roles, of the form A(a) or P (a; b) stating respectively that the object denoted by the constant a is an instance of A and that the pair of objects denoted by the pair of constants (a; b) is an instance of the role P .
The semantics of a DL is as an interpretation I = ( I ; I ), consisting of a nonempty interpretation domain I and an interpretation function I that assigns to each concept C a subset CI of I , and to each role R a binary relation RI over I : AI P I
I I
I (P )I = f(o2; o1)j(o1; o2) 2 P I g (9R)I = fo j 9o0.(o; o0) 2 RI g (:B)I = (:R)I =
I n BI I
I n RI
An interpretation I is a model of C1 v C2, where C1,C2 are general concepts if C1I C2I . Similarly, I is a model of E1 v E2, where E1, E2 are general roles if E1I E2I .
To specify the semantics of membership assertions, the interpretation function is extended to constants, by assigning to each constant a a distinct object aI 2 I . This enforces the unique name assumption on constants. An interpretation I is a model of a membership assertion A(a) (resp., P (a; b)), if aI 2 AI (resp., (aI ; bI ) 2 P I ).
Given an assertion and an interpretation I, I denotes the fact that I is a model of . Given a (finite) set of assertions , I denotes the fact that I is a model of every assertion in . A model of a KB K = hT ; Ai is an interpretation I such that I T and I A. A KB is satisfiable if it has at least one model. A KB K logically implies an assertion , written K , if all models of K are also models of . Similarly, a TBox T logically implies an assertion , written T , if all models of T are also models of .
A TIP-OWL (tuple-independent OWL) knowledge base T KB = hT ; A; P i consists
of a DL-LiteR T-Box T , an ABox A, and a probability distribution P : A ! [0; 1].
Abusing terminology, we say that KB T KB if they have the same T-Box and the
ABox of KB is a subset of the A-Box of T KB. We adopt the independent tuple semantics
in the spirit of the probabilistic semantics for logic programs proposed in [
0 a02A0
Y a2AnA0
1 P (a)A
Based on this semantics, we can now define the probability of existential queries over TIP-OWL knowledge bases as follows. First, the probability of a query over a possible knowledge base is one if the query follows from the knowledge base and zero otherwise:
P (QjKB) = 1 KB j= Q 0 otherwise
Taking the probability of possible knowledge bases into account, the probability of an existential query over a possible knowledge base becomes the product of the probability of that possible knowledge base and the probability of the query given that knowledge base. By summing up these probabilities over all possible knowledge bases, we get the following probability for existential queries over TIP-OWL knowledge bases:
X
KB T KB P (QjT BK) =
P (QjKB) P (KBjT KB)
This defines a complete probabilistic semantics for TIP-OWL knowledge bases and
queries.
2.2 Implementing Reasoning on Top of Probabilistic Databases
In this section, we first briefly recall the idea of first-order rewritability of queries in
DL-Lite and then show that the query rewriting approach proposed by [
Query Rewriting Query processing in DL-LiteR is based on the idea of first-order reducibility. This means that for every conjunctive query q we can find a query q0 that produces the same answers as q by just looking at the A-Box. Calvanese et al. also define a rewriting algorithm that computes a q0 for every q by applying transformations that depend on the T-Box axioms.
Given a consistent T-Box T the algorithm takes a conjunctive query q0 and expands it into a union of conjunctive queries U starting with U = fq0g. The algorithm successively extends U by applying the following rule:
U = U [ fq[l=r(l; I)]g where q is a query in U , l is a literal in q, I is an inclusion axiom from T and r is a replacement function that is defined as follows: l
I r(l; I) l
I A(x) A0 v A A0(x) A(x) 9P v A P (x; ) A(x) 9P v A P ( ; x) P (x; ) A v 9P A(x) P (x; ) 9P 0 v 9P P 0(x; ) P (x; ) 9P 0 v 9P P 0( ; x)
P ( ; x) A v 9P P ( ; x) 9P 0 v P P ( ; x) 9P 0 v 9P P (x; y) P 0 v P P (x; y) P 0 v P P (x; y) P 0 v P P (x; y) P 0 v P r(l; I) Here ’ ’ denotes an unbound variable, i.e., a variable that does not occur in any other literal of any of the queries.
Definition 2 (Derived Query). Let Q = L1 ^ ^ Lm be a conjunctive query over a DL-Lite terminology. We write Q !r Q0 if Q0 = Q _ Q[Li=r(Li; I)] for some literal Li from Q. Let !r denote the transitive closure of !r, then we call every Q0 with Q !r Q0 a derived query of Q. Q0 is called maximal if there is no Q00 such that Q !r Q00 and Q0 !r Q00.
Using the notion of a maximal derived query, we can establish the FOL-reducibility
of DL-Lite by rephrasing the corresponding theorem from [
Theorem 1 (FOL-Reducibility of DL-Lite (from [
Correctness of Query Processing Implementing TIP-OWL on top of probabilistic databases can now be done in the following way. The A-Box is stored in the probabilistic database. It is easy to see that the probabilistic semantics of TIP-OWL A-Boxes and tuple independent databases coincide. What remains to be done is to show that the idea of FOL-reducibility carries over to our probabilistic model. In particular, we have to show that a rewritten query has the same probability given a knowledge base with empty T-Box as the original query given a complete knowledge base. This result is established in the following corollary.
Corollary 1. Let T KB = hT ; A; Pi be a TIP-OWL knowledge base and T KB0 = h;; A; Pi the same knowledge base, but with an empty T-Box. Let further Q be a conjunctive query and Q0 a union of conjunctive queries obtained by rewriting Q on the basis of T , then
P (QjT KB) = P (Q0jT KB0)
We can easily see that the semantics of queries over a TIP-OWL A-Box with empty T-Box directly corresponds to the tuple-independence semantics used in probabilistic databases [15], thus queries posed to correctly constructed probabilistic database have the same probability as a TIP-OWL query with empty T-Box. From theorem 1 we get, that P (QjKB) does not change as T ; A j= Q if and only if A j= Q0. Further, as P (KBjT KB) only depends on A this part also stays unchanged.
Over the past decade, the database community has developed efficient methods for querying uncertain information in probabilistic databases. Important results are the introduction of the independent tuple model for probabilistic data as well as a complete characterization of queries that can be computed in polynomial time. We briefly review these results in this section. 2.3
Extensional Query Processing It has been shown that the key to efficient query processing in probabilistic databases is to avoid the computation of complex event descriptions and to directly compute the probability of a complex query from the probabilities of subqueries. This approach, referred to as extensional query processing, has been shown to correctly compute the probability of queries for the class of tractable queries using the following recursive algorithm:
Symbol components are defined as follows [15]: Let Q = d1 ^ : : : ^ dk be a UCQ in CNF, and K1; : : : ; Km the connected components for the set of queries fd1; : : : ; dkg. The symbol-components of Q are Q1 = Vi2K1 di, . . . , Qm = Vi2Km di. Then the probability P (Q) = P (Q1) : : : P (Qm). If m = 1, then Q is symbol-connected.
Each recursion of the algorithm processes a simpler subexpression, until the probability of an individual can be read directly from the database. Queries that can be completely processed using the steps above are called safe. It has been shown that safe queries exactly correspond to queries that can be computed in PTIME whereas queries that cannot be completely processed using these steps – in particular queries for which we cannot find a separator variable in line 19 – are in #P-hard. This means that we can use the notion of safeness and the processing steps above to analyze the general complexity of certain classes of queries.
Definition 3 (Safeness). A query Q is called safe if and only if it can be computed by iteratively applying Algorithm 1.
Theorem 2 (Dichotomy Theorem (adapted from [15])). The probability of safe queries can be computed in PTIME. If a query is not safe computing its probability is in #Phard.
Jung et al. proved that Theorem 2 also holds for probabilistic OBDA in OWL 2
QL [
Analysis of the SPARQL Dataset and Query Safeness
For our analysis we used the queries collected in the Linked SPARQL Queries Dataset
(LSQ) [
Table 1 shows the different query types and their distribution in the different datasets. Those numbers contain only queries that parse successfully; LSQ also lists queries with parse errors. They clearly show that the main amount of queries are SELECT queries. Interestingly, the dataset for the British Museum’s endpoint only consists of SELECT queries; all being uniformly structured. This implies that those are not actual user queries but automatically created ones of some system. However, the queries from the British Museum make up only a small part of the whole LSQ dataset. @ 1 http://dbpedia.org/ 2 http://linkedgeodata.org/ 3 http://data.semanticweb.org/ 4 http://bm.rkbexplorer.com
Looking at the used SPARQL features, FILTER and DISTINCT are the most prominent, with UNION coming in second. GROUP BY and EXISTS play only a minor role. However, note that DISTINCT is technically a GROUP BY over all variables in the SELECT clause.
The focus of our analysis is on SELECT and ASK queries. For DESCRIBE queries there is no formal definition of how a result is produced, thus making it impossible to determine if the process is safe; whereas CONSTRUCT queries do not directly translate to query answering as it generates a new graph and not a result set. Furthermore, our current implementation cannot analyze queries containing features, like GROUP BY, DISTINCT, EXISTS, OPTIONAL, and endpoint specific functions not part of the SPARQL recommendation (e.g. Oracle’s version of COUNT). After removing those we are left with 507 241 queries for which we can determine query safeness.
We used parts of Ontop [
The distribution of safe and unsafe queries is shown in Table 3. With 99.68%, almost all of the analyzed queries are safe. Regarding the total number of 1 194 424 queries, 42.33% are definitly safe. Note that this does not imply that 57.67% of the queries are unsafe. Those queries need a more thorough analysis because of their usage of DISTINCT/GROUP BY, FILTER, HAVING, EXISTS, or OPTIONAL.
Looking at the numbers for the different data sources, the percent of unsafe queries sent to the Semantic Web Dog Food endpoint is significantly higher than for the other two. Analyzing those queries we found the major number being of the form SELECT ?targetType WHERE f ?obj a <someURI>. ?obj <someOtherURI> ?targetObj. ?targetObj a ?targetType.g. This suggest that those query are generate by some tool and not by a user. Overall, this shows that the users’ general information needs can also be satisfied over probabilistic data in a tractable way.
Our implementation of the algorithm is still quite simple and we are not able to simplify all queries. Thus determining their safeness becomes sometimes unfeasible. This results in a timeout for 69 queries after 10 minutes. Overall, the average processing time for a query is 86ms. There is some other work analyzing the characteristics of deterministic SPARQL queries from different sources. To the best of our knowledge, there is no analysis of the safeness of real-world SPARQL queries for probabilistic data.
In [
Arias et al. [
Han et al. [
In this paper we analyzed half a million queries from the LSQ dataset; those which can directly be translate to (union of) conjunctive queries. Checking for probabilistic query safeness we found nearly all queries to be safe and thus tractable when processed over probabilistic data. Relating to the whole set of queries, about half of them are safe; for the other half there is no information in our analysis. This shows that the general information needs a user of the public SPARQL endpoints serving as sources for the LSQ dataset has are also feasible to be fulfilled on uncertain data. Note that there is no uncertain version of those dataset. However, we argue that the users’ information needs would not change over uncertain data, and that it is possible to create such a version of DBpedia, e.g. by incorporating information about trustworthiness in general or knowledge about how commonly a certain property is accurately extracted. To the best of our knowledge this is the first work that analyzes real-world SPARQL queries in the light of probabilistic data.
For future work, we have two different directions. First, we want to further study queries using constructs like DISTINCT/GROUP BY or OPTIONAL and how they influence query safeness. Second, considering unsafe queries, we want to analyze their structure and investigate ways of handling those effectively, e.g. through approximation or simplification similarly to approaches present in probabilistic databases. SUM 2015, Que´bec City, QC, Canada, September 16-18, 2015. Proceedings, pp. 106—120. Springer International Publishing, Cham (2015), http://dx.doi.org/10.1007/978-3-31923540-0 8 15. Suciu, D., Olteanu, D., Re´, C., Koch, C.: Probabilistic Databases. Morgan & Claypool Publishers (2011)