Efficient Optimization of a Class of Relational Expressions

Summary: Proposes a tableau-based representation for the value of relational expressions built from select, project, and join, using FDs to induce tableau equivalences. NP-complete in general; a polynomial-time algorithm exists for an important subclass. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2134
Venue: SIGMOD
Year: 1978
Pagerank: 0.00034574497
Overall Rank: 97 | 99.34%
DOI: 10.1145/509252.509268

Incoming Non-self Citations Over Time

Authors

1. A. V. Aho (AT&T)
2. Y. Sagiv (Princeton University)
3. J. D. Ullman (Princeton University)

BibTeX Citation

@inproceedings{aho_sigmod78,
        title = {{Efficient Optimization of a Class of Relational Expressions}},
        author = {Aho, A. V. and Sagiv, Y. and Ullman, J. D.},
        series = {{SIGMOD} '78},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/509252.509268},
        url = {https://dl.acm.org/doi/10.1145/509252.509268},
        year = {1978}
}

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
39	Efficiently Updating Materialized Views	1986	SIGMOD	0.00047309646
134	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00030343737
153	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00029032276
225	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00024101949
266	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022823892
309	Optimization of Real Conjunctive Queries	1993	PODS	0.00021768596
312	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.00021733819
357	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00020283734
869	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013503594
1,095	An Extended Relational Algebra with Control Over Duplicate Elimination	1982	PODS	0.00012207515
1,111	The U. R. Strikes Back	1982	PODS	0.00012131168
1,417	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010839353
1,510	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010539169
1,630	On the Decidability of Query Containment under Constraints	1998	PODS	0.00010180625
1,788	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.7653696e-05
2,117	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	9.1434045e-05
2,189	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.9856333e-05
2,238	Deciding Equivalences among Aggregate Queries	1998	PODS	8.8882317e-05
2,289	Windows On The World	1983	SIGMOD	8.7994393e-05
2,550	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.4290753e-05
2,686	On Improving User Response Times in Tableau	2015	SIGMOD	8.25822e-05
3,247	On Chase Termination Beyond Stratification	2009	VLDB	7.5993811e-05
3,349	Quality-driven Integration of Heterogeneous Information Systems	1999	VLDB	7.4942642e-05
3,648	A Universal Relation Database System Implemented Via the Network Model	1982	PODS	7.2267453e-05
4,353	Chase Termination for Guarded Existential Rules	2015	PODS	6.7490677e-05
4,530	Processing Queries with Quantifiers: A Horticultural Approach	1983	PODS	6.6446379e-05
5,062	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.3799383e-05
5,154	Cooperative Update Exchange in the Youtopia System	2009	VLDB	6.3423714e-05
5,352	Range Nesting: A Fast Method To Evaluate Quantified Queries	1983	SIGMOD	6.2528892e-05
5,736	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	6.1050534e-05
7,132	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.694968e-05
7,654	Positive Higher-Order Queries	2010	PODS	5.5746273e-05
7,886	Polynomial-time program transformations in deductive databases	1990	PODS	5.5225498e-05
8,500	Answering Queries In Relational Databases	1983	SIGMOD	5.4133072e-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
9,195	Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study	2023	VLDB	5.3058708e-05
9,259	Querying Weak Instances	1984	PODS	5.2970277e-05
9,430	A Theory of Regular Queries	2016	PODS	5.2704983e-05
11,129	Chase Termination Beyond Polynomial Time	2024	PODS	5.093636e-05
11,750	All-Instances Restricted Chase Termination	2020	PODS	5.093636e-05
12,799	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	5.093636e-05
13,121	Efficient Updates to Independent Schemes in the Weak Instance Model	1990	SIGMOD	5.093636e-05
13,188	Query Optimization by Stored Queries	1987	VLDB	5.093636e-05
13,199	Adaptive Predicate Managers in Database Systems	1986	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,479	Computing Joins Of Relations	1975	SIGMOD
2	14,482	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD
3	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB
4	290	An Overview of Query Optimization in Relational Systems	1998	PODS
5	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	8,294	On the Optimality of Strategies for Multiple Joins	1990	PODS
7	763	On the Complexity of Bounded-Variable Queries	1995	PODS
8	7,858	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
9	143	Optimization of Nonrecursive Queries	1986	VLDB
10	1,467	The Complexity of Evaluating Relational Queries	1983	PODS