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, [4]). The original focus of DL research was the ontology in itself, with problems like satisfiability or subsumption between concepts. The conjunctive query answering problem has been considered more recently. Classical DLs appeared to be highly complex for that reasoning problem, and lightweight description logics (such as EL and DL-Lite) are thus very relevant.
A parallel approach relies on existential rules [5,6], also known as TGDs [1] that form the basis of Datalog ± [8]. Existential rules are logical formulas of the form B → H, where B and H are conjunctions of atoms and where H might contain existentially quantified variables. In contrast to DLs, they allow for any predicate arity (which in particular eases the integration with database systems in which relations are naturally translated into n-ary predicates) and can express some cyclic dependencies on variables. On the other hand, neither disjunction nor negation is expressible with existential rules. Interestingly, the two main families of DLs that have been designed for conjunctive query answering can be translated into existential rules. The associated ontology-based conjunctive query answering problem (CQA) is formalized as follows: given a set of facts (in their logical form an existentially closed conjunction of atoms) F, a set of rules R, and a conjunctive query Q, check whether F, R | = Q hold. This problem is undecidable, and numerous restrictions on R have been proposed recently in order to ensure decidability (see [12] for a survey), which is usually proven by means of one of the two following mechanisms, or a combination of both. The first one is forward chaining: rules are iteratively applied to F, until either no new information is added, or the query is entailed. If a set of rules is such that for any fact, this process halts in finite time or generates a set of facts of bounded treewidth (which is defined on a graph naturally associated with the facts, see e.g. [6]), then the CQA problem is decidable ( [7,5]). The second mechanism is backward chaining: a query Q is rewritten into a set of conjunctive queries (which can be seen as a union of conjunctive queries), such that Q is entailed by F and R if and only if one its rewritings is entailed by F. The CQA problem is decidable if the set of rewritings is finite for any query.
EL [2,11] is one of the description logics that have a reasonable complexity for CQA: NP-complete in combined complexity and Ptime-complete in data complexity. As pointed out before, any EL TBox can be translated into existential rules. However, the smallest known Datalog ± decidable class covering such rules is a class for which CQA complexity is much higher than the original one (2-Exptime-complete in combined complexity). Finally, it is known that one can add to EL inclusions a special kind of complex role inclusions while keeping polynomial data complexity [10]. As far as we know, such results have no counter-part in the rule framework. Moreover, one of the most used complex role inclusion, namely transitivity, is out of the scope of known decidability criteria when combined with decidable classes of existential rules.
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 [3]. The syntactic regularity condition enforced is close from the one imposed in Horn-SROIQ ( [9]).
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 [13] and designed for a more general existential rule class, yielding an easier and worst-case optimal algorithm for orientable fr1 rules. This algorithm is further modified in Section 5 in order to take some complex role inclusions into account. Section 6 concludes the paper.
In this paper, we will avoid technical definitions and rely on examples, to provide an intuition about the main techniques.
We briefly recall the preliminary definitions presented in [6]. An atom is of the form p(t 1 , . . . , t k ) where p is a predicate with arity k, and the t i are terms, i.e., variable or constants. A fact is the existential closure of a conjunction of atoms. 1 An existential rule (or simply a rule when not ambiguous) is a formula R = ∀x∀y(B[x, y] → (∃zH[y, z])) 2where B = body(R) and H = head(R) are finite conjunctions of atoms, called the body and the head of R, respectively. The frontier of R, denoted by fr(R), is the set of variables vars(B) ∩ vars(H) = y. A rule R is applicable to a fact F if there is a homomorphism π from body(R) to F; the result of the application of R on F w.r.t. π is a fact α(F, R, π) = F ∪ π safe (head(R)) where π safe is a substitution of head(R), that replaces each x ∈ fr(R) with π(x), and each other variable with a "fresh" variable, i.e., not introduced before. The direct saturation of F with R is defined as
, by the universal model of F and R).
An EL TBox contains concept inclusions C 1 C 2 , where C 1 and C 2 are concepts built as follows:
Any EL ontology can be translated into a set of existential rules (which are called EL-rules), where
, 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.
3 Orientable fr1 Rules
However, the combined complexity of reasoning with fr1 rules and EL is quite different: 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 x 1 will map its body to dashed atoms, and will create atoms that are also below x 1 . This is due to the fact that information about a term "above" x 1 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 r 1 , . . . , r k . 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.
• a
Fig. 1. An arc is directed from the first to the second argument of an atom.
Definition 1 (<-graph associated with a set of atoms). Let A be a set of atoms. The <-graph associated with A is the directed graph defined as follows:
to each term x appearing in A, we assign a vertex v x , for any x, y such that x y and x and y appear in the same atom with position p x < p y , there is an arc from v x to v y (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. Definition 3 (Orientable fr1 set of rules). A set of rules R is orientable fr1 (or simply 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 = {r(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)}. By taking r 1 < r 2 , s 1 < s 2 and q 1 < q 2 < q 3 , 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.
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 R 1 < R 2 for any role R).
Property 2 (Generalization of EL) Any set of EL-rules is orientable.
In the next examples, we assume for all predicate p that p i < 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 [13] for a class of rules called greedy bounded treewidth set, which includes fr1. While performing forward chaining, a greedy tree decomposition (of bounded width) of the currently generated fact is maintained. We call bags the nodes of this tree, which is built as follows: the root of this tree contains all atoms in F, and each time a rule with frontier f is applied by means of a homomorphism π, we create a new bag that contains the newly generated atoms, and choose as its pBarent the root of the tree if π( f ) is a constant or a variable of F, otherwise the bag in which the variable π( f ) has been generated.
Example 2 (Greedy tree decomposition). Let F = {p(a), q(a)} and R = {R 1 : p(x) → r(x, y) ∧ q(y); R 2 : q(x) → t(x, y) ∧ p(y)}. We show the greedy tree decomposition of α 4 (F, R) in Figure 2. p(a), q(a) r(a, x 1 ), q(x 1 ) t(a, y 1 ), p(y 1 )
r(x 2 , x 3 ), q(x 3 )
r(y 2 , y 3 ), q(y 3 )
t(y 3 , y 4 ), p(y 4 )
Fig. 2. The greedy tree decomposition of α 4 (F, R)
Maintaining this tree decomposition is not sufficient by itself to ensure the termination of the algorithm, since the universal model can be infinite. The main notion used in [13] to ensure the finiteness of the built tree is the equivalence between bags: two bags B and B are said equivalent when every fact that will eventually be mapped "under B" (i.e., using at least one term generated below B) can be mapped similarly (i.e., up to a bijection between terms of B and B )"under B ", and conversely. If two bags are equivalent, it is only necessary to apply rules below one of them, and the other one will be said "blocked". When no more rule is applicable on a non-blocked bag, we obtain the full blocked tree.
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 ∈ R, R ∈ R, and F be a fact. Let B 1 and B 2 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, z 1 and z 2 be the corresponding fresh variables in B 1 and B 2 . B 1 has a child created by a rule application of R mapping fr(R ) to z 1 if and only if B 2 has a child created by a rule application of R mapping fr(R ) to z 2 .
Example 2 (contd.). A full blocked tree of F and R is represented in Figure 3. L 2 is equivalent to D 1 , D 2 to L 1 ; L 2 and D 2 are blocked and no new rule application can be done on B 0 , L 1 or D 1 -this is checked by existence of a * -homomorphism, see below.
Second, we check rule applicability by means of * -homomorphism. This tool is introduced in [13] to evaluate a conjunctive query. Suppose that, at some step of the algorithm, we have generated a blocked tree T . We want to check if there is a homomorphism from Q to the possibly infinite fact encoded by T . This fact can be obtained from T by a possibly infinite sequence of completions, that iteratively copies under blocked bags the atoms found under their equivalent bag (up to variable renaming). Such a homomorphism induces a partition of Q (two atoms are in the same set if they are mapped to the same -initial or added -bag) and a tree structure for this partition (mimicking the tree structure of the image bags). Finally, [13] shows that if there exists such a homomorphism, there exists one requiring only a completion sequence of bounded length. To encode the homomorphism, we thus only need the tree decomposition of Q, homomorphisms from each subset of Q to a bag of T , and the required bounded number of completions: this is the structure called a * -homomorphism. p(a), q(a) r(a, x 1 ), q(x 1 ) t(a, y 1 ), p(y 1 )
t(x 1 , x 2 ), p(x 2 ) r(y 1 , y 2 ), q(y 2 ) Example 3 ( * -homomorphism). Let Q = {r(z, z 1 ), t(z 1 , z 2 ), r(z 2 , z 3 ), t(z 3 , z 4 ), t(z, z 1 )}. Let π = {(z, a), (z 1 , x 1 ), (z 2 , x 2 ), (z 3 , x 3 )(z 4 , x 4 ), (z 1 , y 1 )} from Q to the fact associated with the tree drawn in Figure 2. The corresponding * -homomorphism is pictured in Figure 4.
∅ r(z, z 1 ) t(z, z 1 )
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 Q 1 , {(z, a), (z 1 , x 1 )} is a homomorphism from r(z, z 1 ) to r(a, x 1 ), q(x 1 ), which is consistent with Q 0 since z is mapped to a in both cases. An interesting consistency check occurs for Q 2 and Q 3 : since Q 2 has been mapped to a bag having no child, z 2 has image x 2 when considering Q 2 , and y 1 when considering Q 3 . However, this is consistent since when copying D 2 under L 2 , we rename y 1 by x 2 .
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 [13]. The NPmembership is due to the fact that the structure we build is of polynomial size in F and R. The hardness holds because it generalizes EL.
It is interesting to note that our algorithm, when further restricted to EL ontologies, becomes similar to the algorithm presented in [11]. The main difference is that, while our algorithm maintains equivalence classes, the algorithm in [11] merges equivalent bags. These merges result in the finiteness of the process, but also in the loss of homomorphism soundness with respect to first-order semantics. Soundness is regained by modifying homomorphism check, in a way both based on the orientation of EL and on its tree-model property.
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 = {p(x) → r(x, y) ∧ p(y); r(x, y) ∧ r(y, z) → r(x, z)}. The query Q = {q(x), r(x, y), q(y)} 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 different 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 [10]. In the following, we define an abstract condition of regularity for so-called oriented join rules, and an easily checkable syntactic condition that generalizes existing results. We then illustrate the algorithm with Example 5.
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 = R o ∪ R j where R o 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 r 1 < r 2 , s 1 < s 2 and t 1 < t 2 , or r 1 > r 2 , s 1 > s 2 and t 1 > t 2 .
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 R o be a set of <-oriented fr1 rules, R j be a set of <-oriented join rules (for the same order <), R, R ∈ R o , F be a fact. Let B 1 and B 2 two bags of T * (the greedy tree decomposition of the backbone associated with F and R o ∪ R j ) created by the same rule R ∈ R o . Let z be an existential variable of R, z 1 and z 2 be the corresponding fresh variables of B 1 and B 2 . B 1 has a child created by a rule application of R mapping fr(R ) to z 1 if and only if B 2 has a child created by a rule application of R mapping fr(R ) to z 2 .
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 P F (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, P F (z, z 3 ) = {rtr}. Definition 7 (Regularity of a set of join rules). Let P be a set of binary predicates, and R c be a set of join rules over P. R c is regular if for any predicate p ∈ P, there exists a regular language L p such that, for any fact F , for any x, y ∈ terms(F), the following holds:
F, R c | = p(x, y) ⇔ P F (x, y) ∩ L p ∅
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 effectively 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 t 1 in a bag B equivalent to B 3 , but there should also be a path from a to the image of the frontier of the rule creating B, such that A w (Figure 5) ends in s 3 when reading the word associated with that path. It is worth to note that this is not the case for B 3 and B 5 , but it holds for B 7 , even though B 3 , B 5 and B 7 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.
We take a fact F = {p(a)} and a query Q = {w(a, x)}. 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 t 3 . We represent this homomorphism by the structure represented Figure 7. 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 [10]. Definition 8 (Stratified set of join rules). A set of join rules is stratified if the directed graph G built as follows is acyclic. For every predicate p, there exists a vertex v p in V. There is an arc from v p to v q 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. p(a) r(a, y 1 ), r(y 1 , z 1 ), q(z 1 ), p(z 1 ) r(z 1 , y 2 ), r(y 2 , z 2 ), q(z 2 ), p(z 2 ) r(z 2 , y 2 ), r(y 3 , z 3 ), q(z 3 ), p(z 3 )
Fig. 6. In plain, the full blocked tree; in dashed, a completion (Example 5). By additionally using (only) role inclusions, Q = w(a, x) can be mapped, mapping x to t 3 . Property 5 (Regularity of a stratified set of join rules) A stratified set of join rules is regular.
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 (v p , v q ) 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.
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 [13].
We then investigated how to add some expressive power that could be useful in practice, while staying polynomial in data complexity: we showed how to add transitivity axioms and left-and right-identity rules. Although adding these rules does not fulfill the usual decidability criteria, we adapted the algorithm for orientable rules by using finite automata. Some follow-up naturally come to mind: can we generalize our approach to cover Horn-SROIQ? What is the combined complexity of CQA with the considered rules? What are interesting classes of rules with predicate of any arity that could be added to this basis, while staying polynomial in data complexity? How does the algorithm behave in practice? Moreover, compared to the algorithm presented in [11], the representation of the universal model uses more space, since equivalent nodes are not merged. Can we adapt our algorithm in order to reduce the space requirements?
The author thanks the anonymous reviewers for their useful and constructive comments.