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: h4659e27a7c55d50b
Venue: SIGMOD
Year: 1987
Pagerank: 4.9793485e-05
Overall Rank: 13,469 | 9.45%
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
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00059023577
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038009523
177	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.000266613
440	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018227953
551	Computing Queries from Derived Relations	1985	VLDB	0.000165527
946	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012936921
1,201	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011560838
1,682	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8850863e-05
2,062	A Decidable Class of Bounded Recursions	1987	PODS	9.0974416e-05
4,735	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.4452165e-05

Semantically Similar Papers

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