On Datalog vs. Polynomial Time

Summary: Proves existence of monotone PTIME queries not expressible in several Datalog variants. Uses monotone circuit lower bounds and a novel "Pumping Lemma" for Datalog to pinpoint inherent expressiveness limitations. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 920
Venue: PODS
Year: 1991
Pagerank: 5.9425753e-05
Overall Rank: 6,209 | 57.41%
DOI: 10.1145/113413.113415

Incoming Non-self Citations Over Time

Authors

1. Foto Afrati (National Technical University of Athens)
2. Stavros S. Cosmadakis (IBM)
3. Mihalis Yannakakis (AT&T)

BibTeX Citation

@inproceedings{afrati_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{On Datalog vs. Polynomial Time}},
        url = {https://dl.acm.org/doi/10.1145/113413.113415},
        doi = {10.1145/113413.113415},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Afrati, Foto and Cosmadakis, Stavros S. and Yannakakis, Mihalis},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,986	Combinatorial Games in Database Theory	1995	PODS	5.093636e-05
13,020	Bounded Arity Datalog(!=) Queries on Graphs (Extended Abstract)	1994	PODS	5.093636e-05
13,078	Datalog Expressiveness of Chain Queries: Grammar Tools and Characterizations	1992	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
2,763	Inductive Pebble Games And The Expressive Power Of Datalog	1989	PODS	8.1537086e-05
3,800	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	7.1130834e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,398	Query Evaluation by Circuits	2022	PODS
2	3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS
3	7,886	Polynomial-time program transformations in deductive databases	1990	PODS
4	11,147	Polynomial Time Convergence of the Iterative Evaluation of Datalogo Programs	2024	PODS
5	7,904	Tight Bounds of Circuits for Sum-Product Queries	2024	PODS
6	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
7	953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
8	2,579	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS
9	10,640	Circuits and Formulas for Datalog over Semirings	2025	PODS
10	4,238	Polynomial Time Query Processing in Temporal Deductive Databases	1990	PODS