Estimating record selectivities
Information SystemsPublished 1 January 1983
Stavros Christodoulakis
Citations111
SJR quartileQ1
SJR score0.89
SNIP1.96
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that certain assumptions-used for modelling data base contents, data placement on devices and user requests often are not satisfied in actual data base environments.
Abstract
In this paper we examine the problem of modelling data base contents and user requests. This modelling is necessary in analytic data base performance evaluation studies in order to estimate the number of records of a file that have to be retrieved in response to user(s) requests. The cpu, io, and telecommunication costs of the system are directly or indirectly expressed in terms of these quantities. We first show that certain assumptions-used for modelling data base contents, data placement on devices and user requests often are not satisfied in actual data base environments. Thereafter we provide more detailed modelling techniques based on a multivariate statistical model, and we demonstrate their use in improving data base performance.
Keywords
Computer ScienceDecision Sciences
Journal of the American Statistical AssociationProbability, Random Variables, and Stochastic Processes.
16,350 Citations1984Julia Abrahams, A. Papoulis
Pattern classification and scene analysis
12,643 Citations1973Richard O. Duda, Peter E. Hart
Journal of Business and Economic StatisticsAn Introduction to Multivariate Statistical Analysis
9,232 Citations1986Robb J. Muirhead, T. W. Anderson
Communications of the ACMA relational model of data for large shared data banks
5,238 Citations1970E. F. Codd
A model based on n-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced and certain operations on relations are discussed and applied to the problems of redundancy and consistency in the user's model.
Communications of the ACMA relational model of data for large shared data banks
4,834 Citations1983E. F. Codd
Journal of the Royal Statistical Society Series A (General)Pattern Classification and Scene Analysis.
3,240 Citations1974Mairi Clarke, Richard O. Duda +1 more
Pattern Recognition Principles
3,205 Citations2009
The present work gives an account of basic principles and available techniques for the analysis and design of pattern processing and recognition systems.
Access path selection in a relational database management system
2,153 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
This paper describes how System R chooses access paths for both simple (single relation) and complex queries (such as joins) given a user specification of desired data as a boolean expression of predicates.
ACM Transactions on Database SystemsSystem R
1,043 Citations1976M. M. Astrahan, Michael W. Blasgen +12 more
This paper contains a description of the overall architecture and design of the system, and emphasizes that System R is a vehicle for research in database architecture, and is not planned as a product.
Communications of the ACMAnalysis and performance of inverted data base structures
307 Citations1975Alfonso F. Cárdenas
The need to envision and architecture data base systems in a hierarchical level by level framework is stressed, and formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.
Journal of the American Statistical AssociationFrequency Curves and Correlation.
165 Citations1928Robert W. Burgess, W. Palin Elderton
Access path selection in a relational database management system
152 Citations1979Patricia G. Selinger, M. M. Astrahan +3 more
Communications of the ACMAttribute based file organization in a paged memory environment
143 Citations1974James B. Rothnie, Tomás Lozano‐Pérez
A method called multiple key hashing is proposed which attempts to minimize the high cost of page accessing and can often improve on a simple inversion technique by a factor of 2 or 3.
A heuristic approach to attribute partitioning
124 Citations1979Michael Hammer, Bahram Niamir
The goal of this work is to design mechanisms that can automatically select a near-optimal attribute partition of a file's attributes, based on the usage pattern of the file and on the characteristics of the data in the file, through a heuristic search technique.
ACM Transactions on Database SystemsOptimal partial-match retrieval when fields are independently specified
118 Citations1979Alfred V. Aho, Jeffrey D. Ullman
This paper considers the design of a system to answer partial-match queries from a file containing a collection of records, each record consisting of a sequence of fields.
ACM Transactions on Database SystemsA unifying model of physical databases
102 Citations1982Don Batory, C. C. Gotlieb
A unifying model for the study of database performance is proposed and applications of the model are shown to relate and extend important work concerning batched searching, transposed files, index selection, dynamic hash-based files, generalized access path structures, differential files, network databases, and multifile query processing.
ACM Transactions on Database SystemsPerformance evaluation of a relational associative processor
94 Citations1977Esen A. Ozkarahan, S. A. Schuster +1 more
The relational operations provided by the RAP hardware are described, and a representative approach to providing the same relational operations with conventional software and hardware is devised.
Information SystemsThe optimal selection of secondary indices for files
86 Citations1975Mario Schkolnick
It is shown that all the information assumed for each attribute can be condensed into two parameters and that properties of the optimal solution can be derived from this condensed information.
IBM Systems JournalSystem R: An architectural overview
67 Citations1999Michael W. Blasgen, M. M. Astrahan +15 more
The architecture of System R is described, including the Relational Data System and the Research Storage System, which supports a flexible spectrum of binding times, ranging from precompilation of “canned transactions” to on-line execution of ad hoc queries.
ACM Transactions on Database SystemsMinimum cost selection of secondary indexes for formatted files
62 Citations1977Henry Dwight Anderson, P. Bruce Berra
A cost function is developed for the evaluation of candidate indexing choices and applied to the optimization of index selection, demonstrating the increased effectiveness of secondary indexes for large files, the effect of the relative rates of retrieval and maintenance, the greater cost of allowing for arbitrarily formulated queries, and the impact on cost of the use of different index structures.
IBM Systems JournalSystem R: An architectural overview
53 Citations1981Michael W. Blasgen, M. M. Astrahan +15 more
IEEE Transactions on Electronic ComputersAn Algorithm for Non-Parametric Pattern Recognition
52 Citations1966George Sebestyen, J. Edie
An economical technique for the approximation of probability densities as generalized N-dimensional histograms constructed from a limited number of samples of each class is described.
Query Processing in SDD-1: A System for Distributed Databases
34 Citations1979Nathan Goodman, Philip A. Bernstein +3 more
The semi-join operator is defined, why semi- join is an effective reduction operator, and an algorithm is presented that constructs a cost effective program of semi-joins given an envelope and a database.
Application of an analytical model to evaluate storage structures
34 Citations1976Toby J. Teorey, Kapotaksha Das
Communications of the ACMComparison of several algorithms for computation of means, standard deviations and correlation coefficients
32 Citations1966Peter M. Neely
Bank-wide simulation studies may be performed upon request, and this is presently regarded as the highest potential level of development for the banking information system.
Evaluation of the size of a query expressed in relational algebra
29 Citations1981Philippe Richard
It is shown that, knowing the expected size of all projections of each relation in the database, one can compute the size of each query expressed in relational algebra and give the results for each operator of this language.
Estimating selectivities in data bases
29 Citations1982Stavros Christodoulakis
It is shown that certain assumptions used for modelling data base contents, data placement on devices and user requests often are not satisfied in actual data base environments, and that they may lead to errors in model predictions.
Information SystemsOn the selection of the access path in inverted database organization
11 Citations1979Anne Putkonen
This paper presents an optimization algorithm for the selection of the address lists that are worth using in inverted file organization and examines the conditions from the records that fulfil the conditions.
Information SystemsEfficient algorithms for answering queries with unsorted multilists
4 Citations1978Billy G. Claybrook, Chung-Shu Yang
Three algorithms are given in this paper, each one increasing in complexity and efficiency, for parallel tracing of unsorted multilists, and they attempt to reduce the amount of seek action required to access all the records that satisfy a query.
Birkhäuser Boston eBooksA Multivariate Statistical Model for Data Base Performance Evaluation
4 Citations1982Stavros Christodoulakis
A multivariate statistical model is presented for the estimation of the number of records qualifying in a query or a set of queries (record selectivities) that takes into account non-uniformity and correlations of the attribute values in the data base.