Abstract
Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i.e., a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i.e., query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.
Keywords
- Knowledge Representation and Reasoning: Computational Complexity of Reasoning
- Knowledge Representation and Reasoning: Knowledge Representation Languages
- Knowledge Representation and Reasoning: Logics for Knowledge Representation
- Multidisciplinary Topics and Applications: Databases
