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: 2963
Venue: SIGMOD
Year: 1996
Pagerank: 6.8816554e-05
Overall Rank: 4,134 | 71.64%
DOI: 10.1145/233269.233356

Incoming Non-self Citations Over Time

Authors

1. Mitch Cherniack (Brown University)
2. Stanley B. Zdonik (Brown University)

BibTeX Citation

@inproceedings{cherniack_sigmod96,
        title = {{Rule Languages and Internal Algebras for Rule-Based Optimizers}},
        author = {Cherniack, Mitch and Zdonik, Stanley B.},
        series = {{SIGMOD} '96},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/233269.233356},
        url = {https://dl.acm.org/doi/10.1145/233269.233356},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 8 of 8 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05
2,528	The Case for Enhanced Abstract Data Types	1997	VLDB	8.4620669e-05
4,909	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	6.4486671e-05
7,117	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	5.6976091e-05
8,209	Inferring Function Semantics to Optimize Queries	1998	VLDB	5.4664044e-05
8,712	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	5.3779634e-05
11,983	Q*cert: A Platform for Implementing and Verifying Query Compilers	2017	SIGMOD	5.093636e-05
13,958	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
95	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034607909
129	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.0003068101
192	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00026028406
268	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022788687
1,003	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00012705891
1,012	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00012682631
2,815	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	8.0964463e-05
8,380	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	5.4377187e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,712	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD
2	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
3	13,097	On the power of Rule-Based Languages with Sets	1991	PODS
4	12,496	A Framework for Testing Query Transformation Rules	2009	SIGMOD
5	3,153	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB
6	192	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD
7	7,137	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
8	8,209	Inferring Function Semantics to Optimize Queries	1998	VLDB
9	615	A Rule-Based View of Query Optimization	1987	SIGMOD
10	7,117	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD