{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T16:52:12Z","timestamp":1773939132026,"version":"3.50.1"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2016,11,25]],"date-time":"2016-11-25T00:00:00Z","timestamp":1480032000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"NSERC Discovery."},{"name":"NSERC Strategic Network on Business Intelligence (BIN)."}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s00224-016-9718-9","type":"journal-article","created":{"date-parts":[[2016,11,24]],"date-time":"2016-11-24T21:11:47Z","timestamp":1480021907000},"page":"191-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back"],"prefix":"10.1007","volume":"61","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1144-3179","authenticated-orcid":false,"given":"Leopoldo","family":"Bertossi","sequence":"first","affiliation":[]},{"given":"Babak","family":"Salimi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,25]]},"reference":[{"key":"9718_CR1","doi-asserted-by":"crossref","unstructured":"Afrati, F., Kolaitis, P.: Repair checking in inconsistent databases: Algorithms and complexity. Proc. ICDT, 31\u201341 (2009)","DOI":"10.1145\/1514894.1514899"},{"key":"9718_CR2","doi-asserted-by":"crossref","unstructured":"Arenas, M., Bertossi, L., Chomicki, J.: Consistent query answers in inconsistent databases. Proc. ACM PODS, 68\u201379 (1999)","DOI":"10.1145\/303976.303983"},{"issue":"4\u20135","key":"9718_CR3","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1017\/S1471068403001832","volume":"3","author":"M Arenas","year":"2003","unstructured":"Arenas, M., Bertossi, L., Chomicki, J.: Answer sets for consistent query answers. Theory Pract. Logic Programm. 3(4\u20135), 393\u2013424 (2003)","journal-title":"Theory Pract. Logic Programm."},{"key":"9718_CR4","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1016\/S0304-3975(02)00737-5","volume":"296","author":"M Arenas","year":"2003","unstructured":"Arenas, M., Bertossi, L., Chomicki, J., He, X., Raghavan, V., Spinrad, J.: Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 296, 405\u2013434 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9718_CR5","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1613\/jair.1322","volume":"21","author":"O Arieli","year":"2004","unstructured":"Arieli, O., Denecker, M., Van Nuffelen, B., Bruynooghe, M.: Coherent integration of databases by abductive logic programming. J. Artif Intell. Res. 21, 245\u2013286 (2004)","journal-title":"J. Artif Intell. Res."},{"key":"9718_CR6","doi-asserted-by":"crossref","unstructured":"Barcelo, P., Bertossi, L., Bravo, L.: Characterizing and computing semantically correct answers from databases with annotated logic and answer sets. in semantics of databases. In: Semantics of Databases, Springer LNCS 2582, pp 1\u201327 (2003)","DOI":"10.1007\/3-540-36596-6_2"},{"issue":"2","key":"9718_CR7","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/1147376.1147391","volume":"35","author":"L Bertossi","year":"2006","unstructured":"Bertossi, L.: Consistent query answering in databases. ACM SIGMOD Rec. 35(2), 68\u201376 (2006)","journal-title":"ACM SIGMOD Rec."},{"issue":"5","key":"9718_CR8","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1109\/TKDE.2012.86","volume":"25","author":"L Bertossi","year":"2013","unstructured":"Bertossi, L., Li, L.: Achieving data privacy through secrecy views and null-based virtual updates. IEEE Trans Knowl. Data Eng. 25(5), 987\u20131000 (2013)","journal-title":"IEEE Trans Knowl. Data Eng."},{"key":"9718_CR9","doi-asserted-by":"crossref","unstructured":"Bertossi, L.: Database repairing and consistent query answering, Morgan & Claypool, Synthesis Lectures on Data Management (2011)","DOI":"10.2200\/S00379ED1V01Y201108DTM020"},{"key":"9718_CR10","unstructured":"Bertossi, L., Salimi, B.: Unifying causality, diagnosis, repairs and view-updates in databases. Presented at the First International Workshop on Big Uncertain Data (BUDA 2014). Posted at: arXiv: http:\/\/arXiv.org\/abs\/1405.4228 [cs.DB]"},{"key":"9718_CR11","doi-asserted-by":"crossref","unstructured":"Brankovic, L., Fernau, H.H.: Parameterized approximation algorithms for hitting set. In: Approximation and Online Algorithms, pp 63\u201376. Springer LNCS 7164 (2012)","DOI":"10.1007\/978-3-642-29116-6_6"},{"key":"9718_CR12","doi-asserted-by":"crossref","unstructured":"Bravo, L., Bertossi, L.: Semantically correct query answers in the presence of null values. In: Chomicki, J., Wijsen, J. (eds.) Proceedings EDBT WS on Inconsistency and Incompleteness in Databases (IIDB 06), pp 336\u2013357. Springer LNCS 4254 (2006)","DOI":"10.1007\/11896548_27"},{"key":"9718_CR13","doi-asserted-by":"crossref","unstructured":"Buneman, P., Khanna, S., Tan, W.C.: Why and where: A characterization of data provenance. Proc. ICDT, 316\u2013330 (2001)","DOI":"10.1007\/3-540-44503-X_20"},{"key":"9718_CR14","doi-asserted-by":"crossref","unstructured":"Buneman, P., Tan, W.C.: Provenance in databases. Proc. ACM SIGMOD, 1171\u20131173 (2007)","DOI":"10.1145\/1247480.1247646"},{"issue":"4","key":"9718_CR15","doi-asserted-by":"crossref","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\u2013474 (2009)","journal-title":"Found. Trends Databases"},{"key":"9718_CR16","doi-asserted-by":"crossref","unstructured":"Cheney, J., Chong, S., Foster, N., Seltzer, M.I., Vansummeren, S.: Provenance a future history. OOPSLA Companion (Onward!), 957\u2013964 (2009)","DOI":"10.1145\/1639950.1640064"},{"key":"9718_CR17","doi-asserted-by":"crossref","unstructured":"Cheney, J.: Is Provenance Logical?. Proc. LID, 2\u20136 (2011)","DOI":"10.1145\/1966357.1966359"},{"issue":"1-2","key":"9718_CR18","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1016\/j.ic.2004.04.007","volume":"197","author":"J Chomicki","year":"2005","unstructured":"Chomicki, J., Marcinkowski, J.: Minimal-change integrity maintenance using tuple deletions. Inf. Comput. 197(1-2), 90\u2013121 (2005)","journal-title":"Inf. Comput."},{"key":"9718_CR19","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.1391","volume":"22","author":"H Chockler","year":"2004","unstructured":"Chockler, H., Halpern, J.Y.: Responsibility and blame: a structural-model approach. J. Artif. Intell. Res. 22, 93\u2013115 (2004)","journal-title":"J. Artif. Intell. Res."},{"key":"9718_CR20","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1111\/j.1467-8640.1991.tb00388.x","volume":"7","author":"L Console","year":"1991","unstructured":"Console, L., Torasso, P.: A spectrum of logical definitions of model-based diagnosis. Comput. Intell. 7, 133\u2013141 (1991)","journal-title":"Comput. Intell."},{"issue":"3","key":"9718_CR21","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF00961655","volume":"4","author":"L Console","year":"1995","unstructured":"Console, L., Sapino, M.L., Theseider-Dupre, D.: The role of abduction in database view updating. J. Intell. Inf. Syst. 4(3), 261\u2013280 (1995)","journal-title":"J. Intell. Inf. Syst."},{"issue":"2","key":"9718_CR22","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1145\/357775.357777","volume":"25","author":"Y Cui","year":"2000","unstructured":"Cui, Y., Widom, J., Wiener, J.L.: Tracing the lineage of view data in a warehousing environment. ACM Trans. Database Syst. 25(2), 179\u2013227 (2000)","journal-title":"ACM Trans. Database Syst."},{"issue":"1-2","key":"9718_CR23","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/S0304-3975(96)00179-X","volume":"189","author":"T Eiter","year":"1997","unstructured":"Eiter, T., Gottlob, G., Leone, N.: Abduction from logic programs semantics and complexity. Theor. Comput. Sci. 189(1-2), 129\u2013177 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"9718_CR24","first-page":"99","volume":"12","author":"Th Eiter","year":"1999","unstructured":"Eiter, T. h., Faber, W., Leone, N., Pfeifer, G.: The diagnosis frontend of the DLV system. AI Commun. 12(1-2), 99\u2013111 (1999)","journal-title":"AI Commun."},{"key":"9718_CR25","doi-asserted-by":"crossref","unstructured":"Fagin, R., Kimelfeld, B., Kolaitis, Ph.: Dichotomies in the complexity of preferred repairs. Proc. ACM PODS, 3\u201315 (2015)","DOI":"10.1145\/2745754.2745762"},{"issue":"14","key":"9718_CR26","doi-asserted-by":"crossref","first-page":"3157","DOI":"10.1080\/00207160903176868","volume":"87","author":"H Fernau","year":"2010","unstructured":"Fernau, H.: Parameterized algorithmics for d-hitting set. Int. J. Comput. Math. 87(14), 3157\u20133174 (2010)","journal-title":"Int. J. Comput. Math."},{"issue":"14","key":"9718_CR27","first-page":"3157","volume":"87","author":"A Feldman","year":"2010","unstructured":"Feldman, A., Provan, G., Gemund, A.V.: Approximate model-based diagnosis using greedy stochastic search. J. Artif. Intell. Res. (JAIR) 87(14), 3157\u20133174 (2010)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"9718_CR28","unstructured":"Flum, J., Grohe, M.: Parameterized complexity theory. Texts in Theoretical Computer Science, Springer Verlag (2006)"},{"key":"9718_CR29","unstructured":"Garey, M., Johnson, D.S.: Computers and intractability: a guide to the theory of NP-completenes. W. H. Freeman (1979)"},{"key":"9718_CR30","unstructured":"Gertz, M.: Diagnosis and repair of constraint violations in database systems. PhD Thesis, Universit\u00e4t Hannover (1996)"},{"issue":"5","key":"9718_CR31","first-page":"353","volume":"7","author":"S Greco","year":"2014","unstructured":"Greco, S., Pijcke, F., Wijsen, J.: Certain query answering in partially consistent databases. PVLDB 7(5), 353\u2013364 (2014)","journal-title":"PVLDB"},{"key":"9718_CR32","unstructured":"Halpern, J., Pearl, J.: Causes and explanations: a structural-model approach: part 1. Proc. UAI, 194\u2013202 (2001)"},{"key":"9718_CR33","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1093\/bjps\/axi147","volume":"56","author":"J Halpern","year":"2005","unstructured":"Halpern, J., Pearl, J.: Causes and explanations: a structural-model approach: part 1. British J. Philos. Sci. 56, 843\u2013887 (2005)","journal-title":"British J. Philos. Sci."},{"key":"9718_CR34","unstructured":"Halperin, E.: Improved approximation algorithms for the vertex cover problem in graphs and hyper-graphs. Proceedings ACM-SIAM Symposium on Discrete Algorithms, 329\u2013337 (2000)"},{"key":"9718_CR35","unstructured":"Halpern, J.: Appropriate causal models and stability of causation. Proc. KR\u201914 (2014)"},{"key":"9718_CR36","doi-asserted-by":"crossref","unstructured":"Halpern, J.: A modification of Halpern-Pearl definition of causality. Proc. IJCAI (2015)","DOI":"10.7551\/mitpress\/9780262035026.003.0002"},{"key":"9718_CR37","unstructured":"Kakas A. C., Mancarella, P.: Database updates through abduction. Proc. VLDB, 650\u2013661 (1990)"},{"issue":"3","key":"9718_CR38","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1145\/2380776.2380778","volume":"41","author":"G Karvounarakis","year":"2012","unstructured":"Karvounarakis, G., Green, T.J.: Semiring-annotated data queries and provenance? SIGMOD Rec. 41(3), 5\u201314 (2012)","journal-title":"SIGMOD Rec."},{"key":"9718_CR39","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M Krentel","year":"1988","unstructured":"Krentel, M.: The complexity of optimization problems. J. Comput. Syst. 36, 490\u2013509 (1988)","journal-title":"J. Comput. Syst."},{"key":"9718_CR40","doi-asserted-by":"crossref","unstructured":"Karvounarakis, G., Ives Z. G., Tannen, V.: Querying provenance. Proc. ACM SIGMOD, 951\u2013962 (2010)","DOI":"10.1145\/1807167.1807269"},{"key":"9718_CR41","doi-asserted-by":"crossref","unstructured":"Kimelfeld, B.: A dichotomy in the complexity of deletion propagation with functional dependencies. Proc. ACM PODS (2012)","DOI":"10.1145\/2213556.2213584"},{"issue":"4","key":"9718_CR42","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/2389241.2389243","volume":"37","author":"B Kimelfeld","year":"2012","unstructured":"Kimelfeld, B., Vondrak, J., Williams, R.: Maximizing conjunctive views in deletion propagation. ACM Trans. Database Syst. 37(4), 24 (2012)","journal-title":"ACM Trans. Database Syst."},{"key":"9718_CR43","doi-asserted-by":"crossref","unstructured":"Lopatenko, A., Bertossi, L.: Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. Proc. ICDT, 2007, Springer LNCS 4353, pp. 179\u2013193. Proofs of results are found in [44]","DOI":"10.1007\/11965893_13"},{"key":"9718_CR44","unstructured":"Lopatenko, A., Bertossi, L.: Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. Extended version of [43], including proofs. Posted at: arXiv: http:\/\/arXiv.org\/abs\/cs\/1605.07159 [cs.DB]"},{"issue":"12","key":"9718_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\u20131493 (2011)","journal-title":"PVLDB"},{"key":"9718_CR46","unstructured":"Meliou, A., Gatterbauer, W., Suciu, D.: Bringing provenance to its full potential using causal reasoning. Proc. TaPP (2011)"},{"key":"9718_CR47","doi-asserted-by":"crossref","unstructured":"Meliou, A., Gatterbauer, W., Moore K. F., Suciu, D.: The complexity of causality and responsibility for query answers and non-answers. Proc. VLDB, 34\u201341 (2010)","DOI":"10.14778\/1880172.1880176"},{"issue":"3","key":"9718_CR48","first-page":"59","volume":"33","author":"A Meliou","year":"2010","unstructured":"Meliou, A., Gatterbauer, W., Halpern, J.Y., Koch, C., Moore K. F., Suciu, D.: Causality in databases. IEEE Data Eng. Bull. 33(3), 59\u201367 (2010)","journal-title":"IEEE Data Eng. Bull."},{"issue":"1-4","key":"9718_CR49","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/BF01530747","volume":"11","author":"I Mozetic","year":"1994","unstructured":"Mozetic, I., Holzbaur, C.: Controlling the complexity in model-based diagnosis. Ann. Math. Artif. Intell. 11(1-4), 297\u2013314 (1994)","journal-title":"Ann. Math. Artif. Intell."},{"issue":"1","key":"9718_CR50","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/S1570-8667(03)00009-1","volume":"1","author":"R Niedermeier","year":"2003","unstructured":"Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-hitting set. J Discret. Algorithm. 1(1), 89\u2013102 (2003)","journal-title":"J Discret. Algorithm."},{"issue":"1","key":"9718_CR51","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/j.disopt.2004.11.002","volume":"2","author":"M Okun","year":"2005","unstructured":"Okun, M.: On approximation of the vertex cover problem in hypergraphs. Discret. Optim. 2(1), 101\u2013111 (2005)","journal-title":"Discret. Optim."},{"key":"9718_CR52","unstructured":"Papadimitriou, C.H.: Computational complexity. Addison-Wesley (1994)"},{"issue":"1","key":"9718_CR53","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(87)90062-2","volume":"32","author":"R Reiter","year":"1987","unstructured":"Reiter, R.: A theory of diagnosis from first principles. Artif. Intell. 32(1), 57\u201395 (1987)","journal-title":"Artif. Intell."},{"key":"9718_CR54","doi-asserted-by":"crossref","unstructured":"Reiter, R.: Towards a logical reconstruction of relational database theory. In: On Conceptual Modelling, pp 191\u2013233. Springer (1984)","DOI":"10.1007\/978-1-4612-5196-5_8"},{"key":"9718_CR55","unstructured":"Salimi, B., Bertossi, L.: Causality in databases: the diagnosis and repair connections. Presented at The 15th International Workshop on Non-Monotonic Reasoning (NMR 2014). Posted at: arXiv: 1404.6857 [cs.DB]"},{"key":"9718_CR56","unstructured":"Salimi, B., Bertossi, L.: Causes for query answers from databases, datalog abduction and view-updates: the presence of integrity constraints. Proc. FLAIRS, 2016. Posted as Corr arXiv: http:\/\/arXiv.org\/abs\/cs.DB\/1602.06458"},{"key":"9718_CR57","unstructured":"Salimi, B., Bertossi, L.: Query-answer causality in databases: abductive diagnosis and view-updates. In: Proceedings UAI Causal Inference Workshop, 2015. CEUR-WS Proceedings Vol-1504 (2015)"},{"key":"9718_CR58","unstructured":"Salimi, B., Bertossi, L.: From causes for database queries to repairs and model-based diagnosis and back. In: Proceedings 18th International Conference on Database Theory (ICDT 2015)"},{"issue":"2-3","key":"9718_CR59","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10472-012-9288-8","volume":"64","author":"S Staworko","year":"2012","unstructured":"Staworko, S., Chomicki, J., Marcinkowski, J.: Prioritized repairing and consistent query answering in relational databases. Ann. Math. Artif. Intell. 64(2-3), 209\u2013246 (2012)","journal-title":"Ann. Math. Artif. Intell."},{"key":"9718_CR60","doi-asserted-by":"crossref","unstructured":"Struss, P.: Model-based problem solving. In: Handbook of Knowledge Representation, chap. 10. Elsevier (2008)","DOI":"10.1016\/S1574-6526(07)03010-6"},{"key":"9718_CR61","doi-asserted-by":"crossref","unstructured":"Tannen, V.: Provenance propagation in complex queries. In: Buneman Festschrift, 2013, Springer LNCS 8000, pp. 483\u2013493","DOI":"10.1007\/978-3-642-41660-6_26"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9718-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9718-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9718-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,15]],"date-time":"2019-09-15T19:29:38Z","timestamp":1568575778000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9718-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,11,25]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["9718"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9718-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,11,25]]}}}