The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
CORDS: automatic discovery of correlations and soft functional dependencies
Abstract
The rich dependency structure found in the columns of real-world relational databases can be exploited to great advantage, but can also cause query optimizers---which usually assume that columns are statistically independent---to underestimate the selectivities of conjunctive predicates by orders of magnitude. We introduce CORDS, an efficient and scalable tool for automatic discovery of correlations and soft functional dependencies between columns. CORDS searches for column pairs that might have interesting and useful dependency relations by systematically enumerating candidate pairs and simultaneously pruning unpromising candidates using a flexible set of heuristics. A robust chi-squared analysis is applied to a sample of column values in order to identify correlations, and the number of distinct values in the sampled columns is analyzed to detect soft functional dependencies. CORDS can be used as a data mining tool, producing dependency graphs that are of intrinsic interest. We focus primarily on the use of CORDS in query optimization. Specifically, CORDS recommends groups of columns on which to maintain certain simple joint statistics. These "column-group" statistics are then used by the optimizer to avoid naive selectivity estimates based on inappropriate independence assumptions. This approach, because of its simplicity and judicious use of sampling, is relatively easy to implement in existing commercial systems, has very low overhead, and scales well to the large numbers of columns and large table sizes found in real-world databases. Experiments with a prototype implementation show that the use of CORDS in query optimization can speed up query execution times by an order of magnitude. CORDS can be used in tandem with query feedback systems such as the LEO learning optimizer, leveraging the infrastructure of such systems to correct bad selectivity estimates and ameliorating the poor performance of feedback systems during slow learning phases.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
Hapeman, D. E. (1991) · Technometrics · doi:10.1080/00401706.1991.10484817 · Cited by 9,373
Agresti, A. (2002) · Wiley Series in Probability and Statistics · doi:10.1002/0471249688 · Cited by 6,746
An Introduction to Probability Theory and Its Applications.
Bharucha-Reid, A. T., & Feller, W. (1967) · The American Mathematical Monthly · doi:10.2307/2314609 · Cited by 6,066
Mathematical Methods of Statistics.
Geary, R. C., & Cramer, H. (1947) · The Economic Journal · doi:10.2307/2226151 · Cited by 5,927
Measures of Association for Cross Classifications
Goodman, L. A., & Kruskal, W. H. (1979) · Springer Series in Statistics · doi:10.1007/978-1-4612-9995-0 · Cited by 2,244
Mining quantitative association rules in large relational tables
Srikant, R., & Agrawal, R. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233311 · Cited by 1,480
A General Class of Coefficients of Divergence of One Distribution from Another
Ali, S. M., & Silvey, S. D. (1966) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1966.tb00626.x · Cited by 1,205
An Introduction to Probability Theory and Its Applications, Volume II
Grubbs, F. E., & Feller, W. (1967) · Technometrics · doi:10.2307/1266435 · Cited by 1,097
Goodness-of-Fit Statistics for Discrete Multivariate Data
Read, T. R. C., & Cressie, N. A. C. (1988) · Springer Series in Statistics · doi:10.1007/978-1-4612-4578-0 · Cited by 771
Goodness-of-fit statistics for discrete multivariate data
(1989) · Choice Reviews Online · doi:10.5860/choice.26-2740 · Cited by 738
Measures of Association for Cross Classifications*
Goodman, L. A., & Kruskal, W. H. (1954) · Journal of the American Statistical Association · doi:10.1080/01621459.1954.10501231 · Cited by 678
The Non-Central χ 2 - and F-Distribution and their Applications
PATNAIK, P. B. (1949) · Biometrika · doi:10.2307/2332542 · Cited by 602
The non-central chi2- and F-distributions and their applications.
PATNAIK, P. B. (1949) · PubMed · Cited by 556
On the Choice of the Number of Class Intervals in the Application of the Chi Square Test
Mann, H. B., & Wald, A. (1942) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177731569 · Cited by 275
Learning belief networks from data: an information theory based approach
Cheng, J., Bell, D. A., & Liu, W. (1997) · Proceedings of the sixth international conference on Information and knowledge management · doi:10.1145/266714.266920 · Cited by 239
Brown, P., & Haas, P. J. (2003) · Elsevier eBooks · doi:10.1016/b978-012722442-8/50065-3 · Cited by 73
Self-citation
Cited by
Neo: a learned query optimizer
Marcus, R., Negi, P., Mao, H., Zhang, C., Alizadeh, M., Kraska, T., Papaemmanouil, O., & Tatbul, N. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3342263.3342644 · Cited by 389
An End-to-End Automatic Cloud Database Tuning System Using Deep Reinforcement Learning
Zhang, J., Liu, Y., Zhou, K., Li, G., Xiao, Z., Cheng, B., Xing, J., Wang, Y., Cheng, T., Liu, L., et al. (2019) · Proceedings of the 2019 International Conference on Management of Data · doi:10.1145/3299869.3300085 · Cited by 318
Profiling relational data: a survey
Abedjan, Z., Golab, L., & Naumann, F. (2015) · The VLDB Journal · doi:10.1007/s00778-015-0389-y · Cited by 283
KATARA: A Data Cleaning System Powered by Knowledge Bases and Crowdsourcing
Chu, X., Morcos, J., Ilyas, I. F., Ouzzani, M., Papotti, P., Tang, N., & Ye, Y. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2749431 · Cited by 279
Self-citationData quality: The other face of Big Data
Saha, B., & Srivastava, D. (2014) · 2014 IEEE 30th International Conference on Data Engineering · doi:10.1109/icde.2014.6816764 · Cited by 262
Metadata
- Authors
- Ilyas, I. F., Markl, V., Haas, P., Brown, P., & Aboulnaga, A.
- Venue
- Proceedings of the 2004 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 2004-06-13
- Pages
- 647-658
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2102489964
- Cited by
- 315
- References
- 17
- FWCI
- 6.34
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.