A Journey to the Frontiers of Query Rewritability
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-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 language | English |
|---|---|
| Title of host publication | PODS 2022 - Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems |
| Editors | Leonid Libkin, Pablo Barceló |
| Publisher | ACM Press |
| Pages | 359–367 |
| Number of pages | 9 |
| ISBN (electronic) | 9781450392600 |
| ISBN (print) | 9781450392600 |
| Publication status | Published - 1 Jun 2022 |
| Peer-reviewed | Yes |
External IDs
| Scopus | 85132971246 |
|---|---|
| Mendeley | b21e47b1-7c99-350e-b037-0d325f9b3499 |
| dblp | conf/pods/Ostropolski-Nalewaja22 |
| WOS | 000850439300031 |
Keywords
ASJC Scopus subject areas
Keywords
- existential rules, first-order logic, first-order rewritability, Existential Rules, First-Order Rewritability, First-Order logic