The DOI matches its Crossref record; 55 of the 55 references it cites were found in a registry or an index.
Worst-case optimal join algorithms: [extended abstract]
Open accessAbstract
Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a novel algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a full conjunctive query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose running time achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this paper that any project-join plan is polynomially slower than the optimal bound for some queries. We construct an algorithm whose running time is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. In addition, we show that this bound is equivalent to a geometric inequality by Bollobás and Thomason, one of whose special cases is the famous Loomis-Whitney inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to compute a relaxed notion of joins.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
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
The Structure and Function of Complex Networks
Newman, M. E. J. (2003) · SIAM Review · doi:10.1137/s003614450342480 · Cited by 18,719
Access path selection in a relational database management system
Selinger, P. G., Astrahan, M. M., Chamberlin, D. D., Lorie, R. A., & Price, T. G. (1979) · Proceedings of the 1979 ACM SIGMOD international conference on Management of data - SIGMOD '79 · doi:10.1145/582095.582099 · Cited by 2,188
Query evaluation techniques for large databases
Graefe, G. (1993) · ACM Computing Surveys · doi:10.1145/152610.152611 · Cited by 1,262
Optimal implementation of conjunctive queries in relational data bases
Chandra, A. K., & Merlin, P. M. (1977) · Proceedings of the ninth annual ACM symposium on Theory of computing - STOC '77 · doi:10.1145/800105.803397 · Cited by 1,224
The complexity of relational query languages (Extended Abstract)
Vardi, M. Y. (1982) · Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82 · doi:10.1145/800070.802186 · Cited by 1,184
Optimal aggregation algorithms for middleware
Fagin, R., Lotem, A., & Naor, M. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375567 · Cited by 1,086
On the Desirability of Acyclic Database Schemes
Beeri, C., Fagin, R., Maier, D., & Yannakakis, M. (1983) · Journal of the ACM · doi:10.1145/2402.322389 · Cited by 808
Eddies: continuously adaptive query processing
Avnur, R., & Hellerstein, J. M. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335420 · Cited by 798
NP is as easy as detecting unique solutions
Valiant, L. G., & Vazirani, V. V. (1986) · Theoretical Computer Science · doi:10.1016/0304-3975(86)90135-0 · Cited by 635
Finding and counting given length cycles
Alon, N., Yuster, R., & Zwick, U. (1997) · Algorithmica · doi:10.1007/bf02523189 · Cited by 608
Improved histograms for selectivity estimation of range predicates
Poosala, V., Haas, P. J., Ioannidis, Y. E., & Shekita, E. J. (1996) · Proceedings of the 1996 ACM SIGMOD international conference on Management of data - SIGMOD '96 · doi:10.1145/233269.233342 · Cited by 556
The History of Histograms (abridged)
Ioannidis, Y. (2003) · Elsevier eBooks · doi:10.1016/b978-012722442-8/50011-2 · Cited by 502
Counting triangles and the curse of the last reducer
Suri, S., & Vassilvitskii, S. (2011) · Proceedings of the 20th international conference on World wide web · doi:10.1145/1963405.1963491 · Cited by 408
Hypertree Decompositions and Tractable Queries
Gottlob, G., Leone, N., & Scarcello, F. (2002) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1809 · Cited by 401
Finding a Minimum Circuit in a Graph
Itai, A., & Rodeh, M. (1978) · SIAM Journal on Computing · doi:10.1137/0207033 · Cited by 391
Eddies: continuously adaptive query processing
Avnur, R., & Hellerstein, J. M. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335420 · Cited by 381
The MADlib analytics library: or MAD skills, the SQL
Hellerstein, J. M., Ré, C., Schoppmann, F., Wang, D. Z., Fratkin, E., Gorajek, A., Ng, K. S., Welton, C., Feng, X., Li, K., et al. (2012) · Proceedings of the VLDB Endowment · doi:10.14778/2367502.2367510 · Cited by 373
Self-citationOn characterization of entropy function via information inequalities
Zhang, Z., & Yeung, R. W. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681320 · Cited by 351
DOULION: counting triangles in massive graphs with a coin
Tsourakakis, C. E., Kang, U., Miller, G. L., & Faloutsos, C. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557111 · Cited by 328
Conjunctive query containment revisited
Chekuri, C., & Rajaraman, A. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00220-0 · Cited by 316
A simplied universal relation assumption and its properties
Fagin, R., Mendelzon, A. O., & Ullman, J. D. (1982) · ACM Transactions on Database Systems · doi:10.1145/319732.319735 · Cited by 296
Fast Counting of Triangles in Large Real Networks without Counting: Algorithms and Laws
Tsourakakis, C. E. (2008) · 2008 Eighth IEEE International Conference on Data Mining · doi:10.1109/icdm.2008.72 · Cited by 265
Communication lower bounds for distributed-memory matrix multiplication
Irony, D., Toledo, S., & Tiskin, A. (2004) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2004.03.021 · Cited by 250
Extremal Combinatorics: With Applications in Computer Science
Jukna, S. (2011) · Texts in Theoretical Computer Science. An EATCS Series · doi:10.1007/978-3-642-17364-6 · Cited by 237
Design and implementation of the LogicBlox system
Aref, M., ten Cate, B., Green, T. J., Kimelfeld, B., Olteanu, D., Pasalic, E., Veldhuizen, T. L., & Washburn, G. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2742796 · Cited by 233 · cited 6×
“LFTJ is the work-horse join algorithm for the LogicBlox ’s datalog engine, and was already implemented since about 2009.”
BackgroundInfluentialBernstein, P. A., & Goodman, N. (1981) · SIAM Journal on Computing · doi:10.1137/0210059 · Cited by 226
Skew strikes back: new developments in the theory of join algorithms
Ngo, H. Q., Ré, C., & Rudra, A. (2014) · ACM SIGMOD Record · doi:10.1145/2590989.2590991 · Cited by 222
Self-citationTracking join and self-join sizes in limited storage
Alon, N., Gibbons, P. B., Matias, Y., & Szegedy, M. (1999) · doi:10.1145/303976.303978 · Cited by 211
Nonnegative entropy measures of multivariate symmetric correlations
Han, T. S. (1978) · Information and Control · doi:10.1016/s0019-9958(78)90275-9 · Cited by 210
EmptyHeaded: A Relational Engine for Graph Processing
Aberger, C. R., Lamb, A. A., Tu, S., Nötzli, A., Olukotun, K., & Ré, C. (2017) · ACM Transactions on Database Systems · doi:10.1145/3129246 · Cited by 188
Self-citationTowards a unified architecture for in-RDBMS analytics
Feng, X., Kumar, A., Recht, B., & Ré, C. (2012) · Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2213836.2213874 · Cited by 182
Self-citationFAQ: Questions Asked Frequently
Abo Khamis, M., Ngo, H. Q., & Rudra, A. (2016) · Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems · doi:10.1145/2902251.2902280 · Cited by 172
Self-citationSize Bounds and Query Plans for Relational Joins
Atserias, A., Grohe, M., & Marx, D. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.43 · Cited by 164
Learning Linear Regression Models over Factorized Joins
Schleich, M., Olteanu, D., & Ciucanu, R. (2016) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2882903.2882939 · Cited by 162
Constraint solving via fractional edge covers
Grohe, M., & Marx, D. (2006) · ACM-SIAM Symposium on Discrete Algorithms (SODA) · doi:10.1145/1109557.1109590 · Cited by 152
On the complexity of bounded-variable queries (extended abstract)
Vardi, M. Y. (1995) · doi:10.1145/212433.212474 · Cited by 141
Constraint solving via fractional edge covers
Grohe, M., & Marx, D. (2006) · Symposium on Discrete Algorithms · doi:10.5555/1109557.1109590 · Cited by 133
Kankanamge, C., Sahu, S., Mhedbhi, A., Chen, J., & Salihoğlu, S. (2017) · doi:10.1145/3035918.3056445 · Cited by 129
Size Bounds for Factorised Representations of Query Results
Olteanu, D., & Závodný, J. (2015) · ACM Transactions on Database Systems · doi:10.1145/2656335 · Cited by 116
ISOMER: Consistent Histogram Construction Using Query Feedback
Srivastava, U., Haas, P. J., Markl, V., Kutsch, M., & Tran, T. M. (2006) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2006.84 · Cited by 99
Demonstration of the Myria big data management service
Halperin, D., de Almeida, V. T., Choo, L. L., Chu, S., Koutris, P., Moritz, D., Ortíz, J., Ruamviboonsuk, V., Wang, J., Whitaker, A. C., et al. (2014) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/2588555.2594530 · Cited by 95
Hypertree Decompositions: Questions and Answers
Gottlob, G., Greco, G., Leone, N., & Scarcello, F. (2016) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/2902251.2902309 · Cited by 91
Efficient algorithms for large-scale local triangle counting
Becchetti, L., Boldi, P., Castillo, C., & Gionis, A. (2010) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1839490.1839494 · Cited by 87
On the complexity of database queries (extended abstract)
Papadimitriou, C. H., & Yannakakis, M. (1997) · doi:10.1145/263661.263664 · Cited by 66
In-Database Learning with Sparse Tensors
Khamis, M. A., Ngo, H. Q., Nguyen, X., Olteanu, D., & Schleich, M. (2018) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/3196959.3196960 · Cited by 61
Self-citationJoin Processing for Graph Patterns: An Old Dog with New Tricks
Nguyen, D. T., Aref, M., Bravenboer, M., Kollias, G., Ngo, H. Q., Ré, C., & Rudra, A. (2015) · doi:10.1145/2764947.2764948 · Cited by 60
Self-citationAJAR: Aggregations and Joins over Annotated Relations
Joglekar, M., Puttagunta, R., & Ré, C. (2016) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/2902251.2902293 · Cited by 55
Self-citationAC/DC: In-Database Learning Thunderstruck
Khamis, M. A., Ngo, H. Q., Nguyen, X., Olteanu, D., & Schleich, M. (2018) · Workshop on Data Management for End-to-End Machine Learning (DEEM) · doi:10.1145/3209889.3209896 · Cited by 54
Self-citationJoins via Geometric Resolutions: Worst Case and Beyond
Khamis, M. A., Ngo, H. Q., Ré, C., & Rudra, A. (2016) · ACM Transactions on Database Systems · doi:10.1145/2967101 · Cited by 46
Self-citationComputing Join Queries with Functional Dependencies
Khamis, M. A., Ngo, H. Q., & Suciu, D. M. (2016) · ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) · doi:10.1145/2902251.2902289 · Cited by 45
Self-citationStructure and complexity of relational queries
Chandra, A. K., & Harel, D. (1980) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1980.41 · Cited by 41
A superadditivity and submultiplicativity property for cardinalities of sumsets
Gyarmati, K., Matolcsi, M., & Ruzsa, I. Z. (2010) · COMBINATORICA · doi:10.1007/s00493-010-2413-6 · Cited by 36
Closures of database hypergraphs
Saccà, D. (1985) · Journal of the ACM · doi:10.1145/4221.4997 · Cited by 32
F: regression models over factorized views
Olteanu, D., & Schleich, M. (2016) · Proceedings of the VLDB Endowment · doi:10.14778/3007263.3007312 · Cited by 25
Juggling Functions Inside a Database
Khamis, M. A., Ngo, H. Q., & Rudra, A. (2017) · ACM SIGMOD Record · doi:10.1145/3093754.3093757 · Cited by 15
Self-citation
Cited by
Design and implementation of the LogicBlox system
Aref, M., ten Cate, B., Green, T. J., Kimelfeld, B., Olteanu, D., Pasalic, E., Veldhuizen, T. L., & Washburn, G. (2015) · Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data · doi:10.1145/2723372.2742796 · Cited by 233
Size Bounds for Factorised Representations of Query Results
Olteanu, D., & Závodný, J. (2015) · ACM Transactions on Database Systems · doi:10.1145/2656335 · Cited by 116
Metadata
- Authors
- Ngo, H. Q., Porat, E., Ré, C., & Rudra, A.
- Venue
- Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems
- Publisher
- ACM
- Published
- 2012-05-21
- Volume
- 65
- Issue
- 3
- Pages
- 37-48
- OpenAlex
- W1759086394
- Cited by
- 324
- References
- 55
- FWCI
- 10.51
- Type
- conference paper
- Language
- en
- Open access
- green
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.