Expressiveness of guarded existential rule languages

Georg GottlobGeorg Gottlob, Sebastian RudolphSebastian Rudolph, Mantas SimkusMantas Simkus

ISBN: 978-1-4503-2375-8
Download
DOI Link

Georg Gottlob, Sebastian Rudolph, Mantas Simkus
Expressiveness of guarded existential rule languages
In Richard Hull, Martin Grohe, eds., Proc. 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS'14), 27-38, June 2014. ACM

Details
Bibtex

KurzfassungAbstract
The so-called existential rules have recently gained attention, mainly due to their adequate expressiveness for ontological query answering. Several decidable fragments of such rules have been introduced, employing restriction such as various forms of guardedness to ensure decidability. Some of the more well-known languages in this arena are (weakly) guarded and (weakly) frontier-guarded fragments of existential rules. In this paper, we explore their relative and absolute expressiveness. In particular, we provide a new proof that queries expressed via frontier-guarded and guarded rules can be translated into plain Datalog queries. Since the converse translations are impossible, we develop generalizations of frontier-guarded and guarded rules to nearly frontier-guarded and nearly guarded rules, respectively, which have exactly the expressive power of Datalog. We further show that weakly frontier-guarded rules can be translated into weakly guarded rules, and thus, weakly frontier-guarded and weakly guarded rules have exactly the same expressive power. Such rules cannot be translated into Datalog since their query answering problem is ExpTime-complete in data complexity. We strengthen this result by showing that on ordered databases and with input negation available, weakly guarded rules capture all queries decidable in exponential time. We then show that weakly guarded rules extended with stratified negation are expressive enough to capture all database queries decidable in exponential time, without any assumptions about input databases. Finally, we note that the translations of this paper are, in general, exponential in size, but lead to worst-case optimal algorithms for query answering with considered languages.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{GRS2014,
  author    = {Georg Gottlob and Sebastian Rudolph and Mantas Simkus},
  title     = {Expressiveness of guarded existential rule languages},
  editor    = {Richard Hull and Martin Grohe},
  booktitle = {Proc. 33rd {ACM} {SIGMOD-SIGACT-SIGART} Symposium on Principles
               of Database Systems (PODS'14)},
  publisher = {ACM},
  year      = {2014},
  month     = {June},
  pages     = {27-38},
  doi       = {10.1145/2594538.2594556}
}