The combined approach is a well-known technique used to address the problem of conjunctive query (CQ) answering over knowledge bases. Various versions of the approach exist for relevant fragments of OWL 2. In this paper we focus on the combined approach for CQ answering over RSA, a class of ontologies that extends the OWL 2 profiles while maintaining the tractability of standard reasoning tasks. The algorithm was first presented in [4], but to the best of our knowledge a stable implementation is not currently available. We present RSAComb, a novel implementation of the algorithm that introduces several improvements and fixes to the original approach and uses RDFox as the underlying Datalog reasoner. As well as providing high performance, the extended features of RDFox allow for an optimised implementation of the filtration step. We developed the system with modularity and stability in mind so that it can be used as a standalone tool or integrated into other software as a library. We include an extensive evaluation of the system, focusing on performance and scalability.
Conjunctive query (CQ) answering is a primary reasoning task over knowledge bases for many applications. However, when considering expressive description logic languages, query answering is computationally very expensive, even when considering only complexity w.r.t. the size of the data (data complexity ).
In order to achieve tractability and scalability for the problem, one main approach is to limit the expressive power of the class of ontologies considered.
Query answering algorithms have been developed for several fragments of OWL 2 for which CQ answering is tractable with respect to data complexity ? This work was supported by the AIDA project (Alan Turing Institute), the SIRIUS Centre for Scalable Data Access (Research Council of Norway), Samsung Research UK, Siemens AG, and the EPSRC projects AnaLOG (EP/P025943/1), OASIS (EP/S032347/1) and UK FIRES (EP/S019111/1).
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
[
An interesting fragment of OWL 2, tractable for standard reasoning tasks, is
RSA, an ontology language that subsumes all the OWL 2 profiles, first presented
in [
In this paper we introduce RSAComb, an efficient implementation of the combined approach algorithm for RSA. We developed the system with modularity, extensibility, and integration in mind and the software offers both an intuitive command-line interface and a Scala API to be used as a self-contained library.
The new implementation features RDFox [
The system accepts any OWL 2 ontology and includes a customisable approximation step to RSA. In addition, we streamlined the execution of the combined approach by factoring out those steps in the combined approach that are query independent to make answering multiple queries over the same knowledge base more efficient. Furthermore, we performed an extensive set of experiments on the system. An analysis of the most relevant results is provided in Section 5.
RSAComb has been released as free and open source software. Source code and documentation are available at https://github.com/KRR-Oxford/RSAComb. 2
We assume familiarity with standard concepts of first-order logic (FO), with
OWL 2, the (Horn-)ALCHOIQ fragment and OWL 2 profiles, and with the
definition of CQ, CQ answering and combined approach for CQ answering.
Combined approach in RSA RSA, first introduced in [
The combined approach for CQ answering in RSA consists of two main steps. The first step computes the canonical model of an RSA ontology over an extended signature (introduced to deal with inverse roles and directionality of newly generated binary atoms). The computed canonical model is not universal and, as such, might lead to spurious answers in the evaluation of CQs. The second step of the computation performs a filtration of the computed answers to identify only the certain answers to the input query. Both of these steps are offloaded to a Datalog reasoner able to handle negation as failure and function symbols.
For a definition of the RSA class of ontologies, and a detailed description of
the combined approach algorithm, we refer the reader to [
In this section we give an overview of the system, focusing on the overall architecture and design choices that we had to make along the way.
Figure 1 summarises the workflow of the system: (i) normalisation and customisable approximation steps approximate an unrestricted OWL 2 ontology to RSA; (ii) the canonical model is then computed for the resulting ontology; (iii) a Datalog filtering program is derived from the input query and is combined with the canonical model to produce the set of certain answers to the input query over the approximated ontology. Depending on how the approximation is performed, the set of answers returned might have different properties (e.g., the approximation currently provided computes a lower bound of the answers to the query over the original ontology).
It is worth noting that, in this scenario, steps (i),(ii) are query independent, while step (iii) is ontology independent. As such, when multiple queries are submitted, steps (i-ii) can be performed “offline” and only the third step needs to be performed for each input query.
Our implementation uses RDFox to perform steps (ii) and (iii). 3.1
Modularity the code should be modular and different steps in the algorithm should be as independent of each other as possible. It should be easy to reimplement (or enhance) an intermediate step of the algorithm as long as the signature and the interface with the system as a whole remain unaltered. We achieved this by an extensive use of Scala traits, building a collection of interfaces that describe the behaviour of the different actors that take part in the execution of the combined approach for RSA. As explained in the following sections, the integration with RDFox was also key to provide a good level of modularity to the systems.
Scalability the system has to be able to scale efficiently even for large amounts of data. We factor parts of the computation and reuse previous results whenever possible. A more detailed analysis on the scalability of the system is reported in Section 5.
Integration it should be equally possible to use the system as a self-contained application or integrate it in another system. As such, our software presents a simple but effective command line interface alongside a well-structured set of classes exposing all the necessary tools to work with RSA ontology, while hiding unnecessary implementation details. The different steps can also be disabled for user convenience. 3.2
The process of importing the input ontology into the system is performed using the OWLAPI. Note that only the ontology (TBox, RBox) is imported while the data (ABox) provided as separate files is loaded “on demand” directly into RDFox to maximize performance.
Our system performs an optimised normalisation to reduce the input ontology to the syntax introduced in Table 1. The ontology is then approximated to RSA. These steps allow the input of unrestricted OWL 2 ontologies.
Since the approximation of an unrestricted OWL 2 ontology to RSA can be
highly application-dependent, users can easily provide their own implementation
or turn it off completely when dealing with RSA ontologies. We provide a sound
approximation to RSA, which means that query answers for non-RSA ontologies
will be sound but possibly incomplete (i.e., we compute a lower bound answer).
The algorithm is based on the idea of deleting nodes to reduce the dependency
graph built from the input ontology [
The computation of the canonical model involves the conversion of the input
RSA ontology into logic rules as described in Section 3 in [
Since the canonical model is query independent, this process can be performed once and the result can be cached and reused for every subsequent query over the same input ontology. We achieve this using RDFox’s support for RDF named graphs, which enables us to perform operations on specific “named” subsets of the data. Further operations on the graph operate and produce additional data on a different named graph, leaving the materialised canonical model intact. 3.4
Answer filtration involves the computation of the filtering program from the input query, the filtering of the materialised canonical model and the final process of gathering the answers.
Our system performs the translation of the query into a set of logic rules. As
noted before, this step was reworked to be completely ontology independent1. To
1 See [
Here we can see the real advantage of using named graphs to separate the outcomes of different steps; when processing a new query, the only step we need to take is dropping the named graph associated with the filtration from the previous query, leaving unaltered all other triples. Better yet, here we have the possibility to execute queries in parallel, each one associated with a separate filtering program and hence a different named graph. The materialisation update for each of the queries is isolated and does not interfere with the other processes.
At this point, the task of gathering the answers to the query over the
input knowledge base is reduced to querying a materialised named graph for
the atoms representing the certain answers, which is straightforward for any
materialisation-based Datalog reasoner. Note that this step is slightly different
from the original implementation in [
Here is a description of some of the more significant improvements introduced2
w.r.t. to the original approach presented in [
A main technical difference from the original work on the RSA combined approach is the adoption of RDFox as a Datalog reasoner instead of DLV. This choice has several advantages, but we had to overcome some challenges.
RDFox does not provide direct support for function symbols (which are required in the computation of the canonical model), but we can mimic this using the Skolemization capabilities offered by the tool. In particular a logic rule with function symbols
A(?X) -> R(?X,f(?X)), B(f(?X)) . is turned into
A(?X), SKOLEM("f",?X,?Y) -> R(?X,?Y), B(?Y) . 2 For an up-to-date list of changes, fixes, and improvements we refer the reader to the project repository. where SKOLEM is an RDFox built-in atom that computes a unique identifier from a sequence of terms ("f" and ?X in this example), storing it in the last term of the atom (?Y in this case).
It is worth noting that the SKOLEM functionality is in general more powerful than a hash function3 since RDFox guarantees a bijective relation between a specific sequence and its identifier. In other words, given the special atom SKOLEM(?X,?Y,?Z,?K), we can compute ?K knowing the sequence of terms ?X, ?Y, ?Z, or alternatively “unpack” ?K into its original sequence ?X, ?Y, ?Z. We use this property to optimise the filtering step.
Another benefit of the introduction of RDFox is the ability to organize the computation in named graphs, as described in Section 3.3, to reuse partial results in the computation when necessary.
In general, the introduction of RDFox, and a clever use of its features, allowed us to keep the system somewhat closer to the realm of description logics4. 4.2
RDFox is primarily an RDF reasoner and its ability to handle (extended) Datalog makes it able to capture the entire RL profile. We were able to partially rewrite and simplify the filtering step in the RSA combined approach: a) a first rewriting step gets rid of all atoms with arity greater than 2 through reification; b) filtering rules are then greatly simplified by making extensive use of the SKOLEM functionality introduced above5.
Example 1. Consider rule (3c) from the original filtering program in [
id(~x; ~y; u; v); id(~x; ~y; v; w) ! id(~x; ~y; u; w) (1) Given a function KEY to compute a new term that uniquely identifies a tuple of terms, we can turn any n-ary atom into a set of n atoms of arity 2 using a well-known technique called reification. E.g., an atom P (x; y; z) becomes P1(k; x); P2(k; y); P3(k; z), where k = KEY(x; y; z) and Pn, for 1 n arity(P ), are fresh predicates of arity 2. Rule (1) then becomes id1(k; x1); : : : ;idm+n(k; yn); idm+n+1(k; u); idm+n+2(k; v); id1(j; x1); : : : ;idm+n(j; yn); idm+n+1(j; v); idm+n+2(j; w); l := KEY(~x; ~y; u; w) ! id1(l; x1); : : : ; idm+n(l; yn); idm+n+1(l; v); idm+n+2(l; w) (2) 3 By “hash function” we mean any function that can map values of arbitrary size to fixed-size values. 4 RDF triples are first-class citizens and only atoms with arity 2 are allowed. 5 Thus, avoiding some expensive joins that would slow down the computation (see
Section 5 in [
Using SKOLEM6, we are able to reduce the arity of a predicate P (see predicate id in Rule (3)) without having to introduce arity(P ) additional fresh predicates. Joins over multiple terms (id joining over (~x; ~y) in (1)) can now be rewritten into simpler joins (id joining over a single term k) while the use of SKOLEM does not introduce additional join operation7.
id(k; j); SKOLEM(~x; ~y; u; v; j); id(k; l);SKOLEM(~x; ~y; v; w; l);
SKOLEM(~x; ~y; u; w; t) ! id(k; t) (3) tu 4.3
RDFox has built-in support for > (top, truth or owl:Thing) and different kinds of equality (using owl:sameAs), so that > automatically subsumes any new class introduced within an RDF triple, and equality between terms is always consistent with its semantics.
Unfortunately, in both cases we are not able to use these features directly.
We need to import axioms as Datalog rules, and those are not considered when
RDFox derives new > subsumptions. The equality feature cannot be enabled
along with negation-as-failure, which is required for the combined approach and
is extensively used in our system. To work around this, we introduce the
axiomatisation for both concepts explicitly as explained in [
For every concept name C 2 NC and for every role name R 2 NR in the input ontology, we add the following rules to RDFox: owl:Thing[?X] :- C[?X] .
owl:Thing[?X], owl:Thing[?Y] :- R[?X, ?Y] .
For equality axiomatisation, we make owl:sameAs reflexive, symmetric and transitive as follows: owl:sameAs[?X, ?X] :- owl:Thing[?X] . owl:sameAs[?Y, ?X] :- owl:sameAs[?X, ?Y] .
owl:sameAs[?X, ?Z] :- owl:sameAs[?X, ?Y], owl:sameAs[?Y, ?Z] . and introduce substitution rules to complete the axiomatisation. For every concept name C 2 NC and role name R 2 NR in the input ontology, we add: C[?Y] :- C[?X], owl:sameAs[?X, ?Y] .
R[?Z, ?Y] :- R[?X, ?Y], owl:sameAs[?X, ?Z] .
R[?X, ?Z] :- R[?X, ?Y], owl:sameAs[?Z, ?Z] . 6 https://docs.oxfordsemantic.tech/tuple-tables.html#rdfox-skolem 7 Rule 3 showcases how this functionality can be used in both “directions”: given a previously skolemized term, we can unpack it in a single operation to retrieve the corresponding sequence of terms and given a sequence of terms, we can pack them into a new fresh term.
We have also clarified and refined some specific details of the theoretical
definitions and their implementation reported in [
In the canonical model computation in [
A similar approach has been used to redefine and implement the NI predicate, representing the set of non-anonymous terms in the materialised canonical model. We enumerate the elements of this set introducing the following rule:
NI[?Y] :- named[?X], owl:sameAs[?X, ?Y] . where the named atom represents the set of constants in the original ontology.
A final improvement has been made on the computation of the cycle function during the canonical model computation. The original definition involved a search over all possible triples (A; R; B) where A; B 2 NC , R 2 NR in the original ontology. We realised that traversing the whole space would significantly slow down the computation, and is not necessary; we instead restrict our search over all (A; R; B) triples that appear in a (T5) axiom A v 9R:B in the original normalized ontology. 5
Implementation details Our implementation is written in Scala and uses
RDFox8 as the underlying Datalog reasoner. At the time of writing,
development, and testing have been carried out using Scala v2.13.5 and RDFox v4.1.
Scala allows us to easily interface with Java libraries and in particular with
the OWLAPI [
Testing environment All experiments were performed on an Intel(R) Xeon(R) CPU E5-2640 v3 @ 2.60GHz with 16 real cores, extended via hyper-threading to 32 virtual cores, 512 GB of RAM and running Fedora 33, kernel version 5.8.17-300.fc33.x86_64.
The system has been tested against LUBM [
Approximation to RSA
datasets come in sizes 100 through 800 universities (in steps of 100). Reactome
dataset was sampled from 10% through 100% (in steps of 10%). We used the
same set of queries used in [
The filtering process is instead less dependent on the size of the data and more dependent on its composition and distribution. As such, a bigger dataset does not necessarily correspond to a greater amount of filtering, as shown in Figure 3, where we reported the execution time for query 1 and 2 in Reactome. This figure also shows how the filtering depends on the data distribution; both queries take longer on size “50” than on other datasets (even larger ones) due to its specific content.
In general, we noticed that the time spent by the system on the filtering step is considerably smaller than the time spent on the canonical model computation (as described below, and shown in Figure 5).
This unpredictability of the filtering step can “backfire” when a huge amount of filtering is involved. In Figure 4 we show the filtering time for query 2 in 300 250 200 150 100 50 0 s r e w s n a f o s n o lii m LUBM along with the amount of unfiltered answers that the filtering program needs to process. Of these, less than 1‰ is found to be a certain answers. Figure 4 confirms the previous claims that the filtering step grows proportionally to the amount of filtering that is needed for a particular query. Finally, this figure shows how our system is able to handle a gigantic filtering step, processing hundreds of millions of facts in a reasonable amount of time.
Canonical model computation vs. filtering Finally, Figure 5 shows how execution time is distributed among the two main tasks of the combined approach. Filtering takes consistently less that 20% of the total execution time, when considering bigger datasets. As mentioned before, we can limit the impact of the canonical model computation by factoring out the task and computing it “offline” whenever we found ourselves in a scenario in which we need to perform query answering over a fixed ontology. 6
We presented RSAComb, an alternative and improved implementation of the
combined approach for CQ answering in RSA. The software presents a few
differences from the original description presented in [
RSAComb is currently used as part of an effort to improve the performance
of the OWL 2 reasoner PAGOdA [