Argument Reduction by Factoring

Summary: Factoring is predicate-relative; factorability is undecidable in general. For broad classes, Magic Sets yields a factorable program; factoring enables a rewrite with lower arity and is never slower than the MS program, often dramatically faster. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h30591fbae57c5a04
Venue: VLDB
Year: 1989
Pagerank: 6.7450426e-05
Overall Rank: 4,187 | 71.86%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. J. F. Naughton (Princeton University)
2. R. Ramakrishnan (IBM; University of Wisconsin)
3. Y. Sagiv (Hebrew University)
4. J. D. Ullman (Stanford University)

BibTeX Citation

@article{naughton_vldb89,
        title = {{Argument Reduction by Factoring}},
        author = {Naughton, J. F. and Ramakrishnan, R. and Sagiv, Y. and Ullman, J. D.},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {173--182},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,849	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9795056e-05
7,605	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4844322e-05
13,235	Binding Propagation in Disjunctive Databases	1998	VLDB	4.9769913e-05
13,286	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	4.9769913e-05
13,420	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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.00058997063
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021210493
353	On the Power of Magic	1987	PODS	0.00020213935
1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.267247e-05
2,067	One-Sided Recursions	1987	PODS	9.0898007e-05
3,715	Compiling Separable Recursions	1988	SIGMOD	7.0736815e-05
6,436	Optimizing Existential Datalog Queries	1988	PODS	5.7841149e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,163	Magic Functions: A Technique to Optimize Extended Datalog Recursive Programs	1987	VLDB
2	4,228	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB
3	7,989	Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)	1991	PODS
4	13,420	Factoring Augmented Regular Chain Programs	1990	VLDB
5	4,427	Magic Counting Methods	1987	SIGMOD
6	7,605	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
7	13,395	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
8	7,090	On the Expected Size of Recursive Datalog Queries	1991	PODS
9	1,981	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
10	13,286	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS