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: 2902
Venue: SIGMOD
Year: 1996
Pagerank: 6.5056258e-05
Overall Rank: 4,039 | 71.93%
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,398	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8871067e-05
2,675	The Case for Enhanced Abstract Data Types	1997	VLDB	8.3295149e-05
5,533	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	5.4555519e-05
7,015	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	4.8563411e-05
7,891	Inferring Function Semantics to Optimize Queries	1998	VLDB	4.6203788e-05
8,420	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	4.5116638e-05
11,786	Q*cert: A Platform for Implementing and Verifying Query Compilers	2017	SIGMOD	4.1905499e-05
13,771	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
102	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00049592627
130	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.00044001626
220	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00033312045
309	Extensible Query Processing in Starburst	1989	SIGMOD	0.00028195213
975	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00014879359
991	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00014797083
2,722	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	8.232489e-05
8,039	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	4.5960982e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,420	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	4.5116638e-05
12,856	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB	4.1905499e-05
8,448	On the power of Rule-Based Languages with Sets	1991	PODS	4.5039113e-05
12,310	A Framework for Testing Query Transformation Rules	2009	SIGMOD	4.1905499e-05
4,093	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB	6.4521318e-05
220	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00033312045
6,550	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD	5.0113524e-05
7,891	Inferring Function Semantics to Optimize Queries	1998	VLDB	4.6203788e-05
592	A Rule-Based View of Query Optimization	1987	SIGMOD	0.0001953183
7,015	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	4.8563411e-05