We address the problem of encoding meta-modeling in realworld knowledge bases (KBs), i.e., multiple uses of names and especially non-standard uses of rdf : type, in DL-LiteR, and propose a sub-language of OWL 2 Full, called DL-Lite Full, for the web-scale Open Data for powerful meta-modeling. For meta-knowledge access, meta-queries are introduced by allowing variables to occur in the class and role positions of conjunctive queries. For scalability, based on the techniques of DLLiteR, we provide a way of reducing both satis ability checking and conjunctive query answering in DL-Lite Full to evaluating queries over the data layers of the KBs, and further an approach of answering metaqueries via meta-query rewriting and partial variable materialization. Based on these, we obtain that the considered reasoning tasks in DLLite Full still have PTime KB complexity and AC0 data complexity.
Description logics (DLs) [
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
Meta-modeling plays an import role in describing complex patterns and has
been heavily used in some actual open knowledge bases (KBs) such as the
commonsense KBs including SUMO [
High expressivity of OWL 2 Full leads to the undecidability of reasoning [
In order to capture the massive meta-modeling described in Open Data,
in this paper, we discuss encoding both multiple uses of ordinary names and
non-standard use of rdf : type in DL-LiteR (the language underling OWL 2 QL
and especially designed for ontology based data access [
Di erent from DL-LiteR, DL-Lite Full has only one name set N for classes, roles and individuals. This means that each name in N can be used as classes, roles and individuals simultaneously. In order to capture the non-standard uses of rdf : type, N contains a special name type. DL-Lite Full is de ned as follows. De nition 1 In DL-Lite Full, basic roles S, general roles R, basic classes B, and general classes C are de ned as follows:
S ::= P j P ; B ::= A j 9S;
R ::= S j :S; C ::= B j :B where A; P 2 N. A DL-Lite Full axiom takes the form of S vr R or B vc C, and a DL-Lite Full TBox T is a nite set of DL-Lite Full axioms where type does not occur in the left-hand sides of inclusion axioms (v). A DL-Lite Full individual assertion has the form P (a; b) or A(a), where P; a; b; A 2 N and P 6= type, and a DL-Lite Full ABox A is a nite set of individual assertions. A DL-Lite Full KB K = (T ; A) is a tuple of DL-Lite Full TBox T and ABox A.
DL-Lite Full does not separate the names for classes, roles and individuals.
Thus, we use vr and vc to distinguish between role inclusion axioms and class
inclusion axioms. Besides, type can be used as ordinary names to describe schema
knowledge. By this way, the speci cations of the RDF vocabulary term rdf : type
described in the real world KBs, such as sem : type vr type and sem : hasActor vr
sem : type, can be captured by DL-Lite Full. Here, type is forbidden to occur in
the left-hands of inclusion axioms, since reference [
Let V be a set of variables such that V \ N = ;. We de ne meta-queries. De nition 2 A query atom has the form x(y; z) or y(z), where x; y; z 2 N [ V and x 6= type. A meta-query (MQ) Q is an expression of the form 1 ^ ^ n ! q(x) where i are query atoms, x is a tuple of elements in V[N and each variable in x occurs in some i. We use body(Q) to denote the body Sin=1f ig of Q and head(Q) the head x of Q. Q is called a Boolean query if head(Q) = ().
Notice that query atoms in the form of type(x; y) can be captured by y(x). We call the variables occurring in the positions of the atoms (x; y) and (x) as role variables and class variables , respectively. Without class and role variables, meta-queries degrade into conjunctive queries (CQs). By allowing class and role variables in MQs, schema knowledge and data can be queried uniformly. Example 1 \Asking for the relationships that Lucy has" can be formally represented as the MQ: ?p(Lucy; ?x)^?c(?x) ! q(?p; ?x; ?c). 2.2
DL-Lite Full and MQs are captured by the -semantics de ned in [
-semantics. A -interpretation V = ( V ; V ; RV ; CV ) is a quadruple where V is a non-empty domain set, and V , RV and CV are functions such that V maps each n 2 N to a distinct element in V , RV maps each o 2 V to a subset of V V , CV maps each o 2 V to a subset of V , and RV (typeV ) = f(e; o)jo 2 V ^ e 2 CV (o)g holds. The interpretation of other elements is shown in Fig. 1.(a). -models, -satis ability and -entailment (j= ) are de ned as usual.
Syntax P P :S A 9S
Semantics Syntax Semantics RV (P V ) :B V CV (BV ) f(x; y)j(y; x) 2 RV (P V )g B vc C CV (BV ) CV (CV )
V V RV (SV ) S vr R RV (SV ) RV (RV ) CV (AV ) A(a) aV 2 CV (AV) fxj9y:(x; y) 2 RV (SV )g P (a; b) (aV ; bV ) 2 RV (P V )
(a) ( ) ( ) B v :9type Iz(B; x) ^ y(x) ! q() B v :9type Iz(B; x) ^ x(y) ! q() P v :type I(P; x; y)^y(x) ! q() P v :type I(P; x; y)^x(y) ! q() where x; y; z 2 V, and if B 2 N, Iz(B; x) = B(x); if B = 9P and P 2 N, Iz(B; x) = P (x; z); if B = 9P and P 2 N, Iz(B; x) = P (z; x); if S 2 N, I(S; x; y) = S(x; y); and if S = P and P 2 N, I(S; x; y) = P (y; x) (b)
In a -interpretation, each name is mapped to a domain element and each domain element has a class extension and a role extension, and the role extension of the interpretation of type captures the class extension of all domain elements.
For a tuple u, we use juj and u[i] to denote the length and the i-th element of u, respectively. For a query Q such that jhead(Q)j = j j u , we use Q[head(Q)=u], abbreviated as Q(u), to denote the result of replacing each occurrence of head(Q)[i] in Q with u[i] for 1 i juj.
Semantics of meta-queries. For a MQ Q and -interpretation V, a binding of Q over V is a function that maps each variable in Q to an element in V and each name a in Q to aV . We write V; j= Q if ( (y); (z)) 2 RV ( (x)) for each x(y; z) 2 body(Q) and (y) 2 CV ( (x)) for each x(y) 2 body(Q). For a DL-Lite Full KB K, a tuple u of names and with length jhead(Q)j, is called a certain answer of Q over K if for each -model V of K, there exists a binding of Q(u) over K such that V; j= Q(u) holds. We use ans (Q; K) to denote the set of all the certain answers of Q over K. Notice that u can be an empty tuple () in the case that Q is a Boolean query. In this situation, ans (Q; K) just contains empty tuple if Q is satis ed by every -model of K (Q is true over K). Overall Assumption. In the following, we just consider the KBs without the axioms containing :9type, :9type , :type and :type in the right-hand sides, since, as shown in the proposition below, reasoning with the KBs containing such axioms can be captured by reasoning with the KBs without such axioms via translating these axioms into MQs by function de ned in Fig.1.(b). Proposition 1 For DL-Lite Full KB K, let K0 be the KB obtained from K by dropping the axioms with :9type( ) or :type( ). Then (1) K is -satis able i K0 is satis able, and ans ( ( ); K0) = ; for each axiom in K with :9type( ) or :type( ); (2) if K is -satis able, ans (Q; K) = ans (Q; K0) for each MQ Q.
The proofs of this proposition and the results in the following sections are shown in the Appendix (https://github.com/Lucy321456/Files/blob/master/DL21.pdf). The motivation of making this assumption is to simplify the description of the provided method for reasoning with DL-Lite Full by rst discussing satis ability checking and CQ answering via CQ rewriting, and then based on the results, studying MQ answering via MQ rewriting. As shown in Fig.1, axioms with :9type (:type) actually correspond to MQs rather than CQs. 3
Here, we discuss satis ability checking and CQ answering in DL-Lite Full. In DLLiteR, the considered reasoning tasks can be eventually reduced to evaluating queries over the data layers of KBs. Thus the basic idea is to make use of the techniques especially designed for DL-LiteR. Before that we need to analyze the relationships between DL-Lite Full and DL-LiteR.
Relationships between DL-Lite Full and DL-LiteR
The work like [
r(P ) = vr(P ) r(P ) = vr(P ) r(:S) = :vr(S) c(A) = vc(A) c(9S) = 9 r(S)
c(:B) = : c(B) (B vc C) = c(B) v c(C) (S vr R) = r(S) v r(S)
(A(x)) = vc(A)(x) (P (x; y)) = vr(P )(x; y) (T ) = f ( )j 2 T g (A) = f ( )j 2 Ag (K) = ( (T ); (A)) (Q) = V ( ) ! q(x)
Let C and R be the sets of names for DL-LiteR classes and roles such that C, R and N are pairwise disjoint and have the same cardinality. For simplicity, we use N as the set for DL-LiteR individuals. Let vc and vr be two bijective functions that map each name a 2 N to a class name in C and a role name in R, respectively. The conversion of DL-Lite Full classes, roles, axioms, assertions, query atoms as well as DL-Lite Full KBs K = (T ; A) and CQs Q : V ! q(x) by functions c, r and via renaming is de ned in Figure 2.
In the following, for a DL-LiteR KB O and CQ q over O, we use ans(q; O) to denote the set of all certain answers of q over O. The next lemma shows that renaming can still guarantee the soundness of the considered reasoning tasks. Lemma 1 For a DL-Lite Full KB K, (1) if K is -satis able then (K) is satis able; and (2) ans( (Q); (K)) ans (Q; K) for each CQ Q.
However, unlike the existing work, even adopting UNA, completeness cannot be guaranteed, since non-standard uses of type may entail extra individual assertions which further have an impact on the considered reasoning tasks. Example 2 Consider the following DL-Lite Full KB K = (T ; A) where T = fP vr type; A vc 9type g and A = fP (a; B); A(C)g. K -entails B(a), and Q : C(x) ! q() is true over K, i.e., ans (Q; K) = f()g, since C is -entailed to have individuals. However, such conclusions are not implied by (K). Besides, if we add C vc :C to K, K is no longer -satis able, while (K) is still satis able.
In order to capture the extra conclusions entailed by non-standard uses of type, an intuitive way is to materialize such entailment to (K) by these 3 steps: Step 1. For each vr(type)(a; A) entailed by (K), add vc(A)(a) to (K); Step 2. For each 9vr(type) (A) entailed by (K), add vc(A)(o) to (K), where o 2 N is a fresh name not occurring in K; Step 3. For each B(A), B v 9S and S v vr(type) entailed by (K), add S(A; o) and vc(A)(o) to (A), where o is a fresh name not occurring in K and S(A; o) denotes P (A; o) if S = P and P (o; A) if S = P , where P 2 R. For distinction, we denote the KB obtained by Step 1-3 as m(K). Step 2 and 3 respectively capture the situation that K entails A having individuals and A and vr (P ) sharing some individuals. In the above procedure, we do not need to execute Step 2-3 again, since the fresh names o do not occur in K, thus even if o are entailed to have individuals, such knowledge does not a ect the results of satis ability checking and answering the queries solely containing names in K. Theorem 1 For a DL-Lite Full KB K = (T ; A), (1) K is -satis able i m(K) is satis able; and (2) for a CQ Q and tuple u such that juj = jhead(Q)j and solely contains names occurring in K, then u 2 ans (Q; K) i u 2 ans( (Q); (K)). 3.2
By Theorem 1, the intuitive way of realizing the reduction is to make use of the techniques for DL-LiteR via encoding the inclusion axioms into the queries. The di erence is that for completeness, extra encoding needs to be done to capture the non-standard use of type. For example, for an atom A(x) in a query Q, we not only need to use the axiom B vc A in the TBox to replace A(x) in Q with I(B; x) to generate a new query, but also take the axiom P vr type=type into consideration to further replace A(x) with I(P; x; A)/I(P; A; x) to capture the individuals of A implied by the axioms referring type, where I is a query atom generating function de ned in Fig.3. If x or A is a unbound variable (denoted as ), i.e., the variables not occurring in head(Q) and occurring only once in Q), B vc 9type or B vc 9type also needs to be taken into consideration.
I(B; x) = B(x), if B 2 N I(B; x) = P (x; ), if B = 9P; P 2 N I(B; x) = P ( ; x), if B = 9P ; P 2 N I(S; x; y) = P (x; y), if S = P; P 2 N I(S; x; y) = P (y; x), if S = P ; P 2 N U(x1(y1; z1); x2(y2; z2)) = x3(y3; z3) U(x1(y1); x2(y2)) = x3(y3) where for u 2 fx; y; zg, conditions (1)-(3) hold: (1) if u1 = then u3 = u2; (2) if u2 = then u3 = u1; (3) if u1 6= and u2 6= then u1 = u2 = u3 holds. otherwise U(x1(y1; z1); x2(y2; z2)) = and
U(x1(y1); x2(y2)) =
The concrete rewriting is shown in algorithm PerfectRef in Fig. 3, where the atom uni cation operator U is also de ned in Fig. 3. Before the rewriting, unbound variables in the query are replaced with \ '. The algorithm will also be used to rewrite MQs. Thus PerfectRef takes MQs as input (The x in line 5 and z in line 21 maybe variables. We will explain in the next section). For satis ability checking, the reduction is realized by rewriting the queries corresponding to the axioms with :, and then evaluate the nally obtained queries over the ABox of KB to check whether the KB implies knowledge that validates the negative axioms. The concrete way is shown in Algorithm Violates in Fig. 3. The termination of these two algorithms hold trivially, and the correctness can be guaranteed by the theorem below.
Theorem 2 For a DL-Lite Full KB K = (T ; A), (1) K is -satis able i ans (Q; (;; A)) = ; for each Q 2 Violates (T ); (2) if K is -satis able, then for each CQ Q, ans (Q; K) = SQ02PerfectRef (Q;T ) ans (Q0; (;; A)). Example 3 Consider the KB K = (T ; A) where T = f9P vc A; A vc 9type g and A = fP (B; a)g. For the CQ Q : B(?x) ! q(), by Algorithm 1, we can get PerfectRef (Q; T ) = fq1 : B( ) ! q(); q2 : A(B) ! q(); q3 : P (B; ) ! q()g. Obviously, ans (q3; A) = f()g. Then by Theorem 2, ans (Q; K) = f()g holds.
Based on Theorem 2 and the algorithms in Fig.3, we can further obtain the complexity of satis ability checking and CQ answering in DL-Lite Full. Theorem 3 For a DL-Lite Full KB K = (T ; A), -satis ability checking and CQ answering can be realized in PTime w.r.t. jT j and AC0 w.r.t. jAj. 4
In the following, for a function f , we use dom(f ) to denote the domain of f , Qf to denote the result of replacing each occurrence of a in Q with f (a) for each a 2 dom(f ), and [Qf ] to denote the query obtained by replacing each atom type(x; y) with y(x) with the motivation of unifying the format of queries. 4.1
For MQ answering, a direct way is to convert MQs into CQs by materializing
meta-variables [
Example 4 Consider the following DL-Lite Full KB K = (T ; A) where T = fA vc 9P; 9P vc 9S; P vr typeg and A = fA(a)g, and the query Q :?x(a) ^ S(?x; ?y) ! q(). Obviously, ans (Q; K) = f()g, i.e., Q is true over K, since there exist anonymous elements e and e0 such that e(a) and S(e; e0) are entailed by K. However, no matter what name occurring in K you replace ?x with, the resultant query always has an empty answer set over K.
Fortunately, such entailment can be captured by rewriting the query atoms ?x(y) based on the axioms referring type like P vr type (Line 10-17 in Algorithm 1) rather than doing materialization of ?x. Next, we formalize this approach. De nition 3 For a MQ Q and DL-Lite Full KB K, a MV-Binding = ( r; c) of Q over K is a function such that r maps each role variable of Q to type or a name occurring in K, and c maps some class variables of [Q r] to the names occurring in K. We use Q to denote [Q r] c, and use MVB(Q; K) to denote the set of all the MV-Bindings of Q over K.
In De nition 3, to capture the implied anonymous class elements, maps some class variables of Q to names, and let the reminder class atoms ?x(y) to be rewritten based on the axioms referring type. The way of reducing MQ answering to CQ evaluation over the ABoxes of KBs is shown in the theorem below. Theorem 4 For a v-satis able DL-Lite Full KB K = (T ; A), MQ Q and tuple u of names, then u 2 ans (Q; K) i there exist MV-Binding 2 MVB(Q; K) and CQ Q0 2 PerfectRef (Q ; T ) such that u 2 ans (Q0; (;; A)).
Note that in Theorem 4, the set S 2MVB(Q;K) PerfectRef (Q ; T ) may contain queries with class variables. However, just evaluating the CQs in the set over the ABox is enough to obtain all the certain answers of Q over K.
Example 5 Consider the MQ Q :?c(a)^?p(a; ?x) ! q(?c; ?p; ?x) and -satis able DL-Lite Full KB K = (fA1 vc A2g; fA1(a)g [ Sn i=1fPi(a; bi)g), where Pi 6= type for 1 i n. For Q, if ?p is bound to type then the resultant query has two class variables ?c and ?x, otherwise it has only one class variable ?c. Then:
MVB(Q; K) = So2NK ftypegf(f?p ! og; fg)g [ So2NK ftypeg Se2NK f(f?p ! og; f?c ! eg)g[ f(f?p ! typeg; fg)g [ So2NK f(f?p ! typeg; f?c ! og)gg[ So2NK f(f?p ! typeg; f?x ! og)g [ So2NK Se2NK f(f?p ! typeg; f?c ! o; ?x ! eg)g where NK consists of all the names in K. By trying all the MV-Bindings, we can get ans (Q; K) = Si2=1Sjn=1f(Ai; Pj; bj)g [ Si2=1Sj2=1f(Ai; type; Aj)g. tu
For completeness, not only the names occurring in the TBox but also thus solely occurring in the ABox need to be considered when materializing meta-variables. This makes a large number of candidates need to be tried when answering MQs. Besides, it will also violate the desire of the separation between TBox and ABox reasoning when answering MQs. Next based on two observations and Theorem 5, we provide a novel way of answering MQs via partial meta-variable materialization and MQ rewriting, where just the names in the TBox are referred.
The rst observation is that under -semantics, answering a MQ over a DLLite Full ABox can be realized by evaluating a CQ over a database without try any meta-variable materialization, shown in the lemma below. Lemma 2 For a MQ Q and DL-Lite Full ABox A, we use DB to denote the database fT (a; P; b)jP (a; b) 2 Ag [ fT (a; type; A)jA(a) 2 Ag and Q0 the query Vx(y;z)2body(Q) T (y; x; z) ^ Vx(y)2body(Q) T (y; type; x) ! q(head(Q)). Then ansv(Q; (;; A)) = ans(Q0; DB) holds.
The second observation is that when rewriting queries by the algorithm PerfectRef , if the names occurring in the class/role positions of query atoms do not occur in the right-hand sides of any inclusion axioms, then these query atoms will not be extended to generate new queries.
Enlightened by these, next, we provide the way of answering MQs via partial meta-variable materialization and MQ rewriting. For a DL-Lite Full TBox T , we use Nrc (resp. Nrr) to denote the set of all the names used as classes (resp.
T T roles) in the right-hand sides of the inclusion axioms in T . The way of partially materializing meta-variables of MQs is shown below.
De nition 4 For a MQ Q and DL-Lite Full TBox T , a partial MV-Binding # = (#r; #c) of Q over T is a function such that #r maps some role variables of Q to the names in Nrr
T [ ftypeg and #c maps some class variables of [Q#r] to the names in Nrc. And (fg; fg), i.e., without binding any role and class variable
T of Q, is also a partial MV-Binding of Q over T . We use PMVB(Q; T ) to denote the set of all the partial MV-bindings of Q over T .
Partial MV-Bindings materialize both class variables and role variables partially. The resultant MQs will be rewritten by the algorithm PerfectRef directly. In the rewriting procedure, role variables ?y in the atoms ?y(x; y) will be treated as names not occurring in the TBox, thus these atoms will not be extended to generate new queries (Line 31-52 of PerfectRef ). And class variables ?x in the atoms ?x(y) are also treated as names not occurring in the TBox, and these atoms will just be rewritten based on the axioms referring type, like P vr type (Line 5-30 of PerfectRef ).
Next, before giving the concrete way of answering MQs via partial metavariable materialization and MQ rewriting, we rst analyze the relationships between these two ways of materializing the meta-variables of MQs. De nition 5 For MQ Q, KB K = (T ; A) and partial MV-Binding # 2 PMVB(Q; T ), a MV-Binding 2 MVB(Q; K) is called an extension of # over K if for each reoalcehvcalraisasblveaxriaobfleQx,ifofxQ2,doifmx(#2)dtohmen(#)( xth)e=n#((xx))o=th#e(rxw)isoethe(rxw)i2=seNrTr(;xa)n2=dNfrTocr. We use ePMVB(#; Q; K) to denote the set of the extensions of # of Q over K.
Actually, extensions of partial MV-Binding # are the MV-Bindings obtained by mapping the remainder meta-variables, i.e., meta-variables of Q#, to the names not occurring in the right-hand sides of the inclusion axioms in T . Example 6 (Example 5 con't) # = (fg; f?c ! A2g) is a partial MV-Binding of Q over K's TBox, and ePMVB(#; Q; K) = [o2NK Nrr ftypegf(f?p ! og; f?c ! A2g)g is the set consisting of the MV-Bindings obtainedTby binding the remainder role variable ?p to the names in NK NrTr ftypeg.
By De nition 5, the lemma below indicates that (a) extensions of all the partial MV-Bindings can cover all the MV-Bindings; and (b) the certain answers obtained by trying all the extensions of a partial MV-Binding via MQ rewriting can be captured by answering a MQ through rewriting.
Lemma 3 For a MQ Q and DL-Lite Full KB K = (T ; A), we can get that MVB(Q; K) = S#2PMVB(Q;T ) ePMVB(#; Q; K), and for each # 2 PMVB(Q; T ): S 2ePMVB(#;Q;K) SQ02PerfectRef (Q ;T ) ans (Q0; (;; A))
SQ02PerfectRef (Q#;T )ans (Q0; (;; A)) ans (Q; K)
Combing Lemma 3 and Theorem 4, we can nally obtain the way of answering MQs via partial meta-variable materialization and meta-query rewriting. Theorem 5 For a MQ Q and -satis able DL-Lite Full KB K = (T ; A), then for a tuple u of names, u 2 ans (Q; K) i there exists # 2 PMVB(Q; T ) and Q0 2 PerfectRef (Q#; T ) such that u 2 ans (Q0; (;; A)) holds.
Example 7 (Example 5 cont'd) Nrr = ; and Nrc = fA2g. By De nition 4, Q
T T has totally the following 6 partial MV-Bindings over T : #1 = (fg; fg) #4 = (f?p ! typeg; f?c ! A2g) #2 = (fg; f?c ! A2g) #5 = (f?p ! typeg; f?x ! A2g) #3 = (f?p ! typeg; fg) #6 = (f?p ! typeg; f?c ! A2; ?x ! A2g) Then by Theorem 5, all the certain answers of Q over K can be obtained by evaluating over A the rewritten of the queries Q#1{Q#6 over T . Thus, through partial meta-variable materialization, we just need 6 times of query rewriting rather than 2 (2n + 3) + 2 (2n + 3)2 times (n is shown in Example 5).
KB Num C Num rC Num rC /Num C Num R Num rR Num rR=Num R BTC2012 531,637 92,495 17% 74,932 3,936 5%
DBpedia 225,416 19,269 8% 41,762 468 1%
Theorem 6 For DL-Lite Full KB K = (T ; A) and MQ Q, ans (Q; K) can be obtained in PTime w.r.t. jKj and AC0 w.r.t. jAj.
The work [26{32, 34{36] focused on extending multiple uses of names in
expressive DLs, such as SHOIN [
For light-weight DLs, [40{44] discuss extending DL-LiteR with multiple uses
of names and MQ answering. The main di erence between their work and ours
embodies in the following aspects. We study non-standard uses of rdf : type in
addition. As shown in Example 2 and 4, non-standard uses of rdf : type will enable
a KB to entail a class having extra named individuals or anonymous
individuals and individuals having anonymous classes, i.e., the classes entailed to exist.
This makes punning and full materialization of the meta-variables of MQs, i.e.,
translating MQs into CQs via replacing all meta-variables with names, cannot
guarantee the completeness of satis ability checking and MQ answering
anymore. Thus, we further provide the method for the considered reasoning tasks
via partial meta-variable materialization and MQ rewriting. Here, meta-variables
of MQs are partially materialized using the names occurring in the right-hand
sides of axioms. This can not only guarantee the completeness of the considered
reasoning tasks but also signi cantly reduce the number of queries needed to
be evaluated over the data layers of KBs. There just exists one work, i.e., [
We studied encoding multiple uses of names and non-standard uses of rdf : type,
in DL-LiteR, and proposed a sub-language of OWL 2 Full called DL-Lite Full.
This paper focuses on developing the theoretical aspects of DL-Lite Full for
the considered reasoning tasks. Future work will mainly focus on the following
aspects. Even with partial meta-variable materialization, answering a MQ over
a KB may still need to answer many MQs via MQ rewriting. Heuristics like the
ones in our previous work [
We thank the reviewers and program committee for their valuable comments and suggestions which will help us a lot to improve the whole work.