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
2072
Venue
SIGMOD
Year
1978
Pagerank
0.00064826446
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.00065762967
88 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00052316625
135 Can We Use The Universal Instance Assumption Without Using Nulls? 1981 SIGMOD 0.00042421957
144 Testing Containment of Conjunctive Queries Under Functional and Inclusion Dependencies (Extended Abstract) 1982 PODS 0.00041462501
154 An Optimizing Prolog Front-End to a Relational Query System 1984 SIGMOD 0.00040645847
297 Complexity of Answering Queries Using Materialized Views 1998 PODS 0.00028596715
335 Optimization of Real Conjunctive Queries 1993 PODS 0.00027036073
363 A Graphical Query Language Supporting Recursion 1987 SIGMOD 0.00025715157
700 A Methodology For Interpreting Tree Queries Into Optimal Semi-Join Expressions 1980 SIGMOD 0.00017948517
837 An Extended Relational Algebra with Control Over Duplicate Elimination 1982 PODS 0.00016097758
920 The U. R. Strikes Back 1982 PODS 0.00015338004
971 Rewriting Aggregate Queries Using Views 1999 PODS 0.00014925576
1,196 On Computing Restricted Projections of Representative Instances 1985 PODS 0.00013403617
1,490 On the Decidability of Query Containment under Constraints 1998 PODS 0.00011699154
1,937 Windows On The World 1983 SIGMOD 0.00010029315
1,991 Decidability and Undecidability Results for Boundedness of Linear Recursive Queries 1988 PODS 9.84713e-05
2,103 Deciding Equivalences among Aggregate Queries 1998 PODS 9.5385023e-05
2,311 On Improving User Response Times in Tableau 2015 SIGMOD 9.0539767e-05
2,327 Obtaining Complete Answers from Incomplete Databases 1996 VLDB 9.0276061e-05
2,401 Physical Data Independence, Constraints, and Optimization with Universal Plans 1999 VLDB 8.8954126e-05
2,829 Computing Cores for Data Exchange: New Algorithms and Practical Solutions 2005 PODS 8.0546963e-05
3,170 Quality-driven Integration of Heterogeneous Information Systems 1999 VLDB 7.4482367e-05
3,332 A Universal Relation Database System Implemented Via the Network Model 1982 PODS 7.2123658e-05
3,489 On Chase Termination Beyond Stratification 2009 VLDB 7.0468114e-05
3,909 Chase Termination for Guarded Existential Rules 2015 PODS 6.6375375e-05
4,352 Processing Queries with Quantifiers: A Horticultural Approach 1983 PODS 6.2638329e-05
5,093 Range Nesting: A Fast Method To Evaluate Quantified Queries 1983 SIGMOD 5.7026228e-05
5,195 Equivalence of Queries Combining Set and Bag-Set Semantics 2006 PODS 5.6366303e-05
5,244 Cooperative Update Exchange in the Youtopia System 2009 VLDB 5.6069303e-05
5,709 On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract) 1997 PODS 5.3602702e-05
6,168 Optimal Computation of Total Projections with Unions of Simple Chase Join Expressions 1984 SIGMOD 5.1716335e-05
7,248 Positive Higher-Order Queries 2010 PODS 4.7902631e-05
7,598 Polynomial-time program transformations in deductive databases 1990 PODS 4.7004867e-05
8,216 Answering Queries In Relational Databases 1983 SIGMOD 4.5575596e-05
8,429 Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler 2017 SIGMOD 4.5156925e-05
9,012 Querying Weak Instances 1984 PODS 4.4096041e-05
9,045 Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study 2023 VLDB 4.4039656e-05
9,280 A Theory of Regular Queries 2016 PODS 4.3636639e-05
10,908 Chase Termination Beyond Polynomial Time 2024 PODS 4.1945683e-05
11,553 All-Instances Restricted Chase Termination 2020 PODS 4.1945683e-05
12,606 The NEXT Framework for Logical XQuery Optimization 2004 VLDB 4.1945683e-05
12,926 Efficient Updates to Independent Schemes in the Weak Instance Model 1990 SIGMOD 4.1945683e-05
12,990 Query Optimization By Stored Queries 1987 VLDB 4.1945683e-05
13,000 Adaptive Predicate Managers in Database Systems 1986 VLDB 4.1945683e-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,110 A Recursive Algebra and Query Optimization for Nested Relations 1989 SIGMOD 9.5315487e-05
441 Computing Joins Of Relations 1975 SIGMOD 0.00023058395
14,281 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.00022734812
2,860 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9934503e-05
7,976 On the Optimality of Strategies for Multiple Joins 1990 PODS 4.613363e-05
602 On the Complexity of Bounded-Variable Queries 1995 PODS 0.00019352415
7,824 Optimization of Multiple-Relation Multiple-Disjunct Queries 1988 PODS 4.6418459e-05
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
915 The Complexity of Evaluating Relational Queries 1983 PODS 0.0001538509