{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,2]],"date-time":"2026-10-02T07:51:06Z","timestamp":1790927466585,"version":"4.1.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>Highly expressive declarative languages, such as<jats:italic>datalog<\/jats:italic>, are now commonly used to model the operational logic of data-intensive applications. The typical complexity of such datalog programs, and the large volume of data that they process, call for result<jats:italic>explanation.<\/jats:italic>Results may be explained through the tracking and presentation of<jats:italic>data provenance<\/jats:italic>, and here we focus on a detailed form of provenance (<jats:italic>how-provenance<\/jats:italic>), defining it as the set of derivation trees of a given fact. While informative, the size of such<jats:italic>full<\/jats:italic>provenance information is typically too large and complex (even when compactly represented) to allow displaying it to the user. To this end, we propose a novel top-k query language for querying datalog provenance, supporting selection criteria based on tree patterns and ranking based on the rules and database facts used in derivation. We propose an efficient novel algorithm based on (1) instrumenting the datalog program so that, upon evaluation, it generates only relevant provenance, and (2) efficient top-k (relevant) provenance generation, combined with bottom-up datalog evaluation. The algorithm computes in polynomial data complexity a compact representation of the top-k trees which may be explicitly constructed in linear time with respect to their size. We further experimentally study the algorithm performance, showing its scalability even for complex datalog programs where full provenance tracking is infeasible.<\/jats:p>","DOI":"10.14778\/2824032.2824039","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1394-1405","source":"Crossref","is-referenced-by-count":29,"title":["Selective provenance for datalog programs using top-k queries"],"prefix":"10.14778","volume":"8","author":[{"given":"Daniel","family":"Deutch","sequence":"first","affiliation":[{"name":"Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir","family":"Gilad","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Moskovitch","sequence":"additional","affiliation":[{"name":"Tel Aviv University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Addison-Wesley","author":"Abiteboul S.","year":"1995"},{"key":"e_1_2_1_2_1","first-page":"190","volume-title":"SSDBM","author":"Ailamaki A.","year":"1998"},{"key":"e_1_2_1_3_1","first-page":"101","volume-title":"DOOD","author":"Arora T.","year":"1993"},{"key":"e_1_2_1_4_1","first-page":"493","volume-title":"SIGMOD","author":"Bao Z.","year":"2011"},{"key":"e_1_2_1_5_1","first-page":"1352","volume-title":"CIKM","author":"Bao Z.","year":"2012"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0080-z"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412331.1412340"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1145\/1516360.1516380","volume-title":"EDBT","author":"Chang L.","year":"2009"},{"key":"e_1_2_1_9_1","first-page":"993","volume-title":"SIGMOD","author":"Chapman A. P.","year":"2008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"J. Cheney A. Ahmed and U. A. Acar. Database queries that explain their work. CoRR abs\/1408.1675 2014. J. Cheney A. Ahmed and U. A. Acar. Database queries that explain their work. CoRR abs\/1408.1675 2014.","DOI":"10.1145\/2643135.2643143"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1561\/1900000006"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/1804669.1804680","volume-title":"ICDT","author":"Cohen S.","year":"2010"},{"issue":"3","key":"e_1_2_1_13_1","first-page":"3","article-title":"Business artifacts: A data-centric approach to modeling business operations and processes","volume":"32","author":"Cohn D.","year":"2009","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_14_1","first-page":"1345","volume-title":"SIGMOD","author":"Davidson S. B.","year":"2008"},{"key":"e_1_2_1_15_1","first-page":"1484","volume-title":"ICDE","author":"Deutch D.","year":"2015"},{"key":"e_1_2_1_16_1","first-page":"215","volume-title":"PODS","author":"Deutch D.","year":"2010"},{"key":"e_1_2_1_17_1","first-page":"201","volume-title":"ICDT","author":"Deutch D.","year":"2014"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140445"},{"key":"e_1_2_1_20_1","first-page":"37","volume-title":"SSDBM","author":"Foster I.","year":"2002"},{"key":"e_1_2_1_21_1","first-page":"282","volume-title":"SIGIR","author":"Fuhr N.","year":"1995"},{"key":"e_1_2_1_22_1","unstructured":"http:\/\/www.cs.tau.ac.il\/~danielde\/selpFull.pdf. http:\/\/www.cs.tau.ac.il\/~danielde\/selpFull.pdf."},{"key":"e_1_2_1_23_1","first-page":"413","volume-title":"WWW","author":"Gal\u00e1rraga L. A.","year":"2013"},{"issue":"2","key":"e_1_2_1_24_1","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/j.jal.2009.09.001","article-title":"On database query languages for k-relations","volume":"8","author":"Geerts F.","year":"2010","journal-title":"J. Applied Logic"},{"key":"e_1_2_1_25_1","first-page":"174","volume-title":"ICDE","author":"Glavic B.","year":"2009"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1921003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/978-3-642-41660-6_16","volume-title":"Search of Elegance in the Theory and Practice of Computation","author":"Glavic B.","year":"2013"},{"key":"e_1_2_1_28_1","volume-title":"Tapp","author":"Glavic B.","year":"2013"},{"key":"e_1_2_1_29_1","volume-title":"PODS","author":"Green T. J.","year":"2007"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"729","DOI":"10.1093\/nar\/gkl320","article-title":"Taverna: a tool for building and running workflows of services","volume":"34","author":"Hull D.","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"e_1_2_1_31_1","unstructured":"http:\/\/www.iris-reasoner.org. http:\/\/www.iris-reasoner.org."},{"key":"e_1_2_1_32_1","volume-title":"TaPP","author":"Ives Z. G.","year":"2012"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350236"},{"key":"e_1_2_1_34_1","first-page":"951","volume-title":"SIGMOD","author":"Karvounarakis G.","year":"2010"},{"key":"e_1_2_1_35_1","first-page":"219","volume-title":"SUM","author":"Kenig B.","year":"2013"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0150-5"},{"key":"e_1_2_1_37_1","first-page":"27","volume-title":"VLDB","author":"Kimelfeld B.","year":"2007"},{"issue":"1","key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0020-0190(77)90002-3","article-title":"A generalization of dijkstra's algorithm","volume":"6","author":"Knuth D. E.","year":"1977","journal-title":"Inf. Process. Lett."},{"key":"e_1_2_1_39_1","first-page":"673","volume-title":"ICDE","author":"Li J.","year":"2011"},{"key":"e_1_2_1_40_1","first-page":"97","volume-title":"SIGMOD","author":"Loo B. T.","year":"2006"},{"issue":"12","key":"e_1_2_1_41_1","first-page":"1490","article-title":"Reverse data management","volume":"4","author":"Meliou A.","year":"2011","journal-title":"PVLDB"},{"key":"e_1_2_1_42_1","first-page":"337","volume-title":"SIGMOD","author":"Meliou A.","year":"2012"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1145\/1739041.1739079","volume-title":"EDBT","author":"Missier P.","year":"2010"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-011-0144-2"},{"key":"e_1_2_1_45_1","first-page":"25","volume-title":"VLDS","author":"Niu F.","year":"2012"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1145\/2274576.2274607","volume-title":"ICDT","author":"Olteanu D.","year":"2012"},{"key":"e_1_2_1_47_1","first-page":"365","volume-title":"SIGPLAN","author":"Perera R.","year":"2012"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-006-5833-1"},{"key":"e_1_2_1_49_1","first-page":"1273","volume-title":"CIKM","author":"Ronen R.","year":"2010"},{"key":"e_1_2_1_50_1","first-page":"1579","volume-title":"SIGMOD","author":"Roy S.","year":"2014"},{"issue":"3","key":"e_1_2_1_51_1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF03037166","article-title":"Logical diagnosis of LDL programs","volume":"9","author":"Shmueli O.","year":"1991","journal-title":"New Generation Comput."},{"issue":"2","key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4018\/jwsr.2008040101","article-title":"Karma2: Provenance management for data-driven workflows","volume":"5","author":"Simmhan Y. L.","year":"2008","journal-title":"Int. J. Web Service Res."},{"key":"e_1_2_1_53_1","first-page":"697","volume-title":"WWW","author":"Suchanek F. M.","year":"2007"},{"key":"e_1_2_1_54_1","volume-title":"Synthesis Lectures on Data Management. Morgan & Claypool Publishers","author":"Suciu D.","year":"2011"},{"key":"e_1_2_1_55_1","unstructured":"Prov-overview w3c working group note. http:\/\/www.w3.org\/TR\/prov-overview\/ 2013. Prov-overview w3c working group note. http:\/\/www.w3.org\/TR\/prov-overview\/ 2013."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824039","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,14]],"date-time":"2023-08-14T05:49:43Z","timestamp":1691992183000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824039"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":55,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824039"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824039","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}