The Complexity Of Ordering Subgoals

Summary: Shows that finding a feasible evaluation order for subgoals in a logical rule is inherently exponential-time. Proof establishes an exponential lower bound by reduction from linear-space alternating Turing-machine recognition, avoiding ordinary TM encodings. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 817
Venue: PODS
Year: 1988
Pagerank: 9.3375092e-05
Overall Rank: 2,187 | 84.79%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Jeffrey D. Ullman
2. Moshe Y. Vardi

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
729	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00017483521
3,065	Processing First-Order Queries under Limited Access Patterns	2004	PODS	7.6230903e-05
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-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.0010066783
729	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00017483521

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05
7,090	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB	4.8371966e-05
729	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00017483521
909	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS	0.00015428222
4,141	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS	6.4141369e-05
9,537	On the Feasibility of Checking Temporal Integrity Constraints	1993	PODS	4.3265281e-05
3,413	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS	7.1240395e-05
6,236	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS	5.1436959e-05
8,937	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	4.427232e-05