{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T01:39:32Z","timestamp":1742953172917,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662623855"},{"type":"electronic","value":"9783662623862"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-662-62386-2_6","type":"book-chapter","created":{"date-parts":[[2020,11,20]],"date-time":"2020-11-20T00:30:00Z","timestamp":1605832200000},"page":"154-188","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Selectivity Estimation with Attribute Value Dependencies Using Linked Bayesian Networks"],"prefix":"10.1007","author":[{"given":"Max","family":"Halford","sequence":"first","affiliation":[]},{"given":"Philippe","family":"Saint-Pierre","sequence":"additional","affiliation":[]},{"given":"Franck","family":"Morvan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,20]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Acharya, S., Gibbons, P.B., Poosala, V., Ramaswamy, S.: Join synopses for approximate query answering. In: ACM SIGMOD Record, vol. 28, pp. 275\u2013286. ACM (1999)","key":"6_CR1","DOI":"10.1145\/304181.304207"},{"doi-asserted-by":"crossref","unstructured":"Akdere, M., \u00c7etintemel, U., Riondato, M., Upfal, E., Zdonik, S.B.: Learning-based query performance modeling and prediction. In: IEEE 28th International Conference on Data Engineering (ICDE), pp. 390\u2013401. IEEE (2012)","key":"6_CR2","DOI":"10.1109\/ICDE.2012.64"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.artint.2015.03.003","volume":"244","author":"M Bartlett","year":"2017","unstructured":"Bartlett, M., Cussens, J.: Integer linear programming for the Bayesian network structure learning problem. Artif. Intell. 244, 258\u2013271 (2017)","journal-title":"Artif. Intell."},{"doi-asserted-by":"crossref","unstructured":"Blohsfeld, B., Korus, D., Seeger, B.: A comparison of selectivity estimators for range queries on metric attributes. In: ACM SIGMOD Record, vol. 28, pp. 239\u2013250. ACM (1999)","key":"6_CR4","DOI":"10.1145\/304181.304203"},{"doi-asserted-by":"crossref","unstructured":"Bruno, N., Chaudhuri, S., Gravano, L.: STHoles: a multidimensional workload-aware histogram. In: ACM SIGMOD Record, vol. 30, pp. 211\u2013222. ACM (2001)","key":"6_CR5","DOI":"10.1145\/376284.375686"},{"doi-asserted-by":"crossref","unstructured":"Chaudhuri, S.: An overview of query optimization in relational systems. In: Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pp. 34\u201343. ACM (1998)","key":"6_CR6","DOI":"10.1145\/275487.275492"},{"doi-asserted-by":"crossref","unstructured":"Chaudhuri, S., Motwani, R., Narasayya, V.: On random sampling over joins. In: ACM SIGMOD Record, vol. 28, pp. 263\u2013274. ACM (1999)","key":"6_CR7","DOI":"10.1145\/304181.304206"},{"issue":"1","key":"6_CR8","doi-asserted-by":"publisher","first-page":"994","DOI":"10.14778\/1687627.1687739","volume":"2","author":"S Chaudhuri","year":"2009","unstructured":"Chaudhuri, S., Narasayya, V., Ramamurthy, R.: Exact cardinality query optimization for optimizer testing. Proc. VLDB Endowment 2(1), 994\u20131005 (2009)","journal-title":"Proc. VLDB Endowment"},{"doi-asserted-by":"crossref","unstructured":"Chen, C.M., Roussopoulos, N.: Adaptive selectivity estimation using query feedback, vol. 23. ACM (1994)","key":"6_CR9","DOI":"10.1145\/191843.191874"},{"doi-asserted-by":"crossref","unstructured":"Chen, Y., Yi, K.: Two-level sampling for join size estimation. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 759\u2013774. ACM (2017)","key":"6_CR10","DOI":"10.1145\/3035918.3035921"},{"issue":"3","key":"6_CR11","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1109\/TIT.1968.1054142","volume":"14","author":"C Chow","year":"1968","unstructured":"Chow, C., Liu, C.: Approximating discrete probability distributions with dependence trees. IEEE Trans. Inf. Theory 14(3), 462\u2013467 (1968)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2\u20133","key":"6_CR12","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1016\/0004-3702(90)90060-D","volume":"42","author":"GF Cooper","year":"1990","unstructured":"Cooper, G.F.: The computational complexity of probabilistic inference using Bayesian belief networks. Artif. Intell. 42(2\u20133), 393\u2013405 (1990)","journal-title":"Artif. Intell."},{"key":"6_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/b97670","volume-title":"Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks","author":"RG Cowell","year":"2006","unstructured":"Cowell, R.G., Dawid, P., Lauritzen, S.L., Spiegelhalter, D.J.: Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks. Springer, New York (2006). https:\/\/doi.org\/10.1007\/b97670"},{"issue":"2","key":"6_CR14","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1145\/376284.375685","volume":"30","author":"A Deshpande","year":"2001","unstructured":"Deshpande, A., Garofalakis, M., Rastogi, R.: Independence is good: dependency-based histogram synopses for high-dimensional data. ACM SIGMOD Record 30(2), 199\u2013210 (2001)","journal-title":"ACM SIGMOD Record"},{"issue":"9","key":"6_CR15","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.14778\/3329772.3329780","volume":"12","author":"A Dutt","year":"2019","unstructured":"Dutt, A., Wang, C., Nazi, A., Kandula, S., Narasayya, V., Chaudhuri, S.: Selectivity estimation for range predicates using lightweight models. Proc. VLDB Endowment 12(9), 1044\u20131057 (2019)","journal-title":"Proc. VLDB Endowment"},{"doi-asserted-by":"crossref","unstructured":"Getoor, L., Taskar, B., Koller, D.: Selectivity estimation using probabilistic models. In: ACM SIGMOD Record, vol. 30, pp. 461\u2013472. ACM (2001)","key":"6_CR16","DOI":"10.1145\/376284.375727"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-030-18579-4_1","volume-title":"Database Systems for Advanced Applications","author":"M Halford","year":"2019","unstructured":"Halford, M., Saint-Pierre, P., Morvan, F.: An approach based on Bayesian networks for query selectivity estimation. In: Li, G., Yang, J., Gama, J., Natwichai, J., Tong, Y. (eds.) DASFAA 2019. LNCS, vol. 11447, pp. 3\u201319. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-18579-4_1"},{"doi-asserted-by":"crossref","unstructured":"Heimel, M., Kiefer, M., Markl, V.: Self-tuning, GPU-accelerated kernel density models for multidimensional selectivity estimation. In: Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pp. 1477\u20131492. ACM (2015)","key":"6_CR18","DOI":"10.1145\/2723372.2749438"},{"key":"6_CR19","volume-title":"The Steiner Tree Problem","author":"FK Hwang","year":"1992","unstructured":"Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem, vol. 53. Elsevier, North-Holland (1992)"},{"doi-asserted-by":"crossref","unstructured":"Ioannidis, Y.: The history of histograms (abridged). In: Proceedings 2003 VLDB Conference, pp. 19\u201330. Elsevier (2003)","key":"6_CR20","DOI":"10.1016\/B978-012722442-8\/50011-2"},{"issue":"1","key":"6_CR21","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. (CSUR) 28(1), 121\u2013123 (1996)","journal-title":"ACM Comput. Surv. (CSUR)"},{"doi-asserted-by":"crossref","unstructured":"Ioannidis, Y.E., Christodoulakis, S.: On the propagation of errors in the size of join results, vol. 20. ACM (1991)","key":"6_CR22","DOI":"10.1145\/119995.115835"},{"unstructured":"Ivanov, O., Bartunov, S.: Adaptive cardinality estimation. arXiv preprint arXiv:1711.08330 (2017)","key":"6_CR23"},{"key":"6_CR24","volume-title":"An Introduction to Bayesian Networks","author":"FV Jensen","year":"1996","unstructured":"Jensen, F.V., et al.: An Introduction to Bayesian Networks, vol. 210. UCL press, London (1996)"},{"unstructured":"Kipf, A., Kipf, T., Radke, B., Leis, V., Boncz, P., Kemper, A.: Learned cardinalities: estimating correlated joins with deep learning. arXiv preprint arXiv:1809.00677 (2018)","key":"6_CR25"},{"doi-asserted-by":"crossref","unstructured":"Kipf, A., et al.: Estimating cardinalities with deep sketches. In: Proceedings of the 2019 International Conference on Management of Data, pp. 1937\u20131940 (2019)","key":"6_CR26","DOI":"10.1145\/3299869.3320218"},{"unstructured":"Kooi, R.P.: The optimization of queries in relational databases (1981)","key":"6_CR27"},{"issue":"1","key":"6_CR28","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1090\/S0002-9939-1956-0078686-7","volume":"7","author":"JB Kruskal","year":"1956","unstructured":"Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7(1), 48\u201350 (1956)","journal-title":"Proc. Am. Math. Soc."},{"issue":"2","key":"6_CR29","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2001","unstructured":"Kschischang, F.R., Frey, B.J., Loeliger, H.A., et al.: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47(2), 498\u2013519 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"6_CR30","doi-asserted-by":"publisher","first-page":"204","DOI":"10.14778\/2850583.2850594","volume":"9","author":"V Leis","year":"2015","unstructured":"Leis, V., Gubichev, A., Mirchev, A., Boncz, P., Kemper, A., Neumann, T.: How good are query optimizers, really? Proc. VLDB Endowment 9(3), 204\u2013215 (2015)","journal-title":"Proc. VLDB Endowment"},{"key":"6_CR31","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, 643\u2013668 (2018)","journal-title":"VLDB J."},{"unstructured":"Leis, V., Radke, B., Gubichev, A., Kemper, A., Neumann, T.: Cardinality estimation done right: index-based join sampling. In: CIDR (2017)","key":"6_CR32"},{"unstructured":"Liu, H., Xu, M., Yu, Z., Corvinelli, V., Zuzarte, C.: Cardinality estimation using neural networks. In: Proceedings of the 25th Annual International Conference on Computer Science and Software Engineering, pp. 53\u201359. IBM Corp. (2015)","key":"6_CR33"},{"issue":"1","key":"6_CR34","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/s00778-006-0030-1","volume":"16","author":"V Markl","year":"2007","unstructured":"Markl, V., Haas, P.J., Kutsch, M., Megiddo, N., Srivastava, U., Tran, T.M.: Consistent selectivity estimation via maximum entropy. VLDB J. 16(1), 55\u201376 (2007)","journal-title":"VLDB J."},{"doi-asserted-by":"crossref","unstructured":"Matias, Y., Vitter, J.S., Wang, M.: Wavelet-based histograms for selectivity estimation. In: ACM SIGMOD Record, vol. 27, pp. 448\u2013459. ACM (1998)","key":"6_CR35","DOI":"10.1145\/276305.276344"},{"issue":"1","key":"6_CR36","doi-asserted-by":"publisher","first-page":"982","DOI":"10.14778\/1687627.1687738","volume":"2","author":"G Moerkotte","year":"2009","unstructured":"Moerkotte, G., Neumann, T., Steidl, G.: Preventing bad plans by bounding the impact of cardinality estimation errors. Proc. VLDB Endowment 2(1), 982\u2013993 (2009)","journal-title":"Proc. VLDB Endowment"},{"issue":"9","key":"6_CR37","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.14778\/3213880.3213882","volume":"11","author":"M M\u00fcller","year":"2018","unstructured":"M\u00fcller, M., Moerkotte, G., Kolb, O.: Improved selectivity estimation by combining knowledge from sampling and synopses. Proc. VLDB Endowment 11(9), 1016\u20131028 (2018)","journal-title":"Proc. VLDB Endowment"},{"doi-asserted-by":"crossref","unstructured":"Muralikrishna, M., DeWitt, D.J.: Equi-depth multidimensional histograms. In: ACM SIGMOD Record, vol. 17, pp. 28\u201336. ACM (1988)","key":"6_CR38","DOI":"10.1145\/971701.50205"},{"unstructured":"Olken, F., Rotem, D.: Simple random sampling from relational databases (1986)","key":"6_CR39"},{"doi-asserted-by":"crossref","unstructured":"Poess, M., Smith, B., Kollar, L., Larson, P.: TPC-DS, taking decision support benchmarking to the next level. In: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 582\u2013587 (2002)","key":"6_CR40","DOI":"10.1145\/564691.564759"},{"doi-asserted-by":"crossref","unstructured":"Poosala, V., Haas, P.J., Ioannidis, Y.E., Shekita, E.J.: Improved histograms for selectivity estimation of range predicates. In: ACM SIGMOD Record, vol. 25, pp. 294\u2013305. ACM (1996)","key":"6_CR41","DOI":"10.1145\/235968.233342"},{"key":"6_CR42","first-page":"486","volume":"97","author":"V Poosala","year":"1997","unstructured":"Poosala, V., Ioannidis, Y.E.: Selectivity estimation without the attribute value independence assumption. VLDB 97, 486\u2013495 (1997)","journal-title":"VLDB"},{"doi-asserted-by":"crossref","unstructured":"Selinger, P.G., Astrahan, M.M., Chamberlin, D.D., Lorie, R.A., Price, T.G.: Access path selection in a relational database management system. In: Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, pp. 23\u201334. ACM (1979)","key":"6_CR43","DOI":"10.1145\/582095.582099"},{"key":"6_CR44","first-page":"19","volume":"1","author":"M Stillger","year":"2001","unstructured":"Stillger, M., Lohman, G.M., Markl, V., Kandil, M.: Leo-DB2\u2019s learning optimizer. VLDB 1, 19\u201328 (2001)","journal-title":"VLDB"},{"issue":"11","key":"6_CR45","doi-asserted-by":"publisher","first-page":"852","DOI":"10.14778\/3402707.3402724","volume":"4","author":"K Tzoumas","year":"2011","unstructured":"Tzoumas, K., Deshpande, A., Jensen, C.S.: Lightweight graphical models for selectivity estimation without independence assumptions. Proc. VLDB Endowment 4(11), 852\u2013863 (2011)","journal-title":"Proc. VLDB Endowment"},{"doi-asserted-by":"crossref","unstructured":"Van Aken, D., Pavlo, A., Gordon, G.J., Zhang, B.: Automatic database management system tuning through large-scale machine learning. In: Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1009\u20131024. ACM (2017)","key":"6_CR46","DOI":"10.1145\/3035918.3064029"},{"issue":"12","key":"6_CR47","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.14778\/2824032.2824051","volume":"8","author":"D Vengerov","year":"2015","unstructured":"Vengerov, D., Menck, A.C., Zait, M., Chakkappen, S.P.: Join size estimation subject to filter conditions. Proc. VLDB Endowment 8(12), 1530\u20131541 (2015)","journal-title":"Proc. VLDB Endowment"},{"unstructured":"Wu, W., Chi, Y., Zhu, S., Tatemura, J., Hacig\u00fcm\u00fcs, H., Naughton, J.F.: Predicting query execution time: are optimizer cost models really unusable? In: IEEE 29th International Conference on Data Engineering (ICDE), pp. 1081\u20131092. IEEE (2013)","key":"6_CR48"},{"key":"6_CR49","first-page":"2213","volume":"30","author":"S Yin","year":"2018","unstructured":"Yin, S., Hameurlain, A., Morvan, F.: SLA definition for multi-tenant DBMS and its impact on query optimization. IEEE Trans. Knowl. Data Eng. 30, 2213\u20132226 (2018)","journal-title":"IEEE Trans. Knowl. Data Eng."}],"container-title":["Lecture Notes in Computer Science","Transactions on Large-Scale Data- and Knowledge-Centered Systems XLVI"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-62386-2_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,20]],"date-time":"2020-11-20T00:37:02Z","timestamp":1605832622000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-62386-2_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783662623855","9783662623862"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-62386-2_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"20 November 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}