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: 8087
Venue: VLDB
Year: 1989
Pagerank: 6.9030568e-05
Overall Rank: 4,099 | 71.88%
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,767	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	7.1421254e-05
7,454	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.6128072e-05
12,939	Binding Propagation in Disjunctive Databases	1998	VLDB	5.093636e-05
12,990	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	5.093636e-05
13,124	Factoring Augmented Regular Chain Programs	1990	VLDB	5.093636e-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
16	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00060089598
313	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.0002168869
344	On the Power of Magic	1987	PODS	0.00020659405
1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.4809066e-05
2,033	One-Sided Recursions	1987	PODS	9.2819369e-05
3,629	Compiling Separable Recursions	1988	SIGMOD	7.2392728e-05
6,307	Optimizing Existential Datalog Queries	1988	PODS	5.9196585e-05

Semantically Similar Papers

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