{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T04:59:42Z","timestamp":1790398782890,"version":"4.1.0"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,2,22]],"date-time":"2018-02-22T00:00:00Z","timestamp":1519257600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ICRC"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1636\/13"],"award-info":[{"award-number":["1636\/13"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00778-018-0496-7","type":"journal-article","created":{"date-parts":[[2018,2,22]],"date-time":"2018-02-22T04:28:16Z","timestamp":1519273696000},"page":"245-269","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Efficient provenance tracking for datalog using top-k queries"],"prefix":"10.1007","volume":"27","author":[{"given":"Daniel","family":"Deutch","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-1958","authenticated-orcid":false,"given":"Amir","family":"Gilad","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Moskovitch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,2,22]]},"reference":[{"key":"496_CR1","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":"496_CR2","doi-asserted-by":"crossref","unstructured":"Ailamaki, A., Ioannidis, Y.E., Livny, M.: Scientific workflow management by database management. In: SSDBM (1998)","DOI":"10.1109\/SSDM.1998.688123"},{"key":"496_CR3","doi-asserted-by":"crossref","unstructured":"Arora, T., Ramakrishnan, R., Roth, W.G., Seshadri, P., Srivastava, D.: Explaining program execution in deductive systems. In: DOOD (1993)","DOI":"10.1007\/3-540-57530-8_7"},{"key":"496_CR4","doi-asserted-by":"crossref","unstructured":"Bao, Z., Davidson, S.B., Milo, T.: Labeling recursive workflow executions on-the-fly. In: SIGMOD (2011)","DOI":"10.1145\/1989323.1989375"},{"key":"496_CR5","doi-asserted-by":"crossref","unstructured":"Bao, Z., K\u00f6hler, H., Wang, L., Zhou, X., Sadiq, S.: Efficient provenance storage for relational queries. In: CIKM (2012)","DOI":"10.1145\/2396761.2398439"},{"key":"496_CR6","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s00778-007-0080-z","volume":"17","author":"O Benjelloun","year":"2008","unstructured":"Benjelloun, O., Sarma, A., Halevy, A., Theobald, M., Widom, J.: Databases with uncertainty and lineage. VLDB J. 17, 243 (2008)","journal-title":"VLDB J."},{"issue":"4","key":"496_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1412331.1412340","volume":"33","author":"P Buneman","year":"2008","unstructured":"Buneman, P., Cheney, J., Vansummeren, S.: On the expressiveness of implicit provenance in query and update languages. ACM Trans. Database Syst. 33(4), 1 (2008)","journal-title":"ACM Trans. Database Syst."},{"key":"496_CR8","doi-asserted-by":"crossref","unstructured":"Chang, L., Yu, J.X., Qin, L.: Query ranking in probabilistic XML data. In: EDBT (2009)","DOI":"10.1145\/1516360.1516380"},{"key":"496_CR9","doi-asserted-by":"crossref","unstructured":"Chapman, A.P., Jagadish, H.V., Ramanan, P.: Efficient provenance storage. In: ACM SIGMOD, SIGMOD \u201908 (2008)","DOI":"10.1145\/1376616.1376715"},{"key":"496_CR10","doi-asserted-by":"crossref","unstructured":"Cheney, J., Ahmed, A., Acar, U.A.: Database queries that explain their work. In: CoRR, abs\/1408.1675 (2014)","DOI":"10.1145\/2643135.2643143"},{"issue":"4","key":"496_CR11","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1561\/1900000006","volume":"1","author":"J Cheney","year":"2009","unstructured":"Cheney, J., Chiticariu, L., Tan, W.C.: Provenance in databases: why, how, and where. Found. Trends Databases 1(4), 379 (2009)","journal-title":"Found. Trends Databases"},{"key":"496_CR12","doi-asserted-by":"crossref","unstructured":"Cohen, S., Kimelfeld, B.: Querying parse trees of stochastic context-free grammars. In: ICDT (2010)","DOI":"10.1145\/1804669.1804680"},{"issue":"3","key":"496_CR13","first-page":"3","volume":"32","author":"D Cohn","year":"2009","unstructured":"Cohn, D., Hull, R.: Business artifacts: a data-centric approach to modeling business operations and processes. IEEE Data Eng. Bull. 32(3), 3 (2009)","journal-title":"IEEE Data Eng. Bull."},{"key":"496_CR14","unstructured":"Dam\u00e1sio, C.V., Analyti, A., Antoniou, G.: Justifications for logic programming. In: Logic Programming and Nonmonotonic Reasoning (2013)"},{"key":"496_CR15","doi-asserted-by":"crossref","unstructured":"Davidson, S.B., Freire, J.: Provenance and scientific workflows: challenges and opportunities. In: SIGMOD (2008)","DOI":"10.1145\/1376616.1376772"},{"issue":"12","key":"496_CR16","first-page":"1394","volume":"8","author":"D Deutch","year":"2015","unstructured":"Deutch, D., Gilad, A., Moskovitch, Y.: Selective provenance for datalog programs using top-k queries. PVLDB 8(12), 1394 (2015)","journal-title":"PVLDB"},{"key":"496_CR17","doi-asserted-by":"crossref","unstructured":"Deutch, D., Gilad, A., Moskovitch, Y.: selp: selective tracking and presentation of data provenance (demo). In: ICDE (2015)","DOI":"10.1109\/ICDE.2015.7113407"},{"key":"496_CR18","doi-asserted-by":"crossref","unstructured":"Deutch, D., Koch, C., Milo, T.: On probabilistic fixpoint and markov chain query languages. In: PODS (2010)","DOI":"10.1145\/1807085.1807114"},{"key":"496_CR19","unstructured":"Deutch, D., Milo, T., Roy, S., Tannen, V.: Circuits for datalog provenance. In: ICDT (2014)"},{"issue":"2","key":"496_CR20","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D Eppstein","year":"1998","unstructured":"Eppstein, D.: Finding the k shortest paths. SIAM J. Comput. 28(2), 652 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"496_CR21","first-page":"490","volume":"5","author":"R Fink","year":"2012","unstructured":"Fink, R., Han, L., Olteanu, D.: Aggregation in probabilistic databases via knowledge compilation. PVLDB 5(5), 490 (2012)","journal-title":"PVLDB"},{"key":"496_CR22","doi-asserted-by":"crossref","unstructured":"Foster, I., Vockler, J., Wilde, M., Zhao, A.: Chimera: a virtual data system for representing, querying, and automating data derivation. In: SSDBM (2002)","DOI":"10.1109\/SSDM.2002.1029704"},{"key":"496_CR23","doi-asserted-by":"crossref","unstructured":"Fuhr, N.: Probabilistic datalog:a logic for powerful retrieval methods. In: SIGIR (1995)","DOI":"10.1145\/215206.215372"},{"key":"496_CR24","doi-asserted-by":"crossref","unstructured":"Gal\u00e1rraga, L.A., Teflioudi, C., Hose, K., Suchanek, F.M.: Amie: association rule mining under incomplete evidence in ontological knowledge bases. In: WWW (2013)","DOI":"10.1145\/2488388.2488425"},{"issue":"2","key":"496_CR25","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/j.jal.2009.09.001","volume":"8","author":"F Geerts","year":"2010","unstructured":"Geerts, F., Poggi, A.: On database query languages for k-relations. J. Appl. Logic 8(2), 173\u2013185 (2010)","journal-title":"J. Appl. Logic"},{"key":"496_CR26","doi-asserted-by":"crossref","unstructured":"Glavic B., Alonso, G.: Perm: processing provenance and data on the same data model through query rewriting. In: ICDE, pp. 174\u2013185 (2009)","DOI":"10.1109\/ICDE.2009.15"},{"issue":"1","key":"496_CR27","first-page":"1314","volume":"3","author":"B Glavic","year":"2010","unstructured":"Glavic, B., Alonso, G., Miller, R.J., Haas, L.M.: TRAMP: understanding the behavior of schema mappings through provenance. PVLDB 3(1), 1314\u20131325 (2010)","journal-title":"PVLDB"},{"key":"496_CR28","doi-asserted-by":"crossref","unstructured":"Glavic, B., Miller, R.J., Alonso, G.: Using sql for efficient generation and querying of provenance information. In: In Search of Elegance in the Theory and Practice of Computation. Springer (2013)","DOI":"10.1007\/978-3-642-41660-6_16"},{"key":"496_CR29","unstructured":"Glavic, B., Siddique, J., Andritsos, P., Miller, R.J.: Provenance for data mining. In: Tapp (2013)"},{"key":"496_CR30","doi-asserted-by":"crossref","unstructured":"Green, T.J., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS (2007)","DOI":"10.1145\/1265530.1265535"},{"key":"496_CR31","doi-asserted-by":"publisher","first-page":"W729","DOI":"10.1093\/nar\/gkl320","volume":"34","author":"D Hull","year":"2006","unstructured":"Hull, D., Wolstencroft, K., Stevens, R., Goble, C., Pocock, M., Li, P., Oinn, T.: Taverna: a tool for building and running workflows of services. Nucleic Acids Res. 34, W729 (2006)","journal-title":"Nucleic Acids Res."},{"key":"496_CR32","unstructured":"http:\/\/www.iris-reasoner.org"},{"issue":"4","key":"496_CR33","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/1634.1886","volume":"31","author":"T Imieli\u0144ski","year":"1984","unstructured":"Imieli\u0144ski, T., Lipski Jr., W.: Incomplete information in relational databases. J. ACM 31(4), 761 (1984)","journal-title":"J. ACM"},{"key":"496_CR34","unstructured":"Ives, Z.G., Haeberlen, A., Feng, T., Gatterbauer, W.: Querying provenance for ranking and recommending. In: TaPP (2012)"},{"issue":"11","key":"496_CR35","first-page":"1160","volume":"5","author":"AK Jha","year":"2012","unstructured":"Jha, A.K., Suciu, D.: Probabilistic databases with markoviews. PVLDB 5(11), 1160 (2012)","journal-title":"PVLDB"},{"key":"496_CR36","doi-asserted-by":"crossref","unstructured":"Karvounarakis, G., Ives, Z.G., Tannen, V.: Querying data provenance. In: SIGMOD (2010)","DOI":"10.1145\/1807167.1807269"},{"key":"496_CR37","doi-asserted-by":"crossref","unstructured":"Kenig, B., Gal, A., Strichman, O.: A new class of lineage expressions over probabilistic databases computable in p-time. In: SUM, pp. 219\u2013232 (2013)","DOI":"10.1007\/978-3-642-40381-1_17"},{"issue":"5","key":"496_CR38","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1007\/s00778-009-0150-5","volume":"18","author":"B Kimelfeld","year":"2009","unstructured":"Kimelfeld, B., Kosharovsky, Y., Sagiv, Y.: Query evaluation over probabilistic XML. VLDB J. 18(5), 1117 (2009)","journal-title":"VLDB J."},{"key":"496_CR39","unstructured":"Kimelfeld, B., Sagiv, Y.: Matching twigs in probabilistic XML. In: VLDB (2007)"},{"issue":"1","key":"496_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0020-0190(77)90002-3","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E.: A generalization of Dijkstra\u2019s algorithm. Inf. Process. Lett. 6(1), 1 (1977)","journal-title":"Inf. Process. Lett."},{"key":"496_CR41","doi-asserted-by":"crossref","unstructured":"K\u00f6hler, S., Lud\u00e4scher, B., Smaragdakis, Y.: Declarative datalog debugging for mere mortals. In: Datalog in Academia and Industry (2012)","DOI":"10.1007\/978-3-642-32925-8_12"},{"issue":"2","key":"496_CR42","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/BF00961871","volume":"4","author":"G K\u00f6stler","year":"1995","unstructured":"K\u00f6stler, G., Kie\u00dfling, W., Th\u00f6ne, H., G\u00fcntzer, U.: Fixpoint iteration with subsumption in deductive databases. J. Intell. Inf. Syst. 4(2), 123 (1995)","journal-title":"J. Intell. Inf. Syst."},{"key":"496_CR43","doi-asserted-by":"crossref","unstructured":"Li, J., Liu, C., Zhou, R., Wang, W.: Top-k keyword search over probabilistic XML data. In: ICDE (2011)","DOI":"10.1109\/ICDE.2011.5767875"},{"key":"496_CR44","doi-asserted-by":"crossref","unstructured":"Loo, B.T. et\u00a0al.: Declarative networking: language, execution and optimization. In: SIGMOD (2006)","DOI":"10.1145\/1142473.1142485"},{"issue":"12","key":"496_CR45","first-page":"1490","volume":"4","author":"A Meliou","year":"2011","unstructured":"Meliou, A., Gatterbauer, W., Suciu, D.: Reverse data management. PVLDB 4(12), 1490 (2011)","journal-title":"PVLDB"},{"key":"496_CR46","doi-asserted-by":"crossref","unstructured":"Meliou, A., Suciu, D.: Tiresias: the database oracle for how-to queries. In: SIGMOD (2012)","DOI":"10.1145\/2213836.2213875"},{"key":"496_CR47","doi-asserted-by":"crossref","unstructured":"Missier, P., Paton, N., Belhajjame, K.: Fine-grained and efficient lineage querying of collection-based workflow provenance. In: EDBT (2010)","DOI":"10.1145\/1739041.1739079"},{"issue":"3","key":"496_CR48","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/s11280-011-0144-2","volume":"16","author":"B Ning","year":"2013","unstructured":"Ning, B., Liu, C., Yu, J.X.: Efficient processing of top-k twig queries over probabilistic XML data. World Wide Web 16(3), 299 (2013)","journal-title":"World Wide Web"},{"key":"496_CR49","unstructured":"Niu, F., Zhang, C., Re, C., Shavlik, J.W.: Deepdive: Web-scale knowledge-base construction using statistical learning and inference. In: VLDS, pp. 25\u201328 (2012)"},{"key":"496_CR50","doi-asserted-by":"crossref","unstructured":"Olteanu, D., Zavodny, J.: Factorised representations of query results: size bounds and readability. In: ICDT (2012)","DOI":"10.1145\/2274576.2274607"},{"key":"496_CR51","doi-asserted-by":"crossref","unstructured":"Perera, R., Acar, U.A., Cheney, J., Levy, P.B.: Functional programs that explain their work. In: SIGPLAN (2012)","DOI":"10.1145\/2364527.2364579"},{"key":"496_CR52","unstructured":"Prov-overview, w3c working group note. http:\/\/www.w3.org\/TR\/prov-overview\/ 2013"},{"issue":"1\u20132","key":"496_CR53","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s10994-006-5833-1","volume":"62","author":"M Richardson","year":"2006","unstructured":"Richardson, M., Domingos, P.: Markov logic networks. Mach. Learn. 62(1\u20132), 107 (2006)","journal-title":"Mach. Learn."},{"key":"496_CR54","doi-asserted-by":"crossref","unstructured":"Ronen, R., Shmueli, O.: Automated interaction in social networks with datalog. In: CIKM (2010)","DOI":"10.1145\/1871437.1871599"},{"key":"496_CR55","doi-asserted-by":"crossref","unstructured":"Roy, S., Suciu, D.: A formal approach to finding explanations for database queries. In: SIGMOD (2014)","DOI":"10.1145\/2588555.2588578"},{"issue":"3\/4","key":"496_CR56","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/BF03037166","volume":"9","author":"O Shmueli","year":"1991","unstructured":"Shmueli, O., Tsur, S.: Logical diagnosis of LDL programs. New Gener. Comput. 9(3\/4), 277 (1991)","journal-title":"New Gener. Comput."},{"issue":"2","key":"496_CR57","first-page":"317","volume":"5","author":"YL Simhan","year":"2008","unstructured":"Simhan, Y.L., Plale, B., Gammon, D.: Karma2: provenance management for data-driven workflows. Int. J. Web Serv. Res. 5(2), 317 (2008)","journal-title":"Int. J. Web Serv. Res."},{"key":"496_CR58","doi-asserted-by":"crossref","unstructured":"Suchanek, F.M., Kasneci, G., Weikum, G.: Yago: a core of semantic knowledge. In: WWW (2007)","DOI":"10.1145\/1242572.1242667"},{"key":"496_CR59","doi-asserted-by":"crossref","unstructured":"Suciu, D., Olteanu, D., R\u00e9, C., Koch, C.: Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers (2011)","DOI":"10.2200\/S00362ED1V01Y201105DTM016"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-018-0496-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0496-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-018-0496-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,11]],"date-time":"2019-10-11T06:57:54Z","timestamp":1570777074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-018-0496-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,22]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["496"],"URL":"https:\/\/doi.org\/10.1007\/s00778-018-0496-7","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,22]]},"assertion":[{"value":"21 December 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 November 2017","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2018","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2018","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}