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: h3dd51e239f436107
Venue: SIGMOD
Year: 1990
Pagerank: 5.4755041e-05
Overall Rank: 7,696 | 48.26%
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,886	Constraints and Redundancy in Datalog	1992	PODS	6.9461797e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
352	On the Power of Magic	1987	PODS	0.00020223279
2,024	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.166955e-05
3,713	Compiling Separable Recursions	1988	SIGMOD	7.0770304e-05
4,228	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.7165815e-05
5,413	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.1401229e-05
8,053	Polynomial-time program transformations in deductive databases	1990	PODS	5.3986864e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	979	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
2	13,313	Universal Finiteness and Satisfiability	1994	PODS
3	2,716	Equivalence, Query-Reachability, and Satisfiability in Datalog Extensions	1993	PODS
4	1,660	On the Decidability of Query Containment under Constraints	1998	PODS
5	1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS
6	8,136	On the First-Order Expressibility of Recursive Queries	1989	PODS
7	3,315	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS
8	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
9	4,712	Tools for Datalog Boundedness	1991	PODS
10	8,053	Polynomial-time program transformations in deductive databases	1990	PODS