Evaluating the size of queries on relational databases with non-uniform distribution and stochastic dependence

ABSTRACT

The paper deals with the problem of evaluating how the originality of the attributes of a relation, i.e. the number of distinct values in each attribute, is affected by relational operations that reduce the cardinality of the relation. This is indeed an interesting problem in research areas such as database design and query optimization. Some authors have shown that non uniform distributions and stochastic dependence significantly affect the originality of the attributes. Therefore the models that have been proposed in the literature, based on uniformity and independence assumptions, in several situation can not be conveniently utilized. In this paper we propose a probabilistic model that overcomes the need of the uniformity and independence assumptions. The model is exact for non uniform distributions when the attributes are independent, and gives approximate results when stochastic dependence is considered. In the latter case the analytical results have been compared with a simulation, and proved to be quite accurate.

REFERENCES

• 1: Philip A. Bernstein , Nathan Goodman , Eugene Wong , Christopher L. Reeve , James B. Rothnie, Jr., Query processing in a system for distributed databases (SDD-1), ACM Transactions on Database Systems (TODS), v.6 n.4, p.602-625, Dec. 1981 [doi>10.1145/319628.319650]
• 2: Stefano Ceri , Giuseppe Pelagatti, Distributed databases principles and systems, McGraw-Hill, Inc., New York, NY, 1984
• 3: S. Christodulakis. Estimating record selectivities. Information Systems, 8(2):105-115, 1983.
• 4: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 5: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 6: A.R. Hevner and S. B. Yao. Query processing in distributed database systems. IEEE Transactions on Software Engineering, 5(3):177-187, 1979.
• 7: Larry Kerschberg , Peter D. Ting , S. Bing Yao, Query optimization in star computer networks, ACM Transactions on Database Systems (TODS), v.7 n.4, p.678-711, Dec. 1982 [doi>10.1145/319758.319778]
• 8: W. S. Luk, On estimating block accesses in database organizations, Communications of the ACM, v.26 n.11, p.945-947, Nov. 1983 [doi>10.1145/182.358456]
• 9: Clifford A. Lynch, Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distribution of Column Values, Proceedings of the 14th International Conference on Very Large Data Bases, p.240-251, August 29-September 01, 1988
• 10: Philippe Richard, Evaluation of the size of a query expressed in relational algebra, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582343]
• 11: S. Salza , M. Terranova, Database workload modeling, Database machine performance: modeling methodologies and evaluation strategies, Springer-Verlag, London, 1987
• 12: S. Salza and M. Terranova. Evaluating the cardinality of the result of relational operations" a probabilistic approach. In 6-th Advanced Database Symposium, Tokyo, pages 223-231, 1986.
• 13: Brad T. Vander Zanden , Howard M. Taylor , Dina Bitton, Estimating Block Accessses when Attributes are Correlated, Proceedings of the 12th International Conference on Very Large Data Bases, p.119-127, August 25-28, 1986
• 14: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 15: G.K. Zipf. Human Behaviour and the Principle of Least Effort. Addison Wesley Publ. Co., Reading, Massachussetts, 1949.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Design, Theory