On the effect of join operations on relation sizes
- 1 December 1989
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 14 (4) , 574-603
- https://doi.org/10.1145/76902.76907
Abstract
We propose a generating function approach to the problem of evaluating the sizes of derived relations in a relational database framework. We present a model of relations and show how to use it to deduce probabilistic estimations of derived relation sizes. These are found to asymptotically follow normal distributions under a variety of assumptions.Keywords
This publication has 15 references indexed in Scilit:
- Optimization of distributed tree queriesJournal of Computer and System Sciences, 1984
- On the sizes of projections: A generating function approachInformation Systems, 1984
- How to estimate the sizes of domainsInformation Processing Letters, 1984
- Implications of certain assumptions in database performance evauationACM Transactions on Database Systems, 1984
- Query Optimization in Database SystemsACM Computing Surveys, 1984
- Optimizing Chain Queries in a Distributed Database SystemSIAM Journal on Computing, 1984
- Relational algebra operations and sizes of relationsLecture Notes in Computer Science, 1984
- Note on the expected size of a joinACM SIGMOD Record, 1981
- Extending the database relational model to capture more meaningACM Transactions on Database Systems, 1979
- Central and local limit theorems applied to asymptotic enumerationJournal of Combinatorial Theory, Series A, 1973