On Estimating the Cardinality of the Projection of a Database Relation.

Rafiul Ahad, K. V. Bapa Rao, Dennis McLeod: On Estimating the Cardinality of the Projection of a Database Relation. ACM Trans. Database Syst. 14(1): 28-40(1989)
  author    = {Rafiul Ahad and
               K. V. Bapa Rao and
               Dennis McLeod},
  title     = {On Estimating the Cardinality of the Projection of a Database
  journal   = {ACM Trans. Database Syst.},
  volume    = {14},
  number    = {1},
  year      = {1989},
  pages     = {28-40},
  ee        = {, db/journals/tods/AhadRM89.html},
  bibsource = {DBLP,}


We present an analytical formula for estimating the cardinality of the projection on certain attributes of a subset of a relation in a relational database. This formula takes into account a priori knowledge of the semantics of the real-world objects and relationships that the database is intended to represent. Experimental testing of the formula shows that it has an acceptably low percentage error, and that its worst-case error is smaller than the best-known formula. Furthermore, the formula presented here has the advantage that it does not require a scan of the relation.

Copyright © 1989 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Joint ACM SIGMOD / IEEE Computer Society Anthology

CDROM Version: Load the CDROM "Volume 3 Issue 1, TODS 1976-1990" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX


Alfonso F. Cardenas: Evaluation and Selection of File Organization - A Model and System. Commun. ACM 16(9): 540-548(1973) BibTeX
To-Yat Cheung: Estimating Block Accesses and Number of Recorde in File Management. Commun. ACM 25(7): 484-487(1982) BibTeX
Stavros Christodoulakis: Estimating record selectivities. Inf. Syst. 8(2): 105-115(1983) BibTeX
E. F. Codd: A Relational Model of Data for Large Shared Data Banks. Commun. ACM 13(6): 377-387(1970) BibTeX
W. S. Luk: On Estimating Block Accesses in Database Organizations. Commun. ACM 26(11): 945-947(1983) BibTeX
T. H. Merrett, Ekow J. Otoo: Distribution Models of Relations. VLDB 1979: 418-425 BibTeX
Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976) BibTeX
Kyu-Young Whang, Gio Wiederhold, Daniel Sagalowicz: Estimating Block Accesses in Database Organizations: A Closed Noniterative Formula. Commun. ACM 26(11): 940-944(1983) BibTeX
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX

Referenced by

  1. Paolo Ciaccia, Dario Maio: Domains and Active Domains: What This Distinction Implies for the Estimation of Projection Sizes in Relational Databases. IEEE Trans. Knowl. Data Eng. 7(4): 641-655(1995)
  2. Ravi Mukkamala, Sushil Jajodia: A Note on Estimating the Cardinality of the Projection of a Database Relation. ACM Trans. Database Syst. 16(3): 564-566(1991)
  3. Himawan Gunadhi, Arie Segev: A Framework for Query Optimization in Temporal Databases. SSDBM 1990: 131-147
  4. Jeffrey F. Naughton, S. Seshadri: On Estimating the Size of Projections. ICDT 1990: 499-513
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Tue Jun 24 18:39:05 2008