Estimating Block Accesses When Attributes Are Correlated

Summary: Addresses cost estimation under correlation between queried and clustering attributes, challenging independence-based overestimation. Uses Schur concavity and majorization to efficiently derive block-access costs and construct correlated access distributions. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 7930
Venue: VLDB
Year: 1986
Pagerank: 6.9682171e-05
Overall Rank: 3,996 | 72.59%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Brad T. Vander Zanden (Cornell University)
2. Howard M. Taylor (Cornell University)
3. Dina Bitton (Cornell University)

BibTeX Citation

@article{zanden_vldb86,
        title = {{Estimating Block Accesses When Attributes Are Correlated}},
        author = {Zanden, Brad T. Vander and Taylor, Howard M. and Bitton, Dina},
        journal = {PVLDB},
        series = {{VLDB} '86},
        pages = {119},
        year = {1986}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
474	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017894953
13,030	Estimating Page Fetches for Index Scans with Finite LRU Buffers	1994	SIGMOD	5.093636e-05
13,136	Evaluating the Size of Queries on Relational Databases with non Uniform Distribution and Stochastic Dependence	1989	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 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
417	Estimating Block Transfers and Join Sizes	1983	SIGMOD	0.00018819871
1,614	A Model of Data Distribution Based on Texture Analysis	1985	SIGMOD	0.00010215186

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,847	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS
2	4,790	A Characterization of the Sensitivity of Query Optimization to Storage Access Cost Parameters	2003	SIGMOD
3	682	Robust Estimation of Resource Consumption for SQL Queries using Statistical Techniques	2012	VLDB
4	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
5	3,482	Towards Predicting Query Execution Time for Concurrent and Dynamic Database Workloads	2013	VLDB
6	5,398	A Cost Model for Clustered Object-Oriented Databases	1995	VLDB
7	417	Estimating Block Transfers and Join Sizes	1983	SIGMOD
8	8,965	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB
9	3,771	Query Processing Method for Multi-Attribute Clustered Relations	1990	VLDB
10	2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB