Guarded Ontology-Mediated Queries

Pablo Barceló, Gerald Berger, Georg Gottlob, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

We concentrate on ontology-mediated queries (OMQs) expressed using guarded Datalog and conjunctive queries. Guarded Datalog is a rule-based knowledge representation formalism inspired by the guarded fragment of first-order logic, while conjunctive queries represent a prominent database query language that lies at the core of relational calculus (i.e., first-order queries). For such guarded OMQs we discuss three main algorithmic tasks: query evaluation, query containment, and first-order rewritability. The first one is the task of computing the answer to an OMQ over an input database. The second one is the task of checking whether the answer to an OMQ is contained in the answer of some other OMQ on every input database. The third one asks whether an OMQ can be equivalently rewritten as a first-order query. For query evaluation, we explain how classical results on the satisfiability problem for the guarded fragment of first-order logic can be applied. For query containment, we discuss how tree automata techniques can be used. Finally, for first-order rewritability, we explain how techniques based on a more sophisticated automata model, known as cost automata, can be exploited.
Original languageEnglish
Title of host publicationHajnal Andréka and István Németi on Unity of Science
PublisherSpringer
Pages27-52
Number of pages26
Edition1
ISBN (Electronic)978-3-030-64187-0
ISBN (Print)978-3-030-64186-3
DOIs
Publication statusPublished - 1 Jun 2021

Publication series

NameOutstanding Contributions to Logic
PublisherSpringer, Cham
Volume19
ISSN (Print)2211-2758
ISSN (Electronic)2211-2766

Fingerprint

Dive into the research topics of 'Guarded Ontology-Mediated Queries'. Together they form a unique fingerprint.

Cite this