Database Paper Browser

Back to papers

Estimating the Size of Generalized Transitive Closures

Summary: Framework to estimate size of binary recursively defined relations, enabling transitive closure estimates and generalizations. Linear-time for bounded-degree relations; enables cost-based optimization of recursive queries and avoids infeasible fixpoint. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
7895
Venue
VLDB
Year
1989
Pagerank
0.00018134733
Overall Rank
688 | 95.22%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
92 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00051315959
315 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.0002802103
367 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00025509745
553 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00020272061
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868
783 Random Sampling from Hash Files 1990 SIGMOD 0.00016704834
811 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00016425612
1,255 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00013024064
2,474 Graph-Theoretic Methods In Database Theory 1990 PODS 8.7135761e-05
3,966 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.580483e-05
6,957 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 4.8859842e-05
7,863 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 4.6328993e-05
9,523 Analysis and Application of Adaptive Sampling 2000 PODS 4.331052e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank Cited Paper Year Venue Pagerank
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
39 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00074745564
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
175 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00038338694
228 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00032269684
387 Optimization of Large Join Queries 1988 SIGMOD 0.0002471967
566 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019970535
615 Top-down statistical estimation on a database 1983 SIGMOD 0.00019128024
673 One-Sided Recursions 1987 PODS 0.00018348841
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
897 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00015528028
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
2,042 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.699257e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
5,104 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS 5.6946113e-05
1,055 On The Computation Of The Transitive Closure Of Relational Operators 1986 VLDB 0.00014422575
246 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD 0.00030949575
3,999 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS 6.5469939e-05
880 Efficient Transitive Closure Algorithms 1988 VLDB 0.00015667998
1,648 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD 0.00011028408
815 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00016369666
786 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00016660109
7,181 A Generalized Transitive Closure for Relational Queries 1988 PODS 4.8074621e-05
762 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00017036868