DBScholar

Back to papers

Modular Acyclicity and Tail Recursion in Logic Programs

Summary: Generalize acyclicity to modular acyclicity: guarantees local stratification, unique perfect/Herbrand model MP, decidable membership, and finite semi‑naive Datalog evaluation even without duplicate elimination. Augment magic‑templates to exploit tail recursion via "nonrepeating" programs and give "weak right linearity" as a sufficient syntactic condition (proper superset of right‑linear) to improve evaluation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
927
Venue
PODS
Year
1991
Pagerank
5.6128072e-05
Overall Rank
7,454 | 48.86%
DOI
10.1145/113413.113422

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{ross_pods91,
        address = {New York, NY, USA},
        series = {{PODS} '91},
        title = {{Modular Acyclicity and Tail Recursion in Logic Programs}},
        url = {https://dl.acm.org/doi/10.1145/113413.113422},
        doi = {10.1145/113413.113422},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ross, Kenneth A.},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank Citing Paper Year Venue Pagerank
3,603 Overbound and Right-Linear Queries 1991 PODS 7.2683975e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
174 Decidability And Expressiveness Aspects Of Logic Queries 1987 PODS 0.00027231487
527 The Magic of Duplicates and Aggregates 1990 VLDB 0.00017108864
1,538 Bottom-Up Beats Top-Down For Datalog 1989 PODS 0.00010446034
1,714 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS 9.9404301e-05
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
2,579 Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract) 1989 PODS 8.3906191e-05
3,603 Overbound and Right-Linear Queries 1991 PODS 7.2683975e-05
3,767 Right-, left- and multi-linear rule transformations that maintain context information 1990 VLDB 7.1421254e-05
4,099 Argument Reduction by Factoring 1989 VLDB 6.9030568e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,824 Inference of Inequality Constraints in Logic Programs (Extended Abstract) 1991 PODS
2 953 On the Equivalence of Recursive and Nonrecursive Datalog Programs 1992 PODS
3 7,549 Hard problems for simple logic programs 1990 SIGMOD
4 6,948 On the Expected Size of Recursive Datalog Queries 1991 PODS
5 7,972 On the First-Order Expressibility of Recursive Queries 1989 PODS
6 4,099 Argument Reduction by Factoring 1989 VLDB
7 13,023 Universal Finiteness and Satisfiability 1994 PODS
8 6,729 Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries 1990 VLDB
9 7,824 Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract) 1991 PODS
10 1,714 Modular Stratification and Magic Sets for DATALOG Programs with Negation 1990 PODS