Knowledge representation and reasoning (KR) is the field of artificial intelligence that studies formalisms, mostly based on logics, to represent and do reasoning with various kinds of human knowledge. Modern information systems often comprise a knowledge base expressed in a KR language. At the core of a knowledge base, there is a so-called ontology, which defines the conceptual vocabulary of the knowledge base and describes general knowledge about a domain of interest. Formally, an ontology is a logical theory in a fragment of first-order logic, which may be more or less expressive. The simplest ontologies define hierarchies of concepts and relations, while richer ontologies are often expressed in description logics, a prominent family of KR languages devoted to representing and reasoning with ontologies, or rule-based languages. Another classical component of a knowledge base is the fact base, which contains assertions about specific individuals.

In the last decade, the increasing amounts of available data, which may be large, complex, heterogeneous and/or incomplete, have deeply impacted the field. How to better access data by incorporating knowledge, typically expressed in ontologies, has become a crucial issue, at the crossroad of KR and data management. On the KR side, the challenge was to tackle a new reasoning task, namely querying data (whereas classical KR problems such as consistency checking or classification can be recast as very specific query answering problems), which required to find new languages and algorithmic techniques offering various tradeoffs between expressivity and tractability of reasoning. On the data management side, the challenge was rather to extend query answering techniques to take into account knowledge. The issue of querying data while taking into account inferences enabled by an ontology has received several names, it will be called ontology-mediated query answering in this talk. It can also be seen as querying a knowledge base, composed of an ontology and a (possibly virtual) fact base linked to data sources.

The aim of this tutorial is to give an overview of ongoing research in KR on ontology-mediated query answering. The main KR formalisms investigated in this context will be presented, and compared with respect to expressivity, decidability and computational complexity, with a special focus on a recent family of formalisms, namely existential rules.

The tutorial will be divided in three parts:

• I will first present the context and the main notions related to ontology-mediated query answering: the logical view of queries and data; ontologies in computer science; knowledge bases; relevant knowledge representation and reasoning formalisms; fundamental problems on knowledge bases.
• Then I will present in more detail the main formalisms studied in the context of ontology-mediated query answering: Horn description logics and existential rules. Description logics are decidable fragments of first-order logic, and their Horn subset is roughly obtained by disallowing any form of disjunction. Existential rules are also known as the Datalog± family, or tuple-generating dependencies in database theory, and they generalize both Horn description logics and Datalog, the querying language for deductive databases. The basic algorithmic approaches to ontology-mediated query answering will be reviewed.
• The last part will be devoted to decidability issues in the existential rule framework. Logical entailment with general existential rules is not decidable, however many subclasses for which it is decidable have been defined. I will present the landscape of decidable classes of rules and explain the ideas behind decidability properties.

Bibliography

Jean-François Baget, Michel Leclère and Marie-Laure Mugnier, and Eric Salvat, (2011). On rules with existential variables: Walking the decidability line. Artificial Intelligence, 175(9-10):1620-1654.

Meghyn Bienvenu and Magdalena Ortiz: Ontology-Mediated Query Answering with Data-Tractable Description Logics. Reasoning Web 2015. Web Logic Rules - 11th International Summer School 2015, Lecture Notes in Computer Science 9203, Springer: 218-307

Andrea Calì, Georg Gottlob and Thomas Lukasiewicz: A general Datalog-based framework for tractable query answering over ontologies. Journal of Web Semantics. 14: 57-83 (2012)

Diego Calvanese, Giuseppe De Giacomo, Domenico Lembo, Maurizio Lenzerini and Riccardo Rosati: Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family. Journal of Automated Reasoning. 39(3): 385-429 (2007)

Marie-Laure Mugnier and Michael Thomazo: An Introduction to Ontology-Based Query Answering with Existential Rules. Reasoning Web 2014. Reasoning on the Web in the Big Data Era - 10th International Summer School 2014, Lecture Notes in Computer Science 8714, Springer: 245-278

Back to the 6th Universal Logic School!