A Journey to the Frontiers of Query Rewritability

From International Center for Computational Logic

Toggle side column

A Journey to the Frontiers of Query Rewritability

Piotr Ostropolski-NalewajaPiotr Ostropolski-Nalewaja,  Jerzy MarcinkowskiJerzy Marcinkowski,  David CarralDavid Carral,  Sebastian RudolphSebastian Rudolph
A Journey to the Frontiers of Query Rewritability


Piotr Ostropolski-Nalewaja, Jerzy Marcinkowski, David Carral, Sebastian Rudolph
A Journey to the Frontiers of Query Rewritability
In Leonid Libkin, Pablo Barceló, eds., Proc. 41st Symposium on Principles of Database Systems (PODS'22), 359-367, June 2022. ACM
  • 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:Other info: Link
  • Projekt:Project: CPECDeciGUTScaDS.AI
  • Forschungsgruppe:Research Group: Computational LogicWissensbasierte Systeme
@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 = {Proc. 41st Symposium on Principles of Database Systems (PODS'22)},
  publisher = {ACM},
  year      = {2022},
  month     = {June},
  pages     = {359-367},
  doi       = {10.1145/3517804.3524163}
}