A Journey to the Frontiers of Query Rewritability

Research output: Contribution to book/Conference proceedings/Anthology/ReportConference contributionContributedpeer-review

Contributors

Abstract

We consider (first-order) query rewritability in the context of theory-mediated query answering. The starting point of our journey is the FUS/FES conjecture, which states that any theory that is a finite expansion set (FES) and admits query rewriting (BDD, FUS) must be uniformly bounded. We show that this conjecture holds for a large class of BDD theories, which we call "local". Upon investigating how "non-local"BDD theories can actually get, we discover unexpected phenomena that, we think, are at odds with prevailing intuitions about BDD theories.

Details

Original languageEnglish
Title of host publicationPODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
EditorsLeonid Libkin, Pablo Barceló
PublisherACM Press
Pages359–367
Number of pages9
ISBN (electronic)9781450392600
ISBN (print)9781450392600
Publication statusPublished - 1 Jun 2022
Peer-reviewedYes

External IDs

Scopus 85132971246
Mendeley b21e47b1-7c99-350e-b037-0d325f9b3499
dblp conf/pods/Ostropolski-Nalewaja22
WOS 000850439300031

Keywords

Keywords

  • existential rules, first-order logic, first-order rewritability, Existential Rules, First-Order Rewritability, First-Order logic