Existential rules, a.k.a. tuple-generating dependencies (TGDs), form a well-established formalism for specifying ontologies. In particular, the warded language is a well-behaved fragment of TGD-based ontologies, striking a good balance between expressive power and computational complexity of answering Ontology-Mediated Queries (OMQs). The theoretical foundations of answering OMQs over warded ontologies are by now well-understood, but to the best of our knowledge, very few efforts exist that exploit such a rich theory for building practical query answering algorithms. Our goal is to fill the above gap by designing a novel Datalog rewriting algorithm for OMQs over warded ontologies which is amenable to practical implementations, as well as providing an implementation and an experimental evaluation, with the aim of understanding how key input parameters affect the performance of this approach, and what are its limits when combined with off-the-shelf Datalog-based engines.

Over the past years, there has been a growing demand for ontological reasoning systems based on languages of the Datalog+/- family, such as Vadalog, for their ability to effectively model a wide range of real-world problems with powerful features such as existential quantification. As the scale and complexity of data analysis tasks continue to grow, the ability to distribute the computational workload across multiple non-communicating processors has become vital for these systems to achieve scalable performance. The joint presence of existential quantification and recursion poses new challenges, currently unsolved by existing distributed systems, which only concentrate on Datalog and are therefore unsuitable for ontological reasoning. When working across multiple processors, generating all the facts to answer a specific reasoning query, avoiding duplication, and guaranteeing termination are non-trivial tasks as infinitely many new symbols and facts can be generated by existential quantification and recursion. In this paper, we address such challenges and introduce the first distributed framework in the Datalog+/- space. We propose the condition of homomorphic decomposability, which identifies sets of Datalog+/- rules with good distribution properties. We put homomorphic decomposability into action with a distributed reasoning algorithm for Warded Datalog+/-, the core of Vadalog. We implement Vadalog Parallel, a distributed reasoner for Vadalog and provide experimental evaluation against state-of-the-art systems.

Equality-generating dependencies (EGDs) allow to fully exploit the power of existential quantification in ontological reasoning settings modeled via Tuple-Generating Dependencies (TGDs), by enabling value-assignment or forcing the equivalence of fresh symbols. These capabilities are at the core of many common reasoning tasks, including graph traversals, clustering, data matching and data fusion, and many more related real-world scenarios. However, the interplay of TGDs and EGDs is known to lead to undecidability or intractability of query answering in tractable Datalog+/- fragments, like Warded Datalog+/-, for which, in the sole presence of TGDs, query answering is PTIME in data complexity. Restrictions of equality constraints, like separable EGDs, have been studied, but all achieve decidability at the cost of limited expressive power, which makes them unsuitable for the mentioned tasks. This paper introduces the class of "harmless" EGDs, that subsume separable EGDs and allow to model a very broad class of tasks. We contribute a sufficient syntactic condition for testing harmlessness, an undecidable task in general. We argue that in Warded Datalog+/- with harmless EGDs, ontological reasoning is decidable and PTIME. From such theoretical underpinnings, we develop novel chase-based techniques for reasoning with harmless EGDs and present an implementation within the Vadalog system, a state-of-the-art Datalog-based reasoner. We provide full-scale experimental evaluation and comparative analysis.