Mixing Parallel and Sequential Computation for Top-down OWL RL Inference

The size and growth rate of the Semantic Web call for querying and reasoning methods that can be applied over very large amounts of data. In this paper, we discuss how we can enrich the results of queries by performing rule-based reasoning in a top-down fashion over large RDF knowledge bases. This paper focuses on the technical challenges involved in the topdown evaluation of the reasoning rules. First, we discuss the application of well-known algorithms in the QSQ family, and analyze their advantages and drawbacks. Then, we present a new algorithm, called RDF-SQ, which re-uses different features of the QSQ algorithms and introduces some novelties that target the execution of the OWL-RL rules. We implemented our algorithm inside the QueryPIE prototype and tested its performance against QSQ-R, which is the most popular QSQ algorithm, and a parallel variant of it, which is the current state-of-theart in terms of scalability.We used a large LUBM dataset with ten billion triples, and our tests show that RDF-SQ is significantly faster and more efficient than the competitors in almost all cases.