{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T23:29:09Z","timestamp":1774913349116,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T00:00:00Z","timestamp":1593475200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00224-020-09985-6","type":"journal-article","created":{"date-parts":[[2020,6,30]],"date-time":"2020-06-30T10:03:46Z","timestamp":1593511426000},"page":"122-178","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Consistent Query Answering for Primary Keys in Datalog"],"prefix":"10.1007","volume":"65","author":[{"given":"Paraschos","family":"Koutris","sequence":"first","affiliation":[]},{"given":"Jef","family":"Wijsen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,6,30]]},"reference":[{"key":"9985_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). http:\/\/webdam.inria.fr\/Alice\/"},{"key":"9985_CR2","doi-asserted-by":"publisher","unstructured":"Arenas, M., Bertossi, L. E., Chomicki, J.: Consistent query answers in inconsistent databases. In: ACM PODS, pp. 68\u201379. https:\/\/doi.org\/10.1145\/303976.303983 (1999)","DOI":"10.1145\/303976.303983"},{"issue":"3","key":"9985_CR3","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1016\/S0304-3975(02)00737-5","volume":"296","author":"M Arenas","year":"2003","unstructured":"Arenas, M., Bertossi, L. E., Chomicki, J., He, X., Raghavan, V., Spinrad, J. P.: Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 296(3), 405\u2013434 (2003). https:\/\/doi.org\/10.1016\/S0304-3975(02)00737-5","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9985_CR4","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M. F., Tarjan, R. E.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett. 8 (3), 121\u2013123 (1979). https:\/\/doi.org\/10.1016\/0020-0190(79)90002-4","journal-title":"Inf. Process. Lett."},{"key":"9985_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/9781139025355","volume-title":"An introduction to description logic","author":"F Baader","year":"2017","unstructured":"Baader, F., Horrocks, I., Lutz, C., Sattler, U.: An introduction to description logic. Cambridge University Press, Cambridge (2017). http:\/\/www.cambridge.org\/de\/academic\/subjects\/computer-science\/knowledge-management-databases-and-data-mining\/introduction-description-logic?format=PB#17zVGeWD2TZUeu6s.97"},{"key":"9985_CR6","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1016\/j.jcss.2017.03.015","volume":"88","author":"P Barcel\u00f3","year":"2017","unstructured":"Barcel\u00f3, P., Fontaine, G.: On the data complexity of consistent query answering over graph databases. J. Comput. Syst. Sci. 88, 164\u2013194 (2017). https:\/\/doi.org\/10.1016\/j.jcss.2017.03.015","journal-title":"J. Comput. Syst. Sci."},{"key":"9985_CR7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-01883-1","volume-title":"Database repairing and consistent query answering. Synthesis lectures on data management","author":"LE Bertossi","year":"2011","unstructured":"Bertossi, L. E.: Database repairing and consistent query answering. Synthesis lectures on data management. Morgan & Claypool Publishers, San Rafael (2011)"},{"key":"9985_CR8","doi-asserted-by":"publisher","unstructured":"Bertossi, L. E.: Database repairs and consistent query answering: Origins and further developments. In: Suciu, D., Skritek, S., Koch, C. (eds.) Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2019, Amsterdam, The Netherlands, June 30 - July 5, 2019. https:\/\/doi.org\/10.1145\/3294052.3322190, pp 48\u201358. ACM (2019)","DOI":"10.1145\/3294052.3322190"},{"key":"9985_CR9","doi-asserted-by":"publisher","unstructured":"Bienvenu, M., Bourgaux, C.: Inconsistency-tolerant querying of description logic knowledge bases. In: Pan, J.Z., Calvanese, D., Eiter, T., Horrocks, I., Kifer, M., Lin, F., Zhao, Y. (eds.) Reasoning Web: Logical foundation of knowledge graph construction and query answering - 12th International Summer School 2016, Aberdeen, UK, September 5-9, 2016, Tutorial lectures, Lecture notes in computer science. https:\/\/doi.org\/10.1007\/978-3-319-49493-7_5, vol. 9885, pp 156\u2013202. Springer (2016)","DOI":"10.1007\/978-3-319-49493-7_5"},{"issue":"4","key":"9985_CR10","doi-asserted-by":"publisher","first-page":"24:1","DOI":"10.1145\/1970398.1970400","volume":"12","author":"AA Bulatov","year":"2011","unstructured":"Bulatov, A. A.: Complexity of conservative constraint satisfaction problems. ACM Trans. Comput. Log. 12(4), 24:1\u201324:66 (2011). https:\/\/doi.org\/10.1145\/1970398.1970400","journal-title":"ACM Trans. Comput. Log."},{"key":"9985_CR11","doi-asserted-by":"publisher","unstructured":"Dixit, A. A., Kolaitis, P. G.: A SAT-based system for consistent query answering. In: Janota, M., Lynce, I. (eds.) Theory and Applications of Satisfiability Testing - SAT 2019 - 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11628, pp 117\u2013135. Springer (2019), https:\/\/doi.org\/10.1007\/978-3-030-24258-9_8","DOI":"10.1007\/978-3-030-24258-9_8"},{"key":"9985_CR12","doi-asserted-by":"publisher","unstructured":"Egri, L., Larose, B., Tesson, P.: Symmetric Datalog and constraint satisfaction problems in Logspace. In: LICS, pp. 193\u2013202. https:\/\/doi.org\/10.1109\/LICS.2007.47 (2007)","DOI":"10.1109\/LICS.2007.47"},{"issue":"1","key":"9985_CR13","doi-asserted-by":"publisher","first-page":"7:1","DOI":"10.1145\/2699912","volume":"16","author":"G Fontaine","year":"2015","unstructured":"Fontaine, G.: Why is it hard to obtain a dichotomy for consistent query answering? ACM Trans. Comput. Log. 16 (1), 7:1\u20137:24 (2015). https:\/\/doi.org\/10.1145\/2699912","journal-title":"ACM Trans. Comput. Log."},{"key":"9985_CR14","doi-asserted-by":"publisher","unstructured":"Fuxman, A., Miller, R. J.: First-order query rewriting for inconsistent databases. In: ICDT, pp 337\u2013351 (2005), https:\/\/doi.org\/10.1007\/978-3-540-30570-5_23","DOI":"10.1007\/978-3-540-30570-5_23"},{"issue":"4","key":"9985_CR15","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1016\/j.jcss.2006.10.013","volume":"73","author":"A Fuxman","year":"2007","unstructured":"Fuxman, A., Miller, R. J.: First-order query rewriting for inconsistent databases. J. Comput. Syst. Sci. 73(4), 610\u2013635 (2007). https:\/\/doi.org\/10.1016\/j.jcss.2006.10.013","journal-title":"J. Comput. Syst. Sci."},{"key":"9985_CR16","doi-asserted-by":"publisher","unstructured":"Gr\u00e4del, E., Kolaitis, P. G., Libkin, L., Marx, M., Spencer, J., Vardi, M. Y., Venema, Y., Weinstein, S.: Finite model theory and its applications. Texts in theoretical computer science. An EATCS series springer. https:\/\/doi.org\/10.1007\/3-540-68804-8 (2007)","DOI":"10.1007\/3-540-68804-8"},{"issue":"5","key":"9985_CR17","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). http:\/\/www.vldb.org\/pvldb\/vol7\/p353-greco.pdf","journal-title":"PVLDB"},{"issue":"1","key":"9985_CR18","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1145\/343369.343386","volume":"1","author":"M Grohe","year":"2000","unstructured":"Grohe, M., Schwentick, T.: Locality of order-invariant first-order formulas. ACM Trans. Comput. Log. 1(1), 112\u2013130 (2000). https:\/\/doi.org\/10.1145\/343369.343386","journal-title":"ACM Trans. Comput. Log."},{"issue":"6","key":"9985_CR19","first-page":"397","volume":"6","author":"PG Kolaitis","year":"2013","unstructured":"Kolaitis, P.G., Pema, E., Tan, W.: Efficient querying of inconsistent databases with binary integer programming. PVLDB 6(6), 397\u2013408 (2013). http:\/\/www.vldb.org\/pvldb\/vol6\/p397-tan.pdf","journal-title":"PVLDB"},{"key":"9985_CR20","doi-asserted-by":"publisher","unstructured":"Koutris, P., Wijsen, J.: The data complexity of consistent query answering for self-join-free conjunctive queries under primary key constraints. In: PODS. https:\/\/doi.org\/10.1145\/2745754.2745769, pp 17\u201329 (2015)","DOI":"10.1145\/2745754.2745769"},{"issue":"2","key":"9985_CR21","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/3068334","volume":"42","author":"P Koutris","year":"2017","unstructured":"Koutris, P., Wijsen, J.: Consistent query answering for self-join-free conjunctive queries under primary key constraints. ACM Trans. Database Syst. 42 (2), 9:1\u20139:45 (2017). https:\/\/doi.org\/10.1145\/3068334","journal-title":"ACM Trans. Database Syst."},{"key":"9985_CR22","doi-asserted-by":"publisher","unstructured":"Koutris, P., Wijsen, J.: Consistent query answering for primary keys and conjunctive queries with negated atoms. In: PODS, pp 209\u2013224 (2018), https:\/\/doi.org\/10.1145\/3196959.3196982","DOI":"10.1145\/3196959.3196982"},{"key":"9985_CR23","doi-asserted-by":"publisher","unstructured":"Koutris, P., Wijsen, J.: Consistent query answering for primary keys in logspace. In: Barcel\u00f3, P., Calautti, M. (eds.) 22nd International Conference on Database Theory, ICDT 2019, March 26-28, 2019, Lisbon, Portugal, LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, vol. 127, pp 23:1\u201323:19 (2019), https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2019.23","DOI":"10.4230\/LIPIcs.ICDT.2019.23"},{"key":"9985_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.websem.2015.04.002","volume":"33","author":"D Lembo","year":"2015","unstructured":"Lembo, D., Lenzerini, M., Rosati, R., Ruzzi, M., Savo, D. F.: Inconsistency-tolerant query answering in ontology-based data access. J. Web Sem. 33, 3\u201329 (2015). https:\/\/doi.org\/10.1016\/j.websem.2015.04.002","journal-title":"J. Web Sem."},{"key":"9985_CR25","doi-asserted-by":"publisher","unstructured":"Libkin, L.: Elements of finite model theory. Texts in theoretical computer science. An EATCS series springer. https:\/\/doi.org\/10.1007\/978-3-662-07003-1 (2004)","DOI":"10.1007\/978-3-662-07003-1"},{"key":"9985_CR26","doi-asserted-by":"publisher","unstructured":"Lincoln, A., Williams, V. V., Williams, R. R.: Tight hardness for shortest cycles and paths in sparse graphs. In: ACM-SIAM SODA. https:\/\/doi.org\/10.1137\/1.9781611975031.80, pp 1236\u20131252 (2018)","DOI":"10.1137\/1.9781611975031.80"},{"key":"9985_CR27","doi-asserted-by":"publisher","unstructured":"Lutz, C., Wolter, F.: On the relationship between consistent query answering and constraint satisfaction problems. In: ICDT. https:\/\/doi.org\/10.4230\/LIPIcs.ICDT.2015.363, pp 363\u2013379 (2015)","DOI":"10.4230\/LIPIcs.ICDT.2015.363"},{"issue":"6","key":"9985_CR28","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/j.datak.2010.01.005","volume":"69","author":"MC Marileo","year":"2010","unstructured":"Marileo, M. C., Bertossi, L. E.: The consistency extractor system: Answer set programs for consistent query answering in databases. Data Knowl. Eng. 69(6), 545\u2013572 (2010). https:\/\/doi.org\/10.1016\/j.datak.2010.01.005","journal-title":"Data Knowl. Eng."},{"issue":"6","key":"9985_CR29","doi-asserted-by":"publisher","first-page":"958","DOI":"10.1016\/j.jcss.2013.01.011","volume":"79","author":"D Maslowski","year":"2013","unstructured":"Maslowski, D., Wijsen, J.: A dichotomy in the complexity of counting database repairs. J. Comput. Syst. Sci. 79(6), 958\u2013983 (2013). https:\/\/doi.org\/10.1016\/j.jcss.2013.01.011","journal-title":"J. Comput. Syst. Sci."},{"key":"9985_CR30","doi-asserted-by":"publisher","unstructured":"Maslowski, D., Wijsen, J.: Counting database repairs that satisfy conjunctive queries with self-joins. In: ICDT, pp 155\u2013164 (2014), https:\/\/doi.org\/10.5441\/002\/icdt.2014.18","DOI":"10.5441\/002\/icdt.2014.18"},{"key":"9985_CR31","unstructured":"Pijcke, F.: Theoretical and practical methods for consistent query answering in the relational data model. Ph.D. thesis, University of Mons (2018)"},{"key":"9985_CR32","doi-asserted-by":"publisher","unstructured":"Przymus, P., Boniewicz, A., Burzanska, M., Stencel, K.: Recursive query facilities in relational databases: a survey. In: FGIT. https:\/\/doi.org\/10.1007\/978-3-642-17622-7_10, pp 89\u201399 (2010)","DOI":"10.1007\/978-3-642-17622-7_10"},{"issue":"4","key":"9985_CR33","doi-asserted-by":"publisher","first-page":"17:1","DOI":"10.1145\/1391289.1391291","volume":"55","author":"O Reingold","year":"2008","unstructured":"Reingold, O.: Undirected connectivity in log-space. J. ACM 55 (4), 17:1\u201317:24 (2008). https:\/\/doi.org\/10.1145\/1391289.1391291","journal-title":"J. ACM"},{"key":"9985_CR34","doi-asserted-by":"publisher","unstructured":"Wijsen, J.: On the First-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In: PODS. https:\/\/doi.org\/10.1145\/1807085.1807111, pp 179\u2013190 (2010)","DOI":"10.1145\/1807085.1807111"},{"issue":"2","key":"9985_CR35","doi-asserted-by":"publisher","first-page":"9:1","DOI":"10.1145\/2188349.2188351","volume":"37","author":"J Wijsen","year":"2012","unstructured":"Wijsen, J.: Certain conjunctive query answering in first-order logic. ACM Trans. Database Syst. 37(2), 9:1\u20139:35 (2012). https:\/\/doi.org\/10.1145\/2188349.2188351","journal-title":"ACM Trans. Database Syst."},{"key":"9985_CR36","doi-asserted-by":"publisher","unstructured":"Wijsen, J.: A survey of the data complexity of consistent query answering under key constraints. In: FoIKS. https:\/\/doi.org\/10.1007\/978-3-319-04939-7_2, pp 62\u201378 (2014)","DOI":"10.1007\/978-3-319-04939-7_2"},{"issue":"3","key":"9985_CR37","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1145\/3377391.3377393","volume":"48","author":"J Wijsen","year":"2019","unstructured":"Wijsen, J.: Foundations of query answering on inconsistent databases. SIGMOD Rec. 48(3), 6\u201316 (2019). https:\/\/doi.org\/10.1145\/3377391.3377393","journal-title":"SIGMOD Rec."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09985-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-020-09985-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-020-09985-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,31]],"date-time":"2022-10-31T05:26:31Z","timestamp":1667193991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-020-09985-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,30]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["9985"],"URL":"https:\/\/doi.org\/10.1007\/s00224-020-09985-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,30]]},"assertion":[{"value":"30 June 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}