Rule Languages and Internal Algebras for Rule-Based Optimizers

Summary: Introduces KOLA, a combinator-based algebra for rule-based optimizers that eliminates external code in rule bodies. Shows simple-to-complex transformations, including nested queries, become expressible as pure KOLA rules, easing correctness and reasoning. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2901
Venue: SIGMOD
Year: 1996
Pagerank: 6.5117637e-05
Overall Rank: 4,032 | 71.96%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Mitch Cherniack
2. Stanley B. Zdonik

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,401	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8954126e-05
2,671	The Case for Enhanced Abstract Data Types	1997	VLDB	8.3367703e-05
5,525	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	5.4600815e-05
7,015	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	4.8609507e-05
7,891	Inferring Function Semantics to Optimize Queries	1998	VLDB	4.6247518e-05
8,429	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	4.5156925e-05
11,778	Q*cert: A Platform for Implementing and Verifying Query Compilers	2017	SIGMOD	4.1945683e-05
13,757	Visual COKO: A Debugger for Query Optimizer Development	2002	SIGMOD	-

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
100	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00049624696
130	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.00044031247
219	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00033244259
307	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028211308
975	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00014893961
990	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00014809094
2,719	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	8.2398923e-05
8,037	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	4.6005069e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,429	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	4.5156925e-05
12,847	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1945683e-05
8,454	On the power of Rule-Based Languages with Sets	1991	PODS	4.5082358e-05
12,302	A Framework for Testing Query Transformation Rules	2009	SIGMOD	4.1945683e-05
4,099	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB	6.4545871e-05
219	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00033244259
6,554	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0155947e-05
7,891	Inferring Function Semantics to Optimize Queries	1998	VLDB	4.6247518e-05
594	A Rule-Based View of Query Optimization	1987	SIGMOD	0.00019534507
7,015	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	4.8609507e-05