Dyadic existential rules

Conference item

In the field of ontology-based query answering, existential rules (a.k.a. tuple-generating dependencies) form an expressive Datalog-based language to specify implicit knowledge. The presence of existential quantification in rule-heads, however, makes the main reasoning tasks undecidable. To overcome this limitation, in the last two decades, a number of classes of existential rules guaranteeing the decidability of query answering have been proposed. Unfortunately, such classes are typically based on different syntactic conditions imposing the development of different ad hoc reasoners. This paper introduces a novel general condition that allows to define, systematically, from any decidable class C of existential rules, a new class called Dyadic-C that enjoys the following properties: (i) it is decidable; (ii) it generalizes C; (iii) it keeps the same data complexity as C; and (iv) it can exploit any reasoner for query answering over C. Additionally, the paper proposes a simple and elegant syntactic condition that gives rise to the class Ward+ generalizing the well-known decidable classes Shy and Ward, and being included in Dyadic-Shy.

Authors: Gottlob, G; Manna, M; Marte, C

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: CEUR Workshop Proceedings
• Host title: Proceedings of the 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)
• Volume: 3203
• Pages: 83-96
• Publication date: 2022-08-31
• Event title: 4th International Workshop on the Resurgence of Datalog in Academia and Industry (Datalog-2.0 2022)
• Event location: Genova, Italy
• Event website: https://sites.google.com/view/lpnmr2022/home
• Event start date: 2022-09-05
• Event end date: 2022-09-08
• ISSN: 1613-0073
• Language: English
• Keywords: FFR