Finite model reasoning over existential rules

DOI10.1017/S1471068417000369MaRDI QIDQ4592706zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

query answeringfinite controllabilityDatalogexistential rulesfinite model reasoning

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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)