An Algorithm For Ordering Subgoals In Nail!

Summary: Polynomial-time algorithm for ordering subgoals to generate rule-goal graphs in NAIL! (polynomial when recursive predicate arity is bounded) to support ICODE generation. Always finds a rule-goal graph if one exists; implemented in Cprolog but may be suboptimal. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h7fb8a981cd510910
Venue: PODS
Year: 1988
Pagerank: 0.00010998392
Overall Rank: 1,332 | 91.05%
DOI: 10.1145/308386.308419

Incoming Non-self Citations Over Time

Authors

1. Katherine A. Morris (Stanford University)

BibTeX Citation

@inproceedings{morris_pods88,
        address = {New York, NY, USA},
        series = {{PODS} '88},
        title = {{AN ALGORITHM FOR ORDERING SUBGOALS IN NAIL!}},
        url = {https://dl.acm.org/doi/10.1145/308386.308419},
        doi = {10.1145/308386.308419},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Morris, Katherine A.},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
117	Querying Heterogeneous Information Sources Using Source Descriptions	1996	VLDB	0.00031630695
869	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013348278
2,324	Partial Results for Online Query Processing	2002	SIGMOD	8.6310477e-05
3,364	Magic Conditions	1990	PODS	7.3731362e-05
3,640	The Complexity Of Ordering Subgoals	1988	PODS	7.1439794e-05
7,225	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.5810777e-05
9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS	5.2056825e-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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
3,640	The Complexity Of Ordering Subgoals	1988	PODS	7.1439794e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,131	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
2	2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS
3	4,833	Graph Queries in a Next-Generation Datalog System	2013	VLDB
4	14,707	On Negation in HiLog	1991	PODS
5	13,444	An Implementation Model For Reasoning With Complex Objects	1988	SIGMOD
6	3,484	Design and Implementation of the Glue-Nail Database System	1993	SIGMOD
7	3,640	The Complexity Of Ordering Subgoals	1988	PODS
8	3,659	Glue-Nail: A Deductive Database System	1991	SIGMOD
9	7,835	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB
10	9,266	Efficiently Ordering Subgoals with Access Constraints [Extended Abstract]	2006	PODS