On the First-Order Expressibility of Recursive Queries

Summary: Establishes that for several syntactic fragments of Datalog, first-order (FO) expressibility over finite structures coincides with boundedness (equivalence to recursion-free Datalog). Consequences: FO-expressibility undecidable for binary programs, decidable for monadic ones, and Σ^0_2-complete in general (e.g., transitive closure/path is non-FO). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 875
Venue: PODS
Year: 1989
Pagerank: 5.5160399e-05
Overall Rank: 7,972 | 45.31%
DOI: 10.1145/73721.73752

Incoming Non-self Citations Over Time

Authors

1. Stavros S. Cosmadakis (IBM)

BibTeX Citation

@inproceedings{cosmadakis_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{On the First-Order Expressibility of Recursive Queries}},
        url = {https://dl.acm.org/doi/10.1145/73721.73752},
        doi = {10.1145/73721.73752},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cosmadakis, Stavros S.},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.60327e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
616	Parallel Evaluation of Recursive Rule Queries	1986	PODS	0.00015712636
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,417	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010839353
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
2,015	A Decidable Class of Bounded Recursions	1987	PODS	9.3047297e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,600	Convergence of Datalog over (Pre-) Semirings	2022	PODS
2	13,023	Universal Finiteness and Satisfiability	1994	PODS
3	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
4	9,430	A Theory of Regular Queries	2016	PODS
5	6,077	Safety of Datalog Queries over Infinite Databases	1989	PODS
6	6,301	Evaluating Datalog over Semirings: A Grounding-based Approach	2024	PODS
7	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
8	1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
9	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	4,615	Tools for Datalog Boundedness	1991	PODS