Ontology-based query answering asks whether a Boolean query is satisfied by all models of a logical theory consisting of an extensional 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. 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 showing that finite controllability holds also for shy ontologies. The demonstration is based on a number of technical tools which could be used for similar purposes and are valuable per se.
Querying finite or arbitrary models? No matter! Existential rules may rely on both once again
Amendola, Giovanni;Leone, Nicola;Manna, Marco
2017-01-01
Abstract
Ontology-based query answering asks whether a Boolean query is satisfied by all models of a logical theory consisting of an extensional 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. 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 showing that finite controllability holds also for shy ontologies. The demonstration is based on a number of technical tools which could be used for similar purposes and are valuable per se.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.