Problem Description. Although the sheer size of the open datasets [2] in Linked Open Data (LOD) [3] can be viewed as a positive sign for Semantic Web initiatives, it causes performance bottlenecks for systems and tools that provide data managing and query answering services over the LOD datasets. Moreover, as the growth of the schema knowledge described by OWL, realizing e cient reasoning and expressive query answering has become a challenging task for both data publishers and end users. Most of the studies in this respect (for example, [4{6]) focused on dealing with the scalability issue whereas inferring knowledge through reasoning is often ignored. Moreover, when reasoning is considered, most of the time only lightweight RDFS reasoning can be supported. Proposal of DL-LiteA. Motivated by a statistic analysis of the BTC 2012 dataset3, we propose to use DL-LiteA [10] techniques to reason and query the web-scale open datasets (knowledge bases) described by Semantic Web standards like RDF and OWL due to the low reasoning complexity and suitable expressivity of the language. The distinguished feature of DL-LiteA is FOL-rewritability. This means that in DL-LiteA, by schema knowledge reasoning, both satis ability checking and conjunctive query (CQ) answering can be eventually reduced to answering queries over the data layers of the corresponding knowledge bases (KBs). Moreover the separation between schema knowledge and data layer reasoning makes it possible to use highly optimized database management systems and engines in practice for query answering. Bottleneck of DL-LiteA. Unfortunately, even with low reasoning complexity, when facing the real-life scalability challenge, the actual reasoning and CQ answering realized by DL-LiteA may become infeasible by the following two factors. Firstly, for both satis ability checking and CQ answering, a polynomial size of queries may need to be answered over the data layers of the corresponding KBs w.r.t. the size of the schema knowledge of these KBs. Secondly, for the KBs with massive individual assertions, evaluating a single query over the data layers may be highly time-consuming. The combination of these two factors makes 3 https://km.aifb.kit.edu/projects/btc-2012/
the situation even worse, calling for new techniques for DL-LiteA to tackle the scalability and e ciency challenge.
Our Solution{Divide-and-Conquer. In computer science, divide-and-conquer is the basis of e cient algorithms for all kinds of problems. This impels us to seek for a divide-and-conquer reasoning and query answering approach for DLLiteA, with the basic idea of partitioning both KBs and CQs into smaller chunks and decomposing the original reasoning and query answering tasks into a group of independent sub-tasks such that the overall performance can be improved by taking advantage of the parallelization and distribution techniques.
The challenge for designing such an approach lies in how to carry out KB and CQ partitioning and reasoning reduction in a sound and complete way. Motivated by hash partitioning of RDF graphs (the partitions with the local feature of star-query answering) [15], we expect the smaller KB chunks to have the local feature for both satis ability checking and simple-query answering. Here simple-queries (SQs) are the CQs whose query atoms share a common variable or individual. For CQ answering, we expect to partition a CQ into smaller SQs and evaluate them over smaller KB chunks.
Under these expectations, our divide-and-conquer approach is constructed from both theoretical and practical perspectives. Theoretically, de nitions of KB partitions and CQ partitions are presented and the su cient and necessary conditions are identi ed to determine whether a KB partition holds the desired features and whether a CQ can be answered in the desired way. Practically, based on the theoretical results, the concrete ways of partitioning KBs and CQs and evaluating CQ partitions over KB partitions are described. Moreover, a strategy of optimizing the procedure of evaluating CQ partitions over KB partitions is provided to improve the overall query answering performance. To verify our proposal and approach, experiments are conducted on two web-scale open datasets, i.e., DBpedia and BTC 2012 dataset, and the testing results indicate that the proposed approach opens new possibilities for realizing performance-critical applications on the Web with both expressivity and high scalability.
To the best of our knowledge, this is the rst study on partitioning DL-LiteA KBs and CQs for the purpose of e ciently reasoning with and querying largescale datasets. We assume that the readers are familiar with DL-LiteA and CQs. Next, we illustrate our main scienti c contributions, containing KB partitioning, query partitioning, optimization and experiments. The technique details can be seen in [1]. In this paper, for a CQ Q and DL-LiteA KB K, we use Ans(Q; K) to denote the set of all the certain answers of Q over K. Moreover, we use Hd(Q) and Bd(Q) to denote the head and body of Q, respectively. For two tuples x and u with the same dimension, we use [x=u] to denote a substitution. 2
DL-LiteA KB partitioning Here, we discuss partitioning DL-LiteA KBs into small chunks with the desired feature, containing the formalization of KB partitions, the conditions of detecting the desired KB partitions and the concrete way of computing such KB partitions. Formalizing KB partitions. Before de ning DL-LiteA KB partitions, we rst provide a way of computing a smaller sub-TBox for a given sub-ABox. Procedure 1. For a DL-LiteA KB (T ; A) and sub-ABox A0 A, we use T jA0 to denote a sub-TBox of T constructed by the steps 1{2. Let T jA0 = ;. Then: Step 1. For each 2 T , add to T jA0 if has the form v : or Fun(S) and each name in occurs in (T jA0 ; A0), or has the form v and the name in occurs in (T jA0 ; A0); Step 2. Iterate Step 1, until T jA0 do not change anymore.
Since for a sub-ABox, not all the axioms are relevant in terms of satis
ability checking and CQ answering, and smaller TBoxes can make the considered
reasoning tasks be realized more quickly. The correctness is shown below:
Lemma 1. For a DL-LiteA KB (T ; A) and A0 A, (
By Lemma 1, partitions of DL-LiteA KBs are de ned in the de nition below.
n
De nition 1. For DL-LiteA KB K = (T ; A), the set S = [i=1f(Ti; Ai)g of
DLn
LiteA KBs is called a partition of K if A = [i=1Ai and Ti = T jAi . S is called a
SCSQA-local partition of K i (
Lemma 2. For a DL-LiteA KB K = (T ; A), (
All the query atoms in a SQ share a common individual or variable. Therefore, by Lemma 2, we can get that in the scenario of KB partitioning, for the local feature of satis ability checking and SQ answering, the assertions in the original KB and sharing a common individual should be put in an identical sub-KB. Proposition 1. For DL-LiteA KB K = (T ; A) and partition S of K, if for each U A satisfying that all the assertions in U share a common individual, there exists (T 0; A0) 2 S such that U A0, then S is a SCSQA-local partition of K.
Without redundant individual assertions [1] (Theorem 1), the condition in Proposition 1 can be used as a necessary and su cient condition. Computing SCSQA-local partitions. By Proposition 1, SCSQA-local partitions of DL-LiteA KBs can be obtained by the following procedure. Procedure 2. For a DL-LiteA KB K = (T ; A), a SCSQA-local partition S of K can be obtained by the following steps 1{2: Step 1. Compute a partition A1; ; An of A by the following two sub-steps a{b: a. Compute the set U = fUaja 2 Ig where I is the set of all the individuals of
A, and Ua is the set consisting of all the assertions in A that contain a. b. Compute a partition U1; ; Un of U. For each Ui, let Ai = [e2Ui e. n Step 2. For each 1 i n, compute the TBox T jAi for Ai. Let S = [i=1f(T jAi ; Ai)g.
Di erent ways of partitioning U in step 1.b lead to di erent SCSQA-local partitions of K. In terms of distribution and parallelization, the partitions generating more balanced, smaller sized sub-ABoxes are more likely to achieve the e ciency improvement. For a given size asize of ABoxes in KB partition, a partition of U generating sub-ABoxes sized no more than asize can be obtained by: b1. Compute an ordered tuple O = U1; ; Um of the elements in U such that jUij jUi+1j for 1 i m 1; b2. Continue the following procedure P, until O does not contain any element.
P. Generate a sub-ABox A0. Let A0 = ;. For i from jOj to 1, if jA0 [ O[i]j asize then let A0 = A0 [ O[i]; otherwise for j from 1 to i 1, if jA0 [ O[j]j asize then let A0 = A0 [O[j], otherwise break the rst loop. Remove all the elements used to generate A0 from O.
The complexity of computing SCSQA-local partitions of DL-LiteA KBs is shown below. Low complexity makes the proposed approach appealing for partitioning a large-scale KB into smaller, independent sub-KBs with the desired local feature. Theorem 1. For a KB K = (T ; A), a SCSQA-local partition of K can be computed in O(jT j2) w.r.t. jT j and in O(jAj) w.r.t. jAj. 3
Here, we discuss CQ partitioning and evaluation, containing the formalization of CQ partitions, the conditions of detecting CQ partitions and the concrete way of computing and evaluating CQ partitions.
Formalizing CQ partitions. CQ partitions are de ned in the de nition below.
n
De nition 2. For a CQ Q, we say the set Q = [i=1fqig of CQs is a partition
of Q if (
The concrete way of merging the certain answers of the sub-queries and the correctness are shown in the following de nition and lemma, respectively.
n De nition 3. For a partition Q = [i=1fqig of a CQ Q and a partition S of a DL-LiteA KB K, we de ne:
Ans(Q; Q; S) = fx[x1=u1; ; xn=un]j(u1; ; un) 2 1 ng where x = Hd(Q), for each 1 i n, xi = Hd(qi) and i = [K02S Ans(qi; K0), and for each 1 i; j n, 1 k juij and 1 l juj j, if xi[k] = xj [l] then ui[k] = uj [l]. Lemma 3. Ans(Q; Q; S)
Ans(Q; K) holds.
By the semantics of CQs, we know that distinguished (dist.) variables and non-dist. variables of CQs [1] are interpreted in di erent ways. Based on this, we de ne the concept of SQ-reducibility and show that SQ-reducible CQs can be answered in the descried way, i.e., by rst partitioning CQs into SQs and then answering the smaller SQs over SCSQA-local partitions of DL-LiteA KBs. De nition 4. For a CQ Q, we say Q is SQ-reducible i it has a SQ-partition Q such that Hd(q) Q for each q 2 Q. Lemma 4. For a CQ Q, if Q is SQ-reducible then there exists a SQ-partition Q of Q such that for each satis able DL-LiteA KB K and each SQSQA-local partition S of K, Ans(Q; K) = Ans(Q; Q; S) holds.
Detecting SQ-reducible CQs. Not all CQs are SQ-reducible. This means that there exist CQs Q and DL-LiteA KBs K such that evaluating any SQ-partition of Q over any SCSQA-local partition of K cannot obtain all the certain answers of Q over K. Thus in order to evaluate as many CQs in the desired way as possible, we need to provide a i condition to decide whether a CQ is SQ-reducible. Theorem 2. A CQ Q is SQ-reducible i there do not exist three query atoms P (?x; ?y), and 0 in Q such that ?x and ?y are non-dist. variables of Q, contains ?x but not ?y, and 0 contains ?y but not ?x.
Theorem 3. Detecting whether a CQ Q is SQ-reducible can be done in O(jQj).
Next, we present the concrete ways of partitioning and evaluating SQ-reducible CQs and non-SQ-reducible CQs.
Partitioning and evaluating SQ-reducible CQs. A SQ-reducible CQ may have many SQ-partitions, so we need to rst detect the SQ-partitions that can capture all the certain answers of CQs and then provide the procedure of computing the desired SQ-partitions and the complexity of computing such partitions. Theorem 4. For a SQ-reducible CQ Q, let Q be any SQ-partition of Q such that Hd(q) Hd(Q) for each q 2 Q. Then Ans(Q; K) = Ans(Q; Q; S) holds, for any satis able DL-LiteA KB K and any SCSQA-local partition S of K. Procedure 3. For a SQ-reducible CQ Q, a SQ-partition Q of Q satisfying that Hd(q) Hd(Q) for each q 2 Q can be obtained by the following steps 1{2. Step 1. Let A = Bd(Q) and U = ;. Compute a partition U of Bd(Q) by the steps a-b. a. For each non-dist. variable x of Q, compute the set Ux consisting of all the atoms in A that contain x, and let U = U [ fUxg and A = A Ux. Then for every two di erent non-dist. variables x and y of Q that occur in a same atom in Q, replace Ux and Uy in U with Ux [ Uy; b. For each dist. variable or individual x of Q, compute the set Ux consisting of all the atoms in A that contain x, and let U = U [ fUxg and A = A Ux. Step 2. For U 2 U, generate a CQ q such that Bd(q) = U and Hd(q) consists of all the variables occurring in U that also occur in Hd(Q) or Bd(Q) U, add q to Q. Theorem 5. For a SQ-reducible CQ Q, a partition Q of Q satisfying hd(q) hd(Q) for each q 2 Q can be obtained in O(jQj).
Partitioning and evaluating non-SQ-reducible CQs. If a CQ is not SQreducible, then non-SQ-partitions need to be evaluated to obtain all the certain answers of this CQ. By the semantics of CQs, we nd that if a certain answer of a CQ Q over a KB is obtained by binding some non-dist. variables NV to anonymous elements, then in the scenario of KB and query partitioning, this certain answer can solely be obtained by evaluating a partition of Q in which the sub-queries do not contain the variables in NV as dist. variables. The de nition below illustrates the partitions that can capture such certain answers of Q.
De nition 5. For a CQ Q and set NV of non-dist. variables of Q, we use QjSNQV
to denote a partition of Q satisfying that (
The concrete way of answering non-SQ-reducible CQs and the procedure of computing the desired partitions as well as the complexity are shown below. Theorem 6. Given a non-SQ-reducible CQ Q, for any satis able DL-LiteA KB K and any SCSQA-local partition S of K, Ans(Q; K) = [NV'22NV Ans(Q; QjSNQV'; S) holds where NV is the set consisting of all the non-dist. variables of Q. Procedure 5. For a non-SQ-reducible CQ Q and set NV of some non-dist. variables of Q, the partition QjSNQV, can be obtained by the following two steps: Step 1. Let A = Bd(Q) and U = ;. Compute a partition U of Bd(Q) by the steps a{c. a. Compute an undirected graph G with node set A. For each ( ; 0) 2 (A)2, there exists an edge between and 0 i they share a variable in NV; b. For each connected component l of G, generate an atom set U consisting of all the nodes in l, and set U = U [ fUg and A = A U; c. For each variable or individual x occurring in A, compute a set U consisting of all the atoms in A that contain x, and set U = U [ fUg and A = A U. Step 2. For each U 2 U, generate a CQ q so that Bd(q) = U and Hd(q) consists of all the variables in U that also occur in Hd(Q) or Bd(Q) U, and add q to Q. Theorem 7. The complexity of computing the partition QjSNQV of Q is O(jQj2). 4
Although query partitioning can reduce the nal number of queries needed to be answered over the ABox of a KB signi cantly, a large amount of intermediate results generated by answering sub-queries may also slow down the overall query answering procedure. Thus we further provide an optimization strategy to reduce the intermediate results as many and as early as possible by transferring values between sub-queries, as shown in the following example and proposition. Example 1. Let S be a partition of a KB. Consider the partition Q of a CQ Q:
Q : R(a; ?x) ^ P (?x; ?y) ^ S(?y; ?z) ! q(?x; ?y; ?z)
Q = fq1 : R(a; ?x) ^ P (?x; ?y) ! q(?x; ?y); q2 : S(?y; ?z) ! q(?y; ?z)g After answering q1 over the KBs in S, suppose we obtain the answer set = 3 [i=1f(ai; bi)g. If we transfer the bindings of ?y to q2 before it is evaluated, i.e., 3 replacing answering q2 with answering the CQs [i=1fS(bi; ?z) ! q(bi; ?z)g, then we can avoid computing the answers of q2 which do not bind ?y to b1, b2 or b3.
n Proposition 2. For a partition Q = [i=1fqig of a CQ Q and a partition S of a satis able DL-LiteA KB, the following equation holds:
Ans(Q; Q; S) = fx[x1=u1; where x = Hd(Q), for 1 i
; xn=un]j(u1; ; un) 2 1jB1 n, xi = Hd(qi), B1 = ; and for 1 < k Bk = f[x1=u1; ; xk 1=uk 1]jxk j(u1; ; uk 1) 2 1jB1 njBn g n: k 1jBk 1 g where 1jB1 = [K2S Ans(q1; K) and for 1 < j n, j jBj = [K2S [ 2Bj Ans(qj ; K).
In Proposition 2, Bk denotes the set of the bindings of some variables of qk obtained from the certain answers of the sub-queries evaluated before qk. By observing the CQ rewriting procedure in DL-LiteA, we nd that the transferred variable bindings do not a ect the query rewriting procedure. This means that when answering a sub-query q over a sub-KB K = (T ; A) with a set B of variable bindings, the CQs obtained by rst transferring the bindings in B to q and then rewriting the resultant queries over T are equivalent to the CQs obtained by rst rewriting q over T and then transferring the bindings in B to the rewritten queries. Thus we actually need one time of query rewriting rather than jBj. Hence the procedure of evaluating the partitions of queries can be further optimized. Proposition 3. For a CQ q, satis able DL-LiteA KB K = (T ; A) and set B of functions that maps some variables of q to names, then we can get that: [ 2BPerfectRef(q ; T ) = [ 2Bfq0 jq0 2 PerfectRef(q; T )g
[ 2BAns(q ; K) = [q02PerfectRef(q;T ) [ 2B Ans(q0 ; (;; A)) where PerfectRef denotes one classical query rewriting algorithm in DL-LiteA.
Experiments presented in the subsequent section demonstrate that the value transferring strategy can signi cantly improve the query answering performance. 5
In order to demonstrate the e ciency and rationality of our approach and proposal, we have implemented a prototype system, where multi-thread techniques are adopted to check the satis ability of and answer a single query over the subKBs in a KB partition in a parallel way. We run the system on two web-scale, real-world datasets, i.e., DBpedia 200 dataset extended with DBpedia ontology and BTC 2012 dataset. Next, we present the main results of the experiments. SCSQA-local partition computation. After materializing the name equivalence relations, two DL-LiteA KBs Kdbp and Kbtc are constructed, respectively with 233,227 axioms and 0.2 billion individual assertions and 339,519 axioms and 1.04 billion individual assertions. We randomly choose two numbers, 28 million and 52 million, to respectively limit the size of the sub-ABoxes in KB partitions. Then, a SCSQA-local partition Sdbp of Kdbp with 14 sub-KBs and a SCSQA-local partition Sbtc of Kbtc with 30 sub-KBs are computed by Procedure 2. Satis ability checking. Without KB partition, checking the satis ability of Kdbp totally cost 6 minutes, and for Kbtc, after 6 hours an out-of-memory error was reported caused by the failure in completing generating the queries needed to be evaluated over its ABox. However, facilitated by KB partitioning equipped with parallelization, satis ability checking of Kdbp and Kbtc has been successfully done in 0.07 and 0.15 minutes, respectively. The testing results indicate that KB partitioning equipped with parallelization can signi cantly improve the performance of checking the satis ability of web-scale DL-LiteA KBs. Query answering checking. In order to detect the e ect of KB and query partitioning as well as sub-query value transfer on the performance of CQ answering, we design 14 CQs (8 SQs and 6 non-SQs) for Kdbp and Kbtc, respectively.
The SQ answering results indicate that no matter a SQ has a large or small
number of rewritten queries over the original KB or it can be evaluated e ciently
or ine ciently, in the situation of KB partitioning equipped with parallelization,
this SQ can be answered in an extremely e cient way. On the other hand, the
results of evaluating the tested non-SQ queries indicate that: (
Compared with the works on querying LOD [4{9], our approach pursues both expressivity and scalability, capturing more schema knowledge and handling more expressive queries with the support of DL-LiteA techniques. For scalability, we provide a divide-and-conquer reasoning and query answering approach for DL-LiteA so that the massive knowledge in LOD can be managed by parallel and distribution techniques.
Compared with the works on DL KB modularity [12{14], we study a tractable language DL-LiteA, and concentrate on satis ability checking and CQ answering rather than entailment checking. Moreover, we provide a way of ABox partitioning with linear data complexity where reasoning is not necessary. Compared with the works on RDF graph partitioning [15{17], we consider RDF graphs as DL-LiteA KBs so that constraints in these graphs can be captured. Compared with the works on query rewriting optimization [18{21], our approach features query rewriting optimization in DL-LiteA from the distinctive perspective of query and KB partitioning, and the experiments on real-world datasets show that the number of rewritten queries can be signi cantly reduced. Compared with the works [22,23] on fast satis ability checking, we propose to improve the performance in DL-LiteA from the perspective of KB partitioning. Experiments on web-scale datasets demonstrate the e ciency of our approach. Acknowledgments. This work has been supported by the National Key Research and Development Program of China under grants 2017YFC1700300 and 2017YFB1002300.