A Journey to the Frontiers of Query Rewritability

Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja, Jerzy MarcinkowskiJerzy Marcinkowski, David CarralDavid Carral, Sebastian RudolphSebastian Rudolph

ISBN: 978-1-4503-9260-0
Download
DOI Link

Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral, Sebastian Rudolph
A Journey to the Frontiers of Query Rewritability
In Leonid Libkin, Pablo Barceló, eds., Proceedings of the 41st Symposium on Principles of Database Systems (PODS'22), 359-367, June 2022. ACM

Details
Bibtex

KurzfassungAbstract
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.
Weitere Informationen unter:Further Information: Link
Projekt:Project: CPEC, DeciGUT, ScaDS.AI
Forschungsgruppe:Research Group: Computational LogicComputational Logic, Wissensbasierte SystemeKnowledge-Based Systems

@inproceedings{OMCR2022,
  author    = {Piotr Ostropolski-Nalewaja and Jerzy Marcinkowski and David
               Carral and Sebastian Rudolph},
  title     = {A Journey to the Frontiers of Query Rewritability},
  editor    = {Leonid Libkin and Pablo Barcel{\'{o}}},
  booktitle = {Proceedings of the 41st Symposium on Principles of Database
               Systems (PODS'22)},
  publisher = {ACM},
  year      = {2022},
  month     = {June},
  pages     = {359-367},
  doi       = {10.1145/3517804.3524163}
}