On the Propagation of Errors in the Size of Join Results.
Yannis E. Ioannidis, Stavros Christodoulakis:
On the Propagation of Errors in the Size of Join Results.
SIGMOD Conference 1991: 268-277@inproceedings{DBLP:conf/sigmod/IoannidisC91,
author = {Yannis E. Ioannidis and
Stavros Christodoulakis},
editor = {James Clifford and
Roger King},
title = {On the Propagation of Errors in the Size of Join Results},
booktitle = {Proceedings of the 1991 ACM SIGMOD International Conference on
Management of Data, Denver, Colorado, May 29-31, 1991},
publisher = {ACM Press},
year = {1991},
pages = {268-277},
ee = {http://doi.acm.org/10.1145/115790.115835, db/conf/sigmod/IoannidisC91.html},
crossref = {DBLP:conf/sigmod/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
Query optimizers of current relational database systems
use several statistics maintained by the system on the
contents of the database to decide on the most efficient
access plan for a given query. These statistics contain
errors that transitively affect many estimates derived by
the optimizer. We present a formal framework based
on which the principles of this error propagation can be
studied. Within this framework, we obtain several analytic
results on how the error propagates in general, as
well as in the extreme and average cases. We also provide
results on guarantees that the database system can
make based on the statistics that it maintains. Finally,
we discuss some promising approaches to controlling the
error propagation and derive several interesting properties
of them.
Copyright © 1991 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
Online Version (ACM WWW Account required): Full Text in PDF Format
CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
James Clifford, Roger King (Eds.):
Proceedings of the 1991 ACM SIGMOD International Conference on Management of Data, Denver, Colorado, May 29-31, 1991.
ACM Press 1991 BibTeX
,
SIGMOD Record 20(2),
June 1991
Contents
[Index Terms]
[Full Text in PDF Format, 914 KB]
References
- [Chr84]
- Stavros Christodoulakis:
Implications of Certain Assumptions in Database Performance Evaluation.
ACM Trans. Database Syst. 9(2): 163-186(1984) BibTeX
- [Chr89]
- ...
- [IC91]
- ...
- [Kaz64]
- ...
- [MCS88]
- Michael V. Mannino, Paicheng Chu, Thomas Sager:
Statistical Profile Estimation in Database Systems.
ACM Comput. Surv. 20(3): 191-221(1988) BibTeX
- [ML86a]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Distributed Queries.
VLDB 1986: 149-159 BibTeX
- [ML86b]
- Lothar F. Mackert, Guy M. Lohman:
R* Optimizer Validation and Performance Evaluation for Local Queries.
SIGMOD Conference 1986: 84-95 BibTeX
- [MO79]
- ...
- [S+79]
- 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
- [Sel89]
- ...
- [Zip49]
- George Kingsley Zipf:
Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology.
Addison-Wesley 1949
BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Fri May 16 16:37:14 2008