2.1 RDF schema

We assume a basic familiarity of the reader with the RDF language, that is, the W3C standard for representing information in the form of subject-predicate-object tripletsFootnote ² . RDF schema is an extension of RDF which provides an additional vocabulary to describe relations between classes and properties; specific datatypes and containers such as lists are also supported. Among others, RDF schema allows the definition of domain and range of properties, as well as class and property hierarchies (subsumption relationships). The semantics of RDF schema is defined via the well-known model-set semantics presented in Hayes (Reference Hayes2004) which allows the inference of additional consequences through a logical process.

Most of the inference processes on RDFS can be performed by the application of simple rules and have desirable computational properties: they are tractable when function symbols are not used. However, a complete materialization of all conclusions is impossible in the general case because the language contains an infinite number of axioms as pointed out by ter Horst in ter Horst (Reference ter Horst2005). Therefore, all RDFS reasoning engines are bound to be incomplete.

2.2 Ontology Web langage (OWL)

RDFS allows for definitions of taxonomies of concepts and properties and specification of domains and ranges of properties but it does not support more complex definitions of concepts and restrictions of concepts. Concepts corresponding to expressions such as “a teacher teaches at least one class” or “persons with three children are entitled to additional social benefits” cannot be represented using RDFS, thus an ontology definition language with additional expressivity has been introduced for such definitions. OWL (see Hitzler et al., Reference Hitzler, Krötzsch, Parsia, Patel-Schneider and Rudolph2009) is the standard Web ontology language from W3C, with its first version standardized in 2009 and second version (OWL 2) in 2012. The OWL allows the definitions of vocabularies for annotating RDF data with complex axioms. Axioms such as cardinality restrictions over properties, existential and universal quantifications, intersection, union, disjointness of concepts, symmetry and transitivity of properties among others. There are two semantics which are associated to OWL: the direct semantics, which is underpinned in description logics (DL), and the RDF-based semantics, which is compatible with the RDF semantics. The correspondence between these two semantics was well analyzed by the standardization committee. While OWL 2 is decidable, worst case computational complexity of reasoning tasks is intractable (N2ExpTime-complete) thus fragments of OWL (OWL profiles) that allow for efficient reasoning have been defined.

2.3 Datalog

Datalog is a QL based on function-free Horn rules and has been used as a data model for relational databases (Abiteboul et al., Reference Abiteboul, Hull and Vianu1995). A datalog program consists of facts about a subject of interest and datalog rules to deduce new facts implicit in the data. A datalog rule is in the following form.

(1) $$B_{1} ,...,B_{n} \to H$$

In the rule (1), H is referred to as the head atom and B ₁,...,B _n the body atoms. Facts can be seen as rows in a relational database table, while rules can be used to enrich database queries. The traditional datalog is designed as a QL for deductive databases. In recent years, datalog has also been widely exploited in other applications, such as declarative networking, program analysis, distributed social networking and security as discussed in Huang et al. (Reference Huang, Green and Loo2011).

The evaluation of datalog programs can be either query-driven or not. Query-driven evaluation receives in input an initial query which should contain the final answers of the computation. Non query-driven evaluation does not receive any query in input, and hence focuses on applying all the rules in the program until fixpoint. We call this last type of processing materialization since its goal is to derive any possible conclusion that can be entailed. Traditionally, query-driven evaluation is executed in a top-down fashion, trying to limit the derivation to only answers that are relevant for the input query. However, query-driven evaluation can be implemented also with a bottom-up approach: The Magic-sets algorithm is perhaps the most famous example of query-driven bottom-up approach as discussed in Abiteboul et al. (Reference Abiteboul, Hull and Vianu1995). Materialization is typically implemented in a bottom-up fashion. The most important datalog bottom-up algorithm is called semi-naive evaluation (see Abiteboul et al., Reference Abiteboul, Hull and Vianu1995) and all bottom-up approaches which are discussed in this paper implement variants of this algorithm. The complexity of datalog evaluation is well-known: The data complexity is PTime-complete, and the program complexity and combined complexity are both ExpTime-complete as discussed in Ullman (Reference Ullman1989).

2.4 Nonmonotonic reasoning

Nonmonotonic reasoning presented in Antoniou and Williams (Reference Antoniou and Williams1997) is a family of logics and associated reasoning algorithms that can deal with imperfect information. Imperfection may be caused by missing (incomplete) information, erroneous data, inconsistencies in knowledge structures caused, for example, by combining various ontologies or by evolving knowledge.

A prominent computationally simple approach is the well-founded semantics (WFS) presented in Gelder et al. (Reference Gelder, Ross and Schlipf1991), which considers logic programs with negation and provides a way of interpreting negation. Essentially, it does so by assigning truth values to atoms only if the existing knowledge (the logic program at hand) makes it necessary to do so. So it is a sceptical kind of semantics. Its computational complexity is polynomial, the fastest reasoning algorithm for computing the WFS is quadratic.

Another computationally simple approach is the family of default logics presented in Billington et al. (Reference Billington, Antoniou, Governatori and Maher2010). Its driving idea is that rules may support contradictory conclusions, and it uses a priority relation to resolve such conflicts in a sceptical way, if possible. In a nutshell, a conclusion is drawn if it is supported by facts or rules, and all possible attacks (rules supporting its negation) are successfully countered by stronger supporting rules. Defeasible logics lie at the intersection of logic programming and systems of argumentation, and the most basic defeasible logic has linear complexity.

More expressive nonmonotonic reasoning approaches have also emerged, the most prominent being answer-set programming (ASP) presented in Gelfond (Reference Gelfond2008). Like WFS it is an approach that interprets negation in logic programs. The idea is to compute answer sets, maximal and consistent alternative ‘world views’, based on the existing knowledge. Each answer set represents a credulous way of resolving conflicts in the KB. ASP has exponential complexity, so on the one hand it can represent richer problems compared to the approaches outlined above, but on the other hand it poses big challenges in terms of computation, particularly w.r.t. run time.

After providing a brief overview of reasoning approaches above we turn our attention to computational models in the next section.

3.1 MapReduce framework

MapReduce is a programming model for distributed processing of data on clusters of machines (each machine being called a node) presented in Dean and Ghemawat (Reference Dean and Ghemawat2004). MapReduce transforms lists of input data elements into lists of output data elements. This happens twice, once in a map and again in reduce. The terms map and reduce are taken from several list processing languages such as LISP, Scheme, ML.

Map: The data set to be processed is divided into multiple chunks, and each chunk is assigned to a map. Map nodes generate intermediate output according to a user-defined function. In its general form, the function accepts a key-value pair and returns a set of key-value pairs. The output pairs are typically written to the local disk. The functionality of Map nodes can be represented as

$${\rm Map}\,\colon\,(k_{1} ,v_{1} )\mapsto{\rm list}(k_{2} ,v_{2} ).$$

Reduce: Reduce nodes are notified of the locations of intermediate output. They group values by key, and then process the values according to a user-defined Reduce function. One or more output values is produced. The general process can be represented as

$${\rm Reduce}\,\colon\,(k_{2} ,{\rm list}(v_{2} ))\mapsto{\rm list}(v_{3} ).$$

Map and Reduce functions are shown in Figure 1.

Figure 1

Map and reduce operations

HadoopFootnote ⁶ is a prominent implementation of the MapReduce model. Developers need only define the map and reduce functions. Lower level and administrative tasks, such as allocating data to nodes and recovering from failures, are handled by general purpose (GP) components of the system.

3.2 GPU computing

Graphics processing unit (GPU) is used for efficient processing of computer graphics, images and in turn offloads these responsibilities from a GP central processing unit (CPU). GPUs are highly parallel and follow the single instruction, multiple data (SIMD) model. Threads in a GPU are lightweight, which makes their creation, context switching and termination, a low cost operation. This makes GPU ideal for embarrassingly parallel tasks which exhibit data parallelism. The use of GPUs for non-graphics applications is referred to as GP computing on GPUs (GPGPU) or GPU computing as discussed in Owens et al. (Reference Owens, Houston, Luebke, Green, Stone and Phillips2008).

The architecture of a GPU is shown in Figure 2. A bunch of data records, called streams, are processed at any time by a streaming multiprocessor, which in turn consists of several processing elements (PE). Each PE runs a thread at a time and has access to the local memory including registers and cache. A GPU, typically, has several streaming multiprocessors and all of them have access to a slower, shared global memory.

Figure 2

GPU architecture

GPUs cannot access the main memory. So, it is the responsibility of the CPU to transfer data from the main memory to the GPU’s global memory and when the task is done, transfer back the results to the main memory.

Several programming languages to develop GPGPU applications have been developed by extending the C language. Among them, CUDAFootnote ⁷ from Nvidia and OpenCLFootnote ⁸ (recognized as a standard) from Khronos group are popular.

3.3 Peer-to-peer model

A distributed network architecture is called peer-to-peer (P2P) if resources such as computing power, storage etc. are decentralized and each node can act as both a server as well as a client (Schollmeier, Reference Schollmeier2001). All nodes in the network collaborate with each other to accomplish a common goal. This is different from a Client-Server architecture where servers provide the service and clients have to request the servers to get their job done.

3.4 Multithreading

A traditional (heavyweight) process has a single flow of control and has a sequence of instructions that should be executed sequentially. On the other hand, threads, also called lightweight processes, exist within a process and allow multiple streams of control flow to coexist. All threads within a process share the same address space as that of the parent process. Threads should be synchronized in order to avoid problems such as data inconsistencies and deadlocks.

All computing models discussed above vary in terms of the process/thread interaction and their access to main memory. GPU computing and multithreading have shared memory architecture whereas the other two have a distributed memory architecture. The choice of which model to use, depends on the task at hand.

Having provided a short introduction to reasoning approaches and computional paradigms, we will discuss in the next section the criteria against which large-scale reasoning approaches will be evaluated.

5.1 RDFS

In Kaoudi et al. (Reference Kaoudi, Miliaraki and Koubarakis2008), the authors propose a method for scalable RDFS reasoning (both forward and backward reasoning) using distributed hash tables (DHTs), a popular instantiation of P2P networks.

Target formalism RDFS reasoning is studied in this work.

Supported reasoning tasks Both forward chaining and backward chaining reasoning are considered.

Algorithm The proposed algorithm allows that instance data and schema knowledge are handled uniformly and no global information about the schema is required. The authors rewrite the RDFS entailment rules into datalog rules, thus, some optimization techniques of datalog reasoning can be utilized for RDFS reasoning. The authors propose two distributed algorithms for forward chaining and backward chaining reasoning. The proposed backward chaining algorithm is a top-down algorithm designed for RDFS reasoning in a distributed environment.

Theoretical properties: The proof of soundness and completeness of this method is also reported.

Implementation A prototype system is implemented. The RDF triples are stored as tuples in relational tables. The proposed algorithms are then implemented to adapt to the distributed hash table (DHT) platform. The DHT platform used in this work contains 123 available nodes.

Reported scalability The used data set with binary-tree-shaped RDFS class hierarchies for evaluation is produced using the RBench generator. First, the authors evaluate the backward chaining algorithm. It takes 8 and 50 s respectively for inserting 10³ and 10⁴ triples into the network. However, for forward chaining implementation, the time needed for inserting 10³ and 10⁴ triples varies dramatically from about 100 s to 10 000 s. The experimental results show that the bandwidth of forward chaining algorithm increases exponentially with the tree-depth while it remains constant in backward chaining algorithm. The authors conclude that simple forward chaining implementation cannot scale well. The main issues are caused by redundant computation and communication overhead.

Marvin (MAssive RDF Versatile Inference Network) presented in Oren et al. (Reference Oren, Kotoulas, Anadiotis, Siebes, ten Teije and van Harmelen2009) is a parallel and distributed platform for massive processing of RDF data, based on a P2P model.

Target formalism The work considers incomplete RDFS reasoning.

Supported reasoning tasks The main task here is the computation of the closure for the given set of RDF data.

Algorithm Marvin implements the divide-conquer-swap strategy, which partitions the given data set into subsets (divide), computes the closure (conquer) and repartitions data by exchanging triples among neighboring nodes (swap). Eventual completeness of the inference is guaranteed, since triples that may emit new knowledge are gradually collocated on the same node. In Kotoulas et al. (Reference Kotoulas, Oren and van Harmelen2010), the authors extend the work with a technique to improve the problem of load balancing which affects a fixed term-based partitioning criterion. This technique creates elastic regions in case the frequency of some terms is significantly higher than others.

Implementation Reasoning over monotonic logics is supported, while closure is computed by utilizing reasoners as an external library. In addition, duplicate detection and removal is supported in order to minimize memory and bandwidth overheads. On the one hand, the random approach (triples are exchanged randomly among nodes) provides good load balancing properties, but is highly inefficient since triples appear on random nodes, thus postponing derivation. On the other hand, the deterministic approach (triples are redirected to a specific node according to their key) is efficient as triples that will lead to derivations are located on the same node, but at the cost of highly unbalanced workloads for skewed data set distributions. Marvin achieves a balance between random and deterministic approach, combining load balancing with efficient derivation. The implemented SpeedDate algorithm swaps triples within a neighborhood of nodes, thus popular keys are distributed over several nodes, and provides a certain degree of determinism as triples are constantly located within a restricted subset of nodes.

• ∙ Theoretical properties: Soundness and completeness depends on the used reasoner (as an external library).

Reported scalability The authors studied various metrics by providing simulated results. Simulations deal with the number of nodes, number of items in the system, various data distributions, node availability during the reasoning process, recall, load balancing and scalability. The system is more efficient compared to the random approach, showing similar load balancing properties and is more scalable compared to the deterministic approach, thus able to utilize higher degree of parallelization. Considering scalability, the average throughput per node follows a square root curve with respect to the number of items. Subsequently, authors provide experiments on real RDF data. Despite platform’s overhead, the system reached a throughput of 2.3 million triples s^˗1 on 32 nodes, when no reasoning was applied. However, when reasoning process is included, the system is shown to scale to up to 64 nodes processing data sets of up to 14.9 million triples. In addition, Marvin shows sublinear speedups (reaching a speedup of 12.94 on 64 nodes), while performing better when low tolerance to duplicates is allowed. In Kotoulas et al. (Reference Kotoulas, Oren and van Harmelen2010), the evaluation was extended to 64 computing nodes and data sets with up to 200 million triples and resulted in an overall throughput of 450 thousand triples s^˗1.

In Weaver and Hendler (Reference Weaver and Hendler2009), the authors identify an property of RDFS reasoning; This makes the embarrassingly parallelism of materialization on RDFS ontologies possible, that is, the derived results can be partitioned into independent and fairly even parts.

Target formalism The work considers incomplete RDFS reasoning.

Supported reasoning tasks The authors use this property to optimize the efficiency of materialization based on forward chaining reasoning.

Algorithm The authors find that the RDFS rule set implies a special property (called ABox Partition Safe) that makes the embarrassingly parallelism possible for the materialization of RDFS ontologies. We use the following figure to simply show this property. The triples in an RDFS ontology can be categorized into two parts:schema (or ontological) triples (see Figure 3, the gray part in each processor) and instance (or assertion) triples (the white part). All RDFS rules contain at most one instance triple pattern in rule body. On the other hand, the assumption that schema triples tend to be a fixed part in ontologies is always reasonable. Thus, the main algorithm parallelizes the schema triples to all processors and partitions the assertion triples into fairly even parts and distributes them to different processors (for example, the derived triples from the processor P ₁ are partitioned evenly for all processors). The authors further prove that the partition schema (called ABox partition schema) is correct in each iteration of materialization.

Figure 3

The ABox partition schema

Theoretical limits: The proposed property makes it possible for data partition. However some limits exist when handling other languages. It is not hard to show that this property does not hold in other languages with richer expressive power, like pD* and OWL 2 RL. On the other hand, LUBM is a simply structured manual data set and includes a very small part of schema triples. This is also an important factor that makes the method given in this paper work. No report on real data sets is presented in this work.

Implementation The authors implement their system based on a memory-based cluster with 128 allocated cores (namely a multi-thread system). The system is coded by C\MPI—a parallel data processing interface. This implementation is evaluated on a popular benchmark LUMB.

Reported scalability The purpose of the experiments in this work is to evaluate the scalability of the above implementation. A version of LUMB ontology containing about 650 million triples is used as the test data set. The experimental results show that materialization time increases linearly on the multiplied threads. For the whole data set, the implementation takes 8 min for materialization. For ensuring the parallelism, the system does not eliminate the duplicate triples globally. The authors also set an experiment to show such duplicates tend to be halved when the data set doubles in size.

In Goodman et al. (Reference Goodman, Jimenez, Mizell, al Saffar, Adolf and Haglin2011) authors study RDFS reasoning over a shared-memory machine with multithreaded processors.

Target formalism The proposed method presents a parallel approach for RDFS reasoning.

Supported reasoning tasks The proposed approach deals with dictionary encoding, RDFS closure computation and SPARQL query processing.

Algorithm This work is based on in-memory processing of RDFS triples using multithreading, describing technical details that pertain to the underlying model.

Implementation All processes are performed completely in-memory by utilizing the global shared-memory, on the Cray XMT supercomputer. In particular, authors present an algorithm for encoding RDFS triples, represented in N-Triples or N-Quads format, into a set of 64-bit integers, thus mapping strings into integers. Dictionary encoding is highly optimized for parallel processing while the final representation consists of triples encoded as integer values, and the mappings from each unique string to its corresponding integer value and vice versa. This in-memory representation is used for RDFS closure computation.

RDFS closure is based on a previously presented algorithm, although the approach is altered in order to reduce memory usage. Specifically, triples are stored in a global hash table, with the new approach optimizing the use of hash key values in order to include information about the availability of each slot. In addition, RDFS reasoning is based on processing the entire data set instead of using queues that contain matching triples for each rule. Subsequently, RDFS closure is transformed into a graph representation to facilitate SPARQL query answering. An algorithm called Sprinkle SPARQL is used in order to identify matching triples and calculate final results by combining all intermediate results.

Reported scalability Experimental results show that the system is able to scale up to 512 processors while handling 20 billion triples completely in-memory using the Cray XMT supercomputer. In particular, dictionary encoding handled up to 16.5 billion triples, coming with compression ratio ranging from 3.2 to 4.4, speedups ranging from 2.4 to 3.3, and throughput of up to 561 MB/s. RDFS closure generated 20.1 billion unique triples, requiring 40% less memory at the cost of a 11% to 33% increase in computation time, with speedups ranging from 6 to 9, and throughput of 13.7 (resp. 21.7) million inferences s^˗1 including (resp. ignoring) I/O. SPARQL queries showed speedups ranging from 4.3 to 28 for complicated queries, while authors point out the fact that Sprinkle SPARQL did not outperform all evaluated alternatives, for simple queries, as it comes with a significant overhead.

In Salvadores et al. (Reference Salvadores, Correndo, Harris, Gibbins and Shadbolt2011), the author presents a backward-chaining system to perform minimal RDFS reasoning on top of 4Store, a distributed RDF storage engine.

Target formalism The work considers incomplete RDFS reasoning.

Supported reasoning tasks This work considers query-driven inference (also called backtrack-chaining or query rewriting).

Algorithm In 4Store, data is distributed in non-overlapping segments which are evenly distributed across the peers, while terminological knowledge is replicated on all nodes. This allows the system to perform reasoning without any inter-node communication.

Whenever a query must be processed, each node rewrites it in multiple queries exploiting the terminological knowledge that is available locally. Since the rules in the minimal RDFS segment are rather simple, this process can be carried out efficiently by chaining the subqueries.

Implementation The method is implemented inside the Java engine 4Store. The development of the system seems to be discontinued.

Reported scalability An experimental evaluation was carried out using the LUBM (Guo et al., Reference Guo, Pan and Heflin2005) data set and up to 5 machines. As inputs, the authors used a number of data sets with a number of triples between 13 to 138 million triples and 5 atomic queries. The system produced derivations between 150 and 300 thousands triples s^˗1, but unfortunately no comparison with other systems was performed.

Hoeksema and Kotoulas (Reference Hoeksema and Kotoulas2011) studies stream reasoning over RDF data and C-SPARQL query answering using Yahoo S4Footnote ⁹ .

Target formalism This work deals with distributed stream reasoning over RDFS.

Supported reasoning tasks The presented method is focused on stream reasoning over RDF data and C-SPARQL query answering.

Algorithm The authors first introduce a naive RDFS reasoning process over Yahoo S4 and point out several issues considering performance. Such issues include the minimization of stored triples and join operations that do not lead to inference, incompleteness of the reasoning process and duplicate elimination. Subsequently, an efficient RDFS reasoning is presented providing the description of components for duplicate elimination, for analysis and distribution of unique triples, and components that compute RDFS rules.

Implementation Reasoning process feeds triples to C-SPARQL query processing, where a number of components dealing with different aspects of a C-SPARQL query is defined. In particular, authors describe components that provide variable bindings for matched query patterns, perform joins on variables in the query, filter incoming bindings and emit the final results in the required format. Authors also discuss the two types of windows supported by C-SPARQL, namely a window comprises of either a fixed number of triples or a fixed period of time during which triples are entering the stream. The latter approach is chosen as it is more appropriate given a distributed setting. Triples that enter the system are assigned a timestamp and an expiration time, while triples that are derived again after their expiration are reassigned their corresponding timestamps. Moreover, authors describe several components that support aggregates such as SUM, AVG, COUNT, MIN and MAX.

• ∙ Theoretical properties: The process is based on eventual completeness, namely the system gradually increases its knowledge until no new knowledge can be added.

Reported scalability The system is evaluated based on two metrics, namely maximum throughput in terms of triples per second (with maximum supported throughput of 160 000 triples s^˗1) and the number of processing nodes. When no reasoning is performed and the applied query passes through any given triple (passthrough query), high throughput is achieved even with three nodes showing linear performance. However, when RDFS reasoning is performed over the passthrough query, the system is showed to scale up to 8 nodes, but it is unclear why linear performance is not retained for 16 and 32 nodes. In addition, two queries are considered where no RDFS reasoning is applied. For both queries linear performance is reported for up to eight compute nodes.

The authors of Heino and Pan (Reference Heino and Pan2012) report their work on RDFS reasoning on massively parallel hardware.

Target formalism The authors of this work focus on RDFS reasoning.

Supported reasoning tasks The target reasoning task is materialization.

Algorithm Their approach uses forward chaining based on the six RDFS entailment rules. Their evaluation uses two real-world data sets, DBPedia and YAGO2 Core. To improve efficiency and scalability, a few optimizations have been employed, such as encoding the strings in RDFS document into 64-bit integers.

Implementation The approach has been implemented in both multi-core CPU and multi-core GPU with shared main memory. The CPU implementation uses 4 8-core CPUs and the GPU implementation uses a 20-core GPU.

Reported scalability Evaluation shows that when double the CPU cores used, the CPU kernal time is reduced by half, with up to 16 cores. It also shows an interesting comparison between the CPU implementation and the GPU implementation, in which the latter has a shorter kernal time but longer overall time. The authors explain that this is because GPU has more cores but the data needs to be copied back and forth between the main memory and GPU’s global memory.

DynamiTE (Urbani et al., Reference Urbani, Margara, Jacobs, van Harmelen and Bal2013) is a parallel engine that performs materialization of inference considering the minimal RDF fragment.

Target formalism DynamiTE focuses on maintaining the materialization obtained with the rules in the minimal RDFS fragment in Muñoz et al. (Reference Muñoz, Pérez and Gutierrez2009).

Supported reasoning tasks The system first performs a full materialization (when the data is initially loaded into the system) and then incrementally updates the materialization after new data is added or removed.

Algorithm The full materialization is executed using standard datalog semi-naive evaluation. The incremental updates can be executed either using D-Red, presented in Gupta et al. (Reference Gupta, Mumick and Subrahmanian1993), or with a bookeeping algorithm that stores counters next to each derivations.

Implementation The system is implemented in Java and exploits multi-core parallelism. The KB is indexed on various permutations of the triples and stored on disk using multiple B-Tree data structures.

Reported scalability The system was evaluated using LUBM benchmark data sets presented in Guo et al. (Reference Guo, Pan and Heflin2005) with up to one billion triples. The performance was compared against WebPIE and the results indicated that DymamiTE was able to produce higher throughputs due to less overhead. The best performance was obtained with the counting algorithm. Unfortunately, this algorithm does not work properly with recursive rules as discussed in Motik et al. (Reference Motik, Nenov, Piro and Horrocks2015).

5.2 Datalog, OWL Horst and OWL 2 RL

Soma and Prasanna (Reference Soma and Prasanna2008) studies how reasoning on OWL KBs can be parallelized with balanced workload.

Target formalism The presented approach targets reasoning over OWL Horst.

Supported reasoning tasks This work is focused on the materialization of OWL Horst KBs.

Algorithm Two parallelization techniques are explored, namely rule partitioning and data partitioning. For the case of rule partitioning, each node in the cluster is responsible for the computation of a subset of rules, for a given rule set. Thus, the workload per rule (and node) depends both on the structure of the rule set and the number of rules, therefore, balanced workload is difficult to be achieved. On the contrary, for the case of data partitioning, data is divided into subsets with each subset being assigned to a node, allowing more balanced distribution of the computation among nodes.

In order to evaluate the effectiveness of each partitioning approach, authors proposed certain metrics. Balanced partitioning is achieved when each processor is assigned an equal amount of work, and consequently all processors finish their work simultaneously, thus no processor remains idle (wasting computational power). Inevitably, processors should be synchronized exchanging information, thus the system should minimize communication between processors, namely each processor needs to be as independent as possible. Efficiency, in the context of reasoning, refers to the number of duplicates produced during the inference process. To achieve optimal efficiency each conclusion must be derived by exactly one processor. Speed and scalability evaluate the partitioning process itself. The chosen partitioning approach should be fast and have the potential to scale for large data sets.

Implementation The implementation was based on Java, using Jena as an external reasoner.

Reported scalability Experimental results, computing OWL Horst closure, over millions of triples, on a cluster of machines over P2P communication using Jena reasoner and examining both techniques, are reported. For data partitioning, authors observed both super-linear and sub-linear speedups, depending on the evaluated data set over the graph partitioning algorithm. Moreover, as the number of partitions increases, the time spent in inter-process communication and synchronization increases respectively. In addition, results indicate that graph and domain specific partitioning have a relatively close performance since they produce balanced partitions, while a naive hash based partitioning performs badly due to imbalanced partitions. For rule based partitioning, evaluation shows sub-linear but monotonic speedups. However, the used rule sets were small and thus only a small number of processors could be used.

WebPIE presented in Urbani et al. (Reference Urbani, Kotoulas, Maassen, van Harmelen and Bal2010) and Urbani et al. (Reference Urbani, Kotoulas, Maassen, Van Harmelen and Bal2012b) is a distributed forward-chaining reasoner that relies on the MapReduce primitives to distribute and parallelize the computation. The system is implemented on top of the Hadoop framework and supports reasoning with some RDFS and OWL Horst rules.

Target formalism Reasoning is executed using almost all RDFS rules and the OWL Horst rules.

Supported reasoning tasks The system performs a full materialization of the KB.

Algorithm WebPIE implements intra-query parallelism: that is, the evaluation of each rule is performed in parallel. The parallelism consists of partitioning the input in several chunks and processing each chunk by a different processor. The initial version of WebPIE supported only partial RDFS reasoning, but later it was extended to support the Horst fragment. The research contribution consisted in showing how certain rules could be evaluated efficiently with MapReduce by exploiting certain properties of current data sets (i.e. a relatively small size of terminological knowledge compared to the assertional one).

Implementation Each rule is encoded using the MapReduce primitives, and executed with one or more Hadoop programs. The system reads in input a series of (compressed) RDF triples, performs the materialization, and returns another list of files which contains the inferred triples. Each rule is hardcoded, therefore the system cannot be easily extended to more rules.

Reported scalability WebPIE is the system which has shown the best scalability so far. In the largest experiments, it was able to compute the materialization of 100 billion triples. The system however suffers of two major limitations: First, it cannot be quickly extended to other rulesets since each rule is hardcoded in the program. Second, the system does not index the derivation. This means that after the computation of WebPIE is finished, the user must load its output into a RDF engine in order to query the results efficiently.

The authors of Hogan et al. (Reference Hogan, Pan, Polleres and Decker2010) discuss optimizations of rule-based materialization approaches for reasoning over large static RDF data sets.

Target formalism The considered languages include RDFS, pD* (OWL Horst) and OWL 2 RL.

Supported reasoning tasks The target reasoning task is forward reasoning.

Algorithm The authors generalize and formalize the notion of partial indexing techniques which are optimized for application of linear rules and which rely on a separation of terminological data. Due to their focus on the linear rules in RDFs, pD* and OWL 2 RL rule set, many of the rule executions can be perfectly parallelized.

Implementation A reasoner called SAOR is implemented based on a distributed platform.

Reported scalability In their evaluation, they show that the time required for most expensive tasks such as TBox extraction and ABox reasoning decreased by half when the number of machines doubled.

In Kolovski et al. (Reference Kolovski, Wu and Eadon2010), the authors present efficient optimization techniques for the inference of OWL RL using Oracle Databases.

Target formalism OWL RL is the focus language of this work.

Supported reasoning tasks The methods proposed in this work mainly aim at forward chaining reasoning of OWL RL.

Algorithm Three important topics are addressed: compact materialization of equivalence closures, incremental maintenance of inferred closure and parallel inference. A novel hybrid (memory and disk-based) approach is developed for building large-scale owl:sameAs cliques and applicable to other equivalence relations such as owl:equivalentClass and owl:equivalentProperty. Batches of owl:sameAs assertions are first loaded from input table, then merged in memory and appended to the cliques. Then similar batch processing is employed on the cliques table, merging where needed, until a fix-point is reached.

Implementation The above method is implemented on an Oracle database. To make full utilizations of modern hardware with multiple CPUs and high I/O throughput capacities, The authors give a technique called break-up to simplify complex and multi-pattern rules. Other optimizations that are used to ensure efficiency include the introduction of source table, the usage of 8-byte binary RAW type and the perfect reverse hashing. The authors apply lazy duplicate elimination strategy during the process of incremental inference which indicated through the experiment that the duplicate overhead is acceptable. A heuristic method called dynamic semi-naive evaluation is adopted which could dramatically improve the performance of incremental inference.

Reported scalability The algorithm has time complexity $$O(n\log n)$$ and achieves almost linear performance from experiments.

The authors of Bonatti et al. (Reference Bonatti, Hogan, Polleres and Sauro2011) leverage annotated logic programs to incorporate provenance and trust in linked data reasoning.

Target formalism The authors annotate whether a piece of linked data should be trusted, ignored or used with a numeric ranking in a reasoning procedure that employs part of the OWL 2 RL/RDF rule set.

Supported reasoning tasks The target reasoning task is forward reasoning on the annotated linked data.

Algorithm In addition to a number of desired formal properties such as monotonicity and decidability, the algorithm is designed based on a shared-nothing distributed architecture to support large-scale linked data. In this architecture, a master machine is used to partition the data and task, to request tasks executions, to pull tasks results and to broadcast global knowledge. A number of slave machines are used to execute concrete tasks and can exchange data between each other when necessary. Each slave machine is assigned with an approximately equal number of triples/quads.

Due to the design of the approach, most of the expensive tasks can be performed in an embarrassingly parallel manner, significantly reducing the data exchange between slave machines.

Implementation A prototype system is implemented based on a shared-nothing distributed platform where several independent machines are involved.

Reported scalability The behaviour of embarrassing parallelism has also been observed in evaluation, in which a data set of 1.11 billion triples/quads is used. Evaluation shows that, the distributed reasoning and inconsistency checking time is reduced, on average, by 40%−50% when the number of slaves is doubled. The speed up for distributed ranking is less significant. The reduction of ranking time diminishes when more and more slaves are used.

QueryPIE presented in Urbani et al. (Reference Urbani, van Harmelen, Schlobach and Bal2011) and Urbani, Piro, et al. (Reference Urbani, Piro, van Harmelen and Bal2014) is a backward-chaining, top-down reasoner that supports OWL Horst and partial OWL 2 RL/RDF. The computation can be performed either on a single, multi-core machine, or be distributed across several machines that communicate to each others using a message passing library.

Target formalism The system focuses on generic datalog but it is primarily evaluated using the pD* and OWL 2 RL rulesets.

Supported reasoning tasks The system performs datalog query-driven evaluation using a top-down approach.

Algorithm The system implements two major contributions: a permanent tabling technique (which is rebranded as hybrid reasoning in Urbani, Prio, et al. (Reference Urbani, Piro, van Harmelen and Bal2014), and a parallel variant of the well-known QSQ-R algorithm in Abiteboul et al. (Reference Abiteboul, Hull and Vianu1995).

The tabling technique consists in materializing a consistent part of the terminological knowledge and indexing it in main-memory so that it can be retrieved quickly. This pre-materialization is useful to prune the search space at query-time and reduces the inference process to the calculation of only assertional data.

The parallel variant of QSQ is introduced to speed up the top-down evaluation of the rules. The parallelism is inter-query: this means that the system evaluates several rules concurrently and synchronization is introduced only during few stages. The algorithm presented in (Urbani et al., Reference Urbani, van Harmelen, Schlobach and Bal2011) is incomplete (interestingly, the source of incompleteness is the same that affected the original presentation of QSQR). The algorithm was later fixed in Urbani, Prio, et al. (Reference Urbani, Piro, van Harmelen and Bal2014). In subsequent work, some of the original authors interleaved sequential execution with parallel ones. The sequential code is reserved for “hard” rules which require joins between multiple intensional predicates. Simpler rules, which only require either no join or only joins between extensional and intensional predicates, are executed in parallel.

Implementation The system is implemented in Java. It relies on a distributed computing framework, called Ajira in Urbani, Margara, et al. (Reference Urbani, Margara, Jacobs, Voulgaris and Bal2014), to execute the computation in parallel.

Reported scalability The work in Urbani, Prio, et al. (Reference Urbani, Piro, van Harmelen and Bal2014) reports the execution of single-pattern queries using a LUBM data set of 10 billions triples on a single machine. Later, another evaluation was conducted on multi-pattern queries in Urbani and Jacobs (Reference Urbani and Jacobs2015). In terms of input size, this system scales well since it can handle KBs with billions of triples. However, its main limitation is that it stores the inferred tuples in main memory, and this precludes the execution of queries which produce a number of intermediate answers whose size exceeds the available main memory.

The authors of Aslani and Haarslev (Reference Aslani and Haarslev2012) present an empirical evaluation of a parallel TBox classification algorithm. In this approach, multiple threads work together to construct a shared global taxonomy.

Target formalism The method proposed in this work covers the DL $${\cal S}{\scr H}{\scr I}{\cal Q}$$ . Some optimizations are also discussed for $${\scr E}{\scr L}$$ .

Supported reasoning tasks The target reasoning task is classification on TBoxes.

Algorithm To start with, each thread is assigned with a partition, that is, a set of concepts, in a round-robin manner. Then for each of the assigned concept, the thread will try to find its least super-concepts in a top-down manner, starting from the Τ concept, and its most sub-concepts in a bottom-up manner, starting from the ⊥ concept. For each candidate super/sub-concept, the tread will run a subsumption test to verify the relationship. In order to avoid thread locking, the concurrent collections from the java.util.concurrent are employed to maintain the global taxonomy and other shared data structures. By doing this, the threads can achieve concurrent classification without having to wait for each other.

This mechanism is designed to be independent from the concrete classification mechanism used. Hence, it is applicable to a wide range of representations. Nevertheless, it requires the existence of a subsumption testing algorithm and such an algorithm will be executed by each thread to test concept inclusions. Therefore, the approach cannot provide parallel subsumption checking. Each thread is assigned with approximately equal numbers of concepts to classify. This does not necessarily imply balanced workload because some concepts may require more computation efforts than the others to classify.

Implementation A prototype system is implemented using multi-threads.

Reported scalability In evaluation a number of ontologies with different expressivities and different sizes are tested, the largest one being the SNOMED CT ontology with 379,691 concepts. For each ontology, the evaluation runs the implemented approach with different number of threads (1,2,4) and different partition sizes (5,25) for each thread.

The evaluation shows that the approach has good CPU time improvement performance. When increasing the number of threads or the size of partition, the speed-up (non-parallel classification time in comparison to parallel classification) is approximately increased in a linear manner. Also, increasing the size of the ontology will not significantly affect the speed up.

The authors of Martínez-Angeles et al. (Reference Martínez-Angeles, Dutra, Costa and Buenabad-Chavez2013) exploit the strength of GPUs on highly parallelizable computations, and present an approach of parallelizing datalog bottom-up materialization on GPUs. The most remarkable contribution of this work is that it gives a memory management schema to reduce the transfers between host (CPU) memory and GPU memory.

Target formalism General datalog programs are studied. Ontology languages are not considered in this work.

Supported reasoning tasks This work explores the possibility of using GPUs for enhance bottom-up materialization of datalog programs.

Algorithm The authors implement three relational operations: selection, join and projection. The main algorithm of datalog reasoning is implemented based on these three operations. Specifically, for applying a rule, selection operations are performed on body atoms; join operations are then performed on the selected tuples using the indexed nested loop join algorithm; finally, projection operations retain the useful columns of the temporary relation table according to the variables in the head atom.

It is relatively easy to implement the three relational operations on GPUs, where the main challenge is how to reduce the transfers between GPU memory and CPU memory. The authors give a cache-like method to tackle this issue: a fact list is being maintained, which records all facts being loaded in GPU memory. When a new fact is loaded, its corresponding item is moved to the beginning of the list, or created if no such item exists. The facts at the end of the lists may be deallocated for new facts when memory space is not enough.

The parallelism pattern essentially relies on the mechanism of GPU, that is, a “single operation, massive data processing” pattern. The most critical operation for bottom-up materialization is joining. A basic join operation can be formulated as $$R_{1} (\vec {t}_{1} ) \triangleright \triangleleft R_{2} (\vec {t}_{2} )$$ , where R ₁, R ₂ are two relational names and t⃑ ₁ and t⃑ ₂ are the corresponding argument vectors. When performing joining, each pair of the tuples from R ₁ and R ₂ will be processed by a GPU thread, so that all pairs are processed concurrently.

Implementation A prototype system is implemented based on a GPU server. It is an in-memory system.

Reported scalability The purpose of evaluation is to compare the GPU implementation and the CPU implementation. The evaluations are performed on three designed queries. The experimental results show that the performance on a GPU has a significant improvement compared to that on a single CPU. However these three queries are all evaluated on synthetic data sets. These data sets aim at special situations (for example transitive closure computation) and of which the number of facts stays below millions. This throws two unanswered questions: 1) does this method work in practical cases? 2) what is the upper bound of the data volume that this method can handle?

The authors of Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014) propose an approach for parallelizing materialization of datalog programs. It covers general datalog programs and is further adapted to OWL languages, such as OWL 2 RL.

Target formalism The proposed method and the implemented system handle general datalog materialization. RDFS and OWL 2 RL are also covered in this work.

Supported reasoning tasks Forward chaining materialization on datalog programs is studied.

Algorithm The authors extend the classical datalog materialization algorithm, that is, the semi-naive algorithm (Abiteboul et al., Reference Abiteboul, Hull and Vianu1995), to a parallel variant. They give a strategy of indexing RDF triples in memory. This indexing strategy leads to efficient join operations. The following process briefly describes the algorithm:

1. (a) Step 1. Initially, a global iterator is provided, in which all facts (including the newly added ones) are ordered according to a strict total order.

2. (b) Step 2. Any free thread captures a fact F from the global iterator and attempts to match it to the body atoms in all rules. For example, when a thread is applying the rule (1), it attempts to match F to each B _i (1 ≤ i ≤ n), and all B _j where j<i (resp. j ≥ i) can only be matched to the facts having a lower (resp. Higher or equal) order than B _i .

3. (c) Step 3. Step 2 is repeated until all threads generate no more facts.

The global order helps to avoid generating redundant facts. The other critical issue for this method is how to implement the operations of accessing facts through the global iterator, inserting new facts and checking if a new fact is already existing. In this work, the authors propose a new indexing strategy for RDF triples, which results in highly efficient join operations.

In the core of the materialization algorithm, any free thread obtains the next fact from the global iterator and applies rules on a specific fact set. We give an intuitive algorithm snapshoot in Figure 4 to clarify the parallelism strategy: Thread1 obtains a fact F _i from the iterator. Then, it matches the set of facts with lower orders than F _i (including F _i ) to the rules. Since F _i has to be bound to a body atom for all rules, no repeat matching would be performed by other threads. This strategy makes the workload being partitioned relatively even and different threads share a minimum of connects.

Figure 4

Parallelizing materialization of a datalog program

Implementation A system called RDFox is developed for testing concurrency overhead and scalability. It is essentially an OWL 2 RL management system based on datalog programs. It is an in-memory reasoner.

Implementation limits: The proposed method strategy cannot be prioritized for distributed computing, since it is difficult to maintain a global order on facts when computation nodes share nothing.

Reported scalability The purpose of evaluation is to examine concurrency overhead and scalability of RDFox. The test data sets are LUBM data sets and DBpedia. The experimental results show that: first, RDFox performs better than other serial systems both on materialization and data importing on most data sets; second, the fraction of the work performed in parallel ranges from 88% to 98% when 32 threads are available (according to Amdahl’s law). This means in most cases, parallelizing reasoning pays off; third, in practice, the memory-based approach is sufficient for real data sets like DBpedia. However, from the proposed results, there are still cases when memory goes to exhaustion, such as the test on LUBM_5K (containing about 691.1M triples) with 32 threads being allocated. The main reason is the algorithm leads to the memory usage increasing with the number of threads.

Reasoning on Spark in Kim and Park (Reference Kim and Park2015) (RSPARK henceforth) is a system that was designed to perform forward-chaining reasoning on the Spark, presented in Zaharia et al. (Reference Zaharia, Chowdhury, Franklin, Shenker and Stoica2010), ecosystem. The goal and functioning of this system are very similar to WebPIE and the only difference relates to the used infrastructure (Hadoop for WebPIE, and Spark for RSPARK).

Target formalism Like WebPIE, also this system targets the rules in the RDFS and OWL Horst fragments.

Supported reasoning tasks The system performs a full materialization of the KB.

Algorithm The system performs TBox reasoning (i.e. executes only rules that derive new schema), and then performs ABox reasoning (i.e. executes all other rules). RSPARK executes the rules one-at-the-time. Before doing so, it re-orders the execution order of the rules to reduce the possibility that inference derived at a later stage can serve as input of rules already executed. The rules that perform TBox reasoning are executed only once. This means that the reasoner can potentially be incomplete because it will be unable to produce TBox inference which required some ABox inference first.

Implementation In order to execute the rules, the system represents the triples into <key, value pairs which are then stored in resilient distributed data sets (RDDs). RDDs are the data structures which are manipulated by the Spark’s operators. Overall, the functioning is similar than the one proposed in WebPIE, with the only difference that Spark is a more efficient framework. Interestingly, it appears that this system does not perform dictionary encoding and works directly on raw strings.

Reported scalability The system was evaluated using a KB of about 860 million triples and its performance on this input was compared with WebPIE. The results show that the system is about three times faster. Unfortunately, the evaluation in Kim and Park (Reference Kim and Park2015) was conducted with only five machines. It is not clear how the system would scale either with a larger cluster or with larger data sets.

Large Knowledge Graphs. In Thirtieth AAAI Conference on Articial Intelligence. The last system that we cover in this section is VLog presented in Urbani et al. (Reference Urbani, Jacobs and Kr¶tzsch2016). VLog is a recent reasoner which was designed to perform datalog evaluation on large knowledge graphs. The principal characteristic of VLog is that is uses relatively fewer resources than the other engines to compute the derivation. This allows its usage on machines equipped with commodity hardware. For instance, the authors showed that it is possible to compute the materialization of 0.5B LUBM triples using a normal laptop.

Target formalism VLog implements standard datalog reasoning. Therefore, it can execute rules in the RDFS fragment or OWL RL.

Supported reasoning tasks VLog performs a full materialization of the KB.

Algorithm The main novelty of VLog is that it adopts a columnar storage strategy to store the inferenced tuples. With such approach, the tuples are stored column-by-column rather than row-by-row. This strategy is good for compression since the system can apply well-known database techniques like runtime length encoding (RLE) or standard delta encoding. Furthermore, in some cases columns can be reused for different predicates. These optimizations effectivily reduce the space required to store the inference. One major problem of this approach is that columnar stores perform poorly with updates. To overcome this limitation, VLog avoids the insertion of new elements in existing tables and creates new tables instead. This causes a problem during the rules execution since multiple tables must be merged: To reduce the number of merges, the system performs a sort of back-tracking reasoning to infer whether a table can lead to new inference. The merge is avoided whenever the system determines this is not the case.

Implementation VLog is implemented in C++. The system is neither parallel nor distributed. It can interface to several backend to retrieve the input for the datalog computation. So far, it can interface with Trident (an in-house graph engine), MySQL and MonetDB—two popular DBMS.

Reported scalability VLog is superior to the other competitors in terms of main memory consumption. In Urbani et al. (Reference Urbani, Jacobs and Kr¶tzsch2016), the author compare the performance with RDFox on fairly large KBs (up to 0.5B triples) and show how the system uses much less main memory. In its current version, VLog has two main limitations: First, reasoning is sequential and hence the scalability is limited only to the speed of the CPU, while parallel approaches can scale on two dimensions—CPU and number of CPUs. Second, the system performs only a limited indexing on the materialized inference, which means that data might need further processing before it can be efficiently queried.

5.3 Description logics

The authors in Liebig and Müller (Reference Liebig and Müller2007) propose a parallel tableaux algorithm for $${\cal S}{\scr H}{\cal N}$$ reasoning and extend the work to $${\cal S}{\scr H}{\scr I}{\cal Q}$$ in Liebig et al. (Reference Liebig, Steigmiller and Noppens2010).

Target formalism The DL $${\cal S}{\scr H}{\scr I}{\cal Q}$$ is studied in this work.

Supported reasoning tasks The main reasoning task is to check concept satisfiability. On the other hand, most reasoning tasks can be reduced to the task of checking satisfiability.

Algorithm Tableaux algorithm plays an important role in solving the problem of concept satisfiability. A tableau prover tries to create a model for a given ABox. The proving is actually a procedure of building a tree with different expanded ABoxes being as the tree nodes, while the original given ABox being as the root node. In each node, reasoning rules are being applied to create new branches. For example, we use the following figure to show the work of the disjunction rule (Figure 5).

Figure 5

The disjunction rule

The above disjunction rule says, if for an individual a the assertion $$a\,\colon\,C\,\sqcup\,D$$ is in the ABox, then there are two possible ABoxes: either with C or with D. Thus the two possible ABox candidates (in this case, A ^' and A ^'′) are created as the successors.

The branching procedure in tableaux proofs naturally indicates a parallel schema: processing different branches concurrently. Since the ABox candidates at the same level of the tree are independent from each other, such a parallelism is theoretically reasonable. However the parallelism of this method strongly depends on the given cases. In other words, the number of rule applications determines the degree of the parallelism. Thus, it is also possible that, if no other ABox candidate is generated, the proving is then actually a serial procedure.

Implementation A reasoning implementation is proposed in Liebig and Müller (Reference Liebig and Müller2007) and extended in Liebig et al. (Reference Liebig, Steigmiller and Noppens2010), which is coded using C++.

Reported scalability Experimental evaluation was performed on several hardware settings showing good speedups for systems consisting of up to 4 cores. However, results on a server with 24 cores did not provide significantly higher speedups. Testing maximum cardinality restriction generated high number of alternatives, thus revealing that the overhead coming from synchronization may constitute a bottleneck. Similar speedup patterns were observed for the case of a realistic ontology. The evaluation of a disjunction of eight concepts showed step-wise speedups for increasing number of workers.

In Schlicht and Stuckenschmidt (Reference Schlicht and Stuckenschmidt2008), a distributed resolution technique for DL $${\cal A}{\scr L}{\cal C}$$ is proposed.

Target formalism The target DL is $${\cal A}{\scr L}{\cal C}$$ .

Supported reasoning tasks Distributed resolution technique is used to decide satisfiability.

Algorithm Ordered resolution is used, where literals are ordered and only one sequence of derivation is executed instead of trying all the possible literal sequences for resolving a clause. The given DL KB is assumed to be in the form of first order clauses. These clauses are grouped into modules based on an allocation function. Every module is saturated separately and newly derived clauses are propagated based on the allocation function. The procedure stops when an empty clause is derived in one of the modules or all the modules are saturated.

Implementation Implementation details are not provided.

Reported scalability Evaluation results are not provided.

The distributed resolution technique used for DL $${\cal A}{\scr L}{\cal C}$$ in Schlicht and Stuckenschmidt (Reference Schlicht and Stuckenschmidt2008) has been extended to $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}{\cal Q}$$ in Schlicht and Stuckenschmidt (Reference Schlicht and Stuckenschmidt2009).

Target formalism The target DL is $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}{\cal Q}$$ .

Supported reasoning tasks Satisfiability check and subsumption check are the supported reasoning tasks.

Algorithm The ordered resolution calculus used for $${\cal A}{\scr L}{\cal C}$$ cannot handle the equality literals introduced by number restrictions. Basic superposition, which is an extension of ordered resolution, was used here for $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}{\cal Q}$$ . In order to make it distributed, input clauses are partitioned across the cluster. A first order theorem prover runs on each machine of the cluster and it works only on the assigned clauses. Newly derived clauses are propagated to other provers if necessary.

Implementation Implementation is based on first order prover SPASSFootnote ¹⁰ . In order to make this a distributed reasoner, support for sending and receiving clauses has been added. All the reasoners are connected at startup and the clause communication is handled by separate processes. This helps to avoid blocking of the local reasoner after sending a clause.

Reported Scalability 13 ontologies from chemical, earth and environmental domain were used for testing. They contain 480 classes and 99 individuals. Translation to first order logic yields 930 clauses. Satisfiability check and subsumption check are performed on a group of 13 connected reasoners. The runtime for satisfiability checking is decreased by one third when compared to a single machine reasoner and answering a positive subsumption query takes only a quarter of time.

The use of the MapReduce framework to scale classification of $${\scr E}{\scr L}^{{\plus}} $$ ontologies has been attempted in Mutharaju et al. (Reference Mutharaju, Maier and Hitzler2010) and Zhou et al. (Reference Zhou, Qi, Liu, Mutharaju and Hitzler2016). Forward chaining rules from Baader et al. (Reference Baader, Lutz and Suntisrivaraporn2005) are used for classification. Ontologies are normalized, where axioms are reformulated to one of the fixed forms.

Target formalism $${\scr E}{\scr L}^{{\plus}} $$ is the DL that is supported in this work.

Supported reasoning tasks This work is about classification of $${\scr E}{\scr L}^{{\plus}} $$ ontologies.

Algorithm All axioms are represented as key-value pairs so that they are suitable for MapReduce implementation. The completion rules are also remodelled such that they can easily be represented in the form of map and reduce functions. All completion rules for classification involve either two-way joins or joins involving more than two operands. Rules involving more than two operands are split into two rules such that there are only two join operands. The algorithms for applying the rules are based on two functions: map and reduce. Map function gives out a key-value pair where the key is the join operand and reduce function groups all the key-value pairs that share the same key in order to perform the join.

Implementation Hadoop MapReduce was used for the implementation. Each rule corresponds to a MapReduce job. These jobs are run iteratively until no new output is produced. A separate MapReduce job takes care of removal of duplicate axioms.

Reported Scalability Experiments were run on a 14 node cluster with each node having 16GB RAM and two quad-core processors. Copies of Galen and SNOMED CT ontologies were used to test the scalability of the system. The biggest ontology that the system can handle is 3-SCT (three copies of SNOMED CT) which has around 3.5 million axioms and this can be classified in 1589 min (26 hours).

The MapReduce approach from Mutharaju et al. (Reference Mutharaju, Maier and Hitzler2010) has been extended to $${\scr E}{\scr L}^{{{\plus}{\plus}}} $$ in Maier et al. (Reference Maier, Mutharaju and Hitzler2010).

Target formalism $${\scr E}{\scr L}^{{{\plus}{\plus}}} $$ is supported in this work.

Supported reasoning tasks This work is about classification of $${\scr E}{\scr L}^{{{\plus}{\plus}}} $$ ontologies.

Algorithm In addition to the constructs provided by $${\scr E}{\scr L}^{{\plus}} $$ , nominals and bottom concept are supported. So, in addition to the classification rules from Mutharaju et al. (Reference Mutharaju, Maier and Hitzler2010), rules corresponding to nominals and bottom concept are included here. Some of the classification rules have been split to facilitate the division and distribution of work across machines. These rules are applied repeatedly on the axioms until no new output is generated.

Implementation Algorithms are described in terms of Hadoop MapReduce but concrete implementation details are not provided.

Reported Scalability Theoretical analysis of the best and worst case scenario for the speed-up gained by the use of a distributed framework such as MapReduce is discussed. However, no evaluation results are provided.

MapResolve in Schlicht and Stuckenschmidt (Reference Schlicht and Stuckenschmidt2011) analyzes the challenges of scalable reasoning that is based on the MapReduce framework.

Target formalism This method is focused on the satisfiability of $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}$$ . However, the authors report that the same method can be applied to first order theories as well.

Supported reasoning tasks MapResolve studies the satisfiability of the DL $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}$$ .

Algorithm The main challenge is the fact that in order to compute the closure, a sequence of MapReduce jobs is required as newly derived knowledge must be fed back to the system for further derivations, thus leading to repeated inferences. This issue is identified in existing approaches, for RDFS and OWL Horst materialization, and $${\scr E}{\scr L}^{{\plus}} $$ classification, which are based on MapReduce. Authors present a distributed resolution method for checking the satisfiability of $${\cal A}{\scr L}{\cal C}{\scr H}{\scr I}$$ , while the same method can be applied to first order theories as well. The provided naive approach for distributed DL resolution points out the problem of repeated inferences.

Implementation In order to overcome arising challenges, the authors follow a method where separate sets are maintained for clauses that have already been evaluated and clauses that still require rule application. At each MapReduce job, usable clauses are allocated during the map phase, while already evaluated clauses are loaded to each reducer for resolution. The reducer also deletes duplicate clauses and clauses that are subsumed by other clauses so as to further improve efficiency. At the end of the resolution process, both sets are stored for the next job. Authors deal with load balancing by distributing the set of usable clauses evenly among reducers. In addition, the number of usable clauses that are assigned to each reducer is adjusted after each job by taking into account the predicted and the actual runtime.

Reported scalability No experimental evaluation was provided, thus it is unclear if the minimization of repeated inferences is able to amortize the cost of storing and parsing the sets of clauses in every job.

Different from the conventional Tableau algorithms, the classification of OWL EL ontologies can proceed by applying a set of completion rules and has a polynomial complexity. A parallel, thread-safe classification implementation, ELK, for OWL EL is proposed in Kazakov et al. (Reference Kazakov, Krötzsch and Simancik2011).

Target formalism The authors of this work do not consider role chains. The target DL is $${\scr E}{\scr L}{\scr H}_{{R^{{\plus}} }} $$ where R ⁺ represents that transitive roles are allowed.

Supported reasoning tasks Classification of OWL EL ontologies are studied. Specifically, a set of completion rules are given. The task of classification is then transformed to the procedure of iteratively applying the completion rules.

Algorithm Classification is performed on a set of completion rules that avoids normalization and as well reduces the number of inferences compared to the rules in Baader et al. (Reference Baader, Brandt and Lutz2005). Two main optimization strategies are applied for enhancing efficiency: (1) Some rules are modified to eliminate redundant applications (specifically aiming at R _∃); (2) For a special subsumption query $$F\,\sqsubseteq\,G$$ , the rule applications are performed on a limited set of the axioms (so called reachable axioms) w.r.t. $$F\,\sqsubseteq\,G$$ .

The authors introduce a notion of “context” to implement a parallel saturation-based algorithm. The “context” in ELK means that different axioms (original or derived) may participate in different reasoning parts. For example, in context ₁, all rule applications are performed on the joins with A as the joint. Thus the axioms $$X\,\sqsubseteq\,A$$ or $$A\,\sqsubseteq\,\exists r.C$$ should be imported into this context, but not for $$X\,\sqsubseteq\,B$$ . Thus this parallel strategy is actually a joint-based partition (it also includes the cases of applying the rules with only one premise, since such premise can be treated as the one with a pseudo joint). Since each context is independent of any other, such a method on memory-based framework is thread safe.

Implementation The above algorithm is implemented on an in-memory server. The current version of ELK is an in-memory system.

Reported scalability Efficiency and scalability of ELK is evaluated. The test data sets are real-world ontologies expressed in OWL 2 EL. The experimental results show that it has the best performance on almost all ontologies. For example, it can classify SNOMED CT (containing nearly 300,000 axioms) in 10 s including loading time.

$${\cal D}{\frak e}{\frak s}{\frak l}{\frak o}{\frak g}$$ presented in Wu and Haarslev (Reference Wu and Haarslev2012) is a parallel tableau-based DL reasoner for $${\cal A}{\scr L}{\cal C}$$ , designed for thread-level parallelism.

Target formalism $${\scr D}{\frak e}{\frak s}{\frak l}{\frak o}{\frak g}$$ deals with the DL $${\cal A}{\scr L}{\cal C}$$ .

Supported reasoning tasks $${\cal D}{\frak e}{\frak s}{\frak l}{\frak o}{\frak g}$$ performs TBox classification for the DL $${\cal A}{\scr L}{\cal C}$$ .

Algorithm The algorithm is based on a multithread DL tableux algorithm. The description of $${\cal D}{\frak e}{\frak s}{\frak l}{\frak o}{\frak g}$$ is based mainly of its technical details in terms of implementation.

Implementation The inherent non-determinism of DL tableaux is utilized for parallel TBox classification on a shared-memory setting. Such non-determinism comes from disjunctions and qualified cardinality restrictions. The system consists of several components such as the pre-processing layer that translates the given OWL ontology into the internal representation, the reasoning engine layer that performs DL reasoning, the post-processing layer that processes the results and the infrastructure layer that supports auxiliary operations.

The system is implemented in Java and allows parallelization by introducing optimized data structures. The authors point out the fact that naive tree structures are not well placed for a shared-memory setting. Thus, a list-based structure called stage and a queue-based structure called stage pool are used for the storage of each non-deterministic branch and all branches in the tableau, respectively. Several optimization techniques, such as lazy-unfolding, axiom absorption, semantic branching, dependency directed backtracking and model merging, were studied for their suitability for a parallel implementation and were incorporated into the system. The authors discuss the introduced overhead due to thread management and highlight the need for efficient data structures that allow reasoning while minimizing the frequency of simultaneous access to shared data by multiple threads.

Reported scalability Experimental results indicate good scalability properties for TBox classification based on a multi-threading shared-memory model that is implemented in Java on a 16-core computer. Various data sets, of relatively small size, were considered with the number of axioms in each tested data set ranging from 45 to 1140. It is shown that for small inputs the overhead coming from parallelization due to threads manipulation and access to shared data affects significantly the performance. However, for larger inputs parallelization shows linear performance for up to 16 threads, while the authors stress the fact that reasoning performance remains stable for up to 32 threads, indicating that the system could potentially utilize a larger hardware setting. Opposite to the results for the shared-memory setting, the system did not perform well on a distributed setting as the maximum speedup was below 3 even when 16 processors were assigned on a high-performance computing cluster.

The parallel ABox classification described in Ren et al. (Reference Ren, Pan and Lee2012) is an extension to the procedure used to classify TBox in parallel by ELK in Kazakov et al. (Reference Kazakov, Krötzsch and Simancik2011).

Target formalism The target DL is $${\scr E}{\scr L}{\scr H}_{{ \bot ,R^{{\plus}} }} $$

Supported reasoning tasks ABox materialization is supported in this work.

Algorithm Classification rules similar to the ones in Baader et al. (Reference Baader, Lutz and Suntisrivaraporn2005) are used. But, normalization of ontologies is not required here. Axioms are assigned to contexts, in which inferences can be derived independently in parallel. ABox axioms can be internalized to TBox axioms and the procedure from Kazakov et al. (Reference Kazakov, Krötzsch and Simancik2011) can be used. But this is inefficient due to unnecessary computations. So the authors propose additional rules to cover the bottom concept and individuals.

Implementation Algorithms suitable for a parallel shared-memory machine were proposed and the implementation is in Java.

Reported Scalability Evaluation was done on an Amazon EC2 high-memory instance with 8 virtual cores and 60GB allocated to JVM. ABox axioms were generated for the TBox of NotGalen ontology. For around 1 million individuals and 9 million axioms, executiom time is about 3 min.

The classical DL cannot represent fuzzy information, which is available in some applications, such as multimedia and bioinformatics. Thus extending DL with the ability to handle fuzzy information is another way to enrich the expressive power. In Stoilos et al. (Reference Stoilos, Stamou and Pan2008), the authors propose a language fuzzy- $${\scr E}{\scr L}^{{\plus}} $$ that is a fuzzy extension of OWL EL by adding fuzzy values to the axioms. For example, an axiom $$pyrexia\,\sqsubseteq\,complication$$ is not a precise description since pyrexia is not always caused by a complication. Then we add a fuzzy value to this axiom like $$\langle pyrexia\,\sqsubseteq\,complication,0.6\rangle $$ to describe that under the possibility of the degree 0.6, pyrexia is caused by a complication.

Based on this extension, the classification of a fuzzy ontologies also includes the computation of fuzzy values. For example, the following rule is based on Gödel fuzzy logic in Stoilos et al. (Reference Stoilos, Stamou and Pan2008) (giving the minimum fuzzy value in the pre-conditions to the conclusion):

If $$\langle X\,\sqsubseteq\,Y,n\rangle $$ , $$\langle Y\,\sqsubseteq\,\exists r.Z,m\rangle $$ ,then $$\langle X\,\sqsubseteq\,\exists r.Z,\min (n,m)\rangle $$ .

Since the applications on fuzzy- $${\scr E}{\scr L}^{{\plus}} $$ faces the issue of handling large-scale data sets as well, developing a parallel classification algorithm has also become an appealing topic. In Zhou et al. (Reference Zhou, Qi, Liu, Hitzler and Mutharaju2012) and Zhou et al. (Reference Zhou, Qi and Suntisrivaraporn2013), the authors propose a classification algorithm of fuzzy- $${\scr E}{\scr L}^{{\plus}} $$ based on MapReduce, and evaluate it on real-world data sets such as SNOMED CT.

Target formalism A fuzzy extension of OWL EL, called fuzzy- $${\scr E}{\scr L}^{{\plus}} $$ , is studied in this work.

Supported reasoning tasks The proposed methods in this work aim at parallelizing classification of fuzzy- $${\scr E}{\scr L}^{{\plus}} $$ ontologies.

Algorithm The parallel strategy is joint-based partition. We use the above rule as an example (see Figure 6): the corresponding axioms (original or derived) are distributed among different nodes (or machines), and all the axioms sharing the same joint (Y in the rule) are grouped to the same node and matched according to the rule to derive new axioms.

Figure 6

A joint-based partition example

The algorithm is designed based on MapReduce. Parallelizing axioms corresponds to the map phase, while grouping relative axioms corresponds to the reduce phase. Since one MapReduce job can only perform one 2-way join, some rules should be equally split into several 2-way joins.

Implementation A system is implemented based on Hadoop MapReduce.

Reported scalability The test data sets are two real-world ontologies, Galen and SNOMED CT. The authors run their prototype system on a small cluster with eight nodes (all have basic configurations of 2 GB memory and 2 physical cores), and evaluate it on different copies of the original ontologies. A linear time speedup trend is shown by the tests on Galen. For SNOMED CT, the classification time cannot be consider acceptable even on a few copies of SNOMED CT. This also throws a question: is it necessary to classify TBoxes through distributing computation? Since TBoxes remain of fairly constant size in practice, the in-memory environment might be sufficient to meet the demand.

DistEL in Mutharaju et al. (Reference Mutharaju, Hitzler and Mateti2013) and Mutharaju et al. (Reference Mutharaju, Hitzler, Mateti and Lécué2015) is a distributed $${\scr E}{\scr L}^{{\plus}} $$ classifier, which uses a P2P model and rules from Baader et al. (Reference Baader, Lutz and Suntisrivaraporn2005) for classification.

Target formalism $${\scr E}{\scr L}^{{\plus}} $$ is the DL that is supported in this work.

Supported reasoning tasks Ontology classification is the supported reasoning task.

Algorithm There is a one-to-one correspondence between the classification rules and the type of axioms in the ontology. For example, only a particular rule can be applied on axioms of type $$A\,\sqsubseteq\,B$$ . The basic idea is the following: (i) split the ontology based on the axiom type among the machines in the cluster and (ii) let each machine apply the corresponding rule on the axioms local to it. There is no shared memory and the processes on different machines communicate by message passing. Classification task terminates when each of the processes running on the machines does not produce any new axiom. Barrier synchronization mechanism, where each process waits for the rest of the processes at the end of each iteration, is used to simplify termination detection. There is an uneven load distribution and due to barrier synchronization, there will be some busy nodes and several idle nodes. Work stealing is used to address this—idle nodes take some axioms from the busy nodes and process them locally.

Implementation Axioms are represented as key-value pairs and RedisFootnote ¹¹ is used as the key-value store. The corresponding source code is available from https://github.com/raghavam/DistEL. A P2P architectural model is used here.

Reported Scalability DistEL is evaluated on a cluster ranging from 8 nodes to 64 nodes. Biomedical ontologies such as GO and SNOMED CT, along its duplicates (SNOMEDx2, SNOMEDx3, SNOMEDx5) are used to test the scalability of the system. Traffic ontology from Dublin city is also used. The performance of DistEL is compared to single machine reasoners such as Pellet, ELK, jCEL, Snorocket, HermiT and FaCT++. On small to medium sized ontologies such as GO and SNOMED, the performance of the single machine reasoners is better. For rest of the large ontologies, single machine reasoners run out of memory but DistEL can classify them and it also shows reasonable speedup with increasing number of nodes.

Apart from the MapReduce and fixpoint iteration approach (DistEL), another approach is described in Mutharaju et al. (Reference Mutharaju, Hitzler and Mateti2014). A more detailed description of all the distributed $${\scr E}{\scr L}^{{\plus}} $$ reasoning approaches is given in Mutharaju (Reference Mutharaju2016).

Target formalism $${\scr E}{\scr L}^{{\plus}} $$ DL is supported in this work.

Supported reasoning tasks The reasoning task that is supported in this work is ontology classification.

Algorithm This is a queue based approach, where each concept in the given input ontology is assigned a queue. The rule to be applied depends on the next entry in the queue. The possible entries of the queues are the different axiom types of the ontology obtained after normalization. On single machine reasoners, this approach is more efficient than the fixpoint iteration method followed by the previous two approaches. But, this is not the case in a distributed setup. Axioms are distributed randomly across the machines in the cluster. Then, each machine follows the queue approach and communicates with other machines whenever necessary.

Implementation This approach, named DQuEL, is implemented in Java and a key-value store named Redis is used for storage. Source code is available from https://github.com/raghavam/DQuEL. Except for the termination process, the rest of the system follows a P2P model. A centralized termination process, known as termination controller, checks the queues on all the machines and if they are empty, the reasoning process on each machine is terminated.

Reported Scalability A cluster of 13 nodes is used for evaluation. Bio-medical ontologies such as GO, NCI, SNOMED CT along with 2-SNOMED were used as input ontologies. For larger ontologies such as SNOMED CT and 2-SNOMED, this approach turns out to be inefficient. One of the primary reasons for the inefficiency in this approach is that, unlike in distributed fixpoint iteration, batch processing of axioms is not possible in this approach.

5.4 Nonmonotonic reasoning

The majority of proposed approaches is mainly focused on monotonic reasoning. However, there has been work on nonmonotonic reasoning as well. In Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris and Kotoulas2012b) authors presented the first step towards scalable nonmonotonic reasoning, focusing on defeasible reasoning.

Target formalism The proposed method takes into consideration reasoning over defeasible logic with the restriction that each rule may have only one variable.

Supported reasoning tasks Materialization using forward-chaining is the main task of this approach.

Algorithm The main idea lies on the fact that there is only one variable in the body of the rule. Thus, all predicates of the body have a common argument on which they can be joined in order to decide on the applicability of the rule.

Implementation This method is implemented on MapReduce in order to facilitate large-scale grouping of facts that will lead to rules applicability. However, grouping facts is not sufficient for defeasible reasoning, and thus, an external reasoner implementing the defeasible logic algorithm is applied on each group of facts. The used reasoner implements propositional defeasible logic. Thus, deriving conclusions in order to compute the closure requires a combination of reasoner’s results for each group and the value of the variable for the corresponding group. Full closure can be derived with only one MapReduce job.

• ∙ Theoretical properties: Sound and complete for defeasible logic with one variable.

  Reported scalability Experimental evaluation was carried out showing that defeasible reasoning is feasible over billions of facts. More specifically, experiments were performed on a cluster with 16 nodes using the MapReduce framework. The method was evaluated using a synthetic data set based on uniform distribution, ranging the number of facts from 1 to 8 billion facts over an artificial rule set that had been used in literature. The method showed good scalability properties, with linear speedup over increasing number of facts, reaching data throughput of approximately 2.2 million facts per second. Scaled speedup, namely speedup per utilized node, highlighted the performance improvement attributed to large amounts of main-memory as well as the performance decline due to platform overhead.

  In Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012a) authors extended their abovementioned initial approach (see Tachmazidis et al., Reference Tachmazidis, Antoniou, Flouris and Kotoulas2012b), by relaxing the restriction that each rule may have only one variable.

  Target formalism The extended approach enables scalable defeasible reasoning where rules are allowed to have more than one variable. Authors discuss the use of predicate dependency graph, categorizing rule sets into stratified and non-stratified. The proposed method deals with stratified rule sets.

  Supported reasoning tasks This approach is based on materialization using forward-chaining.

  Algorithm A previously existing method (Tachmazidis et al., Reference Tachmazidis, Antoniou, Flouris and Kotoulas2012b) was not applicable for rule sets that contain more than one variable since in this case all applicable rules for a specific literal need to be recorded prior to the computation of the defeasible logic algorithm. However, the same literal may be supported by a set of rules that may be computed on different nodes as joins are not guaranteed to be performed on the same variable value. Thus, there is a need to differentiate between rule applicability and defeasible reasoning.

  Implementation The calculation of fired rules and defeasible reasoning are performed separately resulting in multiple MapReduce jobs. As only stratified rule sets are allowed, there is a clear reasoning sequence where rules are processed in groups utilizing previously computed knowledge. Fired rules are computed as a set of join operations, matching existing knowledge in order to define rule applicability. Once applicable rules are computed, the available knowledge (facts, applicable rules) for each literal are grouped on a single node allowing the application of the defeasible logic algorithm. After processing all rules, the full closure is computed for the given data set and rule set.

• ∙ Theoretical properties: Sound and complete for defeasible logic over stratified rule sets.

  Reported scalability Experimental results indicate that defeasible reasoning, under the assumption of stratification, can be performed over 500 millions of facts and has the potential to scale up to billions of facts. Specifically, experiments were performed on a cluster of 16 nodes, using manually generated data sets that resemble real-world data sets, which follow a highly skewed distribution. An artificial rule set was used in order to evaluate the method’s scalability. Ranging the number of rules from 2 to 16 showed linear speedup, while despite the skewed nature of the used data sets, the implementation on MapReduce allowed a well-balanced distribution of the workload. However, the method’s performance over increasing number of nodes indicate overheads that are introduced by the platform.

  A different to the abovementioned nonmonotonic approach is presented in Tachmazidis and Antoniou (Reference Tachmazidis and Antoniou2013), which is focused on the logic programming.

  Target formalism Opposite to the previous methods (Tachmazidis & Antoniou, Reference Tachmazidis and Antoniou2013) allows rules that contain negative subgoals, namely a conclusion may be derived provided that part of the rule is determined as true while another part of the rule is determined as false. Such computation allows processing over missing information. However, the presented approach deals only with the stratified semantics of logic programs.

  Supported reasoning tasks Forward-chaining materialization is computed by the proposed approach.

  Algorithm The approach is tailored for stratified semantics of logic programs. Thus, it allows only rule sets whose predicates can form a hierarchy and subsequently be assigned to ranks. However, such constraint provides a pre-defined reasoning sequence, namely performing reasoning from lower to higher ranks, which constitutes the closure.

  Implementation A rule containing both positive and negative subsets is computed as a sequence of join and anti-join operations, using MapReduce. In particular, the positive part is computed through joins resulting in a temporary literal (positive goal) containing all required arguments. Subsequently, positive goal is filtered through a sequence of anti-joins, which retain results from positive goal that do not match the negative subgoal on their common arguments. Once all anti-joins are applied, the remaining results are transformed into the set of conclusions. Various special cases are covered such as the transformation of rules with nested subgoals into a set of rules that provide equivalent results.

• ∙ Theoretical properties: Sound and complete for stratified semantics of logic programs.

  Reported scalability Experimental evaluation is reported showing that the proposed approach is able to scale up to billions of facts. Specifically, the experiments are based on a proposed benchmark for rule engines that perform in-memory reasoning. The volume of data sets was adjusted accordingly to evaluate large amounts of facts, while various evaluation metrics, applicable to the MapReduce implementation, were chosen. Experiments were run on a cluster of 9 nodes with data sets modeling both uniform and zipf distribution. Join and anti-join operations were evaluated for both distributions for up to 1 billion facts showing fairly linear speedup. The method is also showed to scale linearly when the number of rules is ranging from 16 to 128.

  In Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014) authors extended their approach from the stratified semantics of logic programs (see Tachmazidis & Antoniou, Reference Tachmazidis and Antoniou2013) to the full WFS.

  Target formalism (Tachmazidis et al., Reference Tachmazidis, Antoniou and Faber2014) proposed a method for performing reasoning over missing information dealing with the full WFS, and thus, allowing recursion through negation.

  Supported reasoning tasks This approach computes the materialization using forward-chaining.

  Algorithm This work highlighted the fact that reasoning and storing the Herbrand base is infeasible for large inputs. This method captures a significantly wider range of logic programs compared to Tachmazidis and Antoniou (Reference Tachmazidis and Antoniou2013), with which it shares the notion of computing rules with negative subgoals as a sequence of join and anti-join operations. However, Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014) deals with three-valued models meaning that the closure consists of true, undefined and false literals. Processing and storing all three values is prohibitive for large inputs. Nevertheless, it is shown that performing reasoning over true and undefined literals is feasible for large programs.

  Implementation In order to overcome the scalability barrier authors follow the alternating fixpoint procedure where reasoning is performed by computing two estimation sets, highlighting the computational impact of performing reasoning over safe (range restricted) programs. The first set contains true literals while the second contains potentially true and undefined literals. The process guarantees that eventually the two sets represent the model of the program. Thus, the final KB consists of true and undefined literals, while literals that are not contained in the KB are considered false. The approach is designed and optimized for the MapReduce framework. Optimizations come from monotonicity properties of the WFS, utilizing previously derived knowledge, and thus, reducing reasoning time, minimizing the storage of overlapping knowledge and speeding-up the decision process of determining whether the complete closure is computed.

• ∙ Theoretical properties: Sound and complete for the full WFS.

Reported scalability Experimental results showed that the proposed method can be applied to billions of facts. Specifically, an available benchmark, describing various test programs, was used and a new test program was introduced in order to evaluate the results of the proposed optimizations. Experiments were performed on a cluster of 8 nodes, evaluating default negation over synthetic data sets, following uniform distribution, of up to 1 billion facts resulting in fairly linear speedup. The advantages of optimizations follow a clear pattern, higher percentages of pre-computed knowledge result in higher speedups of the optimized over the naive implementation. For constant percentages of pre-computed knowledge, fairly constant speedups of optimized over the naive implementation are observed for various data sets.

This ends the presentation of the state of the art. Next we will critically evaluate this state of the art.

6.1 RDFS

A large part of the work introduced in the previous section focuses on the problem of parallel reasoning on RDFS ontologies using centralized or distributed platforms. The experimental results generally show a positive performance of RDFS reasoning with utilizing parallel techniques. This is mainly due to RDFS being a relatively simple language in terms of expressivity. On the other hand, RDFS has some special properties that can be used to improve the performance of parallel reasoning.

Rule Application Order The materialization of RDFS ontologies (or forward chaining reasoning) can be performed by exhaustively applying the completion rules (Hayes Reference Hayes2004) until the termination condition is satisfied. It is costly to check the termination condition, in particular in a distributed environment. The authors in Urbani et al. (Reference Urbani, Kotoulas, Oren and van Harmelen2009) have found that there exists a rule application order that leads to complete results, under certain assumptions (see the exchange on this matter in Patel-Schneider (Reference Patel-Schneider2012a) and Urbani et al. (Reference Urbani, Kotoulas, Maassen, van Harmelen and Bal2012a). In this order, most of the rules can be applied once. The remaining rules are actually used to compute the transitive closure of subsumptions among classes and properties. Thus, the problem of materialization on RDFS ontologies can be reduced to the problem of computing transitive closure, which is in the complexity class NC, where each problem can be solved effectively in parallel.

Balanced Data Partition The triples in RDFS ontologies can be categorized into two parts: schema (or ontological) triples and instance (or assertion) triples (see Figure 3). As shown in Hayes (Reference Hayes2004), each RDFS rule contains a unique instance triple pattern in preconditions. Schema triples tend to be small in size. Thus, the instance triples can be independently parallelized to different processors by replicating the schema triples across the cluster as discussed in Weaver and Hendler (Reference Weaver and Hendler2009). This method leads to embarrassing parallelism of materialization on RDFS ontologies. For schema triples, a term-based partition method is also proposed in Kotoulas et al. (Reference Kotoulas, Oren and van Harmelen2010) to deal with the problem of load balancing. This method works well in the case that the frequency of some terms is significantly higher than others. Such issues have also been discussed as part of the development of the Marvin platform in Oren et al. (Reference Oren, Kotoulas, Anadiotis, Siebes, ten Teije and van Harmelen2009), where a random approach is proposed to tackle the problem of the skew of data, and a deterministic approach is given to achieve non-redundant reasoning. Thus, Marvin actually achieves a balance between random and deterministic approaches.

Encoding of Triples Different approaches for encoding RDFS triples have been discussed in Oren et al. (Reference Oren, Kotoulas, Anadiotis, Siebes, ten Teije and van Harmelen2009), Goodman et al. (Reference Goodman, Jimenez, Mizell, al Saffar, Adolf and Haglin2011), Hoeksema and Kotoulas (Reference Hoeksema and Kotoulas2011), Heino and Pan (Reference Heino and Pan2012). These approaches can yield a significant throughput improvement and optimize the query answering. In summary, the in-memory reasoning on the Cray XMT supercomputer can scale up to 512 processors while handling 20 billion triples. Marvin is shown to scale to up to 64 nodes when processing data sets of 14.9 billion triples. The system proposed in Kotoulas et al. (Reference Kotoulas, Oren and van Harmelen2010) can run on 64 computing nodes and handle data sets with near 200 million triples and resulted in an overall throughput of 450 thousand triples per second.

Query Answering There is work that deals with the problems of RDFS data query answering in Goodman et al. (Reference Goodman, Jimenez, Mizell, al Saffar, Adolf and Haglin2011) and Hoeksema and Kotoulas (Reference Hoeksema and Kotoulas2011), stream reasoning in Hoeksema and Kotoulas (Reference Hoeksema and Kotoulas2011) and backward chaining processing in Salvadores et al. (Reference Salvadores, Correndo, Harris, Gibbins and Shadbolt2011). There are some special optimizations that can be used in these tasks. For example, a graph-based representation is proposed in Goodman et al. (Reference Goodman, Jimenez, Mizell, al Saffar, Adolf and Haglin2011). Based on this representation, a query can be transformed to graph operations that improve the performance of joins. To handle stream data, the authors in Hoeksema and Kotoulas (Reference Hoeksema and Kotoulas2011) propose a window-based method, which creates a window comprising of either a fixed number of triples or a fixed period of time during which triples are entering the stream.

Although the discussed RDFS reasoning approaches are scalable and efficient, they have certain limitations.

Lack of Benchmarks There are several RDF benchmarks and data generators such as LUBM presented in Guo et al. (Reference Guo, Pan and Heflin2005), SP²Bench presented in Schmidt et al. (Reference Schmidt, Hornung, Meier, Pinkel and Lausen2009), DBPSB presented in Morsey et al. (Reference Morsey, Lehmann, Auer and Ngomo2011), BSBM in Bizer and Schultz (Reference Bizer and Schultz2009), SRBenchin (Zhang et al., Reference Zhang, Pham, Corcho and Calbimonte2012) etc. All of them focus on benchmarking the SPARQL query processing performance and not on reasoning performance. At best, the scalability of an RDFS reasoner can be tested using these benchmarks. Further investigation is required to identify performance hotspots in RDFS reasoning similar to the efforts such as the work presented in Kang et al. (Reference Kang, Pan, Krishnaswamy, Sawangphol and Li2014) and WatDiv in Aluç et al. (Reference Aluç, Hartig, Özsu and Daudjee2014) which are for identifying performance hotspots in ontology reasoning and stress testing the SPARQL query performance respectively. Data generators that focus on such performance hotspots for RDFS reasoning should be developed. The effect of these hotspots on distributed RDFS reasoning can be studied.

Profile Specific Algorithms Several reasoners such as Pellet presented in Sirin et al. (Reference Sirin, Parsia, Grau, Kalyanpur and Katz2007), HermiT in Glimm et al. (Reference Glimm, Horrocks, Motik, Stoilos and Wang2014), Konclude in Steigmiller et al. (Reference Steigmiller, Liebig and Glimm2014) and RDFox in Motik et al (Reference Motik, Nenov, Piro and Horrocks2014) can be used on ontologies of different profiles including RDFS, OWL 2 EL, OWL 2 RL etc. But the scalable reasoning algorithms discussed so far for RDFS and other profiles are very much dependent on the reasoning rules of that particular profile. Similarly, performance optimizations are also dependent on the ruleset and the corresponding data of a particular profile. Instead, it would be beneficial to have a single scalable reasoner that can support several profiles such as RDFS, OWL 2 EL, OWL Horst and OWL 2 RL. A proposal has been put forth in Mutharaju et al. (Reference Mutharaju, Mateti and Hitzler2015) but an implementation is not available. In such cases, end users with large ontologies need not restrict the expressivity of their ontologies to a particular profile. Notice that this comment applies to OWL reasoning of Sections 6.2 and 6.3 and not only to RDFS. Since RDFS reasoning is less complex than generic OWL reasoning, RDFS is one of the main target formalisms that reasoning over a generic reasoner can be used as well, with proper parameterization.

Large TBox One of the primary assumptions in most of the scalable RDFS reasoning approaches is that the number of schema triples are typically fewer compared to the instance triples. This is in general a safe assumption and allows for the duplication of schema triples across the nodes in the cluster. However, with the ongoing research efforts in the field of automated KB construction and population as discussed in Niu et al. (Reference Niu, Zhang, Ré and Shavlik2012), Dong et al. (Reference Dong, Gabrilovich, Heitz, Horn, Lao, Murphy, Strohmann, Sun and Zhang2014), Mahdisoltani et al. (Reference Mahdisoltani, Biega and Suchanek2015), Mitchell et al. (Reference Mitchell, Cohen, Talukdar, Betteridge, Carlson, Mishra, Gardner, Kisiel, Krishnamurthy, Lao, Mazaitis, Mohamed, Nakashole, Platanios, Ritter, Samadi, Settles, Wang, Wijaya, Gupta, Chen, Saparov, Greaves and Welling2015), it could be reasonably expected that KBs with large number of schema triples can be built. In such cases, the assumption on schema triples needs a reconsideration and alternate approaches need to be studied.

6.2 Datalog, OWL Horst and OWL 2 RL

Datalog. In this survey, there is also work on parallel materialization of datalog programs. Compared to ontology languages, datalog is a GP language, so corresponding reasoning systems have to allow user-defined rules as input. On the other hand, the less expressive ontology languages can also be translated to datalog programs as discussed in Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014). Compared to RDFS reasoning, a key challenge of implementing datalog is that one cannot initially give a specific strategy for parallel materialization according to the rules, and cannot easily tackle the problem of data skew either.

Parallelism Strategies One intuitive strategy is to parallelize the application of a rule. Specifically, different processors select different facts of a predicate and perform joining with other ones. This method is adopted in Martínez-Angeles et al. (Reference Martínez-Angeles, Dutra, Costa and Buenabad-Chavez2013) by means of the natural power of parallelism of GPU. However this method cannot control the skew of data, and may give rise to a large amount of redundant rule applications in some cases.

To tackle the above problems, the authors of Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014) propose an approach where each fact has a global order including the derived ones. A unique order ensures that the applications of some rule would not be performed repeatedly. On the other hand, all processors (threads in the case of Motik et al., Reference Motik, Nenov, Piro and Horrocks2014)) work on the global order, such that the distribution of the whole materialization is relatively fair. In this way, the fraction of the computation performed in parallel on the implemented system trends up to 98% according to Amdahl’s law. This means that, in most cases, parallelism can significantly improve the performance of materialization.

Current Limitations These two approaches proposed in Martínez-Angeles et al. (Reference Martínez-Angeles, Dutra, Costa and Buenabad-Chavez2013), Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014) are both implemented based on in-memory systems. Thus the performance is restricted by the utilized memory. For the work of Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014), performing materialization on data sets of 690M triples with 32 threads allocated leads to the exhaustion of memory. The authors in Martínez-Angeles et al. (Reference Martínez-Angeles, Dutra, Costa and Buenabad-Chavez2013) propose some methods for memory management, and evaluate their system on data sets with million facts. The authors of these two papers did not discuss whether their approaches can be used in distributed platforms.

OWL Horst and OWL 2 RL. More recently, the general research focus moved on to performing rule-based reasoning using rules that go beyond the ones in the RDFS set. So far, the results have been moderately successful, with distributed approaches like WebPIE that can scale to RDF data sets with a hundred billion triples, and centralized ones that can compute the closure of data sets of up to hundred of million of triples in a few minutes. These results are certainly encouraging. However, there are still two major problems that remain unsolved: We call them the completeness and worst-case problems.

Completeness If we look at the compliance of current reasoners w.r.t. the expressivity of the supported ontological languages, then we notice that none of the current approaches is evaluated w.r.t. to a complete inference. The problem is that many of the rules in complex ontological languages like OWL RL require the execution of complex joins, whose execution might be very time-consuming on large data sets. Furthermore, several constructs require the materialization of a large number of statements which encode “trivial” knowledge. For example, in OWL RL, a complete materialization engine would need to state that any pair of concepts that is not equal should be considered as different. Furthermore, another important complication that is induced by the rules in expressive fragments like OWL RL, is that ABox data might generate TBox data. Emblematic of this is the case described in Patel-Schneider (Reference Patel-Schneider2012b), where somebody could define a property that is a subproperty of rdfs:subPropertyOf. In this case, the ABox collection effectively causes an expansion of the TBox. These cases are fortunately quite rare, yet they might occur and a complete reasoner is called to address them. What is the performance of complete OWL RL reasoning on a large RDF input is a question which still has not found any empirical answer, to the best of our knowledge.

Worst-case Currently, large KBs use only a subset of the features that are offered by the ontological languages. In general, the TBox is significantly smaller than the ABox (in terms of number of statements), and this allow the applications of ad-hoc techniques to improve the performance. For example, WebPIE replicates the (needed) TBox on each node in order to perform almost all joins locally. Another important feature of current KBs is that the inferred TBox is rather small (again, in terms of statements) and can be quickly inferred. This heuristic was exploited in various systems to improve the performance. In QueryPIE this is used to effectively prune the search tree during the query execution. In RDFox, the evaluation in Motik et al. (Reference Motik, Nenov, Piro and Horrocks2014) used a particular technique to “unfold” the ontology in several rules. This unfolding is doable if the ontology (and corresponding inference), is such that the number of rules remains small. Also, in this case, there is no evidence on the performance of current reasoners in case the input exploit larger and richer ontologies.

Critical Analysis. For datalog and OWL (including OWL RL and OWL Horst), current research effort focuses on tractable variants of these languages. Compared to RDFS, these languages have higher expressivity. Accordingly, more complicated rules are needed for reasoning tasks. In other words, there exist tighter interrelations among rules and data. This makes it hard to completely parallelize rule applications. Furthermore, a fixed-point strategy (using numerous iterations to check termination condition) is inevitable. In this setting, some specialized methods are applied in implementations, for example, sacrificing completeness to avoid complex joins, and maintaining global order to capture load balance.

The experimental results are encouraging for parallel reasoning of datalog and tractable OWL profiles. One reason is that the evaluated data sets typically have small size ontological data (TBoxes) . One can improve performance by utilizing this feature, that is, replicating ontological data on each processor. On the other hand, the evaluated data sets do not fully use the expressive power of target languages. This is another reason for the encouraging results. To make current methods more practical, it is necessary to study the cases with larger and more complex ontological data being involved.

6.3 Description Logics

OWL EL. The complexity of classification with OWL EL ontologies is PTime-complete. This positive complexity is also the reason why OWL EL stands out in the DL family and is widely used in many applications.

In-memory Systems The first polynomial-time reasoner for classification in OWL EL is CEL presented in Krötzsch (Reference Krötzsch2011), which is based on a refined classification algorithm. This algorithm is designed by considering the optimizations used in the linear-time algorithm for checking satisfiability of propositional horn clauses. Since CEL is essentially a serial reasoner, it does not perform very well on large ontologies, like SNOMED CT. The PTime-complete complexity also indicates that in the worst case the classification is inherently a serial procedure. However, the methods utilizing parallel techniques have verified that parallelism can significantly improve the performance of OWL EL classification on real ontologies.

ELK presented in Kazakov et al. (Reference Kazakov, Krötzsch and Simancik2011) is the first attempt to use multi-core techniques and other optimizations to enhance the efficiency of reasoning in OWL EL. It classifies the SNOMED CT ontology in less than half a minute (the classification time of CEL is 15 min). Although some preliminary experiments show that ELK can be scalable to some extent, it is restricted to the main memory of the utilized machines. Ren et al. further proposed a distributed ABox materialization algorithm in Ren et al. (Reference Ren, Pan and Lee2012), which can be exploited to support OWL 2 DL, with the syntactic approximate reasoning algorithm (see Ren et al., Reference Ren, Pan and Zhao2010) used in TrOWL, presented in Thomas et al. (Reference Thomas, Pan and Ren2010).

Distributed Systems Another line of work on parallel reasoning in OWL EL is based on the distributed computation platforms to deal with the scalability problem. These works are based on MapReduce as discussed in Mutharaju et al. (Reference Mutharaju, Maier and Hitzler2010) or Redis as discussed in Mutharaju et al. (Reference Mutharaju, Hitzler, Mateti and Lécué2015). The proposed experiments show that reasoners based on such platforms have good scalability. However, these reasoners are typically not efficient due to the inherent overhead of the platforms. We briefly analyze the reasons as follows; On the one hand, this work implements distributed reasoning based on the CEL calculus, which is actually a normalization-based approach. The CEL calculus introduces redundant and unnecessary concepts to rename complex concepts, such that the classification can be performed based on a set of simple formed rules. However this treatment would lead to a large amount of unnecessary results. In the work of ELK, the authors propose an approach to avoid normalization and directly handle complex concepts. Since the method of ELK requires several global operations, it can hardly be used on distributed platforms. On the other hand, the rules in CEL presented in Baader et al. (Reference Baader, Brandt and Lutz2005) are closely interdependent. Thus, there is no rule application order that avoids the fix-point checking. Furthermore, some rules give rise to multi-way joins which are costly on distributed platforms.

6.4 Nonmonotonic Reasoning

The study of nonmonotonic reasoning revealed several challenges that come from the more complex knowledge structures. In the following, we discuss some of the issues that were revealed in the literature.

Excessive Generation of Literals Nonmonotonic reasoning that is based either on defeasible logic or the WFS comes with a significant overhead in terms of the number of generated literals. More specifically, both approaches are based on three-valued logics, where literals are classified as true, false or undefined. Thus, in order to keep a complete KB, literals for at least two of the three values should be kept in the KB. However, that could potentially lead to an excessive number of stored literals.

In particular, the proof theory of the defeasible logic requires the representation of the so called “not provable” literals, which generates large numbers of literals even for small theories. Thus, the current approach is based on a two-valued subset of the defeasible logic, namely the stratified rule sets as discussed in Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012a), while a scalable solution for the full defeasible logic remains an open question. The initial definition of the WFS did not provide an efficient reasoning process that could generate a manageable amount of literals. Thus, the first step towards the WFS was based of stratified rule sets as discussed in Tachmazidis and Antoniou (Reference Tachmazidis and Antoniou2013). However, more recent work in Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014) showed that by computing and storing true and undefined literals, the closure of the full WFS can be computed while avoiding the generation of excessive number of literals.

Computing Conclusions: Monotonic Vs Nonmonotonic Reasoning Moving from monotonic to nonmonotonic reasoning reveals fundamental differences in terms of conclusion computation. In monotonic reasoning, rules contain only positive subgoals while the application of a rule also implies a new conclusion. On the other hand, nonmonotonic reasoning could contain both positive and negative subgoals as discussed in Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014), or after the computation of applicable rules, an additional step could be required in order to apply the proof theory and derive new conclusions as discussed in Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012a). Thus, while nonmonotonic reasoning can benefit from lessons learnt from monotonic reasoning, it might also require certain adjustments in order to handle the more complex knowledge structures.

Lack of Benchmarks The lack of benchmarks is reflected in the evaluation of the existing work. More specifically, the evaluation of Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris and Kotoulas2012b) is an adjustment of a previous work on an in-memory reasoner. The work in Tachmazidis et al. (Reference Tachmazidis, Antoniou, Flouris, Kotoulas and McCluskey2012a) builds on an existing evaluation and studies several aspects of the proposed method. Both the work in Tachmazidis and Antoniou (Reference Tachmazidis and Antoniou2013) and in Tachmazidis et al. (Reference Tachmazidis, Antoniou and Faber2014) evaluate parts of the WFS, while this evaluation is inspired by an existing benchmark for in-memory reasoners. Thus, there is clearly no benchmark for nonmonotonic reasoning that could access critical parts of a reasoner such as scalability and performance in terms of data volume, data distribution, rule set size and rule set structure.

This concludes the critical analysis of the state of the art in large-scale reasoning on the Web of Data. Notice that without running the experiments across different approaches on the same hardware using the same data sets, it would be difficult to claim that a particular approach to be state-of-the-art or the most scalable compared to all others. Thus in the Table of Section 6 reported scalability is presented without an ordering of systems based on performance since the advancement in hardware and the variation in the time span of the approaches (e.g. in the case of RDFS reasoning, the earliest paper cited is from 2008 whereas the latest is from 2016) is an important factor in achieved performance. In the following and final section we summarize the content and findings of this review, and discuss some areas of future research.