{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T11:18:27Z","timestamp":1743074307984,"version":"3.40.3"},"publisher-location":"New York, NY","reference-count":39,"publisher":"Springer New York","isbn-type":[{"type":"print","value":"9781461482666"},{"type":"electronic","value":"9781461482659"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","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":[[2018]]},"DOI":"10.1007\/978-1-4614-8265-9_80759","type":"book-chapter","created":{"date-parts":[[2018,12,6]],"date-time":"2018-12-06T11:54:56Z","timestamp":1544097296000},"page":"4280-4286","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Uncertain Data Lineage"],"prefix":"10.1007","author":[{"given":"Sudeepa","family":"Roy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,12,7]]},"reference":[{"key":"80759_CR211","unstructured":"Afrati FN, Vasilakopoulos A. Query containment for databases with uncertainty and lineage. In: Proceedings of the 4th International VLDB Workshop on Management of Uncertain Data; 2010. p. 67\u201381."},{"key":"80759_CR212","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09690-2","volume-title":"Managing and mining uncertain data","author":"CC Aggarwal","year":"2009","unstructured":"Aggarwal CC. Managing and mining uncertain data. New York: Springer Publishing Company, Incorporated; 2009."},{"issue":"6","key":"80759_CR213","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/TC.1978.1675141","volume":"27","author":"SB Akers","year":"1978","unstructured":"Akers SB. Binary decision diagrams. IEEE Trans. Comput. 1978;27(6):509\u201316.","journal-title":"IEEE Trans. Comput."},{"key":"80759_CR214","doi-asserted-by":"crossref","unstructured":"Amarilli A, Bourhis P, Senellart P. Tractable lineages on treelike instances: limits and extensions. In: Proceedings of the 35th ACM Symposium on Principles of Database Systems; 2016. p. 355\u2013370.","DOI":"10.1145\/2902251.2902301"},{"issue":"1","key":"80759_CR215","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2984632","volume":"42","author":"Paul Beame","year":"2017","unstructured":"Beame P, Li J, Roy S, Suciu D. Exact model counting of query expressions: limitations of propositional methods. ACM Trans Database Syst. 2017;42(1):1:1\u20131:46.","journal-title":"ACM Transactions on Database Systems"},{"key":"80759_CR216","doi-asserted-by":"crossref","unstructured":"Beame P, Van den Broeck G, Gribkoff E, Suciu D. Symmetric weighted first-order model counting. In: Proceedings of the 34th ACM Symposium on Principles of Database Systems; 2015. p. 313\u201328.","DOI":"10.1145\/2745754.2745760"},{"issue":"1","key":"80759_CR217","first-page":"5","volume":"29","author":"O Benjelloun","year":"2006","unstructured":"Benjelloun O, Sarma AD, Hayworth C, Widom J. An introduction to ULDBs and the Trio system. IEEE Data Eng Bull. 2006;29(1):5\u201316.","journal-title":"IEEE Data Eng Bull"},{"key":"80759_CR218","doi-asserted-by":"crossref","unstructured":"Blaustein BT, Seligman L, Morse M, Allen MD, Rosenthal A. PLUS: Synthesizing privacy, lineage, uncertainty and security. In: Proceedings of the Workshops of 24th International Conference on Data Engineering; 2008. p. 242\u20135.","DOI":"10.1109\/ICDEW.2008.4498325"},{"issue":"8","key":"80759_CR219","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant RE. Graph-based algorithms for Boolean function manipulation. IEEE Trans Comput 1986;35(8):677\u201391.","journal-title":"IEEE Trans Comput"},{"key":"80759_CR2110","doi-asserted-by":"publisher","first-page":"316","DOI":"10.1007\/3-540-44503-X_20","volume-title":"Database Theory \u2014 ICDT 2001","author":"Peter Buneman","year":"2001","unstructured":"Buneman P, Khanna S, Tan WC. Why and where: a characterization of data provenance. In: Proceedings of the 8th International Conference on Database Theory; 2001. p. 316\u201330."},{"issue":"2","key":"80759_CR2111","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1145\/357775.357777","volume":"25","author":"Y Cui","year":"2000","unstructured":"Cui Y, Widom J, Wiener JL. Tracing the lineage of view data in a warehousing environment. ACM Trans Database Syst. 2000;25(2):179\u2013227.","journal-title":"ACM Trans Database Syst"},{"key":"80759_CR2112","doi-asserted-by":"crossref","unstructured":"Dalvi, N, Suciu, D. Management of probabilistic data: foundations and challenges. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems; 2007. p. 1\u201312.","DOI":"10.1145\/1265530.1265531"},{"issue":"6","key":"80759_CR2113","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2395116.2395119","volume":"59","author":"Nilesh Dalvi","year":"2012","unstructured":"Dalvi N, Suciu D. The dichotomy of probabilistic inference for unions of conjunctive queries. J ACM. 2013;59(6):30:1\u201387.","journal-title":"Journal of the ACM"},{"key":"80759_CR2114","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1016\/B978-012088469-8.50076-0","volume-title":"Proceedings 2004 VLDB Conference","author":"N DALVI","year":"2004","unstructured":"Dalvi NN, Suciu D. Efficient query evaluation on probabilistic databases. In: Proceedings of the 30th International Conference on Very Large Data Bases; 2004. p. 864\u201375."},{"key":"80759_CR2115","doi-asserted-by":"crossref","unstructured":"Fink R, Olteanu D. On the optimal approximation of queries using tractable propositional languages. In: Proceedings of the 14th International Conference on Database Theory; 2011. p. 174\u2013185.","DOI":"10.1145\/1938551.1938575"},{"issue":"1","key":"80759_CR2116","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/2877203","volume":"41","author":"R Fink","year":"2016","unstructured":"Fink R, Olteanu D. Dichotomies for queries with negation in probabilistic databases. ACM Trans Database Syst. 2016;41(1):4.","journal-title":"ACM Trans Database Syst"},{"issue":"5","key":"80759_CR2117","doi-asserted-by":"publisher","first-page":"490","DOI":"10.14778\/2140436.2140445","volume":"5","author":"R Fink","year":"2012","unstructured":"Fink R, Han L, Olteanu D. Aggregation in probabilistic databases via knowledge compilation. Proc VLDB Endow. 2012;5(5):490\u2013501.","journal-title":"Proc VLDB Endow"},{"issue":"1","key":"80759_CR2118","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/239041.239045","volume":"15","author":"N Fuhr","year":"1997","unstructured":"Fuhr N, R\u00f6lleke T. A probabilistic relational algebra for the integration of information retrieval and database systems. ACM Trans Inf Syst 1997;15(1):32\u201366.","journal-title":"ACM Trans Inf Syst"},{"key":"80759_CR2119","doi-asserted-by":"crossref","unstructured":"Green TJ. Containment of conjunctive queries on annotated relations. In: Proceedings of the 12th International Conference on Database Theory; 2009. p. 296\u2013309.","DOI":"10.1145\/1514894.1514930"},{"issue":"1","key":"80759_CR2120","first-page":"17","volume":"29","author":"T Green","year":"2006","unstructured":"Green TJ, Tannen V. Models for incomplete and probabilistic information. IEEE Data Eng Bull. 2006;29(1):17\u201324.","journal-title":"IEEE Data Eng Bull"},{"key":"80759_CR2121","doi-asserted-by":"crossref","unstructured":"Green TJ, Karvounarakis G, Tannen V. Provenance semirings. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems; 2007. p. 31\u201340.","DOI":"10.1145\/1265530.1265535"},{"issue":"3","key":"80759_CR2122","first-page":"721","volume":"43","author":"V Gurvich","year":"1991","unstructured":"Gurvich VA. Criteria for repetition-freeness of functions in the algebra of logic. Soviet Math Dokl. 1991;43(3):721\u20136.","journal-title":"Soviet Math Dokl"},{"key":"80759_CR2123","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1613\/jair.2097","volume":"29","author":"J Huang","year":"2007","unstructured":"Huang J, Darwiche A. The language of search. J Artif Intel Res. 2007;29:191\u2013219.","journal-title":"J Artif Intel Res."},{"issue":"4","key":"80759_CR2124","doi-asserted-by":"publisher","first-page":"761","DOI":"10.1145\/1634.1886","volume":"31","author":"T Imielinski","year":"1984","unstructured":"Imielinski T, Lipski W Jr. Incomplete information in relational databases. J ACM. 1984;31(4):761\u201391.","journal-title":"J ACM"},{"key":"80759_CR2125","doi-asserted-by":"crossref","unstructured":"Jha AK, Suciu D. Knowledge compilation meets database theory: compiling queries to decision diagrams. In: Proceedings of the 14th International Conference on Database Theory; 2011. p. 162\u201373.","DOI":"10.1145\/1938551.1938574"},{"key":"80759_CR2126","first-page":"675","volume-title":"Lineage processing over correlated probabilistic databases","author":"B Kanagal","year":"2010","unstructured":"Kanagal B, Deshpande A. Lineage processing over correlated probabilistic databases. In: Proceedings of the ACM SIGMOD International Conference on Management of Data; 2010. p. 675\u2013686."},{"key":"80759_CR2127","doi-asserted-by":"crossref","unstructured":"Karp RM, Luby M. Monte-Carlo algorithms for enumeration and reliability problems. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science; 1983. p. 56\u201364.","DOI":"10.1109\/SFCS.1983.35"},{"issue":"11","key":"80759_CR2128","doi-asserted-by":"crossref","first-page":"1051","DOI":"10.14778\/3402707.3402741","volume":"4","author":"S Khanna","year":"2011","unstructured":"Khanna S, Roy S, Tannen V. Queries with difference on probabilistic databases. Proc VLDB Endow. 2011;4(11):1051\u201362.","journal-title":"Proc VLDB Endow"},{"key":"80759_CR2129","volume-title":"A fast algorithm for the string editing problem and decision graph complexity","author":"WJ Masek","year":"1976","unstructured":"Masek WJ. A fast algorithm for the string editing problem and decision graph complexity. Master\u2019s thesis, MIT; 1976."},{"key":"80759_CR2130","doi-asserted-by":"crossref","unstructured":"Meiser T, Dylla M, Theobald M. Interactive reasoning in uncertain RDF knowledge bases. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management; 2011. p. 2557\u20132560.","DOI":"10.1145\/2063576.2064018"},{"key":"80759_CR2131","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1017\/CBO9780511526633.004","volume-title":"Boolean function complexity","author":"I Newman","year":"1992","unstructured":"Newman I. On read-once Boolean functions. In: Paterson MS, editor. Boolean function complexity. Cambridge\/New York: Cambridge University Press; 1992. p. 25\u201334."},{"issue":"1","key":"80759_CR2132","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2877205","volume":"41","author":"Dan Olteanu","year":"2016","unstructured":"Olteanu D, van Schaik SJ. ENFrame: a framework for processing probabilistic data. ACM Trans Database Syst. 2016;41(1):3:1\u20133:44.","journal-title":"ACM Transactions on Database Systems"},{"key":"80759_CR2133","volume-title":"Probabilistic reasoning in intelligent systems: networks of plausible inference","author":"J Pearl","year":"1988","unstructured":"Pearl J. Probabilistic reasoning in intelligent systems: networks of plausible inference. San Francisco: Morgan Kaufmann Publishers Inc; 1988."},{"key":"80759_CR2134","doi-asserted-by":"crossref","unstructured":"Roy S, Perduca V, Tannen V. Faster query answering in probabilistic databases using read-once functions. In: Proceedings of the 14th International Conference on Database Theory; 2011. p. 232\u201343.","DOI":"10.1145\/1938551.1938582"},{"issue":"1","key":"80759_CR2135","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.14778\/1920841.1920975","volume":"3","author":"P Sen","year":"2010","unstructured":"Sen P, Deshpande A, Getoor L. Read-once functions and query evaluation in probabilistic databases. Proc VLDB Endow. 2010;3(1):1068\u201379.","journal-title":"Proc VLDB Endow"},{"key":"80759_CR2136","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01879-4","volume-title":"Probabilistic databases","author":"D Suciu","year":"2011","unstructured":"Suciu D, Olteanu D, Christopher R, Koch C. Probabilistic databases. 1st ed. San Rafael: Morgan & Claypool Publishers; 2011.","edition":"1"},{"issue":"3","key":"80759_CR2137","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L Valiant","year":"1979","unstructured":"Valiant LG. The complexity of enumeration and reliability problems. SIAM J Comput. 1979;8(3):410\u201321.","journal-title":"SIAM J Comput"},{"key":"80759_CR2138","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789","volume-title":"Branching programs and binary decision diagrams: theory and applications","author":"I Wegener","year":"2000","unstructured":"Wegener I. Branching programs and binary decision diagrams: theory and applications. Philadelphia: SIAM; 2000. ISBN:0-89871-458-3.","ISBN":"https:\/\/id.crossref.org\/isbn\/0898714583"},{"issue":"1\u20132","key":"80759_CR2139","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/S0304-3975(96)00129-6","volume":"171","author":"E Zim\u00e1nyi","year":"1997","unstructured":"Zim\u00e1nyi E. Query evaluation in probabilistic relational databases. Theor Comput Sci. 1997;171(1\u20132): 179\u2013219.","journal-title":"Theor Comput Sci"}],"container-title":["Encyclopedia of Database Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4614-8265-9_80759","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T19:05:21Z","timestamp":1662577521000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4614-8265-9_80759"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9781461482666","9781461482659"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-1-4614-8265-9_80759","relation":{},"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"7 December 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}