Termination Analysis of Rule-based Ontological Reasoning
Abstract. Data-intensive applications heavily exploit the available knowledge about the domain of the data provided in the form of ontologies, in particular, of rule-based ontologies consisting of logical rules of the form "if some facts are true, then some other facts are also true". This knowledge allows for inferring new implicit information via reasoning that is not explicit in the data, which is then used according to the needs of the underlying application, e.g., providing more complete answers to user queries. A key challenge though when reasoning with rule-based ontologies is non-termination. Indeed, the majority of the practically important rule-based ontology languages identified over the years by the knowledge representation and reasoning research community, although they strike a good balance between expressiveness and computational complexity of the relevant reasoning services, do not guarantee the termination of reasoning. This is because of the following two factors: the recursive nature of ontological rules (i.e., the definition of a predicate may depend on itself), and the ability of ontological rules to infer new unknown objects that are not mentioned in the data. This leads to the key problem of uniform termination of reasoning: given a rule-based ontology, is it the case that reasoning terminates for every input database? The goal of this talk is to illustrate the technical challenges underlying the above problem, how those challenges are affected by the mode (naive vs. smart) of reasoning, how they can be overcome, and what are the interesting open problems. To this end, we are going to focus on the guarded family of existential rules.
Short Bio: Andreas Pieris is an Associate Professor at the University of Edinburgh since 2020 and an Assistant Professor at the University of Cyprus since 2021. Prior to this, he was an Assistant Professor at the University of Edinburgh from 2016 until 2020. His research interests are database theory with emphasis on uncertain data, knowledge representation and reasoning, and logic in computer science. He has published numerous papers in leading international conferences and journals. He has also served on the program committees of several conferences, including the top-tier database theory and artificial intelligence conferences.