{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,24]],"date-time":"2026-07-24T02:40:41Z","timestamp":1784860841384,"version":"3.55.0"},"reference-count":128,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T00:00:00Z","timestamp":1623628800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T00:00:00Z","timestamp":1623628800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hasso-Plattner-Institut f\u00fcr Digital Engineering gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Effective query optimization is a core feature of any database management system. While most query optimization techniques make use of simple metadata, such as cardinalities and other basic statistics, other optimization techniques are based on more advanced metadata including data dependencies, such as functional, uniqueness, order, or inclusion dependencies. This survey provides an overview, intuitive descriptions, and classifications of query optimization and execution strategies that are enabled by data dependencies. We consider the most popular types of data dependencies and focus on optimization strategies that target the optimization of relational database queries. The survey supports database vendors to identify optimization opportunities as well as DBMS researchers to find related work and open research questions.<\/jats:p>","DOI":"10.1007\/s00778-021-00676-3","type":"journal-article","created":{"date-parts":[[2021,6,14]],"date-time":"2021-06-14T05:02:41Z","timestamp":1623646961000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":46,"title":["Data dependencies for query optimization: a survey"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1832-7282","authenticated-orcid":false,"given":"Jan","family":"Kossmann","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4019-8221","authenticated-orcid":false,"given":"Thorsten","family":"Papenbrock","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4483-1389","authenticated-orcid":false,"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,6,14]]},"reference":[{"key":"676_CR1","doi-asserted-by":"crossref","unstructured":"Abadi, D.J., Madden, S., Ferreira, M.: Integrating compression and execution in column-oriented database systems. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 671\u2013682 (2006)","DOI":"10.1145\/1142473.1142548"},{"key":"676_CR2","doi-asserted-by":"crossref","unstructured":"Abadi, D.J., Madden, S., Hachem, N.: Column-stores vs. row-stores: how different are they really? In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 967\u2013980 (2008)","DOI":"10.1145\/1376616.1376712"},{"issue":"4","key":"676_CR3","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/s00778-015-0389-y","volume":"24","author":"Z Abedjan","year":"2015","unstructured":"Abedjan, Z., Golab, L., Naumann, F.: Profiling relational data: a survey. VLDB J. 24(4), 557\u2013581 (2015)","journal-title":"VLDB J."},{"key":"676_CR4","doi-asserted-by":"crossref","unstructured":"Abedjan, Z., Quian\u00e9Ruiz, J.-A., Naumann, F.: Detecting unique column combinations on dynamic data. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 1036\u20131047 (2014)","DOI":"10.1109\/ICDE.2014.6816721"},{"key":"676_CR5","doi-asserted-by":"crossref","unstructured":"Abedjan, Z., et al.: Data Profiling. Vol. 10. Synthesis Lectures on Data Management 4. Morgan & Claypool Publishers (2018)","DOI":"10.2200\/S00878ED1V01Y201810DTM052"},{"key":"676_CR6","volume-title":"Foundations of Databases","author":"S Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Boston (1995)"},{"key":"676_CR7","doi-asserted-by":"crossref","unstructured":"Armstrong, W.W.: Dependency structures of data base relationships. In: IFIP Congress, pp. 580\u2013583 (1974)","DOI":"10.1515\/9783110840308-026"},{"issue":"1","key":"676_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(86)80022-5","volume":"70","author":"P Atzeni","year":"1986","unstructured":"Atzeni, P., Morfuni, N.M.: Functional dependencies and constraints on null values in database relations. Inf. Control 70(1), 1\u201331 (1986)","journal-title":"Inf. Control"},{"key":"676_CR9","doi-asserted-by":"crossref","unstructured":"Bass\u00e9e, R., Wijsen, J.: Neighborhood dependencies for prediction. In: Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD), pp. 562\u2013567. Springer, Berlin (2001)","DOI":"10.1007\/3-540-45357-1_59"},{"issue":"4","key":"676_CR10","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1145\/1634.1636","volume":"31","author":"C Beeri","year":"1984","unstructured":"Beeri, C., Vardi, M.: A proof procedure for data dependencies. J. ACM 31(4), 718\u2013741 (1984)","journal-title":"J. ACM"},{"issue":"4","key":"676_CR11","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1145\/319628.319650","volume":"6","author":"PA Bernstein","year":"1981","unstructured":"Bernstein, P.A., et al.: Query processing in a system for distributed databases (SDD-1). ACM Trans. Database Syst. 6(4), 602\u2013625 (1981)","journal-title":"ACM Trans. Database Syst."},{"key":"676_CR12","doi-asserted-by":"crossref","unstructured":"Bertossi, L.E.: Database Repairing and Consistent Query Answering. Morgan and Claypool Publishers (2011)","DOI":"10.1007\/978-3-031-01883-1"},{"issue":"11","key":"676_CR13","first-page":"2270","volume":"13","author":"J Birnick","year":"2020","unstructured":"Birnick, J., et al.: Hitting set enumeration with partial information for unique column combination discovery. PVLDB 13(11), 2270\u20132283 (2020)","journal-title":"PVLDB"},{"key":"676_CR14","unstructured":"Bl\u00e4sius, T., Friedrich, T., Schirneck, M.: The parameterized complexity of dependency detection in relational databases. In: Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC), vol. 6, no. (1\u20136), p. 13 (2017)"},{"key":"676_CR15","doi-asserted-by":"crossref","unstructured":"Bohannon, P., et al.: Conditional functional dependencies for data cleaning. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 746\u2013755 (2007)","DOI":"10.1109\/ICDE.2007.367920"},{"key":"676_CR16","doi-asserted-by":"crossref","unstructured":"Boissier, M., Schlosser, R., Uflacker, M.: Hybrid data layouts for tiered HTAP databases with pareto-optimal data placements. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 209\u2013 220 (2018)","DOI":"10.1109\/ICDE.2018.00028"},{"key":"676_CR17","doi-asserted-by":"crossref","unstructured":"Boncz, P.A., Neumann, T., Erling, O.: TPC-H analyzed: hidden messages and lessons learned from an influential benchmark. In: Performance Characterization and Benchmarking\u20145th TPC Technology Conference (TPCTC), pp. 61\u201376 (2013)","DOI":"10.1007\/978-3-319-04936-6_5"},{"key":"676_CR18","doi-asserted-by":"crossref","unstructured":"Brown, P., Haas, P.J.: BHUNT: automatic discovery of fuzzy algebraic constraints in relational data. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 668\u2013679 (2003)","DOI":"10.1016\/B978-012722442-8\/50065-3"},{"issue":"1","key":"676_CR19","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TKDE.2015.2472010","volume":"28","author":"L Caruccio","year":"2016","unstructured":"Caruccio, L., Deufemia, V., Polese, G.: Relaxed functional dependencies: a survey of approaches. IEEE Trans. Knowl. Data Eng. 28(1), 147\u2013165 (2016)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"676_CR20","unstructured":"Caruccio, L.: et al.: Incremental discovery of functional dependencies with a bit-vector algorithm. In: Proceedings of the Italian Symposium on Advanced Database Systems (2019)"},{"key":"676_CR21","doi-asserted-by":"crossref","unstructured":"Casanova, M.A., Fagin, R., Papadimitriou, C.H.: Inclusion dependencies and their interaction with functional dependencies. In: Proceedings of the Symposium on Principles of Database Systems (PODS), pp. 171\u2013176 (1982)","DOI":"10.1145\/588111.588141"},{"issue":"2","key":"676_CR22","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1145\/78922.78924","volume":"15","author":"US Chakravarthy","year":"1990","unstructured":"Chakravarthy, U.S., Grant, J., Minker, J.: Logic-based approach to semantic query optimization. ACM Trans. Database Syst. 15(2), 162\u2013207 (1990)","journal-title":"ACM Trans. Database Syst."},{"key":"676_CR23","unstructured":"Chaudhuri, S., Shim, K.: Including group-by in query optimization. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 354\u2013366 (1994)"},{"key":"676_CR24","unstructured":"Cheng, Q., et al.: Implementation of two semantic query optimization techniques in DB2 universal database. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 687\u2013698 (1999)"},{"key":"676_CR25","unstructured":"Ciaccia, P., Golfarelli, M., Rizzi, S.: On estimating the cardinality of aggregate views. In: Proceedings of the International Workshop on Design and Management of Data Warehouses, pp. 12.1\u201312.10 (2001)"},{"issue":"6","key":"676_CR26","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"EF Codd","year":"1970","unstructured":"Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377\u2013387 (1970)","journal-title":"Commun. ACM"},{"key":"676_CR27","unstructured":"Codd, E.F.: Further normalization of the data base relational model. In: IBM Research Report, San Jose, California RJ 909 (1971)"},{"issue":"3","key":"676_CR28","first-page":"23","volume":"7","author":"EF Codd","year":"1975","unstructured":"Codd, E.F.: Understanding relations (Installment #7). FDT Bull. ACM SIGFIDET SIGMOD 7(3), 23\u201328 (1975)","journal-title":"FDT Bull. ACM SIGFIDET SIGMOD"},{"key":"676_CR29","unstructured":"Date, C.J., Darwen, H.: Relational database writings 1989\u20131991. In: The Role of functional Dependence in Query Decomposition, pp. 133\u2013150. Addison-Wesley. Chap (1992)"},{"key":"676_CR30","unstructured":"Dayal, U.: Of nests and trees: a unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 197\u2013208 (1987)"},{"key":"676_CR31","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Nash, A., Remmel, J.B.: The chase revisited. In: Proceedings of the Symposium on Principles of Database Systems (PODS), pp. 149\u2013158 (2008)","DOI":"10.1145\/1376916.1376938"},{"key":"676_CR32","unstructured":"Deutsch, A., Popa, L., Tannen, V.: Physical data independence, constraints, and optimization with universal plans. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 459\u2013470 (1999)"},{"issue":"1","key":"676_CR33","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1145\/1121995.1122010","volume":"35","author":"A Deutsch","year":"2006","unstructured":"Deutsch, A., Popa, L., Tannen, V.: Query reformulation with constraints. SIGMOD Rec. 35(1), 65\u201373 (2006)","journal-title":"SIGMOD Rec."},{"key":"676_CR34","doi-asserted-by":"crossref","unstructured":"Dong, J., Hull, R.: Applying approximate order dependency to reduce indexing space. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 119\u2013127 (1982)","DOI":"10.1145\/582353.582375"},{"issue":"1\u20132","key":"676_CR35","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(96)00317-9","volume":"191","author":"RG Downey","year":"1998","unstructured":"Downey, R.G., Fellows, M.R., Regan, K.W.: Parameterized circuit complexity and the W hierarchy. Theor. Comput. Sci. 191(1\u20132), 97\u2013115 (1998)","journal-title":"Theor. Comput. Sci."},{"key":"676_CR36","unstructured":"Dreseler, M., et al.: Hyrise re-engineered: an extensible database system for research in relational in-memory data management. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 313\u2013324 (2019)"},{"key":"676_CR37","doi-asserted-by":"crossref","unstructured":"D\u00fcrsch, F, et al.: Inclusion dependency discovery: an experimental evaluation of thirteen algorithms. In: Proceedings of the International Conference on Information and Knowledge Management (CIKM), pp. 219\u2013228 (2019)","DOI":"10.1145\/3357384.3357916"},{"issue":"10","key":"676_CR38","first-page":"756","volume":"9","author":"M Eich","year":"2016","unstructured":"Eich, M., Fender, P., Moerkotte, G.: Faster plan generation through consideration of functional dependencies and keys. PVLDB 9(10), 756\u2013767 (2016)","journal-title":"PVLDB"},{"issue":"3","key":"676_CR39","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/320557.320571","volume":"2","author":"R Fagin","year":"1977","unstructured":"Fagin, R.: Multivalued dependencies and a new normal form for relational databases. ACM Trans. Datab. Syst. 2(3), 262\u2013278 (1977)","journal-title":"ACM Trans. Datab. Syst."},{"issue":"1","key":"676_CR40","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1145\/1061318.1061323","volume":"30","author":"R Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P.G., Popa, L.: Data exchange: getting to the core. ACM Trans. Database Syst. 30(1), 174\u2013210 (2005)","journal-title":"ACM Trans. Database Syst."},{"issue":"3","key":"676_CR41","first-page":"139","volume":"12","author":"PA Flach","year":"1999","unstructured":"Flach, P.A., Savnik, I.: Database dependency discovery: a machine learning approach. AI Commun. 12(3), 139\u2013160 (1999)","journal-title":"AI Commun."},{"key":"676_CR42","doi-asserted-by":"crossref","unstructured":"Ganguly, S., Hasan, W., Krishnamurthy, R.: Query optimization for parallel execution. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 9\u201318 (1992)","DOI":"10.1145\/141484.130291"},{"key":"676_CR43","doi-asserted-by":"crossref","unstructured":"Ganski, R.A., Wong, H.K.T.: Optimization of nested SQL queries revisited. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 23\u201333 (1987)","DOI":"10.1145\/38714.38723"},{"key":"676_CR44","unstructured":"Gelenbe, E., Gardy, D.: The size of projections of relations satisfying a functional dependency. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 325\u2013333 (1982)"},{"key":"676_CR45","doi-asserted-by":"crossref","unstructured":"Giannella, C., et al.: Improving query evaluation with approximate functional dependency based decompositions. In: Proceedings of British National Conference on Databases BNCOD, pp. 26\u201341 (2002)","DOI":"10.1007\/3-540-45495-0_3"},{"key":"676_CR46","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(83)90084-1","volume":"26","author":"S Ginsburg","year":"1983","unstructured":"Ginsburg, S., Hull, R.: Order dependency in the relational model. Theor. Comput. Sci. 26, 149\u2013195 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"676_CR47","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1145\/5925.5929","volume":"33","author":"S Ginsburg","year":"1986","unstructured":"Ginsburg, S., Hull, R.: Sort sets in the relational model. J. ACM 33(3), 465\u2013488 (1986)","journal-title":"J. ACM"},{"issue":"1","key":"676_CR48","first-page":"574","volume":"2","author":"L Golab","year":"2009","unstructured":"Golab, L., et al.: Sequential dependencies. PVLDB 2(1), 574\u2013585 (2009)","journal-title":"PVLDB"},{"issue":"2","key":"676_CR49","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1145\/152610.152611","volume":"25","author":"G Graefe","year":"1993","unstructured":"Graefe, G.: Query evaluation techniques for large databases. ACM Comput. Surv. 25(2), 73\u2013170 (1993)","journal-title":"ACM Comput. Surv."},{"issue":"3","key":"676_CR50","first-page":"19","volume":"18","author":"G Graefe","year":"1995","unstructured":"Graefe, G.: The cascades framework for query optimization. IEEE Data Eng. Bull. 18(3), 19\u201329 (1995)","journal-title":"IEEE Data Eng. Bull."},{"key":"676_CR51","unstructured":"Gryz, J.: Query folding with inclusion dependencies. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 126\u2013133 (1998)"},{"key":"676_CR52","unstructured":"Hammer, M., Zdonik, S.B.: Knowledge-based query processing. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 137\u2013147 (1980)"},{"issue":"4","key":"676_CR53","first-page":"301","volume":"7","author":"A Heise","year":"2013","unstructured":"Heise, A., et al.: Scalable discovery of unique column combinations. PVLDB 7(4), 301\u2013312 (2013)","journal-title":"PVLDB"},{"key":"676_CR54","unstructured":"Huhtala, Y., et al.: Efficient discovery of functional and approximate dependencies using partitions. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 392\u2013401 (1998)"},{"key":"676_CR55","doi-asserted-by":"crossref","unstructured":"Huhtala, Y., et\u00a0al.: TANE: an efficient algorithm for discovering functional and approximate dependencies. Comput. J. 42(2), 100\u2013111 (1999)","DOI":"10.1093\/comjnl\/42.2.100"},{"key":"676_CR56","unstructured":"IBM. Referential integrity constraints help reduce the number of statistical views. (2019). https:\/\/www.ibm.com\/support\/knowledgecenter\/SSEPGG_11.5.0\/com.ibm.db2.luw.admin.perf.doc\/doc\/c0059081.html (visited on 04\/28\/2020)"},{"key":"676_CR57","doi-asserted-by":"crossref","unstructured":"Ileana, I., et al.: Complete yet practical search for minimal query reformulations under constraints\u2019. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 1015\u20131026 (2014)","DOI":"10.1145\/2588555.2593683"},{"key":"676_CR58","doi-asserted-by":"crossref","unstructured":"Ilyas, I.F. et al.: CORDS: automatic discovery of correlations and soft functional dependencies. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 647\u2013658 (2004)","DOI":"10.1145\/1007568.1007641"},{"key":"676_CR59","unstructured":"International Organization for Standardization: ISO\/IEC 9075-2:1999 (SQL Standard 1999). Standard (1999)"},{"key":"676_CR60","unstructured":"International Organization for Standardization: ISO\/IEC 9075:1992 (SQL Standard 1992). Standard (1992)"},{"issue":"1","key":"676_CR61","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1145\/234313.234367","volume":"28","author":"YE Ioannidis","year":"1996","unstructured":"Ioannidis, Y.E.: Query optimization. ACM Comput. Surv. 28(1), 121\u2013123 (1996)","journal-title":"ACM Comput. Surv."},{"key":"676_CR62","unstructured":"Klebanoff, J: Apache derby: intersect and except design (2005). https:\/\/db.apache.org\/derby\/papers\/Intersect-design.html (visited on 11\/23\/2020)"},{"issue":"2","key":"676_CR63","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1145\/356924.356928","volume":"16","author":"M Jarke","year":"1984","unstructured":"Jarke, M., Koch, J.: Query optimization in database systems. ACM Comput. Surv. 16(2), 111\u2013152 (1984)","journal-title":"ACM Comput. Surv."},{"issue":"1","key":"676_CR64","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0022-0000(84)90081-3","volume":"28","author":"DS Johnson","year":"1984","unstructured":"Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167\u2013189 (1984)","journal-title":"J. Comput. Syst. Sci."},{"key":"676_CR65","doi-asserted-by":"crossref","unstructured":"Kambayashi, Y., Yoshikawa, M.: Query processing utilizing dependencies and horizontal decomposition. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 55\u201367 (1983)","DOI":"10.1145\/971695.582205"},{"key":"676_CR66","doi-asserted-by":"crossref","unstructured":"Kemper, A., Neumann, T.: HyPer: a hybrid OLTP&OLAP main memory database system based on virtual memory snapshots. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 195\u2013206 (2011)","DOI":"10.1109\/ICDE.2011.5767867"},{"issue":"3","key":"676_CR67","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1145\/319732.319745","volume":"7","author":"W Kim","year":"1982","unstructured":"Kim, W.: On optimizing an SQL-like nested query. ACM Trans. Datab. Syst. 7(3), 443\u2013469 (1982)","journal-title":"ACM Trans. Datab. Syst."},{"issue":"1","key":"676_CR68","first-page":"1222","volume":"2","author":"H Kimura","year":"2009","unstructured":"Kimura, H., et al.: Correlation maps: a compressed access method for exploiting soft functional dependencies. PVLDB 2(1), 1222\u20131233 (2009)","journal-title":"PVLDB"},{"key":"676_CR69","doi-asserted-by":"crossref","unstructured":"King, J.J.: Modelling concepts for reasoning about access to knowledge. In: Proceedings of the Workshop on Data Abstraction, Databases and Conceptual Modelling, pp. 138\u2013140 (1980)","DOI":"10.1145\/960128.806901"},{"key":"676_CR70","doi-asserted-by":"crossref","unstructured":"Klaebe, S., Baumann, S., Sattler, K.-U.: PatchIndex - exploiting approximate constraints in self-managing databases. In: Proceedings of the International Conference on Data Engineering (ICDE) Workshops, pp. 139\u2013146 (2020)","DOI":"10.1109\/ICDEW49219.2020.00014"},{"key":"676_CR71","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, H., Link, S.: SQL schema design: foundations, normal forms, and normalization. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 267\u2013279 (2016)","DOI":"10.1145\/2882903.2915239"},{"issue":"11","key":"676_CR72","first-page":"1118","volume":"8","author":"H K\u00f6hler","year":"2015","unstructured":"K\u00f6hler, H., Link, S., Zhou, X.: Possible and certain SQL keys. PVLDB 8(11), 1118\u20131129 (2015)","journal-title":"PVLDB"},{"key":"676_CR73","unstructured":"Kruse, S., Papenbrock, T., Naumann, F.: Scaling out the discovery of inclusion dependencies. In: Proceedings of the Conference Datenbanksysteme in Business, Technologie und Web Technik (BTW), pp. 445\u2013454 (2015)"},{"key":"676_CR74","unstructured":"Larson, P.-A., Galindo-Legaria, C.A.: Partial pre-aggregation in relational database queries. US Patent 7,593,926 (2009)"},{"issue":"3","key":"676_CR75","first-page":"204","volume":"9","author":"V Leis","year":"2015","unstructured":"Leis, V., et al.: How good are query optimizers, really? PVLDB 9(3), 204\u2013215 (2015)","journal-title":"PVLDB"},{"issue":"5","key":"676_CR76","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/s00778-017-0480-7","volume":"27","author":"V Leis","year":"2018","unstructured":"Leis, V., et al.: Query optimization through the looking glass, and what we found running the Join Order Benchmark. VLDB J. 27(5), 643\u2013668 (2018)","journal-title":"VLDB J."},{"issue":"2","key":"676_CR77","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1109\/TKDE.2010.197","volume":"24","author":"J Liu","year":"2012","unstructured":"Liu, J., et al.: Discover dependencies from data: a review. IEEE Trans. Knowl. Data Eng. 24(2), 251\u2013264 (2012)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2","key":"676_CR78","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(78)90009-0","volume":"17","author":"CL Lucchesi","year":"1978","unstructured":"Lucchesi, C.L., Osborn, S.L.: Candidate keys for relations. J. Comput. Syst. Sci. 17(2), 270\u2013279 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"676_CR79","volume-title":"Encyclopedia of Database Systems","author":"S Manegold","year":"2018","unstructured":"Manegold, S.: Cost estimation. In: Liu, L., \u00d6zsu, M.T. (eds.) Encyclopedia of Database Systems, 2nd edn. Springer, Berlin (2018)","edition":"2"},{"key":"676_CR80","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/s10844-007-0048-x","volume":"32","author":"DF Marchi","year":"2009","unstructured":"Marchi, D.F., Lopes, S., Petit, J.-M.: Unary and n-ary inclusion dependency discovery in relational databases. J. Intell. Inf. Syst. 32, 53\u201373 (2009)","journal-title":"J. Intell. Inf. Syst."},{"issue":"3","key":"676_CR81","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/s00778-013-0333-y","volume":"23","author":"M Meier","year":"2014","unstructured":"Meier, M.: The backchase revisited. VLDB J. 23(3), 495\u2013516 (2014)","journal-title":"VLDB J."},{"key":"676_CR82","unstructured":"Memarzia, P., Ray, S., Bhavsar, V.C.: A six-dimensional analysis of in-memory aggregation. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 289\u2013300 (2019)"},{"key":"676_CR83","unstructured":"Microsoft: Foreign key constraints (without NOCHECK) boost performance and data integrity (2004). https:\/\/web.archive.org\/web\/20101219111457\/http:\/\/www.microsoft.com\/technet\/abouttn\/flash\/tips\/tips_122104.mspx (visited on 04\/28\/2020)"},{"key":"676_CR84","unstructured":"Microsoft: Optimizing queries that access correlated datetime columns (2008). https:\/\/docs.microsoft.com\/en- us\/previous-versions\/sql\/sql-server-2005\/ms177416(v=sql.90)?redirectedfrom=MSDN (visited on 04\/30\/2020)"},{"key":"676_CR85","doi-asserted-by":"crossref","unstructured":"M\u00fcller, I. et al.: Cache-efficient aggregation: hashing is sorting. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 1123\u20131136 (2015)","DOI":"10.1145\/2723372.2747644"},{"issue":"5","key":"676_CR86","doi-asserted-by":"publisher","first-page":"558","DOI":"10.1109\/32.52778","volume":"16","author":"JK Mullin","year":"1990","unstructured":"Mullin, J.K.: Optimal semijoins for distributed database systems. ACM Trans. Softw. Eng. 16(5), 558\u2013560 (1990)","journal-title":"ACM Trans. Softw. Eng."},{"key":"676_CR87","unstructured":"MySQL: MySQL 8.0 reference manual\u2014optimizing IN and EXISTS subquery predicates with semijoin transformations (2020). https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/semijoins.html (visited on 05\/07\/2020)"},{"key":"676_CR88","unstructured":"MySQL: MySQL 8.0 reference manual\u2014SELECT statement (2020). https:\/\/dev.mysql.com\/doc\/refman\/8.0\/en\/select.html (visited on 11\/23\/2020)"},{"key":"676_CR89","doi-asserted-by":"crossref","unstructured":"Nambiar, U., Kambhampati, S.: Mining approximate functional dependencies and concept similarities to answer imprecise queries. In: Proceedings of the ACM Workshop on the Web and Databases (WebDB), pp. 73\u201378 (2004)","DOI":"10.1145\/1017074.1017093"},{"issue":"4","key":"676_CR90","doi-asserted-by":"publisher","first-page":"680","DOI":"10.1145\/1994.2209","volume":"9","author":"SB Navathe","year":"1984","unstructured":"Navathe, S.B., et al.: Vertical partitioning algorithms for database design. ACM Trans. Datab. Syst. 9(4), 680\u2013710 (1984)","journal-title":"ACM Trans. Datab. Syst."},{"issue":"13","key":"676_CR91","first-page":"1734","volume":"7","author":"T Neumann","year":"2014","unstructured":"Neumann, T.: Engineering high-performance database engines. PVLDB 7(13), 1734\u20131741 (2014)","journal-title":"PVLDB"},{"key":"676_CR92","unstructured":"Neumann, T., Kemper, A.: Unnesting arbitrary queries. In: Proceedings of the Conference Datenbanksysteme in Business, Technologie und Web Technik (BTW), pp. 383\u2013402 (2015)"},{"key":"676_CR93","unstructured":"O\u2019Neil, P.E.: Database Principles, Programming, Performance. Morgan Kaufmann, Burlington (1994)"},{"key":"676_CR94","unstructured":"Oracle: Scalar subquery expressions (2019). https:\/\/docs.oracle.com\/en\/database\/oracle\/oracle-database\/19\/sqlrf\/Scalar-Subquery-Expressions.html (visited on 09\/06\/2019)"},{"key":"676_CR95","doi-asserted-by":"crossref","unstructured":"Papenbrock, T., Naumann, F.: A hybrid approach to functional dependency discovery. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 821\u2013833 (2016)","DOI":"10.1145\/2882903.2915203"},{"key":"676_CR96","unstructured":"Papenbrock, T., Naumann, F.: Data-driven schema normalization. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 342\u2013353 (2017)"},{"issue":"7","key":"676_CR97","first-page":"774","volume":"8","author":"T Papenbrock","year":"2015","unstructured":"Papenbrock, T., et al.: Divide and conquer-based inclusion dependency discovery. PVLDB 8(7), 774\u2013785 (2015)","journal-title":"PVLDB"},{"issue":"10","key":"676_CR98","first-page":"1082","volume":"8","author":"T Papenbrock","year":"2015","unstructured":"Papenbrock, T., et al.: Functional dependency discovery: an experimental evaluation of seven algorithms. PVLDB 8(10), 1082\u20131093 (2015)","journal-title":"PVLDB"},{"key":"676_CR99","unstructured":"Paulley, G.N., Larson, P.: Exploiting uniqueness in query optimization. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 68\u201379 (1994)"},{"key":"676_CR100","unstructured":"Paulley, G.N.: Exploiting Functional Dependence in Query Optimization. AAINQ51220. Ph.D Thesis. Waterloo, ON, Canada (2000)"},{"key":"676_CR101","doi-asserted-by":"crossref","unstructured":"Pirahesh, H., Hellerstein, J.M., Hasan, W.: Extensible\/rule based query rewrite optimization in starburst. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 39\u201348 (1992)","DOI":"10.1145\/141484.130294"},{"key":"676_CR102","volume-title":"Encyclopedia of Database Systems","author":"E Pitoura","year":"2018","unstructured":"Pitoura, E.: Query rewriting. In: Liu, L., \u00d6zsu, M.T. (eds.) Encyclopedia of Database Systems, 2nd edn. Springer, Berlin (2018)","edition":"2"},{"key":"676_CR103","doi-asserted-by":"crossref","unstructured":"Popa, L. et al.: A chase too far? In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 273\u2013284 (2000)","DOI":"10.1145\/335191.335421"},{"issue":"2","key":"676_CR104","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1093\/comjnl\/39.2.124","volume":"39","author":"H Saiedian","year":"1996","unstructured":"Saiedian, H., Spencer, T.: An efficient algorithm to compute the candidate keys of a relational database schema. Comput. J. 39(2), 124\u2013132 (1996)","journal-title":"Comput. J."},{"key":"676_CR105","unstructured":"SAP: Expressions\u2014Subqueries in Expressions (2019). https:\/\/help.sap.com\/viewer\/4fe29514fd584807ac9f2a04f6754767\/2.0.04\/en-US\/20a4389775191014b5a6bf2ccc0df2ed.html (visited on 04\/28\/2020)"},{"key":"676_CR106","unstructured":"Schiefer, B., Strain, L.G., Yan, W.P.: Method for estimating cardinalities for query processing in a relational database management system. US Patent 5,761,653 (1998)"},{"key":"676_CR107","unstructured":"Schirmer, P., et al.: DynFD: functional dependency discovery in dynamic datasets. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 253\u2013264 (2019)"},{"key":"676_CR108","doi-asserted-by":"crossref","unstructured":"Selinger, P.G., et al.: Access path selection in a relational database management system. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 23\u201334 (1979)","DOI":"10.1145\/582095.582099"},{"key":"676_CR109","doi-asserted-by":"crossref","unstructured":"Shaabani, N., Meinel, C.: Incremental discovery of inclusion dependencies. In: Proceedings of the International Conference on Scientific and Statistical Database Management (SSDBM), pp. 2:1\u20132:12. ACM (2017)","DOI":"10.1145\/3085504.3085506"},{"key":"676_CR110","doi-asserted-by":"crossref","unstructured":"Simmen, D.E., Shekita, E.J., Malkemus, T.: Fundamental techniques for order optimization. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 57\u201367 (1996)","DOI":"10.1145\/235968.233320"},{"key":"676_CR111","unstructured":"Stocker, K., et al.: Integrating semi-join-reducers into state of the art query processors. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 575\u2013584 (2001)"},{"key":"676_CR112","doi-asserted-by":"crossref","unstructured":"Stonebraker, M.: Implementation of integrity constraints and views by query modification. In: Proceedings of the International Conference on Management of Data (SIGMOD), pp. 65\u201378 (1975)","DOI":"10.1145\/500080.500091"},{"key":"676_CR113","unstructured":"Szlichta, J., Godfrey, P., Gryz, J.: Chasing polarized order dependencies. In: Proceedings of the Alberto Mendelzon International Workshop on Foundations of Data Management, pp. 168\u2013179 (2012)"},{"issue":"11","key":"676_CR114","first-page":"1220","volume":"5","author":"J Szlichta","year":"2012","unstructured":"Szlichta, J., Godfrey, P., Gryz, J.: Fundamentals of order dependencies. PVLDB 5(11), 1220\u20131231 (2012)","journal-title":"PVLDB"},{"key":"676_CR115","unstructured":"Szlichta, J., et al.: Business-intelligence queries with order dependencies in DB2. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 750\u2013761 (2014)"},{"issue":"7","key":"676_CR116","first-page":"721","volume":"10","author":"J Szlichta","year":"2017","unstructured":"Szlichta, J., et al.: Effective and complete discovery of order dependencies via set-based axiomatization. PVLDB 10(7), 721\u2013732 (2017)","journal-title":"PVLDB"},{"key":"676_CR117","doi-asserted-by":"crossref","unstructured":"Szlichta, J., et al.: Queries on dates: fast yet not blind. In: Proceedings of the International Conference on Extending Database Technology (EDBT), pp. 497\u2013502 (2011)","DOI":"10.1145\/1951365.1951424"},{"issue":"10","key":"676_CR118","first-page":"1669","volume":"13","author":"Z Tan","year":"2020","unstructured":"Tan, Z., et al.: Fast incremental discovery of pointwise order dependencies. PVLDB 13(10), 1669\u20131681 (2020)","journal-title":"PVLDB"},{"key":"676_CR119","unstructured":"The PostgreSQL Global Development Group: PostgreSQL: Documentation: 13: 70.1. Row estimation examples (2020). https:\/\/www.postgresql.org\/docs\/13\/row-estimation-examples.html (visited on 10\/30\/2020)"},{"key":"676_CR120","doi-asserted-by":"crossref","unstructured":"Wang, S.-L., et al.: Maintenance of discovered functional dependencies: incremental deletion. In: Intelligent Systems Design and Applications, pp. 579\u2013588. Springer, Heidelberg (2003)","DOI":"10.1007\/978-3-540-44999-7_55"},{"issue":"1","key":"676_CR121","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/128765.128767","volume":"17","author":"GE Weddell","year":"1992","unstructured":"Weddell, G.E.: Reasoning about functional dependencies generalized for semantic data models. ACM Trans. Database Syst. 17(1), 32\u201364 (1992)","journal-title":"ACM Trans. Database Syst."},{"key":"676_CR122","doi-asserted-by":"crossref","unstructured":"Wei, Z., Leck, U., Link, S.: Entity integrity, referential integrity, and query optimization with embedded uniqueness constraints. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 1694\u20131697 (2019)","DOI":"10.1109\/ICDE.2019.00175"},{"issue":"11","key":"676_CR123","first-page":"1458","volume":"12","author":"Z Wei","year":"2019","unstructured":"Wei, Z., Link, S.: Embedded functional dependencies and data-completeness tailored database design. PVLDB 12(11), 1458\u20131470 (2019)","journal-title":"PVLDB"},{"key":"676_CR124","unstructured":"Yan, W.P.: Query Optimization Techniques for Aggregation Queries\u2019. Ph.D Thesis, Department of Computer Science, University of Waterloo (1995)"},{"key":"676_CR125","unstructured":"Yan, W.P., Larson, P.: Eager aggregation and lazy aggregation. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 345\u2013357 (1995)"},{"key":"676_CR126","unstructured":"Yan, W.P., Larson, P.: Performing group-by before join. In: Proceedings of the International Conference on Data Engineering (ICDE), pp. 89\u2013100 (1994)"},{"key":"676_CR127","unstructured":"Yang, H.Z., Larson, P.: Query transformation for PSJ-queries. In: Proceedings of the International Conference on Very Large Databases (VLDB), pp. 245\u2013254 (1987)"},{"issue":"3","key":"676_CR128","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1109\/69.87981","volume":"1","author":"CT Yu","year":"1989","unstructured":"Yu, C.T., Sun, W.: Automatic knowledge acquisition and maintenance for semantic query optimization. IEEE Trans. Knowl. Data Eng. 1(3), 362\u2013375 (1989)","journal-title":"IEEE Trans. Knowl. Data Eng."}],"updated-by":[{"DOI":"10.1007\/s00778-021-00710-4","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,12,28]],"date-time":"2021-12-28T00:00:00Z","timestamp":1640649600000}}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00676-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-021-00676-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-021-00676-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T00:09:47Z","timestamp":1675469387000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-021-00676-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,14]]},"references-count":128,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["676"],"URL":"https:\/\/doi.org\/10.1007\/s00778-021-00676-3","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s00778-021-00710-4","asserted-by":"object"}]},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,14]]},"assertion":[{"value":"7 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 June 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 December 2021","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00778-021-00710-4","URL":"https:\/\/doi.org\/10.1007\/s00778-021-00710-4","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}