DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling Zhenzhen Gu1 and Songmao Zhang2 1 Faculty of Computer Science, Free University of Bozen-Bolzano, Bolzano, Italy 2 Academy of Mathematics and Systems Sciences, Chinese Academy of Sciences, Beijing, China zhgu@unibz.it, smzhang@math.ac.cn Abstract. We address the problem of encoding meta-modeling in real- world 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 DL- LiteR , we provide a way of reducing both satisfiability 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 meta- queries via meta-query rewriting and partial variable materialization. Based on these, we obtain that the considered reasoning tasks in DL- Lite Full still have PTime KB complexity and AC0 data complexity. Keywords: Semantic Web · DL-LiteR · OWL 2 Full · Meta-modeling. 1 Introduction Description logics (DLs) [5], decidable sub-languages of the first-order logic, lay the logic foundation of the famous and popular web ontology language OWL. The latest version OWL 2 [12, 24] includes two expressive sub-languages OWL 2 DL and OWL 2 Full as well as three profiles OWL 2 QL, OWL 2 EL and OWL 2 RL for scalability at different aspects. OWL 2 DL is formalized based on the expressive DL SROIQ [38] and OWL 2 QL, OWL 2 EL and OWL 2 RL are underlined by the lightweight DLs DL-LiteR [6, 7], EL [9] and DLP [10] respectively. OWL 2 Full is obtained by removing the restrictions for decidability. The distinctive feature of OWL 2 Full is meta-modeling where ordinary names can be used in multiple ways, such as asserting Mother to be a class and at the same time to be an individual of family roles. Besides, RDF(S)/OWL vocabulary terms which correspond to logic constructors can also be used as ordinary names to describe data and knowledge, such as asserting sem : type and sem : subTypeOf to be a sub-property of rdfs : type and rdfs : subClassOf, respectively. Copyright c 2021 for this paper by its authors. Use permitted under Creative Com- mons License Attribution 4.0 International (CC BY 4.0). 2 Zhenzhen Gu and Songmao Zhang 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 com- monsense KBs including SUMO [17] for the top-level concepts and OpenCyc [18] for across-domain knowledge, and the life sciences KBs [19] like FMA [20]. This can be seen from the statistics in our previous work [31]. Besides, some large scale Open Data [1, 2, 4] also contain massive meta-modeling, like the Billion Triple Challenge (BTC) data set [21], where among the names used as classes, 25.5% are also specified as individuals, and among the names used as roles, 8.7% are individuals at the same time. And some terms like moive : film cut are used as classes, roles and individuals simultaneously. High expressivity of OWL 2 Full leads to the undecidability of reasoning [26], making complete reasoning impossible and developing practical systems difficult. In order to cater for the requirement of meta-modeling, OWL 2 DL provides a technique called punning which syntactically allows names to have multiple uses while semantically treats the multiple uses of names as different semantic entities. As a syntactical solution, punning will not draw any extra conclusions compared with OWL 2 DL. Besides punning, there already exist some works [26–32, 34–36, 39–43] studying extending DLs like SROIQ and DL-LiteR with meta-modeling by allowing names to have multiple uses. However, in all these work, except [39] which investigates extending meta-modeling with instantiation in SROIQ and SHOIQ, non-standard uses of RDF(S)/OWL vocabulary terms have been ignored. Although, compared with multiple uses of ordinary names, non-standard uses of RDF(S)/OWL vocabulary terms relatively less happen, as declared in [45], it nonetheless can be useful, such as distinguishing different kinds of instantiations. 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 [6, 11]), and provide a sub-language of OWL 2 Full called DL-Lite Full. Non-standard uses of other RDF(S)/OWL vocabulary terms will be discussed in the future work. For meta- knowledge accessing, meta-queries are introduced by allowing variables to occur in the class and role positions of queries. We define the syntax and semantics of DL-Lite Full and meta-queries. For data layer scalability, we provide the way of reducing satisfiability checking and conjunctive query answering in DL-Lite Full to evaluate queries over the data layer of KBs and further the way of answering meta-queries through meta-query rewriting and partial variable materialization. Based on this, we obtain that the considered reasoning tasks in DL-Lite Full still have AC0 data complexity and PTime KB complexity. 2 The definition of DL-Lite Full and meta-queries 2.1 The syntax of DL-Lite Full and meta-queries Different 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 DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 3 and individuals simultaneously. In order to capture the non-standard uses of rdf : type, N contains a special name type. DL-Lite Full is defined as follows. Definition 1 In DL-Lite Full, basic roles S, general roles R, basic classes B, and general classes C are defined as follows: S ::= P | P − , B ::= A | ∃S, R ::= S | ¬S, C ::= B | ¬B where A, P ∈ 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 finite 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 ∈ N and P 6= type, and a DL-Lite Full ABox A is a finite 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 specifications 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 [22] has suggested that such kinds of axioms are generally best left to philosophers. As a matter of fact, we did not find such use of type in the actual KBs. Moreover, we emphasize that individual assertions with the form type(a, b) can be captured by b(a). Let V be a set of variables such that V ∩ N = ∅. We define meta-queries. Definition 2 A query atom has the form x(y, z) or y(z), where x, y, z ∈ 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 Snand each variable in x occurs in some αi . We use body(Q) to denote the body i=1 {αi } 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 rep- resented as the MQ: ?p(Lucy, ?x)∧?c(?x) → q(?p, ?x, ?c). 2.2 The semantics of DL-Lite Full and meta-queries DL-Lite Full and MQs are captured by the ν-semantics defined in [26] which is based on HiLog and takes a similar way of OWL 2 RDF-Based semantics to 4 Zhenzhen Gu and Songmao Zhang interpret the multiple uses of names. Here, the ν-semantics is extended based on OWL 2 RDF-Based semantics to capture the non-standard use of type. ν-semantics. A ν-interpretation V = (∆V , ·V , RV , C V ) is a quadruple where ∆V is a non-empty domain set, and ·V , RV and C V are functions such that ·V maps each n ∈ N to a distinct element in ∆V , RV maps each o ∈ ∆V to a subset of ∆V × ∆V , C V maps each o ∈ ∆V to a subset of ∆V , and RV (typeV ) = {(e, o)|o ∈ ∆V ∧ e ∈ C V (o)} holds. The interpretation of other elements is shown in Fig. 1.(a). ν-models, ν-satisfiability and ν-entailment (|=ν ) are defined as usual. Syntax Semantics Syntax Semantics P RV (P V ) ¬B ∆V − C V (B V ) P− {(x, y)|(y, x) ∈ RV (P V )} B vc C C V (B V ) ⊆ C V (C V ) ¬S ∆V × ∆V − RV (S V ) S vr R RV (S V ) ⊆ RV (RV ) A C V (AV ) A(a) aV ∈ C V (AV) ∃S {x|∃y.(x, y) ∈ RV (S V )} P (a, b) (aV , bV ) ∈ RV (P V ) (a) α δ(α) α δ(α) B v ¬∃type Iz (B, x) ∧ y(x) → q() B v ¬∃type− 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 ∈ V, and if B ∈ N, Iz (B, x) = B(x); if B = ∃P and P ∈ N, Iz (B, x) = P (x, z); if B = ∃P − and P ∈ N, Iz (B, x) = P (z, x); if S ∈ N, I(S, x, y) = S(x, y); and if S = P − and P ∈ N, I(S, x, y) = P (y, x) (b) Fig. 1. (a) Interpretation of DL-Lite Full elements w.r.t. a ν-interpretation V, (b) translation of disjoint axioms to MQs. 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 |u| and u[i] to denote the length and the i-th el- ement of u, respectively. For a query Q such that |head(Q)| = |u|, we use Q[head(Q)/u], abbreviated as Q(u), to denote the result of replacing each oc- currence of head(Q)[i] in Q with u[i] for 1 ≤ i ≤ |u|. 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, π |=ν Q if (π(y), π(z)) ∈ RV (π(x)) for each x(y, z) ∈ body(Q) and π(y) ∈ C V (π(x)) for each x(y) ∈ body(Q). For a DL-Lite Full KB K, a tuple u of names and with length |head(Q)|, 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, π |=ν 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 satisfied by every ν-model of K (Q is true over K). DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 5 Overall Assumption. In the following, we just consider the KBs without the axioms containing ¬∃type, ¬∃type− , ¬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 δ defined 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 ¬∃type(− ) or ¬type(− ). Then (1) K is ν-satisfiable iff K0 is satisfiable, and ansν (δ(α), K0 ) = ∅ for each axiom α in K with ¬∃type(− ) or ¬type(− ); (2) if K is ν-satisfiable, 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 first discussing satisfia- bility 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 ¬∃type (¬type) actually correspond to MQs rather than CQs. 3 Satisfiability checking and conjunctive query answering Here, we discuss satisfiability checking and CQ answering in DL-Lite Full. In DL- LiteR , 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 . 3.1 Relationships between DL-Lite Full and DL-LiteR The work like [26, 29, 40] conclude that under unique name assumption (UNA), meta-modeling, i.e., multiple uses of names, can be handled by OWL 2 Punning via renaming. However, this does not hold anymore in DL-Lite Full due to the presence of type in the TBox. Next, let’s first see the translation by renaming. τr (P ) = vr (P ) τc (¬B) = ¬τc (B) τ (T ) = {τ (α)|α ∈ T } τr (P − ) = vr (P )− τ (B vc C) = τc (B) v τc (C) τ (A) = {τ (α)|α ∈ A} τr (¬S) = ¬vr (S) τ (S vr R) = τr (S) v τr (S) τ (K) = (τ V (T ), τ (A)) τc (A) = vc (A) τ (A(x)) = vc (A)(x) τ (Q) = τ (α) → q(x) τc (∃S) = ∃τr (S) τ (P (x, y)) = vr (P )(x, y) Fig. 2. Definition of the translation functions, where A, P ∈ N, P 6= type, x, y ∈ N ∪ V. 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 6 Zhenzhen Gu and Songmao Zhang functions that map each name a ∈ N to a class name in C and a role name in R, respectively. The conversion of DL-Lite Full classes, roles, axioms,Vassertions, query atoms as well as DL-Lite Full KBs K = (T , A) and CQs Q : α → q(x) by functions τc , τr and τ via renaming is defined 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 ν-satisfiable then τ (K) is satisfiable; and (2) ans(τ (Q), τ (K)) ⊆ ansν (Q, K) for each CQ Q. However, unlike the existing work, even adopting UNA, completeness can- not 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 = {P vr type, A vc ∃type− } and A = {P (a, B), A(C)}. K ν-entails B(a), and Q : C(x) → q() is true over K, i.e., ansν (Q, K) = {()}, 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 ν-satisfiable, while τ (K) is still satisfiable. 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 ∃vr (type)− (A) entailed by τ (K), add vc (A)(o) to τ (K), where o ∈ N is a fresh name not occurring in K; Step 3. For each B(A), B v ∃S 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 ∈ 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 affect the results of satisfiability checking and answering the queries solely containing names in K. Theorem 1 For a DL-Lite Full KB K = (T , A), (1) K is ν-satisfiable iff τ m (K) is satisfiable; and (2) for a CQ Q and tuple u such that |u| = |head(Q)| and solely contains names occurring in K, then u ∈ ansν (Q, K) iff u ∈ ans(τ (Q), τ (K)). 3.2 Reasoning via query rewriting 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 difference is that for completeness, extra encoding needs to be done to capture DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 7 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 defined 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 ∃type or B vc ∃type− also needs to be taken into consideration. I(B, x) = B(x), if B ∈ N I(B, x) = P (x, −), if B = ∃P, P ∈ N I(B, x) = P (−, x), if B = ∃P − , P ∈ N I(S, x, y) = P (x, y), if S = P, P ∈ N I(S, x, y) = P (y, x), if S = P − , P ∈ N U(x1 (y1 , z1 ), x2 (y2 , z2 )) = x3 (y3 , z3 ) U(x1 (y1 ), x2 (y2 )) = x3 (y3 ) where for u ∈ {x, y, z}, 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 )) = − Fig. 3. The algorithm PerfectRef ν and Violatesν . The concrete rewriting is shown in algorithm PerfectRef ν in Fig. 3, where the atom unification operator U is also defined 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 8 Zhenzhen Gu and Songmao Zhang 5 and z in line 21 maybe variables. We will explain in the next section). For satisfiability checking, the reduction is realized by rewriting the queries corre- sponding to the axioms with ¬, and then evaluate the finally 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 ν-satisfiable iff ansν (Q, (∅, A)) = ∅ for each Q S ∈ Violatesν (T ); (2) if K is ν-satisfiable, then for each CQ Q, ansν (Q, K) = Q0 ∈PerfectRef ν (Q,T ) ansν (Q0 , (∅, A)). Example 3 Consider the KB K = (T , A) where T = {∃P vc A, A vc ∃type− } and A = {P (B, a)}. For the CQ Q : B(?x) → q(), by Algorithm 1, we can get PerfectRef ν (Q, T ) = {q1 : B(−) → q(), q2 : A(B) → q(), q3 : P (B, −) → q()}. Obviously, ansν (q3 , A) = {()}. Then by Theorem 2, ansν (Q, K) = {()} holds. Based on Theorem 2 and the algorithms in Fig.3, we can further obtain the complexity of satisfiability checking and CQ answering in DL-Lite Full. Theorem 3 For a DL-Lite Full KB K = (T , A), ν-satisfiability checking and CQ answering can be realized in PTime w.r.t. |T | and AC0 w.r.t. |A|. 4 Meta-query answering in DL-Lite Full 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 ∈ 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 Meta-query answering via meta-variable materialization For MQ answering, a direct way is to convert MQs into CQs by materializing meta-variables [29] with names. However, again unlike the existing work, com- pleteness cannot be guaranteed, since axioms referring type may enable the KBs not only to entail extra class individual assertions but also to imply that a named or anonymous individual may have anonymous classes, i.e., the classes implied to exist, such as the element e shown in the example below. Example 4 Consider the following DL-Lite Full KB K = (T , A) where T = {A vc ∃P, ∃P − vc ∃S, P vr type} and A = {A(a)}, and the query Q :?x(a) ∧ S(?x, ?y) → q(). Obviously, ansν (Q, K) = {()}, 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. DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 9 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. Definition 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 Definition 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-satisfiable DL-Lite Full KB K = (T , A), MQ Q and tuple u of names, then u ∈ ansν (Q, K) iff there exist MV-Binding θ ∈ MVB(Q, K) and CQ Q0 ∈ PerfectRef ν (Qθ, T ) such that u ∈ ansν (Q0 , (∅, A)). S Note that in Theorem 4, the set θ∈MVB(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) Sn→ q(?c, ?p, ?x) and ν-satisfiable DL-Lite Full KB K = ({A1 vc A2 }, {A1 (a)} ∪ i=1 {Pi (a, bi )}), 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: S MVB(Q, S K) = S o∈NK −{type} {({?p → o}, {})} ∪ {({?p → o}, {?c → e})}∪ S o∈NK −{type} e∈NK S {({?p → type}, {})} ∪ {({?p So∈NK S → type}, {?c → o})}}∪ o∈NK {({?p → type}, {?x → o})} ∪ o∈NK e∈NK {({?p → type}, {?c → o, ?x → e})} where NK consists Snthe names in K. By S S2of all trying 2 S2 all the MV-Bindings, we can get ansν (Q, K) = i=1 j=1 {(Ai , Pj , bj )} ∪ i=1 j=1 {(Ai , type, Aj )}. t u 4.2 Meta-query answering via partial meta-variable materialization and meta-query rewriting 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 material- ization and MQ rewriting, where just the names in the TBox are referred. The first observation is that under ν-semantics, answering a MQ over a DL- Lite Full ABox can be realized by evaluating a CQ over a database without try any meta-variable materialization, shown in the lemma below. 10 Zhenzhen Gu and Songmao Zhang Lemma 2 For a MQ Q and DL-Lite Full ABox A, we use DB to denote the database V {T (a, P, b)|P (a, b) ∈V A} ∪ {T (a, type, A)|A(a) ∈ A} and Q0 the query x(y,z)∈body(Q) T (y, x, z) ∧ x(y)∈body(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 rr T (resp. NT ) to denote the set of all the names used as classes (resp. roles) in the right-hand sides of the inclusion axioms in T . The way of partially materializing meta-variables of MQs is shown below. Definition 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 ∪ {type} and ϑc maps some class variables of [Qϑr ] to the names in Nrc T . And ({}, {}), i.e., without binding any role and class variable 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 par- tially. 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 meta- variable materialization and MQ rewriting, we first analyze the relationships between these two ways of materializing the meta-variables of MQs. Definition 5 For MQ Q, KB K = (T , A) and partial MV-Binding ϑ ∈ PMVB(Q, T ), a MV-Binding θ ∈ MVB(Q, K) is called an extension of ϑ over K if for each / Nrr role variable x of Q, if x ∈ dom(ϑ) then θ(x) = ϑ(x) otherwise θ(x) ∈ T ; and for each class variable x of Q, if x ∈ dom(ϑ) then θ(x) = ϑ(x) otherwise θ(x) ∈ / Nrc T . 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) ϑ = ({}, {?c → A2 }) is a partial MV-Binding of Q over K’s TBox, and ePMVB(ϑ, Q, K) = ∪o∈NK −NrrT −{type} {({?p → o}, {?c → A2 })} is the set consisting of the MV-Bindings obtained by binding the remainder role variable ?p to the names in NK − NrrT − {type}. DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 11 By Definition 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 ForSa MQ Q and DL-Lite Full KB K = (T , A), we can get that MVB(Q, K) = ϑ∈PMVB(Q,T ) ePMVB(ϑ, Q, K), and for each ϑ ∈ PMVB(Q, T ): 0 S S θ∈ePMVB(ϑ,Q,K) Q0 ∈PerfectRef ν (Qθ,T ) ansν (Q , (∅, A)) ⊆ 0 S Q0 ∈PerfectRef ν (Qϑ,T ) ansν (Q , (∅, A)) ⊆ ansν (Q, K) Combing Lemma 3 and Theorem 4, we can finally obtain the way of answering MQs via partial meta-variable materialization and meta-query rewriting. Theorem 5 For a MQ Q and ν-satisfiable DL-Lite Full KB K = (T , A), then for a tuple u of names, u ∈ ansν (Q, K) iff there exists ϑ ∈ PMVB(Q, T ) and Q0 ∈ PerfectRef ν (Qϑ, T ) such that u ∈ ansν (Q0 , (∅, A)) holds. Example 7 (Example 5 cont’d) Nrr rc T = ∅ and NT = {A2 }. By Definition 4, Q has totally the following 6 partial MV-Bindings over T : ϑ1 = ({}, {}) ϑ4 = ({?p → type}, {?c → A2 }) ϑ2 = ({}, {?c → A2 }) ϑ5 = ({?p → type}, {?x → A2 }) ϑ3 = ({?p → type}, {}) ϑ6 = ({?p → type}, {?c → A2 , ?x → A2 }) 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% Fig. 4. Statistics of the names used as classes/roles in BTC 2012 dataset and DBpedia, where Num C (Num R) denotes the number of names used as classes (roles), and Num rC (Num rR) number of names used as classes (roles) in the right-hand sides of axioms. Just considering the names occurring in the right-hand sides of the inclusion axioms can significantly reduce the number of candidates needed to be tried for the meta-variables of MQs Q, and further the number of queries eventually needed to be considered over the ABoxes of the KBs. This can be seen from the statistics of two actual KBs shown in Fig. 4. Finally, based on Lemma 2 and Theorem 5, we can further obtain the com- plexity of MQ answering in DL-Lite Full. Theorem 6 For DL-Lite Full KB K = (T , A) and MQ Q, ansν(Q, K) can be obtained in PTime w.r.t. |K| and AC0 w.r.t. |A|. 12 Zhenzhen Gu and Songmao Zhang 5 Related work The work [26–32, 34–36] focused on extending multiple uses of names in expres- sive DLs, such as SHOIN [37] and SROIQ [38]. Compared with these work, we concentrate on a light-weight DL, i.e., DL-LiteR , and study not only multiple uses of names but also non-standard uses of rdf : type. For light-weight DLs, [40–44] discuss extending DL-LiteR with multiple uses of names and MQ answering. The main difference between their work and ours embodies in the following aspects. We study non-standard uses of rdf : type in ad- dition. 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 individu- als 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 satisfiability checking and MQ answering any- more. 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 significantly reduce the number of queries needed to be evaluated over the data layers of KBs. There just exists one work, i.e., [39], discussing meta-modeling with instantiation in SROIQ and SHOIQ, where non-standard use of rdf : type can be captured. The authors provide methods of reducing satisfiability checking in the extended languages to satisfiability check- ing in the DL languages. However, this technique cannot be applied to DL-LiteR , since DL-LiteR does not support the constructors, like enumeration, used when translating the KBs in the extended languages to DL KBs. 6 Conclusion and future work 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 [28,30] need to be developed to optimize the procedure of MQ answering. Besides, DL-Lite Full just captures the non-standard uses of rdfs : type. Extending DL-Lite Full to capture the non-standard uses of other RDF(S)/OWL vocabulary terms as well as studying the rewriting ability and complexity of such extensions is also worth studying. Acknowledgments We thank the reviewers and program committee for their valuable comments and suggestions which will help us a lot to improve the whole work. DL-Lite Full: A Sub-language of OWL 2 Full for Powerful Meta-modeling 13 References 1. O’Riain, S., Curry, E., and Harth, A.: XBRL and open data for global financial ecosystems: A linked data approach. The International Journal of Accounting In- formation Systems 13(2): 141–162 (2012). 2. Polleres, A., and Steyskal, S.: Semantic Web Standards for Publishing and Inte- grating Open Data. In: Standards and Standardization: Concepts, Methodologies, Tools, and Applications (2015). 3. Bizer, C., Heath, T., and Berners-Lee, T.: Linked data-the story so far. J. on Se- mantic Web and Information Systems 5(3) 1–22 (2009). 4. Gu, Z., Zhang, S., and Cao, C.: Reasoning and querying web-scale open data based on DL-LiteA in a divide-and-conquer way. J. Web Semant 55: 122–144 (2019). 5. Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P., eds.: The Description Logic Handbook: Theory, Implementation, and Applications. Cambrige University Press, second edition (2007). 6. Poggi, A., Lembo, D., Calvanese, D., De Giacomo, G., Lenzerini, M., and Rosati, R.: Linking data to ontologies. Journal on Data Semantics 10(2008): 133–173 (2008). 7. Calvanese, D., De Giacomo, G., Lembo, D., Lenzerini, M., and Rosati, R.: Tractable reasoning and efficient query answering in description logics: The DL-Lite family. Journal of automated reasoning 39(3): 385–429 (2009). 8. Artale, A., Calvanese. D., Kontchakov, R., and Zakharyaschev, M.: DL-Lite without UNA. In Proceedings of DL’09 (2009). 9. Baader, F., Brandt, S., and Lutz, C.: Pushing the EL envelope. In Proceedings of IJCAI’05 (2005). 10. Grosof, B. N., Horrocks, I., Volz, R., and Decker, S.: Description logic programs: Combining logic programs with description logic. In Proceedings of the 12th inter- national conference on World Wide Web (2003). 11. Xiao, G., Calvanese, D., Kontchakov, R., Lembo, D., Poggi, A., Rosati, R., and Zakharyaschev, M.: Ontology-Based Data Access: A Survey. In Proceedings of IJ- CAI’18 (2018). 12. Hitzler, P., Krötzsch, M., Parsia, B., Patel-Schneider, P. F., and Rudolph, S.: OWL 2 Web Ontology Language Primer (Second Edition). W3C Recommendation (2012). 13. Hayes, P. J., and Patel-Schneider, P. F.: RDF 1.1 Semantics. W3C Recommenda- tion (2014). 14. Bishop, B., Kiryakov, A., Ognyanov, D., Peikov, I., Tashev, Z., and Velkov, R.: FactForge: A fast track to the web of Data. Semantic Web Journal 2(2): 157–166 (2011). 15. Umbrich, J., Hogan, A., Polleres, A., and Decker, S.: Link Traversal Querying for a diverse Web of Data. Semantic Web Journal 6(6): 585–624 (2012). 16. OWL 2 Punning, https://www.w3.org/TR/owl2-new-features/#F12:\_Punning. Last accessed 21 Jun 2021. 17. SUMO ontology, http://www.adampease.org/OP/. Last accessed 21 Jun 2021. 18. OpenCyc Ontology, http://sw.opencyc.org/. Last accessed 21 Jun 2021. 19. Life Science Ontologies, https://bioportal.bioontology.org/ontologies. Last accessed 21 Jun 2021. 20. FMA ontology, https://www.bioontology.org/wiki/index.php/FMAInOwl. Last accessed 21 Jun 2021. 21. BTC data set, https://km.aifb.kit.edu/projects/btc-2012/. Last accessed 21 Jun 2021 14 Zhenzhen Gu and Songmao Zhang 22. Hogan, A.: Exploiting RDFS and OWL for Integrating Heterogeneous, Large-Scale, Linked Data Corpora. Ph.D. thesis, National University of Ireland, Galway, 2011. 23. Schneider, M.: OWL 2 Web Ontology Language RDF-Based Semantics (Second Edition). W3C Recommendation (2012). 24. Golbreich, C., and Wallace, E. K.: OWL 2 Web Ontology Language New Features and Rationale (Second Edition). W3C Recommendation (2012). 25. Chen, W., Kifer, M., and Warren, D. S.: HILOG: a foundation for higher-order logic programming. Journal of Logic Programming 15(3): 187–230 (1993). 26. Motik, B.: On the Properties of Metamodeling in OWL. Journal of Logic and Computation 17(4): 617–637 (2007). 27. De Giacomo, G., Lenzerini, M., and Rosati, R.: Higher-Order Description Logics for Domain Metamodeling. In Proceedings of AAAI’11 (2011). 28. Gu, Z., and Zhang, S.: Querying Large and Expressive Biomedical Ontologies. In Proceedings of HPCC’15 (2015). 29. Gu, Z.: Meta-modeling extension of Horn-SROIQ and Query Answering. In Pro- ceedings of DL’16 (2016). 30. Gu, Z., and Zhang, S.: The more irresistible Hi(SRIQ) for meta-modeling and meta-query answering. Frontiers of Computer Science 12(5): 1029–1031 (2018). 31. Gu, Z., Cao, C., and Zhang, S.: An Expressive Sub-language of OWL 2 Full for Domain Meta-modeling. In Proceedings of DL’19 (2019). 32. Pan, J. Z., and Horrocks, I.: OWL FA: A Metamodeling Extension of OWL DL. In Proceedings of WWW’06 (2006). 33. Homola, M., Kl’uka, J., Svátek, V., and Vacura, M.: Typed higher-order variant of SROIQ - why not?. In Proceedings of DL’14 (2014). 34. Motz, R., Rohrer, E., Severi, P.: Reasoning for ALCQ extended with a flexible meta-modeling hierarchy. In: 4th Joint International Semantic Technology Confer- ence (2014). 35. Motz, R., Rohrer, E., and Severi, P.: The description logic SHIQ with a flexible meta-modeling hierarchy. Journal of Web Semantics 35(2015): 214–234 (2015). 36. Glimm, B., Rudolph, S., and Völker, J.: Integrated metamodeling and diagnosis in OWL 2. In Proceedings of ISWC’10 (2010). 37. Horrocks, I., Sattler, U.: A tableau decision procedure for SHOIQ. Journal of automated reasoning, 39(3), 249-276, 2007. 38. Horrocks, I., Kutz, O., Sattler, U.: The Even More Irresistible SROIQ. In: 10th International Conference on Principles of Knowledge Representation and Reasoning, 2006. 39. Kubincová, P., Kl’uka, J., and Homola, M.: Towards Expressive Metamodelling with Instantiation. In Proceedings of DL’15 (2015). 40. De Giacomo, G.; Lenzerini, M.; and Rosati, R. 2011. Higher-Order Description Logics for Domain Metamodeling. In Proceedings of AAAI’11. 41. Lenzerini, M., Lepore, L., and Poggi, A.: Practical higher-order query answering over Hi(DL-LiteR ) knowledge bases. In Proceedings of DL’14 (2014). 42. Lenzerini, M., Lepore, L., and Poggi, A.: Answering meta-queries over Hi(OWL2QL) ontologies. In Proceedings of IJCAI’16 (2016). 43. Lenzerini, M., Lepore, L., and Poggi, A.: Metaquerying made practical for OWL 2 QL ontologies. Information Systems 88(2020) 101294 (2020). 44. Lenzerini, M., Lepore, L., and Poggi, A.: Metamodeling and metaquerying in OWL 2 QL. Artificial Intelligence 292 (2021). 45. Patel-Schneider, P. F.: Reasoning in RDFS is inherently serial, at least in the worst case. In Proceedings of the 11th International Semantic Web Conference, Posters & Demonstrations Track. (2012).