Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries

Summary: Optimizes recursive Datalog evaluation by splitting mutually recursive rule loops, ordering rules to reduce joins, and exploiting loop invariants. A delta-aware seminaive algorithm supports nested subloops and improves magic-set-transformed query execution. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8149
Venue: VLDB
Year: 1990
Pagerank: 5.789691e-05
Overall Rank: 6,729 | 53.84%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Juhani Kuittinen (University of Helsinki)
2. Otto Nurmi (University of Helsinki)
3. Seppo Sippu (University of Jyväskylä)
4. Eljas Soisalon-Soininen (University of Helsinki)

BibTeX Citation

@article{kuittinen_vldb90,
        title = {{Efficient Implementation of Loops in Bottom-Up Evaluation of Logic Queries}},
        author = {Kuittinen, Juhani and Nurmi, Otto and Sippu, Seppo and Soisalon-Soininen, Eljas},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {372},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,680	Rule Ordering in Bottom-Up Fixpoint Evaluation of Logic Programs	1990	VLDB	5.5684407e-05

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 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
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
344	On the Power of Magic	1987	PODS	0.00020659405
1,538	Bottom-Up Beats Top-Down For Datalog	1989	PODS	0.00010446034
4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.5930956e-05
8,314	Optimization of Systems of Algebraic Equations for Evaluating Datalog Queries	1987	VLDB	5.4554917e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
2	3,629	Compiling Separable Recursions	1988	SIGMOD
3	7,679	Space Optimization in the Bottom-Up Evaluation of Logic Programs	1991	SIGMOD
4	7,131	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
5	13,186	An Extended Disjunctive Normal Form Approach for Optimizing Recursive Logic Queries in Loosely Coupled Environments	1987	VLDB
6	6,008	More Efficient Datalog Queries: Subsumptive Tabling Beats Magic Sets	2011	SIGMOD
7	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
8	429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS
9	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
10	16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS