A Necessary Condition For A Doubly Recursive Rule To Be Equivalent To A Linear Recursive Rule

Summary: Identifies a necessary (and sufficient) condition on variable placement in a class of doubly recursive rules to collapse them into a single linear recursive rule; formal proof in Sec. 4. Extends TrYu to enable recognizing nonlinear recursive queries that are equivalent to linear ones, enabling efficient linear-recursive-query processing. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2356
Venue: SIGMOD
Year: 1987
Pagerank: 4.1945683e-05
Overall Rank: 12,981 | 9.70%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Wenming Zhang
2. C T Yu

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.0010066783
77	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00057043861
172	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00038808816
296	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00028644922
416	Computing Queries from Derived Relations	1985	VLDB	0.0002380776
617	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00019090876
1,185	Data Independent Recursion in Deductive Databases	1986	PODS	0.00013445831
1,712	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.00010804573
2,206	A Decidable Class of Bounded Recursions	1987	PODS	9.2910236e-05
4,881	Translation And Optimization Of Logic Queries: The Algebraic Approach	1986	VLDB	5.8567721e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,529	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD	0.00011496686
1,648	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	0.00011028408
3,414	Overbound and Right-Linear Queries	1991	PODS	7.1232056e-05
12,962	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD	4.1945683e-05
12,921	Semigroup techniques in recursive query optimization	1990	PODS	4.1945683e-05
9,112	Optimizing Recursive Queries in SQL	2005	SIGMOD	4.3942347e-05
4,329	Commutativity And Its Role In The Processing Of Linear Recursion	1989	VLDB	6.2858126e-05
2,042	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD	9.699257e-05
3,999	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS	6.5469939e-05
5,180	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	5.6422249e-05