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: h277c651c53c3a9f0
Venue: PODS
Year: 1999
Pagerank: 5.6913065e-05
Overall Rank: 6,741 | 54.68%
DOI: 10.1145/303976.303991

Incoming Non-self Citations Over Time

Authors

1. Stavros Cosmadakis (University of Patras)

BibTeX Citation

@inproceedings{cosmadakis_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Inherent Complexity of Recursive Queries (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/303976.303991},
        doi = {10.1145/303976.303991},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cosmadakis, Stavros},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,429	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.7884926e-05
9,347	Optimizing Recursive Queries in SQL	2005	SIGMOD	5.1900828e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
2,822	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	7.9707629e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS
2	7,064	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
3	979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
4	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
5	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS
6	8,275	The Complexity of Why-Provenance for Datalog Queries	2024	PODS
7	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
8	3,315	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS
9	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
10	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS