Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination

Research output: Contribution to book/conference proceedings/anthology/reportConference contributionContributedpeer-review

Abstract

The disjunctive restricted chase is a sound and complete procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. Alas, this procedure does not always terminate and checking if it does is undecidable. However, we can use acyclicity notions (sufficient conditions that imply termination) to effectively apply the chase in many real-world cases. To know if these conditions are as general as possible, we can use cyclicity notions (sufficient conditions that imply non-termination). In this paper, we discuss some issues with previously existing cyclicity notions, propose some novel notions for non-termination by dismantling the original idea, and empirically verify the generality of the new criteria.

Details

Original languageEnglish
Title of host publicationProceedings of the 20th International Conference on Principles of Knowledge Representation and Reasoning (KR 2023)
Pages301–310
Number of pages10
Publication statusPublished - 1 Sept 2023
Peer-reviewedYes

Publication series

SeriesProceedings of the International Conference on Principles of Knowledge Representation and Reasoning
Volume20

External IDs

Mendeley a4cb31a1-23c1-3337-a8b8-28c9800036b8
unpaywall 10.24963/kr.2023/30