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.722747e-05
Overall Rank: 4,206 | 71.81%
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,856	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9565167e-05
7,622	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.4663379e-05
13,276	Binding Propagation in Disjunctive Databases	1998	VLDB	4.9605343e-05
13,327	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	4.9605343e-05
13,461	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9605343e-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.00058816744
319	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021142713
353	On the Power of Magic	1987	PODS	0.0002014941
1,986	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2371562e-05
2,078	One-Sided Recursions	1987	PODS	9.0607099e-05
3,722	Compiling Separable Recursions	1988	SIGMOD	7.0503269e-05
6,448	Optimizing Existential Datalog Queries	1988	PODS	5.7650024e-05

Semantically Similar Papers

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