Semigroup techniques in recursive query optimization

Summary: Introduces a 'rule expansion' semigroup for finite linear recursive Datalog rules, where multiplication is top-down rule expansion and associativity is proven while distinguishing variable roles. Connects semigroup concepts to program boundedness and rule commutativity to codify prior results and derive new algebraic optimization directions for recursive query evaluation. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 895
Venue: PODS
Year: 1990
Pagerank: 5.093636e-05
Overall Rank: 13,116 | 10.02%
DOI: 10.1145/298514.298553

Incoming Non-self Citations Over Time

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

Authors

1. Thane Plambeck (Stanford University)

BibTeX Citation

@inproceedings{plambeck_pods90,
        address = {New York, NY, USA},
        series = {{PODS} '90},
        title = {{Semigroup techniques in recursive query optimization}},
        url = {https://dl.acm.org/doi/10.1145/298514.298553},
        doi = {10.1145/298514.298553},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Plambeck, Thane},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 6 of 6 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1,173	Data Independent Recursion in Deductive Databases	1986	PODS	0.00011822695
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
1,970	Proof-Tree Transformation Theorems and Their Applications	1989	PODS	9.3746238e-05
2,076	A Study of Transitive Closure As a Recursion Mechanism	1987	SIGMOD	9.212586e-05
4,150	Commutativity and Its Role in the Processing of Linear Recursion	1989	VLDB	6.8705682e-05
5,288	Linearizing nonlinear recursions in polynomial time (Extended Abstract)	1989	PODS	6.280882e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	143	Optimization of Nonrecursive Queries	1986	VLDB
2	13,158	Classification Of Recursive Formulas In Deductive Databases	1988	SIGMOD
3	4,972	On the Optimization of Recursive Relational Queries: Application to Graph Queries	2020	SIGMOD
4	9,933	Semantic Acyclicity Under Constraints	2016	PODS
5	6,926	On the Decidability of Containment of Recursive Datalog Queries - Preliminary report	2004	PODS
6	7,131	Magic-sets Transformation in Nonrecursive Systems	1992	PODS
7	2,054	Evaluation Of Database Recursive Logic Programs As Recurrent Function Series	1986	SIGMOD
8	4,369	Semantic Query Optimization in the Presence of Types	2010	PODS
9	13,099	Structural Query Optimization — A Uniform Framework For Semantic Query Optimization In Deductive Databases	1991	PODS
10	2,883	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS