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
- 2. Sebastian Rudolph
- 3. Mantas Šimkus
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 3,909 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6375375e-05 |
| 5,165 | The Vadalog System: Datalog-based Reasoning for Knowledge Graphs | 2018 | VLDB | 5.6529675e-05 |
| 9,739 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 4.2936538e-05 |
| 11,386 | Rewriting the Infinite Chase | 2022 | VLDB | 4.1945683e-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 |
|---|---|---|---|---|
| 38 | Testing Implications Of Data Dependencies | 1979 | SIGMOD | 0.00075110004 |
| 1,018 | ILOG: Declarative Creation and Manipulation of Object Identifiers | 1990 | VLDB | 0.00014627963 |
| 5,057 | Queries with Guarded Negation | 2012 | VLDB | 5.7294436e-05 |
| 6,143 | Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP | 2013 | PODS | 5.1889914e-05 |
| 9,739 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 4.2936538e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,503 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS | 5.4738619e-05 |
| 7,591 | On the First-Order Expressibility of Recursive Queries | 1989 | PODS | 4.702934e-05 |
| 4,491 | Non-Deterministic Languages to Express Deterministic Transformations | 1990 | PODS | 6.1422281e-05 |
| 6,417 | Optimizing Existential Datalog Queries | 1988 | PODS | 5.0717071e-05 |
| 4,346 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS | 6.2725564e-05 |
| 5,057 | Queries with Guarded Negation | 2012 | VLDB | 5.7294436e-05 |
| 8,454 | On the power of Rule-Based Languages with Sets | 1991 | PODS | 4.5082358e-05 |
| 4,298 | Well-Founded Semantics for Extended Datalog and Ontological Reasoning | 2013 | PODS | 6.2885419e-05 |
| 3,909 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6375375e-05 |
| 11,898 | Default Negation for Non-Guarded Existential Rules | 2015 | PODS | 4.1945683e-05 |