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: 1168
Venue: PODS
Year: 1999
Pagerank: 5.8219225e-05
Overall Rank: 6,613 | 54.63%
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,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS	5.9213518e-05
9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD	5.3090815e-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.00060089598
2,763	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	8.1537086e-05

Semantically Similar Papers

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