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: h25287c422a786871
Venue: SIGMOD
Year: 1978
Pagerank: 0.00033914384
Overall Rank: 102 | 99.32%
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.00046602544
136	Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract)	1982	PODS	0.00029740459
155	Common Expression Analysis in Database Applications	1982	SIGMOD	0.00028527932
238	Complexity of Answering Queries Using Materialized Views	1998	PODS	0.00023591683
278	Can We Use The Universal Instance Assumption Without Using Nulls?	1981	SIGMOD	0.00022313978
305	A Graphical Query Language Supporting Recursion	1987	SIGMOD	0.0002159111
310	Optimization of Real Conjunctive Queries	1993	PODS	0.00021374145
368	An Optimizing Prolog Front-End to a Relational Query System	1984	SIGMOD	0.00019864474
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
1,113	An Extended Relational Algebra with Control Over Duplicate Elimination	1982	PODS	0.00011971883
1,138	The U. R. Strikes Back	1982	PODS	0.00011865234
1,455	On Computing Restricted Projections of Representative Instances	1985	PODS	0.00010599099
1,540	A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions	1980	SIGMOD	0.00010315359
1,660	On the Decidability of Query Containment under Constraints	1998	PODS	9.9592164e-05
1,830	Decidability and Undecidability Results for Boundedness of Linear Recursive Queries	1988	PODS	9.5498891e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,226	Physical Data Independence, Constraints, and Optimization with Universal Plans	1999	VLDB	8.8033052e-05
2,269	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7196256e-05
2,346	Windows On The World	1983	SIGMOD	8.6020356e-05
2,594	Computing Cores for Data Exchange: New Algorithms and Practical Solutions	2005	PODS	8.2426092e-05
2,700	On Improving User Response Times in Tableau	2015	SIGMOD	8.1188166e-05
3,322	On Chase Termination Beyond Stratification	2009	VLDB	7.4292359e-05
3,407	Quality-driven Integration of Heterogeneous Information Systems	1999	VLDB	7.328074e-05
3,733	A Universal Relation Database System Implemented Via the Network Model	1982	PODS	7.0646557e-05
4,445	Chase Termination for Guarded Existential Rules	2015	PODS	6.5976367e-05
4,627	Processing Queries with Quantifiers: A Horticultural Approach	1983	PODS	6.4968665e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
5,256	Cooperative Update Exchange in the Youtopia System	2009	VLDB	6.2073004e-05
5,479	Range Nesting: A Fast Method To Evaluate Quantified Queries	1983	SIGMOD	6.1132235e-05
5,841	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.9735439e-05
7,279	Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions	1984	SIGMOD	5.5671882e-05
7,805	Positive Higher-Order Queries	2010	PODS	5.4501544e-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,053	Polynomial-time program transformations in deductive databases	1990	PODS	5.3986864e-05
8,667	Answering Queries In Relational Databases	1983	SIGMOD	5.2918559e-05
9,375	Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study	2023	VLDB	5.1868213e-05
9,433	Querying Weak Instances	1984	PODS	5.1781766e-05
9,611	A Theory of Regular Queries	2016	PODS	5.1522425e-05
11,477	Chase Termination Beyond Polynomial Time	2024	PODS	4.9793485e-05
12,053	All-Instances Restricted Chase Termination	2020	PODS	4.9793485e-05
13,089	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9793485e-05
13,411	Efficient Updates to Independent Schemes in the Weak Instance Model	1990	SIGMOD	4.9793485e-05
13,478	Query Optimization by Stored Queries	1987	VLDB	4.9793485e-05
13,489	Adaptive Predicate Managers in Database Systems	1986	VLDB	4.9793485e-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,514	Computing Joins Of Relations	1975	SIGMOD
2	10,264	EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract)	1984	SIGMOD
3	272	An Overview of Query Optimization in Relational Systems	1998	PODS
4	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB
5	10,508	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
6	8,462	On the Optimality of Strategies for Multiple Joins	1990	PODS
7	794	On the Complexity of Bounded-Variable Queries	1995	PODS
8	8,015	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS
9	143	Optimization of Nonrecursive Queries	1986	VLDB
10	1,503	The Complexity of Evaluating Relational Queries	1983	PODS