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,913 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6311557e-05 |
| 5,166 | The Vadalog System: Datalog-based Reasoning for Knowledge Graphs | 2018 | VLDB | 5.6475375e-05 |
| 9,738 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 4.2895392e-05 |
| 11,388 | Rewriting the Infinite Chase | 2022 | VLDB | 4.1905499e-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.0007528369 |
| 1,020 | ILOG: Declarative Creation and Manipulation of Object Identifiers | 1990 | VLDB | 0.00014614067 |
| 5,054 | Queries with Guarded Negation | 2012 | VLDB | 5.7239696e-05 |
| 6,147 | Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP | 2013 | PODS | 5.1840098e-05 |
| 9,738 | Expressive Languages for Querying the Semantic Web | 2014 | PODS | 4.2895392e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,516 | Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract) | 2000 | PODS | 5.4685963e-05 |
| 7,594 | On the First-Order Expressibility of Recursive Queries | 1989 | PODS | 4.6983854e-05 |
| 4,494 | Non-Deterministic Languages to Express Deterministic Transformations | 1990 | PODS | 6.1363251e-05 |
| 6,412 | Optimizing Existential Datalog Queries | 1988 | PODS | 5.0668361e-05 |
| 4,343 | Languages for Relational Databases over Interpreted Structures | 1997 | PODS | 6.2665123e-05 |
| 5,054 | Queries with Guarded Negation | 2012 | VLDB | 5.7239696e-05 |
| 8,448 | On the power of Rule-Based Languages with Sets | 1991 | PODS | 4.5039113e-05 |
| 4,291 | Well-Founded Semantics for Extended Datalog and Ontological Reasoning | 2013 | PODS | 6.2824978e-05 |
| 3,913 | Chase Termination for Guarded Existential Rules | 2015 | PODS | 6.6311557e-05 |
| 11,906 | Default Negation for Non-Guarded Existential Rules | 2015 | PODS | 4.1905499e-05 |