{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T16:10:55Z","timestamp":1746115855652,"version":"3.40.4"},"publisher-location":"Cham","reference-count":38,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031911170"},{"type":"electronic","value":"9783031911187"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,5,1]],"date-time":"2025-05-01T00:00:00Z","timestamp":1746057600000},"content-version":"vor","delay-in-days":120,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Charts, figures, and text derived from data play an important role in decision making. But making sense of\u00a0or fact-checking outputs means understanding how they relate to the underlying data. Even for experts with access to the source code and data sets, this poses a significant challenge. We introduce a new program analysis framework (A supporting artifact is available at <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"https:\/\/zenodo.org\/records\/14637654\" ext-link-type=\"uri\">https:\/\/zenodo.org\/records\/14637654<\/jats:ext-link> [5].) which supports interactive exploration of fine-grained IO relationships directly through computed outputs, using dynamic dependence graphs. This framework enables a novel notion in data provenance which\u00a0we call <jats:italic>linked inputs<\/jats:italic>, a relation of mutual relevance or cognacy which arises between inputs\u00a0that contribute to common features of the output. We give a procedure for computing linked inputs over a dependence graph, and show how the presented in this paper is faster on most examples than an implementation based\u00a0on execution traces.<\/jats:p>","DOI":"10.1007\/978-3-031-91118-7_6","type":"book-chapter","created":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:17:40Z","timestamp":1746001060000},"page":"144-171","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Cognacy Queries over Dependence Graphs for Transparent Visualisations"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-5995-6994","authenticated-orcid":false,"given":"Joe","family":"Bond","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9106-934X","authenticated-orcid":false,"given":"Cristina","family":"David","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3845-9928","authenticated-orcid":false,"given":"Minh","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7058-7842","authenticated-orcid":false,"given":"Dominic","family":"Orchard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9249-9862","authenticated-orcid":false,"given":"Roly","family":"Perera","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,5,1]]},"reference":[{"key":"6_CR1","doi-asserted-by":"publisher","unstructured":"Acar, U.A., Blelloch, G.E., Harper, R.: Adaptive functional programming. In: POPL \u201902: Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. pp. 247\u2013259. ACM Press, New York, NY, USA (2002). https:\/\/doi.org\/10.1145\/503272.503296","DOI":"10.1145\/503272.503296"},{"key":"6_CR2","doi-asserted-by":"publisher","unstructured":"Agrawal, H., Horgan, J.R.: Dynamic program slicing. In: PLDI \u201990: Proceedings of the ACM SIGPLAN 1990 Conference on Programming Language Design and Implementation. pp. 246\u2013256. ACM, New York, NY, USA (1990). https:\/\/doi.org\/10.1145\/93542.93576","DOI":"10.1145\/93542.93576"},{"key":"6_CR3","doi-asserted-by":"publisher","unstructured":"Beaumont, C., Robitaille, T., Goodman, A., Borkin, M.: Multidimensional data exploration with glue. In: van\u00a0der Walt, S., Millman, J., Huff, K. (eds.) Proceedings of the 12th Python in Science Conference. pp. 8 \u2013 12 (2013). https:\/\/doi.org\/10.25080\/Majora-8b375195-002","DOI":"10.25080\/Majora-8b375195-002"},{"key":"6_CR4","doi-asserted-by":"publisher","unstructured":"Becker, R.A., Cleveland, W.S.: Brushing scatterplots. Technometrics 29(2), 127\u2013142 (May 1987). https:\/\/doi.org\/10.1080\/00401706.1987.10488204","DOI":"10.1080\/00401706.1987.10488204"},{"key":"6_CR5","unstructured":"Bond, J., David, C., Nguyen, M., Orchard, M., Perera, R.: Fluid. https:\/\/zenodo.org\/records\/14637654 (2025)"},{"key":"6_CR6","unstructured":"Bremer, N., Ranzijn, M.: Urbanization in east asia between 2000 and 2010. http:\/\/nbremer.github.io\/urbanization\/ (2015)"},{"key":"6_CR7","doi-asserted-by":"publisher","unstructured":"Buja, A., McDonald, J.A., Michalak, J., Stuetzle, W.: Interactive data visualization using focusing and linking. In: Proceedings of Visualization \u201991. pp. 156\u2013163 (Oct 1991). https:\/\/doi.org\/10.1109\/VISUAL.1991.175794","DOI":"10.1109\/VISUAL.1991.175794"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Buneman, P., Khanna, S., Tan, W.C.: Why and where: A characterization of data provenance. In: Proceedings of the 8th International Conference on Database Theory. pp. 316\u2013330. ICDT \u201901, Springer-Verlag, London, UK (2001)","DOI":"10.1007\/3-540-44503-X_20"},{"key":"6_CR9","doi-asserted-by":"publisher","unstructured":"Callahan, S.P., Freire, J., Santos, E., Scheidegger, C.E., Silva, C.T., Vo, H.T.: VisTrails: Visualization meets data management. In: Proceedings of the ACM SIGMOD International Conference on Management of Data. pp. 745\u2013747 (2006). https:\/\/doi.org\/10.1145\/1142473.1142574","DOI":"10.1145\/1142473.1142574"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Cheney, J., Ahmed, A., Acar, U.A.: Provenance as dependency analysis. Mathematical Structures in Computer Science 21(6), 1301\u20131337 (2011)","DOI":"10.1017\/S0960129511000211"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Cooper, E., Lindley, S., Wadler, P., Yallop, J.: Links: web programming without tiers. In: Proceedings of the 5th International Conference on Formal methods for Components and Objects. pp. 266\u2013296. FMCO\u201906, Springer-Verlag, Berlin, Heidelberg (2007)","DOI":"10.1007\/978-3-540-74792-5_12"},{"key":"6_CR12","doi-asserted-by":"publisher","unstructured":"Davidson, S.B., Freire, J.: Provenance and scientific workflows: challenges and opportunities. In: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. pp. 1345\u20131350. SIGMOD \u201908, ACM, New York, NY, USA (2008). https:\/\/doi.org\/10.1145\/1376616.1376772","DOI":"10.1145\/1376616.1376772"},{"key":"6_CR13","doi-asserted-by":"publisher","unstructured":"DerSimonian, R., Laird, N.: Meta-analysis in clinical trials. Control Clin Trials 7(3), 177\u201388 (Sep 1986). https:\/\/doi.org\/10.1016\/0197-2456(86)90046-2","DOI":"10.1016\/0197-2456(86)90046-2"},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Dietrich, B., M\u00fcller, T., Grust, T.: Data provenance for recursive sql queries. In: Proceedings of the 14th International Workshop on the Theory and Practice of Provenance. TaPP \u201922, Association for Computing Machinery, New York, NY, USA (2022). https:\/\/doi.org\/10.1145\/3530800.3534536, https:\/\/doi.org\/10.1145\/3530800.3534536","DOI":"10.1145\/3530800.3534536"},{"key":"6_CR15","doi-asserted-by":"publisher","unstructured":"Dragicevic, P., Jansen, Y., Sarma, A., Kay, M., Chevalier, F.: Increasing the transparency of research papers with explorable multiverse analyses. In: CHI 2019 - The ACM CHI Conference on Human Factors in Computing Systems. Glasgow, United Kingdom (May 2019). https:\/\/doi.org\/10.1145\/3290605.3300295","DOI":"10.1145\/3290605.3300295"},{"key":"6_CR16","doi-asserted-by":"publisher","unstructured":"Fehrenbach, S., Cheney, J.: Language-integrated provenance by trace analysis. In: Proceedings of the 17th ACM SIGPLAN International Symposium on Database Programming Languages. p. 74\u201384. DBPL 2019, Association for Computing Machinery, New York, NY, USA (2019). https:\/\/doi.org\/10.1145\/3315507.3330198, https:\/\/doi.org\/10.1145\/3315507.3330198","DOI":"10.1145\/3315507.3330198"},{"key":"6_CR17","doi-asserted-by":"publisher","unstructured":"Ferrante, J., Ottenstein, K.J., Warren, J.D.: The program dependence graph and its use in optimization. ACM Trans. Program. Lang. Syst. 9(3), 319\u2013349 (jul 1987). https:\/\/doi.org\/10.1145\/24039.24041","DOI":"10.1145\/24039.24041"},{"key":"6_CR18","doi-asserted-by":"crossref","unstructured":"Field, J., Tip, F.: Dynamic dependence in term rewriting systems and its application to program slicing. Information and Software Technology 40(11\u201312), 609\u2013636 (November\/December 1998)","DOI":"10.1016\/S0950-5849(98)00087-1"},{"key":"6_CR19","doi-asserted-by":"publisher","unstructured":"Hammer, C., Grimme, M., Krinke, J.: Dynamic path conditions in dependence graphs. pp. 58\u201367 (01 2006). https:\/\/doi.org\/10.1145\/1111542.1111552","DOI":"10.1145\/1111542.1111552"},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Heer, J., Agrawala, M., Willett, W.: Generalized selection via interactive query relaxation. In: ACM Human Factors in Computing Systems (CHI). pp. 959\u2013968 (2008)","DOI":"10.1145\/1357054.1357203"},{"key":"6_CR21","doi-asserted-by":"publisher","unstructured":"Hinze, R.: Generalizing generalized tries. Journal of Functional Programming 10(4), 327\u2013351 (2000). https:\/\/doi.org\/10.1017\/S0956796800003713","DOI":"10.1017\/S0956796800003713"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Jonsson, B., Tarski, A.: Boolean algebras with operators. part i. American Journal of Mathematics 73(4), 891\u2013939 (1951), http:\/\/www.jstor.org\/stable\/2372123","DOI":"10.2307\/2372123"},{"key":"6_CR23","doi-asserted-by":"publisher","unstructured":"Livny, M., Ramakrishnan, R., Beyer, K., Chen, G., Donjerkovic, D., Lawande, S., Myllymaki, J., Wenger, K.: Devise: integrated querying and visual exploration of large datasets. SIGMOD Rec. 26(2), 301\u2013312 (jun 1997). https:\/\/doi.org\/10.1145\/253262.253335, https:\/\/doi.org\/10.1145\/253262.253335","DOI":"10.1145\/253262.253335"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Menni, M., Smith, C.: Modes of adjointness. Journal of Philosophical Logic 43(2\/3), 365\u2013391 (2014), http:\/\/www.jstor.org\/stable\/24564097","DOI":"10.1007\/s10992-012-9266-y"},{"key":"6_CR25","doi-asserted-by":"publisher","unstructured":"Murphy, J., Sexton, D., Barnett, D., Jones, G., Webb, M., Collins, M., Stainforth, D.: Quantification of modelling uncertainties in a large ensemble of climate change simulations. Nature 430, 768\u201372 (09 2004). https:\/\/doi.org\/10.1038\/nature02771","DOI":"10.1038\/nature02771"},{"key":"6_CR26","unstructured":"Nielsen, J.: Usability Engineering. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1994)"},{"key":"6_CR27","doi-asserted-by":"publisher","unstructured":"North, C., Shneiderman, B.: Snap-together visualization: a user interface for coordinating visualizations via relational schemata. In: Proceedings of the Working Conference on Advanced Visual Interfaces. p. 128\u2013135. AVI \u201900, Association for Computing Machinery, New York, NY, USA (2000). https:\/\/doi.org\/10.1145\/345513.345282","DOI":"10.1145\/345513.345282"},{"key":"6_CR28","doi-asserted-by":"publisher","unstructured":"Perera, R., Acar, U.A., Cheney, J., Levy, P.B.: Functional programs that explain their work. In: Proceedings of the 17th ACM SIGPLAN International Conference on Functional Programming. pp. 365\u2013376. ICFP \u201912, ACM, New York, NY, USA (2012). https:\/\/doi.org\/10.1002\/jgt.3190130202","DOI":"10.1002\/jgt.3190130202"},{"key":"6_CR29","doi-asserted-by":"publisher","unstructured":"Perera, R., Garg, D., Cheney, J.: Causally consistent dynamic slicing. In: Desharnais, J., Jagadeesan, R. (eds.) Concurrency Theory, 27th International Conference, CONCUR \u201916. Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2016). https:\/\/doi.org\/10.4230\/LIPIcs.CONCUR.2016.18","DOI":"10.4230\/LIPIcs.CONCUR.2016.18"},{"key":"6_CR30","doi-asserted-by":"publisher","unstructured":"Perera, R., Nguyen, M., Petricek, T., Wang, M.: Linked visualisations via galois dependencies. Proc. ACM Program. Lang. 6(POPL) (2022). https:\/\/doi.org\/10.1145\/3498668","DOI":"10.1145\/3498668"},{"key":"6_CR31","unstructured":"Peyton\u00a0Jones, S., Eisenberg, R., Graf, S.: Triemaps that match. Tech. rep. (July 2022), https:\/\/simon.peytonjones.org\/triemaps-that-match\/"},{"key":"6_CR32","doi-asserted-by":"publisher","unstructured":"Psallidas, F., Wu, E.: Smoke: fine-grained lineage at interactive speed. Proc. VLDB Endow. 11(6), 719\u2013732 (feb 2018). https:\/\/doi.org\/10.14778\/3199517.3199522, https:\/\/doi.org\/10.14778\/3199517.3199522","DOI":"10.14778\/3199517.3199522"},{"key":"6_CR33","doi-asserted-by":"publisher","unstructured":"Ricciotti, W., Stolarek, J., Perera, R., Cheney, J.: Imperative functional programs that explain their work. Proceedings of the ACM on Programming Languages 1(ICFP), 14:1\u201314:28 (2017). https:\/\/doi.org\/10.1145\/3110258","DOI":"10.1145\/3110258"},{"key":"6_CR34","doi-asserted-by":"publisher","unstructured":"Roberts, J.C., Wright, M.A.E.: Towards ubiquitous brushing for information visualization. In: Tenth International Conference on Information Visualisation (IV\u201906). pp. 151\u2013156 (July 2006). https:\/\/doi.org\/10.1109\/IV.2006.113","DOI":"10.1109\/IV.2006.113"},{"key":"6_CR35","doi-asserted-by":"crossref","unstructured":"Satyanarayan, A., Moritz, D., Wongsuphasawat, K., Heer, J.: Vega-Lite: A grammar of interactive graphics. IEEE Trans. Visualization & Comp. Graphics (Proc. InfoVis) (2017)","DOI":"10.31219\/osf.io\/mqzyx"},{"key":"6_CR36","doi-asserted-by":"publisher","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. p. 23\u201334. SIGMOD \u201979, Association for Computing Machinery, New York, NY, USA (1979). https:\/\/doi.org\/10.1145\/582095.582099, https:\/\/doi.org\/10.1145\/582095.582099","DOI":"10.1145\/582095.582099"},{"key":"6_CR37","doi-asserted-by":"publisher","unstructured":"Soremekun, E., Kirschner, L., B\u00f6hme, M., Zeller, A.: Locating faults with program slicing: an empirical analysis. Empirical Software Engineering 26(3), \u00a051 (Apr 2021). https:\/\/doi.org\/10.1007\/s10664-020-09931-7","DOI":"10.1007\/s10664-020-09931-7"},{"key":"6_CR38","doi-asserted-by":"publisher","unstructured":"Truemper, K.: On the delta-wye reduction for planar graphs. Journal of Graph Theory 13(2), 141\u2013148 (1989). https:\/\/doi.org\/10.1002\/jgt.3190130202","DOI":"10.1002\/jgt.3190130202"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91118-7_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T08:17:47Z","timestamp":1746001067000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91118-7_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031911170","9783031911187"],"references-count":38,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91118-7_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"1 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hamilton, ON","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 May 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"34","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/2025\/conferences\/esop\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}