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.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/vldb7588 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

Printed Edition

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

References

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