Expressiveness of Guarded Existential Rule Languages
Summary: Shows frontier-guarded and guarded existential-rule queries can be translated into plain Datalog and introduces nearly-frontier / nearly-guarded fragments that exactly capture Datalog (translations may be exponential). Proves weakly frontier-guarded = weakly guarded, establishes ExpTime-completeness, and that weakly guarded (+input negation on ordered DBs) and weakly guarded with stratified negation capture all ExpTime queries (stratified case without DB assumptions). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Georg Gottlob (University of Oxford)
- 2. Sebastian Rudolph (Technical University of Dresden)
- 3. Mantas Šimkus (Vienna University of Technology)
BibTeX Citation
@inproceedings{gottlob_pods14,
address = {New York, NY, USA},
series = {{PODS} '14},
title = {{Expressiveness of Guarded Existential Rule Languages}},
url = {https://dl.acm.org/doi/10.1145/2594538.2594556},
doi = {10.1145/2594538.2594556},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Gottlob, Georg and Rudolph, Sebastian and Šimkus, Mantas},
year = {2014}
}Incoming Citations (Sorted by Pagerank)
Showing 5 of 5 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,447 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.5945135e-05 |
| 5,037 | The Vadalog System: Datalog-based Reasoning for Knowledge Graphs | 2018 | VLDB | 6.3008628e-05 |
| 9,366 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 5.1849263e-05 |
| 11,898 | Rewriting the Infinite Chase | 2022 | VLDB | 4.9769913e-05 |
| 12,199 | Containment for Rule-Based Ontology-Mediated Queries | 2018 | PODS | 4.9769913e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 5 of 5 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 41 | Testing Implications Of Data Dependencies | 1979 | SIGMOD | 0.00045878061 |
| 1,003 | ILOG: Declarative Creation and Manipulation of Object Identifiers | 1990 | VLDB | 0.00012591126 |
| 4,246 | Queries with Guarded Negation | 2012 | VLDB | 6.7032723e-05 |
| 5,479 | Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP | 2013 | PODS | 6.1138487e-05 |
| 9,366 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 5.1849263e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 6,322 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS |
| 2 | 8,142 | On the First-Order Expressibility of Recursive Queries | 1989 | PODS |
| 3 | 6,436 | Optimizing Existential Datalog Queries | 1988 | PODS |
| 4 | 3,799 | Non-Deterministic Languages to Express Deterministic Transformations | 1990 | PODS |
| 5 | 4,428 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS |
| 6 | 4,246 | Queries with Guarded Negation | 2012 | VLDB |
| 7 | 13,393 | On the power of Rule-Based Languages with Sets | 1991 | PODS |
| 8 | 6,354 | Well-Founded Semantics for Extended Datalog and Ontological Reasoning | 2013 | PODS |
| 9 | 4,447 | Chase Termination for Guarded Existential Rules | 2015 | PODS |
| 10 | 12,396 | Default Negation for Non-Guarded Existential Rules | 2015 | PODS |