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.9605343e-05
Overall Rank: 13,516 | 9.40%
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.00058816744
67	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.0003786983
179	Decidability And Expressiveness Aspects Of Logic Queries	1987	PODS	0.00026563438
443	On the Implementation of a Simple Class of Logic Queries for Databases	1986	PODS	0.00018161613
553	Computing Queries from Derived Relations	1985	VLDB	0.00016493992
950	A Time Bound on the Materialization of Some Recursively Defined Views	1985	VLDB	0.00012888761
1,204	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011517335
1,688	Bounds on the Propagation of Selection into Logic Programs	1987	PODS	9.8481921e-05
2,075	A Decidable Class of Bounded Recursions	1987	PODS	9.0631365e-05
4,757	Translation and Optimization of Logic Queries: The Algebraic Approach	1986	VLDB	6.4208636e-05

Semantically Similar Papers

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