Ontological databases have become the distinguished knowledge bases for today's systems, which consist of an extensional database and an ontology. Several ontological languages have been proposed to model domain knowledge such as Datalog[∃] which extends Datalog with existential quantification. This addition has enriched the language capabilities in capturing complex domain knowledge, however, it makes reasoning tasks, such as query answering, undecidable. Identifying decidable fragments of Datalog[∃] is an important approach to deal with the above issues, where prominent examples are fragments supporting so-called query rewritability. Several rewriting algorithms have been introduced; however, these algorithms are executed in a sequential fashion. In this paper we discuss a methodology that allows existing rewriting algorithms to exploit multi-core architectures, and show how to employ this methodology to implement a parallel version of an existing query rewriting algorithm.
Knowledge representation and reasoning have gained a lot of interest in the last decade. The so-called ontological database, a.k.a. knowledge base, has evolved to be a prominent approach for managing today’s system data. A knowledge base merges an extensional database (e.g., a relational database) with an ontology, i.e., a logical theory encoding domain knowledge. The addition of an ontology on top of a standard database then allows to derive additional (called intensional) knowledge that was never explicit in the database alone.
This is a step forward in enhancing reasoning activities. An ontology is an explicit
specification of a conceptualization of an area of interest [
Several formal languages have been proposed to model ontologies, among which there are
the ones based on Description Logics (DLs) [
Prominent examples are fragments supporting so-called query rewritability, i.e., Datalog[∃] ontologies for which a given query and the ontology can be compiled to a new query, in particular, to a union of conjunctive queries (UCQ), that can be evaluated directly on the extensional database alone. The result of the evaluation will be the same as if the original query is executed against the extensional database and the ontology rules.
Example 1. Consider the following Datalog[∃] ontology rule which asserts that for each project X in some department Y, there exists a supervisor Z who is assigned to the department Y of the project, and consider the (conjunctive) query (CQ) which asks for all projects who have a supervisor assigned in the ’db’ department: : ∀∀ project(), inDept(, ) → ∃supervisor(, , )
() :- ∃ supervisor(, , ).
The equivalent rewritten query of the above ontology Σ and query , is the following UCQ: Σ = {() :- ∃ supervisor(, , ), () :- (), (, )}.
The above query states that an answer (tuple) (B) to the query is a project of the database that is either explicitly assigned a supervisor at the ’db’ department, or a project at the ’db’ department.
Several rewritable fragments of Datalog[∃], and corresponding rewriting algorithms, have
been introduced in recent years, however, to the best of our knowledge, all such algorithms
are only meant to be executed in a sequential manner, and hence do not scale well with large
ontologies as in the worst case, query rewriting leads to an exponentially sized new UCQ. This
drawback has influenced the database research community to develop new algorithms that can
enhance the query rewriting process. In [
Despite the work that has been introduced in this area, however, the sequential execution of these algorithms remains the main bottleneck.
Contributions. The goal of this work is to explore the following research goals: 1. Introduce a new methodology that allows to existing rewriting algorithms to perform parallel computations. 2. By means of the above methodology, define a parallel version of one of the main (sequential) query rewriting algorithms known in the literature.
Organization. The paper is organized as follows: Section 2 introduces basic notation and notions. Section 3 discusses the state-of-the-art regarding query rewriting techniques for Datalog[∃]-based ontologies. The proposed methodology for enhancing query answering via parallelization, together with an algorithmic proposal based on this methodology is discussed in Section 4. Conclusions and directions for future work as presented in Section 5.
Relational Schema: A relational schema R consists of a finite set of predicates (relation names),
each with a specific arity. We use ∆ , , and to denote countably infinite sets of constants,
nulls and variables. A term is a constant, null or variable. An atomic formula (or simply atom)
over a schema R is an expression of the form (¯), where is a predicate of R with arity , and
¯ = 1, . . . , is a tuple of terms. An atom without variables is called a fact. An instance is a set
of facts, while a database is an instance without nulls.
(Unions of) Conjunctive Queries (UCQs): A Conjunctive query (CQ) is a rule-based query
that corresponds to the select-project-join fragment of relational algebra queries and can be
represented in either a first-order logic form or rule-like syntax form [
In a rule-like syntax form, a CQ is an expression of the form:
(¯) : − 1(¯1), . . . , (¯), where (¯) is an atom, called the head of the query, and denoted head(), with ¯ are the output variables of , while 1(¯1), . . . , (¯) is a sequence of atoms, called the body of the query; body() denotes the set of atoms of the body of . A union of Conjunctive queries (UCQ) is a set of CQs all having the same head predicate.
Answer of a UCQ over a database: Answers of a CQ over an instance are defined via homomorphisms. A homomorphism from a set of atoms to a set of atoms is a function ℎ mapping terms in to terms in , being the identity over the constants. Given an instance , a conjunctive query Q with output variables ¯, and a tuple of constants and nulls ¯, we say that ¯ is an answer to over if there is a homomorphism ℎ from the body of Q to such that ℎ(¯) = ¯.
Datalog[∃] Ontologies and Knowledge Bases: A Datalog[∃] rule, a.k.a. tuple generating dependency (TGD) is an expression of the form:
∀¯1, . . . , ¯ 1(¯1), . . . , (¯) → ∃¯ 0(¯0) where each (¯) is an atom over the tuple of variables ¯, with ¯ ⊆ ¯0 In particular, 0(¯0) is the head, and 1(¯1), . . . , (¯) is the body of the rule.1 An ontology Σ is a finite set of TGDs. 1For simplicity, we often omit the universal quantifier from rules.
Models of a Knowledge Base: A knowledge base is a pair (, Σ) of a database and an
ontology Σ . A model of (, Σ) is an instance such that D ⊆ I and I satisfies each TGD of Σ ; I
satisfies a TGD if, whenever there exists a homomorphism h from its body to , then there is
an extension h’ ⊇ h of h, such that h’ is a homomorphism from the head of to I.
Ontological Query Answering: Given a knowledge base (, Σ) and a UCQ (¯, the answers
to (¯) over (, Σ) , denoted ans(, , Σ) is the set of tuples ¯ of constants such that ¯ ∈ (),
for every model of (, Σ) [
It is well-known that ontological query answering, i.e., the problem of checking whether a given tuple ¯ is an answer to a given UCQ over a given knowledge base, is undecidable, unless restrictions on the ontology language are enforced.
Datalog[∃] is an extension of classical Datalog that enhances its expressivity by introducing
existential quantifiers to its rules. Although this version has enhanced the knowledge
representation capabilities of the language, this increase in expressive power makes ontological query
answering undecidable. Current approaches to tackle this issue focused on identifying fragments
of the Datalog[∃] language, that guarantee that ontological query answering becomes decidable.
The most prominent approach is the one of rewritability. An ontology Σ is rewritable if for any
UCQ Q, it is possible to rewrite Σ and to a new UCQ Q’ such that, for every database , the
answers of Q over the knowledge base (D, Σ ) coincide with the answers of Q’ over D alone, i.e.,
ans(, , Σ) = ′(), for every database . Such a query ′ is called a perfect rewriting of Σ
and . Diferent fragments of Datalog[ ∃] have been introduced in the literature that guarantee
ontologies written in such fragments are rewritable, such as linear ontologies, multi-linear
ontologies and sticky ontologies. All such fragments are powerful enough to express ontologies
written in other important formalisms such as Description Logics [
Several eforts in implementing rewriting algorithms for the these fragments have been
introduced. One prominent example is the so called XRewrite algorithm [
and the query taken from Example 1.
project(), inDept(, ) → ∃ supervisor(, , )
() :- supervisor(, , )
The rewriting step starts with finding a match for the head of , i.e., head( ), and (a subset of) the body of , body(). The match in this case is for supervisor(A, db, B) and supervisor(Z,Y,X), which is {X → B,Y → db, Z → A}. Thus, the atom supervisor(A, db, B) in in the body of can be replaced with the body of .2 The result of the rewriting step is a new CQ Q.
() :- project(), inDept(, ).
Applying the rewriting step without considering some important constraints could lead to unsound or incomplete rewritings. To overcome such problems, two conditions are required before a rewriting step can be performed, namely the applicability condition, which, roughly, guarantees that the rewriting step does not produce a new query obtained by means of joining values coming from existential variables with constants, and factorization, which is an intermediate operation that simplifies a given query, so that the applicability condition can be applied.
The XRewrite algorithm is thus an exhaustive application of rewriting step and factorization, until no new queries can be produced, and the result of the algorithm is the union of all queries produced. The key property of the algorithm is that it always terminates, whenever the input ontology is rewritable. The authors introduced some preliminary work on making this algorithm run in parallel, but this has been achieved only for Linear TGDs. The authors achieved the parallelization by decomposing the input query into smaller chunks and rewrite each of these chunks independently, using the XRewrite algorithm and finally merge the rewriting of each chunk into the final rewriting.
Another algorithm that exploits similar ideas to the XRewrite is the PURE rewriting
algorithm [
To the best of our knowledge, all existing rewriting algorithms are essentially computing
sequentially, and thus do not scale well with large ontologies. The research problem to be
addressed is thus to identify methodologies for parallelization and then, extend the preceding
algorithms with these approaches. To apply parallelization, we can exploit an idea that was
initially introduced in [
person() → ∃ hasFather(, ) 2Variables in the body of that do not appear in its head are assumed to be replaced with fresh variable names, to avoid clashes with existing variables in the query.
( ) :- hasFather(, ), employee( ) .
Note that due to the applicability condition, the head of cannot be unified with the atom hasFather(, ) of the query, since is a join variable in the query, and this variable is going to be mapped to the existential variable of .
With the above in mind, it is clear that to safely decompose the query, we first need to understand which variables in the query have a chance to be unified with an existential variable, at any step of the rewriting algorithm; atoms of the query mentioning such variables should never be separated, when decomposing the query.
Example 5. Consider the following example.
1: person( ) → ∃ hasFather(, ) 2 : son( ) → male( ) 3 : father( ) → male( ) 4: son( ) → ∃ hasFather(, ) 5 : daughter( ) → ∃ hasFather(, ) 2 : daughter( ) → female( )
Consider also the following conjunctive query asking for all (, ), where a is a male and has father b.
(, ) :
male(), hasFather(, ).
After inspecting the rules in Σ , it is easy to verify that there is no join variable occurring in that has a chance to be unified with an existential variable during the rewriting process, therefore, we can safely decompose . For example, as the following 2 subqueries3: 1() 2(, ) ::male() hasFather(, ) We then use a so-called reconciliation rule to encode the original query as the conjunction of the above to sub-queries:
: (, ) :- 1(), 2(, ), that intuitively says that Q is the query obtained by computing the join of the queries 1,Σ2,Σ.
The simplest form of parallelization one can employ is thus the one where given a UCQ
and an ontology Σ , we first decompose into subqueries 1,. . . ,, and then employ an
ofthe-shelf sequential rewriting algorithm over each w.r.t. Σ . Then, by using the reconciliation
rule , and the rewritings of each , one can perform the "unfolding" of , obtainig the final
rewritten UCQ. This is the approach employed in [
We present a preliminary modification of the XRewrite algorithm using the above approach in Algorithm 1.
Algorithm 1 The modified XRewrite algorithm Input: a CQ Q over a schema R and a set Σ of TGDs over R Output: the perfect rewriting of Q w.r.t. Σ := {(Q, r, u)}; repeat := ; foreach (Q, x, u) ∈ , where x ∈ {r, f} do (1, . . . , , ) := decompose(Q, Σ ); for = 1 to do in parallel := ∅; foreach ∈ Σ do /* rewriting step */ foreach S ⊆ body() such that is applicable to S do
Let be the MGU for S,; Construct Q’ by replacing S with body( ) in , and
apply to all variables of Q’; := ∪ (Q’, r, u); end /* factorization step */ foreach S ⊆ body() which is factorizable w.r.t. do
Let be the MGU for the atoms in ; Construct Q’ by applying to the variables of body(Q); := ∪ (Q’, f, u); end end end /* query Q is now explored */ := ( ∖ {(Q, x, u)}) ∪ {(Q, x, e)}; /* unfolding of the rewritings */ Σ := unfold(1 , . . . , , ); foreach in Σ obtained from queries all marked with r do if there is no (Q”, r, *) ∈ which is equal to Q, up to variable renaming then := ∪ {(Q, r, u)}; end end foreach in Σ obtained by using a query marked with f do if there is no (Q”, *, *) ∈ which is equal to Q, up to variable renaming then := ∪ {(Q, f, u)}; end end end until = ; := {Q | (Q, r, e) ∈ }; return
The algorithm keeps track of all intermediate rewritten queries in a set , where each query is marked with two flags: the first is either r or f, meaning that the query is going to be part of the final rewriting, or it is the result of an intermediate factorization, while the second is either u or e meaning the query is unexplored, and thus needs to be processed, or it has been already processed (explored). The main idea is to initialize with the input query, and then, iteratively do the following: decompose the currently worked-on query extracted from , via the decomposition approach explained earlier. Then, for each subquery , an independent thread is used to apply the rewriting and the factorization steps to exhaustively, as in the original XRewrite algorithm, and the resulting UCQ obtained from each subquery is stored in a dedicated set . The algorithm then marks the worked-on query as explored, and the results are then joined together with the unfolding operation, obtaining a UCQ Σ whose elements (CQs) need to be added to the global set . In the last part of the algorithm, if a CQ in Σ has been obtained by combining only queries marked with r, i.e., as "to be rewritten", then this CQ will be part of the final rewriting, and thus it is marked with r in the set . If instead one of the queries used to construct the CQ was marked with f, i.e., "as being just an intermediate query obtained by factorization", then we mark the CQ with f in the set as it means it needs further processing.
Correctness and Termination. To show that the algorithm is correct, and terminates for
every ontology Σ that is rewritable, we extend the proofs of correctness and of termination
employed in [
Regarding the termination, this follows from the termination of the original XRewrite algorithm, and the fact that the unfolding of the reconciliation rule of a CQ w.r.t. the UCQs that rewrite each component of coincides with the perfect rewriting of , and thus does not introduce more UCQs w.r.t. the ones introduced by sequential version of XRewrite.
In this paper, we considered the problem of Ontological Query Answering via query rewriting,
for Datalog[∃] ontologies. That is, given a Datalog[∃] ontology Σ and a query , compute a
UCQ Σ such that the answers to over the knowledge base (, Σ) coincide with the answers
of Σ over , for every database . We studied the problem from a theoretical perspective, and
identified state of the art algorithms that would greatly benefit from parallel implementations.
We highlighted a preliminary proposal in this direction by adapting the (sequential) XRewrite
algorithm from [