DBScholar

Back to papers

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
h76984c944231cb8f
Venue
PODS
Year
1988
Pagerank
7.1439794e-05
Overall Rank
3,640 | 75.53%
DOI
10.1145/308386.308417

Incoming Non-self Citations Over Time

Authors

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,332 An Algorithm For Ordering Subgoals In Nail! 1988 PODS 0.00010998392
2,790 Processing First-Order Queries under Limited Access Patterns 2004 PODS 8.0100392e-05
9,266 Efficiently Ordering Subgoals with Access Constraints [Extended Abstract] 2006 PODS 5.2056825e-05
Previous Page 1 / 1 Next

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
18 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00059023577
1,332 An Algorithm For Ordering Subgoals In Nail! 1988 PODS 0.00010998392
Previous Page 1 / 1 Next

Semantically Similar Papers

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