Characterizing boundedness in chase variants
From MaRDI portal
Abstract: Existential rules are a positive fragment of first-order logic that generalizes function-free Horn rules by allowing existentially quantified variables in rule heads. This family of languages has recently attracted significant interest in the context of ontology-mediated query answering. Forward chaining, also known as the chase, is a fundamental tool for computing universal models of knowledge bases, which consist of existential rules and facts. Several chase variants have been defined, which differ on the way they handle redundancies. A set of existential rules is bounded if it ensures the existence of a bound on the depth of the chase, independently from any set of facts. Deciding if a set of rules is bounded is an undecidable problem for all chase variants. Nevertheless, when computing universal models, knowing that a set of rules is bounded for some chase variant does not help much in practice if the bound remains unknown or even very large. Hence, we investigate the decidability of the k-boundedness problem, which asks whether the depth of the chase for a given set of rules is bounded by an integer k. We identify a general property which, when satisfied by a chase variant, leads to the decidability of k-boundedness. We then show that the main chase variants satisfy this property, namely the oblivious, semi-oblivious (aka Skolem), and restricted chase, as well as their breadth-first versions. This paper is under consideration for publication in Theory and Practice of Logic Programming.
Recommendations
- On the k-Boundedness for Existential Rules
- Restricted chase termination for existential rules: a hierarchical approach and experimentation
- Restricted Chase Termination: A Hierarchical Approach and Experimentation
- Extending acyclicity notions for existential rules
- Acyclicity notions for existential rules and their application to query answering in ontologies
Cites work
- A Proof Procedure for Data Dependencies
- About Boundedness for some Datalog and Datalogneg Programs
- Achilles, Turtle, and Undecidable Boundedness Problems for Small DATALOG Programs
- Acyclicity notions for existential rules and their application to query answering in ontologies
- All-instances termination of chase is undecidable
- Anatomy of the Chase
- Boundedness is undecidable for datalog programs with a single recursive rule
- Data exchange: semantics and query answering
- Datalog and Its Extensions for Semantic Web Databases
- Extending acyclicity notions for existential rules
- scientific article; zbMATH DE number 3723857 (Why is no real title available?)
- scientific article; zbMATH DE number 839556 (Why is no real title available?)
- On rules with existential variables: walking the decidability line
- On the k-Boundedness for Existential Rules
- Taming the infinite chase: query answering under expressive relational constraints
- Tractable reasoning and efficient query answering in description logics: The DL-Lite family
- Undecidable boundedness problems for datalog programs
- Undecidable optimization problems for database logic programs
Cited in
(9)- Acyclicity notions for existential rules and their application to query answering in ontologies
- Taming the infinite chase: query answering under expressive relational constraints
- Restricted chase termination for existential rules: a hierarchical approach and experimentation
- A Single Approach to Decide Chase Termination on Linear Existential Rules
- Extending acyclicity notions for existential rules
- On the k-Boundedness for Existential Rules
- Restricted Chase Termination: A Hierarchical Approach and Experimentation
- Derivation-Graph-Based Characterizations of Decidable Existential Rule Sets
- On rules with existential variables: walking the decidability line
This page was built for publication: Characterizing boundedness in chase variants
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4957209)
