Containment for Rule-Based Ontology-Mediated Queries

Pablo Barceló, Gerald Berger, Andreas Pieris

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many efforts have been dedicated to identifying restrictions on ontologies expressed as tuple-generating dependencies (tgds), a.k.a. existential rules, that lead to the decidability of the problem of answering ontology-mediated queries (OMQs). This has given rise to three families of formalisms: guarded, non-recursive, and sticky sets of tgds. We study the containment problem for OMQs expressed in such formalisms, which is a key ingredient for solving static analysis tasks associated with them. Our main contribution is the development of specially tailored techniques for OMQ containment under the classes of tgds stated above. This enables us to obtain sharp complexity bounds for the problems at hand.
Original languageEnglish
Title of host publicationProceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018
Place of PublicationHouston, TX, USA
PublisherACM
Pages267-279
Number of pages13
ISBN (Print)978-1-4503-4706-8
DOIs
Publication statusPublished - 27 May 2018
EventACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018 - Texas, Houston, United States
Duration: 10 Jun 201815 Jun 2018
https://sigmod2018.org/

Conference

ConferenceACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2018
CountryUnited States
CityHouston
Period10/06/1815/06/18
Internet address

Fingerprint Dive into the research topics of 'Containment for Rule-Based Ontology-Mediated Queries'. Together they form a unique fingerprint.

Cite this