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.755142e-05
Overall Rank: 4,181 | 71.90%
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,226	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8033052e-05
2,571	The Case for Enhanced Abstract Data Types	1997	VLDB	8.2840962e-05
4,108	QueryBooster: Improving SQL Performance Using Middleware Services for Human-Centered Query Rewriting	2023	VLDB	6.8020689e-05
7,233	Changing the Rules: Transformations for Rule-Based Optimizers*	1998	SIGMOD	5.5792253e-05
7,865	Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler	2017	SIGMOD	5.4365956e-05
8,372	Inferring Function Semantics to Optimize Queries	1998	VLDB	5.3447387e-05
12,281	Q*cert: A Platform for Implementing and Verifying Query Compilers	2017	SIGMOD	4.9793485e-05
14,269	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
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034124569
132	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.00030241193
196	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025626873
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022504729
1,015	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00012500439
1,025	Algebraic Support for Complex Objects with Arrays, Identity, and Inheritance	1991	SIGMOD	0.00012427098
2,864	Optimization and Dataflow Algorithms for Nested Tree Queries	1989	VLDB	7.9273714e-05
8,549	OFL: A Functional Execution Model for Object Query Languages	1995	SIGMOD	5.3171056e-05

Semantically Similar Papers

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