Grammar-like Functional Rules for Representing Query Optimization Alternatives

Summary: Grammar-like functional rules represent query-optimization alternatives as data, with parameterized productions and conditions. Terminals are runtime primitives; non-terminals form plans with cost vectors and a glue to satisfy input properties. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2434
Venue: SIGMOD
Year: 1988
Pagerank: 0.00026028406
Overall Rank: 192 | 98.69%
DOI: 10.1145/50202.50204

Incoming Non-self Citations Over Time

Authors

1. Guy M. Lohman (IBM)

BibTeX Citation

@inproceedings{lohman_sigmod88,
        title = {{Grammar-like Functional Rules for Representing Query Optimization Alternatives}},
        author = {Lohman, Guy M.},
        series = {{SIGMOD} '88},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/50202.50204},
        url = {https://dl.acm.org/doi/10.1145/50202.50204},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 49 of 49 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
171	Optimizing Queries across Diverse Data Sources	1997	VLDB	0.00027363924
206	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00025092273
268	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022788687
290	An Overview of Query Optimization in Relational Systems	1998	PODS	0.0002227038
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
380	On Saying "Enough Already!" in SQL	1997	SIGMOD	0.00019563191
457	Don’t Scrap It, Wrap It! A Wrapper Architecture for Legacy Data Sources	1997	VLDB	0.00018120468
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
497	The Design of XPRS	1988	VLDB	0.00017462492
677	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00015065909
744	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014411295
1,272	A Framework for Automating Physical Database Design	1991	VLDB	0.0001138436
1,410	Magic is Relevant	1990	SIGMOD	0.00010853223
1,462	Advanced Query Processing in Object Bases Using Access Support Relations	1990	VLDB	0.00010701465
1,744	System RX: One Part Relational, One Part XML	2005	SIGMOD	9.868841e-05
1,759	Rank-aware Query Optimization	2004	SIGMOD	9.8160244e-05
1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD	9.6721003e-05
1,982	WeTune: Automatic Discovery and Verification of Query Rewrite Rules	2022	SIGMOD	9.3573897e-05
2,286	Extending the Search Strategy in a Query Optimizer	1991	VLDB	8.8044994e-05
2,505	A Transformation-Based Approach to Optimizing Loops in Database Programming Languages	1992	SIGMOD	8.4960641e-05
2,507	AQuery: Query Language for Ordered Data, Optimization Techniques, and Experiments	2003	VLDB	8.4889096e-05
2,563	AnalyticDB: Real-time OLAP Database System at Alibaba Cloud	2019	VLDB	8.412445e-05
2,628	Gral: An Extensible Relational Database System for Geometric Applications	1989	VLDB	8.326647e-05
3,036	On Parallel Processing of Aggregate and Scalar Functions in Object-Relational DBMS	1998	SIGMOD	7.8287552e-05
3,061	The Starburst Long Field Manager	1989	VLDB	7.8045347e-05
3,067	Evaluating Queries with Generalized Path Expressions	1996	SIGMOD	7.7940121e-05
3,097	Evita Raced: Metacompilation for Declarative Networks	2008	VLDB	7.7619658e-05
3,153	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB	7.6976958e-05
3,650	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.2249961e-05
3,656	Bypassing Joins in Disjunctive Queries	1995	VLDB	7.2224287e-05
3,726	Parallelizing Query Optimization	2008	VLDB	7.1697834e-05
4,134	Rule Languages and Internal Algebras for Rule-Based Optimizers	1996	SIGMOD	6.8816554e-05
4,346	Estimating Compilation Time of a Query Optimizer	2003	SIGMOD	6.7510183e-05
4,413	A Blackboard Architecture for Query Optimization in Object Bases	1993	VLDB	6.7168289e-05
4,645	User-Defined Table Operators: Enhancing Extensibility for ORDBMS	1999	VLDB	6.5900051e-05
4,771	Loading a Cache with Query Results	1999	VLDB	6.5158709e-05
4,998	An Incremental Join Attachment for Starburst	1990	VLDB	6.407975e-05
5,765	Charting the Design Space of Query Execution using VOILA	2021	VLDB	6.0953705e-05
6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD	6.0024042e-05
6,807	A Signature Access Method for the Starburst Database System	1989	VLDB	5.7664881e-05
7,774	Building Advanced SQL Analytics From Low-Level Plan Operators	2021	SIGMOD	5.5468469e-05
8,119	User-Optimizer Communication using Abstract Plans in Sybase ASE	2001	VLDB	5.4835315e-05
8,164	SlabCity: Whole-Query Optimization using Program Synthesis	2023	VLDB	5.4750309e-05
8,368	Excalibur: A Virtual Machine for Adaptive Fine-grained JIT-Compiled Query Execution based on VOILA	2023	VLDB	5.4419148e-05
8,423	Cracking SQL Barriers: An LLM-based Dialect Translation System	2025	SIGMOD	5.4275169e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
9,279	Including Bloom Filters in Bottom-up Optimization	2025	SIGMOD	5.2934632e-05
11,261	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.093636e-05
12,938	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0024089429
34	The Design Of Postgres	1986	SIGMOD	0.00049302774
80	Hashing Methods and Relational Algebra Operations	1984	VLDB	0.00036536643
119	The EXODUS Optimizer Generator	1987	SIGMOD	0.0003183602
152	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00029038365
342	R* Optimizer Validation and Performance Evaluation for Distributed Queries	1986	VLDB	0.00020673706
386	Distributed Query Processing In A Relational Data Base System	1978	SIGMOD	0.00019451022
615	A Rule-Based View of Query Optimization	1987	SIGMOD	0.00015720167
1,377	A Data Management Extension Architecture	1987	SIGMOD	0.00010972063
2,263	Optimization of Nested Queries in a Distributed Relational Database	1984	VLDB	8.8440084e-05
3,153	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB	7.6976958e-05
3,669	Distributing A Database For Parallelism	1983	SIGMOD	7.2118979e-05
3,980	Remotely-Sensed Geophysical Databases: Experience and Implications for Generalized DBMSs	1983	SIGMOD	6.9752983e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	143	Optimization of Nonrecursive Queries	1986	VLDB
2	984	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB
3	289	Optimization of Dynamic Query Evaluation Plans	1994	SIGMOD
4	13,040	Investigation of Algebraic Query Optimisation for Database Programming Languages	1994	VLDB
5	677	Query Optimization in the Presence of Foreign Functions	1993	VLDB
6	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
7	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB
8	7,137	Rule-Based Translation of Relational Queries into Iterative Programs	1986	SIGMOD
9	615	A Rule-Based View of Query Optimization	1987	SIGMOD
10	3,153	Implementing an Interpreter for Functional Rules in a Query Optimizer	1988	VLDB