{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,27]],"date-time":"2025-12-27T15:06:18Z","timestamp":1766847978495},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T00:00:00Z","timestamp":1330992000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2013,4]]},"DOI":"10.1007\/s00224-012-9392-5","type":"journal-article","created":{"date-parts":[[2012,3,5]],"date-time":"2012-03-05T21:16:00Z","timestamp":1330982160000},"page":"403-440","source":"Crossref","is-referenced-by-count":23,"title":["Knowledge Compilation Meets Database Theory: Compiling Queries to Decision Diagrams"],"prefix":"10.1007","volume":"52","author":[{"given":"Abhay","family":"Jha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"key":"9392_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S0020-0190(98)00042-8","volume":"66","author":"B. Bollig","year":"1998","unstructured":"Bollig, B., Wegener, I.: A\u00a0very simple function that requires exponential-size read-once branching programs. Inf. Process. Lett. 66, 53\u201357 (1998)","journal-title":"Inf. Process. Lett."},{"key":"9392_CR2","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1007\/s002240000128","volume":"32","author":"B. Bollig","year":"1999","unstructured":"Bollig, B., Wegener, I.: Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams. Theory Comput. Syst. 32, 487\u2013503 (1999). doi: 10.1007\/s002240000128","journal-title":"Theory Comput. Syst."},{"key":"9392_CR3","first-page":"688","volume-title":"DAC","author":"R.E. Bryant","year":"1985","unstructured":"Bryant, R.E.: Symbolic manipulation of boolean functions using a graphical representation. In: DAC, pp.\u00a0688\u2013694 (1985)"},{"issue":"8","key":"9392_CR4","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R.E. Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677\u2013691 (1986)","journal-title":"IEEE Trans. Comput."},{"issue":"2","key":"9392_CR5","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1109\/12.73590","volume":"40","author":"R.E. Bryant","year":"1991","unstructured":"Bryant, R.E.: On the complexity of VLSI implementations and graph representations of boolean functions with application to integer multiplication. IEEE Trans. Comput. 40(2), 205\u2013213 (1991) doi: 10.1109\/12.73590","journal-title":"IEEE Trans. Comput."},{"issue":"3,4","key":"9392_CR6","first-page":"137","volume":"10","author":"M. Cadoli","year":"1997","unstructured":"Cadoli, M., Donini, F.M.: A\u00a0survey on knowledge compilation. AI Commun. 10(3,4), 137\u2013150 (1997)","journal-title":"AI Commun."},{"key":"9392_CR7","first-page":"77","volume-title":"Proceedings of 9th ACM Symposium on Theory of Computing","author":"A. Chandra","year":"1977","unstructured":"Chandra, A., Merlin, P.: Optimal implementation of conjunctive queries in relational data bases. In: Proceedings of 9th ACM Symposium on Theory of Computing, Boulder, Colorado, pp.\u00a077\u201390 (1977)"},{"key":"9392_CR8","first-page":"293","volume-title":"PODS","author":"N. Dalvi","year":"2007","unstructured":"Dalvi, N., Suciu, D.: The dichotomy of conjunctive queries on probabilistic structures. In: PODS, pp.\u00a0293\u2013302 (2007)"},{"issue":"4","key":"9392_CR9","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1007\/s00778-006-0004-3","volume":"16","author":"N. Dalvi","year":"2007","unstructured":"Dalvi, N., Suciu, D.: Efficient query evaluation on probabilistic databases. VLDB J. 16(4), 523\u2013544 (2007)","journal-title":"VLDB J."},{"key":"9392_CR10","first-page":"1","volume-title":"PODS","author":"N. Dalvi","year":"2007","unstructured":"Dalvi, N., Suciu, D.: Management of probabilistic data: foundations and challenges. In: PODS, pp.\u00a01\u201312. ACM Press, New York (2007)"},{"key":"9392_CR11","first-page":"203","volume-title":"PODS","author":"N.N. Dalvi","year":"2010","unstructured":"Dalvi, N.N., Schnaitter, K., Suciu, D.: Computing query probability with incidence algebras. In: PODS, pp.\u00a0203\u2013214 (2010)"},{"key":"9392_CR12","unstructured":"Darwiche, A.: On the tractable counting of theory models and its application to belief revision and truth maintenance. CoRR cs.AI\/0003044 (2000)"},{"issue":"1","key":"9392_CR13","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1613\/jair.989","volume":"17","author":"A. Darwiche","year":"2002","unstructured":"Darwiche, A., Marquis, P.: A\u00a0knowledge compilation map. J. Artif. Intell. Res. 17(1), 229\u2013264 (2002)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"9392_CR14","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0020-0190(97)00041-0","volume":"62","author":"A. G\u00e1l","year":"1997","unstructured":"G\u00e1l, A.: A simple function that requires exponential size read-once branching programs. Inf. Process. Lett. 62(1), 13\u201316 (1997). doi: 10.1016\/S0020-0190(97)00041-0 . http:\/\/www.sciencedirect.com\/science\/article\/B6V0F-3SNV288-T\/2\/39afb175413bd7ee03397bb582be0161","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"9392_CR15","doi-asserted-by":"crossref","first-page":"1197","DOI":"10.1109\/12.324545","volume":"43","author":"J. Gergov","year":"1994","unstructured":"Gergov, J., Meinel, C.: Efficient boolean manipulation with obdd\u2019s can be extended to fbdd\u2019s. IEEE Trans. Comput. 43(10), 1197\u20131209 (1994)","journal-title":"IEEE Trans. Comput."},{"issue":"10","key":"9392_CR16","doi-asserted-by":"crossref","first-page":"1465","DOI":"10.1016\/j.dam.2005.09.016","volume":"154","author":"M.C. Golumbic","year":"2006","unstructured":"Golumbic, M.C., Mintz, A., Rotics, U.: Factoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees. Discrete Appl. Math. 154(10), 1465\u20131477 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9392_CR17","first-page":"31","volume-title":"PODS","author":"T. Green","year":"2007","unstructured":"Green, T., Karvounarakis, G., Tannen, V.: Provenance semirings. In: PODS, pp.\u00a031\u201340 (2007)"},{"key":"9392_CR18","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1145\/1514894.1514930","volume-title":"ICDT","author":"T.J. Green","year":"2009","unstructured":"Green, T.J.: Containment of conjunctive queries on annotated relations. In: ICDT, pp.\u00a0296\u2013309 (2009)"},{"key":"9392_CR19","first-page":"183","volume":"32","author":"V. Gurvich","year":"1977","unstructured":"Gurvich, V.: Repetition-free boolean functions. Usp. Mat. Nauk 32, 183\u2013184 (1977)","journal-title":"Usp. Mat. Nauk"},{"key":"9392_CR20","first-page":"326","volume-title":"SUM","author":"D. Olteanu","year":"2008","unstructured":"Olteanu, D., Huang, J.: Using OBDDs for efficient query evaluation on probabilistic databases. In: SUM, pp.\u00a0326\u2013340 (2008)"},{"key":"9392_CR21","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1145\/1938551.1938582","volume-title":"Proceedings of the 14th International Conference on Database Theory, ICDT\u201911","author":"S. Roy","year":"2011","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, ICDT\u201911, pp.\u00a0232\u2013243. ACM, New York (2011). doi: 10.1145\/1938551.1938582"},{"key":"9392_CR22","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1145\/322217.322221","volume":"27","author":"Y. Sagiv","year":"1980","unstructured":"Sagiv, Y., Yannakakis, M.: Equivalences among relational expressions with the union and difference operators. J. ACM 27, 633\u2013655 (1980)","journal-title":"J. ACM"},{"key":"9392_CR23","volume-title":"VLDB","author":"P. Sen","year":"2010","unstructured":"Sen, P., Deshpande, A., Getoor, L.: Read-once functions and query evaluation in probabilistic databases. In: VLDB (2010)"},{"issue":"1&2","key":"9392_CR24","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1016\/0304-3975(94)00078-W","volume":"141","author":"D. Sieling","year":"1995","unstructured":"Sieling, D., Wegener, I.: Graph driven bdds\u2014a new data structure for boolean functions. Theor. Comput. Sci. 141(1&2), 283\u2013310 (1995)","journal-title":"Theor. Comput. Sci."},{"key":"9392_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1739041.1739043","volume-title":"EDBT","author":"V. Tannen","year":"2010","unstructured":"Tannen, V.: Provenance for database transformations. In: EDBT, p.\u00a01 (2010)"},{"key":"9392_CR26","doi-asserted-by":"crossref","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. SIAM, Philadelphia (2000)"},{"issue":"1\u20132","key":"9392_CR27","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/S0166-218X(03)00297-X","volume":"138","author":"I. Wegener","year":"2004","unstructured":"Wegener, I.: BDDs\u2013design, analysis, complexity, and applications. Discrete Appl. Math. 138(1\u20132), 229\u2013251 (2004)","journal-title":"Discrete Appl. Math."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9392-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-012-9392-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-012-9392-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,24]],"date-time":"2019-06-24T23:28:47Z","timestamp":1561418927000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-012-9392-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,6]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["9392"],"URL":"https:\/\/doi.org\/10.1007\/s00224-012-9392-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,6]]}}}