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: 2418
Venue: SIGMOD
Year: 1987
Pagerank: 5.093636e-05
Overall Rank: 13,179 | 9.58%
DOI: 10.1145/38713.38751

Incoming Non-self Citations Over Time

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

Authors

1. Wenming Zhang (University of Illinois Chicago)
2. C T Yu (University of Illinois Chicago)

BibTeX Citation

@inproceedings{zhang_sigmod87,
        title = {{A NECESSARY CONDITION FOR A DOUBLY RECURSIVE RULE TO BE EQUIVALENT TO A LINEAR RECURSIVE RULE}},
        author = {Zhang, Wenming and Yu, C T},
        series = {{SIGMOD} '87},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/38713.38751},
        url = {https://dl.acm.org/doi/10.1145/38713.38751},
        year = {1987}
}

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.00060089598
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
174	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00027231487
429	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018607152
539	Computing Queries from Derived Relations	1985	VLDB	0.00016872223
916	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00013224702
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,653	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	0.000101081
2,015	A Decidable Class of Bounded Recursions	1987	PODS	9.3047297e-05
4,634	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.5930956e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
2	2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD
3	3,603	Overbound and Right-Linear Queries	1991	PODS
4	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
5	13,116	Semigroup techniques in recursive query optimization	1990	PODS
6	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD
7	4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB
8	1,921	Efficient Evaluation of Right-, Left-, and Multi-Linear Rules	1989	SIGMOD
9	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
10	5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS