Inherent Complexity of Recursive Queries (Extended Abstract)

Summary: Lower bounds for Datalog evaluation via a new class of linear FO formulas whose quantifier depth and variable count measure sequential and parallel complexity respectively. A combinatorial game yields non-expressibility proofs and tight lower bounds using uniformity/invariance. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1169
Venue: PODS
Year: 1999
Pagerank: 5.1436959e-05
Overall Rank: 6,236 | 56.62%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Stavros Cosmadakis

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,992	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.2415551e-05
9,112	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3942347e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.0010066783
2,310	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	9.0580784e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,365	On the Expected Size of Recursive Datalog Queries	1991	PODS	5.0945408e-05
7,070	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS	4.843579e-05
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
1,490	On the Decidability of Query Containment under Constraints	1998	PODS	0.00011699154
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05
8,125	The Complexity of Why-Provenance for Datalog Queries	2024	PODS	4.5797807e-05
12,904	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS	4.1945683e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
7,591	On the First-Order Expressibility of Recursive Queries	1989	PODS	4.702934e-05