On rules with existential variables: walking the decidability line

DOI10.1016/j.artint.2011.03.002zbMath1225.68247OpenAlexW2040566369MaRDI QIDQ646515

Marie-Laure Mugnier, Michel Leclère, Eric Salvat, Jean-François Baget

Publication date: 17 November 2011

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2011.03.002

zbMATH Keywords

rulesdecidabilitybackward chainingforward chainingchaserule dependencyTGD

Mathematics Subject Classification ID

Logic in artificial intelligence (68T27)

Related Items (39)

Provenance Circuits for Trees and Treelike Instances ⋮ An argumentative approach for handling inconsistency in prioritized Datalog ± ontologies ⋮ Knowledge base exchange: the case of OWL 2 QL ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ Bringing existential variables in answer set programming and bringing non-monotony in existential rules: two sides of the same coin ⋮ Towards more expressive ontology languages: the query answering problem ⋮ Preserving Constraints with the Stable Chase ⋮ Querying the Unary Negation Fragment with Regular Path Expressions. ⋮ Logic-based argumentation with existential rules ⋮ Finite model reasoning over existential rules ⋮ Answer Counting under Guarded TGDs ⋮ The pragmatic proof: Hypermedia API composition and execution ⋮ On the k-Boundedness for Existential Rules ⋮ A First Order Logic Benchmark for Defeasible Reasoning Tool Profiling ⋮ On Horn Conjunctive Queries ⋮ Polynomial combined first-order rewritings for linear and guarded existential rules ⋮ Deciding FO-rewritability of Regular Languages and Ontology-Mediated Queries in Linear Temporal Logic ⋮ Uniform Restricted Chase Termination ⋮ On combining ontologies and rules ⋮ Recent Advances in Datalog$$^\pm $$ ⋮ Reasoning on anonymity in Datalog ⋮ The price of query rewriting in ontology-based data access ⋮ Combining decidability paradigms for existential rules ⋮ First-order rewritability of ontology-mediated queries in linear temporal logic ⋮ Datalog and Its Extensions for Semantic Web Databases ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Semi-oblivious chase termination: the sticky case ⋮ Restricted Chase Termination for Existential Rules: A Hierarchical Approach and Experimentation ⋮ Characterizing Boundedness in Chase Variants ⋮ A Single Approach to Decide Chase Termination on Linear Existential Rules ⋮ Datalog: Bag Semantics via Set Semantics ⋮ Inconsistency-Tolerant Query Answering: Rationality Properties and Computational Complexity Analysis ⋮ The Impact of Active Domain Predicates on Guarded Existential Rules ⋮ Guarded Ontology-Mediated Queries ⋮ First-Order Rewritability and Complexity of Two-Dimensional Temporal Ontology-Mediated Queries ⋮ $$\exists $$ -ASP for Computing Repairs with Existential Ontologies ⋮ Query Rewriting under Linear $$\mathcal {EL}$$ Knowledge Bases

Uses Software

• Datalog

Cites Work

• Data exchange: semantics and query answering
• Graph-based knowledge representation. Computational foundations of conceptual graphs
• Testing containment of conjunctive queries under functional and inclusion dependencies
• The implication and finite implication problems for typed template dependencies
• A top-down proof procedure for generalized data dependencies
• Tractable reasoning and efficient query answering in description logics: The DL-Lite family
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable
• A Proof Procedure for Data Dependencies
• Rules Dependencies in Backward Chaining of Conceptual Graphs Rules
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On rules with existential variables: walking the decidability line