ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language.

Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63
@inproceedings{DBLP:conf/vldb/Demolombe80,
  author    = {Robert Demolombe},
  title     = {Estimation of the Number of Tuples Satisfying a Query Expressed
               in Predicate Calculus Language},
  booktitle = {Sixth International Conference on Very Large Data Bases, October
               1-3, 1980, Montreal, Quebec, Canada, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1980},
  pages     = {55-63},
  ee        = {db/conf/vldb/Demolombe80.html},
  crossref  = {DBLP:conf/vldb/80},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We present a statistic model which allows us to estimate the cardinality of queries and sub-queries expressed in Predicate Calculus language. In a first step, we deal with expressions formed only with an AND operator with n operands. We show how we can estimate recursively the cardinality of an expression with n operands in function of an expression of n-l operands. The formulae giving the cardinalities are calculated under several hypotheses concerning the independence of criteria which determine sub-expressions, and those which define the relations. The parameters which must be known are : the cardinalities of the relations and of their projections on each argument; the probability for an element in the intersection of several projections of relations to be in a given projection of a relation (these parameters are called inter-relation quantified dependencies); the probability that several components of a tuple of a relation are equal; and the probability that the constants which appear in a query belong to the corresponding projections of the relations. In a second step, we extend the method to general expressions including the operators NOT and OR. Finally, we discuss the feasibility of the method.

Copyright © 1980 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. IEEE Computer Society 1980
Contents BibTeX

References

[1]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[2]
E. F. Codd: Relational Completeness of Data Base Sublanguages. In: R. Rustin (ed.): Database Systems: 65-98, Prentice Hall and IBM Research Report RJ 987, San Jose, California : (1972) BibTeX
[3]
...
[4]
...
[5]
Robert Demolombe: Semantic Checking of Questions Expressed in Predicate Calculus Language. VLDB 1979: 444-450 BibTeX
[6]
Robert Demolombe: Assigning Meaning to Ill-Defined Queries Expressed in Predicate Caculus Language. Advances in Data Base Theory 1979: 367-395 BibTeX
[7]
Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 BibTeX
[8]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[9]
Patrick A. V. Hall: Optimization of a Single Relation Expression in a Relational Data Base System. IBM J. Res. Dev. 20(3): 244-257(1976) BibTeX
[10]
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 BibTeX
[11]
...
[12]
John Miles Smith, Philip Yen-Tang Chang: Optimizing the Performance of a Relational Algebra Database Interface. Commun. ACM 18(10): 568-579(1975) BibTeX
[13]
Larry J. Stockmeyer, C. K. Wong: On the Number of Comparisons to Find the Intersection of Two Relations. SIAM J. Comput. 8(3): 388-404(1979) BibTeX
[14]
...
[15]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing (Abstract). SIGMOD Conference 1976: 155 BibTeX
[16]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX

Referenced by

  1. Alfons Kemper, Guido Moerkotte, Michael Steinbrunn: Optimizing Boolean Expressions in Object-Bases. VLDB 1992: 79-90
  2. Kyu-Young Whang, Brad T. Vander Zanden, Howard M. Taylor: A Linear-Time Probabilistic Counting Algorithm for Database Applications. ACM Trans. Database Syst. 15(2): 208-229(1990)
  3. Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider: Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990: 1-11
  4. Richard J. Lipton, Jeffrey F. Naughton: Query Size Estimation by Adaptive Sampling. PODS 1990: 40-46
  5. Saumya K. Debray, Nai-Wei Lin: Static Estimation of Query Sizes in Horn Programs. ICDT 1990: 514-528
  6. Meng Chang Chen, Lawrence McNamee, Norman S. Matloff: Selectivity Estimation Using Homogeneity Measurement. ICDE 1990: 304-310
  7. Richard J. Lipton, Jeffrey F. Naughton: Estimating the Size of Generalized Transitive Closures. VLDB 1989: 165-171
  8. Brad T. Vander Zanden, Howard M. Taylor, Dina Bitton: Estimating Block Accessses when Attributes are Correlated. VLDB 1986: 119-127
  9. Matthias Jarke, Jürgen Koch: Query Optimization in Database Systems. ACM Comput. Surv. 16(2): 111-152(1984)
  10. Hervé Gallaire, Jack Minker, Jean-Marie Nicolas: Logic and Databases: A Deductive Approach. ACM Comput. Surv. 16(2): 153-185(1984)
  11. Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276
  12. Erol Gelenbe, Danièle Gardy: The Size of Projections of Relations Satisfying a Functional Dependency. VLDB 1982: 325-333
  13. Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
  14. Hervé Gallaire: Impacts of Logic and Databases (Invited Paper). VLDB 1981: 248-259
  15. Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163
  16. Jean Le Bihan, Christian Esculier, Gérard Le Lann, Witold Litwin, Georges Gardarin, S. Sedillort, L. Treille: SIRIUS: A French Nationwide Project on Distributed Data Bases. VLDB 1980: 75-85
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:08 2009