Ontological Conjunctive Query Answering via Existential Rules

Logic & Computation

The need for ontological query answering has been widely acknowledged, both in the knowledge representation and reasoning community and in the database community. Indeed, ontologies may be used to infer data that is not explicitly stored, which allows to overcome incompleteness of the data. Moreover, it allows to abstract from the specific way the data is stored, allowing the user to perform queries on a more conceptual level. A typical application may be sketched as follows. A hospital stores data relative to its patients in a database, according to a given schema. On top of this database, an ontology specifies the meaning of the terms that are used in the database. For instance, it may state that a given drug is used to cure diabetes. In other terms, it explicits the relationships that hold between different terms used in the schema. The conjunction of the database and the ontology is called a knowledge base. The ontological query answering problem consists in querying such a knowledge base, usually by means of a conjunctive query. Such a semantically-enhanced interrogation is especially useful when one is confronted with incomplete data, which is very likely to occur in context when data is coming from heterogeneous sources. In the hospital case, a query searching for people having diabetes would not only retrieve people for which this diagnosis is explicitly stated in the database, but also those who are treated with a drug known to be used in order to treat diabetes. The recent years have seen an intense research effort aiming at answering conjunctive queries in the presence of ontologies. In particular, the Datalog +/- framework, whose basic elements are also called existential rules, has raised a lot of interest. An ontology is specified by a set of rules, that are syntactically similar to Datalog rules, the classical recursive query language for databases, with the notable exception of allowing the presence of existentially quantified variables in rule heads. This feature, known as value invention, has been recognized as crucial for modeling purposes. An example of such rule referring to our previous example would be as follows: $\forall x (\fun{treatedBy}(x,DrugA) \rightarrow \exists y~ \fun{affects}(y,x) \wedge \fun{diabetes}(y))$, where DrugA is the name of a specific drug. However, this extended expressivity comes to a high price: conjunctive query answering under a set of existential rules is an undecidable problem. In this course, we propose to present the classical approaches for performing conjunctive query answering under existential rules, together with known cases where these approaches are known to terminate. In particular, much attention will be given to rewriting techniques, both from a practical and a theoretical point of view.

First week
17:00 - 18:30 - slot 4