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)

Paper ID: 1631
Venue: PODS
Year: 2014
Pagerank: 5.7758194e-05
Overall Rank: 6,785 | 53.45%
DOI: 10.1145/2594538.2594556

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,353	Chase Termination for Guarded Existential Rules	2015	PODS	6.7490677e-05
4,920	The Vadalog System: Datalog-based Reasoning for Knowledge Graphs	2018	VLDB	6.4449498e-05
9,181	Expressive Languages for Querying the Semantic Web	2014	PODS	5.3064263e-05
11,584	Rewriting the Infinite Chase	2022	VLDB	5.093636e-05
11,893	Containment for Rule-Based Ontology-Mediated Queries	2018	PODS	5.093636e-05

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
40	Testing Implications Of Data Dependencies	1979	SIGMOD	0.00046918506
971	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00012875736
4,163	Queries with Guarded Negation	2012	VLDB	6.8603553e-05
5,347	Ontology-based Data Access: A Study through Disjunctive Datalog, CSP, and MMSNP	2013	PODS	6.2571376e-05
9,181	Expressive Languages for Querying the Semantic Web	2014	PODS	5.3064263e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,184	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS
2	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
3	6,307	Optimizing Existential Datalog Queries	1988	PODS
4	3,712	Non-Deterministic Languages to Express Deterministic Transformations	1990	PODS
5	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
6	4,163	Queries with Guarded Negation	2012	VLDB
7	13,097	On the power of Rule-Based Languages with Sets	1991	PODS
8	6,221	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS
9	4,353	Chase Termination for Guarded Existential Rules	2015	PODS
10	12,097	Default Negation for Non-Guarded Existential Rules	2015	PODS