Capturing Homomorphism-Closed Decidable Queries with Existential Rules

Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/GutachtenBeitrag in KonferenzbandBeigetragenBegutachtung

Beitragende

Abstract

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 diagonalisation argument that this is unavoidable.

Details

OriginalspracheEnglisch
TitelProceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning
Redakteure/-innenMeghyn Bienvenu, Gerhard Lakemeyer, Esra Erdem
Seiten141-150
Seitenumfang10
PublikationsstatusVeröffentlicht - 2021
Peer-Review-StatusJa

Konferenz

Titel18th International Conference on Principles of Knowledge Representation and Reasoning
KurztitelKR 2021
Veranstaltungsnummer18
Dauer3 - 12 November 2021
Webseite
BekanntheitsgradInternationale Veranstaltung
Ortonline
StadtHanoi
LandVietnam

Externe IDs

Scopus 85126244863

Schlagworte

ASJC Scopus Sachgebiete