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.
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
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)
Copyright © Tue Mar 16 02:21:56 2010
by Michael Ley (ley@uni-trier.de)