Database Paper Browser

Back to papers

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
2073
Venue
SIGMOD
Year
1978
Pagerank
0.00064817807
Overall Rank
58 | 99.60%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 44 of 44 citing papers.

Rank Citing Paper Year Venue Pagerank
55 Efficiently Updating Materialized Views 1986 SIGMOD 0.00065687017
89 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00052299473
131 Can We Use The Universal Instance Assumption Without Using Nulls? 1981 SIGMOD 0.00043719033
142 Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) 1982 PODS 0.00041780711
154 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00040747653
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028572729
335 Optimization of Real Conjunctive Queries 1993 PODS 0.00027012705
364 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025657601
698 A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions 1980 SIGMOD 0.00017958037
835 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016081611
924 The U. R. Strikes Back 1982 PODS 0.00015249498
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014915911
1,167 On Computing Restricted Projections of Representative Instances 1985 PODS 0.0001354084
1,489 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011687823
1,965 Windows On The World 1983 SIGMOD 9.9176387e-05
1,997 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.837483e-05
2,105 Deciding Equivalences among Aggregate Queries 1998 PODS 9.5309231e-05
2,318 On Improving User Response Times in Tableau 2015 SIGMOD 9.04679e-05
2,331 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.019917e-05
2,398 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.8871067e-05
2,835 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.0468415e-05
3,175 Quality-driven Integration of Heterogeneous Information Systems 1999 VLDB 7.4418854e-05
3,339 A Universal Relation Database System Implemented Via the Network Model 1982 PODS 7.1989217e-05
3,494 On Chase Termination Beyond Stratification 2009 VLDB 7.0401e-05
3,913 Chase Termination for Guarded Existential Rules 2015 PODS 6.6311557e-05
4,349 Processing Queries with Quantifiers: A Horticultural Approach 1983 PODS 6.2577871e-05
5,093 Range Nesting: A Fast Method To Evaluate Quantified Queries 1983 SIGMOD 5.6972661e-05
5,196 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6311982e-05
5,247 Cooperative Update Exchange in the Youtopia System 2009 VLDB 5.601577e-05
5,719 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3551435e-05
7,070 Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions 1984 SIGMOD 4.8380576e-05
7,244 Positive Higher-Order Queries 2010 PODS 4.7856771e-05
7,603 Polynomial-time program transformations in deductive databases 1990 PODS 4.6959912e-05
8,205 Answering Queries In Relational Databases 1983 SIGMOD 4.5546165e-05
8,420 Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler 2017 SIGMOD 4.5116638e-05
9,045 Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study 2023 VLDB 4.3997447e-05
9,098 Querying Weak Instances 1984 PODS 4.3917473e-05
9,285 A Theory of Regular Queries 2016 PODS 4.3594818e-05
10,912 Chase Termination Beyond Polynomial Time 2024 PODS 4.1905499e-05
11,557 All-Instances Restricted Chase Termination 2020 PODS 4.1905499e-05
12,615 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.1905499e-05
12,936 Efficient Updates to Independent Schemes in the Weak Instance Model 1990 SIGMOD 4.1905499e-05
13,001 Query Optimization By Stored Queries 1987 VLDB 4.1905499e-05
13,011 Adaptive Predicate Managers in Database Systems 1986 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
2,109 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5283567e-05
445 Computing Joins Of Relations 1975 SIGMOD 0.00023029279
14,295 EFFICIENT PROCESSING OF RELATIONAL CALCULUS EXPRESSIONS USING RANGE QUERY THEORY (Extended Abstract) 1984 SIGMOD -
454 An Overview of Query Optimization in Relational Systems 1998 PODS 0.00022796106
2,867 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9931252e-05
7,979 On the Optimality of Strategies for Multiple Joins 1990 PODS 4.6089395e-05
603 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019334592
7,829 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS 4.6373918e-05
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
912 The Complexity of Evaluating Relational Queries 1983 PODS 0.00015374685