Hard problems for simple logic programs

Summary: Undecidability for generalized single-IDB Datalog problems: sequencability and base-case linearizability, proven by CFG simulation with bounded initialization rules. Implications: containment/equivalence undecidable even for linear programs or a single recursive rule; tightens prior results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2533
Venue: SIGMOD
Year: 1990
Pagerank: 5.6011655e-05
Overall Rank: 7,549 | 48.21%
DOI: 10.1145/93597.93622

Incoming Non-self Citations Over Time

Authors

1. Yatin P. Saraiya (Stanford University)

BibTeX Citation

@inproceedings{saraiya_sigmod90,
        title = {{Hard problems for simple logic programs}},
        author = {Saraiya, Yatin P.},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.93622},
        url = {https://dl.acm.org/doi/10.1145/93597.93622},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,812	Constraints and Redundancy in Datalog	1992	PODS	7.105413e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 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
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
344	On the Power of Magic	1987	PODS	0.00020659405
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05
7,886	Polynomial-time program transformations in deductive databases	1990	PODS	5.5225498e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
2	13,023	Universal Finiteness and Satisfiability	1994	PODS
3	2,662	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
4	1,630	On the Decidability of Query Containment under Constraints	1998	PODS
5	1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
6	7,972	On the First-Order Expressibility of Recursive Queries	1989	PODS
7	3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS
8	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
9	4,615	Tools for Datalog Boundedness	1991	PODS
10	7,886	Polynomial-time program transformations in deductive databases	1990	PODS