Bernardo Cuenca Grau

AIJ Journal 2026 Journal Article

From monotonic graph neural networks to datalog and back: Expressive power and practical applications

• David Tena Cucala
• Bernardo Cuenca Grau
• Boris Motik
• Egor V. Kostylev

Many tasks over knowledge graphs, such as link prediction, can be conceptualised as a problem of learning a transformation of sets of relational facts. Machine learning models such as graph neural networks (GNNs) can be used to realise this transformation, allowing the transformation to be learned from examples. However, it is often difficult to verify formally the properties of such a transformation, or understand why it derives a specific fact. Alternatively, such a transformation can be realised using a set of rules expressed in a knowledge representation language such as Datalog. Formal properties of such a transformation can be verified using symbolic means, and each derived fact can be justified by a rule; however, writing and curating the rules is costly and requires expertise in both the application domain and the formal language. To bridge the gap between these two approaches, in this paper we study the relationship between transformations realised by monotonic max-sum GNNs , a subclass of GNNs with nonnegative weights and max and sum aggregation functions, and transformations realised by Datalog rules. First, we provide an algorithm that can verify whether a given Datalog rule is sound for a network, in the sense that the GNN always derives all consequences of the rule on any input dataset. Second, we provide an algorithm that allows us to justify any fact derived by a GNN by computing a rule that is sound for the GNN and that derives the fact. Third, we study the expressive power of monotonic max-sum GNNs and show that, for each such GNN, one can compute a Datalog program where applying the GNN to any dataset produces the same facts as a single round of application of the program’s rules to the dataset; we also sharpen our result to the subclass of monotonic max GNNs, which use only the max aggregation function, and identify a corresponding class of Datalog programs. Finally, we carry out a practical evaluation and show that monotonic max-sum GNNs can be successfully trained in practice on common knowledge graph tasks, and that extracting rules from max-sum GNNs is practically feasible.

AAAI Conference 2026 Conference Paper

The Correspondence Between Bounded Graph Neural Networks and Fragments of First-Order Logic

• Bernardo Cuenca Grau
• Eva Feng
• Przemysław Andrzej Wałęga

Graph Neural Networks (GNNs) address two key challenges in applying deep learning to graph-structured data: they handle varying size input graphs and ensure invariance under graph isomorphism. While GNNs have demonstrated broad applicability, understanding their expressive power remains an important question. In this paper, we propose GNN architectures that correspond precisely to prominent fragments of first-order logic (FO), including various modal logics as well as more expressive two-variable fragments. To establish these results, we apply methods from finite model theory of first-order and modal logics to the domain of graph representation learning. Our results provide a unifying framework for understanding the logical expressiveness of GNNs within FO.

ICLR Conference 2025 Conference Paper

Bayesian Treatment of the Spectrum of the Empirical Kernel in (Sub)Linear-Width Neural Networks

• Ouns El Harzli
• Bernardo Cuenca Grau

We study Bayesian neural networks (BNNs) in the theoretical limits of infinitely increasing number of training examples, network width and input space dimension. Our findings establish new bridges between kernel-theoretic approaches and techniques derived from statistical mechanics through the correspondence between Mercer's eigenvalues and limiting spectral distributions of covariance matrices studied in random matrix theory. Our theoretical contributions first consist in novel integral formulas that accurately describe the predictors of BNNs in the asymptotic linear-width and sublinear-width regimes. Moreover, we extend the recently developed renormalisation theory of deep linear neural networks, enabling a rigorous explanation of the mounting empirical evidence that hints at the theory's applicability to nonlinear BNNs with ReLU activations in the linear-width regime. From a practical standpoint, our results introduce a novel technique for estimating the predictor statistics of a trained BNN that is applicable to the sublinear-width regime where the predictions of the renormalisation theory are inaccurate.

KR Conference 2025 Conference Paper

Logical Expressivity and Explanations for Monotonic GNNs with Scoring Functions

• Matthew Morris
• David J. Tena Cucala
• Bernardo Cuenca Grau

Graph neural networks (GNNs) are often used for the task of link prediction: predicting missing binary facts in knowledge graphs (KGs). To address the lack of explainability of GNNs on KGs, recent works extract Datalog rules from GNNs with provable correspondence guarantees. The extracted rules can be used to explain the GNN's predictions; furthermore, they can help characterise the expressive power of various GNN models. However, these works address only a form of link prediction based on a restricted, low-expressivity graph encoding/decoding method. In this paper, we consider a more general and popular approach for link prediction where a scoring function is used to decode the GNN output into fact predictions. We show how GNNs and scoring functions can be adapted to be monotonic, use the monotonicity to extract sound rules for explaining predictions, and leverage existing results about the kind of rules that scoring functions can capture. We also define procedures for obtaining equivalent Datalog programs for certain classes of monotonic GNNs with scoring functions. Our experiments show that, on link prediction benchmarks, monotonic GNNs and scoring functions perform well in practice and yield many sound rules.

KR Conference 2024 Conference Paper

Bridging Max Graph Neural Networks and Datalog with Negation

• David J. Tena Cucala
• Bernardo Cuenca Grau

We consider a general class of data transformations based on Graph Neural Networks (GNNs), which can be used for a wide variety of tasks. An important question in this setting is to characterise the expressive power of these transformations in terms of a suitable logic-based language. From a practical perspective, the correspondence of a GNN with a logical theory can be exploited for explaining the model's predictions symbolically. In this paper, we introduce a broad family of GNN-based transformations which can be characterised using Datalog programs with negation-as-failure, which can be computed from the GNNs after training. This generalises existing approaches based on positive programs by enabling the learning of nonmonotonic transformations. We show empirically that these GNNs offer good performance for knowledge graph completion tasks, and that we can efficiently extract programs for explaining individual predictions.

AAAI Conference 2024 Conference Paper

Double-Descent Curves in Neural Networks: A New Perspective Using Gaussian Processes

• Ouns El Harzli
• Bernardo Cuenca Grau
• Guillermo Valle-Pérez
• Ard A. Louis

Double-descent curves in neural networks describe the phenomenon that the generalisation error initially descends with increasing parameters, then grows after reaching an optimal number of parameters which is less than the number of data points, but then descends again in the overparameterized regime. In this paper, we use techniques from random matrix theory to characterize the spectral distribution of the empirical feature covariance matrix as a width-dependent perturbation of the spectrum of the neural network Gaussian process (NNGP) kernel, thus establishing a novel connection between the NNGP literature and the random matrix theory literature in the context of neural networks. Our analytical expressions allow us to explore the generalisation behavior of the corresponding kernel and GP regression. Furthermore, they offer a new interpretation of double-descent in terms of the discrepancy between the width-dependent empirical kernel and the width-independent NNGP kernel.

ICLR Conference 2024 Conference Paper

Faithful Rule Extraction for Differentiable Rule Learning Models

• Xiaxia Wang 0001
• David Jaime Tena Cucala
• Bernardo Cuenca Grau
• Ian Horrocks 0001

There is increasing interest in methods for extracting interpretable rules from ML models trained to solve a wide range of tasks over knowledge graphs (KGs), such as KG completion, node classification, question answering and recommendation. Many such approaches, however, lack formal guarantees establishing the precise relationship between the model and the extracted rules, and this lack of assurance becomes especially problematic when the extracted rules are applied in safety-critical contexts or to ensure compliance with legal requirements. Recent research has examined whether the rules derived from the influential Neural-LP model exhibit soundness (or completeness), which means that the results obtained by applying the model to any dataset always contain (or are contained in) the results obtained by applying the rules to the same dataset. In this paper, we extend this analysis to the context of DRUM, an approach that has demonstrated superior practical performance. After observing that the rules currently extracted from a DRUM model can be unsound and/or incomplete, we propose a novel algorithm where the output rules, expressed in an extension of Datalog, ensure both soundness and completeness. This algorithm, however, can be inefficient in practice and hence we propose additional constraints to DRUM models facilitating rule extraction, albeit at the expense of reduced expressive power.

KR Conference 2024 Conference Paper

MTLearn: Extracting Temporal Rules Using Datalog Rule Learners

• Dingmin Wang
• Przemysław Andrzej Wałęga
• Bernardo Cuenca Grau

We propose a framework for temporal rule learning from datasets, which capitalises on the availability of increasingly mature Datalog rule learners. Our approach is based on the idea of splitting a temporal dataset into windows, extracting static rules from each window with an off-the-shelf Datalog rule learner, and then combining the obtained static rules into temporal rules corresponding to the whole dataset. Temporal rules generated by our approach are expressed in DatalogMTL and are assigned time-sensitive confidence scores. We have implemented our approach in a system MTLearn compatible with any Datalog rule learner, as well as with a range of strategies for scoring the output temporal rules. The evaluation results on the task of temporal link prediction show that our proposed approach is highly competitive, achieve performance comparable to that of state-of-the-art machine learning models for both the extrapolation and the interpolation settings, while at the same time providing interpretable results.

ICLR Conference 2024 Conference Paper

Orbit-Equivariant Graph Neural Networks

• Matthew Morris
• Bernardo Cuenca Grau
• Ian Horrocks 0001

Equivariance is an important structural property that is captured by architectures such as graph neural networks (GNNs). However, equivariant graph functions cannot produce different outputs for similar nodes, which may be undesirable when the function is trying to optimize some global graph property. In this paper, we define orbit-equivariance, a relaxation of equivariance which allows for such functions whilst retaining important structural inductive biases. We situate the property in the hierarchy of graph functions, define a taxonomy of orbit-equivariant functions, and provide four different ways to achieve non-equivariant GNNs. For each, we analyze their expressivity with respect to orbit-equivariance and evaluate them on two novel datasets, one of which stems from a real-world use-case of designing optimal bioisosteres.

KR Conference 2024 Conference Paper

Relational Graph Convolutional Networks Do Not Learn Sound Rules

• Matthew Morris
• David J. Tena Cucala
• Bernardo Cuenca Grau
• Ian Horrocks

Graph neural networks (GNNs) are frequently used to predict missing facts in knowledge graphs (KGs). Motivated by the lack of explainability for the outputs of these models, recent work has aimed to explain their predictions using Datalog, a widely used logic-based formalism. However, such work has been restricted to certain subclasses of GNNs. In this paper, we consider one of the most popular GNN architectures for KGs, R-GCN, and we provide two methods to extract rules that explain its predictions and are sound, in the sense that each fact derived by the rules is also predicted by the GNN, for any input dataset. Furthermore, we provide a method that can verify that certain classes of Datalog rules are not sound for the R-GCN. In our experiments, we train R-GCNs on KG completion benchmarks, and we are able to verify that no Datalog rule is sound for these models, even though the models often obtain high to near-perfect accuracy. This raises some concerns about the ability of R-GCN models to generalise and about the explainability of their predictions. We further provide two variations to the training paradigm of R-GCN that encourage it to learn sound rules and find a trade-off between model accuracy and the number of learned sound rules.

ECAI Conference 2023 Conference Paper

An Empirical Study of Retrieval-Enhanced Graph Neural Networks

• Dingmin Wang
• Shengchao Liu
• Hanchen Wang 0002
• Bernardo Cuenca Grau
• Linfeng Song
• Jian Tang 0005
• Le Song
• Qi Liu 0049

Graph Neural Networks (GNNs) are effective tools for graph representation learning. Most GNNs rely on a recursive neighborhood aggregation scheme, named message passing, thereby their theoretical expressive power is limited to the first-order Weisfeiler-Lehman test (1-WL). An effective approach to this challenge is to explicitly retrieve some annotated examples used to enhance GNN models. While retrieval-enhanced models have been proved to be effective in many language and vision domains, it remains an open question how effective retrieval-enhanced GNNs are when applied to graph datasets. Motivated by this, we want to explore how the retrieval idea can help augment the useful information learned in the graph neural networks, and we design a retrieval-enhanced scheme called GRAPHRETRIEVAL, which is agnostic to the choice of graph neural network models. In GRAPHRETRIEVAL, for each input graph, similar graphs together with their ground-true labels are retrieved from an existing database. Thus they can act as a potential enhancement to complete various graph property predictive tasks. We conduct comprehensive experiments over 13 datasets, and we observe that GRAPHRETRIEVAL is able to reach substantial improvements over existing GNNs. Moreover, our empirical study also illustrates that retrieval enhancement is a promising remedy for alleviating the long-tailed label distribution problem.

IJCAI Conference 2023 Conference Paper

Cardinality-Minimal Explanations for Monotonic Neural Networks

• Ouns El Harzli
• Bernardo Cuenca Grau
• Ian Horrocks

In recent years, there has been increasing interest in explanation methods for neural model predictions that offer precise formal guarantees. These include abductive (respectively, contrastive) methods, which aim to compute minimal subsets of input features that are sufficient for a given prediction to hold (respectively, to change a given prediction). The corresponding decision problems are, however, known to be intractable. In this paper, we investigate whether tractability can be regained by focusing on neural models implementing a monotonic function. Although the relevant decision problems remain intractable, we can show that they become solvable in polynomial time by means of greedy algorithms if we additionally assume that the activation functions are continuous everywhere and differentiable almost everywhere. Our experiments suggest favourable performance of our algorithms.

AAAI Conference 2023 Conference Paper

Efficient Embeddings of Logical Variables for Query Answering over Incomplete Knowledge Graphs

• Dingmin Wang
• Yeyuan Chen
• Bernardo Cuenca Grau

The problem of answering complex First-order Logic queries over incomplete knowledge graphs is receiving growing attention in the literature. A promising recent approach to this problem has been to exploit neural link predictors, which can be effective in identifying individual missing triples in the incomplete graph, in order to efficiently answer complex queries. A crucial advantage of this approach over other methods is that it does not require example answers to complex queries for training, as it relies only on the availability of a trained link predictor for the knowledge graph at hand. This approach, however, can be computationally expensive during inference, and cannot deal with queries involving negation. In this paper, we propose a novel approach that addresses all of these limitations. Experiments on established benchmark datasets demonstrate that our approach offers superior performance while significantly reducing inference times.

JAIR Journal 2023 Journal Article

Finite Materialisability of Datalog Programs with Metric Temporal Operators

• Przemysław Wałęga
• Michał Zawidzki
• Bernardo Cuenca Grau

DatalogMTL is an extension of Datalog with metric temporal operators that has recently found applications in stream reasoning and temporal ontology-based data access. In contrast to plain Datalog, where materialisation (a.k.a. forward chaining) naturally terminates in finitely many steps, reaching a fixpoint in DatalogMTL may require infinitely many rounds of rule applications. As a result, existing reasoning systems resort to other approaches, such as constructing large Büchi automata, whose implementations turn out to be highly inefficient in practice. In this paper, we propose and study finitely materialisable DatalogMTL programs, for which forward chaining reasoning is guaranteed to terminate. We consider a data-dependent notion of finite materialisability of a program, where termination is guaranteed for a given dataset, as well as a data-independent notion, where termination is guaranteed regardless of the dataset. We show that, for bounded programs (a natural DatalogMTL fragment for which reasoning is as hard as in the full language), checking data-dependent finite materialisability is ExpSpace-complete in combined complexity and PSpace-complete in data complexity; furthermore, we propose a practical materialisation-based decision procedure that works in doubly exponential time. We show that checking data-independent finite materialisability for bounded progams is computationally easier, namely ExpTime-complete; moreover, we propose sufficient conditions for data-indenpendent finite materialisability that can be efficiently checked. We provide also the complexity landscape of fact entailment for different classes of finitely materialisable programs; surprisingly, we could identify a large class of finitely materialisable programs, called MTL-acyclic programs, for which fact entailment has exactly the same data and combined complexity as in plain Datalog, which makes this fragment especially well suited for big-scale applications.

AAAI Conference 2023 Conference Paper

Materialisation-Based Reasoning in DatalogMTL with Bounded Intervals

• Przemysław A. Wałęga
• Michał Zawidzki
• Dingmin Wang
• Bernardo Cuenca Grau

DatalogMTL is a powerful extension of Datalog with operators from metric temporal logic (MTL), which has received significant attention in recent years. In this paper, we investigate materialisation-based reasoning (a.k.a. forward chaining) in the context of DatalogMTL programs and datasets with bounded intervals, where partial representations of the canonical model are obtained through successive rounds of rule applications. Although materialisation does not naturally terminate in this setting, it is known that the structure of canonical models is ultimately periodic. Our first contribution in this paper is a detailed analysis of the periodic structure of canonical models; in particular, we formulate saturation conditions whose satisfaction by a partial materialisation implies an ability to recover the full canonical model via unfolding; this allows us to compute the actual periods describing the repeating parts of the canonical model as well as to establish concrete bounds on the number of rounds of rule applications required to achieve saturation. Based on these theoretical results, we propose a practical reasoning algorithm where saturation can be efficiently detected as materialisation progresses, and where the relevant periods used to evaluate entailment of queries via unfolding are efficiently computed. We have implemented our algorithm and our experiments suggest that our approach is both scalable and robust.

KR Conference 2023 Conference Paper

On the Correspondence Between Monotonic Max-Sum GNNs and Datalog

• David Tena Cucala
• Bernardo Cuenca Grau
• Boris Motik
• Egor V. Kostylev

Although there has been significant interest in applying machine learning techniques to structured data, the expressivity (i. e. , a description of what can be learned) of such techniques is still poorly understood. In this paper, we study data transformations based on graph neural networks (GNNs). First, we note that the choice of how a dataset is encoded into a numeric form processable by a GNN can obscure the characterisation of a model's expressivity, and we argue that a canonical encoding provides an appropriate basis. Second, we study the expressivity of monotonic max-sum GNNs, which cover a subclass of GNNs with max and sum aggregation functions. We show that, for each such GNN, one can compute a Datalog program such that applying the GNN to any dataset produces the same facts as a single round of application of the program's rules to the dataset. Monotonic max-sum GNNs can sum an unbounded number of feature vectors which can result in arbitrarily large feature values, whereas rule application requires only a bounded number of constants. Hence, our result shows that the unbounded summation of monotonic max-sum GNNs does not increase their expressive power. Third, we sharpen our result to the subclass of monotonic max GNNs, which use only the max aggregation function, and identify a corresponding class of Datalog programs.

KR Conference 2023 Conference Paper

Revisiting Inferential Benchmarks for Knowledge Graph Completion

• Shuwen Liu
• Bernardo Cuenca Grau
• Ian Horrocks
• Egor V. Kostylev

Knowledge Graph (KG) completion is the problem of extending an incomplete KG with missing facts. A key feature of Machine Learning approaches for KG completion is their ability to learn inference patterns, so that the predicted facts are the results of applying these patterns to the KG. Standard completion benchmarks, however, are not well-suited for evaluating models' abilities to learn patterns, because the training and test sets of these benchmarks are a random split of a given KG and hence do not capture the causality of inference patterns. We propose a novel approach for designing KG completion benchmarks based on the following principles: there is a set of logical rules so that the missing facts are the results of the rules' application; the training set includes both premises matching rule antecedents and the corresponding conclusions; the test set consists of the results of applying the rules to the training set; the negative examples are designed to discourage the models from learning rules not entailed by the rule set. We use our methodology to generate several benchmarks and evaluate a wide range of existing KG completion systems. Our results provide novel insights on the ability of existing models to induce inference patterns from incomplete KGs.

ICLR Conference 2022 Conference Paper

Explainable GNN-Based Models over Knowledge Graphs

• David Jaime Tena Cucala
• Bernardo Cuenca Grau
• Egor V. Kostylev
• Boris Motik

Graph Neural Networks (GNNs) are often used to learn transformations of graph data. While effective in practice, such approaches make predictions via numeric manipulations so their output cannot be easily explained symbolically. We propose a new family of GNN-based transformations of graph data that can be trained effectively, but where all predictions can be explained symbolically as logical inferences in Datalog—a well-known rule-based formalism. In particular, we show how to encode an input knowledge graph into a graph with numeric feature vectors, process this graph using a GNN, and decode the result into an output knowledge graph. We use a new class of monotonic GNNs (MGNNs) to ensure that this process is equivalent to a round of application of a set of Datalog rules. We also show that, given an arbitrary MGNN, we can automatically extract rules that completely characterise the transformation. We evaluate our approach by applying it to classification tasks in knowledge graph completion.

KR Conference 2022 Conference Paper

Faithful Approaches to Rule Learning

• David J. Tena Cucala
• Bernardo Cuenca Grau
• Boris Motik

Rule learning involves developing machine learning models that can be applied to a set of logical facts to predict additional facts, as well as providing methods for extracting from the learned model a set of logical rules that explain symbolically the model's predictions. Existing such approaches, however, do not describe formally the relationship between the model's predictions and the derivations of the extracted rules; rather, it is often claimed without justification that the extracted rules `approximate' or `explain' the model, and rule quality is evaluated by manual inspection. In this paper, we study the formal properties of Neural-LP--a prominent rule learning approach. We show that the rules extracted from Neural-LP models can be both unsound and incomplete: on the same input dataset, the extracted rules can derive facts not predicted by the model, and the model can make predictions not derived by the extracted rules. We also propose a modification to the Neural-LP model that ensures that the extracted rules are always sound and complete. Finally, we show that, on several prominent benchmarks, the classification performance of our modified model is comparable to that of the standard Neural-LP model. Thus, faithful learning of rules is feasible from both a theoretical and practical point of view.

AAAI Conference 2022 Conference Paper

MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators

• Dingmin Wang
• Pan Hu
• Przemysław Andrzej Wałęga
• Bernardo Cuenca Grau

DatalogMTL is an extension of Datalog with operators from metric temporal logic which has received significant attention in recent years. It is a highly expressive knowledge representation language that is well-suited for applications in temporal ontology-based query answering and stream processing. Reasoning in DatalogMTL is, however, of high computational complexity, making implementation challenging and hindering its adoption in applications. In this paper, we present a novel approach for practical reasoning in DatalogMTL which combines materialisation (a. k. a. forward chaining) with automata-based techniques. We have implemented this approach in a reasoner called MeTeoR and evaluated its performance using a temporal extension of the Lehigh University Benchmark and a benchmark based on real-world meteorological data. Our experiments show that MeTeoR is a scalable system which enables reasoning over complex temporal rules and datasets involving tens of millions of temporal facts.

AIJ Journal 2022 Journal Article

The delay and window size problems in rule-based stream reasoning

• Alessandro Ronca
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

In recent years, there has been an increasing interest in extending stream processing engines with rule-based temporal reasoning capabilities. To ensure correctness, such systems must be able to output results over the partial data received so far as if the entire (infinite) stream had been available; furthermore, these results must be streamed out as soon as the relevant data is received, thus incurring the minimum possible delay; finally, due to memory limitations, systems can only keep a limited history of previous facts in memory to perform further computations. These requirements pose significant theoretical and practical challenges since temporal rules can derive new information and propagate it both towards past and future time points; as a result, streamed answers can depend on data that has not yet been received, as well as on data that arrived far in the past. Towards developing a solid foundation for practical rule-based stream reasoning, we propose and study in this paper a suite of decision problems that can be exploited by stream reasoning algorithms to tackle the aforementioned challenges, and provide tight complexity bounds for a core temporal extension of Datalog. All of the problems we consider can be solved at design time (under reasonable assumptions), prior to the processing of any data. Solving these problems enables the use of reasoning algorithms that process the input streams incrementally using a sliding window, while at the same time supporting an expressive rule-based knowledge representation language and minimising both latency and memory consumption.

KR Conference 2021 Conference Paper

DatalogMTL with Negation Under Stable Models Semantics

• Przemysław A. Wałęga
• David J. Tena Cucala
• Egor V. Kostylev
• Bernardo Cuenca Grau

We introduce negation under stable models semantics in DatalogMTL—a temporal extension of Datalog with metric operators. As a result, we obtain a rule language which combines the power of answer set programming with the temporal dimension provided by metric operators. We show that, in this setting, reasoning becomes undecidable over the rationals and decidable in EXPSPACE in data complexity over the integers. We also show that, if we restrict our attention to forward-propagating programs (where rules propagate information in a single temporal direction), reasoning over integers becomes PSPACE-complete in data complexity and hence no harder than over positive programs; however, reasoning over the rationals in this fragment remains undecidable.

KR Conference 2021 Conference Paper

Finitely Materialisable Datalog Programs with Metric Temporal Operators

• Przemysław A. Wałęga
• Michał Zawidzki
• Bernardo Cuenca Grau

DatalogMTL is an extension of Datalog with metric temporal operators that has recently received significant attention. In contrast to plain Datalog, where scalable implementations are often based on materialisation (a. k. a. forward chaining), reasoning algorithms for recursive fragments of DatalogMTL are automata-based and not well suited for practice. In this paper we propose the class of finitely materialisable DatalogMTL programs, for which forward chaining reasoning terminates after finitely many rounds of rule application. We show that, for bounded programs (a large fragment of DatalogMTL where temporal intervals are restricted to not mention infinity), checking whether a program is finitely materialisable is feasible in exponential time, and propose sufficient conditions for finite materialisability that can be checked more efficiently. We finally show that fact entailment over finitely materialisable bounded programs is ExpTime-complete, and hence no harder than Datalog reasoning.

AIJ Journal 2021 Journal Article

Pay-as-you-go consequence-based reasoning for the description logic SROIQ

• David Tena Cucala
• Bernardo Cuenca Grau
• Ian Horrocks

Consequence-based (CB) reasoners combine ideas from resolution and (hyper)tableau calculi for solving key reasoning problems in Description Logics (DLs), such as ontology classification. Existing CB reasoners, however, are only capable of handling DLs without nominals (such as ALCHIQ ), or DLs without disjunction (such as Horn- ALCHOIQ ). In this paper, we present a consequence-based calculus for concept subsumption and classification in the DL ALCHOI Q +, which extends ALC with role hierarchies, inverse roles, number restrictions, and nominals; to the best of our knowledge, ours is the first CB calculus for an NExpTime-complete DL. By using standard transformations, our calculus extends to SROIQ, which covers all of OWL 2 DL except for datatypes. A key feature of our calculus is its pay-as-you-go behaviour: our calculus is worst-case optimal for all the well-known proper fragments of ALCHOI Q +. Furthermore, our calculus can be applied to DL reasoning problems other than subsumption and ontology classification, such as instance retrieval and realisation. We have implemented our calculus as an extension of Sequoia, a CB reasoner which previously supported ontology classification in SRIQ. We have performed an empirical evaluation of our implementation, which shows that Sequoia offers competitive performance. Although there still remains plenty of room for further optimisation, the calculus presented in this paper and its implementation provide an important addition to the repertoire of reasoning techniques and practical systems for expressive DLs.

AAAI Conference 2021 Conference Paper

Stratified Negation in Datalog with Metric Temporal Operators

• David J Tena Cucala
• Przemysław A Wałęga
• Bernardo Cuenca Grau
• Egor Kostylev

We extend DatalogMTL—Datalog with operators from metric temporal logic—by adding stratified negation as failure. The new language provides additional expressive power for representing and reasoning about temporal data and knowledge in a wide range of applications. We consider models over the rational timeline, study their properties, and establish the computational complexity of reasoning. We show that, as in negation-free DatalogMTL, fact entailment in our language is PSPACE-complete in data and EXPSPACE-complete in combined complexity. Thus, the extension with stratified negation does not lead to higher complexity.

AAAI Conference 2020 Conference Paper

Complexity and Expressive Power of Disjunction and Negation in Limit Datalog

• Mark Kaminski
• Bernardo Cuenca Grau
• Egor V. Kostylev
• Ian Horrocks

Limit Datalog is a fragment of DatalogZ—the extension of Datalog with arithmetic functions over the integers—which has been proposed as a declarative language suitable for capturing data analysis tasks. In limit Datalog programs, all intensional predicates with a numeric argument are limit predicates that keep maximal (or minimal) bounds on numeric values. Furthermore, to ensure decidability of reasoning, limit Datalog imposes a linearity condition restricting the use of multiplication in rules. In this paper, we study the complexity and expressive power of limit Datalog programs extended with disjunction in the heads of rules and non-monotonic negation under the stable model semantics. We show that allowing for unrestricted use of negation leads to undecidability of reasoning. Decidability can be restored by stratifying the use of negation over predicates carrying numeric values. We show that the resulting language is ΠEXP 2 -complete in combined complexity and that it captures ΠP 2 over ordered structures in the sense of descriptive complexity. We also provide a study of several fragments of this language: we show that the complexity and expressive power of the full language are already reached for disjunction-free programs; furthermore, we show that semi-positive disjunctive programs are coNEXPcomplete and that they capture coNP.

KR Conference 2020 Conference Paper

DatalogMTL over the Integer Timeline

• Przemysław A. Wałęga
• Bernardo Cuenca Grau
• Mark Kaminski
• Egor V. Kostylev

We study DatalogMTL—an extension of Datalog with metric temporal operators—under integer semantics, where the temporal domain of both interpretations and temporal operators consists of integer time points only. This is in contrast to the standard semantics, which is defined over the rational timeline. DatalogMTL under integer semantics is an interesting KR language: on the one hand, one can often assume the integer timeline in applications; on the other hand, it captures prominent temporal extensions of Datalog such as Datalog1S. We show that the choice of integer semantics leads to more favourable computational properties. We first show that reasoning over integers is at most as hard as reasoning over rationals for DatalogMTL and its natural fragments. Then, we investigate fragments of DatalogMTL where adopting the integer semantics makes reasoning easier. In particular, we show that complexity drops from P-hard to NC1-complete for the propositional fragment (where all object variables are grounded), and from TC0-hard to ACC0 for the linear fragment where the past diamond operator is the only metric operator allowed in rule bodies. Thus, reasoning in such fragments is both tractable and highly parallelisable, which suggests their appropriateness for data-intensive applications.

IJCAI Conference 2020 Conference Paper

Tractable Fragments of Datalog with Metric Temporal Operators

• Przemysław A. Wałęga
• Bernardo Cuenca Grau
• Mark Kaminski
• Egor V. Kostylev

We study the data complexity of reasoning for several fragments of MTL - an extension of Datalog with metric temporal operators over the rational numbers. Reasoning in the full MTL language is PSPACE-complete, which handicaps its application in practice. To achieve tractability we first study the core fragment, which disallows conjunction in rule bodies, and show that reasoning remains PSPACE-hard. Intractability prompts us to also limit the kinds of temporal operators allowed in rules, and we propose a practical core fragment for which reasoning becomes TC0-complete. Finally, we show that this fragment can be extended by allowing linear conjunctions in rule bodies, where at most one atom can be intensional (IDB); we show that the resulting fragment is NL-complete, and hence no harder than plain linear Datalog.

IJCAI Conference 2019 Conference Paper

DatalogMTL: Computational Complexity and Expressive Power

• Przemysław A. Wałęga
• Bernardo Cuenca Grau
• Mark Kaminski
• Egor V. Kostylev

We study the complexity and expressive power of DatalogMTL - a knowledge representation language that extends Datalog with operators from metric temporal logic (MTL) and which has found applications in ontology-based data access and stream reasoning. We establish tight PSpace data complexity bounds and also show that DatalogMTL extended with negation on input predicates can express all queries in PSpace; this implies that MTL operators add significant expressive power to Datalog. Furthermore, we provide tight combined complexity bounds for the forward-propagating fragment of DatalogMTL, which was proposed in the context of stream reasoning, and show that it is possible to express all PSpace queries in the fragment extended with the falsum predicate.

AIJ Journal 2019 Journal Article

Foundations of ontology-based data access under bag semantics

• Charalampos Nikolaou
• Egor V. Kostylev
• George Konstantinidis
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign to ontology predicates views over the data. The conventional semantics of OBDA is set-based—that is, the extension of the views defined by the mappings does not contain duplicate tuples. This treatment is, however, in disagreement with the standard semantics of database views and database management systems in general, which is based on bags and where duplicate tuples are retained by default. The distinction between set and bag semantics in databases is very significant in practice, and it influences the evaluation of aggregate queries. In this article, we propose and study a bag semantics for OBDA which provides a solid foundation for the future study of aggregate and analytic queries. Our semantics is compatible with both the bag semantics of database views and the set-based conventional semantics of OBDA. Furthermore, it is compatible with existing bag-based semantics for data exchange recently proposed in the literature. We show that adopting a bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability of query answering, we consider suitable restrictions along three dimensions, namely, the query language, the ontology language, and the adoption of the unique name assumption. Our investigation shows a complete picture of the computational properties of query answering under bag semantics over ontologies in the DL-Lite family.

JAIR Journal 2019 Journal Article

Logical Foundations of Linked Data Anonymisation

• Bernardo Cuenca Grau
• Egor V. Kostylev

The widespread adoption of the Linked Data paradigm has been driven by the increasing demand for information exchange between organisations, as well as by regulations in domains such as health care and governance that require certain data to be published. In this setting, sensitive information is at high risk of disclosure since published data can be often seamlessly linkedwith arbitrary external data sources.In this paper we lay the logical foundations of anonymisation in the context of Linked Data. We consider anonymisations of RDF graphs (and, more generally, relational datasets with labelled nulls) and define notions of policy-compliant and linkage-safe anonymisations. Policy compliance ensures that an anonymised dataset does not reveal any sensitive information as specified by a policy query. Linkage safety ensures that an anonymised dataset remains compliant even if it is linked to (possibly unknown) external datasets available on the Web, thus providing provable protection guarantees against data linkage attacks. We establish the computational complexity of the underpinning decision problems both under the open-world semantics inherent to RDF and under the assumption that an attacker has complete, closed-world knowledge over some parts of the original data.

AAAI Conference 2019 Conference Paper

Reasoning over Streaming Data in Metric Temporal Datalog

• Przemysław Andrzej Wałęga
• Mark Kaminski
• Bernardo Cuenca Grau

We study stream reasoning in datalogMTL—an extension of Datalog with metric temporal operators. We propose a sound and complete stream reasoning algorithm that is applicable to a fragment datalogMTLFP of datalogMTL, in which propagation of derived information towards past time points is precluded. Memory consumption in our algorithm depends both on the properties of the rule set and the input data stream; in particular, it depends on the distances between timestamps occurring in data. This is undesirable since these distances can be very small, in which case the algorithm may require large amounts of memory. To address this issue, we propose a second algorithm, where the size of the required memory becomes independent on the timestamps in the data at the expense of disallowing punctual intervals in the rule set. Finally, we provide tight bounds to the data complexity of standard query answering in datalogMTLFP without punctual intervals in rules, which yield a new PSPACE lower bound to the data complexity of the full datalogMTL.

IJCAI Conference 2019 Conference Paper

Satisfaction and Implication of Integrity Constraints in Ontology-based Data Access

• Charalampos Nikolaou
• Bernardo Cuenca Grau
• Egor V. Kostylev
• Mark Kaminski
• Ian Horrocks

We extend ontology-based data access with integrity constraints over both the source and target schemas. The relevant reasoning problems in this setting are constraint satisfaction—to check whether a database satisfies the target constraints given the mappings and the ontology—and source-to-target (resp. , target-to-source) constraint implication, which is to check whether a target constraint (resp. , a source constraint) is satisfied by each database satisfying the source constraints (resp. , the target constraints). We establish decidability and complexity bounds for all these problems in the case where ontologies are expressed in DL-LiteR and constraints range from functional dependencies to disjunctive tuple-generating dependencies.

IJCAI Conference 2018 Conference Paper

Consequence-based Reasoning for Description Logics with Disjunction, Inverse Roles, Number Restrictions, and Nominals

• David Tena Cucala
• Bernardo Cuenca Grau
• Ian Horrocks

We present a consequence-based calculus for concept subsumption and classification in the description logic ALCHOIQ, which extends ALC with role hierarchies, inverse roles, number restrictions, and nominals. By using standard transformations, our calculus extends to SROIQ, which covers all of OWL 2 DL except for datatypes. A key feature of our calculus is its pay-as-you-go behaviour: unlike existing algorithms, our calculus is worst-case optimal for all the well-known proper fragments of ALCHOIQ, albeit not for the full logic.

JAIR Journal 2018 Journal Article

Consequence-Based Reasoning for Description Logics with Disjunctions and Number Restrictions

• Andrew Bate
• Boris Motik
• Bernardo Cuenca Grau
• David Tena Cucala
• František Simančík
• Ian Horrocks

Classification of description logic (DL) ontologies is a key computational problem in modern data management applications, so considerable effort has been devoted to the development and optimisation of practical reasoning calculi. Consequence-based calculi combine ideas from hypertableau and resolution in a way that has proved very effective in practice. However, existing consequence-based calculi can handle either Horn DLs (which do not support disjunction) or DLs without number restrictions. In this paper, we overcome this important limitation and present the first consequence-based calculus for deciding concept subsumption in the DL ALCHIQ+. Our calculus runs in exponential time assuming unary coding of numbers, and on ELH ontologies it runs in polynomial time. The extension to disjunctions and number restrictions is technically involved: we capture the relevant consequences using first-order clauses, and our inference rules adapt paramodulation techniques from first-order theorem proving. By using a well-known preprocessing step, the calculus can also decide concept subsumptions in SRIQ---a rich DL that covers all features of OWL 2 DL apart from nominals and datatypes. We have implemented our calculus in a new reasoner called Sequoia. We present the architecture of our reasoner and discuss several novel and important implementation techniques such as clause indexing and redundancy elimination. Finally, we present the results of an extensive performance evaluation, which revealed Sequoia to be competitive with existing reasoners. Thus, the calculus and the techniques we present in this paper provide an important addition to the repertoire of practical implementation techniques for description logic reasoning.

AIJ Journal 2018 Journal Article

Logical foundations of information disclosure in ontology-based data integration

• Michael Benedikt
• Bernardo Cuenca Grau
• Egor V. Kostylev

Ontology-based data integration systems allow users to effectively access data sitting in multiple sources by means of queries over a global schema described by an ontology. In practice, data sources often contain sensitive information that the data owners want to keep inaccessible to users. Our aim in this paper is to lay the logical foundations of information disclosure in ontology-based data integration. Our focus is on the semantic requirements that a data integration system should satisfy before it is made available to users for querying, as well as on the computational complexity of checking whether such requirements are fulfilled. In particular, we formalise and study the problem of determining whether a given data integration system discloses a source query to an attacker. We consider disclosure on a particular dataset, and also whether a schema admits a dataset on which disclosure occurs. We provide matching lower and upper complexity bounds on disclosure analysis, in the process introducing a number of techniques for analysing logical privacy issues in ontology-based data integration.

IJCAI Conference 2018 Conference Paper

Stratified Negation in Limit Datalog Programs

• Mark Kaminski
• Bernardo Cuenca Grau
• Egor V. Kostylev
• Boris Motik
• Ian Horrocks

There has recently been an increasing interest in declarative data analysis, where analytic tasks are specified using a logical language, and their implementation and optimisation are delegated to a general-purpose query engine. Existing declarative languages for data analysis can be formalised as variants of logic programming equipped with arithmetic function symbols and/or aggregation, and are typically undecidable. In prior work, the language of limit programs was proposed, which is sufficiently powerful to capture many analysis tasks and has decidable entailment problem. Rules in this language, however, do not allow for negation. In this paper, we study an extension of limit programs with stratified negation-as-failure. We show that the additional expressive power makes reasoning computationally more demanding, and provide tight data complexity bounds. We also identify a fragment with tractable data complexity and sufficient expressivity to capture many relevant tasks.

AAAI Conference 2018 Conference Paper

Stream Reasoning in Temporal Datalog

• Alessandro Ronca
• Mark Kaminski
• Bernardo Cuenca Grau
• Boris Motik
• Ian Horrocks

In recent years, there has been an increasing interest in extending traditional stream processing engines with logical, rule-based, reasoning capabilities. This poses significant theoretical and practical challenges since rules can derive new information and propagate it both towards past and future time points; as a result, streamed query answers can depend on data that has not yet been received, as well as on data that arrived far in the past. Stream reasoning algorithms, however, must be able to stream out query answers as soon as possible, and can only keep a limited number of previous input facts in memory. In this paper, we propose novel reasoning problems to deal with these challenges, and study their computational properties on Datalog extended with a temporal sort and the successor function—a core rule-based language for stream reasoning applications.

KR Conference 2018 Conference Paper

The Window Validity Problem in Rule-Based Stream Reasoning

• Alessandro Ronca
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

Rule-based temporal query languages provide the expressive power and flexibility required to capture in a natural way complex analysis tasks over streaming data. Stream processing applications, however, typically require near real-time response using limited resources. In particular, it becomes essential that the underpinning query language has favourable computational properties and that stream processing algorithms are able to keep only a small number of previously received facts in memory at any point in time without sacrificing correctness. In this paper, we propose a recursive fragment of temporal Datalog with tractable data complexity and study the properties of a generic stream reasoning algorithm for this fragment. We focus on the window validity problem as a way to minimise the number of time points for which the stream reasoning algorithm needs to keep data in memory at any point in time.

IJCAI Conference 2017 Conference Paper

Foundations of Declarative Data Analysis Using Limit Datalog Programs

• Mark Kaminski
• Bernardo Cuenca Grau
• Egor V. Kostylev
• Boris Motik
• Ian Horrocks

Motivated by applications in declarative data analysis, we study DatalogZ---an extension of positive Datalog with arithmetic functions over integers. This language is known to be undecidable, so we propose two fragments. In limit DatalogZ predicates are axiomatised to keep minimal/maximal numeric values, allowing us to show that fact entailment is coNExpTime-complete in combined, and coNP-complete in data complexity. Moreover, an additional stability requirement causes the complexity to drop to ExpTime and PTime, respectively. Finally, we show that stable DatalogZ can express many useful data analysis tasks, and so our results provide a sound foundation for the development of advanced information systems.

AAAI Conference 2017 Conference Paper

Source Information Disclosure in Ontology-Based Data Integration

• Michael Benedikt
• Bernardo Cuenca Grau
• Egor Kostylev

Ontology-based data integration systems allow users to effectively access data sitting in multiple sources by means of queries over a global schema described by an ontology. In practice, datasources often contain sensitive information that the data owners want to keep inaccessible to users. In this paper, we formalize and study the problem of determining whether a given data integration system discloses a source query to an attacker. We consider disclosure on a particular dataset, and also whether a schema admits a dataset on which disclosure occurs. We provide lower and upper bounds on disclosure analysis, in the process introducing a number of techniques for analyzing logical privacy issues in ontology-based data integration.

IJCAI Conference 2017 Conference Paper

The Bag Semantics of Ontology-Based Data Access

• Charalampos Nikolaou
• Egor V. Kostylev
• George Konstantinidis
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

Ontology-based data access (OBDA) is a popular approach for integrating and querying multiple data sources by means of a shared ontology. The ontology is linked to the sources using mappings, which assign views over the data to ontology predicates. Motivated by the need for OBDA systems supporting database-style aggregate queries, we propose a bag semantics for OBDA, where duplicate tuples in the views defined by the mappings are retained, as is the case in standard databases. We show that bag semantics makes conjunctive query answering in OBDA coNP-hard in data complexity. To regain tractability, we consider a rather general class of queries and show its rewritability to a generalisation of the relational calculus to bags.

AIJ Journal 2016 Journal Article

Datalog rewritability of Disjunctive Datalog programs and non-Horn ontologies

• Mark Kaminski
• Yavor Nenov
• Bernardo Cuenca Grau

We study the problem of rewriting a Disjunctive Datalog program into an equivalent plain Datalog program (i. e. , one that entails the same facts for every dataset). We show that a Disjunctive Datalog program is Datalog rewritable if and only if it can be rewritten into a linear program (i. e. , having at most one IDB body atom in each rule), thus providing a novel characterisation of Datalog rewritability in terms of linearisability. Motivated by this result, we propose the class of markable programs, which extends both Datalog and linear Disjunctive Datalog and admits Datalog rewritings of polynomial size. We show that our results can be seamlessly applied to ontological reasoning and identify two classes of non-Horn ontologies that admit Datalog rewritings of polynomial and exponential size, respectively. Finally, we shift our attention to conjunctive query answering and extend our results to the problem of computing a rewriting of a Disjunctive Datalog program that yields the same answers to a given query w. r. t. arbitrary data. Our empirical results suggest that a fair number of non-Horn ontologies are Datalog rewritable and that query answering over such ontologies becomes feasible using a Datalog engine.

KR Conference 2016 Conference Paper

Extending Consequence-Based Reasoning to SRIQ

• Andrew Bate
• Boris Motik
• Bernardo Cuenca Grau
• Frantisek Simancik
• Ian Horrocks

Consequence-based calculi are a family of reasoning algorithms for description logics (DLs), and they combine hypertableau and resolution in a way that often achieves excellent performance in practice. Up to now, however, they were proposed for either Horn DLs (which do not support disjunction), or for DLs without counting quantifiers. In this paper we present a novel consequence-based calculus for SRIQ— a rich DL that supports both features. This extension is nontrivial since the intermediate consequences that need to be derived during reasoning cannot be captured using DLs themselves. The results of our preliminary performance evaluation suggest the feasibility of our approach in practice.

AAAI Conference 2016 Conference Paper

Logical Foundations of Privacy-Preserving Publishing of Linked Data

• Bernardo Cuenca Grau
• Egor Kostylev

The widespread adoption of Linked Data has been driven by the increasing demand for information exchange between organisations, as well as by data publishing regulations in domains such as health care and governance. In this setting, sensitive information is at risk of disclosure since published data can be linked with arbitrary external data sources. In this paper we lay the foundations of privacy-preserving data publishing (PPDP) in the context of Linked Data. We consider anonymisations of RDF graphs (and, more generally, relational datasets with labelled nulls) and define notions of safe and optimal anonymisations. Safety ensures that the anonymised data can be published with provable protection guarantees against linking attacks, whereas optimality ensures that it preserves as much information from the original data as possible, while satisfying the safety requirement. We establish the complexity of the underpinning decision problems both under open-world semantics inherent to RDF and a closed-world semantics, where we assume that an attacker has complete knowledge over some part of the original data.

JAIR Journal 2016 Journal Article

Module Extraction in Expressive Ontology Languages via Datalog Reasoning

• Ana Armas Romero
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

Module extraction is the task of computing a (preferably small) fragment M of an ontology T that preserves a class of entailments over a signature of interest S. Extracting modules of minimal size is well-known to be computationally hard, and often algorithmically infeasible, especially for highly expressive ontology languages. Thus, practical techniques typically rely on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations ensure that M preserves all second-order entailments of T w.r.t. S, which is a stronger condition than is required in many applications, and may lead to unnecessarily large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach generalises existing approximations in an elegant way. More importantly, it allows extraction of modules that are tailored to preserve only specific kinds of entailments, and thus are often significantly smaller. Our evaluation on a wide range of ontologies confirms the feasibility and benefits of our approach in practice.

IJCAI Conference 2015 Conference Paper

Computing Horn Rewritings of Description Logics Ontologies

• Mark Kaminski
• Bernardo Cuenca Grau

We study the problem of rewriting an ontology O1 expressed in a DL L1 into an ontology O2 in a Horn DL L2 such that O1 and O2 are equisatisfiable when extended with an arbitrary dataset. Ontologies that admit such rewritings are amenable to reasoning techniques ensuring tractability in data complexity. After showing undecidability whenever L1 extends ALCF, we focus on devising efficiently checkable conditions that ensure existence of a Horn rewriting. By lifting existing techniques for rewriting Disjunctive Datalog programs into plain Datalog to the case of arbitrary first-order programs with function symbols, we identify a class of ontologies that admit Horn rewritings of polynomial size. Our experiments indicate that many real-world ontologies satisfy our sufficient conditions and thus admit polynomial Horn rewritings.

IJCAI Conference 2015 Conference Paper

Controlled Query Evaluation for Datalog and OWL 2 Profile Ontologies

• Bernardo Cuenca Grau
• Evgeny Kharlamov
• Egor V. Kostylev
• Dmitriy Zheleznyakov

We study confidentiality enforcement in ontologies under the Controlled Query Evaluation framework, where a policy specifies the sensitive information and a censor ensures that query answers that may compromise the policy are not returned. We focus on censors that ensure confidentiality while maximising information access, and consider both Datalog and the OWL 2 profiles as ontology languages.

AAAI Conference 2015 Conference Paper

Ontology Module Extraction via Datalog Reasoning

• Ana Armas Romero
• Mark Kaminski
• Bernardo Cuenca Grau
• Ian Horrocks

Module extraction—the task of computing a (preferably small) fragment M of an ontology T that preserves entailments over a signature Σ—has found many applications in recent years. Extracting modules of minimal size is, however, computationally hard, and often algorithmically infeasible. Thus, practical techniques are based on approximations, where M provably captures the relevant entailments, but is not guaranteed to be minimal. Existing approximations, however, ensure that M preserves all second-order entailments of T w. r. t. Σ, which is stronger than is required in many applications, and may lead to large modules in practice. In this paper we propose a novel approach in which module extraction is reduced to a reasoning problem in datalog. Our approach not only generalises existing approximations in an elegant way, but it can also be tailored to preserve only specific kinds of entailments, which allows us to extract significantly smaller modules. An evaluation on widely-used ontologies has shown very encouraging results.

JAIR Journal 2015 Journal Article

PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner

• Yujiao Zhou
• Bernardo Cuenca Grau
• Yavor Nenov
• Mark Kaminski
• Ian Horrocks

Answering conjunctive queries over ontology-enriched datasets is a core reasoning task for many applications. Query answering is, however, computationally very expensive, which has led to the development of query answering procedures that sacrifice either expressive power of the ontology language, or the completeness of query answers in order to improve scalability. In this paper, we describe a hybrid approach to query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable `pay-as-you-go' performance. The key feature of our approach is that it delegates the bulk of the computation to the datalog reasoner and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. Furthermore, although our main goal is to efficiently answer queries over OWL 2 ontologies and data, our technical results are very general and our approach is applicable to first-order knowledge representation languages that can be captured by rules allowing for existential quantification and disjunction in the head; our only assumption is the availability of a datalog reasoner and a fully-fledged reasoner for the language of interest, both of which are used as `black boxes'. We have implemented our techniques in the PAGOdA system, which combines the datalog reasoner RDFox and the OWL 2 reasoner HermiT. Our extensive evaluation shows that PAGOdA succeeds in providing scalable pay-as-you-go query answering for a wide range of OWL 2 ontologies, datasets and queries.

IJCAI Conference 2015 Conference Paper

The Combined Approach to Query Answering Beyond the OWL 2 Profiles

• Cristina Feier
• David Carral
• Giorgio Stefanoni
• Bernardo Cuenca Grau
• Ian Horrocks

Combined approaches have become a successful technique for CQ answering over ontologies. Existing algorithms, however, are restricted to the logics underpinning the OWL 2 profiles. Our goal is to make combined approaches applicable to a wider range of ontologies. We focus on RSA: a class of Horn ontologies that extends the profiles while ensuring tractability of standard reasoning. We show that CQ answering over RSA ontologies without role composition is feasible in NP. Our reasoning procedure generalises the combined approach for ELHO and DL-LiteR using an encoding of CQ answering into fact entailment w. r. t. a logic program with function symbols and stratified negation. Our results have significant practical implications since many out-of-profile Horn ontologies are RSA.

AAAI Conference 2014 Conference Paper

Datalog Rewritability of Disjunctive Datalog Programs and its Applications to Ontology Reasoning

• Mark Kaminski
• Yavor Nenov
• Bernardo Cuenca Grau

We study the problem of rewriting a disjunctive datalog program into plain datalog. We show that a disjunctive program is rewritable if and only if it is equivalent to a linear disjunctive program, thus providing a novel characterisation of datalog rewritability. Motivated by this result, we propose weakly linear disjunctive datalog—a novel rule-based KR language that extends both datalog and linear disjunctive datalog and for which reasoning is tractable in data complexity. We then explore applications of weakly linear programs to ontology reasoning and propose a tractable extension of OWL 2 RL with disjunctive axioms. Our empirical results suggest that many non-Horn ontologies can be reduced to weakly linear programs and that query answering over such ontologies using a datalog engine is feasible in practice.

AAAI Conference 2014 Conference Paper

Pay-As-You-Go OWL Query Answering Using a Triple Store

• Yujiao Zhou
• Yavor Nenov
• Bernardo Cuenca Grau
• Ian Horrocks

We present an enhanced hybrid approach to OWL query answering that combines an RDF triple-store with an OWL reasoner in order to provide scalable pay-as-you-go performance. The enhancements presented here include an extension to deal with arbitrary OWL ontologies, and optimisations that significantly improve scalability. We have implemented these techniques in a prototype system, a preliminary evaluation of which has produced very encouraging results.

IJCAI Conference 2013 Conference Paper

Computing Datalog Rewritings Beyond Horn Ontologies

• Bernardo Cuenca Grau
• Boris Motik
• Giorgos Stoilos
• Ian Horrocks

Rewriting-based approaches for answering queries over an OWL 2 DL ontology have so far been developed mainly for Horn fragments of OWL 2 DL. In this paper, we study the possibilities of answering queries over non-Horn ontologies using datalog rewritings. We prove that this is impossible in general even for very simple ontology languages, and even if PTIME = NP. Furthermore, we present a resolution-based procedure for SHI ontologies that, in case it terminates, produces a datalog rewriting of the ontology. We also show that our procedure necessarily terminates on DL-LiteH, + bool ontologies—an extension of OWL 2 QL with transitive roles and Boolean connectives.

KR Conference 2012 Conference Paper

Acyclicity Conditions and their Application to Query Answering in Description Logics

• Bernardo Cuenca Grau
• Ian Horrocks
• Markus Krötzsch
• Clemens Kupke
• Despoina Magka
• Boris Motik
• Zhe Wang

problem in both database and KR settings. This problem is undecidable (Beeri and Vardi 1981) in general, and it can be characterised using chase (Johnson and Klug 1984; Maier, Mendelzon, and Sagiv 1979), a technique closely related to the hypertableau calculus (Motik, Shearer, and Horrocks 2009). The chase extends in a forward-chaining manner the original set of facts by introducing facts implied by the rules. The result of the chase is called the universal model, and an arbitrary conjunctive query can be answered over the original set of facts and the rules by simply evaluating the query in the universal model. Rules with existentially quantified variables in the head— so-called generating rules—require the introduction of fresh individuals, and cyclic applications of generating rules may lead to non-termination; moreover, determining whether chase terminates on a set of rules and facts is undecidable. However, several decidable classes of existential rules have been identified, and the existing proposals can be classified into two main groups. In the first group, rules are restricted such that their (possibly infinite) universal models can be represented using finitary means. This group includes rules with universal models of bounded treewidth (Baget et al. 2011), guarded rules (Calı̀ et al. 2010), and ‘sticky’ rules (Calı̀, Gottlob, and Pieris 2011). In the second group, one uses a sufficient (but not necessary) acyclicity condition that ensures chase termination. Roughly speaking, acyclicity conditions analyse information flow between the rules to ensure that no cyclic applications of generating rules are possible. Weak acyclicity (WA) (Fagin et al. 2005) was one of the first such notions, and it was extended to safety (SF) (Meier, Schmidt, and Lausen 2009), stratification (ST) (Deutsch, Nash, and Remmel 2008), acyclicity of a graph of rule dependencies (aGRD) (Baget, Mugnier, and Thomazo 2011), joint acyclicity (JA) (Krötzsch and Rudolph 2011), and super-weak acyclicity (SWA) (Marnette 2009). Acyclicity conditions are relevant for at least two reasons. First, unlike guarded rules, acyclic rules can axiomatise structures of arbitrary shapes, as long as these structures are bounded in size. Second, the chase result for acyclic rules can be stored and manipulated as if it were a database. This is important in data exchange, where the goal is to materialise the transformed database. In this paper, we argue that acyclicity is also relevant for description logics (DLs), the KR formalisms underpin- Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a key problem in knowledge representation and databases. This problem can be solved using the chase (aka materialisation) algorithm; however, CQ answering is undecidable for general existential rules, so the chase is not guaranteed to terminate. Several acyclicity conditions provide sufficient conditions for chase termination. In this paper, we present two novel such conditions—modelfaithful acyclicity (MFA) and model-summarising acyclicity (MSA)—that generalise many of the acyclicity conditions known so far in the literature. Materialisation provides the basis for several widely-used OWL 2 DL reasoners. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2 DL; furthermore, some systems go beyond OWL 2 RL, but they provide no termination guarantees. In this paper we investigate whether various acyclicity conditions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 DL ontologies are MSA, and that the facts obtained via materialisation are not too large. Thus, our results suggest that principled extensions to materialisationbased OWL 2 DL reasoners may be practically feasible.

AAAI Conference 2012 Conference Paper

Benchmarking Ontology-Based Query Rewriting Systems

• Martha Imprialou
• Giorgos Stoilos
• Bernardo Cuenca Grau

Query rewriting is a prominent reasoning technique in ontology-based data access applications. A wide variety of query rewriting algorithms have been proposed in recent years and implemented in highly optimised reasoning systems. Query rewriting systems are complex software programs; even if based on provably correct algorithms, sophisticated optimisations make the systems more complex and errors become more likely to happen. In this paper, we present an algorithm that, given an ontology as input, synthetically generates “relevant” test queries. Intuitively, each of these queries can be used to verify whether the system correctly performs a certain set of “inferences”, each of which can be traced back to axioms in the input ontology. Furthermore, we present techniques that allow us to determine whether a system is unsound and/or incomplete for a given test query and ontology. Our evaluation shows that most publicly available query rewriting systems are unsound and/or incomplete, even on commonly used benchmark ontologies; more importantly, our techniques revealed the precise causes of their correctness issues and the systems were then corrected based on our feedback. Finally, since our evaluation is based on a larger set of test queries than existing benchmarks, which are based on hand-crafted queries, it also provides a better understanding of the scalability behaviour of each system.

ECAI Conference 2012 Conference Paper

Large-scale Interactive Ontology Matching: Algorithms and Implementation

• Ernesto Jiménez-Ruiz
• Bernardo Cuenca Grau
• Yujiao Zhou
• Ian Horrocks 0001

In this paper we present the ontology matching system LogMap 2, a much improved version of its predecessor LogMap. LogMap 2 supports user interaction during the matching process, which is essential for use cases requiring very accurate mappings. Interactivity, however, imposes very strict scalability requirements; we are able to satisfy these requirements by providing real-time user response even for large-scale ontologies. Finally, LogMap 2 implements scalable reasoning and diagnosis algorithms, which minimise any logical inconsistencies introduced by the matching process.

KR Conference 2012 Conference Paper

Ontology Evolution under Semantic Constraints

• Bernardo Cuenca Grau
• Ernesto Jimenez-Ruiz
• Evgeny Kharlamov
• Dmitriy Zheleznyakov

2011; Konev, Walther, and Wolter 2008; Gonçalves, Parsia, and Sattler 2011). In AI and Belief Revision, the process of “incorporating” new information into a knowledge base (KB) is called revision, whereas the process of “retracting” information that is no longer considered to hold is called contraction (Alchourrón, Gärdenfors, and Makinson 1985; Peppas 2007). The properties that revision and contraction operators need to satisfy are dictated by the principle of minimal change (Alchourrón, Gärdenfors, and Makinson 1985), according to which the semantics of a KB should change “as little as possible”, thus ensuring that modifications have the least possible impact. A distinction is often made between revision and update, where the purpose of the latter is to bring the KB up to date when the world changes (Katsuno and Mendelzon 1991; Kharlamov and Zheleznyakov 2011; Liu et al. 2011). In this paper, however, we use the term evolution to encompass revision and contraction, and we do not consider here the problem of update. Logic-based semantics derived from the principle of minimal change have been recently studied in the context of ontology evolution. These semantics are either model-based (MBS) or formula-based (FBS). Under both semantics, evolution of an LO-ontology O results in an LO0 -ontology O0 that incorporates (or retracts) the required information, and the difference lies in the way O0 is obtained. Under MBS the set of all models M of O is evolved into a new set M0 of models that are “as close as possible” to those in M (w. r. t. some notion of distance between models); then, O0 is the ontology that axiomatises M0 (Qi and Du 2009; Giacomo et al. 2009; Calvanese et al. 2010; Kharlamov and Zheleznyakov 2011; Wang, Wang, and Topor 2010b; 2010a). MBSs, however, suffer from intrinsic inexpressibility problems, even for lightweight DLs such as DL-Lite (Calvanese et al. 2007), where axiomatisation of M0 requires a DL with disjunction and nominals (Kharlamov and Zheleznyakov 2011). Under FBS, O0 is defined as a maximal subset of the deductive closure of O (under LO-consequences) that satisfies the evolution requirements. FBSs for DLs have been less studied. In particular, existing results (Calvanese et al. 2010; Lenzerini and Savo 2011) are restricted to DL-Lite, where the closure of O is finite. It is unknown, however, how to compute O0 if the closure of O is infinite, as is the case when O is an EL ontology (Baader, Brandt, and Lutz 2005). The dynamic nature of ontology development has motivated the formal study of ontology evolution problems. This paper presents a logical framework that enables fine-grained investigation of evolution problems at a deductive level. In our framework, the optimal evolutions of an ontology O are those ontologies O0 that maximally preserve both the structure of O, and its entailments in a given preservation language. We show that our framework is compatible with the postulates of Belief Revision, and we investigate the existence of optimal evolutions in various settings. In particular, we present first results on TBox-level revision and contraction in the EL and F L0 families of Description Logics.

IJCAI Conference 2011 Conference Paper

What to Ask to an Incomplete Semantic Web Reasoner?

• Bernardo Cuenca Grau
• Giorgos Stoilos

Largely motivated by Semantic Web applications, many highly scalable, but incomplete, query answering systems have been recently developed. Evaluating the scalability-completeness trade-off exhibited by such systems is an important requirement for many applications. In this paper, we address the problem of formally comparing complete and incomplete systems given an ontology schema (or TBox) T. We formulate precise conditions on TBoxes T expressed in the EL, QL or RL profile of OWL 2 under which an incomplete system is indistinguishable from a complete one w. r. t. T, regardless of the input query and data. Our results also allow us to quantify the "degree of incompleteness" of a given system w. r. t. T as well as to automatically identify concrete queries and data patterns for which the incomplete system will miss answers.

AAAI Conference 2010 Conference Paper

How Incomplete Is Your Semantic Web Reasoner?

• Giorgos Stoilos
• Bernardo Cuenca Grau
• Ian Horrocks

Conjunctive query answering is a key reasoning service for many ontology-based applications. In order to improve scalability, many Semantic Web query answering systems give up completeness (i. e. , they do not guarantee to return all query answers). It may be useful or even critical to the designers and users of such systems to understand how much and what kind of information is (potentially) being lost. We present a method for generating test data that can be used to provide at least partial answers to these questions, a purpose for which existing benchmarks are not well suited. In addition to developing a general framework that formalises the problem, we describe practical data generation algorithms for some popular ontology languages, and present some very encouraging results from our preliminary evaluation.

KR Conference 2010 Conference Paper

Pushing the Limits of Reasoning over Ontologies with Hidden Content

• Bernardo Cuenca Grau
• Boris Motik

There is currently a growing interest in techniques for hiding parts of the signature of an ontology Kh that is being reused by another ontology Kv. Towards this goal, Cuenca Grau, Motik, and Kazakov (2009) recently proposed the import-byquery framework, which makes the content of Kh accessible through a limited query interface. If Kv reuses the symbols from Kh in a certain restricted way, one can reason over Kv ∪ Kh by accessing only Kv and the query interface. In this paper, we map out the landscape of the import-by-query problem. We show that certain restrictions of our original framework are strictly necessary to make reasoning possible, we propose extensions that overcome some of the expressivity limitations, we present several novel reasoning algorithms, and we outline the limitations of the new framework.

IJCAI Conference 2009 Conference Paper

• Bernardo Cuenca Grau
• Boris Motik
• Yevgeny Kazakov

To enable ontology reuse, the Web Ontology Language (OWL) allows an ontology Kv to import an ontology Kh. To reason with such a Kv, a reasoner needs physical access to the axioms of Kh. For copyright and/or privacy reasons, however, the authors of Kh might not want to publish the axioms of Kh; instead, they might prefer to provide an oracle that can answer a (limited) set of queries over Kh, thus allowing Kv to import Kh “by query. ” In this paper, we study import-by-query algorithms, which can answer questions about Kv ∪ Kh by accessing only Kv and the oracle. We show that no such algorithm exists in general, and present restrictions under which importing by query becomes feasible.

AIJ Journal 2009 Journal Article

Representing ontologies using description logics, description graphs, and rules

• Boris Motik
• Bernardo Cuenca Grau
• Ian Horrocks
• Ulrike Sattler

Description logics (DLs) are a family of state-of-the-art knowledge representation languages, and their expressive power has been carefully crafted to provide useful knowledge modeling primitives while allowing for practically effective decision procedures for the basic reasoning problems. Recent experience with DLs, however, has shown that their expressivity is often insufficient to accurately describe structured objects—objects whose parts are interconnected in arbitrary, rather than tree-like ways. DL knowledge bases describing structured objects are therefore usually underconstrained, which precludes the entailment of certain consequences and causes performance problems during reasoning. To address this problem, we propose an extension of DL languages with description graphs—a knowledge modeling construct that can accurately describe objects with parts connected in arbitrary ways. Furthermore, to enable modeling the conditional aspects of structured objects, we also extend DLs with rules. We present an in-depth study of the computational properties of such a formalism. In particular, we first identify the sources of undecidability of the general, unrestricted formalism. Based on that analysis, we then investigate several restrictions of the general formalism that make reasoning decidable. We present practical evidence that such a logic can be used to model nontrivial structured objects. Finally, we present a practical decision procedure for our formalism, as well as tight complexity bounds.

ECAI Conference 2008 Conference Paper

Privacy-Preserving Query Answering in Logic-based Information Systems

• Bernardo Cuenca Grau
• Ian Horrocks 0001

We study privacy guarantees for the owner of an information system who wants to share some of the information in the system with clients while keeping some other information secret. The privacy guarantees ensure that publishing the new information will not compromise the secret one. We present a framework for describing privacy guarantees that generalises existing probabilistic frameworks in relational databases. We also formulate different flavors of privacy-preserving query answering as novel, purely logic-based reasoning problems and establish general connections between these reasoning problems and the probabilistic privacy guarantees.

KR Conference 2008 Conference Paper

Representing Structured Objects using Description Graphs

• Boris Motik
• Bernardo Cuenca Grau
• Ian Horrocks
• Ulrike Sattler

State-of-the-art ontology languages are often not sufficiently expressive to accurately represent domains consisting of objects connected in a complex way. As a possible remedy, in our previous work we have proposed an extension of ontology languages with description graphs. In this paper, we extend this formalism by allowing for multiple graphs that can be combined in complex ways, thus obtaining a powerful language for modeling structured objects. By imposing a particular acyclicity restriction on the relationships between the graphs, we ensure that checking satisfiability of knowledge bases expressed in our language is decidable. We also present a practical reasoning algorithm.

IJCAI Conference 2007 Conference Paper

• Bernardo Cuenca Grau
• Ian Horrocks
• Yevgeny Kazakov
• Ulrike Sattler

Modularity is a key requirement for collaborative ontology engineering and for distributed ontology reuse on the Web. Modern ontology languages, such as OWL, are logic-based, and thus a useful notion of modularity needs to take the semantics of ontologies and their implications into account. We propose a logic-based notion of modularity that allows the modeler to specify the external signature of their ontology, whose symbols are assumed to be defined in some other ontology. We define two restrictions on the usage of the external signature, a syntactic and a slightly less restrictive, semantic one, each of which is decidable and guarantees a certain kind of "black-box" behavior, which enables the controlled merging of ontologies. Analysis of real-world ontologies suggests that these restrictions are not too onerous.

KR Conference 2006 Conference Paper

From Wine to Water: Optimizing Description Logic Reasoning for Nominals

• Evren Sirin
• Bernardo Cuenca Grau
• Bijan Parsia

OWL-DL is a World Wide Web Consortium standard for representing ontologies on the Semantic Web. It can be seen as a syntactic variant of the Description Logic SHOIN(D), with an OWL-DL ontology corresponding to a SHOIN(D) knowledge base. The very recent accomplishment of a decision procedure for SHOIN(D) poses the challenge of turning the decision procedure into a practical implementation. In particular, we emphasize the need of new optimization techniques for nominals, especially in the presence of large number of individuals in the KB. In this paper, we present new techniques for optimizing DL reasoning in the presence of nominals in the TBox and individuals in a large ABox. We have integrated our optimizations in the open-source Pellet reasoner, which is sound and complete for SHOIN(D), and found that they suffice for efficiently classifying the famous Wine Ontology. We also show that these optimization techniques produce significant performance improvements in other widely used ontologies containing nominals, such as the OWL-S and AKT ontologies.

KR Conference 2006 Conference Paper

Modularity and Web Ontologies

• Bernardo Cuenca Grau
• Bijan Parsia
• Evren Sirin
• Aditya Kalyanpur

Modularity in ontologies is key both for large scale ontology development and for distributed ontology reuse on the Web. However, the problems of formally characterizing a modular representation, on the one hand, and of automatically identifying modules within an OWL ontology, on the other, has not been satisfactorily addressed, although their relevance has been widely accepted by the Ontology Engineering and Semantic Web communities. In this paper, we provide a notion of modularity grounded on the semantics of OWL-DL. We present an algorithm for automatically identifying and extracting modules from OWL-DL ontologies, an implementation and some promising empirical results on real-world ontologies.