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: 817
Venue: PODS
Year: 1988
Pagerank: 0.00011234343
Overall Rank: 1,306 | 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.00032192665
851	Query Optimization in the Presence of Limited Access Patterns	1999	SIGMOD	0.00013611183
2,280	Partial Results for Online Query Processing	2002	SIGMOD	8.8129961e-05
3,307	Magic Conditions	1990	PODS	7.5385358e-05
3,565	The Complexity Of Ordering Subgoals	1988	PODS	7.3058198e-05
7,079	Adding Magic to an Optimising Datalog Compiler	2008	SIGMOD	5.7090732e-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
3,565	The Complexity Of Ordering Subgoals	1988	PODS	7.3058198e-05

Semantically Similar Papers

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