DBScholar

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
8086
Venue
VLDB
Year
1989
Pagerank
0.00010965236
Overall Rank
1,382 | 90.52%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{lipton_vldb89,
        title = {{Estimating the Size of Generalized Transitive Closures}},
        author = {Lipton, Richard J. and Naughton, Jeffrey F.},
        journal = {PVLDB},
        series = {{VLDB} '89},
        pages = {165},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank Citing Paper Year Venue Pagerank
76 Practical Selectivity Estimation through Adaptive Sampling 1990 SIGMOD 0.00037054261
339 Sequential Sampling Procedures For Query Size Estimation 1992 SIGMOD 0.00020723773
484 Error-Constrained COUNT Query Evaluation in Relational Databases 1991 SIGMOD 0.00017746696
730 Bifocal Sampling for Skew-Resistant Join Size Estimation 1996 SIGMOD 0.00014539362
992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS 0.00012790174
1,186 Fixed-Precision Estimation of Join Selectivity 1993 PODS 0.00011764128
1,206 Random Sampling from Hash Files 1990 SIGMOD 0.00011663837
1,440 On the Relative Cost of Sampling for Join Selectivity Estimation 1994 PODS 0.00010778889
2,957 Graph-Theoretic Methods In Database Theory 1990 PODS 7.9200375e-05
4,458 Random Sampling from Pseudo-Ranked B+ Trees 1992 VLDB 6.6905953e-05
7,079 Adding Magic to an Optimising Datalog Compiler 2008 SIGMOD 5.7090732e-05
7,891 Adaptive Optimizations of Recursive Queries in Teradata 2012 SIGMOD 5.5211516e-05
9,676 Analysis and Application of Adaptive Sampling 2000 PODS 5.2377579e-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
36 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00048351457
55 Statistical Estimators for Relational Algebra Expressions 1988 PODS 0.00040746149
143 Optimization of Nonrecursive Queries 1986 VLDB 0.0002959213
217 Traversal Recursion: A Practical Approach to Supporting Recursive Applications 1986 SIGMOD 0.00024458594
417 Estimating Block Transfers and Join Sizes 1983 SIGMOD 0.00018819871
463 Optimization of Large Join Queries 1988 SIGMOD 0.00018064961
839 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00013692785
934 Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values 1988 VLDB 0.00013108714
1,086 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB 0.00012252192
1,114 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB 0.00012118382
1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB 0.00011437537
1,330 Efficient Transitive Closure Algorithms 1988 VLDB 0.00011140171
1,405 Top-down statistical estimation on a database 1983 SIGMOD 0.00010875661
1,921 Efficient Evaluation of Right-, Left-, and Multi-Linear Rules 1989 SIGMOD 9.4809066e-05
2,033 One-Sided Recursions 1987 PODS 9.2819369e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 3,941 Guaranteeing the O~(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins 2023 PODS
2 1,259 On the Computation of the Transitive Closure of Relational Operators 1986 VLDB
3 282 Efficient Management of Transitive Relationships in Large Data and Knowledge Bases 1989 SIGMOD
4 4,425 EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract) 1987 PODS
5 1,330 Efficient Transitive Closure Algorithms 1988 VLDB
6 2,076 A Study of Transitive Closure As a Recursion Mechanism 1987 SIGMOD
7 1,114 Direct Algorithms for Computing the Transitive Closure of Database Relations 1987 VLDB
8 1,086 New Strategies for Computing the Transitive Closure of a Database Relation 1987 VLDB
9 7,438 A Generalized Transitive Closure for Relational Queries 1988 PODS
10 992 Query Size Estimation by Adaptive Sampling (Extended Abstract) 1990 PODS