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}
}

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 ...

Printed Edition

Sixth International Conference on Very Large Data Bases, October 1-3, 1980, Montreal, Quebec, Canada, Proceedings. IEEE Computer Society 1980
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

References

[1]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
...
[5]
Robert Demolombe: Semantic Checking of Questions Expressed in Predicate Calculus Language. VLDB 1979: 444-450 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[6]
Robert Demolombe: Assigning Meaning to Ill-Defined Queries Expressed in Predicate Caculus Language. Advances in Data Base Theory 1979: 367-395 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[7]
Leo R. Gotlieb: Computing Joins of Relations. SIGMOD Conference 1975: 55-63 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Robert M. Pecherer: Efficient Evaluation of Expressions in a Relational Algebra. ACM Pacific 1975: 44-49 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[14]
...
[15]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing (Abstract). SIGMOD Conference 1976: 155 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Tue Mar 16 02:21:56 2010 by Michael Ley (ley@uni-trier.de)