{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:11:16Z","timestamp":1760202676921},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2014,11,4]],"date-time":"2014-11-04T00:00:00Z","timestamp":1415059200000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00224-014-9586-0","type":"journal-article","created":{"date-parts":[[2014,11,3]],"date-time":"2014-11-03T06:31:53Z","timestamp":1414996313000},"page":"843-891","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["On the Data Complexity of Consistent Query Answering"],"prefix":"10.1007","volume":"57","author":[{"given":"Balder","family":"ten Cate","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ga\u00eblle","family":"Fontaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,4]]},"reference":[{"key":"9586_CR1","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley (1995)"},{"key":"9586_CR2","doi-asserted-by":"crossref","unstructured":"Afrati, F.N., Kolaitis, P.G.: Repair checking in inconsistent databases: Algorithms and complexity. In: ICDT, pp. 31\u201341 (2009)","DOI":"10.1145\/1514894.1514899"},{"key":"9586_CR3","doi-asserted-by":"crossref","unstructured":"Arenas, M., Bertossi, L.E.: On the decidability of consistent query answering. In: AMW (2010)","DOI":"10.1007\/978-0-387-39940-9_5021"},{"key":"9586_CR4","doi-asserted-by":"crossref","unstructured":"Arenas, M., Bertossi, L.E., Chomicki, J.: Consistent query answers in inconsistent databases. In: PODS, pp. 68\u201379 (1999)","DOI":"10.1145\/303976.303983"},{"key":"9586_CR5","doi-asserted-by":"crossref","unstructured":"B\u00e1r\u00e1ny, V., Gottlob, G., Otto, M.: Querying the guarded fragment. In: Proc. of LICS, pp. 1\u201310 (2010)","DOI":"10.1109\/LICS.2010.26"},{"key":"9586_CR6","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of dtds. J. ACM 55(2), (2008)","DOI":"10.1145\/1346330.1346333"},{"issue":"2","key":"9586_CR7","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/1147376.1147391","volume":"35","author":"LE Bertossi","year":"2006","unstructured":"Bertossi, L.E.: Consistent query answering in databases. SIGMOD Rec 35(2), 68\u201376 (2006)","journal-title":"SIGMOD Rec"},{"key":"9586_CR8","doi-asserted-by":"crossref","unstructured":"B\u00f6rger, E., Gr\u00e4del, E., Gurevich, Y.: The Classical Decision Problem. Perspectives in Mathematical Logic. Springer (1997)","DOI":"10.1007\/978-3-642-59207-2"},{"key":"9586_CR9","unstructured":"Bravo, L., Bertossi, L.E.: Consistent query answering under inclusion dependencies. In: CASCON, pp. 202\u2013216 (2004)"},{"key":"9586_CR10","unstructured":"Cal\u00ec, A., Gottlob, G., Kifer, M.: Taming the infinite chase: Query answering under expressive relational constraints. In: Brewka, G., Lang, J. (eds.) KR, pp. 70\u201380. AAAI Press (2008)"},{"key":"9586_CR11","doi-asserted-by":"crossref","unstructured":"Cal\u00ec, A., Lembo, D., Rosati, R.: On the decidability and complexity of query answering over inconsistent and incomplete databases. In: PODS, pp. 260\u2013271 (2003)","DOI":"10.1145\/773153.773179"},{"issue":"1","key":"9586_CR12","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1145\/1629175.1629201","volume":"53","author":"B ten Cate","year":"2010","unstructured":"ten Cate, B., Kolaitis, P.G.: Structural characterizations of schema-mapping languages. Commun. ACM 53(1), 101\u2013110 (2010)","journal-title":"Commun. ACM"},{"key":"9586_CR13","doi-asserted-by":"crossref","unstructured":"Chomicki, J.: Consistent query answering: Five easy pieces. In: ICDT, pp. 1\u201317 (2007)","DOI":"10.1007\/11965893_1"},{"issue":"1\u20132","key":"9586_CR14","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\u20132), 90\u2013121 (2005)","journal-title":"Inf. Comput."},{"key":"9586_CR15","doi-asserted-by":"crossref","unstructured":"Deutsch, A., Tannen, V.: Reformulation of XML queries and constraints. In: ICDT, pp. 225\u2013241 (2003)","DOI":"10.1007\/3-540-36285-1_15"},{"issue":"4","key":"9586_CR16","doi-asserted-by":"crossref","first-page":"952","DOI":"10.1145\/322344.322347","volume":"29","author":"R Fagin","year":"1982","unstructured":"Fagin, R.: Horn clauses and database dependencies. J. ACM 29(4), 952\u2013985 (1982)","journal-title":"J. ACM"},{"issue":"1","key":"9586_CR17","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.tcs.2004.10.033","volume":"336","author":"R Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: Semantics and query answering. Theor. Comput. Sci. 336(1), 89\u2013124 (2005)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9586_CR18","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1145\/1061318.1061323","volume":"30","author":"R Fagin","year":"2005","unstructured":"Fagin, R., Kolaitis, P. G., Popa, L.: Data exchange: Getting to the core. TODS 30(1), 174\u2013210 (2005)","journal-title":"TODS"},{"key":"9586_CR19","doi-asserted-by":"crossref","unstructured":"Fontaine, G.: Why is it hard to obtain a dichotomy for consistent query answering? In: LICS. To appear (2013)","DOI":"10.1109\/LICS.2013.62"},{"issue":"4","key":"9586_CR20","doi-asserted-by":"crossref","first-page":"1454","DOI":"10.1145\/1189769.1189778","volume":"31","author":"A Fuxman","year":"2006","unstructured":"Fuxman, A., Kolaitis, P.G., Miller, R.J., Chiew Tan, W.: Peer data exchange. ACM Trans. Database Syst. 31(4), 1454\u20131498 (2006)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"9586_CR21","doi-asserted-by":"crossref","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"9586_CR22","volume-title":"Computers and Intractability; A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1990","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)"},{"issue":"2","key":"9586_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1346330.1346334","volume":"55","author":"G Gottlob","year":"2008","unstructured":"Gottlob, G., Nash, A.: Efficient core computation in data exchange. J. ACM 55(2), 1\u201349 (2008)","journal-title":"J. ACM"},{"key":"9586_CR24","doi-asserted-by":"crossref","unstructured":"Grahne, G., Onet, A.: Data correspondence, exchange and repair. In: ICDT, pp. 219\u2013230 (2010)","DOI":"10.1145\/1804669.1804698"},{"key":"9586_CR25","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0012-365X(92)90282-K","volume":"109","author":"P Hell","year":"1992","unstructured":"Hell, P., Ne\u0161et\u0159il, J.: The core of a graph. Discret. Math 109, 117\u2013126 (1992)","journal-title":"Discret. Math"},{"key":"9586_CR26","unstructured":"Hernich, A.: Foundations of Query Answering in Relational Data Exchange. PhD thesis, Goethe-Universit\u00e4t Frankfurt am Main (2010)"},{"key":"9586_CR27","doi-asserted-by":"crossref","unstructured":"Hernich, A., Schweikardt, N.: CWA-solutions for data exchange settings with target dependencies. In: PODS, pp. 113\u2013122 (2007)","DOI":"10.1145\/1265530.1265547"},{"key":"9586_CR28","doi-asserted-by":"crossref","unstructured":"Kolaitis, P.G., Panttaja, J., Tan, W.-C.: The complexity of data exchange. In: Proceedings of PODS\u201906, pp. 30\u201339 (2006)","DOI":"10.1145\/1142351.1142357"},{"issue":"3","key":"9586_CR29","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/j.ipl.2011.10.018","volume":"112","author":"PG Kolaitis","year":"2012","unstructured":"Kolaitis, P.G., Pema, E.: A dichotomy in the complexity of consistent query answering for queries with two atoms. Inf. Process. Lett. 112(3), 77\u201385 (2012)","journal-title":"Inf. Process. Lett."},{"key":"9586_CR30","volume-title":"Computational Complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"issue":"3","key":"9586_CR31","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1016\/j.jcss.2010.04.011","volume":"77","author":"R Rosati","year":"2011","unstructured":"Rosati, R.: On the finite controllability of conjunctive query answering in databases under open-world assumption. J. Comput. Syst. Sci. 77(3), 572\u2013594 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9586_CR32","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.is.2009.03.004","volume":"35","author":"S Staworko","year":"2010","unstructured":"Staworko, S., Chomicki, J.: Consistent query answers in the presence of universal constraints. Inf. Syst 35(1), 1\u201322 (2010)","journal-title":"Inf. Syst"},{"key":"9586_CR33","first-page":"22","volume-title":"On the data complexity of consistent query answering. In: Proceedings of the 15th International Conference on Database Theory, ICDT \u201912","author":"B ten Cate","year":"2012","unstructured":"ten Cate, B., Fontaine, G., Kolaitis, P.G.: On the data complexity of consistent query answering. In: Proceedings of the 15th International Conference on Database Theory, ICDT \u201912, pp 22\u201333. ACM, New York (2012)"},{"key":"9586_CR34","doi-asserted-by":"crossref","unstructured":"Vardi, M.Y.: The complexity of relational query languages (extended abstract). In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 137\u2013146 (1982)","DOI":"10.1145\/800070.802186"},{"key":"9586_CR35","doi-asserted-by":"crossref","first-page":"722","DOI":"10.1145\/1093382.1093385","volume":"30","author":"J Wijsen","year":"2005","unstructured":"Wijsen, J.: Database repairing using updates. ACM Trans. Database Syst. 30, 722\u2013768 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"9586_CR36","doi-asserted-by":"crossref","unstructured":"Wijsen, J.: On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In: PODS, pp. 179\u2013190 (2010)","DOI":"10.1145\/1807085.1807111"},{"issue":"21","key":"9586_CR37","doi-asserted-by":"crossref","first-page":"950","DOI":"10.1016\/j.ipl.2010.07.021","volume":"110","author":"J Wijsen","year":"2010","unstructured":"Wijsen, J.: A remark on the complexity of consistent conjunctive query answering under primary key violations. Inf. Process. Lett. 110(21), 950\u2013955 (2010)","journal-title":"Inf. Process. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9586-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9586-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9586-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,26]],"date-time":"2020-08-26T10:34:26Z","timestamp":1598438066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9586-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,4]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9586"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9586-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,4]]}}}