Ian Horrocks

NeurIPS Conference 2025 Conference Paper

Sound Logical Explanations for Mean Aggregation Graph Neural Networks

• Matthew Morris
• Ian Horrocks

Graph neural networks (GNNs) are frequently used for knowledge graph completion. Their black-box nature has motivated work that uses sound logical rules to explain predictions and characterise their expressivity. However, despite the prevalence of GNNs that use mean as an aggregation function, explainability and expressivity results are lacking for them. We consider GNNs with mean aggregation and non-negative weights (MAGNNs), proving the precise class of monotonic rules that can be sound for them, as well as providing a restricted fragment of first-order logic to explain any MAGNN prediction. Our experiments show that restricting mean-aggregation GNNs to have non-negative weights yields comparable or improved performance on standard inductive benchmarks, that sound rules are obtained in practice, that insightful explanations can be generated in practice, and that the sound rules can expose issues in the trained models.

NeurIPS Conference 2024 Conference Paper

Language Models as Hierarchy Encoders

• Yuan He
• Zhangdie Yuan
• Jiaoyan Chen
• Ian Horrocks

Interpreting hierarchical structures latent in language is a key limitation of current language models (LMs). While previous research has implicitly leveraged these hierarchies to enhance LMs, approaches for their explicit encoding are yet to be explored. To address this, we introduce a novel approach to re-train transformer encoder-based LMs as Hierarchy Transformer encoders (HiTs), harnessing the expansive nature of hyperbolic space. Our method situates the output embedding space of pre-trained LMs within a Poincaré ball with a curvature that adapts to the embedding dimension, followed by re-training on hyperbolic clustering and centripetal losses. These losses are designed to effectively cluster related entities (input as texts) and organise them hierarchically. We evaluate HiTs against pre-trained LMs, standard fine-tuned LMs, and several hyperbolic embedding baselines, focusing on their capabilities in simulating transitive inference, predicting subsumptions, and transferring knowledge across hierarchies. The results demonstrate that HiTs consistently outperform all baselines in these tasks, underscoring the effectiveness and transferability of our re-trained hierarchy encoders.

AAAI Conference 2024 Conference Paper

Optimised Storage for Datalog Reasoning

• Xinyue Zhang
• Pan Hu
• Yavor Nenov
• Ian Horrocks

Materialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. However, storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given set of facts is large. We observe that for certain combinations of rules, there exist data structures that compactly represent the reasoning result and can be efficiently queried when necessary. In this paper, we present a general framework that allows for the integration of such optimised storage schemes with standard materialisation algorithms. Moreover, we devise optimised storage schemes targeting at transitive rules and union rules, two types of (combination of) rules that commonly occur in practice. Our experimental evaluation shows that our approach significantly improves memory consumption, sometimes by orders of magnitude, while remaining competitive in terms of query answering time.

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.

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.

IJCAI Conference 2023 Conference Paper

Enhancing Datalog Reasoning with Hypertree Decompositions

• Xinyue Zhang
• Pan Hu
• Yavor Nenov
• Ian Horrocks

Datalog reasoning based on the seminaive evaluation strategy evaluates rules using traditional join plans, which often leads to redundancy and inefficiency in practice, especially when the rules are complex. Hypertree decompositions help identify efficient query plans and reduce similar redundancy in query answering. However, it is unclear how this can be applied to materialisation and incremental reasoning with recursive Datalog programs. Moreover, hypertree decompositions require additional data structures and thus introduce nonnegligible overhead in both runtime and memory consumption. In this paper, we provide algorithms that exploit hypertree decompositions for the materialisation and incremental evaluation of Datalog programs. Furthermore, we combine this approach with standard Datalog reasoning algorithms in a modular fashion so that the overhead caused by the decompositions is reduced. Our empirical evaluation shows that, when the program contains complex rules, the combined approach is usually significantly faster than the baseline approach, sometimes by orders of magnitude.

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.

AAAI Conference 2022 Conference Paper

BERTMap: A BERT-Based Ontology Alignment System

• Yuan He
• Jiaoyan Chen
• Denvar Antonyrajah
• Ian Horrocks

Ontology alignment (a. k. a ontology matching (OM)) plays a critical role in knowledge integration. Owing to the success of machine learning in many domains, it has been applied in OM. However, the existing methods, which often adopt adhoc feature engineering or non-contextual word embeddings, have not yet outperformed rule-based systems especially in an unsupervised setting. In this paper, we propose a novel OM system named BERTMap which can support both unsupervised and semi-supervised settings. It first predicts mappings using a classifier based on fine-tuning the contextual embedding model BERT on text semantics corpora extracted from ontologies, and then refines the mappings through extension and repair by utilizing the ontology structure and logic. Our evaluation with three alignment tasks on biomedical ontologies demonstrates that BERTMap can often perform better than the leading OM systems LogMap and AML.

AIJ Journal 2022 Journal Article

Modular materialisation of Datalog programs

• Pan Hu
• Boris Motik
• Ian Horrocks

Answering queries over large datasets extended with Datalog rules plays a key role in numerous data management applications, and it has been implemented in several highly optimised Datalog systems in both academic and commercial contexts. Many systems implement reasoning via materialisation, which involves precomputing all consequences of the rules and the dataset in a preprocessing step. Some systems also use incremental reasoning algorithms, which can update the materialisation efficiently when the input dataset changes. Such techniques allow queries to be processed without any reference to the rules, so they are often used in applications where the performance of query answering is critical. Existing materialisation and incremental reasoning techniques enumerate all possible ways to apply rules to the data in order to derive all relevant consequences. This, however, can be inefficient because derivations of rules commonly used in practice are redundant; for example, rules axiomatising a binary predicate as symmetric and transitive can have a cubic number of applications, yet they can derive at most a quadratic number of facts. Such redundancy can be a significant source of overhead in practice and can prevent Datalog systems from successfully processing large datasets. To address this issue, in this paper we present a novel framework for modular materialisation and incremental reasoning. Our key idea is that, for certain combinations of rules commonly used in practice, all consequences can be derived using specialised procedures that do not necessarily enumerate all possible rule applications. Thus, our framework supports materialisation and incremental reasoning via a collection of modules. Each module is responsible for deriving consequences of a subset of the program, by using either standard rule application or proprietary algorithms. We prove that such an approach is complete as long as each module satisfies certain properties. Our formalisation of a module is very general, and in fact it allows modules to keep arbitrary auxiliary information. We also show how to realise custom procedures for four types of modules: transitivity, symmetry–transitivity, chain rules, and sequencing elements of a total order. Finally, we demonstrate empirically that using our custom procedures can speed up materialisation and incremental reasoning by several orders of magnitude on several well-known benchmarks. Thus, our technique has the potential to significantly improve the scalability of Datalog reasoners.

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.

NeurIPS Conference 2021 Conference Paper

INDIGO: GNN-Based Inductive Knowledge Graph Completion Using Pair-Wise Encoding

• Shuwen Liu
• Bernardo Grau
• Ian Horrocks
• Egor Kostylev

The aim of knowledge graph (KG) completion is to extend an incomplete KG with missing triples. Popular approaches based on graph embeddings typically work by first representing the KG in a vector space, and then applying a predefined scoring function to the resulting vectors to complete the KG. These approaches work well in transductive settings, where predicted triples involve only constants seen during training; however, they are not applicable in inductive settings, where the KG on which the model was trained is extended with new constants or merged with other KGs. The use of Graph Neural Networks (GNNs) has recently been proposed as a way to overcome these limitations; however, existing approaches do not fully exploit the capabilities of GNNs and still rely on heuristics and ad-hoc scoring functions. In this paper, we propose a novel approach, where the KG is fully encoded into a GNN in a transparent way, and where the predicted triples can be read out directly from the last layer of the GNN without the need for additional components or scoring functions. Our experiments show that our model outperforms state-of-the-art approaches on inductive KG completion benchmarks.

IJCAI Conference 2021 Conference Paper

Knowledge-aware Zero-Shot Learning: Survey and Perspective

• Jiaoyan Chen
• Yuxia Geng
• Zhuo Chen
• Ian Horrocks
• Jeff Z. Pan
• Huajun Chen

Zero-shot learning (ZSL) which aims at predicting classes that have never appeared during the training using external knowledge (a. k. a. side information) has been widely investigated. In this paper we present a literature review towards ZSL in the perspective of external knowledge, where we categorize the external knowledge, review their methods and compare different external knowledge. With the literature review, we further discuss and outlook the role of symbolic knowledge in addressing ZSL and other machine learning sample shortage issues.

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 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.

AAAI Conference 2019 Conference Paper

ColNet: Embedding the Semantics of Web Tables for Column Type Prediction

• Jiaoyan Chen
• Ernesto Jiménez-Ruiz
• Ian Horrocks
• Charles Sutton

Automatically annotating column types with knowledge base (KB) concepts is a critical task to gain a basic understanding of web tables. Current methods rely on either table metadata like column name or entity correspondences of cells in the KB, and may fail to deal with growing web tables with incomplete meta information. In this paper we propose a neural network based column type annotation framework named ColNet which is able to integrate KB reasoning and lookup with machine learning and can automatically train Convolutional Neural Networks for prediction. The prediction model not only considers the contextual semantics within a cell using word representation, but also embeds the semantics of a column by learning locality features from multiple cells. The method is evaluated with DBPedia and two different web table datasets, T2Dv2 from the general Web and Limaye from Wikipedia pages, and achieves higher performance than the state-of-the-art approaches.

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.

IJCAI Conference 2019 Conference Paper

Learning Semantic Annotations for Tabular Data

• Jiaoyan Chen
• Ernesto Jimenez-Ruiz
• Ian Horrocks
• Charles Sutton

The usefulness of tabular data such as web tables critically depends on understanding their semantics. This study focuses on column type prediction for tables without any meta data. Unlike traditional lexical matching-based methods, we propose a deep prediction model that can fully exploit a table’s contextual semantics, including table locality features learned by a Hybrid NeuralNetwork (HNN), and inter-column semantics features learned by a knowledge base (KB) lookup and query answering algorithm. It exhibits good performance not only on individual table sets, but also when transferring from one table set to another.

AIJ Journal 2019 Journal Article

Maintenance of datalog materialisations revisited

• Boris Motik
• Yavor Nenov
• Robert Piro
• Ian Horrocks

Datalog is a rule-based formalism that can axiomatise recursive properties such as reachability and transitive closure. Datalog implementations often materialise (i. e. , precompute and store) all facts entailed by a datalog program and a set of explicit facts. Queries can thus be answered directly in the materialised facts, which is beneficial to the performance of query answering, but the materialised facts must be updated whenever the explicit facts change. Rematerialising all facts ‘from scratch’ can be very inefficient, so numerous materialisation maintenance algorithms have been developed that aim to efficiently identify the facts that require updating and thus reduce the overall work. Most such approaches are variants of the counting or Delete/Rederive (DRed) algorithms. Algorithms in the former group maintain additional data structures and are usually applicable only if datalog rules are not recursive, which limits their applicability in practice. Algorithms in the latter group do not require additional data structures and can handle recursive rules, but they can be inefficient when facts have multiple derivations. Finally, to the best of our knowledge, these approaches have not been compared and their practical applicability has not been investigated. Datalog is becoming increasingly important in practice, so a more comprehensive understanding of the tradeoffs between different approaches to materialisation maintenance is needed. In this paper we present three such algorithms for datalog with stratified negation: a new counting algorithm that can handle recursive rules, an optimised variant of the DRed algorithm that does not repeat derivations, and a new Forward/Backward/Forward (FBF) algorithm that extends DRed to better handle facts with multiple derivations. Furthermore, we study the worst-case performance of these algorithms and compare the algorithms' behaviour on several examples. Finally, we present the results of an extensive, first-of-a-kind empirical evaluation in which we investigate the robustness and the scaling behaviour of our algorithms. We thus provide important theoretical and practical insights into all three algorithms that will provide invaluable guidance to future implementors of datalog systems.

AAAI Conference 2019 Conference Paper

Modular Materialisation of Datalog Programs

• Pan Hu
• Boris Motik
• Ian Horrocks

The seminaı̈ve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algorithms. To integrate such algorithms into a general reasoning approach that can handle arbitrary rules, we propose a modular framework for computing and maintaining a materialisation. We split a datalog program into modules that can be handled using specialised algorithms, and we handle the remaining rules using the seminaı̈ve algorithm. We also present two algorithms for computing the transitive and the symmetric– transitive closure of a relation that can be used within our framework. Finally, we show empirically that our framework can handle arbitrary datalog programs while outperforming existing approaches, often by orders of magnitude.

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.

AAAI Conference 2018 Conference Paper

Optimised Maintenance of Datalog Materialisations

• Pan Hu
• Boris Motik
• Ian Horrocks

To efficiently answer queries, datalog systems often materialise all consequences of a datalog program, so the materialisation must be updated whenever the input facts change. Several solutions to the materialisation update problem have been proposed. The Delete/Rederive (DRed) and the Backward/Forward (B/F) algorithms solve this problem for general datalog, but both contain steps that evaluate rules ‘backwards’ by matching their heads to a fact and evaluating the partially instantiated rule bodies as queries. We show that this can be a considerable source of overhead even on very small updates. In contrast, the Counting algorithm does not evaluate the rules ‘backwards’, but it can handle only nonrecursive rules. We present two hybrid approaches that combine DRed and B/F with Counting so as to reduce or even eliminate ‘backward’ rule evaluation while still handling arbitrary datalog programs. We show empirically that our hybrid algorithms are usually significantly faster than existing approaches, sometimes by orders of magnitude.

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.

KR Conference 2018 Conference Paper

Transfer Learning Explanation with Ontologies

• Jiaoyan Chen
• Freddy Lecue
• Jeff Z Pan
• Ian Horrocks
• Huajun Chen

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.

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.

AAAI Conference 2017 Conference Paper

Trust-Sensitive Evolution of DL-Lite Knowledge Bases

• Dmitriy Zheleznyakov
• Evgeny Kharlamov
• Ian Horrocks

Evolution of Knowledge Bases (KBs) consists of incorporating new information in an existing KB. Previous studies assume that the new information should be fully trusted and thus completely incorporated in the old knowledge. We suggest a setting where the new knowledge can be partially trusted and develop model-based approaches (MBAs) to KB evolution that rely on this assumption. Under MBAs the result of evolution is a set of interpretations and thus two core problems for MBAs are closure, i. e. , whether evolution result can be axiomatised with a KB, and approximation, i. e. , whether it can be (maximally) approximated with a KB. We show that DL-Lite is not closed under a wide range of trust-sensitive MBAs. We introduce a notion of s-approximation that improves the previously proposed approximations and show how to compute it for various trust-sensitive MBAs.

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.

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

Combining Rewriting and Incremental Materialisation Maintenance for Datalog Programs with Equality

• Boris Motik
• Yavor Nenov
• Robert Piro
• Ian Horrocks

Materialisation precomputes all consequences of a set of facts and a datalog program so that queries can be evaluated directly (i. e. , independently from the program). Rewriting optimises materialisation for datalog programs with equality by replacing all equal constants with a single representative; and incremental maintenance algorithms can efficiently update a materialisation for small changes in the input facts. Both techniques are critical to practical applicability of datalog systems; however, we are unaware of an approach that combines rewriting and incremental maintenance. In this paper we present the first such combination, and we show empirically that it can speed up updates by several orders of magnitude compared to using either rewriting or incremental maintenance in isolation.

AAAI Conference 2015 Conference Paper

Handling Owl:sameAs via Rewriting

• Boris Motik
• Yavor Nenov
• Robert Piro
• Ian Horrocks

Rewriting is widely used to optimise owl: sameAs reasoning in materialisation based OWL 2 RL systems. We investigate issues related to both the correctness and efficiency of rewriting, and present an algorithm that guarantees correctness, improves efficiency, and can be effectively parallelised. Our evaluation shows that our approach can reduce reasoning times on practical data sets by orders of magnitude.

AAAI Conference 2015 Conference Paper

Incremental Update of Datalog Materialisation: the Backward/Forward Algorithm

• Boris Motik
• Yavor Nenov
• Robert Piro
• Ian Horrocks

Datalog-based systems often materialise all consequences of a datalog program and the data, allowing users’ queries to be evaluated directly in the materialisation. This process, however, can be computationally intensive, so most systems update the materialisation incrementally when input data changes. We argue that existing solutions, such as the wellknown Delete/Rederive (DRed) algorithm, can be inefficient in cases when facts have many alternate derivations. As a possible remedy, we propose a novel Backward/Forward (B/F) algorithm that tries to reduce the amount of work by a combination of backward and forward chaining. In our evaluation, the B/F algorithm was several orders of magnitude more efficient than the DRed algorithm on some inputs, and it was never significantly less efficient.

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.

AIJ Journal 2014 Journal Article

Consequence-based and fixed-parameter tractable reasoning in description logics

• František Simančík
• Boris Motik
• Ian Horrocks

In this paper we investigate the consequence-based algorithms that are nowadays commonly used for subsumption reasoning with description logic ontologies, presenting the following novel results. First, we present a very general consequence-based reasoning algorithm that can be instantiated so as to capture the essential features of the known algorithms. Second, we use this algorithm to develop a novel framework for a quantitative and parametric analysis of the complexity of subsumption reasoning in description logic ontologies. Our approach is based on the notion of a decomposition—a graph-like structure that, roughly speaking, summarizes the models relevant during ontology reasoning. We identify width and length as decomposition parameters that determine the “level” of combinatorial reasoning. We prove that, when parameterized by a decomposition, our consequence-based algorithm runs in time that is fixed-parameter tractable in width and length. Third, we briefly discuss how length and width characterize the behavior of tableau algorithms. Fourth, we show that the width and length of existing ontologies are reasonably small, which, we believe, explains the good performance of consequence-based algorithms in practice. We thus obtain a sound foundation for a practical implementation of ontology reasoners, as well as a way to analyze the reasoners' performance.

IS Journal 2014 Journal Article

Description Logics

• Markus Krötzsch
• Frantisek Simancik
• Ian Horrocks

This article provides a self-contained first introduction to description logics (DLs). The main concepts and features are explained with examples before the syntax and semantics of the DL SROIQ are defined in detail. Additional sections review lightweight DL languages, discuss the relationship to the Web Ontology Language (OWL), and give pointers to further reading.

AAAI Conference 2014 Conference Paper

Parallel Materialisation of Datalog Programs in Centralised, Main-Memory RDF Systems

• Boris Motik
• Yavor Nenov
• Robert Piro
• Ian Horrocks
• Dan Olteanu

We present a novel approach to parallel materialisation (i. e. , fixpoint computation) of datalog programs in centralised, main-memory, multi-core RDF systems. Our approach comprises an algorithm that evenly distributes the workload to cores, and an RDF indexing data structure that supports efficient, ‘mostly’ lock-free parallel updates. Our empirical evaluation shows that our approach parallelises computation very well: with 16 physical cores, materialisation can be up to 13. 9 times faster than with just one core.

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.

IJCAI Conference 2013 Conference Paper

Computing Stable Models for Nonmonotonic Existential Rules

• Despoina Magka
• Markus Krötzsch
• Ian Horrocks

In this work, we consider function-free existential rules extended with nonmonotonic negation under a stable model semantics. We present new acyclicity and stratification conditions that identify a large class of rule sets having finite, unique stable models, and we show how the addition of constraints on the input facts can further extend this class. Checking these conditions is computationally feasible, and we provide tight complexity bounds. Finally, we demonstrate how these new methods allowed us to solve relevant reasoning problems over a realworld knowledge base from biochemistry using an off-the-shelf answer set programming engine.

AAAI Conference 2013 Conference Paper

Introducing Nominals to the Combined Query Answering Approaches for EL

• Giorgio Stefanoni
• Boris Motik
• Ian Horrocks

So-called combined approaches answer a conjunctive query over a description logic ontology in three steps: first, they materialise certain consequences of the ontology and the data; second, they evaluate the query over the data; and third, they filter the result of the second phase to eliminate unsound answers. Such approaches were developed for various members of the DL-Lite and the EL families of languages, but none of them can handle ontologies containing nominals. In our work, we bridge this gap and present a combined query answering approach for ELHOr ⊥ —a logic that contains all features of the OWL 2 EL standard apart from transitive roles and complex role inclusions. This extension is nontrivial because nominals require equality reasoning, which introduces complexity into the first and the third step. Our empirical evaluation suggests that our technique is suitable for practical application, and so it provides a practical basis for conjunctive query answering in a large fragment of OWL 2 EL.

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.

IJCAI Conference 2011 Conference Paper

Consequence-Based Reasoning beyond Horn Ontologies

• Frantisek Simancik
• Yevgeny Kazakov
• Ian Horrocks

Consequence-based ontology reasoning procedures have so far been known only for Horn ontology languages. A difficulty in extending such procedures is that non-Horn axioms seem to require reasoning by case, which causes non-determinism in tableau-based procedures. In this paper we present a consequence-based procedure for ALCH that overcomes this difficulty by using rules similar to ordered resolution to deal with disjunctive axioms in a deterministic way; it retains all the favourable attributes of existing consequence-based procedures, such as goal-directed "one pass" classification, optimal worst-case complexity, and "pay-asyou- go" behaviour. Our preliminary empirical evaluation suggests that the procedure scales well to non-Horn ontologies.

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.

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.

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.

KR Conference 2008 Conference Paper

Unions of Conjunctive Queries in SHOQ

• Birte Glimm
• Ian Horrocks
• Ulrike Sattler

Conjunctive queries play an important role as an expressive query language in Description Logics (DLs). Decision procedures for expressive Description Logics are, however, only recently emerging and it is still an open question whether answering conjunctive queries is decidable for the DL SHOIQ that underlies the OWL DL standard. In fact, no decision procedure was known for expressive DLs that contain nominals. In this paper, we close this gap by providing a decision procedure for entailment of unions of conjunctive queries in SHOQ. Our algorithm runs in deterministic time single exponential in the size of the knowledge base and double exponential in the size of the query, which is the same as for SHIQ. Our procedure also shows that SHOQ knowledge base consistency is indeed ExpTime-complete, which was, to the best of our knowledge, always conjectured but never proved.

IJCAI Conference 2007 Conference Paper

• Birte Glimm
• Ian Horrocks
• Carsten Lutz
• Ulrike Sattler

Conjunctive queries play an important role as an expressive query language for Description Logics (DLs). Although modern DLs usually provide for transitive roles, it was an open problem whether conjunctive query answering over DL knowledge bases is decidable if transitive roles are admitted in the query. In this paper, we consider conjunctive queries over knowledge bases formulated in the popular DL SHIQ and allow transitive roles in both the query and the knowledge base. We show that query answering is decidable and establish the following complexity bounds: regarding combined complexity, we devise a deterministic algorithm for query answering that needs time single exponential in the size of the KB and double exponential in the size of the query. Regarding data complexity, we prove co-NP-completeness.

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

The Even More Irresistible SROIQ

• Oliver Kutz
• Ian Horrocks
• Ulrike Sattler

We describe an extension of the description logic underlying OWL-DL, SHOIN, with a number of expressive means that we believe will make it more useful in practise. Roughly speaking, we extend SHOIN with all expressive means that were suggested to us by ontology developers as useful additions to OWL-DL, and which, additionally, do not affect its decidability and practicability. We consider complex role inclusion axioms to express propagation of one property along another one, which have proven useful in medical terminologies. Furthermore, we extend SHOIN with reflexive, antisymmetric, and irreflexive roles, disjoint roles, a universal role, and constructs exists R. Self, allowing, for instance, the definition of concepts such as a "narcist". Finally, we consider negated role assertions in Aboxes and qualified number restrictions. The resulting logic is called SROIQ. We present a rather elegant tableau-based reasoning algorithm: it combines the use of automata to keep track of universal value restrictions with the techniques developed for SHOIQ. The logic SROIQ has been adopted as the logical basis for the next iteration of OWL, OWL 1. 1.

IJCAI Conference 2005 Conference Paper

A Tableaux Decision Procedure for SHOIQ

• Ian Horrocks
• Ulrike

This paper presents a tableaux decision procedure for SHOIQ, the DL underlying OWL DL. To the best of our knowledge, this is the first goal-directed decision procedure for SHOIQ.

AIJ Journal 2004 Journal Article

Decidability of SHIQ with complex role inclusion axioms

• Ian Horrocks
• Ulrike Sattler

Motivated by medical terminology applications, we investigate the decidability of an expressive and prominent description logic (DL), SHIQ, extended with role inclusion axioms of the form R ○ S ⊑ ˙ T. It is well known that a naive such extension leads to undecidability, and thus we restrict our attention to axioms of the form R ○ S ⊑ ˙ R or S ○ R ⊑ ˙ R, which is the most important form of axioms in the applications that motivated this extension. Surprisingly, this extension is still undecidable. However, it turns out that by restricting our attention further to acyclic sets of such axioms, we regain decidability. We present a tableau-based decision procedure for this DL and report on its implementation, which promises to behave well in practice and provides important additional functionality in a medical terminology application.

IJCAI Conference 2003 Conference Paper

Decidability of SHIQ with Complex Role Inclusion Axioms

• Ian Horrocks
• Ulrike Sattler

IJCAI Conference 2003 Conference Paper

Keys, Nominals, and Concrete Domains

• Carsten Lutz
• Carlos Areces
• Ian Horrocks
• Ulrike Sattler

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to "concrete" domains such as numbers and strings. We propose to extend such DLs with key constraints that allow the expression of statements like "US citizens are uniquely identified by their social security number". Based on this idea, we introduce a number of natural description logics and present (un)decidability results and tight NEx- PTlME complexity bounds.

KR Conference 2002 Conference Paper

Evaluating a modular Abox algorithm

• Sergio Tessaris
• Ian Horrocks
• Graham Gough

AAAI Conference 2002 Conference Paper

Reviewing the Design of DAML+OIL: An Ontology Language for the Semantic Web

• Ian Horrocks
• Bell Labs Research; Frank van Harmelen

In the current “Syntactic Web”, uninterpreted syntactic constructs are given meaning only by private off-line agreements that are inaccessible to computers. In the Semantic Web vision, this is replaced by a web where both data and its semantic definition are accessible and manipulable by computer software. DAML+OIL is an ontology language specifically designed for this use in the Web; it exploits existing Web standards (XML and RDF), adding the familiar ontological primitives of object oriented and frame based systems, and the formal rigor of a very expressive description logic. The definition of DAML+OIL is now over a year old, and the language has been in fairly widespread use. In this paper, we review DAML+OIL’s relation with its key ingredients (XML, RDF, OIL, DAML-ONT, Description Logics), we discuss the design decisions and trade-offs that were the basis for the language definition, and identify a number of implementation challenges posed by the current language. These issues are important for designers of other representation languages for the Semantic Web, be they competitors or successors of DAML+OIL, such as the language currently under definition by W3C.