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.748235e-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,848	Right-, left- and multi-linear rule transformations that maintain context information	1990	VLDB	6.9827773e-05
7,599	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS	5.487029e-05
13,229	Binding Propagation in Disjunctive Databases	1998	VLDB	4.9793485e-05
13,280	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS	4.9793485e-05
13,414	Factoring Augmented Regular Chain Programs	1990	VLDB	4.9793485e-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.00059023577
317	OPTIMIZING DATALOG PROGRAMS (Extended Abstract)	1987	PODS	0.00021220438
352	On the Power of Magic	1987	PODS	0.00020223279
1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.2716242e-05
2,065	One-Sided Recursions	1987	PODS	9.0940924e-05
3,713	Compiling Separable Recursions	1988	SIGMOD	7.0770304e-05
6,433	Optimizing Existential Datalog Queries	1988	PODS	5.7868542e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,159	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,984	Termination Detection in Logic Programs using Argument Sizes* (Extended Abstract)	1991	PODS
4	4,425	Magic Counting Methods	1987	SIGMOD
5	13,414	Factoring Augmented Regular Chain Programs	1990	VLDB
6	7,599	Modular Acyclicity and Tail Recursion in Logic Programs	1991	PODS
7	13,389	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
8	7,088	On the Expected Size of Recursive Datalog Queries	1991	PODS
9	1,979	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
10	13,280	Magic Factoring of Closure Programs (Extended Abstract)	1995	PODS