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: h4c7d090b0bfe23b9
Venue: SIGMOD
Year: 1996
Pagerank: 6.7307148e-05
Overall Rank: 4,197 | 71.87%
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,241	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.7710222e-05
2,576	The Case for Enhanced Abstract Data Types	1997	VLDB	8.2547439e-05
4,079	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	6.8026178e-05
7,255	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	5.5581956e-05
7,885	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	5.4169619e-05
8,393	Inferring Function Semantics to Optimize Queries	1998	VLDB	5.3246196e-05
12,330	Q*cert: A Platform for Implementing and Verifying Query Compilers	2017	SIGMOD	4.9605343e-05
14,314	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
99	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034024478
133	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.0003015194
197	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025558952
275	Extensible Query Processing in Starburst	1989	SIGMOD	0.000224395
1,015	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00012468327
1,030	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00012380641
2,874	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	7.898744e-05
8,575	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	5.29707e-05

Semantically Similar Papers

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