The Space-Efficient Core of Vadalog

Summary: Pinpoints piece-wise linear recursion (each TGD body has ≤1 mutually-recursive atom) as Vadalog's space-efficient core, capturing common industrial patterns and enabling tractable, space-efficient reasoning when combined with wardedness. Proves piece-wise linear alone is undecidable and characterizes expressiveness trade-offs of (piece-wise linear) warded TGDs versus related Datalog fragments. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1750
Venue: PODS
Year: 2019
Pagerank: 4.2895392e-05
Overall Rank: 9,737 | 32.33%
DOI: 10.1145/3294052.3319688

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,716	Datalog Unchained	2021	PODS	5.3569788e-05
13,206	KG-Roar: Interactive Datalog-based Reasoning on Virtual Knowledge Graphs	2023	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
142	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00041780711
784	Efficiently Answering Reachability Queries on Very Large Directed Graphs	2008	SIGMOD	0.00016648392
1,200	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013342243
1,885	The iBench Integration Metadata Generator	2016	VLDB	0.00010206139
2,212	A Decidable Class of Bounded Recursions	1987	PODS	9.2818302e-05
3,007	Benchmarking the Chase	2017	PODS	7.7243073e-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

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,056	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	4.1905499e-05
5,637	Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries	1990	VLDB	5.3978567e-05
8,129	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5753896e-05
10,296	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.1905499e-05
2,912	Convergence of Datalog over (Pre-) Semirings	2022	PODS	7.9261665e-05
9,813	Optimizing Nested Recursive Queries	2024	SIGMOD	4.2742278e-05
12,914	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1905499e-05
9,385	Exploiting the Power of Equality-generating Dependencies in Ontological Reasoning	2022	VLDB	4.342951e-05
11,133	The Vadalog Parallel System: Distributed Reasoning with Datalog+/-	2024	VLDB	4.1905499e-05
5,166	The Vadalog System: Datalog-based Reasoning for Knowledge Graphs	2018	VLDB	5.6475375e-05