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: 816
Venue: PODS
Year: 1988
Pagerank: 7.3058198e-05
Overall Rank: 3,565 | 75.55%
DOI: 10.1145/308386.308417

Incoming Non-self Citations Over Time

Authors

1. Jeffrey D. Ullman (Stanford University)
2. Moshe Y. Vardi (IBM)

BibTeX Citation

@inproceedings{ullman_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{THE COMPLEXITY OF ORDERING SUBGOALS}},
        url = {https://dl.acm.org/doi/10.1145/308386.308417},
        doi = {10.1145/308386.308417},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ullman, Jeffrey D. and Vardi, Moshe Y.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,306	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00011234343
2,733	Processing First-Order Queries under Limited Access Patterns	2004	PODS	8.1927747e-05
9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	5.3251649e-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.00060089598
1,306	An Algorithm For Ordering Subgoals In Nail!	1988	PODS	0.00011234343

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
2	5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS
3	7,680	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB
4	1,306	An Algorithm For Ordering Subgoals In Nail!	1988	PODS
5	953	On the Equivalence of Recursive and Nonrecursive Datalog Programs	1992	PODS
6	4,263	Explicit Control of Logic Programs Through Rule Algebra	1988	PODS
7	9,905	On the Feasibility of Checking Temporal Integrity Constraints	1993	PODS
8	3,245	On the Complexity of Equivalence between Recursive and Nonrecursive Datalog Programs	1994	PODS
9	6,613	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
10	9,093	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS