Ontology-based data access consists in using ontologies while querying data. Due to the high complexity of this problem, considering lightweight description logics like EL is especially relevant. Another strand of research is based on existential rules. In this paper, we use this latter formalism in order to cover EL with the same complexity of reasoning while allowing any predicate arity and some cycles on variables. We then add complex role inclusions to enhance expressivity, while staying polynomial in data complexity and generalizing existing results. In particular, we consider transitivity and right/left identity rules, which do not behave well with respect to usual decidability paradigms.
Ontology-based data access (OBDA) recently received a lot of attention both from
knowledge representation and database communities. This problem can be stated as
follows: given a set of facts and an ontology (the knowledge base), one wants to
evaluate a conjunctive query against this knowledge base. The ontology can be represented
in several ways. Traditional ontology languages are description logics (DLs,[
A parallel approach relies on existential rules [
EL [
The contribution of this paper is two-fold:
– first, it presents a class of existential rules, namely orientable fr1, that covers EL
ontologies while keeping the same (data or combined) complexity for CQA
(Theorem 1). The proposed class allows for predicates of arbitrary arity and a form of
cyclic dependencies between variables;
– second, it generalizes this class by adding complex role inclusions while staying
polynomial in data complexity (Theorem 2); it allows for left and right identity
rules, which have been proven useful for modeling purposes [
In Section 2, basic definitions about EL and existential rules are recalled. In Section
3, orientable fr1 rules are introduced. Section 4 adapts the algorithm presented in [
In this paper, we will avoid technical definitions and rely on examples, to provide an intuition about the main techniques. 2
We briefly recall the preliminary definitions presented in [
An EL TBox contains concept inclusions C1 v C2, where C1 and C2 are concepts built as follows:
C := > j A j C1 u C2 j 9R:C
Any EL ontology can be translated into a set of existential rules (which are called EL-rules), where C1 v C2 is translated into (C1)(x) ! (C2)(x), with inductively built as explained Table 1. The smallest known decidable class covering rules needed for the translation of an arbitrary EL TBox is the set of frontier-1 (fr1) rules, i.e., the set of rules whose body and head share exactly one variable. However, the combined complexity of reasoning with fr1 rules and EL is quite di erent: 2-Exptime-complete in the former case, and NP-complete in the latter – though both are in Ptime for data complexity. In this section, we present a class of rules that covers EL while keeping the same combined and data complexities.
EL-rules have the following idiosyncrasy: they add information “below” the frontier of the rule, as pictured in Figure 1. Any EL-rule mapping its frontier to x1 will map its body to dashed atoms, and will create atoms that are also below x1. This is due to the fact that information about a term “above” x1 is not even expressible, since no inverse role is possible. Orientable fr1 rules generalize this idea.
We define for every predicate r of arity k a strict total order on its positions r1; : : : ; rk. We denote by < the union of all these relations. Given such a strict partial order, we can associate a directed graph with each set of atoms. 2 We can now omit quantifiers since there is no ambiguity.
x2 x1 x3
y1
<-graph associated with A is the directed graph defined as follows: – to each term x appearing in A, we assign a vertex vx, – for any x; y such that x , y and x and y appear in the same atom with position px < py, there is an arc from vx to vy (note that no loop can occur).
Intuitively, a rule is oriented for an order < if the atoms needed to trigger it as well as the atoms created by it are situated both in the same right direction according to <. Definition 2 (<-oriented fr1 rule). Let R be a rule and < a strict total order on the position of its predicates. R is <-oriented fr1 if it is fr1 and if the <-graph associated with body(R) [ head(R) is a directed acyclic graph such that there is a path from fr(R) to any other node.
Given this notion of rule orientation, we naturally define the notion of orientable fr1 set of rules.
orientable when not ambiguous) if there exists an order < such that every rule of R is <-oriented fr1.
Example 1 (Orientable fr1 set of rules). Let us take R = fr(x; y) ^ p(y) ! q(x; z; t) ^ s(z; t); q(x; y; z) ^ s(y; z) ! r(x; t) ^ r(t; t) ^ p(t)g. By taking r1 < r2; s1 < s2 and q1 < q2 < q3, we can easily check that this set of rules is <-oriented. Note that these rules are not translatable in EL because of the predicate of arity 3 and of cycles. Property 1 (Recognizability problem) The problem of deciding whether a set of rules R is orientable is NP-complete.
The hardness result comes from a reduction of 3-SAT. NP-hardness of the recognizability problem might impede the practical applicability of following results. However, this complexity remains quite small compared to the combined complexity of CQA with a lot of known classes, and, more importantly, even strongly restricted sets of orientable rules are still of interest. Indeed, the next property shows that rules translating EL ontologies are very naturally oriented (with R1 < R2 for any role R).
In the next examples, we assume for all predicate p that pi < p j if and only if i < j.
In this section, we present a forward chaining algorithm which is a simplified version of
the algorithm introduced in [
Example 2 (Greedy tree decomposition). Let F = fp(a); q(a)g and R = fR1 : p(x) ! r(x; y) ^ q(y); R2 : q(x) ! t(x; y) ^ p(y)g. We show the greedy tree decomposition of 4(F; R) in Figure 2.
R1
Maintaining this tree decomposition is not su cient by itself to ensure the
termination of the algorithm, since the universal model can be infinite. The main notion used in
[
This equivalence as well as rule applications are computed in the original algorithm by means of patterns, that are attached to each bag. The complexity of the original algorithm is due to the high number of relevant patterns. In the remaining of this section, we explain how to compute the equivalence relation as well as new rule applications without using patterns – and thus we do not present patterns here.
First, we can simplify equivalence between bags: with orientable fr1 rules, two bags are equivalent if they have been created by the same rule, as stated by the following property.
Property 3 Let R be a set of orientable fr1 rules, R 2 R; R0 2 R, and F be a fact. Let B1 and B2 be two bags of T (the tree decomposition of the universal model of F and R) created by the same rule R. Let z be an existential variable of R, z1 and z2 be the corresponding fresh variables in B1 and B2. B1 has a child created by a rule application of R0 mapping fr(R0) to z1 if and only if B2 has a child created by a rule application of R0 mapping fr(R0) to z2.
Example 2 (contd.). A full blocked tree of F and R is represented in Figure 3. L2 is equivalent to D1, D2 to L1; L2 and D2 are blocked and no new rule application can be done on B0, L1 or D1 – this is checked by existence of a -homomorphism, see below.
Second, we check rule applicability by means of -homomorphism. This tool is
introduced in [
R1 Example 3 ( -homomorphism). Let Q = fr(z; z1); t(z1; z2); r(z2; z3); t(z3; z4); t(z; z01)g. Let = f(z; a); (z1; x1); (z2; x2); (z3; x3)(z4; x4); (z01; y1)g from Q to the fact associated with the tree drawn in Figure 2. The corresponding -homomorphism is pictured in Figure 4.
; r(z; z1) t(z1; z2) r(z2; z3) t(z3; z4) t(z; z01)
Q6 ! D1
Given a tree decomposition of Q and homomorphisms from bags of this decomposition to corresponding bags of T (as in Figure 4), we check if it is actually a homomorphism. We check for any pair of adjacent nodes that the associated mappings are compatible, i.e., the image of any term is unique. In the given example, for Q1, f(z; a); (z1; x1)g is a homomorphism from r(z; z1) to r(a; x1); q(x1), which is consistent with Q0 since z is mapped to a in both cases. An interesting consistency check occurs for Q2 and Q3: since Q2 has been mapped to a bag having no child, z2 has image x2 when considering Q2, and y1 when considering Q3. However, this is consistent since when copying D2 under L2, we rename y1 by x2.
Theorem 1. The conjunctive query answering problem with a set of orientable fr1 rules
is Ptime-complete for data complexity and NP-complete for combined complexity.
Proof. The Ptime membership comes from similar result for fr1 rules in [
It is interesting to note that our algorithm, when further restricted to EL ontologies,
becomes similar to the algorithm presented in [
Complex role inclusions are arguably useful in practice. However, this kind of rules does not behave well with respect to both forward chaining and backward chaining, as illustrated with Example 4.
Example 4. Let R = fp(x) ! r(x; y) ^ p(y); r(x; y) ^ r(y; z) ! r(x; z)g. The query Q = fq(x); r(x; y); q(y)g is not rewritable w.r.t. R into a finite union of conjunctive queries, and R does not generate facts of bounded treewidth either: a clique of arbitrary size can be built by performing forward chaining on the fact p(a).
In order to stay as close as possible to the algorithm of previous section, we split any
fact generated during the chase into two parts: atoms generated by fr1 rules (the
backbone), and those generated by role inclusions. The first part is of bounded treewidth,
and can be managed in the same way as before. The second part will be dealt with in
a di erent fashion: we restrict the set of allowed role inclusions in order to deal with
them by means of automata, as it was already done in [
Definition 4 (Join rule). A join rule is a rule of the following shape: r(x; y) ^ s(y; z) ! t(x; z). Transitivity rules are the case where r = s = t, left-identity rules where r = t. Definition 5 (Backbone). Let F be a fact, R = Ro [ R j where Ro is a set of fr1 rules and R j is a set of join rules. The backbone associated with F and R is the subset of atoms of the universal model of F and R that have been created by a fr1 rule.
The backbone is of bounded treewidth, and a tree decomposition can be built greedily. In order to have a counter-part of Property 3 on bag equivalence, we consider only orientable join rules.
Definition 6 (<-oriented join rules). Let R be the following join rule: r(x; y)^s(y; z) ! t(x; z). R is a <-oriented join rule if: – either r1 < r2; s1 < s2 and t1 < t2, – or r1 > r2; s1 > s2 and t1 > t2.
The following property allows us to keep a trivial equivalence relation on bags. Indeed, it ensures that the criterion used in the previous section to check equivalence between bags remains valid when adding <-oriented join rules to our framework. Property 4 Let Ro be a set of <-oriented fr1 rules, R j be a set of <-oriented join rules (for the same order <), R; R0 2 Ro, F be a fact. Let B1 and B2 two bags of T (the greedy tree decomposition of the backbone associated with F and Ro [ R j) created by the same rule R 2 Ro. Let z be an existential variable of R, z1 and z2 be the corresponding fresh variables of B1 and B2. B1 has a child created by a rule application of R0 mapping fr(R0) to z1 if and only if B2 has a child created by a rule application of R0 mapping fr(R0) to z2.
Having a finite representation of the backbone, we use regularity in order to manage join rules. Given a fact F and x and y two terms of F, we denote by PF (x; y) the set of words that describe a finite elementary path from x to y. For instance, in the query Q of Figure 4, PF (z; z3) = frtrg.
and Rc be a set of join rules over P. Rc is regular if for any predicate p 2 P, there exists a regular language Lp such that, for any fact F , for any x; y 2 terms(F), the following holds:
F; Rc j= p(x; y) , PF (x; y) \ Lp , ;
Similarly to a -homomorphism, a j-homomorphism is a labeled tree structure, together with a mapping from its bags to the bags of the full blocked tree. In the homomorphism case, the consistency check consists only in checking that each term of the query has a well-defined image. In the j-homomorphism case, we also have to check that atoms generated by complex role inclusions can be e ectively generated. Let us consider Example 5 and Figure 5. In order to have w(a; x) entailed by the universal model, not only should x be mapped to t1 in a bag B equivalent to B3, but there should also be a path from a to the image of the frontier of the rule creating B, such that Aw (Figure 5) ends in s3 when reading the word associated with that path. It is worth to note that this is not the case for B3 and B5, but it holds for B7, even though B3; B5 and B7 are equivalent. We thus add this information about states in the j-homomorphism.
Compared to the orientable fr1 case, the size of a completion needed to map a query can be bigger up to a factor which is exponential in the query and in the automaton used to recognize regular predicates. This does not increase the data complexity of CQA with the union of a <-oriented fr1 set of rules and a <-oriented and regular set of join rules, which remains Ptime-complete. However further work is required to determine the combined complexity of the problem.
Example 5. Let R = Ro [ R j with Ro = fp(x) ! r(x; y) ^ r(y; z) ^ q(z) ^ p(z); q(x) ! w(x; y)g and R j = fr(x; y) ^ r(y; z) ! s(x; z); s(x; y) ^ r(y; z) ! t(x; z); t(x; y) ^ w(y; z) ! w(x; z)g. We take a fact F = fp(a)g and a query Q = fw(a; x)g. The regular expressions associated with r; s; t and w are r, rr + s, rrr + sr + t, and (rrr + sr + t) w.
There exists a homomorphism from Q to the completion represented in Figure 6, mapping x to t3. We represent this homomorphism by the structure represented Figure 7. s0
s r s1 t r s2 r s3
w s4
Last, we present a syntactic condition that ensures that a set of join rules is regular.
In particular, this condition generalizes the condition proposed in [
graph G built as follows is acyclic. For every predicate p, there exists a vertex vp in V. There is an arc from vp to vq where p , q if there exists a rule r(x; y) ^ s(y; z) ! t(x; z), where p = r or p = s and q = t.
B1 B2 B4
p(a) r(a; y1); r(y1; z1); q(z1); p(z1) r(z1; y2); r(y2; z2); q(z2); p(z2) r(z2; y2); r(y3; z3); q(z3); p(z3) w(z1; t1) w(z2; t2) w(z3; t3)
B3 B5 B7
Proof (sketch). By induction on the structure of G. A predicate p whose vertex does not have an incoming arc is associated with the regular expression p. For any q, if we have a regular expression for any p such that (vp; vq) is an arc of G, we can build one for q. Theorem 2. The CQA problem with rules being the union of of <-oriented fr1 rules and <-oriented regular join rules (for the same order <) is Ptime in data complexity. 6
In this preliminary work, we identified a class of existential rules, namely fr1 orientable
rules, covering EL ontologies while keeping the same complexity for CQA. Rules allow
to easily use predicates of any arity and some cycles between variables. We exploited
the simplicity of orientable fr1 rules to simplify the very recent algorithm from [
The author thanks the anonymous reviewers for their useful and constructive comments.