Finite model reasoning over existential rules

DOI10.1017/S1471068417000369zbMATH Open1422.68060arXiv1707.01870OpenAlexW2963287580MaRDI QIDQ4592706FDOQ4592706

Authors: Giovanni Amendola, N. Leone, M. Manna 

Publication date: 8 November 2017

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Abstract: Ontology-based query answering (OBQA) asks whether a Boolean conjunctive query is satisfied by all models of a logical theory consisting of a relational database paired with an ontology. The introduction of existential rules (i.e., Datalog rules extended with existential quantifiers in rule-heads) as a means to specify the ontology gave birth to Datalog+/-, a framework that has received increasing attention in the last decade, with focus also on decidability and finite controllability to support effective reasoning. Five basic decidable fragments have been singled out: linear, weakly-acyclic, guarded, sticky, and shy. Moreover, for all these fragments, except shy, the important property of finite controllability has been proved, ensuring that a query is satisfied by all models of the theory iff it is satisfied by all its finite models. In this paper we complete the picture by demonstrating that finite controllability of OBQA holds also for shy ontologies, and it therefore applies to all basic decidable Datalog+/- classes. To make the demonstration, we devise a general technique to facilitate the process of (dis)proving finite controllability of an arbitrary ontological fragment. This paper is under consideration for acceptance in TPLP.

Full work available at URL: https://arxiv.org/abs/1707.01870

Recommendations

• Fast query answering over existential rules
• Towards more expressive ontology languages: the query answering problem
• On the complexity of ontological reasoning under disjunctive existential rules
• Converging to the chase -- a tool for finite controllability
• Extending acyclicity notions for existential rules

zbMATH Keywords

query answeringfinite controllabilityDatalogexistential rulesfinite model reasoning

Mathematics Subject Classification ID

Knowledge representation (68T30) Database theory (68P15) Logic in computer science (03B70)

Cites Work

• Testing containment of conjunctive queries under functional and inclusion dependencies
• Taming the infinite chase: query answering under expressive relational constraints
• Title not available (Why is that?)
• Querying the Guarded Fragment
• Data exchange: semantics and query answering
• Ontology-based data access: a study through disjunctive Datalog, CSP, and MMSNP
• Combining decidability paradigms for existential rules
• On rules with existential variables: walking the decidability line
• Converging to the chase -- a tool for finite controllability
• Converging to the chase -- a tool for finite controllability
• Towards more expressive ontology languages: the query answering problem
• Title not available (Why is that?)
• The price of query rewriting in ontology-based data access
• Query Rewriting and Optimization for Ontological Databases
• Guarded-based disjunctive tuple-generating dependencies
• Querying the guarded fragment with transitivity

Cited In (4)

• Combining decidability paradigms for existential rules
• Fast query answering over existential rules
• On the complexity of ontological reasoning under disjunctive existential rules
• Finite open-world query answering with number restrictions

This page was built for publication: Finite model reasoning over existential rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592706)