Capturing Homomorphism-Closed Decidable Queries with Existential Rules

Talk by Markus Krötzsch

Location: Online
Start: 2. December 2021 at 11:00 am
End: 2. December 2021 at 12:00 pm
Event series: Research Seminar Logic and AI
iCal

Existential rules are a very popular ontology-mediated query language for which the chase represents a generic computational approach for query answering. It is straightforward that existential rule queries exhibiting chase termination are decidable and can only recognize properties that are preserved under homomorphisms. In this paper, we show the converse: every decidable query that is closed under homomorphism can be expressed by an existential rule set for which the standard chase universally terminates. Membership in this fragment is not decidable, but we show via a diagonalization argument that this is unavoidable.

This work has been presented in a relatively short presentation at KR 2021. This extended talk will have room for more in-depth explanations and discussions.

The talk is via BigBlueButton, link:

https://bbb.tu-dresden.de/b/ali-zgz-l8d-52n